数值分析论文(14).doc

Newton迭代法及其应用摘要：本文研究应用泰勒展开式构造出Newton迭代法，论证了它的局部收敛性和收敛阶。分别讨论了单根情形和重根情形，给出了实例应用。最后给出了离散Newton法(割线法) 的具体做法。关键词：泰勒展开式，Newton迭代法及其收敛性，重根，离散Newton法(割线法)。Newton迭代法 1.Newton法及其收敛性求方程f（x）=0的根，如果已知它的一个近似,可利用Taylor展开式求出f(x)在附近的线性近似，即，在x与之间忽略余项，则得方程的近似右端为x的线性方程，若，则解,记作,它可作为的解的新近似，即(2.4.1)称为解方程的Newton法.在几何上求方程的解，即求曲线y=f(x)与x轴交点.若已知的一个近似,通过点(，f()作曲线y=f(x)的切线，它与x轴交点为,作为的新近似，如图1所示关于Newton法收敛性有以下的局部收敛定理.定理1 设是f(x)=0的一个根，f(x)在附近二阶导数连续，且，则Newton法(2.4.1)具有二阶收敛，且 (2.4.2) 证明 由式(2.4.1)知迭代函数,，,而，由定理可知，Newton迭代(2.4.1)具有二阶收敛，由式可得到式(2.4.2).证毕.定理表明Newton法收敛很快，但在附近时才能保证迭代序列收敛.有关Newton法半局部收敛性与全局收敛定理.此处不再讨论.例1用Newton法求方程的根.解,Newton迭代为 取即为根的近似，它表明Newton法收敛很快.例2设0，求平方根的过程可化为解方程.若用Newton法求解，由式(2.4.1)得(2.4.3)这是在计算机上作开方运算的一个实际有效的方法，它每步迭代只做一次除法和一次加法再做一次移位即可，计算量少，又收敛很快，对Newton法我们已证明了它的局部收敛性，对式(2.4.3)可证明对任何迭代法都是收敛的，因为当时有即,而对任意，也可验证,即从k=1开始，且 所以从k=1起是一个单调递减有下界的序列，有极限.在式(2.4.3)中令k可得，这就说明了只要，迭代(2.4.3)总收敛到,且是二阶收敛.在例2.4的迭代法(3)中，用式(2.4.3)求只迭代3次就得到=1.732 051,具有7位有效数字. 求非线性方程f(x)=0的根x*,几何上就是求曲线y=f(x)与x轴交点x*，若已知曲线上一点过此点作它的切线。方程为此切线与x轴交点记作，它就是(2,4,1)给出的Newtor迭代法，由图2-3看到Newton法求根就是用切线近似曲线，切线与x轴交点xk+1作为方程f(x)=0根x*的新近似。根据定理2.3可以证明Newton法是二阶收敛的，这就是定理4.1给出的结果，Newton法由于收敛快，它是方程求根最常用和最重要的方法，在计算机上用Newton法解方程的计算步骤：算法如下：（Newton法）步0：给初始近似,计算精度 最大迭代步数N,0k.步1：计算f(x)f,若 ，转步4，否则做步2：计算 ，若y=0,转步4，否则步3：若，步4，否则，若，转步4，否则转步1步4：打印x,f,y,k计算停止。此算法给出了4个停止准则，保证计算在有限步结束，其中y=0及均属非正常结束，说明用Newton法求根得不到结果，步2中y=0实际使用时可改为（可取）。计算例子见例2.6及例2.7，例2.7得到的计算的Newton法程序（2.4.3）是计算机中计算开方的最有效算法，它对任意初值都能使序列收敛于，且为平方收敛，一般只要迭代35次就可达到79位有效数字，因此计算量很省。2.重根情形当,则为方程(2.1.1)的重根，此时,Newton法的迭代函数,，故Newton法仍收敛，但只是线性收敛.若迭代函数改为，则，故迭代法(2.4.5)具有二阶收敛.对重根还可构造另一种迭代法，令若是的m重根，则所以是的单根，对它用Newton法，迭代函数为 从而可构造迭代法(2.4.6) 它也是二阶收敛的.例3方程的根是二重根，试用Newton法及(2.4.5)、(2.4.6)三种迭代法各计算3步.解 方法(1)：Newton迭代，方法(2)：迭代法(2.4.5)，方法(3)：迭代法(2.4.6)，三种方法均取=1.5计算结果如下： 方法（1）方法（2）方法（3）1.458 333 3331.436 607 1431.425 497 619 1.416 666 6671.414 215 686 1.414 213 562 1.411 764 7061.414 211 4381.414 213 562 方法(2)与方法(3)均达到精确度，而方法(1)只有线性收敛，要达到相同精度需迭代30次。当x*是f(x)=0的重根时，用Newton法计算，只有线性收敛，如果已知x*是m重根则使用迭代法（2.4.5），否则可使用（2.4.6），见例43.离散Newton法(割线法)求解方程的Newton法(2.4.1)要计算,如果导数计算不方便，通常可用计算函数差商近似，即 将它代入式(2.4.1)则得离散Newton法：(2.4.7)这种迭代法与式(2.2.2)不同，它要给出两个初始近似，才能逐次计算出.因此称为多点(两点)迭代，迭代(2.4.7)称为割线法，其几何意义是，用曲线上两点的割线与x轴交点作为=0根的新近似，即的根x，记作，它就是方程(2.1.1)根的新近似，如图2所示.图2由于割线法与单点迭代法(2.2.2)不同，其收敛性要复杂一些.但可以证明割线法(2.4.7)是超线性收敛的，且收敛阶,故割线法收敛也是很快的.用Newton法时，若f(x)不好计算，可改用离散Newton法（2.4.7），它也称为弦截法或割线法，它的几何意义是用两点与的连线近似曲线，以直线方程的根近似的根x*，得到的迭代公式（2.4.7）与前面讨论的迭代法不同，必须给出两个初始近似才能逐次计算出这种迭代法称为两点迭代，它具有超线性收敛，其收敛阶p=1.618例4割线法求方程的根，设取由（2.4.7）计算结果为与例2.6用Newton法计算3步得到的结果相当，说明此方法收敛也是很快的小结1用迭代法求方程f(x)=0的根，首先要能正确使用二分法，不动点迭代法和Newton法求出方程的根，并避免计算错误。作为迭代法选取合适的初始近似或有根区间是很重要的。二分法既是求方程实根x*的一种简单迭代法，又是求方程一个足够好近似根的有效算法。当为有限区间，每次二分迭代可使有根区间缩减一半且n次迭代Xn的误差因收敛较慢，故它常作为提供迭代法初值的算法。2.重点是构造收敛的迭代法及牛顿法，首先必须掌握判断不动点迭代法收敛性的条件，只有收敛的迭代法才能用于球方程的根。判断收敛性要分清是在区间，上整体收敛还是已知方程的根x，只证明它的局部收敛性。对于前者主要根据收敛定理，证明，且在上 ，则xk收敛于根x*。对于局部收敛性只需用定理证明 即可。3.对收敛的迭代序列xk，还要知道收敛快慢，首先要掌握收敛的定义，并能熟练应用定理，确定或证明迭代序列xk的收敛阶p，其中计算 往往要用Hopital 法则求极限。P越大则xk收敛越快，在p=1则由判断收敛快慢，a越小则序列收敛越快。4对收敛慢或不收敛的迭代序列要通过Steffensen迭代法，加速其收敛。5Newton迭代法是求方程f(x)=0最重要的迭代法。（1）用牛顿法求根公式求方程的根，要了解用此方法必须，且方法是局部收敛，一般要求初始近似x0与跟x*靠近，如x0选择不合适，可用Newton下山法求根。（2）Newton迭代法是2阶收敛的，当x0选择合适时计算几步即可达到精度要求，对Newton迭代由可以证明具体迭代序列的收敛性。（3）重根情形下，f（x*）=0，但f （xk） 0仍然可用Newton法求根，但它只是线性收敛，为提高收敛速度应使用具有2阶收敛的迭代法（2.4.5）及（2.4.6）求重根。例如：设a0，x0，证明迭代公式xk+1=xk(x2k+3a)/(3x2k+a)是计算 的3阶方法，并求这题目主要用到收敛阶的概念，它可以直接利用定义，也可以利用定理的结论证明。下面先证明迭代序列的收敛性。证明：显然，当a0，x0时，x0(k=1，2。)令则对，即迭代收敛，设xk的极限是a，则有a=a(a+3a)/(3a+a),解得a=0,a=,取，下面只要求故迭代序列是3阶收敛的上面是由定义直接得到的结果，如用定理由于1用迭代法求方程f(x)=0的根，首先要能正确使用二分法，不动点迭代法和Newton法求出方程的根，并避免计算错误。作为迭代法选取合适的初始近似或有根区间是很重要的。二分法既是求方程实根x*的一种简单迭代法，又是求方程一个足够好近似根的有效算法。当为有限区间，每次二分迭代可使有根区间缩减一半且n次迭代Xn的误差因收敛较慢，故它常作为提供迭代法初值的算法。2.重点是构造收敛的迭代法及牛顿法，首先必须掌握判断不动点迭代法收敛性的条件，只有收敛的迭代法才能用于球方程的根。判断收敛性要分清是在区间，上整体收敛还是已知方程的根x，只证明它的局部收敛性。对于前者主要根据收敛定理，证明，且在上 ，则xk收敛于根x*。对于局部收敛性只需用定理证明 即可。3.对收敛的迭代序列xk，还要知道收敛快慢，首先要掌握收敛的定义，并能熟练应用定理，确定或证明迭代序列xk的收敛阶p，其中计算 往往要用Hopital 法则求极限。P越大则xk收敛越快，在p=1则由判断收敛快慢，a越小则序列收敛越快。4对收敛慢或不收敛的迭代序列要通过Steffensen迭代法，加速其收敛。5Newton迭代法是求方程f(x)=0最重要的迭代法。（1）用牛顿法求根公式求方程的根，要了解用此方法必须，且方法是局部收敛，一般要求初始近似x0与跟x*靠近，如x0选择不合适，可用Newton下山法求根。（2）Newton迭代法是2阶收敛的，当x0选择合适时计算几步即可达到精度要求，对Newton迭代由可以证明具体迭代序列的收敛性。（3）重根情形下，f（x*）=0，但f （xk） 0仍然可用Newton法求根，但它只是线性收敛，为提高收敛速度应使用具有2阶收敛的迭代法（2.4.5）及（2.4.6）求重根。例如：设a0，x0，证明迭代公式xk+1=xk(x2k+3a)/(3x2k+a)是计算 的3阶方法，并求这题目主要用到收敛阶的概念，它可以直接利用定义，也可以利用定理的结论证明。下面先证明迭代序列的收敛性。证明：显然，当a0，x0时，x0(k=1，2。)令则对，即迭代收敛，设xk的极限是a，则有a=a(a+3a)/(3a+a),解得a=0,a=,取，下面只要求故迭代序列是3阶收敛的上面是由定义直接得到的结果，如用定理由于由定理可知迭代序列是3阶收敛的。且这与前面直接用定义证明是一致的。又如证明求的Newton迭代法对且xk是单调递减序列证明： 因，故xk 0(k=1,2)对即对一切k1，xk，从而故xk+1xk 即x是单调递减序列，它是整体收敛的。参考文献： 1陈纪修 ,於崇华 ,金路 .数学分析 (上册 )M.北京 :高等教育出版社 ,2004:193-194. 2施吉林 ,刘淑珍 ,陈桂芝