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

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

/*NumericalSolutionsofNonlinearEquations（Group）

*/歷史背景

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

求方程幾何意義基本定理

如果函數(shù)在上連續(xù)，且，則至少有一個數(shù)使得，若同時的一階導數(shù)在內(nèi)存在且保持定號，即(或)則這樣的在內(nèi)唯一。

abx*§1二分法

/*BisectionMethod*/原理：若f

C[a,b]，且f(a)·f(b)<0，則f

在(a,b)上必有一根?；舅枷耄褐鸩綄^(qū)間分半，通過判別區(qū)間端點函數(shù)值的符號，進一步搜索有根區(qū)間，將有根區(qū)間縮小到充分小，從而求出滿足給定精度的根的近似值。以此類推終止法則？abx1x2abWhentostop?或不能保證

x

的精度x*2xx*3、由二分法的過程可知：4、對分次數(shù)的計算公式：1、2、令誤差

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

對f(x)

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

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

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

/*TheoryofIteration

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

，且g連續(xù)，則由可知x*=g(x*)，即x*是g的不動點，也就是f

的根。看起來很簡單，令人有點不相信，那么問題是什么呢？誰告訴你這種方法是收斂的呢？f(x)的根g(x)的不動點一、不動點迭代

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

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

時，

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

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

x0

，求x=g(x)

的解.輸入:

初始近似值

x0;容許誤差

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

Nmax.輸出:

近似解x

或失敗信息.Step1Seti=1;Step2While(iNmax)dosteps3-6

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

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

Step5Seti++;

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

Nmax

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

）

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

設為的不動點，在的某鄰域連續(xù)，且，則迭代法(*)局部收斂。證明：因為在的某鄰域連續(xù)，存在鄰域即對則由定理2.3，迭代法(*)對收斂，即局部收斂.注

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

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

（2）設迭代函數(shù)滿足收斂定理的條件，則產(chǎn)生的序列滿足，如果在或的鄰域有若取，必有，此時有

設迭代法的迭代函數(shù)的高階導數(shù)在不動點的鄰域里連續(xù)，則式（*）是階收斂的充要條件是且證明：由Taylor公式：充分性取極限得必要性設迭代式（*）是階收斂的，則有即且（反證法）設不成立則存在最小正整數(shù)，滿足情形一情形二由充分性證明知，迭代式（*）是階收斂的即而的極限不存在與階收斂矛盾證明方法與情形一類似（自己練習）注:（1）一階方法和二階方法迭代步數(shù)的比較，見教材P22

（2）本節(jié)結(jié)論可以推廣到求方程的復數(shù)根（是復數(shù)）。一、使用兩個迭代值的組合方法：§3迭代收斂的加速方法

/*Accelerating

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

將x=g(x)

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

xyy=xy=g(x)x*如：迭代公式為幾何意義如圖示注：

(1)這種迭代對原迭代公式(*)的各近似值在根的兩側(cè)往復地趨于時較為有效；中點(2)只有且較大時，加速效果才明顯。又如：新的迭代函數(shù)為當時根據(jù)定理2.3知，迭代法至少是二階的

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

一般地，由組合得到迭代式或者這個方法稱為艾特肯(Aitken)加速收斂方法

若令則得到所謂的斯蒂芬森(Steffensen)迭代法：Steffensen迭代法的優(yōu)點：可以改進收斂速度，有時也能把不收斂的迭代法改進為收斂的二階方法例4：已知方程在上有一個根（正根）可以選取5種迭代格式：1、即2、即3、即顯示計算結(jié)果

設不動點迭代的迭代函數(shù)在其不動點的某鄰域內(nèi)具有二階連續(xù)導數(shù)，