牛顿迭代法及其应用[摘要]本文研究应用泰勒展开式构造出牛顿迭代法，论证了它的局部收敛性和收敛阶。

分别讨论了单根情形和重根情形，给出了实例应用。

最后给出了离散牛顿法的具体做法。

[关键词] 关键词：泰勒展开式，牛顿迭代法及其收敛性，重根，离散牛顿法。

1.牛顿法及其收敛性求方程f（x）=0的根，如果已知它的一个近似,可利用Taylor展开式求出f(x)在附近的线性近似，即，ξ在x与之间忽略余项，则得方程的近似右端为x的线性方程，若，则解,记作,它可作为的解的新近似，即(2.4.1)称为解方程的牛顿法.在几何上求方程的解，即求曲线y=f(x)与x轴交点.若已知的一个近似,通过点(，f())作曲线y=f(x)的切线，它与x轴交点为,作为的新近似，如图1所示图1关于牛顿法收敛性有以下的局部收敛定理.定理1设是f(x)=0的一个根，f(x)在附近二阶导数连续，且，则牛顿法(2.4.1)具有二阶收敛，且(2.4.2)证明由式(2.4.1)知迭代函数,，,而，由定理可知，牛顿迭代(2.4.1)具有二阶收敛，由式可得到式(2.4.2).证毕.定理表明牛顿法收敛很快，但在附近时才能保证迭代序列收敛.有关牛顿法半局部收敛性与全局收敛定理.此处不再讨论.例1用牛顿法求方程的根.,牛顿迭代为取即为根的近似，它表明牛顿法收敛很快.例2设＞0，求平方根的过程可化为解方程.若用牛顿法求解，由式(2.4.1)得(2.4.3)这是在计算机上作开方运算的一个实际有效的方法，它每步迭代只做一次除法和一次加法再做一次移位即可，计算量少，又收敛很快，对牛顿法我们已证明了它的局部收敛性，对式(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)给出的牛顿迭代法，由图2-3看到牛顿法求根就是用切线近似曲线，切线与x轴交点xk+1作为方程f(x)=0根x*的新近似。

根据定理2.3可以证明牛顿法是二阶收敛的，这就是定理4.1给出的结果，牛顿法由于收敛快，它是方程求根最常用和最重要的方法，在计算机上用牛顿法解方程的计算步骤：算法如下：（牛顿法）步0：给初始近似,计算精度最大迭代步数N,0→k.步1：计算f(x)→f,若，转步4，否则做步2：计算，若y=0,转步4，否则步3：若，步4，否则，若，转步4，否则转步1步4：打印x,f,y,k计算停止。

此算法给出了4个停止准则，保证计算在有限步结束，其中y=0及均属非正常结束，，说明用牛顿法求根得不到结果，步2中y=0实际使用时可改为（可取）。

计算例子见例2.6及例2.7，例2.7得到的计算的牛顿法程序（2.4.3）是计算机中计算开方的最有效算法，它对任意初值都能使序列收敛于，且为平方收敛，一般只要迭代3－5次就可达到7－9位有效数字，因此计算量很省。

2.重根情形当,则为方程(2.1.1)的重根，此时,牛顿法的迭代函数,，故牛顿法仍收敛，但只是线性收敛.若迭代函数改为，则，故迭代法(2.4.5)具有二阶收敛.对重根还可构造另一种迭代法，令若是的m重根，则所以是的单根，对它用牛顿法，迭代函数为从而可构造迭代法(2.4.6)它也是二阶收敛的.例3方程的根是二重根，试用牛顿法及(2.4.5)、(2.4.6)三种迭代法各计算3步.解方法(1)：牛顿迭代，方法(2)：迭代法(2.4.5)，方法(3)：迭代法(2.4.6)，三种方法均取=1.5计算结果如下：方法（1）方法（2）方法（3）1.458 3333331.436 607 1431.425 497 619 1.416 666 6671.414 215 6861.414 213 5621.411 764 7061.414 211 4381.414 213 562方法(2)与方法(3)均达到精确度，而方法(1)只有线性收敛，要达到相同精度需迭代30次.当x*是f(x)=0的重根时，用牛顿法计算，只有线性收敛，如果已知x*是m 重根则使用迭代法（2.4.5），否则可使用（2.4.6），见例43.离散牛顿法求解方程的牛顿法(2.4.1)要计算,如果导数计算不方便，通常可用计算函数差商近似，即将它代入式(2.4.1)则得离散牛顿法：(2.4.7)这种迭代法与式(2.2.2)不同，它要给出两个初始近似，才能逐次计算出.因此称为多点(两点)迭代，迭代(2.4.7)称为割线法，其几何意义是，用曲线上两点的割线与x轴交点作为=0根的新近似，即的根x，记作，它就是方程(2.1.1)根的新近似，如图2所示.图2由于割线法与单点迭代法(2.2.2)不同，其收敛性要复杂一些.但可以证明割线法(2.4.7)是超线性收敛的，且收敛阶,故割线法收敛也是很快的.用牛顿法时，若f'(x)不好计算，可改用离散牛顿法（2.4.7），它也称为弦截法或割线法，它的几何意义是用两点与的连线近似曲线，以直线方程的根近似的根x*，得到的迭代公式（2.4.7）与前面讨论的迭代法不同，必须给出两个初始近似才能逐次计算出这种迭代法称为两点迭代，它具有超线性收敛，其收敛阶p=1.618例4割线法求方程的根，设取由（2.4.7）计算结果为与例2.6用牛顿法计算3步得到的结果相当，说明此方法收敛也是很快的。

小结：1．用迭代法求方程f(x)=0的根，首先要能正确使用二分法，不动点迭代法和牛顿法求出方程的根，并避免计算错误。

作为迭代法选取合适的初始近似或有根区间是很重要的。

二分法既是求方程实根x*的一种简单迭代法，又是求方程一个足够好近似根的有效算法。

当为有限区间，每次二分迭代可使有根区间缩减一半且n次迭代Xn的误差因收敛较慢，故它常作为提供迭代法初值的算法。

2.重点是构造收敛的迭代法及牛顿法，首先必须掌握判断不动点迭代法收敛性的条件，只有收敛的迭代法才能用于球方程的根。

判断收敛性要分清是在区间，上整体收敛还是已知方程的根x，只证明它的局部收敛性。

对于前者主要根据收敛定理，证明，且在上，则｛x k｝收敛于根x*。

对于局部收敛性只需用定理证明即可。

3.对收敛的迭代序列｛x k｝，还要知道收敛快慢，首先要掌握收敛的定义，并能熟练应用定理，确定或证明迭代序列｛x k｝的收敛阶p，其中计算往往要用洛必达法则求极限。

P越大则｛x k｝收敛越快，在p=1则由判断收敛快慢，a越小则序列收敛越快。

4．对收敛慢或不收敛的迭代序列要通过加速迭代法，加速其收敛。

5．牛顿迭代法是求方程f(x)=0最重要的迭代法。

（1）用牛顿法求根公式求方程的根，要了解用此方法必须，且方法是局部收敛，一般要求初始近似x0与跟x*靠近，如x0选择不合适，可用牛顿下山法求根。

（2）牛顿迭代法是2阶收敛的，当x0选择合适时计算几步即可达到精度要求，对牛顿迭代由可以证明具体迭代序列的收敛性。

（3）重根情形下，f´（x*）=0，但f ´（x k）≠0仍然可用牛顿法求根，但它只是线性收敛，为提高收敛速度应使用具有2阶收敛的迭代法（2.4.5）及（2.4.6）求重根。

例如：设a>0，x>0，证明迭代公式x k+1=x k(x2k+3a)/(3x2k+a)是计算的3阶方法，并求这题目主要用到收敛阶的概念，它可以直接利用定义，也可以利用定理的结论证明。

下面先证明迭代序列的收敛性。

证明：显然，当a>0，x>0时，x>0(k=1，2。

)令则｝的极限是a，则有a=a(a+3a)/(3a+a),对，即迭代收敛，设｛xk解得a=0,a=± a ,取，下面只要求故迭代序列是3阶收敛的上面是由定义直接得到的结果，如用定理由于由定理可知迭代序列是3阶收敛的。

且这与前面直接用定义证明是一致的。

又如证明求 a 的牛顿迭代法对且｛xk｝是单调递减序列证明：因，故xk>0(k=1,2…)对即对一切k≥1，xk≥ a ，从而故xk+1≤xk即｛x｝是单调递减序列，它是整体收敛的参考文献：[1]陈纪修,於崇华,金路.数学分析(上册)[M].北京:高等教育出版社,2004:193-194.[2]施吉林,刘淑珍,陈桂芝.计算机数值方法[M].北京:高等教育出版社,2003:237-242,245-246.[3]李红,徐长发.数值分析学习辅导习题解析[M].武汉:华中科技大学出版社,2005:234-235,253-254,257-258,268270.[4]杨泮池,乔学军,林芳,等.计算方法要点与解题[M].西安:西安交通大学出版社,2006:23,34.[5]何旭初,苏煜城,包雪松.计算数学简明教程[M].北京:高等教育出版社,1986:203-205.。