非線性方程與方程組的數(shù)值解法

非線性方程與方程組的數(shù)值解法第1頁(yè)，共70頁(yè)，2023年，2月20日，星期四第七章非線性方程與方程組的數(shù)值解法

/*NumericalSolutionsofNonlinearEquationsandNonlinearAlgebraicSystems*/我們知道在實(shí)際應(yīng)用中有許多非線性方程的例子例如:（1）在光的衍射理論（thetheoryofdiffractionoflight)中,我們需要求x-tanx=0的根（2）在行星軌道（planetaryorbits）的計(jì)算中,對(duì)任意的a和b，我們需要求x-asinx=b的根（3）在數(shù)學(xué)中，需要求n次多項(xiàng)式的根第2頁(yè)，共70頁(yè)，2023年，2月20日，星期四歷史背景

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

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

abx*第4頁(yè)，共70頁(yè)，2023年，2月20日，星期四§1二分法

/*BisectionMethod*/原理：若f

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

x

的精度x*2xx*第6頁(yè)，共70頁(yè)，2023年，2月20日，星期四二分法算法給定區(qū)間[a,b]

，求f(x)=0

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

a和b;容許誤差

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

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.第7頁(yè)，共70頁(yè)，2023年，2月20日，星期四3、由二分法的過(guò)程可知：4、對(duì)分次數(shù)的計(jì)算公式：1、2、令誤差

分析第8頁(yè)，共70頁(yè)，2023年，2月20日，星期四解：例1：用二分法求方程在區(qū)間上的根，精確到小數(shù)點(diǎn)后第2位，問(wèn)至少需對(duì)分多少次？第9頁(yè)，共70頁(yè)，2023年，2月20日，星期四kakbkxkf(xk)符號(hào)01234561.01.251.31251.32031.51.3751.34381.32811.251.3751.31251.34381.32811.32031.3242

?+?++??第10頁(yè)，共70頁(yè)，2023年，2月20日，星期四①簡(jiǎn)單;②

對(duì)f(x)

要求不高(只要連續(xù)即可).①無(wú)法求復(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)第11頁(yè)，共70頁(yè)，2023年，2月20日，星期四§2不動(dòng)點(diǎn)迭代法及其收斂性f(x)=0x=φ(x)（迭代函數(shù)）等價(jià)變換思路從一個(gè)初值x0出發(fā)，計(jì)算x1=φ(x0),x2=φ(x1),…,xk+1=φ(xk),…若收斂，即存在x*使得

，且φ

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

(x*)，即x*是φ

的不動(dòng)點(diǎn)，也就是f的根?？雌饋?lái)很簡(jiǎn)單，令人有點(diǎn)不相信，那么問(wèn)題是什么呢？如何判定這種方法是收斂的呢？f(x)的根φ(x)的不動(dòng)點(diǎn)一、不動(dòng)點(diǎn)迭代

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

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

時(shí)，

xk收斂到x*？第17頁(yè)，共70頁(yè)，2023年，2月20日，星期四L越收斂越快可用來(lái)控制收斂精度④⑤⑥小注：條件(II)可改為在[a,b]滿足Lipschitz條件,定理結(jié)論仍然成立。第18頁(yè)，共70頁(yè)，2023年，2月20日，星期四

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

x0

，求x=φ(x)

的解.輸入:

初始近似值

x0;容許誤差

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

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

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

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

Step5Seti++;

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

Nmax

iterations);/*不成功*/ STOP.當(dāng)x很大時(shí)，此處可改為第19頁(yè)，共70頁(yè)，2023年，2月20日，星期四二、局部收斂性/*LocalConvergence*/（局部收斂性

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

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

第21頁(yè)，共70頁(yè)，2023年，2月20日，星期四例3：已知方程在1.5附近有根，把方程寫(xiě)成三種不同的等價(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第22頁(yè)，共70頁(yè)，2023年，2月20日，星期四（收斂階/*theorderofConvergence*/)設(shè)序列收斂到，，若存在實(shí)數(shù)及常數(shù)，使,則稱(chēng)序列是階收斂的，稱(chēng)為漸近誤差常數(shù)。當(dāng)且時(shí)，稱(chēng)為線性收斂，為超線性收斂，時(shí)為平方或二次收斂.注:（1）的大小反映了迭代法收斂的快慢，是收斂速度的一種度量;

（2）設(shè)迭代函數(shù)滿足收斂定理的條件，則產(chǎn)生的序列滿足，如果在或的鄰域有若取，必有，此時(shí)有第23頁(yè)，共70頁(yè)，2023年，2月20日，星期四設(shè)迭代法的迭代函數(shù)的高階導(dǎo)數(shù)在不動(dòng)點(diǎn)的鄰域里連續(xù)，則式（*）是階收斂的充要條件是且證明：由Taylor公式：充分性取極限得第24頁(yè)，共70頁(yè)，2023年，2月20日，星期四必要性設(shè)迭代式（*）是階收斂的，則有即且（反證法）設(shè)結(jié)論不成立則存在最小正整數(shù)滿足情形一情形二由充分性證明知，迭代式（*）是階收斂的即而的極限不存在與階收斂矛盾證明方法與情形一類(lèi)似第25頁(yè)，共70頁(yè)，2023年，2月20日，星期四kxk迭代法(1)迭代法(2)迭代法(3)迭代法(4)0123

?

x0

x1

x2

x3

?23987?21.521.5?21.751.734751.732631?21.751.7321431.732051?例4：只用四則運(yùn)算不用開(kāi)方求方程的根第26頁(yè)，共70頁(yè)，2023年，2月20日，星期四一、使用兩個(gè)迭代值的組合方法：§3迭代收斂的加速方法

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

將x=φ(x)

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

第27頁(yè)，共70頁(yè)，2023年，2月20日，星期四xyy=xy=

φ(x)x*如：迭代公式為幾何意義如圖示注：(1)這種迭代對(duì)原迭代公式(*)的各近似值在根的兩側(cè)往復(fù)地趨于時(shí)較為有效；中點(diǎn)(2)只有且較大時(shí)，加速效果才明顯。第28頁(yè)，共70頁(yè)，2023年，2月20日，星期四又如：新的迭代函數(shù)為當(dāng)時(shí)故迭代法至少是二階的.

但由于不知道，故也得不到，因此可取其的近似值，即從而有第29頁(yè)，共70頁(yè)，2023年，2月20日，星期四二、Steffensen(斯蒂芬森)加速迭代法：（三個(gè)迭代值組合）xyy=xy=

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

第30頁(yè)，共70頁(yè)，2023年，2月20日，星期四一般地，由組合得到迭代式或者這個(gè)方法稱(chēng)為斯蒂芬森(Steffensen)迭代方法

第31頁(yè)，共70頁(yè)，2023年，2月20日，星期四若令則得到斯蒂芬森(Steffensen)迭代法的另一種形式：Steffensen迭代法的優(yōu)點(diǎn)：可以改進(jìn)收斂速度，有時(shí)也能把不收斂的迭代法改進(jìn)為收斂的二階方法.埃特金（Aitken）加速方法：第32頁(yè)，共70頁(yè)，2023年，2月20日，星期四例5：已知方程在上有一個(gè)根（正根）下面選取3種迭代格式：1、即2、即3、即第33頁(yè)，共70頁(yè)，2023年，2月20日，星期四取計(jì)算結(jié)果如下：法2原迭代次數(shù)29法3原來(lái)不收斂法1原來(lái)不收斂第34頁(yè)，共70頁(yè)，2023年，2月20日，星期四設(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è)則第35頁(yè)，共70頁(yè)，2023年，2月20日，星期四反之，設(shè)型洛比塔法則第36頁(yè)，共70頁(yè)，2023年，2月20日，星期四其次證明Steffensen迭代是二階收斂的由Taylor公式：在處展開(kāi)則上式中用替換即證第37頁(yè)，共70頁(yè)，2023年，2月20日，星期四代入上述結(jié)果：注意：對(duì)本來(lái)就是p(>1)階收斂的方法，改用Stefensen迭代方法優(yōu)點(diǎn)不多。第38頁(yè)，共70頁(yè)，2023年，2月20日，星期四第39頁(yè)，共70頁(yè)，2023年，2月20日，星期四第40頁(yè)，共70頁(yè)，2023年，2月20日，星期四第41頁(yè)，共70頁(yè)，2023年，2月20日，星期四第42頁(yè)，共70頁(yè)，2023年，2月20日，星期四第43頁(yè)，共70頁(yè)，2023年，2月20日，星期四第44頁(yè)，共70頁(yè)，2023年，2月20日，星期四§4牛頓法

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

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

x*，將f(x)在x0

做一階Taylor展開(kāi):，在x0和x之間2、Taylor展開(kāi)法/*Taylor’sexpansionMethod*/第46頁(yè)，共70頁(yè)，2023年，2月20日，星期四將(x*

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

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

x*就是f的根。與x軸交點(diǎn)的橫坐標(biāo)第47頁(yè)，共70頁(yè)，2023年，2月20日，星期四無(wú)開(kāi)方運(yùn)算，又無(wú)除法運(yùn)算。例1：寫(xiě)出求的Newton迭代格式；寫(xiě)出求的Newton迭代格式,要求公式中既解：等價(jià)于求方程的正根解法一：等價(jià)于求方程的正根第48頁(yè)，共70頁(yè)，2023年，2月20日，星期四解法二：等價(jià)于求方程的正根

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

為方程f(x)=0的根，在包含x*的某個(gè)開(kāi)區(qū)間內(nèi)連續(xù)，且，則存在x*的鄰域，使得任取初值，由Newton’sMethod產(chǎn)生的序列以不低于二階的收斂速度收斂于x*，且Th第49頁(yè)，共70頁(yè)，2023年，2月20日，星期四證明：Newton’sMethod

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

/*simpleroot*/附近收斂快只要，則令可得結(jié)論。第50頁(yè)，共70頁(yè)，2023年，2月20日，星期四有根根唯一產(chǎn)生的序列單調(diào)有界保證收斂證明：因?yàn)閒

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

（收斂的充分條件）設(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}收斂于方程的根,Th且第51頁(yè)，共70頁(yè)，2023年，2月20日，星期四由中值定理，使得因此即在上單調(diào)遞增由另一方面，由Taylor展開(kāi)得介于、之間第52頁(yè)，共70頁(yè)，2023年，2月20日，星期四重復(fù)以上過(guò)程，可得（歸納法）（自己證）因此，數(shù)列單調(diào)下降且有下界令由Taylor展開(kāi)得第53頁(yè)，共70頁(yè)，2023年，2月20日，星期四注：Newton’sMethod收斂性依賴(lài)于x0

的選取。x*x0x0x0

（收斂的另一充分條件）設(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í)根。Th且第54頁(yè)，共70頁(yè)，2023年，2月20日，星期四Th中條件（3）的幾何意義保證數(shù)列單調(diào)遞增且有上界第55頁(yè)，共70頁(yè)，2023年，2月20日，星期四改進(jìn)與推廣/*improvementandgeneralization*/重根

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

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

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

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

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

將求

f

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

的單根。第56頁(yè)，共70頁(yè)，2023年，2月20日，星期四求復(fù)根

/*FindingComplexRoots*/

——

Newton

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

為初值，同樣有設(shè)代入公式，令實(shí)、虛部對(duì)應(yīng)相等，可得第57頁(yè)，共70頁(yè)，2023年，2月20日，星期四§5弦割法與拋物線法

/*SecantMethodandParabolaMethod

*/x0x1割線

/*secantline*/切線斜率

割線斜率需要2個(gè)初值x0和x1。Newton’sMethod每一步要計(jì)算f和，為了避免計(jì)算導(dǎo)數(shù)值，現(xiàn)用f的值近似，從而得到弦割法（割線法）。x2一、弦割法第58頁(yè)，共70頁(yè)，2023年，2月20日，星期四

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

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

其中收斂速度介于NewtonandBisection

之間

第59頁(yè)，共70頁(yè)，2023年，2月20日，星期四Corollary(推論)設(shè)x*

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

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

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