非線性方程的求根方法

非線性方程的求根方法1第1頁，共50頁，2023年，2月20日，星期四BisectionMethod方程求根的二分法Fixed-PointIteration迭代法及其收斂性NewtonMethodofNonlinearEquations

Newton迭代法2第2頁，共50頁，2023年，2月20日，星期四在實(shí)際應(yīng)用中有許多非線性方程的例子，例如（1）在光的衍射理論（thetheoryofdiffractionoflight)中,需要求x-tanx=0的根（2）在行星軌道（planetaryorbits）的計(jì)算中,對任意的a和b，需要求x-asinx=b的根（3）在數(shù)學(xué)中，需要求n次多項(xiàng)式xn+a1

xn-1+...+an-1x+an

＝0的根3第3頁，共50頁，2023年，2月20日，星期四方程求解是科學(xué)計(jì)算中一個(gè)重要的研究對象;幾百年前就已經(jīng)找到了代數(shù)方程中二次至五次方程的求解公式;但是,對于更高次數(shù)的代數(shù)方程目前仍無有效的精確解法;對于無規(guī)律的非代數(shù)方程的求解也無精確解法;因此,研究非線性方程的數(shù)值解法成為必然。4第4頁，共50頁，2023年，2月20日，星期四非線性方程的一般形式：f(x)=0代數(shù)方程：f(x)=a0+a1x+……+anxn

（an0）超越方程：f(x)中含三角函數(shù)、指數(shù)函數(shù)、或其他超越函數(shù)。用數(shù)值方法求解非線性方程的步驟：（1）找出有根區(qū)間；（只含一個(gè)實(shí)根的區(qū)間稱隔根區(qū)間）（2）近似根的精確化。從隔根區(qū)間內(nèi)的一個(gè)或多個(gè)點(diǎn)出發(fā)，逐次逼近，尋求滿足精度的根的近似值。5第5頁，共50頁，2023年，2月20日，星期四BisectionMethod二分法

二分法的基本思想： 假定f(x)=0在[a,b]內(nèi)有唯一單實(shí)根x*，考察有根區(qū)間[a,b]，取中點(diǎn)x0=(a+b)/2，若f(x0)=0，則x*=x0，否則，（1）若f(x0)f(a)>0，則x*在x0右側(cè)，令a1=x0，b1=b;（2）若f(x0)f(a)<0，則x*在x0左側(cè)，令a1=a，b1=x0。介值定理設(shè)函數(shù)f(x)在區(qū)間[a,b]連續(xù)，且f(a)f(b)<0，則方程f(x)=0在區(qū)間(a,b)內(nèi)至少有一個(gè)根。6第6頁，共50頁，2023年，2月20日，星期四以[a1,b1]為新的隔根區(qū)間，且僅為[a,b]的一半，對[a1,b1]重復(fù)前過程，得新的隔根區(qū)間[a2,b2]，如此二分下去，得一系列隔根區(qū)間：[a,b][a1,b1][a2,b2]……[ak,bk]……其中每個(gè)區(qū)間都是前一區(qū)間的一半，故[ak,bk]的長度：當(dāng)k趨于無窮時(shí)趨于0。即若二分過程無限繼續(xù)下去，這些區(qū)間最后必收斂于一點(diǎn)x*，即方程的根。7第7頁，共50頁，2023年，2月20日，星期四性質(zhì)：f(an)·f(bn)<0;bn–

an=(b–a)/2nBisectionMethod

每次二分后，取有根區(qū)間的中點(diǎn)xk=(ak+bk)/2作為根的近似值，則可得一近似根序列：x0,x1,x2,…該序列必以根x*為極限。 實(shí)際計(jì)算中，若給定充分小的正數(shù)0和允許誤差限1，當(dāng)|f(xn)|<0或bn-an<1時(shí)，均可取x*xn。8第8頁，共50頁，2023年，2月20日，星期四定理設(shè)x*為方程f(x)=0在[a,b]內(nèi)唯一根，且f(x)滿足f(a)f(b)<0，則由二分法產(chǎn)生的第n個(gè)區(qū)間[an,bn]的中點(diǎn)xn滿足不等式證明：9第9頁，共50頁，2023年，2月20日，星期四1.先驗(yàn)誤差估計(jì)：利用誤差估計(jì)定理，令得從而得到對分次數(shù)k，取xk作為根得近似值x*。2.后驗(yàn)誤差估計(jì)：給定ε，每步檢查，若成立，則取，否則繼續(xù)對分。10第10頁，共50頁，2023年，2月20日，星期四

例用二分法求

在(1,2)內(nèi)的根，要求絕對誤差不超過

解：f(1)=-5<0有根區(qū)間

中點(diǎn)f(2)=14>0-(1,2)+

f(1.25)<0(1.25,1.5)f(1.375)>0(1.25,1.375)f(1.313)<0(1.313,1.375)f(1.344)<0(1.344,1.375)f(1.360)<0(1.360,1.375)f(1.368)>0(1.360,1.368)

f(1.5)>0(1,1.5)11第11頁，共50頁，2023年，2月20日，星期四計(jì)算過程簡單，收斂性可保證；對函數(shù)的性質(zhì)要求低，只要連續(xù)即可。收斂速度慢；不能求復(fù)根和重根；調(diào)用一次求解一個(gè)[a,b]間的多個(gè)根無法求得。二分法求解非線性方程的優(yōu)缺點(diǎn)12第12頁，共50頁，2023年，2月20日，星期四不動點(diǎn)迭代法不動點(diǎn)的存在性與迭代法的收斂性迭代收斂的加速方法Fixed-PointIteration13第13頁，共50頁，2023年，2月20日，星期四迭代法的基本思想迭代法是一種逐次逼近的方法，用某個(gè)固定公式反復(fù)校正根的近似值，使之逐步精確化，最后得到滿足精度要求的結(jié)果。例：求方程x3-x-1=0在x=1.5附近的一個(gè)根。將所給方程改寫成假設(shè)初值x0=1.5是其根，代入得x1≠x0，再將x1代入得x2≠x1，再將x2代入得14第14頁，共50頁，2023年，2月20日，星期四如此下去，這種逐步校正的過程稱為迭代過程。這里用的公式稱為迭代公式，即

k=0,1,2,……迭代結(jié)果見下表。僅取六位數(shù)字，x7與x8相同，即認(rèn)為x8是方程的根。

x*≈x8=1.32472k

xkk

xk012341.51.357211.330861.325881.3249456781.324761.324731.324721.3247215第15頁，共50頁，2023年，2月20日，星期四將連續(xù)函數(shù)方程f(x)＝0改寫為等價(jià)形式：x=(x)其中(x)也是連續(xù)函數(shù)，稱為迭代函數(shù)。不動點(diǎn)：若x*滿足f(x*)=0，則x*=(x*)；反之，若x*=(x*)

，則f(x*)=0

，稱x*為(x)的一個(gè)不動點(diǎn)。不動點(diǎn)迭代：

(k=0,1,……)若對任意x0[a,b]，由上述迭代得序列{xk}，有極限則稱迭代過程收斂，且x*=(x*)為(x)的不動點(diǎn)。Fixed-PointIteration16第16頁，共50頁，2023年，2月20日，星期四迭代法并不總令人滿意，如將前述方程x3-x-1=0改寫為另一等價(jià)形式：建迭代公式：仍取初值x0=1.5，則有x1=2.375，x2=12.396，x3=1904,結(jié)果越來越大。此時(shí)稱迭代過程發(fā)散。x2

x1

x0y=x幾何意義：17第17頁，共50頁，2023年，2月20日，星期四xy0x2Px*P0x1x0P1P2Q0Q1Q2y=xy=(x)收斂的迭代法18第18頁，共50頁，2023年，2月20日，星期四發(fā)散的迭代法xy0x2Px*P0x1x0P1P2Q0Q1y=xy=(x)19第19頁，共50頁，2023年，2月20日，星期四Remark：可以通過不同的途徑將f(x)=0化為x=φ(x)的形式，從而構(gòu)造不同的迭代公式，得到不同的迭代序列。在所有這些構(gòu)造的迭代公式中形成的序列中，有的序列是收斂的，而有些是發(fā)散的。問題：如何選取合適的迭代函數(shù)φ(x)？ 迭代函數(shù)φ(x)應(yīng)滿足什么條件，序列{xk}收斂？ 怎樣加速序列{xk}的收斂？20第20頁，共50頁，2023年，2月20日，星期四定理（存在性）

設(shè)(x)C[a,b]且滿足以下兩個(gè)條件：（1）對于任意x[a,b]，有a≤(x)≤b；（2）若(x)在[a,b]一階連續(xù)，且存在常數(shù)0<L<1，使得對任意x[a,b]，成立

|’(x)|≤L則(x)在[a,b]上存在唯一的不動點(diǎn)x*。存在性與迭代法的收斂性21第21頁，共50頁，2023年，2月20日，星期四證若或,顯然有不動點(diǎn)設(shè),則有,記則有所以,存在x*,使得即,x*即為不動點(diǎn).22第22頁，共50頁，2023年，2月20日，星期四唯一性證明：設(shè)有x1*≠x2*,使得,,則其中,ξ介于x1*和x2*之間.由定理?xiàng)l件可得,矛盾,這說明只可能有x1*=x2*.23第23頁，共50頁，2023年，2月20日，星期四定理（全局收斂性）設(shè)(x)C[a,b]且滿足以下兩個(gè)條件：（1）對于任意x[a,b]，有a≤(x)≤b；（2）若(x)在[a,b]一階連續(xù)，且存在常數(shù)0<L<1，使得對任意x[a,b]，成立 |`(x)|≤L

則對任意x0[a,b]，由xn+1=(xn)得到的迭代序列{xn}收斂到(x)的不動點(diǎn)x*，并有誤差估計(jì)：24第24頁，共50頁，2023年，2月20日，星期四證明：(0<L<1)所以,故迭代格式收斂.25第25頁，共50頁，2023年，2月20日，星期四反復(fù)遞推，可得誤差估計(jì)式26第26頁，共50頁，2023年，2月20日，星期四定義設(shè)(x)有不動點(diǎn)x*，若存在x*的某鄰域R：|x-x*|≤，對任意x0R，迭代過程xk+1=(xk)產(chǎn)生的序列{xk}R且收斂到x*，則稱不動點(diǎn)迭代法xk+1=(xk)局部收斂。

注：定理給出的收斂性稱全局收斂性，實(shí)際應(yīng)用時(shí)通常只在不動點(diǎn)x*鄰近考察其收斂性，稱局部收斂性。27第27頁，共50頁，2023年，2月20日，星期四證明：根據(jù)連續(xù)函數(shù)性質(zhì)，因`(x)連續(xù)，存在x*的某鄰域R：|x-x*|≤，對任意x

R，|`(x)|≤L<1，且

|(x)-x*|=|(x)-(x*)|=|`(ξ)||x-x*|≤L|x-x*|≤|x-x*|≤即對任意x

R，總有(x)

R。由全局收斂性定義知，迭代過程xk+1=(xk)對于任意初值x0R均收斂。定理（局部收斂性）

設(shè)x*為(x)的不動點(diǎn)，`(x)在x*的某鄰域連續(xù)，且|`(x*)|<1，則不動點(diǎn)迭代法xk+1=(xk

)局部收斂。28第28頁，共50頁，2023年，2月20日，星期四例：用不同方法求 的根解：（1） （2） （3） （4）29第29頁，共50頁，2023年，2月20日，星期四取x0=2，對上述四種方法，計(jì)算三步所得結(jié)果如下：k xk (1) (2) (3) (4)0 x0 2 2 2 2x1 3 1.5 1.75 1.75x2 9 2 1.73475 1.732143x3 87 1.5 1.732361 1.732051注：x*=1.7320508……30第30頁，共50頁，2023年，2月20日，星期四例用迭代法求方程在內(nèi)的實(shí)根。取

解：對方程進(jìn)行如下三種變形：

建立迭代格式：

這是一個(gè)發(fā)散的迭代格式。

31第31頁，共50頁，2023年，2月20日，星期四建立迭代格式：

該迭代格式收斂。

建立迭代格式：

該迭代格式收斂。

32第32頁，共50頁，2023年，2月20日，星期四例.用迭代法求方程在內(nèi)的實(shí)根。取

解：對方程進(jìn)行如下三種變形：

理論分析：

由上述定理知，迭代格式發(fā)散，和計(jì)算結(jié)果吻合。

理論分析：

由定理知，迭代格式收斂，和計(jì)算結(jié)果吻合。

33第33頁，共50頁，2023年，2月20日，星期四理論分析：由定理知，迭代格式收斂，和計(jì)算結(jié)果吻合。而且，，②和③都收斂，但③收斂的效果比②好。

34第34頁，共50頁，2023年，2月20日，星期四例求

在[0，1]內(nèi)的一個(gè)實(shí)根.

將方程化為等價(jià)方程

因?yàn)橛?/p>

所以對于[0，1]中任意初值，迭代序列

收斂，計(jì)算結(jié)果如下表，取

35第35頁，共50頁，2023年，2月20日，星期四注.方程也可化為等價(jià)方程

但此時(shí)定理、推論條件不成立，迭代序列不能保證收斂。

36第36頁，共50頁，2023年，2月20日，星期四Remark2：可以證明，若在根的鄰域中，則可以以鄰域內(nèi)任何一點(diǎn)為初始值，用迭代過程產(chǎn)生的序列就一定不會收斂于。事實(shí)上，Remark3：當(dāng)不取在的鄰域?yàn)閮?nèi)時(shí)可能不收斂。Remark1：全局與局部收斂定理中的條件都是充分條件，條件滿足則迭代法收斂，不滿足則不能判定，此時(shí)可以用試算來判定迭代法的是收斂性。Remark4：全局收斂定理中的兩個(gè)誤差估計(jì)式實(shí)際上給出了迭代收斂的兩個(gè)準(zhǔn)則：事后誤差估計(jì)與事先誤差估計(jì)（利用估計(jì)式可以預(yù)先求出迭代次數(shù)k）。37第37頁，共50頁，2023年，2月20日，星期四一、事先誤差估計(jì)法二、事后誤差估計(jì)法有先計(jì)算滿足誤差要求的迭代次數(shù)k，再進(jìn)行迭代。由由因此可以用來控制迭代過程。只要使，就可使

，對于較為復(fù)雜的迭代函數(shù)，其導(dǎo)數(shù)也較為復(fù)雜，使得L難以取得，因而實(shí)際中不常用此方法。38第38頁，共50頁，2023年，2月20日，星期四Remark1:迭代方法的優(yōu)點(diǎn)是計(jì)算程序簡單，并且雖然是以求解非線性方程的實(shí)根來討論的，但類似的結(jié)果完全可以推廣到求方程的復(fù)數(shù)根的情形。Remark2：由全局收斂定理知，若L1，則{xk}必然收斂較慢；若L<<1，則收斂速度快。39第39頁，共50頁，2023年，2月20日，星期四定義：設(shè)迭代過程xk+1=(xk)

收斂于方程x=(x

)的根x*，若迭代誤差ek=xk–x*

當(dāng)k時(shí)成立下列漸近關(guān)系式： （c為常數(shù)，且c0）則稱迭代過程是r階收斂的。特別地，r=1時(shí)稱線性收斂；r=2時(shí)稱平方收斂；r>1時(shí)稱超線性收斂。且r越大，收斂越快。迭代收斂階定義40第40頁，共50頁，2023年，2月20日，星期四例：

線性收斂.平方收斂.例：迭代收斂階舉例41第41頁，共50頁，2023年，2月20日，星期四定理設(shè)x*為x=(x

)的不動點(diǎn)，若(x

)滿足：（1）(x

)在x*附近是p次連續(xù)可微的(p>1)；（2）則迭代過程xn+1=(xn)在點(diǎn)x*鄰近是p階收斂的。得所以故迭代過程xn+1=(xn

)p階收斂。證：由Taylor公式42第42頁，共50頁，2023年，2月20日，星期四

待定參數(shù)法：若|g’(x)|1，則將x=g(x)等價(jià)地改造為求K，使得例：求在(1,2)的實(shí)根。如果用進(jìn)行迭代，則在(1,2)中有現(xiàn)令希望，即在(1,2)上可取任意，例如K=0.5，則對應(yīng)即產(chǎn)生收斂序列。迭代收斂的加速方法

acceleratingconvergence

43第43頁，共50頁，2023年，2月20日，星期四一Aitken加速收斂方法假定`(x

)改變不大，近似取某個(gè)近似值L，則有由微分中值定理，有同理兩式相比，得44第44頁，共50頁，2023年，2月20日，星期四類推可得故上式即為Aitken加速收斂方法的迭代格式.45第45頁，共50頁，2023年，2月20日，星期四分別用簡單迭代法和Aitken加速算法求方程x=1.6+0.99cosx在x0=/2附近的根。(=1.585471802)例46第46頁，共50頁，2023年，2月20日，星期四

解用迭代公式：k簡單迭代法kAitken算法xk|xk-xk-1|xk|xk-xk-1|012341.570801.61.571091.599711.571380.02920.028910.028620.028330121.57079631.5854725