2.1割線法與拋物線法ppt課件

1、第六章非線性方程組的迭代解法 6.3.2 割線法與拋物線法割線法與拋物線法6.3.1 Newton迭代法迭代法 6.3 一元方程的常用迭代法一元方程的常用迭代法第六章非線性方程組的迭代解法 設(shè)x*是方程f(x)=0的實(shí)根， 是 一個(gè)近似根，用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的右端最后一項(xiàng)忽略不記，作的右端最后一項(xiàng)忽略不記，作為為x*新的一個(gè)近

2、似值，就有新的一個(gè)近似值，就有之之間間與與在在kxx* )()(1kkkkxfxfxx ，k=0,1,，（6.3.2）這就是這就是Newton迭代法。迭代法。6.3.1 Newton迭代法迭代法 第六章非線性方程組的迭代解法 對(duì)6.3.2可作如下的幾何解釋： 為函數(shù)f(x)在點(diǎn) 處的切線與橫坐標(biāo)軸的交點(diǎn),見圖6-3.因此Newton迭代法也稱為切線法.kx1 kxY 0 1kx*xy=f(x)(kxfkxX將將(6.3.2)寫成一般的不動(dòng)點(diǎn)迭代寫成一般的不動(dòng)點(diǎn)迭代(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*的的一個(gè)區(qū)間上有二階連續(xù)導(dǎo)數(shù)一個(gè)區(qū)間上有二階連續(xù)導(dǎo)數(shù),則則Newton迭代法迭代法6.3.2至至少二階收斂，并且少二階收斂，并且0)(, 0)(* xfxf設(shè)設(shè).)(2)()(*2*1limxfxfxxxxkkk 以上討論的是以上討論的是Newton法的局部收斂性。對(duì)于某些非線法的局部收斂性。對(duì)于某些非線性方程，性方程，Newton法具有全局收斂性。法具有全局收斂性。例6

4、.8 設(shè)a0,對(duì)方程 -a=0試證:取任何初值 0，Newton迭代法都收斂到算術(shù)根 。a0 x2x ,1,0),(211kxaxxkkk由此可知由此可知證證 對(duì)對(duì)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 , 即即 是方是方程的單根時(shí)程的單根時(shí),Newton法至少具有二階局部收斂性。下面法至少具有二階局部收斂性。下面討論

5、重根的情形討論重根的情形.可見可見,對(duì)于任何對(duì)于任何 0,都有都有 ,并且并且 非增非增.因而因而 是有下界的非增序列是有下界的非增序列,從而有極限從而有極限x*.對(duì)對(duì)6.3.3的兩邊取極限的兩邊取極限,得到得到 -a=0,因?yàn)橐驗(yàn)?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 從而，從而， 。因此只要。因此只要 ，這時(shí)的，這時(shí)的Newton迭代法線性收斂。迭代法線性收斂。1)(0*x0)( kxf為了改善重根時(shí)為了改善

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

7、*是是 的單零點(diǎn)的單零點(diǎn).可將可將Newton法的迭代函數(shù)修改為法的迭代函數(shù)修改為)(x)()()()()()(*xgxxxmgxgxxx 第六章非線性方程組的迭代解法 (2)由由(6.3.4),m=2迭代公式為迭代公式為.2221kkkkxxxx(3) 由由(6.3.5)確定的修改方法，迭代公式化簡為確定的修改方法，迭代公式化簡為.2)2(221kkkkkxxxxx 三種方法均取三種方法均取 =1.5,計(jì)算結(jié)果列于表計(jì)算結(jié)果列于表6-7.方法方法2和方和方法法(3)都是二階方法，都是二階方法， 都達(dá)到了誤差限為都達(dá)到了誤差限為 的精確度的精確度,而普通而普通的的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法的每步計(jì)算都要求提供函數(shù)的導(dǎo)數(shù)值，當(dāng)函數(shù)法的每步計(jì)算都要求提供函數(shù)的導(dǎo)數(shù)值，當(dāng)函數(shù)f(x) 比較復(fù)雜時(shí)，提供它的導(dǎo)數(shù)值往往是有困難的。此時(shí)，比較復(fù)雜時(shí)，提供它的導(dǎo)

9、數(shù)值往往是有困難的。此時(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ì)算公式。其幾何解釋為通過這就是割線法的計(jì)算公式。其幾何解釋為通過 和作的割線，割線與和作的割線，割線與x軸交點(diǎn)

10、的橫坐軸交點(diǎn)的橫坐標(biāo)是標(biāo)是 。)(,(kkxfx1 kx 為了回避導(dǎo)數(shù)值為了回避導(dǎo)數(shù)值 的計(jì)算，除了前面的簡化的計(jì)算，除了前面的簡化Newton法之外，我們也可用點(diǎn)法之外，我們也可用點(diǎn) 上的差商代上的差商代替替 ，得到迭代公式，得到迭代公式)(kxf1, kkxx)(kxf)()()(111kkkkkkkxfxfxfxxxx)( xfy )(,(11 kkxfx第六章非線性方程組的迭代解法 與與Newton法不同的是，用割線法計(jì)算法不同的是，用割線法計(jì)算 時(shí)，時(shí)，需要有兩個(gè)初始值需要有兩個(gè)初始值 。計(jì)算。計(jì)算 時(shí)，要保留上步時(shí)，要保留上步的的 和和 ，再計(jì)算一次函數(shù)值，再計(jì)算一次函數(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) 時(shí)，由時(shí)，由6.3.6式產(chǎn)生的序列式產(chǎn)生的序列 ，并且按并且按 階收斂到根階收斂到根 。證證 由由6.3.6兩邊減去兩邊減去 ，利用均差的記號(hào)有，利用均差的記號(hào)有 ,* xx1 M0)( xf0)(* xf)(min2)(maxxfx

12、fMxx )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()(),kkkkkfxfxxxxxfxx

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

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

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

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

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

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