2.1级-牛顿法ppt课件

1、5 5 牛顿迭代法牛顿迭代法 广泛应用的广泛应用的 高效计算方法高效计算方法 基本思想基本思想 非线性方程局部线性化非线性方程局部线性化( (化繁为简化繁为简) ) 特点特点 单根附近具有较高的收敛速度单根附近具有较高的收敛速度 5.1 Newton迭代公式迭代公式 ( Newton( Newton法或切线法或牛顿切线法法或切线法或牛顿切线法 ) ) 1 公式公式 设非线性方程设非线性方程0)( xf)1.5(,其精确解或真解为其精确解或真解为. * x 二次连续可导二次连续可导, ,xk是是(4.1)的的k次近似解次近似解. 2 )( ! 2 )( )()()( kkkk xx f xxxf

2、xfxf 其其中中介于介于x x与与xkxk之间之间 用泰勒展开式的线性部分近似用泰勒展开式的线性部分近似 f(x), f(x),即有即有 并设并设f (x)f (x) 则则f(x)f(x)在点在点xkxk的泰勒展开式的泰勒展开式 为为 )()()( kkk xxxfxfxf k xx )0)( k xf Newton迭代公式迭代公式 )( )( 1 k k kk xf xf xx )3 .5()0)( k xf )()( kkk xxxfxf )( )( k k xf xf 把把 )( )( k k k xf xf xx 作为第作为第k+1k+1次近似解，即得次近似解，即得 说明说明Newt

3、on法是一个逐次线性化方法法是一个逐次线性化方法. 0 令令 )2.5( 2 几何意义几何意义 设曲线设曲线y =f(x)y =f(x)的图象如图示的图象如图示, , 0)( xfxk是是的的k k 次近似次近似, , 曲线曲线 y =f(x) y =f(x) 上对应的点为上对应的点为 ),(,( kk xfx 过该点作曲线过该点作曲线 y=f (x)的切线的切线Lk 交交x x 轴于点轴于点xk+1xk+1 : k L用用)()( kkk xxxfxfy 近似曲线近似曲线y =f(x),y =f(x),则则Lk与与x轴的交点轴的交点 1 k x作为作为f(x)=0f(x)=0的第的第k+1k

4、+1次近似解次近似解. . 即由即由(4.2)(4.2)式令式令y =0y =0得得 )( )( 1 k k kk xf xf xx )0)( k xf 该式就是该式就是NewtonNewton法的迭代公式法的迭代公式, ,因此因此NewtonNewton法也称为切线法法也称为切线法. . x y o )( xfy k L * x )(,( kk xfx k x 1 k x )2.5( 例例1 用牛顿切线法求方程用牛顿切线法求方程x = e-x在在0.5附近的根附近的根 . 解解 由由 x=e-x 得得 xex=1，取取 f (x)=xex-1， xx xeexf )( 取取x0=0.5计算结

5、果如表计算结果如表5-1所示所示 . 0 1 2 3 4 0.5 0.57102044 0.567155569 0.567143291 0.56714329 k k x 表表5-1 说明说明 牛顿切线法比一般迭代法收敛要快得多牛顿切线法比一般迭代法收敛要快得多 . 牛顿公式牛顿公式 k x k k x k x x k kk x ex x exe ex xx k kk k 1 1 1 3 牛顿切线法在数学上的应用实例牛顿切线法在数学上的应用实例 简单迭代法的例简单迭代法的例4 4 迭代迭代1818次次 解方程、求算术平解方程、求算术平 方根、造倒数表等方根、造倒数表等 3. 牛顿切线法在数学上的

6、应用实例牛顿切线法在数学上的应用实例 解方程、求算术平解方程、求算术平 方根、造倒数表等方根、造倒数表等 例例2不用除法运算，构造求不用除法运算，构造求 解解 的值的迭代公式的值的迭代公式. )1( 1 c c 迭代格式迭代格式 令令 , 1 c x 取取 c xxf 1 )( 则则, 1)(, x f 1 1 c x xx , 1 c x 令令取取, 1 )(c x xf 则则, 1 )( 2 x xf 2 2 2 1 1 cxx x c x xx #.2 2 1kkk cxxx ; 1 c 例例3导出计算导出计算 解解 的牛顿公式，并计算的牛顿公式，并计算 )0( cc 计算结果如表计算结

7、果如表5-2所示所示 . 0 1 2 3 4 10 10.750000 10.723837 10.723805 10.723805 k k x 表表5-2 当当k=3时，得时，得8位有效数字位有效数字10.723805. .115 计算计算)0( cc是求是求x2-c = 0的正根，的正根， 解出解出x即得到即得到 .c 取取 f (x)=x2-c ， ,2)(xxf )(5 . 0 2 2 x c x x cx xx 的值在的值在10和和11之间，之间，115取初值取初值x0=10，则由牛顿迭代公式，则由牛顿迭代公式 ), 115 (5 . 0 1 k kk x xx 注注 牛顿法也存在收敛

8、问题，并不牛顿法也存在收敛问题，并不 是对所有函数牛顿法都收敛是对所有函数牛顿法都收敛.如图示如图示: 因此讨论收敛因此讨论收敛 定理定理. . x y o * x )( xfy 1k x k x 2k x 牛顿法迭代会越跑越远牛顿法迭代会越跑越远. . 5.2 Newton法收敛定理法收敛定理 定理定理9 9（NewtonNewton法局部超线性收敛性）法局部超线性收敛性）如果如果f(x)f(x)在解在解x x* *邻近连续邻近连续 可导可导,且且, 0)( * x f 则存在则存在, 0 只要只要,| * 0 xx 收敛于收敛于x x* *即即 . 0lim * * 1 xx xx k k

9、 k )5 .5( Newton序列超线性序列超线性 分析分析Newton迭代公式为迭代公式为, )( )( 1 k k kk xf xf xx 若证其收敛性，可若证其收敛性，可 看作简单迭代，即看作简单迭代，即 ,)( 1 kk xxg 则迭代函数为则迭代函数为 )( )( )( xf xf xxg )0)( x f 由由f(x)f(x)在解在解x x* *邻近连续可导，邻近连续可导， 则则g(x)g(x)在不动点在不动点x x* *处可微，假设处可微，假设. 0)( * x g 则利用推论则利用推论2 2知迭代序列知迭代序列xkxk收敛于收敛于x x* *，而且，而且0)(lim * *

10、* 1 xg xx xx k k k 成立成立. . 0 )()( lim * * xx xgxg k k k 因因此此只只要要证证 证明证明 )( )( )( )( )()( * * * xf xf x xf xf xxgxg )0)( * xf )( )( )( )( * * xf xf x xf xf x )( )()( )( * * xf xfxf xx )( )( )( )( * xx xf f xx ),( )( )()( * xx xf fxf 其中其中 介于介于x与与 * x之间之间. . 即即 , )( )()()()( * * xf fxf xx xgxg 若令若令, *

11、xx那么那么, * x 再由再由 f (x)的连续性知的连续性知),()( * xfxf , 0)()( * xff 那么那么 . 0 )()( lim * * * xx xgxg xx 即即. 0)( * x g 所以由推论所以由推论2 2得得 . 0lim * * 1 xx xx k k k 中值定理中值定理 牛顿法二阶收敛牛顿法二阶收敛 分析分析 由定理由定理9 9知知NewtonNewton法超线性收敛，因此该定理只证法超线性收敛，因此该定理只证(5.6)(5.6) 式式, ,因因(5.6)(5.6)式中有式中有f(x)f(x)的二阶导数及的二阶导数及,)( 2* xxk 因此试用含二

12、阶导数因此试用含二阶导数 项的泰勒展开式项的泰勒展开式. . 定理定理1010（NewtonNewton法局部二阶收敛性）法局部二阶收敛性） 如果如果f(x)f(x)在解在解 * x邻近二次邻近二次 , 0)( * x f则存在则存在, 0 只要只要,| * 0 xxNewton序列二阶序列二阶 , * x即即. )(2 )( )( lim * * 2* * 1 xf xf xx xx k k k )6 .5( 连续可导连续可导, ,且且 收敛于收敛于 证明证明 首先首先 )( )()()()( * k kkk xf xfxfxfxx )0)( * xf 将将)( * xf在点在点 k x 进

13、行泰勒展开进行泰勒展开: : 2* )( !2 )( )()()( k k kkk xx f xxxfxfxf 代入上式代入上式, ,得得 2* 1 )( )(2 )( xx xf f xx k k k k )( )( * 1 k k kk xf xf xxxx 其中其中 k 介于介于 k x与与 * x之间之间. . 说明说明当当0)( * x f时时, ,有有 , 0 )( lim 2* * 1 xx xx k k k Newton法超二阶收敛法超二阶收敛. 定理定理9 9和定理和定理1010都要求满足都要求满足,| * 0 xx对初值要求高对初值要求高, ,初值初值 选取较困难选取较困难

14、. .在实际应用中可以放宽对初值的要求在实际应用中可以放宽对初值的要求,即有以下的非即有以下的非 局部收敛定理局部收敛定理. . . )(2 )( )( lim * * 2* * 1 xf xf xx xx k k k 0)( * x f# # 当当 k时时, ,. * x k 并由并由)(),(xfxf 的连续性的连续性, ,那么那么, * xxk . )(2 )( )( 2* * 1 k k k k xf f xx xx 则则 2* 1 )( )(2 )( xx xf f xx k k k k 其中其中 k 介于介于 k x与与 * x之间之间. . 注注 （1掌握掌握Newton迭代公式并会用迭代公式并会用Newton迭代法编程求方程的近迭代法编程求方程的近 似解似解. （2掌握掌握Newton法局部二阶收敛定理的证明法局部二阶收敛定理的证明. 作业作业 2. 证明计算证明计算的的Newton程序为程序为)2( 3 1 2 1 k kk x a xx (并用此迭代并