数值分析4牛顿迭代法课件.ppt

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

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

3、 C=0令令 f(x)=x2 C,则则xxf2)(nnnnxCxxx221 211nnnxCxx 8:167/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 平方根算法实验平方根算法实验8:168/25收敛性收敛性:(1

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

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

6、1020310nnnnnxxxxx 牛顿迭代格式牛顿迭代格式则有则有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 牛顿迭代法实验牛顿迭代法实验8:1612/25注释注释1:为了二次收敛有意义我们需要为了二次收敛有意义我们需要f(x)相除相除,这这个假设是关键的。个假设是关键的。f(x)=x3 3x+2=0在在x*

7、=1附近附近0)(xf8:161:()/()nnnnxxf xf x 牛牛顿顿迭迭代代法法13/25x*x0 x0 x0Newton方法收敛性依赖于方法收敛性依赖于x0 的选取。存的选取。存在在 x0使使Newton迭代法陷入死循环。迭代法陷入死循环。注释注释2:8:1614/25Newton迭代法的变型弦截法迭代法的变型弦截法)()()()(111 nnnnnnnxxxfxfxfxx)()(1nnnnxfxfxx 1-1()()()nnnnnf xf xfxxx 由于由于代入牛顿迭代格式代入牛顿迭代格式x0 x18:1615/25n xn|en|en+1|/|en|1.6181 -1.5 5

8、.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.52e-0060.66545-2.000000000004.26e-0120.66678:1617/25表表5 初值取初值取

10、 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-003 0.500781.0022618 2.26e-003 0.500491.0011313 1.13e-003 0.5002101.

11、0005657 5.65e-004 0.5001111.0002829 2.82e-004 0.50008:1618/25推论推论:设设 x*是是 f(x)=0 的二重根的二重根,则牛顿迭代法只具则牛顿迭代法只具有一阶收敛。有一阶收敛。证证:x*是二重根是二重根 f(x)=(x x*)2g(x)()()(2)()(*xgxxxgxxxf )()()(2)()()(*xgxxxgxgxxxx 211)(*x 牛顿迭代法只是一阶收敛牛顿迭代法只是一阶收敛。*1,()11mxn 重重根根8:1619/25nxn|en|en+1|/|en|201.5 5.00e-00111.033333333333.

12、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)单根单根8:1620/25Examine the function graphically(to locate roughly where the roots are

13、 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 refine the initial guess with a root-finding algorithm(bisection is dependab

14、le but slow;Newton is fast if the initial value is good)一些建议一些建议21/258:16迭代方法比较迭代方法比较二分法二分法 函数值的正负号函数值的正负号不动点家族不动点家族(牛顿法牛顿法)函数值函数值(函数的导数值函数的导数值)收敛速度慢收敛速度慢 收敛速度快收敛速度快(特别快特别快)总是收敛总是收敛 收敛是有条件的收敛是有条件的22/25非线性方程组非线性方程组:GaussNewton方法方法()()()()()()()kkkF xF xFxxx ()()()()()()kkkFxxxF x 111122221212()()()()

15、()()()()()()nnnnnnfxfxfxxxxfxfxfxxxxfxfxfxxxxFx (1)()()()1()()kkkkxxFxF x 8:161()()()nfxF xfx 1nxxx ()0F x 23/25例例3.用牛顿迭代法求解非线性方程组用牛顿迭代法求解非线性方程组 01)5.0()2(01222yxyx211212(,)1fx xxx2221212(,)(2)(0.5)1fxxxx 11121122212212421ffxxxFxxffxx 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