割線法與拋物線法ppt課件

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

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

3、是超線性收斂的。更準(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 以上討論的是以上討論的是Newton法的部分收斂性。對于某些非線法的部分收斂性。對于某些非線性方程，性方程，Newton法具有全局收斂性。法具有全局收斂性。例6.8

4、 設(shè)a0,對方程 -a=0試證:取任何初值 0，Newton迭代法都收斂到算術(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)(),()()(* xgxgxxxfm在定理在定理6.5中中,要求要求f(x*)=0 , 即即 是方是方程的單根時程的單根時,Newton法至少具有二階部分收斂性。下面法至少具有二階部分收斂性。下面討論重根

5、的情形討論重根的情形.可見可見,對于任何對于任何 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á)式的導(dǎo)數(shù)表達(dá)式,容易求出容易求出)(x.11)(*mx 從而，從而， 。因此只需。因此只需 ，這時的，這時的Newton迭代法線性收斂。迭代法線性收斂。1)(0*x0)( kxf為了改善重根時為了改善重根

6、時Newton法的收斂性，有如下兩種方法的收斂性，有如下兩種方法。法。假設(shè)改為取假設(shè)改為取)()()(xfxmfxx 容易驗證容易驗證 。 迭代至少二階收斂迭代至少二階收斂.0)(*x假設(shè)令假設(shè)令 ,由由x*是是f(x)的的m重零點，有重零點，有)()()(xfxfx 第六章非線性方程組的迭代解法 例例6.9 方程方程 的根的根 是二重根是二重根.用三用三種方法求解種方法求解.04424 xx2* x解解 (1)用用Newton法有法有.4221kkkkxxxx .)()()()()()()()(2xfxfxfxfxfxxxxx 這種方法也是至少二階收斂的這種方法也是至少二階收斂的.所以，所以

7、，x*是是 的單零點的單零點.可將可將Newton法的迭代函數(shù)修正為法的迭代函數(shù)修正為)(x)()()()()()(*xgxxxmgxgxxx 第六章非線性方程組的迭代解法 (2)由由(6.3.4),m=2迭代公式為迭代公式為.2221kkkkxxxx(3) 由由(6.3.5)確定的修正方法，迭代公式化簡為確定的修正方法，迭代公式化簡為.2)2(221kkkkkxxxxx 三種方法均取三種方法均取 =1.5,計算結(jié)果列于表計算結(jié)果列于表6-7.方法方法2和方和方法法(3)都是二階方法，都是二階方法， 都到達(dá)了誤差限為都到達(dá)了誤差限為 的準(zhǔn)確度的準(zhǔn)確度,而普通而普通的的Newton法是一階的法是

8、一階的,要近要近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.414213562表表6-7Newton法的每步計算都要求提供函數(shù)的導(dǎo)數(shù)值，當(dāng)函數(shù)法的每步計算都要求提供函數(shù)的導(dǎo)數(shù)值，當(dāng)函數(shù)f(x) 比較復(fù)雜時，提供它的導(dǎo)數(shù)值往往是有困難的。此時，比較復(fù)雜時，提供它

9、的導(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法普通為線性收斂。法普通為線性收斂。0)(* x通通常常 6.3.2 割線法與拋物線法割線法與拋物線法這就是割線法的計算公式。其幾何解釋為經(jīng)過這就是割線法的計算公式。其幾何解釋為經(jīng)過 和作的割線，割線與和作的割線，割線與x軸

10、交點的橫坐軸交點的橫坐標(biāo)是標(biāo)是 。)(,(kkxfx1 kx 為了逃避導(dǎo)數(shù)值為了逃避導(dǎo)數(shù)值 的計算，除了前面的簡化的計算，除了前面的簡化Newton法之外，我們也可用點法之外，我們也可用點 上的差商替上的差商替代代 ，得到迭代公式，得到迭代公式)(kxf1, kkxx)(kxf)()()(111kkkkkkkxfxfxfxxxx)( xfy )(,(11 kkxfx第六章非線性方程組的迭代解法 與與Newton法不同的是，用割線法計算法不同的是，用割線法計算 時，時，需求有兩個初始值需求有兩個初始值 。計算。計算 時，要保管上步時，要保管上步的的 和和 ，再計算一次函數(shù)值，再計算一次函數(shù)值 。

11、所以割線法。所以割線法是一種兩步迭代法，不能直接用單步迭代法收斂性分析是一種兩步迭代法，不能直接用單步迭代法收斂性分析的結(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)生的序列式產(chǎn)生的序列 ，并且按并且按 階收斂到根階收斂到根 。證證 由由6.3.6兩邊減去兩邊減去 ，利用均差的記號有，利用均差的記號有 ,* xx1 M0)( xf0)(* xf)(min2)(ma

12、xxfxfMxx )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,xxxkk*xxekk 11)( 2)( kkkkkeeffe )9 . 3 . 6(,1)(1*kkkkxxfxxfxx ,)(1*1*1*kkkkkkxxfxxxfxxxx *11()(),kkkkkfxfxxxx

13、xfxx第六章非線性方程組的迭代解法 假設(shè)假設(shè) 那么利用那么利用6.3.7和和 得：得： kkee,11M 211MeeMekkk這闡明這闡明 時，序列時，序列 。又由于：。又由于： 10, xx kx0121)(eMeMeeMekkkkk 所以，當(dāng)所以，當(dāng) 時，時， ，即，即 收斂到收斂到 。從上式也可知。從上式也可知割線法至少是一階收斂的。割線法至少是一階收斂的。 進(jìn)一步確定收斂的階，這里我們給出一個不嚴(yán)厲的證進(jìn)一步確定收斂的階，這里我們給出一個不嚴(yán)厲的證明。由明。由6.3.9有有k0kekx*x1*! kkkeeMe)10. 3 . 6(這里這里 。令。令 ，代入，代入6.3.10得得)

14、( 2/)( *xfxfM kmeMdk* 11 kkkmmm0*0eMm 1*1eMm 第六章非線性方程組的迭代解法 我們知道，差分方程我們知道，差分方程 的通解為的通解為 ，這里，這里， 為恣意常數(shù)，為恣意常數(shù)，11 kkkzzzkkkccz2211 21,cc618. 12511 618. 02512 和和 是方程是方程 的兩個跟。當(dāng)?shù)膬蓚€跟。當(dāng)k充分大時，充分大時， 設(shè)設(shè) ，c為常數(shù)，那么有為常數(shù)，那么有 1 2 012kkcm1 1*1*111!11)()( MdMeekkmmkk這闡明割線法的收斂階為這闡明割線法的收斂階為 。定理證畢。定理證畢 。618. 11類似于簡單類似于簡單

15、NewtonNewton法，有如下的單點割線法法，有如下的單點割線法 , 2 , 1),()()(001 kxfxfxfxxxxkkkkk第六章非線性方程組的迭代解法 其迭代函數(shù)為其迭代函數(shù)為)()()()(00 xfxfxxxfxxk于是于是 )( )( 1)( *fxfx其中其中 在在 和和 之間。由此可見，單點割線法普通為線之間。由此可見，單點割線法普通為線形收斂。但當(dāng)形收斂。但當(dāng) 變化不大時，變化不大時， ，收斂仍能，收斂仍能夠很快。夠很快。0 x*x)( xf0)( *x例例10 10 分別用單點割線法，割線法和分別用單點割線法，割線法和NewtonNewton法求解法求解Leona

16、rdoLeonardo方程方程020102)(23xxxxf解解 1043)( 2xxxf46)( xxf由于由于 故，在故，在1 1，2 2內(nèi)僅有一個根。對于單點割線法和割線法，取內(nèi)僅有一個根。對于單點割線法和割線法，取 計算結(jié)果如表計算結(jié)果如表6-86-8。 012)2(, 07) 1 (, 0)( ffxf2, 110 xx第六章非線性方程組的迭代解法 對于對于NewtonNewton法，由于在法，由于在0.20.2內(nèi)內(nèi) ，故取，故取 ，計算結(jié)果如表計算結(jié)果如表6-8 6-8 0)2(, 0)( fxf20 x5x單點割線法單點割線法割線法割線法Newton法法1.3684210531.

17、3684210531.3833887041.3688512631.3688504691.3688694191.3688032981.3688081041.3688081091.3688086441.3688081081.368808108 表表 6-8由計算結(jié)果知，對單點割線法有由計算結(jié)果知，對單點割線法有 ，對割線法，對割線法有有 ，對，對NewtonNewton法有法有 ，故取，故取 545105 . 0 xx845104 . 0 xx845101 . 0 xx368808108. 1*x第六章非線性方程組的迭代解法 割線法的收斂階雖然低于割線法的收斂階雖然低于Newton法，但迭代一次只

18、法，但迭代一次只需計算一次需計算一次 函數(shù)值，不需計算導(dǎo)數(shù)值函數(shù)值，不需計算導(dǎo)數(shù)值 ，所，所以效率高，實踐問題中經(jīng)常運(yùn)用。與割線法類似，我們可以效率高，實踐問題中經(jīng)常運(yùn)用。與割線法類似，我們可經(jīng)過三點經(jī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)(2