牛顿迭代法

Newton迭代法的基本思想设是f(x)=0的一个近似根，把f(x)在处作泰勒展开若取前两项来近似代替f(x)(称为f(x)的线性化)，则得近似的线性方程设,令其解为,得（1)这称为f(x)=0的牛顿迭代格式。KXKX2)(!2)())(()()(kkkkkxxxfxxxfxfxf0))(()()(kkkxxxfxfxf0)(kxf1kx)()(1kkkkxfxfxx下一页它对应的迭代方程为显然是f(x)=0的同解方程，故其迭代函数为在f(x)=0的根的某个邻域内,在的邻域R内，对任意初值，应用由公式（1）来解方程的方法就称为牛顿迭代法。它是解代数方程和超越方程的有效方法之一.)(xR0)(xf0x)()()(xfxfxx1)()()()(2Lxfxfxfx返回下一页)()(xfxfxx)0)((xf上一页牛顿法的几何意义由（1）式知是点处的切线与X轴的交点的横坐标（如图）。也就是说，新的近似值是用代替曲线y=f(x)的切线与x轴相交得到的。继续取点,再做切线与x轴相交，又可得。由图可见，只要初值取的充分靠近,这个序列就会很快收敛于。Newton迭代法又称切线法1kx)(xfy)()(kkkxfxxxfy))(,(kkxfx1kx))(,(11kkxfx,2kx下一页上一页返回y返回下一页上一页牛顿迭代法的步骤步一、准备。选定初始近似值，计算步二、迭代。按公式迭代一次，得到新的近似值，计算步三、控制。如果满足。则终止迭代，以作为所求的根；否则转步四。此处是允许误差,0x)(00xff)(00xff0001ffxx1x)(),(1111xffxff1x11x1返回下一页上一页而。其中c是取绝对值或相对误差的控制常数，一般可取c=1。步四、修改。如果迭代次数达到预定指定的次数N，或者则方法失败；否则以代替转步二继续迭代。时。，当时；当cxxxxcxxx1101101.....,01f),,(111ffx),,(000ffx返回下一页上一页例题例1:用牛顿法求下面方程的根解因,所以迭代公式为选取,计算结果列于下表从计算结果可以看出,牛顿法的收敛速度是很快的,进行了四次迭代就得到了较满意的结果.20102)(23xxxxf1043)(2xxxf)1043/()20102(2231nnnnnnnxxxxxxx10xn12341.4117647061.3693364711.3688081891.368808108nx返回下一页上一页例2计算的近似值。=10-6x0=0.88解：令x=问题转化为求ƒ(x)=x2-0.78265=0的正根由牛顿迭代公式xk+1=xk-ƒ(xk)/ƒ'(xk)=xk/2+0.78265/2xk迭代结果k0123xk0.8800000.8846880.8846750.884675满足了精度要求=0.884675)(/)(01xfxfxxnnn返回下一页0.782650.782650.78265上一页返回下一页1）当用Newton法求ｍ重根时，不妨设f（x）=xgxxm*0xg*f（x）=xgxxxgxxmm*1m*=xg*xxxmgxx1m**kkk*1kxxfxfxxx=k*kkk*kk*kxgxxxmgxgxxxmgxxklim*k*1kxxxx=klimk*kkk*kkxgxxxmgxgxxxmg=0m1mxmgxg1m**此时，Newton法具有线性敛速。上一页2)修正Newton法求m重根迭代公式注：若是方程的m重根，而在的某一邻域内连续，则修正Newton法是局部收敛的，并具有至少二阶的收敛速度。因为：)()(1kkkkxfxfmxx*x0)(xf)()(xfm*x上一页下一页返回考察函数)()()(xfxfmxx处的导数在*x用定义求导hxhxfhxfmhxhxhx*)*()*(**)()*()*()*(1hxfhxfhmTailor展开)(*)()!1(*)(*)()(*)(!*)(*)(1)(11)(mmmmmmhOxfmhxfhxfhOxfmhxfhxfhm)(*)()!1()(*)(!1)(11)(mmmmmmhOxfmhhOxfmhhm))(1(1hOmhhm)(hO)0(0h0*)(x所以由定理2知至少是二阶收敛上一页下一页返回牛顿迭代法的优缺点1、优点：牛顿迭代法具有平方收敛的速度，所以在迭代过程中只要迭代几次就会得到很精确的解。这是牛顿迭代法比简单迭代法优越的地方。2、缺点：选定的初值要接近方程的解，否则有可能的不到收敛的结果。再者，牛顿迭代法计算量比较大。因每次迭代除计算函数值外还要计算微商值。返回下一页上一页设(x)在有根区间(a,b)上存在二阶导数，且满足（1）(a)(b)0；（2）`(x)0，x(a,b)；（3）``(x)不变号，x(a,b)；（4）初值x0(a,b)；且使(x0)``(x0)0。则牛顿迭代序列{xi}收敛于(x)=0在(a,b)内唯一的根。判别Newton法收敛的充分条件返回上一页