數(shù)值分析32迭代加速、牛頓法及弦截法

1、第第3章章 非線性方程的數(shù)值解法非線性方程的數(shù)值解法 3.1 方程求根與二分法方程求根與二分法 3.2 迭代法及其收斂性迭代法及其收斂性 3.3 迭代收斂的加速方法迭代收斂的加速方法 3.4 牛頓法牛頓法 3.5 弦截法與拋物線法弦截法與拋物線法3.3 迭代收斂的加速方法迭代收斂的加速方法3.3.1 3.3.1 埃特金加速收斂方法埃特金加速收斂方法 對于收斂的迭代過程，只要迭代足夠多次，就可對于收斂的迭代過程，只要迭代足夠多次，就可以使結(jié)果達(dá)到任意的精度，但是有時迭代過程收斂較以使結(jié)果達(dá)到任意的精度，但是有時迭代過程收斂較慢，從而使計(jì)算量變得很大慢，從而使計(jì)算量變得很大. 設(shè)設(shè) x0 是根是根

2、 x*的某個近似值的某個近似值, 用迭代公式校正一次得用迭代公式校正一次得 x1= (x0)而由微分中值定理，有而由微分中值定理，有.),)()()(0001之間之間與與在在xxxxxxxx 假設(shè)假設(shè) (x) 改變不大改變不大, 近似地取某個近似值近似地取某個近似值 L, 則有則有由于由于 x2- -x*L(x1- -x*).)1 . 3().(01 xxLxx 若將校正值若將校正值 x1= (x0) 再校正一次，又得再校正一次，又得 x2= (x1)將它與將它與(3.1)式聯(lián)立，消去未知的式聯(lián)立，消去未知的L，有，有 xxxxxxxx1021由此推知由此推知.2)(2012201001221

3、20 xxxxxxxxxxxxx . 0lim1 xxxxkkk在計(jì)算了在計(jì)算了 x1 及及 x2 之后，可用上式右端作為之后，可用上式右端作為 x* 的新近的新近似似,記作記作 x1，一般情形是由，一般情形是由xk計(jì)算計(jì)算 xk+1, xk+2，記，記它表明序列它表明序列xk的收斂速度比的收斂速度比xk的收斂速度快的收斂速度快.)2 . 3()., 1 , 0()(2)(2212211 kxxxxxxxxxxkkkkkkkkkk (3.1)式稱為式稱為埃特金埃特金(Aitken) 2加速方法加速方法. 可以證明可以證明也稱為也稱為埃特金埃特金 ( Aitken ) 外推法外推法. 可以證明可

4、以證明:)(1kkxx 為線性收斂為線性收斂,則埃特金法為平方收斂則埃特金法為平方收斂； 注：注：埃特金埃特金(Aitken)加速迭代法也可寫成下面格式加速迭代法也可寫成下面格式(1)1(2)(1)11(2)(1)2(2)1111(2)(1)11()()()2kkkkkkkkkkkxxxxxxxxxxx 若若)(1kkxx 為為 p ( p 1)階收斂，階收斂，)(x 導(dǎo)數(shù)連續(xù)，則埃特金法為導(dǎo)數(shù)連續(xù)，則埃特金法為 2p1 階收斂階收斂.的的 p 階階若若3.3.2 3.3.2 斯蒂芬森斯蒂芬森(Steffensen)(Steffensen)迭代法迭代法 埃特金方法埃特金方法不管原序列不管原序列

5、xk是怎樣產(chǎn)生的，對是怎樣產(chǎn)生的，對xk進(jìn)行加速計(jì)算，得到序列進(jìn)行加速計(jì)算，得到序列 xk . 如果把如果把埃特金加速技埃特金加速技巧與不定點(diǎn)迭代結(jié)合巧與不定點(diǎn)迭代結(jié)合，則可得到如下的迭代法：，則可得到如下的迭代法：),(),(kkkkyzxy )3 . 3()., 1 , 0(2)(21 kxyzxyxxkkkkkkk稱為稱為斯蒂芬森斯蒂芬森(Steffensen)迭代法迭代法. 實(shí)際上實(shí)際上(3.3)是將不定點(diǎn)迭代法是將不定點(diǎn)迭代法(2.2)計(jì)算兩步合并計(jì)算兩步合并成一步得到的，可將它寫成另一種不動點(diǎn)迭代成一步得到的，可將它寫成另一種不動點(diǎn)迭代)4 . 3(), 1 , 0()(1 kxx

6、kk )5 . 3(.)(2)()()(2xxxxxxx 其中其中 對不動點(diǎn)迭代對不動點(diǎn)迭代(3.5)有以下局部收斂性定理有以下局部收斂性定理. 若若x*為為(3.5)定義的迭代函數(shù)定義的迭代函數(shù)(x)的不動點(diǎn)，的不動點(diǎn)，則則x*為為 (x)的不定點(diǎn)的不定點(diǎn). 反之，若反之，若x*為為 (x)的不動點(diǎn)，的不動點(diǎn)，設(shè)設(shè)(x)在在 x* 連續(xù)連續(xù) ，(x*)1，則，則x*是是(x)的不動點(diǎn)，的不動點(diǎn)，且且斯蒂芬森迭代法斯蒂芬森迭代法(3.3)是是2階收斂階收斂的的. 3.4 牛牛 頓頓 法法3.4.1 3.4.1 牛頓法及其收斂性牛頓法及其收斂性)()()(000 xxxfxfxf 牛頓法實(shí)質(zhì)上是

7、一種牛頓法實(shí)質(zhì)上是一種線性化方法線性化方法，其基本思想，其基本思想是將非線性方程是將非線性方程 f(x)=0 逐步歸結(jié)為某種線性方程來逐步歸結(jié)為某種線性方程來求解求解. 設(shè)已知方程設(shè)已知方程f(x)=0有近似根有近似根x0，且在，且在 x0附近附近f(x)可可用一階泰勒多項(xiàng)式近似，表示為用一階泰勒多項(xiàng)式近似，表示為當(dāng)當(dāng) f (x0)0 時，方程時，方程 f(x)=0 可用線性方程可用線性方程(切線切線) 近似近似代替，即代替，即 f(x0)+f (x0)(x- -x0)=0. (4.1)解此線性方程得解此線性方程得)()(000 xfxfxx 得迭代公式得迭代公式此式稱為此式稱為牛頓牛頓(Ne

8、wton)迭代公式迭代公式.)2 . 4(), 1 , 0()()(1 kxfxfxxkkkk牛頓法的牛頓法的幾何意義：幾何意義：設(shè)設(shè)xk是根是根x*的某個近似值，的某個近似值，過曲線過曲線y=f(x)上橫坐標(biāo)為上橫坐標(biāo)為xk的點(diǎn)的點(diǎn)Pk引切線，并將該切引切線，并將該切線與線與x軸交點(diǎn)的橫坐標(biāo)軸交點(diǎn)的橫坐標(biāo)xk+1作為作為x*的新的近似值的新的近似值. 注意注意到切線方程為到切線方程為這樣求得的值這樣求得的值xk+1必滿足必滿足(4.1), 從而就是牛頓公式從而就是牛頓公式(4.2)的計(jì)算結(jié)果的計(jì)算結(jié)果. xyx*xky=f(x)xk+1PkPk+1xk+2).)()(kkkxxxfxfy 牛

9、頓迭代法的收斂性牛頓迭代法的收斂性)()()(xfxfxx 設(shè)設(shè)x*是是 f(x) 的一個單根，即的一個單根，即 f(x*)=0，f (x*)0, 有有. 0)()()(, 0)()()()(2* xfxfxxfxfxfx 牛頓迭代法的迭代函數(shù)為牛頓迭代法的迭代函數(shù)為由定理由定理4可得可得212!122( )()1()lim| lim|()| | 0.()()2!2()kkkkkkxxxxfxxxxxxfx 由此得到，當(dāng)由此得到，當(dāng)x*為為單根單根時，牛頓迭代法在根時，牛頓迭代法在根x*的的鄰近是鄰近是二階二階(平方平方)收斂收斂的的.設(shè)設(shè)f C2a, b, 若若x*為為 f(x)在在a, b

10、上的根，且上的根，且 f (x*) 0，則存在，則存在 x* 的鄰域的鄰域 U, 使得任取使得任取初值初值 x0 U，牛頓法產(chǎn)生的序列，牛頓法產(chǎn)生的序列 xk 收斂到收斂到 x*，且滿，且滿足足12()lim| |.()2()kkkxxfxxxfx 解解 將原方程化為將原方程化為 xex= 0，則，則牛頓迭代公式為牛頓迭代公式為kkxxkkkeexxx 11取取 x0=0.5，迭代得，迭代得x1=0.566311, x2=0.5671431, x3=0.5671433. f(x)=xex， f (x)=1+ex， 例例1 用牛頓迭代法求方程用牛頓迭代法求方程x=ex在在x=0.5附近的根附近的

11、根.例例2 對于給定的正數(shù)對于給定的正數(shù) C，應(yīng)用牛頓法解二次方程，應(yīng)用牛頓法解二次方程, 02 Cx我們現(xiàn)在我們現(xiàn)在證明證明，這種迭代公式對于任意初值，這種迭代公式對于任意初值x00都是收斂的都是收斂的.推導(dǎo)出求開方值推導(dǎo)出求開方值 的計(jì)算公式的計(jì)算公式.C.21)()()(,)(2 xCxxfxfxxCxxf )5 . 4(.211 kkkxCxx事實(shí)上，對事實(shí)上，對(4.5)式進(jìn)行配方整理，易知式進(jìn)行配方整理，易知 .2121CxxCxkkk 以上兩式相除得以上兩式相除得.211 CxCxCxCxkkkk據(jù)此反復(fù)遞推有據(jù)此反復(fù)遞推有)6 . 4(.200kCxCxCxCxkk 記記00

12、xCqxC整理整理(4.6)式，得式，得.1222kkqqCCxk 對任意初值對任意初值x00，總有，總有|q|0)重根重根時，則時，則 f(x) 可表為可表為 f(x)=(x- -x*)mg(x).其中其中 g(x*)0，此時用牛頓迭代法，此時用牛頓迭代法(4.2)求求 x* 仍然收斂，仍然收斂，只是只是 收斂速度將大大減慢收斂速度將大大減慢. 事實(shí)上，因?yàn)榈绞聦?shí)上，因?yàn)榈?()()()()()()(*1kkkkkkkkkkxgxxxmgxgxxxxfxfxx 令令ek=xkx*，則，則)()()(*11kkkkkkkkxgexmgxgeexxe 可見用牛頓法求方程的重根時僅為可

13、見用牛頓法求方程的重根時僅為線性收斂線性收斂. 011)()()(1limlim1 mxgexmgxgeekkkkkkkk從而有從而有兩種兩種的的方法方法：1) ) 取如下迭代函數(shù)取如下迭代函數(shù). 0)(,)()()( xxfxfmxx 則則)13. 4()., 1 , 0()()(1 kxfxfmxxkkkk得到迭代公式得到迭代公式下面介紹一個下面介紹一個求重?cái)?shù)求重?cái)?shù)m的方法的方法，令，令211 kkkkkxxxx 則則112121111kkkkkkkkkkkeeeeeeeeee 求求m重根具有重根具有2階收斂階收斂. 但要知道但要知道x*的的重?cái)?shù)重?cái)?shù)m.由式由式11lim1kkkeem .

14、111limmmmkk 得得因此得估計(jì)因此得估計(jì)m的式子為的式子為.11km 對對f(x)=(x- -x*)mg(x), g(x*)0，令函數(shù)，令函數(shù).)()()()()()()()(xgxxxmgxgxxxfxfx 則為求則為求(x)=0的單根的單根x*的問題，對它用牛頓法是二階的問題，對它用牛頓法是二階(平方平方)收斂的收斂的. 其迭代函數(shù)為其迭代函數(shù)為2) ) 將求重根問題化為求單根問題將求重根問題化為求單根問題. .)()()()()()()()(2xfxfxfxfxfxxxxx )14. 4()., 1 , 0()()()()()(21 kxfxfxfxfxfxxkkkkkkk從而構(gòu)

15、造出迭代方法為從而構(gòu)造出迭代方法為 例例3 用牛頓迭代法求函數(shù)用牛頓迭代法求函數(shù) f(x)=(x- -1)sin(x- -1)+3x- -x3+1=0 在在0.95附近之根附近之根. 解解 取取x0 = 0.95 用牛頓迭代法求用牛頓迭代法求得的得的xk見右表見右表. 可可見見xk收斂很慢收斂很慢.kxk km01234560.950.97442790.98705830.99348780.99673280.99835760.99919010.50900.50470.50070.51252.03692.01902.00282.0511由重根數(shù)由重根數(shù)m=2, 用用(4.13)式加速法，作式加速法

16、，作求得求得 x0=0.95, x1=0.9988559, x2=x3=1.收斂速度大大加快于直接用牛頓迭代公式收斂速度大大加快于直接用牛頓迭代公式.1()()kkkkf xxxmf x 3.5 弦截法與拋物線法弦截法與拋物線法用牛頓法求方程用牛頓法求方程 f(x)=0的根，每步除計(jì)算的根，每步除計(jì)算 f(xk)外外還要算還要算 f (xk)，當(dāng)函數(shù)，當(dāng)函數(shù) f(x) 比較復(fù)雜時，計(jì)算比較復(fù)雜時，計(jì)算 f (x)往往往往比較困難，為此可以利用已求函數(shù)值比較困難，為此可以利用已求函數(shù)值 f(xk),f(xk- -1),來來回避導(dǎo)數(shù)值回避導(dǎo)數(shù)值 f (xk)的計(jì)算的計(jì)算. 這類方法是建立在這類方法

17、是建立在插值原理插值原理基礎(chǔ)上的，下面介紹基礎(chǔ)上的，下面介紹弦截法與拋物線法弦截法與拋物線法.3.5.1 3.5.1 弦截弦截( (割線割線) )法法設(shè)設(shè) xk, xk- -1是是 f(x)=0的近似根，我們利用的近似根，我們利用 f(xk), f(xk- -1)構(gòu)造一次插值多項(xiàng)式構(gòu)造一次插值多項(xiàng)式 p1(x)，并用，并用 p1(x)=0 的根作為方程的根作為方程f(x)=0 的新的近似根的新的近似根 xk+1，由于，由于)1 . 5().()()()()(111kkkkkkxxxxxfxfxfxp 因此有因此有)2 . 5().()()()(111 kkkkkkkxxxfxfxfxx這樣導(dǎo)出

18、的迭代公式這樣導(dǎo)出的迭代公式(5.2)可以看做牛頓公式可以看做牛頓公式.)()(1kkkkxfxfxx 11)()( kkkkxxxfxf中的導(dǎo)數(shù)中的導(dǎo)數(shù) 用用差商差商 取代的結(jié)果取代的結(jié)果.)(kxf (5.2)式有明顯的式有明顯的幾何意義：幾何意義： 設(shè)曲線設(shè)曲線y=f(x)上橫坐標(biāo)為上橫坐標(biāo)為xk- -1和和xk的點(diǎn)分別為的點(diǎn)分別為Pk-1和和Pk, 則差商則差商 表示弦表示弦 的斜率的斜率, 弦弦 的方程為的方程為11)()( kkkkxxxfxfkkPP1 kkPP1 )()()()(00kkkkxxxxxfxfxfy Ox*xk+1xkPkxk- -1yxPk- -1因此，按因此，

19、按(5.2)式求得式求得xk+1實(shí)際上是兩點(diǎn)弦實(shí)際上是兩點(diǎn)弦線線 與與x軸交點(diǎn)軸交點(diǎn)的橫坐標(biāo)的橫坐標(biāo)(令令y=0解出解出x即可即可).這種算法因此這種算法因此而形象地稱為而形象地稱為弦截弦截(割線割線)法法.kkPP1 注：注：弦截法與切線法弦截法與切線法(牛頓法牛頓法)都是線性化分法，但兩都是線性化分法，但兩者有本質(zhì)的區(qū)別者有本質(zhì)的區(qū)別. 切線法在計(jì)算切線法在計(jì)算 xk+1 時只用到前一步時只用到前一步的值的值 xk，而弦截法要用到前面兩步的結(jié)果，而弦截法要用到前面兩步的結(jié)果 xk- -1, xk，因，因此使用這種方法必須先給出兩個開始值此使用這種方法必須先給出兩個開始值 x0, x1.定理

20、定理6 假設(shè)假設(shè)f(x)在根在根x*的鄰域內(nèi)的鄰域內(nèi): |x- -x*|具有具有二階連續(xù)導(dǎo)數(shù)，且對任意二階連續(xù)導(dǎo)數(shù)，且對任意x 有有f (x)0，所取的初，所取的初值值x0, x1 ，那么當(dāng)鄰域，那么當(dāng)鄰域充分小時，弦截法充分小時，弦截法(5.2)將將按階按階.618. 1251 p收斂到收斂到x*. 這里這里p是方程是方程2- - -1=0的正根的正根.定理證明可見定理證明可見P116.因?yàn)橐驗(yàn)?5.2)式用到前兩點(diǎn)式用到前兩點(diǎn)xk- -1和和xk的值，故此方法的值，故此方法又稱為又稱為雙點(diǎn)割線法雙點(diǎn)割線法.).()()()(0001xxxfxfxfxxkkkk 每步只用一個新點(diǎn)每步只用一個

21、新點(diǎn)xk的值，此方法稱為的值，此方法稱為單點(diǎn)割線法單點(diǎn)割線法.如果把如果把(5.2)式中的式中的xk- -1改為改為x0，即迭代公式為，即迭代公式為例例4 用牛頓迭代法和割線法求方程用牛頓迭代法和割線法求方程 f(x)=x4+2x2x3=0， 在區(qū)間在區(qū)間(1, 1.5)內(nèi)之根內(nèi)之根(誤差為誤差為10- -9). 解解 取取x0=1.5，用牛頓法，用牛頓法, 可得可得x6=1.12412303030；取取x0=1.5, x1=1，用，用雙點(diǎn)割線法雙點(diǎn)割線法，迭代，迭代6次得到同樣的次得到同樣的結(jié)果，而采用結(jié)果，而采用單點(diǎn)割線法單點(diǎn)割線法，則迭代，則迭代18次得次得x18=1.124123029

22、.* *3.5.2 3.5.2 拋物線法拋物線法設(shè)已知方程設(shè)已知方程 f(x)=0的三個近似根的三個近似根 xk, xk- -1, xk- -2，我，我們以這三點(diǎn)為節(jié)點(diǎn)構(gòu)造們以這三點(diǎn)為節(jié)點(diǎn)構(gòu)造二次插值多項(xiàng)式二次插值多項(xiàng)式 p2(x)，并適當(dāng)，并適當(dāng)選取選取 p2(x) 的一個零點(diǎn)的一個零點(diǎn) xk+1 作為新的近似根，這樣確作為新的近似根，這樣確定的迭代過程稱為定的迭代過程稱為拋物線法拋物線法，亦稱為，亦稱為密勒密勒(Mller)法法. 在幾何圖形上在幾何圖形上, 這種方法的基本思想是用拋物線這種方法的基本思想是用拋物線y=p2(x)與與 x 軸的交點(diǎn)軸的交點(diǎn) xk+1 作為所求根作為所求根 x

23、* 的近似位置的近似位置.Ox*xk+1xky=P2(x)xk- -2yxy=f(x)xk- -1拋物線法的拋物線法的幾何意義幾何意義見下面圖形見下面圖形.現(xiàn)在推導(dǎo)拋物線法的計(jì)算公式現(xiàn)在推導(dǎo)拋物線法的計(jì)算公式. 插值多項(xiàng)式插值多項(xiàng)式).)(,)(,)()(12112 kkkkkkkkkxxxxxxxfxxxxfxfxp有兩個零點(diǎn)有兩個零點(diǎn)).(,1211 kkkkkkkxxxxxfxxf )3 . 5(.,)(4)(22121 kkkkkkkxxxfxfxfxx 式中式中因子在因子在(5.3)式定出一個值式定出一個值xk+1，我們需要討論根，我們需要討論根式前正負(fù)號的取舍問題式前正負(fù)號的取舍問題.在在xk, xk- -1,