非線性方程與方程組的數值解法第一頁，共七十頁，2022年，8月28日第七章非線性方程與方程組的數值解法

/*NumericalSolutionsofNonlinearEquationsandNonlinearAlgebraicSystems*/我們知道在實際應用中有許多非線性方程的例子例如:（1）在光的衍射理論（thetheoryofdiffractionoflight)中,我們需要求x-tanx=0的根（2）在行星軌道（planetaryorbits）的計算中,對任意的a和b，我們需要求x-asinx=b的根（3）在數學中，需要求n次多項式的根第二頁，共七十頁，2022年，8月28日歷史背景

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

第三頁，共七十頁，2022年，8月28日求方程幾何意義基本定理如果函數在上連續(xù)，且則至少有一個數使得，若同時的一階導數在內存在且保持定號，即(或)則這樣的在內唯一。

abx*第四頁，共七十頁，2022年，8月28日§1二分法

/*BisectionMethod*/原理：若f

C[a,b]，且f(a)·f(b)<0，則f在(a,b)上至少有一實根?；舅枷耄褐鸩綄^(qū)間分半，通過判別區(qū)間端點函數值的符號，進一步搜索有根區(qū)間，將有根區(qū)間縮小到充分小，從而求出滿足給定精度的根的近似值。以此類推第五頁，共七十頁，2022年，8月28日終止法則？abx1x2abWhentostop?或不能保證

x

的精度x*2xx*第六頁，共七十頁，2022年，8月28日二分法算法給定區(qū)間[a,b]

，求f(x)=0

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

a和b;容許誤差

TOL;最大對分次數

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

<TOL

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

ElseSet

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

Step3;Step7Outputthesolutionofequation:

x;STOP.第七頁，共七十頁，2022年，8月28日3、由二分法的過程可知：4、對分次數的計算公式：1、2、令誤差

分析第八頁，共七十頁，2022年，8月28日解：例1：用二分法求方程在區(qū)間上的根，精確到小數點后第2位，問至少需對分多少次？第九頁，共七十頁，2022年，8月28日kakbkxkf(xk)符號01234561.01.251.31251.32031.51.3751.34381.32811.251.3751.31251.34381.32811.32031.3242

?+?++??第十頁，共七十頁，2022年，8月28日①簡單;②

對f(x)

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

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

草圖以確定根的大概位置，或用搜索程序，將[a,b]分為若干小區(qū)間，對每一個滿足f(ak)·f(bk)<0的區(qū)間調用二分法程序，可找出區(qū)間[a,b]內的多個根，且不必要求f(a)·f(b)<0。優(yōu)點缺點第十一頁，共七十頁，2022年，8月28日§2不動點迭代法及其收斂性f(x)=0x=φ(x)（迭代函數）等價變換思路從一個初值x0出發(fā)，計算x1=φ(x0),x2=φ(x1),…,xk+1=φ(xk),…若收斂，即存在x*使得

，且φ

連續(xù)，則由可知x*=φ

(x*)，即x*是φ

的不動點，也就是f的根?？雌饋砗芎唵危钊擞悬c不相信，那么問題是什么呢？如何判定這種方法是收斂的呢？f(x)的根φ(x)的不動點一、不動點迭代

/*Fixed-PointIteration*/第十二頁，共七十頁，2022年，8月28日xyy=xxyy=xxyy=xxyy=xx*x*x*x*y=φ(x)y=φ(x)y=φ(x)y=φ(x)x0p0x1p1x0p0x1p1x0p0x1p1x0p0x1p1幾何意義第十三頁，共七十頁，2022年，8月28日例2：已知方程在上有一個根（正根）下面選取5種迭代格式：1、即2、即3、即4、即5、即第十四頁，共七十頁，2022年，8月28日取計算結果如下：法1法4法3法2法5第十五頁，共七十頁，2022年，8月28日Lipschitz條件成立的充分條件考慮方程x=φ(x),若(I)當x[a,b]時，φ(x)[a,b]；(II)0L<1使得

對x[a,b]成立。則任取x0[a,b]，由xk+1=φ(xk)得到的序列收斂于φ(x)在[a,b]上的唯一不動點。并且有誤差估計式：(k=1,2,…)且存在極限連續(xù)時第十六頁，共七十頁，2022年，8月28日證明：①φ(x)在[a,b]上存在不動點？令有根②不動點唯一？反證：若不然，設還有，則在和之間。而③當k

時，

xk收斂到x*？第十七頁，共七十頁，2022年，8月28日L越收斂越快可用來控制收斂精度④⑤⑥小注：條件(II)可改為在[a,b]滿足Lipschitz條件,定理結論仍然成立。第十八頁，共七十頁，2022年，8月28日

算法:不動點迭代給定初始近似值

x0

，求x=φ(x)

的解.輸入:

初始近似值

x0;容許誤差

TOL;最大迭代次數

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

Step3Setx=φ(x0);/*計算xi*/

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

Step5Seti++;

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

Nmax

iterations);/*不成功*/ STOP.當x很大時，此處可改為第十九頁，共七十頁，2022年，8月28日二、局部收斂性/*LocalConvergence*/（局部收斂性

）若存在的不動點的一個閉鄰域對任意的，由迭代法產生的序列均收斂于，則稱該迭代法局部收斂。

注解:局部收斂性特點：假定解存在，且肯定存在解的一個鄰域，使得對其中所有初始值，由迭代生成的序列收斂于解。半局部收斂特點：不知道解存在，但指出要從滿足一定（通常很強）條件的初始值出發(fā)，保證收斂于某一（臨近）解。全局（整體）收斂：肯定在全空間或至少其中一個很大的部分中，無論從何處出發(fā)，都能保證收斂于一個解。第二十頁，共七十頁，2022年，8月28日設為的不動點，在的某鄰域連續(xù)，且，則迭代法(*)局部收斂。證明：因為在的某鄰域連續(xù)，存在鄰域即對則由上一定理，迭代法(*)對收斂，即局部收斂.注

第二十一頁，共七十頁，2022年，8月28日例3：已知方程在1.5附近有根，把方程寫成三種不同的等價形式(1)對應迭代格式；(2)對應迭代格式；(3)對應迭代格式;判斷迭代格式在的收斂性，選一種收斂格式計算，精確到小數點后第二位。解：（1），，迭代格式收斂；（2），，迭代格式收斂；（3），，迭代格式發(fā)散。選擇(2)計算

012341.51.4811.4731.4691.467第二十二頁，共七十頁，2022年，8月28日（收斂階/*theorderofConvergence*/)設序列收斂到，，若存在實數及常數，使,則稱序列是階收斂的，稱為漸近誤差常數。當且時，稱為線性收斂，為超線性收斂，時為平方或二次收斂.注:（1）的大小反映了迭代法收斂的快慢，是收斂速度的一種度量;

（2）設迭代函數滿足收斂定理的條件，則產生的序列滿足，如果在或的鄰域有若取，必有，此時有第二十三頁，共七十頁，2022年，8月28日設迭代法的迭代函數的高階導數在不動點的鄰域里連續(xù)，則式（*）是階收斂的充要條件是且證明：由Taylor公式：充分性取極限得第二十四頁，共七十頁，2022年，8月28日必要性設迭代式（*）是階收斂的，則有即且（反證法）設結論不成立則存在最小正整數滿足情形一情形二由充分性證明知，迭代式（*）是階收斂的即而的極限不存在與階收斂矛盾證明方法與情形一類似第二十五頁，共七十頁，2022年，8月28日kxk迭代法(1)迭代法(2)迭代法(3)迭代法(4)0123

?

x0

x1

x2

x3

?23987?21.521.5?21.751.734751.732631?21.751.7321431.732051?例4：只用四則運算不用開方求方程的根第二十六頁，共七十頁，2022年，8月28日一、使用兩個迭代值的組合方法：§3迭代收斂的加速方法

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

將x=φ(x)

等價地改造為當和時，有相應的迭代公式為或者選取特殊的，有可能使迭代加速。

第二十七頁，共七十頁，2022年，8月28日xyy=xy=

φ(x)x*如：迭代公式為幾何意義如圖示注：(1)這種迭代對原迭代公式(*)的各近似值在根的兩側往復地趨于時較為有效；中點(2)只有且較大時，加速效果才明顯。第二十八頁，共七十頁，2022年，8月28日又如：新的迭代函數為當時故迭代法至少是二階的.

但由于不知道，故也得不到，因此可取其的近似值，即從而有第二十九頁，共七十頁，2022年，8月28日二、Steffensen(斯蒂芬森)加速迭代法：（三個迭代值組合）xyy=xy=

φ(x)x*x0從初值出發(fā)，計算出在曲線上得到兩個點用直線連接、兩點它與的交點設為點的坐標為將視為新的初值，重復上述步驟

第三十頁，共七十頁，2022年，8月28日一般地，由組合得到迭代式或者這個方法稱為斯蒂芬森(Steffensen)迭代方法

第三十一頁，共七十頁，2022年，8月28日若令則得到斯蒂芬森(Steffensen)迭代法的另一種形式：Steffensen迭代法的優(yōu)點：可以改進收斂速度，有時也能把不收斂的迭代法改進為收斂的二階方法.埃特金（Aitken）加速方法：第三十二頁，共七十頁，2022年，8月28日例5：已知方程在上有一個根（正根）下面選取3種迭代格式：1、即2、即3、即第三十三頁，共七十頁，2022年，8月28日取計算結果如下：法2原迭代次數29法3原來不收斂法1原來不收斂第三十四頁，共七十頁，2022年，8月28日設不動點迭代的迭代函數在其不動點的某鄰域內具有二階連續(xù)導數，則斯蒂芬森(Steffensen)的迭代技術是二階收斂的，而且其極限仍為。證明：設斯蒂芬森(Steffensen)的迭代為其中首先證明有相同的不動點設則第三十五頁，共七十頁，2022年，8月28日反之，設型洛比塔法則第三十六頁，共七十頁，2022年，8月28日其次證明Steffensen迭代是二階收斂的由Taylor公式：在處展開則上式中用替換即證第三十七頁，共七十頁，2022年，8月28日代入上述結果：注意：對本來就是p(>1)階收斂的方法，改用Stefensen迭代方法優(yōu)點不多。第三十八頁，共七十頁，2022年，8月28日第三十九頁，共七十頁，2022年，8月28日第四十頁，共七十頁，2022年，8月28日第四十一頁，共七十頁，2022年，8月28日第四十二頁，共七十頁，2022年，8月28日第四十三頁，共七十頁，2022年，8月28日第四十四頁，共七十頁，2022年，8月28日§4牛頓法

/*Newton-RaphsonMethod*/一、牛頓迭代公式的推導1、待定參數法不動點迭代的關鍵是構造滿足收斂條件的迭代函數

一種自然的選擇是令為了加速不動點迭代的收斂過程，應盡可能使迭代函數在處有更多階導數等于零。令現(xiàn)設第四十五頁，共七十頁，2022年，8月28日取滿足因此，選取迭代函數Newton–Raphson迭代格式稱之為牛頓—拉夫森方法，簡稱牛頓法原理：將非線性方程線性化取x0

x*，將f(x)在x0

做一階Taylor展開:，在x0和x之間2、Taylor展開法/*Taylor’sexpansionMethod*/第四十六頁，共七十頁，2022年，8月28日將(x*

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

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

x*就是f的根。與x軸交點的橫坐標第四十七頁，共七十頁，2022年，8月28日無開方運算，又無除法運算。例1：寫出求的Newton迭代格式；寫出求的Newton迭代格式,要求公式中既解：等價于求方程的正根解法一：等價于求方程的正根第四十八頁，共七十頁，2022年，8月28日解法二：等價于求方程的正根

（局部收斂性）設x*

為方程f(x)=0的根，在包含x*的某個開區(qū)間內連續(xù)，且，則存在x*的鄰域，使得任取初值，由Newton’sMethod產生的序列以不低于二階的收斂速度收斂于x*，且Th第四十九頁，共七十頁，2022年，8月28日證明：Newton’sMethod

事實上是一種特殊的不動點迭代其中，則至少平方收斂由Taylor展開：在單根

/*simpleroot*/附近收斂快只要，則令可得結論。第五十頁，共七十頁，2022年，8月28日有根根唯一產生的序列單調有界保證收斂證明：因為f

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

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

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

；(3)選取x0

[a,b]使得；則Newton’sMethod產生的序列{xk}收斂于方程的根,Th且第五十一頁，共七十頁，2022年，8月28日由中值定理，使得因此即在上單調遞增由另一方面，由Taylor展開得介于、之間第五十二頁，共七十頁，2022年，8月28日重復以上過程，可得（歸納法）（自己證）因此，數列單調下降且有下界令由Taylor展開得第五十三頁，共七十頁，2022年，8月28日注：Newton’sMethod收斂性依賴于x0

的選取。x*x0x0x0

（收斂的另一充分條件）設

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

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

；(3)

，則對，Newton’sMethod產生的序列{xk}收斂于方程在[a,b]內的唯一實根。Th且第五十四頁，共七十頁，2022年，8月28日Th中條件（3）的幾何意義保證數列單調遞增且有上界第五十五頁，共七十頁，2022年，8月28日改進與推廣/*improvementandgeneralization*/重根

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

是否仍收斂？設x*是f的m重根，則：且。因為Newton’sMethod

事實上是一種特殊的不動點迭代，其中，則A1:

有局部收斂性，但重數m

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

將求

f

的重根轉化為求另一函數的單根。令，則f的重根=

的單根。第五十六頁，共七十頁，2022年，8月28日求復根

/*FindingComplexRoots*/

——

Newton

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

為初值，同樣有設代入公式，令實、虛部對應相等，可得第五十七頁，共七十頁，2022年，8月28日§5弦割法與拋物線法

/*SecantMethodandParabolaMethod

*/x0x1割線

/*secantline*/切線斜率

割線斜率需要2個初值x0和x1。Newton’sMethod每一步要計算f和，為了避免計算導數值，現(xiàn)用f的值近似，從而得到弦割法（割線法）。x2一、弦割法第五十八頁，共七十頁，2022年，8月28日

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

中有足夠階連續(xù)導數，且滿足Th則對，由弦割法產生的序列都收斂于x*，且(i)(ii)(iii)

其中收斂速度介于NewtonandBisection

之間

第五十九頁，共七十頁，2022年，8月28日Corollary(推論)設x*

為方程f(x)=0的一個根，，且在x*的附近連續(xù)，則使得則由弦割法產生的序列都收斂于x*。例1

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

證明：令方程存在根方程存在唯一根且在附近連續(xù)由推論知，由弦割法產生的序列