一元方程常用迭代法

1、第六章非線性方程組的迭代解法 6.3.2 割線法與拋物線法割線法與拋物線法6.3.1 Newton迭代法迭代法 6.3 一元方程的常用迭代法一元方程的常用迭代法第六章非線性方程組的迭代解法 設(shè)設(shè)x*是方程是方程f(x)=0的實根，的實根， 是是 一個近似根，用一個近似根，用Taylor展開式有展開式有,)(2)()()()(02*kkkkxxfxxxfxfxf *xxk kx這里假設(shè)存在并連續(xù)。若，可得這里假設(shè)存在并連續(xù)。若，可得)( xf0)( kxf,)()(2)()()(2*kkkkkxxxffxfxfxx （6.3.1）其中其中 。若（。若（6.3.1）的右端最后一項忽略不記，作為）的

2、右端最后一項忽略不記，作為x*新的一個近似值，就有新的一個近似值，就有之之間間與與在在kxx* )()(1kkkkxfxfxx ，k=0,1,，（6.3.2）這就是這就是Newton迭代法迭代法。6.3.1 Newton迭代法迭代法 第六章非線性方程組的迭代解法 對（對（6.3.2）可作如下）可作如下的幾何解釋：的幾何解釋： 為函數(shù)為函數(shù)f(x)在點在點 處的切線與處的切線與橫坐標(biāo)軸的交點橫坐標(biāo)軸的交點,見圖見圖6-3.因此因此Newton迭代法也稱迭代法也稱為切線法為切線法.kx1 kxY 0 1kx*xy=f(x)(kxfkxX將將(6.3.2)寫成一般的不動點迭代寫成一般的不動點迭代(6

3、.2.3)的形式的形式,有有,)()()(xfxfxx 2)()()()(xfxfxfx 所以有所以有 Newton迭代法是超線性迭代法是超線性收斂的。更準(zhǔn)確地收斂的。更準(zhǔn)確地,從從(6.3.1)和和(6.3.2)可得下面的定理可得下面的定理.)0)( , 0)(* xfx 第六章非線性方程組的迭代解法 定理定理6.5 , 且且f(x)在包含在包含x*的的一個區(qū)間上有二階連續(xù)導(dǎo)數(shù)一個區(qū)間上有二階連續(xù)導(dǎo)數(shù),則則Newton迭代法（迭代法（6.3.2）至）至少二階收斂，并且少二階收斂，并且0)(, 0)(* xfxf設(shè)設(shè).)(2)()(*2*1limxfxfxxxxkkk 以上討論的是以上討論的是

4、Newton法的局部收斂性。對于某些非線法的局部收斂性。對于某些非線性方程，性方程，Newton法具有全局收斂性。法具有全局收斂性。例例6.8 設(shè)設(shè)a0,對方程對方程 -a=0試證試證:取任何初值取任何初值 0，Newton迭代法都收斂到算術(shù)根迭代法都收斂到算術(shù)根 。a0 x2x ,1,0),(211kxaxxkkk由此可知由此可知證證 對對f(x)= -a, Newton迭代法為迭代法為2x第六章非線性方程組的迭代解法 ).(21,)(21)2(2121221axxxxaxxaaxxxaxkkkkkkkkkk 設(shè)設(shè)x*是是f(x)=0的的m重根重根,，即，即2 m.0)(),()()(* x

5、gxgxxxfm在定理在定理6.5中中,要求要求f(x*)=0 , 即即 是方是方程的單根時程的單根時,Newton法至少具有二階局部收斂性。下面法至少具有二階局部收斂性。下面討論重根的情形討論重根的情形.可見可見,對于任何對于任何 0,都有都有 ,并且并且 非增非增.因此因此 是有下界的非增序列是有下界的非增序列,從而有極限從而有極限x*.對對（6.3.3）的兩邊取極限）的兩邊取極限,得到得到 -a=0,因為因為 0,故有故有x*= 。） ,2,1(kaxk0 xkxkx,0)(* xfa 2*xkx*x第六章非線性方程組的迭代解法 由由Newton迭代函數(shù)迭代函數(shù) 的導(dǎo)數(shù)表達式的導(dǎo)數(shù)表達式

6、,容易求出容易求出)(x.11)(*mx 從而，從而， 。因此只要。因此只要 ，這時的，這時的Newton迭代法線性收斂。迭代法線性收斂。1)(0*x0)( kxf為了改善重根時為了改善重根時Newton法的收斂性，有如下兩種方法的收斂性，有如下兩種方法。法。若改為取若改為取)()()(xfxmfxx 容易驗證容易驗證 。 迭代至少二階收斂迭代至少二階收斂.0)(*x若令若令 ,由由x*是是f(x)的的m重零點，有重零點，有)()()(xfxfx 第六章非線性方程組的迭代解法 例例6.9 方程方程 的根的根 是二重根是二重根.用三用三種方法求解種方法求解.04424 xx2* x解解 (1)用

7、用Newton法有法有.4221kkkkxxxx .)()()()()()()()(2xfxfxfxfxfxxxxx 這種方法也是至少二階收斂的這種方法也是至少二階收斂的.所以，所以，x*是是 的單零點的單零點.可將可將Newton法的迭代函數(shù)修改為法的迭代函數(shù)修改為)(x)()()()()()(*xgxxxmgxgxxx 第六章非線性方程組的迭代解法 (2)由由(6.3.4),m=2迭代公式為迭代公式為.2221kkkkxxxx(3) 由由(6.3.5)確定的修改方法，迭代公式化簡為確定的修改方法，迭代公式化簡為.2)2(221kkkkkxxxxx 三種方法均取三種方法均取 =1.5,計算結(jié)

8、果列于表計算結(jié)果列于表6-7.方法（方法（2）和方）和方法法(3)都是二階方法，都是二階方法， 都達到了誤差限為都達到了誤差限為 的精確度的精確度,而普通而普通的的Newton法是一階的法是一階的,要近要近30次迭代才有相同精度的結(jié)果次迭代才有相同精度的結(jié)果.0 x0 x910 第六章非線性方程組的迭代解法 Xk X0 X1 X2 X3方法(1) 1.5 1.458333333 1.436607143 1.425497619方法(2) 1.5 1.416666667 1.414215686 1.414213562方法(3) 1.5 1.411764706 1.414211438 1.41421

9、3562表表6-7Newton法的每步計算都要求提供函數(shù)的導(dǎo)數(shù)值，當(dāng)函數(shù)法的每步計算都要求提供函數(shù)的導(dǎo)數(shù)值，當(dāng)函數(shù)f(x) 比較復(fù)雜時，提供它的導(dǎo)數(shù)值往往是有困難的。此時，比較復(fù)雜時，提供它的導(dǎo)數(shù)值往往是有困難的。此時，在在Newton迭代法（迭代法（6.3.2）中，可用）中，可用 或常數(shù)或常數(shù)D取代取代 迭代式變?yōu)榈阶優(yōu)?(0 xf),(kxf)()(01xfxfxxkkk.)(1Dxfxxkkk或或這稱為這稱為簡化簡化Newton法法。其迭代函數(shù)為。其迭代函數(shù)為第六章非線性方程組的迭代解法 ?；駾xfxxxfxfxx)()()( )()(0簡化簡化Newton法一般為線性收斂。法一般為

10、線性收斂。0)(* x通通常常 6.3.2 割線法與拋物線法割線法與拋物線法這就是割線法的計算公式。其幾何解釋為通過這就是割線法的計算公式。其幾何解釋為通過 和作的割線，割線與和作的割線，割線與x軸交點的橫坐軸交點的橫坐標(biāo)是標(biāo)是 。)(,(kkxfx1 kx 為了回避導(dǎo)數(shù)值為了回避導(dǎo)數(shù)值 的計算，除了前面的簡化的計算，除了前面的簡化Newton法之外，我們也可用點法之外，我們也可用點 上的差商代上的差商代替替 ，得到迭代公式，得到迭代公式)(kxf1, kkxx)(kxf)()()(111kkkkkkkxfxfxfxxxx)( xfy )(,(11 kkxfx第六章非線性方程組的迭代解法 與與

11、Newton法不同的是，用割線法計算法不同的是，用割線法計算 時，時，需要有兩個初始值需要有兩個初始值 。計算計算 時，要保留上步時，要保留上步的的 和和 ，再計算一次函數(shù)值，再計算一次函數(shù)值 。所以割線。所以割線法是一種兩步迭代法，不能直接用單步迭代法收斂性分法是一種兩步迭代法，不能直接用單步迭代法收斂性分析的結(jié)果。下面給出割線法收斂性的定理。析的結(jié)果。下面給出割線法收斂性的定理。1 kx10 xx 和和1 kx)(1 kxf)(kxf1 kx定理定理6.6 設(shè)設(shè) ,在區(qū)間在區(qū)間 上的二上的二階導(dǎo)數(shù)連續(xù)階導(dǎo)數(shù)連續(xù),且且 。又設(shè)。又設(shè) ，其中，其中 則當(dāng)則當(dāng) 時，由（時，由（6.3.6）式產(chǎn)生

12、的序列）式產(chǎn)生的序列 ，并且按并且按 階收斂到根階收斂到根 。證證 由（由（6.3.6）兩邊減去）兩邊減去 ，利用均差的記號有，利用均差的記號有 ,* xx1 M0)( xf0)(* xf)(min2)(maxxfxfMxx )7 . 3 . 6(10,xx kx618. 12/ )51( p*x*x第六章非線性方程組的迭代解法 因因f(x)有二階導(dǎo)數(shù)，所以有有二階導(dǎo)數(shù)，所以有)( ,1kkkfxxf )( 21,*1kkkfxxxf )8 . 3 . 6(k其中其中 在在 之間，之間， 在包含在包含 的最小區(qū)間的最小區(qū)間上。仍記上。仍記 ，由（，由（6.3.8）有）有 kkxx,1k*1,x

13、xxkk*xxekk 11)( 2)( kkkkkeeffe )9 . 3 . 6(,1)(1*kkkkxxfxxfxx ,)(1*1*1*kkkkkkxxfxxxfxxxx *11()(),kkkkkfxfxxxxxfxx第六章非線性方程組的迭代解法 若若 則利用（則利用（6.3.7）和）和 得：得： kkee,11M 211MeeMekkk這說明這說明 時，序列時，序列 。又由于：。又由于： 10, xx kx0121)(eMeMeeMekkkkk 所以，當(dāng)所以，當(dāng) 時，時， ，即，即 收斂到收斂到 。從上式也可知。從上式也可知割線法至少是一階收斂的。割線法至少是一階收斂的。 進一步確定收

14、斂的階，這里我們給出一個不嚴(yán)格的證進一步確定收斂的階，這里我們給出一個不嚴(yán)格的證明。由（明。由（6.3.9）有）有k0kekx*x1*! kkkeeMe)10. 3 . 6(這里這里 。令。令 ，代入（，代入（6.3.10）得得)( 2/)( *xfxfM kmeMdk* 11 kkkmmm0*0eMm 1*1eMm 第六章非線性方程組的迭代解法 我們知道，差分方程我們知道，差分方程 的通解為的通解為 ，這里，這里， 為任意常數(shù)，為任意常數(shù)，11 kkkzzzkkkccz2211 21,cc618. 12511 618. 02512 和和 是方程是方程 的兩個跟。當(dāng)?shù)膬蓚€跟。當(dāng)k充分大時，充分

15、大時， 設(shè)設(shè) ，c為常數(shù)，則有為常數(shù)，則有 1 2 012kkcm1 1*1*111!11)()( MdMeekkmmkk這說明割線法的收斂階為這說明割線法的收斂階為 。定理證畢。定理證畢 。618. 11類似于簡單類似于簡單Newton法，有如下的單點割線法法，有如下的單點割線法 , 2 , 1),()()(001 kxfxfxfxxxxkkkkk第六章非線性方程組的迭代解法 其迭代函數(shù)為其迭代函數(shù)為)()()()(00 xfxfxxxfxxk于是于是 )( )( 1)( *fxfx其中其中 在在 和和 之間。由此可見，單點割線法一般為線之間。由此可見，單點割線法一般為線形收斂。但當(dāng)形收斂。

16、但當(dāng) 變化不大時，變化不大時， ，收斂仍可，收斂仍可能很快。能很快。0 x*x)( xf0)( *x例例10 分別用單點割線法，割線法和分別用單點割線法，割線法和Newton法求解法求解Leonardo方程方程020102)(23xxxxf解解 1043)( 2xxxf46)( xxf由于由于 故，在（故，在（1，2）內(nèi)）內(nèi)僅有一個僅有一個根。根。對于單點割線法和割線法，取對于單點割線法和割線法，取 計計算結(jié)果如表算結(jié)果如表6-8。 012)2(, 07) 1 (, 0)( ffxf2, 110 xx第六章非線性方程組的迭代解法 對于對于Newton法，由于在（法，由于在（0.2）內(nèi)）內(nèi) ，故

17、取，故取 ，計算結(jié)果如表計算結(jié)果如表6-8 0)2(, 0)( fxf20 x5x單點割線法單點割線法割線法割線法Newton法法1.3684210531.3684210531.3833887041.3688512631.3688504691.3688694191.3688032981.3688081041.3688081091.3688086441.3688081081.368808108 表表 6-8由計算結(jié)果知，對單點割線法有由計算結(jié)果知，對單點割線法有 ，對割線法，對割線法有有 ，對，對Newton法有法有 ，故取，故取 545105 . 0 xx845104 . 0 xx845101

18、 . 0 xx368808108. 1*x第六章非線性方程組的迭代解法 割線法的收斂階雖然低于割線法的收斂階雖然低于Newton法，但迭代一次只法，但迭代一次只需計算一次需計算一次 函數(shù)值，不需計算導(dǎo)數(shù)值函數(shù)值，不需計算導(dǎo)數(shù)值 ，所，所以效率高，實際問題中經(jīng)常使用。與割線法類似，我們可以效率高，實際問題中經(jīng)常使用。與割線法類似，我們可通過三點通過三點 作一條拋物線，適作一條拋物線，適當(dāng)選取它與當(dāng)選取它與x軸交點的橫坐標(biāo)作為軸交點的橫坐標(biāo)作為 。這樣產(chǎn)生迭代序列。這樣產(chǎn)生迭代序列的方法稱為的方法稱為拋物線法拋物線法，亦稱，亦稱Muller方法方法。 1 kx)(kxf)( kxf).,1, 2)(,(kkkixfxii 下面給出拋物線法的計算公式。過三點下面給出拋物線法的計算公式。過三點 的插值多項式為的插值多項式為).,1, 2)(,(kkkixfxii )(,)(,)()(12112 kkkkkkkkkxxxxxxxfxxxxfxfxp221)(,)()(kkkkkkkxxxxxfxxxf 其中其中 ,)(,2111 kkkkkkkkxxxfxxxxf 第六章非線性方程組的迭代解法 kx1kx二次方程二次方程 有兩個根，我們選擇接近有兩個根，我們選擇接近 的一個作的一個作 ，即得迭代公式即得迭代公式 0)