牛顿迭代法李保洋数学科学学院信息与计算科学学号：060424067指导老师：苏孟龙摘要：牛顿在17世纪提出的一种在实数域和复数域上近似求解方程的方法，即牛顿迭代法.迭代法是一种不断用变量的旧值递推新值的过程•跟迭代法相对应的是直接法或者称为一次解法，即一次性解决问题•迭代法又分为精确迭代和近似迭代“牛顿迭代法”属于近似迭代法，本文主要讨论的是牛顿迭代法，方法本身的发现和演变和修正过程，避免二阶导数计算的Newton迭代法的一个改进，并与中国古代的算法，即盈不足术，与牛顿迭代算法的比较•关键词：Newton迭代算法；近似求解；收敛阶；数值试验；中国古代数学;九章算术；Duffing方程；非线性方程；收敛速度；渐进性0引言：迭代法也称辗转法，是一种不断用变量的旧值递推新值的过程，跟迭代法相对应的是直接法或者称为一次解法，即一次性解决问题•迭代法又分为精确迭代和近似迭代•“二分法”和“牛顿迭代法”属于近似迭代法•迭代算法是用计算机解决问题的一种基本方法•它利用计算机运算速度快、适合做重复性操作的特点，让计算机对一组指令（或一定步骤）进行重复执行，在每次执行这组指令（或这些步骤）时，都从变量的原值推出它的一个新值•具体使用迭代法求根时应注意以下两种可能发生的情况：（1）如果方程无解，算法求出的近似根序列就不会收敛，迭代过程会变成死循环，因此在使用迭代算法前应先考察方程是否有解，并在程序中对迭代的次数给予限制•（2）方程虽然有解，但迭代公式选择不当，或迭代的初始近似根选择不合理，也会导致迭代失败•所以利用迭代算法解决问题，需要做好以下三个方面的工作：1、确定迭代变量•在可以用迭代算法解决的问题中，至少存在一个直接或间接地不断由旧值递推出新值的变量，这个变量就是迭代变量2、建立迭代关系式.所谓迭代关系式，指如何从变量的前一个值推出其下一个值的公式（或关系）.迭代关系式的建立是解决迭代问题的关键，通常可以使用递推或倒推的方法来完成.3、对迭代过程进行控制，在什么时候结束迭代过程？这是编写迭代程序必须考虑的问题.不能让迭代过程无休止地重复执行下去.迭代过程的控制通常可分为两种情况：一种是所需的迭代次数是个确定的值，可以计算出来；另一种是所需的迭代次数无法确定.对于前一种情况，可以构建一个固定次数的循环来实现对迭代过程的控制；对于后一种情况，需要进一步分析出用来结束迭代过程的条件.1牛顿迭代法：洛阳师范学院本科毕业论文X 0 牛顿迭代有十分明显的几何意义，如图所示:牛顿 迭代法(Newton method)又称为牛顿-拉夫逊方法(Newto n-Rapfsonmethod)，它是牛顿在17世纪提出的一种在实数域和复数域上近似求解方程的方 法.多数方程不存在求根公式，因此求精确根非常困难甚至不可能，从而寻找方程的近似根就显得特别重要•方法使用函数f x 的泰勒级数的前面几项来寻找方程f x =0的根•牛顿迭代法是求方程根的重要方法之一，其最大优点是在方程f x =0的单根附近具有平方收敛性，而且该法还可以用来求方程的重根、复根. 另外该方法广泛用于计算机编程中：解非线性方程f x ]=0的牛顿(Newton)法是把非线性的方程线性化的一种近似方法•把f x 的x 点附近展开泰勒(Taylor )级' 2 f x = f x 0 f X - X 0 f x 0 ］亠 ix - X 0取其线性部分作为非线性方程f x =0的近似方程，则有:f X 。
f ' X 。
X - x 0 =0 ；设f ' x 。
=0,则其解为：再把f x 在％附近展开泰勒(Taylor)级数，也取其现行部分作为f x i ； = 0的近似方 程.若f % = 0，则得:这样，得到牛顿(Newton)法的一个迭代序列:当选取初值X o以后，过X o,f X o「|做f X的切线，其切线方程为:y - f X。
= f' & x - X。
；求此切线方程和X轴的交点，即得：x— X。
一f X ' f X牛顿法正因为有这一明显的几何意义，所以也叫切线法例：用牛顿法求下面方程的根f X = X3 2x2 10x - 20 = 0 ；解：因f x]=3x2・4x *10，所以迭代公式为:x n勺.二焉一X32x210x -20 3x24x 10 ；选取X（）=1计算结果列表:从结果可以看出，牛顿法的收敛是很快的，X5误差10」较大，因每次计算迭代除了计算函数值外还要计算微商值•为此我们提出了简化牛顿法：其公式为X n1=X n-f X n「f' X ；用上面的公式计算，不再需要每步重新计算微商值，所以计算量小一些，但收敛也要慢一些•为了避免计算导数还可以采用差商代导数的方案：-5 "X n —f X n -f X n^关于牛顿迭代的收敛有下面结果：如果f X在零点附近存在连续的二阶微商,•是f X的一重零点，且初始X0充分接近于，那么牛顿迭代是收敛的，且有&十仝|十"卩）/0'（匕）卜焉仝2这表明牛顿法是二阶收敛的（平方收敛的）最后考虑f x是多项式的特殊情况，此时f X , f x在某个x值，比如x = c 时的计算可用综合除法•设 f (x )=ax n+ax n半+川a n」x + a n，除以x —c，得商q(x)，余r:f x 二q x x c ; r(1)其中:q x i=b o x n‘ bx n，川b n/ ;r = 0 = f c；比较(1)式两边x k的系数便知这些b k可以按下表进行：这一过程其实就是秦九韶算法，计算多项式值的嵌套算法：f c 二丨|| a o a i c ■ a?c c 川a.」c a n ；每个括号的值就是这里的bollllllbn.至于导数的计算，注意到(1)式可得：f'x=qx q'x x-c ；于是：fc =q c；'因此再对b0||||||bn进行上述过程，或者再用一次秦九韶算法即可•2一种修正的牛顿迭代法：给出了牛顿迭代法的一种修正形式，并证明了当r=1/2时修正的牛顿迭代法是二阶收敛的，当参数r =1/2时是三阶收敛的，数值实验表明，与经典牛顿迭代法相比，该修正牛顿迭代法具有一定的优势•众所周知，数值求解非线性方程f x =0的根的方法很多.经典的牛顿迭代法是非线性方程组求根的一个基本方法，它二次收敛到单根，线性收敛到重根•牛顿法因收敛速度快而得到广泛应用，也倍受学者的重视，近年来很多文献中提出各种改进的牛顿方法•文献［8］中利用Newton迭代法和微分中值定理“中值点”的渐进性，提出了一种多点迭代法.设f （x ）满足下述条件:f x 卢 c 2 l.a,b ］, f a f b ：： 0 ；因此，当b 与a 的距离无限接近时有:1:a - b-a .也就是说，在区间（a,b ）不甚大时，中值点 一定在其渐近位置2:a 2 ^a 附近，并随区间变小而趋于其渐近位置.图所示迭代法构造图本方 案基于上述考虑，给出一种通过迭代点选取另一个点，利用两个点进行迭代求近 似根的新方法•这种方法虽然在迭代中又只利用了一个其它点，但其计算精度却相 当高，它的某一种特殊情形恰是通常的 Newt on 迭代法.为了更加直观起见，我们 通过几何直观图来构造这种迭代法•设f x 满足条件（A ），当选定初值x o （仅要求f x o f " x 0），如图所示，作交点的切线交x 轴于B x o -丄旦,0I f （ X 。
）AQ 线段的斜率为:f ' x - 0， f" x 在［a,b ］上保号. 根据微分中值定理，存在• （a,b ），使得:f (沧)一 f x o - (A)=f ，而 12 图1 迭代法构适图f (Xo )f '(x o )」使得:由微分中值定理知，存在f x oX 。
/ ;:应丫。
f r 。
“ "仏）丿重复上述过程，得到多点迭代公式f （X k ） X k 1 =Xk -f （ X k f Xk-Crf^H、、、 f （兀）丿其中 X k [a,b]，k =1,2,3,111.下面我们对上述事实，从理论上加以严格证明.定理 设f X 满足条件（A ），则由多点迭代公式（1）产生的序列｛X n ｝必收敛于 ［a, b ］上的唯一 a ，这里 x n ：= a,b 丨，f a ］=0 .证明函数f X 在上连续，由连续函数根的存在定理，从 f a f b ：：：0知道 f X 在〔a,b 上根存在，又由条件f x =0及f X 保号知道，f X 在〔a,b 1上不 变号，故f x 在l.a,b 1上是单调函数，因此f x 在l.a,b ］上根a 存在且唯一.由定理条件曲线y 二f x 可有如下四种不同情况：（1）f a ：： 0, f b 0, f " x 0，则 f ' x 单调上升，f ' a f ' b0 ； （2） f a <0, f b 0,f " x0，则 f ' x而.：、x 0 - P X 。
- 1 -rf （X 。
），因此，我们取数「V ,在点X 0「1「r b 作切线PC ，图中 AD 平行于PC .即用 点P 的导数门X 。
- 1 - r0）丿代替点A 的导数，而仍用点 A 的迭代格式得到点 D 的坐标x 0 一 Xo -（X 。
） （X 。
单调下降，f' a f' b 0 ；H I I I⑶ fa 0, f b <0, f x 0,则 f x 单调上升，f a f b ：： 0 ；⑷ fa 0, f b ::: 0, f " x ：0,则 f ' x 单调下降，f ' a f ' b ：： 0.通过对自变量的变号或对函数的变号可将四种情况归结为一种情况，所以我 们只需对情况(一)证明迭代过程(1)收敛就可以了 •若初值人：=[a,b],x 0 . a,所以f x o • 0，故有般地，若X n = a ，同样可以证明由式(2)得到的x n *满足ax n 十：：：焉.所以由 式⑴产生的迭代序列｛x n ｝单调下降且有下界.依极限理论必有极限.对式(2)两边取 极限，由极限理论可以求得 f a i=0.再由f ' x =0，x^ ■ l-a,b 1，可知函数方程 f x =0在〔a,b 】上的根是唯一的，因此有a 二a .当r =1时，式⑵即为Newton 迭代公式.f （a ）+f （f x 。
一a ） xf (加-a ) - 、T"鳥f x d J%）丿 一方面, 匚三［a.x ° ，且 f x 0 二 f x°-a .下证 f x < f&_（1_「）吕* . I f （x 。