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

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

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

(x*)，即x*是

的不動(dòng)點(diǎn)，也就是f(x)的零點(diǎn)。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收斂定理和誤差估計(jì)定理1

設(shè)在[a,b]上有連續(xù)的一階導(dǎo)數(shù),且(1)有(2)則有(1)函數(shù)在[a,b]上存在唯一的不動(dòng)點(diǎn)x*由迭代公式(2.2)得到的序列(2)都收斂到方程的根x*(3)(4)證明(1)先證明存在性,作函數(shù)由條件(1)可知由連續(xù)函數(shù)根的存在定理可知,必有使得h(x*)=0，即再證明唯一性,設(shè)也是一個(gè)解,即那么因?yàn)長(zhǎng)<1,所以有(2)由條件(2)和Lagrange中值定理得因?yàn)長(zhǎng)<1,所以當(dāng)時(shí),有(3)和(4)利用(2)的方法令即分別得定理1的幾點(diǎn)說(shuō)明(i)通常將條件(1)稱為映內(nèi)性；(ii)條件(2)也可以改為：存在常數(shù)L且0<L<1使得結(jié)論仍然成立,這個(gè)條件通常稱為壓縮性；(iii)結(jié)論(3)說(shuō)明的誤差大概是常數(shù)乘上Lk,但是一般L未知;(iv)結(jié)論(4)說(shuō)明與有關(guān)因此得到迭代法的終止條件3一般迭代法的算法算法：(1)取初始點(diǎn)x0,最大迭代次數(shù)N和精度要求并置k=0；(2)計(jì)算(3)若則停止計(jì)算；(4)若k=N,則停止計(jì)算；否則k=k+1,轉(zhuǎn)(2).4局部收斂定理迭代序列{xk}在區(qū)間[a,b]上的收斂性通常稱為全局收斂性.實(shí)際應(yīng)用只在不動(dòng)點(diǎn)x*的鄰近考察收斂性，稱為局部收斂性.定義設(shè)有不動(dòng)點(diǎn)x*,如果存在x*的某個(gè)鄰域?qū)θ我獾牡?2.2)產(chǎn)生的序列且收斂到x*,則稱(2.2)局部收斂.證明由連續(xù)函數(shù)的性質(zhì),存在x*的某個(gè)鄰域?qū)θ我獾挠卸鶕?jù)定理1可以斷定迭代過(guò)程(2.2)對(duì)任意初值均收斂.定理2若x*為迭代函數(shù)的不動(dòng)點(diǎn),在x*的某個(gè)鄰域內(nèi)有連續(xù)導(dǎo)數(shù),且則迭代法(2.2)局部收斂.例只用四則運(yùn)算不用開方求方程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?例設(shè)試討論a的取值范圍使迭代公式(2.2)局部收斂到解因?yàn)樗杂啥ɡ?可知只需即所以當(dāng)時(shí),迭代公式收斂.例5迭代收斂的階則稱該迭代為r階收斂.(C為常數(shù))(1)當(dāng)r=1時(shí)稱為線性收斂，此時(shí)C<1；(2)

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

收斂到的不動(dòng)點(diǎn)x*.記ek=xk

x*，若不動(dòng)點(diǎn)迭代中，若則線性收斂則迭代公式是p階收斂的，且定理3

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

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

展開:(

在xk和x之間)當(dāng)

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

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

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

設(shè)f(x)在其零點(diǎn)x*的某個(gè)鄰域內(nèi)二階連續(xù)可導(dǎo)且

0，則存在x*的某個(gè)

鄰域N(x*)

=[x*-

,x*

+

],

使得對(duì)

x0

N(x*)，Newton法產(chǎn)生的序列以不低于二階的收斂速度收斂到x*.例設(shè)計(jì)一個(gè)二階收斂算法計(jì)算

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

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

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

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

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

構(gòu)造針對(duì)

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

(x)的單重根.

例取初始點(diǎn)x0=1.5,分別用Newton法和求重根的兩種方法計(jì)算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兩種改進(jìn)方法的結(jié)果比較用Newton迭代公式求解,只能是線性收斂,而改進(jìn)的兩種方法都具有二階收斂,所以計(jì)算速度要快得多.但是很多問(wèn)題事先不知道根的重?cái)?shù)，所以方法一有時(shí)并不實(shí)用.Newton法的收斂依賴于初始點(diǎn)的選取.5Newton下山法如果x0偏離所求根x*較遠(yuǎn),則Newton法可能發(fā)散,為防止迭代發(fā)散,我們對(duì)迭代過(guò)程再附加一項(xiàng)要求,即具有單調(diào)性:滿足這項(xiàng)要求的算法稱為下山法

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

弦截法/*Seca