数值分析牛顿迭代法.ppt

《数值分析牛顿迭代法.ppt》由会员分享，可在线阅读，更多相关《数值分析牛顿迭代法.ppt（24页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数值分析牛顿迭代法现在学习的是第1页，共24页数值分析4Newton迭代格式迭代格式Newton迭代法的收敛性迭代法的收敛性Newton迭代法收敛速度迭代法收敛速度弦截法迭代格式弦截法迭代格式2022/10/3现在学习的是第2页，共24页Nature and Nature law lay hid in night.God said,Let Newton be,and all was light.Alexander Pope2022/10/3现在学习的是第3页，共24页给定初值给定初值 x0,迭代产生数列迭代产生数列x0,x1,x2,xn,2022/10/3现在学习的是第4页，共24页设设 x*

2、是方程是方程 f(x)=0 的根的根,x0是是x*的近似值。在的近似值。在 x0 附近对函数做附近对函数做局部线性化局部线性化x1比比x0更接近于更接近于x*x0 x1x*f(x)=0 化难为易化繁为简2022/10/3现在学习的是第5页，共24页应用应用求正数平方根算法求正数平方根算法设设C 0,x2 C=0令令 f(x)=x2 C,则则2022/10/3现在学习的是第6页，共24页初值初值:x0=1.5迭代格式迭代格式:xn+1=0.5(xn+2/xn)(n=0,1,2,)例例1.平方根算法求平方根算法求 xn|en|1.416666666666667 2.45e-0031.4142156

3、86274510 2.12e-0061.414213562374690 1.59e-0121.414213562373095 2.22e-0161.414213562373095 2.22e-016表表1 1 平方根算法实验平方根算法实验2022/10/3现在学习的是第7页，共24页收敛性收敛性:(1)符合不动点框架符合不动点框架(2)从序列收敛的角度从序列收敛的角度(单调有界序列单调有界序列)2022/10/3现在学习的是第8页，共24页由此可知由此可知平方根算法具有平方根算法具有 2 阶收敛速度。阶收敛速度。思考思考:如何求倒数、平方根和立方根？如何求倒数、平方根和立方根？现在学习的是第9

4、页，共24页Newton迭代法的局部收敛性迭代法的局部收敛性定理定理2.7 设设 f(x)在点在点x*的某邻域内具有二阶连续的某邻域内具有二阶连续导导数数,且且 f(x*)=0和和 f(x*)0,则对充分靠近点则对充分靠近点x*的的初值初值x0,Newton迭代法迭代法至少平方至少平方收敛收敛。所以所以Newton迭代法至少平方收敛。迭代法至少平方收敛。2022/10/3现在学习的是第10页，共24页例例2.求求 x3+10 x 20=0 在在 x0=1.5 附近的根附近的根解解:取取牛顿迭代格式牛顿迭代格式则有则有n xn|en|0 1.51 1.59701492537 0.00245280

5、8741981 2 1.59456374876 1.632137654805e-063 1.59456211663 7.227551890309e-134 1.59456211663 2.220446049250e-16 表表2 2 牛顿迭代法实验牛顿迭代法实验2022/10/3现在学习的是第11页，共24页注释注释1:为了二次收敛有意义我们需要为了二次收敛有意义我们需要f(x)相除相除,这个这个假设是关键的。假设是关键的。f(x)=x3 3x+2=0在在x*=1附近附近2022/10/3现在学习的是第12页，共24页x*x0 x0 x0Newton方法收敛性依赖于方法收敛性依赖于x0 的选取

6、。存在的选取。存在 x0使使Newton迭代法陷入死循环。迭代法陷入死循环。注释注释2:2022/10/3现在学习的是第13页，共24页Newton迭代法的变型迭代法的变型弦截法弦截法由于由于代入牛顿迭代格式代入牛顿迭代格式x0 x12022/10/3现在学习的是第14页，共24页n 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.81

7、096 -1.99982796307 1.72e-004 0.77427 -1.99999936831 6.31e-007 0.77858 -2.00000000007 7.24e-011 0.7778表表3 弦截法收敛速度实验弦截法收敛速度实验例例3 3.已知方程已知方程有两根有两根:取根附近值做初值取根附近值做初值,分析牛顿迭代法实验的数据。分析牛顿迭代法实验的数据。参考参考:数值分析基础数值分析基础,关冶关冶 陆金甫陆金甫现在学习的是第15页，共24页表表4 初值取初值取 1.5 时牛顿迭代法速度时牛顿迭代法速度n xn|en|en+1|/|en|20-1.5 5.00e-0011-2.

8、333333333333.33e-0011.33332-2.055555555555.55e-0020.50003-2.001949317731.94e-0030.63164-2.000002528292.52e-0060.66545-2.000000000004.26e-0120.66672022/10/3现在学习的是第16页，共24页表表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.

9、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.0005657 5.65e-004 0.5001111.0002829 2.82e-004 0.50002022/10/3现在学习的是第17页，共24页推论推论:设设 x*是是 f(x)=0 的二重根的二重根,则牛顿迭代法只具有一阶则牛顿迭

10、代法只具有一阶收敛。收敛。证证:x*是二重根是二重根 f(x)=(x x*)2g(x)牛顿迭代法只是一阶收敛牛顿迭代法只是一阶收敛。2022/10/3现在学习的是第18页，共24页nxn|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 重根重根,修正的牛顿迭代法修正的牛顿迭代法为二阶收敛为二阶收敛 表表5 x*为二重根时修正的牛顿迭代实验为二重根时修正的牛顿迭代实验

11、m=2 f(x)1/m或或f(x)/f(x)单单根根2022/10/3现在学习的是第19页，共24页Examine the function graphically(to locate roughly where the roots are and how many there may be)lcurve sketching is one way or.lbest:use a Matlab plot to get the lay of the landset the interval or the starting point (find a range of x-values over wh

12、ich the function changes sign)iteratively refine the initial guess with a root-finding algorithm(bisection is dependable but slow;Newton is fast if the initial value is good)一些建议一些建议现在学习的是第20页，共24页迭代方法比较迭代方法比较二分法二分法 函数值的正负号函数值的正负号不动点家族不动点家族(牛顿法牛顿法)函数值函数值(函数的导数值函数的导数值)收敛速度慢收敛速度慢 收敛速度快收敛速度快(特别快特别快)总是收

13、敛总是收敛 收敛是有条件的收敛是有条件的2022/10/3现在学习的是第21页，共24页非线性方程组非线性方程组:GaussNewton方法方法2022/10/3现在学习的是第22页，共24页例例3.用牛顿迭代法求解非线性方程组用牛顿迭代法求解非线性方程组 现在学习的是第23页，共24页分别取初值分别取初值(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.3912现在学习的是第24页，共24页