第二章非線性方程的數(shù)值解法課件

第二章非線性方程的數(shù)值解法

/*NumericalSolutionsofNonlinearEquations*/本章主要內(nèi)容：1、二分法2、不動(dòng)點(diǎn)迭代的構(gòu)造及其收斂性判定（重點(diǎn)）3、Newton和Steffensen迭代（重點(diǎn)）4、割線法5、非線性方程組的迭代解法歷史背景

代數(shù)方程的求根問題是一個(gè)古老的數(shù)學(xué)問題。理論上，次代數(shù)方程在復(fù)數(shù)域內(nèi)一定有個(gè)根(考慮重?cái)?shù))。早在16世紀(jì)就找到了三次、四次方程的求根公式，但直到19世紀(jì)才證明大于等于5次的一般代數(shù)方程式不能用代數(shù)公式求解，而對(duì)于超越方程就復(fù)雜的多，如果有解，其解可能是一個(gè)或幾個(gè)，也可能是無窮多個(gè)。一般也不存在根的解析表達(dá)式。因此需要研究數(shù)值方法求得滿足一定精度要求的根的近似解。

求方程幾何意義基本定理如果函數(shù)在上連續(xù)，且則至少有一個(gè)數(shù)使得，若同時(shí)的一階導(dǎo)數(shù)在內(nèi)存在且保持定號(hào)，即(或)則這樣的在內(nèi)唯一。

abx*§1二分法

/*BisectionMethod*/原理：若f

C[a,b]，且f(a)·f(b)<0，則f在(a,b)上至少有一實(shí)根?；舅枷耄褐鸩綄^(qū)間分半，通過判別區(qū)間端點(diǎn)函數(shù)值的符號(hào)，進(jìn)一步搜索有根區(qū)間，將有根區(qū)間縮小到充分小，從而求出滿足給定精度的根的近似值。以此類推終止法則？abx1x2abWhentostop?或不能保證

x

的精度x*2xx*二分法算法給定區(qū)間[a,b]

，求f(x)=0

在該區(qū)間上的根x.輸入:

a和b;容許誤差

TOL;最大對(duì)分次數(shù)

Nmax.輸出:近似根x.Step1Setk=1;Step2Computex=f((a+b)/2);Step3While(kNmax)dosteps4-6Step4If|x|

<TOL

,STOP;Outputthesolutionx.Step5Ifx*f(a)<0,Setb=x;

ElseSet

a=x;Step6Setk=k+1;Computex=f((a+b)/2);GoTo

Step3;Step7Outputthesolutionofequation:

x;STOP.3、由二分法的過程可知：4、對(duì)分次數(shù)的計(jì)算公式：1、2、令誤差

分析解：例1：用二分法求方程在區(qū)間上的根，誤差限為，問至少需對(duì)分多少次？①簡(jiǎn)單;②

對(duì)f(x)

要求不高(只要連續(xù)即可).①無法求復(fù)根及偶重根②收斂慢

注：用二分法求根，最好先給出f(x)

草圖以確定根的大概位置?；蛴盟阉鞒绦颍瑢a,b]分為若干小區(qū)間，對(duì)每一個(gè)滿足f(ak)·f(bk)<0的區(qū)間調(diào)用二分法程序，可找出區(qū)間[a,b]內(nèi)的多個(gè)根，且不必要求f(a)·f(b)<0。優(yōu)點(diǎn)缺點(diǎn)§2迭代法的理論

/*TheoryofIteration

Method*/f(x)=0x=g(x)（迭代函數(shù)）等價(jià)變換思路從一個(gè)初值x0出發(fā)，計(jì)算x1=g(x0),x2=g(x1),…,xk+1=g(xk),…若收斂，即存在x*使得

，且g連續(xù)，則由可知x*=g(x*)，即x*是g的不動(dòng)點(diǎn)，也就是f的根?？雌饋砗芎?jiǎn)單，令人有點(diǎn)不相信，那么問題是什么呢？如何判定這種方法是收斂的呢？f(x)的根g(x)的不動(dòng)點(diǎn)一、不動(dòng)點(diǎn)迭代

/*Fixed-PointIteration*/xyy=xxyy=xxyy=xxyy=xx*x*x*x*y=g(x)y=g(x)y=g(x)y=g(x)x0p0x1p1x0p0x1p1x0p0x1p1x0p0x1p1幾何意義例2：已知方程在上有一個(gè)根（正根）下面選取5種迭代格式：1、即2、即3、即4、即5、即取計(jì)算結(jié)果如下：法1法4法3法2法5Lipschitz條件成立的充分條件考慮方程x=g(x),若(I)當(dāng)x[a,b]時(shí)，g(x)[a,b]；(II)0L<1使得

對(duì)x[a,b]成立。則任取x0[a,b]，由xk+1=g(xk)得到的序列收斂于g(x)在[a,b]上的唯一不動(dòng)點(diǎn)。并且有誤差估計(jì)式：(k=1,2,…)且存在極限連續(xù)時(shí)證明：①g(x)在[a,b]上存在不動(dòng)點(diǎn)？令有根②不動(dòng)點(diǎn)唯一？反證：若不然，設(shè)還有，則在和之間。而③當(dāng)k

時(shí)，

xk收斂到x*？L越收斂越快可用來控制收斂精度④⑤⑥小注：條件(II)可改為在[a,b]滿足Lipschitz條件,定理結(jié)論仍然成立(定理2.3’)。

算法:不動(dòng)點(diǎn)迭代給定初始近似值

x0

，求x=g(x)

的解.輸入:

初始近似值

x0;容許誤差

TOL;最大迭代次數(shù)

Nmax.輸出:近似解x或失敗信息.Step1Seti=1;Step2While(iNmax)dosteps3-6

Step3Setx=g(x0);/*計(jì)算xi*/

Step4If|xx0|<TOLthenOutput(x);/*成功*/ STOP;

Step5Seti++;

Step6Setx0=x;/*更新x0*/Step7Output(Themethodfailedafter

Nmax

iterations);/*不成功*/ STOP.當(dāng)x很大時(shí)，此處可改為二、局部收斂性/*LocalConvergence*/（局部收斂性

）若存在的不動(dòng)點(diǎn)的一個(gè)閉鄰域?qū)θ我獾?，由迭代法產(chǎn)生的序列均收斂于，則稱該迭代法局部收斂。

注解:局部收斂性特點(diǎn)：假定解存在，且肯定存在解的一個(gè)鄰域，使得對(duì)其中所有初始值，由迭代生成的序列收斂于解。半局部收斂特點(diǎn)：不知道解存在，但指出要從滿足一定（通常很強(qiáng)）條件的初始值出發(fā)，保證收斂于某一（臨近）解。全局（整體）收斂：肯定在全空間或至少其中一個(gè)很大的部分中，無論從何處出發(fā)，都能保證收斂于一個(gè)解。設(shè)為的不動(dòng)點(diǎn)，在的某鄰域連續(xù)，且，則迭代法(*)局部收斂。證明：因?yàn)樵诘哪赤徲蜻B續(xù)，存在鄰域即對(duì)則由定理2.3’，迭代法(*)對(duì)收斂，即局部收斂.注

例3：已知方程在1.5附近有根，把方程寫成三種不同的等價(jià)形式(1)對(duì)應(yīng)迭代格式；(2)對(duì)應(yīng)迭代格式；(3)對(duì)應(yīng)迭代格式;判斷迭代格式在的收斂性，選一種收斂格式計(jì)算，精確到小數(shù)點(diǎn)后第二位。解：（1），，迭代格式收斂；（2），，迭代格式收斂；（3），，迭代格式發(fā)散。選擇(2)計(jì)算

012341.51.4811.4731.4691.467（收斂階/*theorderofConvergence*/)設(shè)序列收斂到，，若存在實(shí)數(shù)及常數(shù)，使,則稱序列是階收斂的，稱為漸近誤差常數(shù)。當(dāng)且時(shí)，稱為線性收斂，為超線性收斂，時(shí)為平方或二次收斂.注:（1）的大小反映了迭代法收斂的快慢，是收斂速度的一種度量;

（2）設(shè)迭代函數(shù)滿足收斂定理的條件，則產(chǎn)生的序列滿足，如果在或的鄰域有若取，必有，此時(shí)有設(shè)迭代法的迭代函數(shù)的高階導(dǎo)數(shù)在不動(dòng)點(diǎn)的鄰域里連續(xù)，則式（*）是階收斂的充要條件是且證明：由Taylor公式：充分性取極限得必要性設(shè)迭代式（*）是階收斂的，則有即且（反證法）設(shè)結(jié)論不成立則存在最小正整數(shù)滿足情形一情形二由充分性證明知，迭代式（*）是階收斂的即而的極限不存在與階收斂矛盾證明方法與情形一類似（自己練習(xí)）一、使用兩個(gè)迭代值的組合方法：§3迭代收斂的加速方法

/*Accelerating

Method*/本節(jié)討論迭代法加速收斂問題，常用于線性收斂迭代法

將x=g(x)

等價(jià)地改造為當(dāng)和時(shí)，有相應(yīng)的迭代公式為或者選取特殊的，有可能使迭代加速。

xyy=xy=g(x)x*如：迭代公式為幾何意義如圖示注：(1)這種迭代對(duì)原迭代公式(*)的各近似值在根的兩側(cè)往復(fù)地趨于時(shí)較為有效；中點(diǎn)(2)只有且較大時(shí)，加速效果才明顯。又如：新的迭代函數(shù)為當(dāng)時(shí)根據(jù)定理2.5知，迭代法至少是二階的.

但由于不知道，故也得不到，因此可取其的近似值，即從而有二、Steffensen(斯蒂芬森)加速迭代法：（三個(gè)迭代值組合）xyy=xy=g(x)x*x0從初值出發(fā)，計(jì)算出在曲線上得到兩個(gè)點(diǎn)用直線連接、兩點(diǎn)它與的交點(diǎn)設(shè)為點(diǎn)的坐標(biāo)為將視為新的初值，重復(fù)上述步驟

一般地，由組合得到迭代式或者這個(gè)方法稱為斯蒂芬森(Steffensen)迭代方法

若令則得到斯蒂芬森(Steffensen)迭代法的另一種形式：Steffensen迭代法的優(yōu)點(diǎn)：可以改進(jìn)收斂速度，有時(shí)也能把不收斂的迭代法改進(jìn)為收斂的二階方法.艾特肯（Aitken）加速方法：例4：已知方程在上有一個(gè)根（正根）下面選取3種迭代格式：1、即2、即3、即顯示計(jì)算結(jié)果設(shè)不動(dòng)點(diǎn)迭代的迭代函數(shù)在其不動(dòng)點(diǎn)的某鄰域內(nèi)具有二階連續(xù)導(dǎo)數(shù)，則斯蒂芬森(Steffensen)的迭代技術(shù)是二階收斂的，而且其極限仍為。證明：設(shè)斯蒂芬森(Steffensen)的迭代為其中首先證明有相同的不動(dòng)點(diǎn)設(shè)則反之，設(shè)型洛比塔法則其次證明Steffensen迭代是二階收斂的由Taylor公式：在處展開則上式中用替換即證代入上述結(jié)果：注意：對(duì)本來就是P(>1)階收斂的方法，改用Stefensen迭代方法優(yōu)點(diǎn)不多。取計(jì)算結(jié)果如下：法2原迭代次數(shù)29法3原來不收斂法1原來不收斂返回§4牛頓法

/*Newton-RaphsonMethod*/一、牛頓迭代公式的推導(dǎo)1、待定參數(shù)法不動(dòng)點(diǎn)迭代的關(guān)鍵是構(gòu)造滿足收斂條件的迭代函數(shù)

一種自然的選擇是令為了加速不動(dòng)點(diǎn)迭代的收斂過程，應(yīng)盡可能使迭代函數(shù)在處有更多階導(dǎo)數(shù)等于零（定理2.5）。令現(xiàn)設(shè)取滿足因此，選取迭代函數(shù)Newton–Raphson迭代格式稱之為牛頓—拉夫森方法，簡(jiǎn)稱牛頓法原理：將非線性方程線性化取x0

x*，將f(x)在x0

做一階Taylor展開:，在x0和x之間2、Taylor展開法/*Taylor’sexpansionMethod*/將(x*

x0)2看成高階小量，則有：xyx*x0只要f

C1，每一步迭代都有而且，則

x*就是f的根。與x軸交點(diǎn)的橫坐標(biāo)無開方運(yùn)算，又無除法運(yùn)算。例1：寫出求的Newton迭代格式；寫出求的Newton迭代格式,要求公式中既解：等價(jià)于求方程的正根解法一：等價(jià)于求方程的正根解法二：等價(jià)于求方程的正根Th2.7

（局部收斂性）設(shè)x*

為方程f(x)=0的根，在包含x*的某個(gè)開區(qū)間內(nèi)連續(xù)，且，則存在x*的鄰域，使得任取初值，由Newton’sMethod產(chǎn)生的序列以不低于二階的收斂速度收斂于x*，且證明：Newton’sMethod

事實(shí)上是一種特殊的不動(dòng)點(diǎn)迭代其中，則收斂由Taylor展開：在單根

/*simpleroot*/附近收斂快只要，則令可得結(jié)論。Th2.5有根根唯一產(chǎn)生的序列單調(diào)有界保證收斂證明：因?yàn)閒

C2[a,b]，由（1）和（2）知f(x)在[a,b]內(nèi)有唯一根下面由條件（1）、（2）分4種情況討論：僅證明第一種情況，其它情況類似討論Th2.8

（收斂的充分條件）設(shè)f(x)=0且f

C2[a,b]，若(1)f(a)f(b)<0；(2)在整個(gè)[a,b]上不變號(hào)且

；(3)選取x0

[a,b]使得；則Newton’sMethod產(chǎn)生的序列{xk}收斂于方程的根,且由中值定理，使得因此即在上單調(diào)遞增由另一方面，由Taylor展開得介于、之間重復(fù)以上過程，可得（歸納法）（自己證）因此，數(shù)列單調(diào)下降且有下界令由Taylor展開得注：Newton’sMethod收斂性依賴于x0

的選取。x*x0x0x0Th2.9

（收斂的另一充分條件）設(shè)

在[a,b]上連續(xù)，(1)

f(a)f(b)<0；(2)在整個(gè)[a,b]上且

；(3)

，則對(duì)，Newton’sMethod產(chǎn)生的序列{xk}收斂于方程在[a,b]內(nèi)的唯一實(shí)根。且Th2.9中條件（3）的幾何意義保證數(shù)列單調(diào)遞增且有上界證明仿照Th2.9改進(jìn)與推廣（補(bǔ)充）

/*improvementandgeneralization*/重根

/*multipleroot*/加速收斂法：Q1:若，Newton’sMethod

是否仍收斂？設(shè)x*是f的n重根，則：且。因?yàn)镹ewton’sMethod

事實(shí)上是一種特殊的不動(dòng)點(diǎn)迭代，其中，則A1:

有局部收斂性，但重?cái)?shù)n

越高，收斂越慢。Q2:如何加速重根情況時(shí)的收斂速度？A2:

將求

f

的重根轉(zhuǎn)化為求另一函數(shù)的單根。令，則f的重根=

的單根。求復(fù)根

/*FindingComplexRoots*/——Newton

公式中的自變量可以是復(fù)數(shù)記z=x+iy,z0

為初值，同樣有設(shè)代入公式，令實(shí)、虛部對(duì)應(yīng)相等，可得§5弦割法與拋物線法

/*SecantMethodandParabolaMethod

*/x0x1割線

/*secantline*/切線斜率

割線斜率需要2個(gè)初值x0和x1。Newton’sMethod每一步要計(jì)算f和，為了避免計(jì)算導(dǎo)數(shù)值，現(xiàn)用f的值近似，從而得到弦割法（割線法）。x2一、弦割法Th2.10

局部收斂性設(shè)表示區(qū)間，x*為方程f(x)=0的根，函數(shù)f(x)在

中有足夠階連續(xù)導(dǎo)數(shù)，且滿足則對(duì)，由割線法產(chǎn)生的序列都收斂于x*，且(i)(ii)(iii)

其中收斂速度介于NewtonandBisection

之間

Corollary(推論)設(shè)x*

為方程f(x)=0的一個(gè)根，，且在x*的附近連續(xù)，則使得由Secant

Method產(chǎn)生的序列都收斂于x*。例1

證明方程在區(qū)間內(nèi)有唯一根，且使得對(duì)任意的初始值，由割線法產(chǎn)生的序列都收斂于。

證明：令方程存在根方程存在唯一根且在附近連續(xù)由推論知，由割線法產(chǎn)生的序列都收斂于。

xk-2Muller方法的思想來源于弦割法:利用3個(gè)已知點(diǎn)構(gòu)造一條拋物線,取其與x軸的交點(diǎn)構(gòu)造下一次迭代值.x*二、拋物線法(Muller)幾何圖示xkxk-1xk+1

Muller方法的具體實(shí)現(xiàn):設(shè)已知三個(gè)點(diǎn)則過上述三個(gè)點(diǎn)的拋物線方程為:取該拋物線與x軸的交點(diǎn)作為下一次迭代值,即然后取新的相鄰的三次迭代值重復(fù)上述過程,即為Muller方法.

Muller方法中拋物線根的計(jì)算方法:首先要將拋物線化為規(guī)范形式:引入新的變量將上述變量代入前面的拋物線方程,得其中的兩個(gè)零點(diǎn)為:取的兩個(gè)零點(diǎn)中靠近的那個(gè)零點(diǎn),則有

Muller方法的迭代公式為:具體計(jì)算步驟見教材P39.

算法:Muller方法給定初始近似值

x0

，x1

，

x2,求f(x