數(shù)值分析：第七章 非線性方程的數(shù)值解法

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

1例如：

無精確解法

數(shù)值解法:構(gòu)造數(shù)列，使得：并且

非線性方程

f(x)=0的根2§1二分法

原理：若f

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

在(a,b)上必有一根。3

abx1x2ab什么時(shí)候停止?或不能保證

x

的精度x*2xx*4

誤差分析：第1步產(chǎn)生的有誤差第k步產(chǎn)生的xk

有誤差對(duì)于給定的精度

,可估計(jì)二分法所需的步數(shù)k：①簡單;②對(duì)f(x)

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

5注：用二分法求根，最好先給出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。6例1已知在[1,2]有一個(gè)零點(diǎn)，.二分法計(jì)算結(jié)果見表7.17§2迭代法f(x)=0x=g(x)等價(jià)變換f(x)的根g(x)的不動(dòng)點(diǎn)思路從一個(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

的根。8例.用迭代法求方程在內(nèi)的實(shí)根。取

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

建立迭代格式：

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

9建立迭代格式：

該迭代格式收斂。

建立迭代格式：

該迭代格式收斂。

10結(jié)論：可見，對(duì)的迭代函數(shù)

(1)不唯一(2)發(fā)散或收斂(3)收斂的快、慢。11

xyy=xxyy=xxyy=xxyy=xx*x*x*x*y=g(x)y=g(x)y=g(x)y=g(x)x0p0x1p1x0p0x1p1x0p0x1p1x0p0x1p112

定理考慮方程x=g(x),g(x)C[a,b],若(I)當(dāng)x[a,b]時(shí)，g(x)[a,b]；(II)0L<1使得

|g’(x)|L<1對(duì)x[a,b]成立。則任取x0[a,b]，由xk+1=g(xk)得到的序列收斂于g(x)在[a,b]上的唯一不動(dòng)點(diǎn)。并且有誤差估計(jì)式：(k=1,2,…)且存在極限k13

證明：①g(x)在[a,b]上存在不動(dòng)點(diǎn)？令有根②不動(dòng)點(diǎn)唯一？反證：若不然，設(shè)還有，則在和之間。而③當(dāng)k

時(shí)，

xk收斂到x*？14

④⑤⑥可用來控制收斂精度L越收斂越快小注：定理?xiàng)l件非必要條件，可將[a,b]縮小，定義局部收斂性：若g(x)在x*的某鄰域B={x||xx*|}內(nèi)連續(xù)可微且|g’(x*)|<1，則由x0B開始的迭代收斂。即調(diào)整初值可得到收斂的結(jié)果。15

算法:簡單迭代法

給定初始近似值x0，求x=g(x)的解.Input:

初始近似值

x0;誤差容限

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

Nmax.Output:

近似解

x

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

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

xi*/

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

Step5Seti++;

Step6Setx0=x;/*更新

x0*/Step7Output(ThemethodfailedafterNmaxiterations);/*失敗！*/ STOP.當(dāng)x很大時(shí)，此處可改為16例.用迭代法求方程在內(nèi)的實(shí)根。取

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

理論分析：

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

理論分析：

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

17理論分析：由定理知，迭代格式收斂，和計(jì)算結(jié)果吻合。而且，，由（5）式知，②和③都收斂，但③收斂的效果比②好。

18例求

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

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

因?yàn)榇藭r(shí)定理1中的條件（1）成立，又

所以定理1中條件（2）也成立，對(duì)于[0，1]中任意初值，迭代序列

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

19表7.2

注.

方程也可化為等價(jià)方程

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

20三、迭代過程的收斂速度（收斂階）定義設(shè)迭代序列收斂于

如果存在實(shí)數(shù)

和非零常數(shù)

使成立

則稱序列是階收斂的，

相應(yīng)的迭代方法稱為

階收斂方法.

收斂速度的階：判斷迭代方法收斂快慢的重要標(biāo)準(zhǔn)。

21定理4

設(shè)

是的根，

于的鄰域次連續(xù)可微

，又

(*)

則只要初始值選得充分接近，迭代方法

階收斂，且有

證明首先,

由定理3迭代序列局部收斂性.現(xiàn)在附近展開

22其中

位于

與之間.利用（*）及

有由的連續(xù)性，就完成了定理的證明.

23例：證明迭代格式

是求

的三階方法.

假設(shè)充分靠近，求：

證明：

即為方程的根。

為計(jì)算方便，將方程化為：

（*）

對(duì)（*）式求一階、二階、三階導(dǎo)數(shù)

可以驗(yàn)證

由上述定理知其為三階收斂方法。

且有

24§2迭代法f(x)=0x=g(x)等價(jià)變換f(x)的根g(x)的不動(dòng)點(diǎn)思路從一個(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

的根。25§3.牛頓（Newton）迭代方法

一、基本算法

二、修改的Newton迭代法

三、重根的處理

26一、基本算法

●算法推導(dǎo)

設(shè)，存在的某一鄰域，使得非線性函數(shù)

取迭代初值,滿足

1.建立從的迭代公式

將在點(diǎn)一階Taylor展開：

考慮是的單根27由

（因?yàn)椋?/p>

282.建立從的迭代公式

將在點(diǎn)一階Taylor展開：

依此類推，可得一般的迭代格式：

上述迭代格式稱為求的解的牛頓迭代法。

29●幾何意義在點(diǎn)處作的切線，切線方程為：

求該切線與軸交點(diǎn)的橫坐標(biāo)，正是的值，即

30●依次類推，在點(diǎn)處作的切線，切線方程為：

求該切線與軸交點(diǎn)的橫坐標(biāo)，正是的值，即

∴牛頓迭代法又稱為切線求根法。

31●牛頓迭代法的收斂條件與收斂速度（針對(duì)單根而言）定理設(shè)

則由

牛頓迭代法產(chǎn)生的迭代序列

局部收斂于，且為平方收斂。

證明1：在牛頓迭代法的迭代格式中，迭代函數(shù)為：

∴在的鄰域內(nèi)具有二階連續(xù)導(dǎo)數(shù)，即

32又

牛頓迭代法局部收斂于

又

即有：牛頓迭代法具有二階（平方）收斂速度。

注.定理要求充分接近(局部收斂)，充分的程度

沒有具體的描述，而且若的值沒有取好，有可

能得不到收斂的結(jié)果。

以下定理，給出了滿足一定的條件時(shí)，要使牛頓迭代法收斂，應(yīng)滿足什么條件。

33證明2：Newton迭代法事實(shí)上是一種特殊的不動(dòng)點(diǎn)迭代其中，則收斂由Taylor展開：只要f’(x*)0，則令可得結(jié)論。在單根

附近收斂快34定理設(shè)在區(qū)間上的二階導(dǎo)數(shù)存在，且滿足：

①（保證中至少存在一個(gè)根）

②（保證牛頓迭代法能做下去及方程在上只有一個(gè)根）

③保持符號(hào)不變。

（保證在上是上凸或下凸的）

④初始值

（保證從出發(fā)的）

則牛頓迭代法產(chǎn)生的迭代序列

收斂于

在區(qū)間的唯一根。

35例.

用Newton迭代法建立求

的迭代公式.

解：第一步，將原問題轉(zhuǎn)化為求某一非線性方程的根的問題

方程1

有根號(hào)不方便計(jì)算

方程2

其正根為

關(guān)于方程2

的Newton迭代公式如下：

36利用上述保證條件，令

取區(qū)間

注意：當(dāng)時(shí)，

可以驗(yàn)證，條件①②③成立

取作初始值，則條件④成立

則有：

37例用簡單迭代法和牛頓迭代法求方程在附近的根，取解法一：用簡單迭代法

對(duì)方程建立迭代格式：

取，計(jì)算可得：（在第26步才達(dá)到要求）38解法二：用牛頓迭代法對(duì)方程建立牛頓迭代格式：

取，計(jì)算可得：（在第三步就達(dá)到要求）比較：后者(收斂階為2)比前者(收斂階為1)的收斂快。困難：若很難直接求出來，則計(jì)算量可能會(huì)很大。

39例1用Newton法求方程的根,要求迭代格式一：迭代格式二：格式一:

迭代次數(shù)

27,數(shù)值解0.442852706格式二:迭代次數(shù)3,數(shù)值解

0.44285440140例2求函數(shù)的正實(shí)根精度要求：從圖形中我們可以看出：在x=7和x=8

之間有一單根；在x=1和x=2

之間有一重根。用Matlab畫圖，查看根的分布情形41初值x0＝8.0

時(shí),計(jì)算的是單根,

迭代次數(shù)為28,數(shù)值解為7.600001481

初值x0＝1.0時(shí),計(jì)算的是重根,

迭代次數(shù)為1356,數(shù)值解為1.198631981取初值x0＝8.0,用牛頓迭代公式計(jì)算如下：取初值x0＝1.0,用牛頓迭代公式計(jì)算如下：42二、修改的Newton迭代法●簡化的牛頓迭代法

1.主要思路用某個(gè)定點(diǎn)上的值（或一常數(shù)M）取代如，令，則可得稱它為簡化的牛頓迭代方法。

2.優(yōu)缺點(diǎn)優(yōu)點(diǎn)：計(jì)算簡單缺點(diǎn)：沒有充分利用本身的特性，收斂速度慢，收斂階為1。43

3.幾何意義過點(diǎn)，斜率為的直線方程為：

它與軸交點(diǎn)的橫坐標(biāo)為：

而這正是簡化的牛頓迭代方法中的的表達(dá)式。44三、重根的處理主要討論用牛頓迭代法解決重根的問題

設(shè)的重根（），即

●

直接利用牛頓迭代法求解

迭代格式：

收斂階為1.

即直接用牛頓迭代法求解，效果并不理想.

推導(dǎo)過程：

45顯然，即上述迭代格式確實(shí)可構(gòu)造求方程

的根的迭代格式。

迭代格式：

46又令(*)兩邊同時(shí)減去

若收斂，即

當(dāng)時(shí)，

∴對(duì)重根用牛頓迭代方法只是線性收斂。

47

●用改進(jìn)的牛頓迭代法來求解

1.改進(jìn)的牛頓迭代法

其收斂階為2.

（推導(dǎo)過程：

48若收斂，即

∴此種改進(jìn)的牛頓迭代方法是平方收斂。）

492.改進(jìn)的牛頓迭代法

（將重根情形化為單根情形）

迭代格式為：

其中，

其收斂速度為平方收斂.

（令說明是的單根。

用牛頓迭代法求的根求的重根）

50下山法

——Newton迭代法的

局部微調(diào)：原理：若由xk

得到的xk+1不能使|f|減小，則在xk

和xk+1之間找一個(gè)更好的點(diǎn)，使得。xkxk+1注：=1時(shí)就是Newton迭代公式。當(dāng)=1代入效果不好時(shí)，將減半計(jì)算。51

算法:Newton下山法給定初始近似值x0，求f(x)=0的根.Input:

初始近似值

x0;f(x)和

f’(x);最小步長

xmin;

關(guān)于x的誤差容限TOL1;

關(guān)于

的誤差容限TOL2;

最大迭代次數(shù)

Nmax.Output:

近似解x

或失敗信息.Step1Setk=1;Step2While(kNmax)dosteps3-10

Step3Set=1;

Step4Set

;/*計(jì)算

xk*/

Step5If|xx0|<TOL1thenOutput(x);STOP;/*成功*/

Step6Ifthenx0=x;GOTOStep