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

数值分析牛顿迭代法第1页，此课件共24页哦数值分析4Newton迭代格式迭代格式Newton迭代法的收敛性迭代法的收敛性Newton迭代法收敛速度迭代法收敛速度弦截法迭代格式弦截法迭代格式2022/10/14第2页，此课件共24页哦Nature and Nature law lay hid in night.God said,Let Newton be,and all was light.Alexander Pope2022/10/14第3页，此课件共24页哦给定初值给定初值 x0,迭代产生数列迭代产生数列x0,x1,x2,xn,2022/10/14第4页，此课件共24页哦设设 x*是方程是方程 f(x)=0 的根的根,x0是是x*的近似值。在的近似值。在 x0 附近对函数做附近对函数做局部线性化局部线性化x1比比x0更接近于更接近于x*x0 x1x*f(x)=0 化难为易化繁为简2022/10/14第5页，此课件共24页哦应用应用求正数平方根算法求正数平方根算法设设C 0,x2 C=0令令 f(x)=x2 C,则则2022/10/14第6页，此课件共24页哦初值初值:x0=1.5迭代格式迭代格式:xn+1=0.5(xn+2/xn)(n=0,1,2,)例例1.平方根算法求平方根算法求 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 平方根算法实验平方根算法实验2022/10/14第7页，此课件共24页哦收敛性收敛性:(1)符合不动点框架符合不动点框架(2)从序列收敛的角度从序列收敛的角度(单调有界序列单调有界序列)2022/10/14第8页，此课件共24页哦由此可知由此可知平方根算法具有平方根算法具有 2 阶收敛速度。阶收敛速度。思考思考:如何求倒数、平方根和立方根？如何求倒数、平方根和立方根？第9页，此课件共24页哦Newton迭代法的局部收敛性迭代法的局部收敛性定理定理2.7 设设 f(x)在点在点x*的某邻域内具有二阶连续的某邻域内具有二阶连续导导数数,且且 f(x*)=0和和 f(x*)0,则对充分靠近点则对充分靠近点x*的的初值初值x0,Newton迭代法迭代法至少平方至少平方收敛收敛。所以所以Newton迭代法至少平方收敛。迭代法至少平方收敛。2022/10/14第10页，此课件共24页哦例例2.求求 x3+10 x 20=0 在在 x0=1.5 附近的根附近的根解解:取取牛顿迭代格式牛顿迭代格式则有则有n 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 牛顿迭代法实验牛顿迭代法实验2022/10/14第11页，此课件共24页哦注释注释1:为了二次收敛有意义我们需要为了二次收敛有意义我们需要f(x)相除相除,这个假这个假设是关键的。设是关键的。f(x)=x3 3x+2=0在在x*=1附近附近2022/10/14第12页，此课件共24页哦x*x0 x0 x0Newton方法收敛性依赖于方法收敛性依赖于x0 的选取。存在的选取。存在 x0使使Newton迭代法陷入死循环。迭代法陷入死循环。注释注释2:2022/10/14第13页，此课件共24页哦Newton迭代法的变型迭代法的变型弦截法弦截法由于由于代入牛顿迭代格式代入牛顿迭代格式x0 x12022/10/14第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.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.已知方程已知方程有两根有两根:取根附近值做初值取根附近值做初值,分析牛顿迭代法实验的数据。分析牛顿迭代法实验的数据。参考参考:数值分析基础数值分析基础,关冶关冶 陆金甫陆金甫第15页，此课件共24页哦表表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.66672022/10/14第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.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/14第17页，此课件共24页哦推论推论:设设 x*是是 f(x)=0 的二重根的二重根,则牛顿迭代法只具有一则牛顿迭代法只具有一阶收敛。阶收敛。证证:x*是二重根是二重根 f(x)=(x x*)2g(x)牛顿迭代法只是一阶收敛牛顿迭代法只是一阶收敛。2022/10/14第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*为二重根时修正的牛顿迭代实验为二重根时修正的牛顿迭代实验 m=2 f(x)1/m或或f(x)/f(x)单单根根2022/10/14第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 which 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页哦迭代方法比较迭代方法比较二分法二分法 函数值的正负号函数值的正负号不动点家族不动点家族(牛顿法牛顿法)函数值函数值(函数的导数值函数的导数值)收敛速度慢收敛速度慢 收敛速度快收敛速度快(特别快特别快)总是收敛总是收敛 收敛是有条件的收敛是有条件的2022/10/14第21页，此课件共24页哦非线性方程组非线性方程组:GaussNewton方法方法2022/10/14第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页哦