第四章 一元方程求根/非线性方程组数值解法初步4．3 Newton 迭代法 1. Newton 迭代法解一元非线性方程组0)(=x f （4.3.1）的Newton 迭代法是不动点迭代法的一种特殊形式。
可从不同途径导出Newton 迭代公式，这里采用Taylor 展开。
设方程0)(=x f 的根*x 的一个近似值0x ,将)(x f 在0x 附近展开得20000)(!2)(''))((')()(0x x f x x x f x f x f -+-+==ξ 或表示为 200000)()('2)('')(')(x x x f f x f x f x x ---=ξ （4.3.2）其中设0)('0≠x f ，''f 存在、连续，而ξ在x 与0x 之间。
忽略上式最后一项*x 的一个新近似值)(')(0001x f x f x x -= 把1x 代替上式右端的0x ，并设0)('1≠x f ，于是又得新近似值)(')(1112x f x f x x -=如此继续，可知当),2,1,0(0)(' =≠k x f k 可得),2,1,0()(')(1 =-=+k x f x f x x k k k k （4.3.3）这就是著名的Newton （牛顿）迭代公式。
在迭代序列收敛的情况下，取一定精度的迭代值kx 作为方程0)(=x f 的根*x 的近似值，这就是解方程组0)(=x f 的Newton 迭代法。
显然，它以在*x 附近函数0)(=x f 线性化为基础，并以),2,1,0(0)(' =≠k x f k 为前提。
例 4.3.1 用Newton 迭代法求下列方程的近似根：1-x xe =0解 令 1)(-=x xe x f ,则x x xe e x f +=)(',于是迭代公式为),1,0(11 =+--=+k ex e e x x x kkkxk x x k k k 整理得),1,0(11 =+--=-+k x e x x x kxk k k k取5.00=x 请同学们自己动手完成2．Newton 迭代法的收敛性Newton 迭代公式作为不动点迭代，其迭代函数为 )(')()(x f x f x x -=ϕ 从而有222)]('[)('')()]('[)('')()]('[1)('x f x f x f x f x f x f x f x =--=ϕ 可见，如果在方程0)(=x f 的根*x 的某个邻域内0)('0≠x f (从而有0)('*≠x f ，即*x 是单根的情况)，''f 存在并连续（从而有界），则只要x 足够靠近*x ，(从而|)(|x f 足够靠近0)，就有1|)('|<≤L xϕ,于是根据定理4.2.1的推论，Newton 迭代公式收敛于*x ，并且0)(*=x f 导致 0)('*=x ϕ，于是又根据收敛阶的判定定理4.2.4 ，可知Newton 迭代公式在单根附近至少是2阶的。
下面陈述定理。
定理 4.3.1 设0)(*=x f , 0)('*≠x f , 且在*x 的邻域上''f 存在、连续，则可得(1) Newton 迭代公式在单根情况下至少2阶收敛；(2) )('2)('')()(lim **2**1x f x f x x x x k k k =--+∞→ （4.3.4） 证明： 只须证明结论(2). （4.3.2）式中的0x 和x 可分别换为k x 和*x ， 在k x 这一点用Taylor 展开得2**)()('2)('')(')(k k k k k x x x f f x f x f x x ---=ξ再与)(')(1k k k k x f x f x x -=+相减，则易得2**1)()('2)(''k k k x x x f f x x -=-+ξ注意到：当∞→k 时，*x →ξ， *x x k →，由上式取极限即可得结论(2)3．Newton 法的计算机算法 ① )(00x f F =； )(''00x f F =② 如果 0'0=F ，则输出“方法失败”并停机③ 对 ,,,2,1K k =做a. '/0001F F x x -=b. )(11x f F =; )(''11x f F =c. 如果101||ε<-x x 或 21||ε<F ，则输出近似解1x 和k 值并停机。
d. 如果 0'1=F ，则输出“方法失败”并停机e. '';;101010F F F F x x ===④ 输出“经K 次迭代仍无满足要求的近似解”并停机。
4．Newton 法对方程重根的处理 对于 *x 为0)(=x f 的m 重根(1>m )的情形，这时)()()(*x g x x x f m -=其中g2阶可导，0)(*≠x g ，于是由)(')()()()()()(')()(*1**x g x x x g x x m x g x x x x f x f x x mm m -+---=-=-ϕ=)(')()()()(**x g x x x mg x g x x x -+-- '***)(')()()()()()()()(1)('⎥⎦⎤⎢⎣⎡-+---+-=x g x x x mg x g x x x g x x x mg x g x m ϕ令*x x =带入上式，可知当1>m 时，111)('*<-=mx ϕ 0)('*≠x ϕ 根据收敛阶判别定理，Newton 法在重根的情形下只能保证有1阶收敛的。
对此 ，人们提出改善重根情形Newton 法收敛性的两种方法。
方法1： 如果已知重根的重数m ,则利用m 构造迭代公式),2,1,0()(')(1 =-=+k x f x f m x x k k k k这时迭代函数)(')()(x f x f m x x -=ϕ，容易求出0)('*=x ϕ，故迭代公式)(')(1k k k k x f x f mx x -=+至少2阶收敛的。
这种方法的缺点是要事先知道重根的重数，但实际应用中往往不知道。
方法2：做)(')()(x f x f x F =。
如果*x 是0)(=x f 的m 重根(1>m ),则*x 是0)('=x f 的1-m 重根，从而*x 是)(x F 的单根。
于是对0)(=x F 使用Newton 迭代，则新的迭代公式也是2阶收敛。
注意到))]('[)('')()]('[/())(')(()')(')(/()(')()(')(22x f x f x f x f x f x f x f x f x f x f x F x F -== )('')()]('[)(')(2x f x f x f x f x f -= 新迭代公式),2,1,0()('')()]('[)(')(21 =--=+k x f x f x f x f x f x x k k k k k k k 这种方法缺点是需要f的2阶导数。
5．Newton 法应用的几点注意① Newton 迭代法可用来求平方根，如求)0(>c c 。
令 c x =，则c x =2得方程0)(2=-=c x x f其正根想x>0 即cNewton 迭代公式 ),2,1,0(221 =--=+k x cx x x kk k k或整理成),2,1,0)((211=+=+k x cx x kk k 且 221)(21)2(21c x x c c x x x c x k kk k k k -=+-=-+故对任意的00>x ,均有 ),2,1,0( =>k c x k 。
又有0)(2121<-=-+k kk k x c x x x 故知迭代序列}{k x 是有下界的单调递增递减序列，从而有极限*x 。
对迭代公式两边取极限得)(21***xcx x +=，即c x =，这说明只需要取00>x 迭代公式收敛于c .② Newton 迭代法也可用来求方程的复根***υi u x +=(如果有复根的话)，这时初值应取 000υi u x +=，并在迭代时用复数运算即可。
③ Newton 迭代法对初值的近似程度要求很高，因此，应用中必要时先用二分法求出足够精确的0x ，然后在用 Newton 法迭代到收敛为止。
④解决Newton 法初值0x 近似要求的另一种途径是结合所谓“下山算法”。
对方程0)(=x f ，下山算法是指在迭代过程中附加一个使)(x f 按模下降的约束条件|)(||)(|1k k x f x f <+ 以确保迭代过程不发散或不原地踏步。
把下山算法和Newton 法结合称为Newton 下山法，其做法是：引入下山因子λ，将Newton 公式修改为 ),2,1,0()(')(1 =-=+k x f x f x x k k k k λ对初值0x ，依次以 ,21,21,12=λ(或再加上限制λελ≥，λε为下山因子的下界)计算出相应的1x ，并相应检验下降条件，直至出现下降条件|)(||)(|1k k x f x f <+成立。
然后才继续以Newton 公式(1=λ)加速(2阶)迭代。
如果又出现下降条件不成立，又重新操作上述选择λ的过程。
4．4 Aitken 加速方案/Steffensen 迭代法仅有线性收敛速度的一般不动点迭代法并不理想，而具有2阶收敛速度的Newton 法则要求条件较高。
因此，突破线性收敛速度的研究得到广泛的关注，已经提出一些效果显著的可行方案。
1．Aitken 加速方案假设迭代序列 }{k x 线性收敛，按线性收敛的定义应有0*1*≠≈--+k kk C x x x x ，同理，也应有011*2*≠≈--+++k k k C x x x x 。
因此，当k 充分大时，1+≈k k C C ，故有1*2**1*+++--≈--k k k k x x x x x x x x 从中解出*x ，则得kk k k k k k k k k k k x x x x x x x x x x x x x +---=+--=+++++++++12212212212*2)(2 ( 4.4.1 )或kk k k k k x x x x x x x +---==++++12212*2)( ( 4.4.2 ) 这表明，当由某种迭代计算出k x ，1+k x ,2+k x 之后，用（4.4.1）式或(4.4.2)式的值作为*x 的近似值，并记为k x ，可望得到有更好的近似效果。