数值分析4(牛顿迭代法)

1、1/25*lim()nnxx 0101()()nnxxxxx 不动点框架不动点框架:*收敛性收敛性 收敛速度收敛速度(1)( )( *)( *)( *)0 ( *)0rrxxxx |( )| 1x 2/25数值分析4Newton迭代格式迭代格式Newton迭代法的收敛性迭代法的收敛性Newton迭代法收敛速度迭代法收敛速度弦截法迭代格式弦截法迭代格式*3/25*Nature and Nature law lay hid in night. God said, Let Newton be, and all was light. Alexander Pope4/25( ) ( )( )xxx f

2、xx *()1()()0 xxfx *()0, ( )1/( )fxxfx 如如果果取取1:()/()nnnnxxf xfx 牛牛顿顿迭迭代代法法给定初值给定初值 x0 , 迭代产生数列迭代产生数列x0, x1, x2, xn, *5/25设设 x*是方程是方程 f(x)=0 的根的根, x0是是x*的近似值。的近似值。在在 x0 附近对函数做附近对函数做局部线性化局部线性化)()()(000 xxxfxfxf x1比比x0更接近于更接近于x*x0 x1x*0)()(000 xxxfxf f(x) = 0 )()(0001xfxfxx *6/25应用应用求正数平方根算法求正数平方根算法设设C

3、0,Cx x2 C = 0令令 f(x) = x2 C , 则则xxf2)( nnnnxCxxx221 211nnnxCxx *7/25初值初值: x0=1.5迭代格式迭代格式: xn+1=0.5(xn+2/xn) (n = 0,1,2,)例例1. 平方根算法求平方根算法求2 xn | en |1.416666666666667 2.45e-0031.414215686274510 2.12e-0061.414213562374690 1.59e-0121.414213562373095 2.22e-0161.414213562373095 2.22e-016表表1 1 平方根算法实验平方根算

4、法实验*8/25收敛性收敛性: (1) 符合不动点框架符合不动点框架00, 2 (1) ()nxxn 只只有有界界要要112222nnnxxx 22121(2)22nnnnxxxx *(2) 从序列收敛的角度从序列收敛的角度(单调有界序列单调有界序列)21212=0 2(2)nnnnnnnxxxxxxx 单单调调下下降降9/25由此可知由此可知平方根算法具有平方根算法具有 2 阶收敛速度。阶收敛速度。 nnnxxx21)2(221 221|2|2|lim21 nnnxx222121 nnnxxx22121(2)22nnnnxxxx 2lim nnx思考思考: 如何求倒数、平方根和立方根？如何求

5、倒数、平方根和立方根？10/25Newton迭代法的局部收敛性迭代法的局部收敛性定理定理2.7 设设 f(x) 在点在点x*的某邻域内具有二阶连的某邻域内具有二阶连续续导数导数, 且且 f(x*)=0和和 f(x*) 0, 则对充分靠近则对充分靠近点点x*的初值的初值x0, Newton迭代法迭代法至少平方至少平方收敛收敛。)()(1nnnnxfxfxx )()()(xfxfxx *2()()()/(0)1 xf xfxfx 收收敛敛所以所以Newton迭代法至少平方收敛。迭代法至少平方收敛。)()()(*xfxfx *11/25例例2.求求 x3 +10 x 20 =0 在在 x0=1.5

6、附近的根附近的根解解:取取2010)(3 xxxf3121020310nnnnnxxxxx 牛顿迭代格式牛顿迭代格式则有则有103)(2 xxfn xn | en | 0 1.51 1.59701492537 0.002452808741981 2 1.59456374876 1.632137654805e-063 1.59456211663 7.227551890309e-134 1.59456211663 2.220446049250e-16 表表2 2 牛顿迭代法实验牛顿迭代法实验*12/25注释注释1: 为了二次收敛有意义我们需要为了二次收敛有意义我们需要f(x)相除相除, 这这个假设

7、是关键的。个假设是关键的。 f(x)=x3 3x + 2 = 0在在x*=1附近附近0)( xf*1: ()/()nnnnxxf xf x 牛牛顿顿迭迭代代法法13/25x*x0 x0 x0Newton方法收敛性依赖于方法收敛性依赖于x0 的选取。存的选取。存在在 x0使使Newton迭代法陷入死循环。迭代法陷入死循环。注释注释2:*14/25Newton迭代法的变型弦截法迭代法的变型弦截法)()()()(111 nnnnnnnxxxfxfxfxx)()(1nnnnxfxfxx 1-1()()()nnnnnf xf xfxxx 由于由于代入牛顿迭代格式代入牛顿迭代格式x0 x1*15/25n

8、xn | en | | en+1 |/| en |1.6181 -1.5 5.00e-0012 -2.5 5.00e-001 1.53473 -1.83783783783 1.62e-001 0.49784 -1.95420890762 4.57e-002 0.86915 -2.00552244119 5.52e-003 0.81096 -1.99982796307 1.72e-004 0.77427 -1.99999936831 6.31e-007 0.77858 -2.00000000007 7.24e-011 0.7778表表3 弦截法收敛速度实验弦截法收敛速度实验例例3 3. .已知方

9、程已知方程有两根有两根: :取根附近值做初值取根附近值做初值, ,分析牛顿迭代法实验的数据。分析牛顿迭代法实验的数据。 0233 xx2*1 x1*2 x参考参考: : 数值分析基础数值分析基础, , 关冶关冶 陆金甫陆金甫16/25表表4 初值取初值取 1.5 时牛顿迭代法速度时牛顿迭代法速度n xn | en | | en+1 |/| en |20-1.5 5.00e-0011-2.333333333333.33e-0011.33332-2.055555555555.55e-0020.50003-2.001949317731.94e-0030.63164-2.000002528292.52

10、e-0060.66545-2.000000000004.26e-0120.6667*17/25表表5 初值取初值取 1.5 时牛顿迭代法速度时牛顿迭代法速度n xn | en | | en+1 |/| en |01.5 5.00e-00111.2666666 2.66e-001 0.533321.1385620 1.38e-001 0.519631.0707773 7.07e-002 0.510841.0357918 3.57e-002 0.505751.0180008 1.80e-002 0.502961.0090271 9.02e-003 0.501571.0045203 4.52e-00

11、3 0.500781.0022618 2.26e-003 0.500491.0011313 1.13e-003 0.5002101.0005657 5.65e-004 0.5001111.0002829 2.82e-004 0.5000*18/25推论推论: 设设 x*是是 f(x)=0 的二重根的二重根, 则牛顿迭代法只具则牛顿迭代法只具有一阶收敛。有一阶收敛。证证: x*是二重根是二重根 f(x)=(x x*)2g(x)()()(2)()(*xgxxxgxxxf )()()(2)()()(*xgxxxgxgxxxx 211)(* x 牛顿迭代法只是一阶收敛牛顿迭代法只是一阶收敛。*1, (

12、)11mxn 重重根根*19/25nxn | en | | en+1 |/| en |201.5 5.00e-00111.033333333333.33e-002 0.133321.000182149361.85e-004 0.163931.000000005525.52e-009 0.1667 若若 x*是是 f(x)=0 的的 m 重根重根,修正的牛顿迭代法修正的牛顿迭代法)()(1nnnnxfxfmxx 为二阶收敛为二阶收敛 表表5 x*为二重根时修正的牛顿迭代实验为二重根时修正的牛顿迭代实验)()(21nnnnxfxfxx m = 2 f(x)1/m或或f(x)/f(x)单根单根*20

13、/25Examine the function graphically (to locate roughly where the roots are and how many there may be)l curve sketching is one way or.l best: use a Matlab plot to get the lay of the landset the interval or the starting point (find a range of x- values over which the function changes sign)iteratively

14、refine the initial guess with a root-finding algorithm (bisection is dependable but slow; Newton is fast if the initial value is good)一些建议一些建议21/25*迭代方法比较迭代方法比较二分法二分法 函数值的正负号函数值的正负号不动点家族不动点家族(牛顿法牛顿法)函数值函数值(函数的导数值函数的导数值) 收敛速度慢收敛速度慢 收敛速度快收敛速度快(特别快特别快) 总是收敛总是收敛 收敛是有条件的收敛是有条件的22/25非线性方程组非线性方程组: GaussNew

15、ton方法方法()()()( )()()()kkkF xF xFxxx ()()()()()()kkkFxxxF x 111122221212( )( )( )( )( )( )( )( )( )( )nnnnnnfxfxfxxxxfxfxfxxxxfxfxfxxxxFx (1)()()()1()()kkkkxxFxF x *1( )( )( )nfxF xfx 1nxxx ( )0F x 23/25例例3. 用牛顿迭代法求解非线性方程组用牛顿迭代法求解非线性方程组 01)5 . 0()2(01222yxyx211212(,)1fx xxx2221212(,)(2)(0.5)1fxxxx 11

16、121122212212421ffxxxFxxffxx 24/25()()12()()12(1)( )1111(,)(1)( )222(,)kkkkkkxxkkxxxxfFfxx 分别取初值分别取初值(1,0)和和(2,2),牛顿迭代法计算数据如下牛顿迭代法计算数据如下 nx1 x2 x1 x201 0 2 211.06250.12501.64581.583321.06730.13911.55701.416331.06730.13921.54651.391741.06730.13921.54631.391225/25*lim()nnxx 0101()()nnxxxxx 不动点框架不动点框架:收敛性收敛性 收敛速度收敛速度|( )| 1x (1)( )( *)( *)( *)0 ( *)0rrxxxx 26/25* Iteration in mathematics may refer to the process of iterating a function i.e. applying a function repeatedly, using the output from one iteration as the input to the next. Iteration of ap