數(shù)值分析課件 第二章2.2

數(shù)值分析第二章解非線性方程的數(shù)值方法一、二分法二、迭代法三、Newton法對給定方程f(x)=0,可以用各種方法轉化成等價方程二、迭代法1迭代法的基本思想若x*是f(x)的根,即若,則有稱x*為函數(shù)的一個不動點.設x0是一個近似解，可以構造序列迭代法(2.2)稱為簡單迭代法或單點迭代法.稱函數(shù)為迭代函數(shù).簡單迭代法(2.2),若迭代序列{xk}保持有界,全在定義域內稱為適定的;若進一步有稱為是收斂的.若收斂，即存在x*使得則由

的連續(xù)性和可得x*=

(x*)，即x*是

的不動點，也就是f(x)的零點。kxk012345671.51.357211.330861.325881.324941.324761.324731.32472例求x3-x-1=0在1.5附近的根x*解xyy=xxyy=xxyy=xxyy=xx*x*x*x*y=

(x)y=

(x)y=

(x)y=

(x)x0p0x1p1x0p0x1p1

x0p0x1p1

x0p0x1p1

x2

2收斂定理和誤差估計定理1

設在[a,b]上有連續(xù)的一階導數(shù),且(1)有(2)則有(1)函數(shù)在[a,b]上存在唯一的不動點x*由迭代公式(2.2)得到的序列(2)都收斂到方程的根x*(3)(4)證明(1)先證明存在性,作函數(shù)由條件(1)可知由連續(xù)函數(shù)根的存在定理可知,必有使得h(x*)=0，即再證明唯一性,設也是一個解,即那么因為L<1,所以有(2)由條件(2)和Lagrange中值定理得因為L<1,所以當時,有(3)和(4)利用(2)的方法令即分別得定理1的幾點說明(i)通常將條件(1)稱為映內性；(ii)條件(2)也可以改為：存在常數(shù)L且0<L<1使得結論仍然成立,這個條件通常稱為壓縮性；(iii)結論(3)說明的誤差大概是常數(shù)乘上Lk,但是一般L未知;(iv)結論(4)說明與有關因此得到迭代法的終止條件3一般迭代法的算法算法：(1)取初始點x0,最大迭代次數(shù)N和精度要求并置k=0；(2)計算(3)若則停止計算；(4)若k=N,則停止計算；否則k=k+1,轉(2).4局部收斂定理迭代序列{xk}在區(qū)間[a,b]上的收斂性通常稱為全局收斂性.實際應用只在不動點x*的鄰近考察收斂性，稱為局部收斂性.定義設有不動點x*,如果存在x*的某個鄰域對任意的迭代(2.2)產生的序列且收斂到x*,則稱(2.2)局部收斂.證明由連續(xù)函數(shù)的性質,存在x*的某個鄰域對任意的有而根據(jù)定理1可以斷定迭代過程(2.2)對任意初值均收斂.定理2若x*為迭代函數(shù)的不動點,在x*的某個鄰域內有連續(xù)導數(shù),且則迭代法(2.2)局部收斂.例只用四則運算不用開方求方程x2-3=0的根解kxk迭代法(1)迭代法(2)迭代法(3)迭代法(4)0123

?

x0

x1

x2

x3

?23987?21.521.5?21.751.734751.732631?21.751.7321431.732051?例設試討論a的取值范圍使迭代公式(2.2)局部收斂到解因為所以由定理2可知只需即所以當時,迭代公式收斂.例5迭代收斂的階則稱該迭代為r階收斂.(C為常數(shù))(1)當r=1時稱為線性收斂，此時C<1；(2)

當r=2時稱為二次收斂，或平方收斂；(3)當r=1,C=0時稱為超線性收斂.二分法線性收斂;定義設迭代

收斂到的不動點x*.記ek=xk

x*，若不動點迭代中，若則線性收斂則迭代公式是p階收斂的，且定理3

設迭代若在x*的某鄰域內連續(xù)，且證明：

根據(jù)泰勒展開有6迭代加速若則迭代公式(2.2)只是線性收斂的取初始點x0,令那么由此得迭代公式如何求L?再令得到由此得Steffensen加速法Steffensen加速法是平方收斂的.三、Newton法1Newton法基本思想設xk是f(x)=0的近似根,將f(x)在xk一階Taylor

展開:(

在xk和x之間)當

f‘(x)0時,即將非線性方程線性化于是xyx*xkxk+1Newton法的幾何意義Newton法的本質就是不斷用切線來近似曲線，因此Newton法也成為切線法.2Newton法的算法(1)取初始點x0,最大迭代次數(shù)N和精度要求ε置k=0;(2)計算(3)若則停止計算;(4)若k=N則停止計算;否則置k=k+1,轉(2).Newton法可以看作下面的不動點迭代：其中

’(x*)=0Newton法至少二階局部收斂3Newton法收斂性證明(略)Newton法也可以看作一類特殊的加速迭代取

(x)=x-f(x)定理4

設f(x)在其零點x*的某個鄰域內二階連續(xù)可導且

0，則存在x*的某個

鄰域N(x*)

=[x*-

,x*

+

],

使得對

x0

N(x*)，Newton法產生的序列以不低于二階的收斂速度收斂到x*.例設計一個二階收斂算法計算

(a>0).解：轉化為求

x2-a=0的正根Newton迭代：二階收斂設x*是f(x)的m(m

2)重根,Newton法是否收斂？4

重根情況所以Newton迭代：線性收斂,且重數(shù)m越高,收斂越慢.提高收斂速度但m通常無法預先知道！法一：取

二階收斂法二：將求f(x)的重根轉化為求另一個函數(shù)的單根.

構造針對

(x)的具有二階收斂的Newton迭代：令，則x*是

(x)的單重根.

例取初始點x0=1.5,分別用Newton法和求重根的兩種方法計算f(x)=(x+1)(x-1)2=0解(1)Newton法迭代公式k012345xk1.51.27271.14411.07441.03781.0191k6789……13xk1.00961.00481.00241.0012……1.0001(2)方法一：取,m=2迭代公式為方法二:迭代公式為取k0123方法一xk1.51.04551.00051.0000方法二xk1.50.96080.99961.0000兩種改進方法的結果比較用Newton迭代公式求解,只能是線性收斂,而改進的兩種方法都具有二階收斂,所以計算速度要快得多.但是很多問題事先不知道根的重數(shù)，所以方法一有時并不實用.Newton法的收斂依賴于初始點的選取.5Newton下山法如果x0偏離所求根x*較遠,則Newton法可能發(fā)散,為防止迭代發(fā)散,我們對迭代過程再附加一項要求,即具有單調性:滿足這項要求的算法稱為下山法

k為數(shù)列中滿足的最大數(shù).§4Newton-RaphsonMethod

弦截法/*Seca