牛顿-拉夫森迭代法 2

§3.4牛顿迭代法牛顿迭代法也称为牛顿-拉夫森(Newton-Raphson)迭代法，它是数值分析中最重要的方法之一，它不仅适用于方程或方程组的求解，还常用于微分方程和积分方程求解。3.4.1牛顿迭代法用迭代法解非线性方程时，如何构造迭代函数是非常重要的，那么怎样构造的迭代函数才能保证迭代法收敛呢？牛顿迭代法就是常用的方法之一，其迭代格式的来源大概有以下几种方式：1设f(x)GC2［a,b］，对f(x)在点X0日",b］作泰勒展开：f(x)=f(x)+f(x)(x-x)+f(提Txo)2ooo2!略去二次项，得到f⑴的线性近似式：f(x)牝f(xo)+f(xo)(x-xo)。x=x八、00），_f（x）

气+】—气_广（x）

kf(x)由此得到方程f3)=x=x八、00），_f（x）

气+】—气_广（x）

k由此得到方程f3)=0的近似根(假定『3)。即可构造出迭代格式(假定广(气)*0)：这就是牛顿迭代公式，若得到的序列｛xo即可构造出迭代格式(假定广(气)*0)：这就是牛顿迭代公式，若得到的序列｛x2牛顿迭代法也称为牛顿切线法，这是由于f(x)的线性化近似函数l(x)=f(xo)+广(xo)(x-xo)是曲线＞=f(x)过点(xo,f(xo))的切线而得名的，求f(x)的零点代之以求l(x)的零点，即切线l(x)与x轴交点的横坐标，如右图所示，这就是牛顿切线法的几何解释。实际上，牛顿迭代法也可以从几何意义上推出。利用牛顿迭代公式，由xk得到xk+1，从几何图形上看，就是过点(气,f(气))作函数f⑴的切线lk，切线lk与x轴的交点就是xk+1，所以有f(x)=)kTxk+i，整理后也能得出牛顿迭代公式：_f(x)气+广x_fd)

k。3要保证迭代法收敛，不管非线性方程f(x)=0的形式如何，总可以构造：x=9(x)=x一k(x)f(x)(k(x)*o)作为方程求解的迭代函数。因为：9'(x)=1-k(x)f(x)一k(x)f(x)而且9(x)在根a附近越小，其局部收敛速度越快，故可令：9'(a)=°

若广(口)"0(即根a不是/(x)=0的重根)，则由0(a)=0得：()广(以),k(x)=1x=x-旦因此可令f，(X)，则也可以得出迭代公式：k+1kf(Xk)O4迭代法的基本思想是将方程f(x)=0改写成等价的迭代形式x=^(x)，但随之而来的问题却是迭代公式不一定收敛，或者收敛的速度较慢。运用前述加速技巧，对于简单迭代过程七+1=J+f("，其加速公式具有形式:"n+1—七)天—中(x)，其中n+1nf(x)nL记L=°T,上面两式可以合并写成：i"1*X"n+1—七)天—中(x)，其中n+1nf(x)nL记L=°T,上面两式可以合并写成：i"1*需要注意的是，由于L是甲'(x)的估计值，若取中(x)=x+f(x)，则0(x)实际上便是f'(x)的估计值。假设广(x)"0，则可以用广(x)代替上式中的L，就可得到牛顿法的迭代xf(x「x—x—n公式：En广(叩o牛顿迭代法实质上是一种线性化方法，其基本思想是将非线性方程逐步归结为某种线性方程来求解。3.4.2牛顿迭代法的收敛性中(x)-x—^牛顿迭代公式可以看成是由广(x)而获得的不动点迭代格式。这样就可以应用不动点迭代的收敛原则，只须证明在根a附近的迭代函数是一个压缩映象。由于：=1—[f(x)]2-f(x)f"(x)=f(x)f"(x)^_[f3]2[f'(x)]20(a)=f(a)f"(a)=0这里的根^单根，即f(a)=0且f(a)。0，于是：[f(a)]2O那么由0'(x)的连续性可知，存在一个邻域(a—&,a+&)，对这个邻域内的一切x，有：0'(x)<q，其中ovq<1，因此0(x)为区间(a-&，a+&)上的一个压缩映象，于是有以下结论：定理3.4.1设f⑴GC2[a,b]，**是f⑴=0的精确解，且广3^"0，则存在**的&邻域(**一&'X*+5)，对于任何迭代初值*0日**一如**+5)，迭代序列｛收敛于x*O牛顿迭代法具有较高的收敛速度，它的收敛阶数为P=2；而牛顿迭代法的局部收敛性较强，只有初值充分地接近'*，才能确保迭代序列的收敛性。为了放宽对局部收敛性的限制，必须再增加条件建立以下收敛的充分条件。定理3.4.2设f(x)GC2［a,b］，且满足：在区间［a，b］上，⑴f(a)f(b)<0；⑵广⑴。0；⑶f"(x)不变号；⑷幻或⑶满足条件：f(<「(<>0①f(a)<0，f(b)>0，f(x)>0，f"(x)>0.；②f(a)<0，f(b)>0，广⑴>0，f"(x)<0.；③f(a)>0，f(b)<0，f(x)<0，f"(x)>0.；④f(a)>0，f(b)<0，f(x)<0，f"(x)<0。则牛顿迭代序列'七｝，单调地收敛于方程f(x)=0的唯一解x*。由条件⑴至条件⑷可归结为四种情形：对定理的几何意义作如下说明：条件⑴保证了根的存在性；条件⑵表明函数单调变化，在区间［a,b］内有惟一的根；条件⑶表示函数图形在区间［缶b］上的凹向不变。条件⑶和条件⑷一起保证了每一次迭代值都界于区间［ab］i,y内。性)>0/V)<0理)A0b=x。f'Xx)<0在不满足上述收敛充分条件时，有可能导致迭代值远离所求根的情况或死循环的情况(如卜图所示)。【例3.4.1】对于给定的正数a，用牛顿法建立求平方根的收敛迭代公式。解令f3)=42—a，(x>0)，则/⑴=°的正根就是［••'"。x2一a1.a.七+广七—丐厂=2(Xn+r)用牛顿法求解的迭代公式是：七七，公式(3.4.2)由于当x>0时，广(x)=2x>0,f"(x)=2>0,故由收敛定理可知，对于任意满足条件%>履的初始近似值，由选代公式所产生的序列必定收敛于平方根*a。公式(3.4.2)是计算平方根的准确而有效的计算方法。3.4.3牛顿迭代法的变形用牛顿法解方程，虽然在单根附近具有较快的收敛速度，但它有个明显的缺点，就是每次都要计算导数广(x)，当f(x)比较复杂时，计算广(x)可能很困难。下面介绍两种克服这种困难的方法，另外还介绍一种扩大牛顿迭代法初值选择范围的方法，它们统称为变形的牛顿迭代法。1简化牛顿法为避免频繁地计算导数值广(x)，可将它取为固定值，比如在牛顿迭代公式中用f'(X°)代替广"J，即在迭代过程中始终保持分母不变，则有简化牛顿迭代公式(或固定斜率切线法)：Xn+法)：Xn+1f(X)nf(x)°公式(3.4.3)满足上式的L满足上式的L为:其几何意义如下图所示，这时除第一次迭代仍为曲线的切线外，其余皆为该切线的平行线。简化牛顿法避免了每次计算导数值。更一般地，若取f(Xn)=L,则迭代公式成为：x=X一f(Xn)〃+1nL，称为推广的简化切线法。这时L值应满足下式：b'(X)|=1—平<1L可见当L与广(x)同号且满足上述不等式时，推广的简化切线法是收敛的。该迭代形式在参数法里也曾得到过。2由牛顿法的收敛性定理知，牛顿法对初始值的选取要求是很高的。一般地说，牛顿法只有局部收敛性。当初始值取得离根太远时，迭代将不收敛，而一旦初始值进入收敛域内，牛顿法就有平方收敛的速度，为了扬长避短，扩大初始值选取的范围，下面介绍牛顿法的一种改进——牛顿下山法。x=x_xf(七)将牛顿法的迭代公式修改为："1"E)公式(3.4.3)f(x)f(x)f(x)xx其中，入是一个参数，入的选取应使f(nJ<”(n)成立，当"(n+/<"1或1n+1/<£x*牝x££££2，就停止迭代，且取n+1，其中1，2为事先给定的精度，1称为残量精确度，2为根的误差限；否则再减入，继续迭代。按上述迭代过程计算，实际上得到了一个以零为下界的严格单调下降的函数值序列，这个方法就称为牛顿下山法。入称为下山因子，要求满足0<£x-1-1，匕称为下山因子下界，为了方便，一般开始时可简单地取*=1，然后逐步分半11减小，即可选取"T，2，22，…，"%，且使f("<fC成立。牛顿下山法计算步骤可归纳如下：⑴选取初始近似值^0；⑵取下山因子入=Lx=x_^3⑶计算%+1，En广")⑷计算f(xn+1)，并比较/(七+1)与If3n)k勺大小，分以下两种情况：若^^n+1)'<''3『，则当七+1Xn<%时，则就取，~*n+1，计算过程结束；当lx—xUYY1n+1n1>£2时，则把xn+1作为新的^值，并重复回到⑶。若f(七+1)Jf心，则当拦％且If(七+1)<£1，就取渺牝孔，计算过程结束；否则，若X-£X，而f(xn+1)N£1时，则把、1加上一个适当选定的小正数，即取七+1葺作为新的七值，并转向⑶重复计算；当"'％，且f(xn+1)N£1时，则将下山因子缩小一半，并转向⑶重复计算。牛顿下山法不但放宽了初值的选取，且有时对某一初值，虽然用牛顿法不收敛，但用牛顿下山法却有可能收敛。一般来说，牛顿下山法不再有平方收敛速度，它的优点在于可能将原来收敛域以外的初始值，经过几次迭代后拉入收敛域内。例如，已知方程f(x)=x3_x_1=0的一个根为x*a1.32472,若取初值xo=0.6，用牛顿法计算得到的第一次近似值x1=17.9反而比x0更偏离根。若改用牛顿下山法，当取下山因子"=2时，可得'广质63，修正后的迭代序列收敛。(沈建的…史万明P48)3.4.4弦截法1单点弦截法为避免牛顿迭代法中导数的计算，可用平均变化率:

来近似代替广（七），于是得到如下迭代公式：X=X-"）（一）二X0f3”）—f3。）"1”2）-f（x°）”0f（叩—f（X0）公式（3.4.4）i称为单点弦截法。单点弦截法具有明显的几何意义，它林宥是用联结点A（X。，*）与点B（七，七）的直线，代替/\曲线求取与横轴交点作为近似值七+1的方法，以后再过//:（Xo，*）与（七+1，七+1）两点，作直线求取与横轴的丁:,一交点作为X”+2，等等。其中（X0，*）是一个固定点，°/：/X一拓―r称为不动点，另一点则不断更换，故名单点弦截法。可；/以证明，单点弦截法具有收敛的阶r=1，即具有线性收敛速度。2双点弦截法若把单点弦截法中的不动点（气），*）改为变动点（七一1，七一1），则得到下面的双点弦截法的迭代公式：X=X-f（叩（X-X）=七-1f（Xn）一"（七一1）n+1”f（X）-f（X）n”-1f（X）-f（X）公式（345）nn-1nn-1有J-\i\D.%O/m-t-i--t-b.、，-u［、.lqjl/_.、l/＞、ra-r/.rt/—rri.t-t、r,—、—ui—/Xf（XJ\/rti—/Xf（XJ\ir.用弦截法求根的近似值，在儿何上相当于过点（k-1，k-1），和点（k，k）作弦，然后用弦与X轴的交点的横坐标Xk+1作为X*的新的近似值。由于在双点弦截法中，构造的迭代公式在计算新的近似值Xk+1时，不仅用到点Xk上的函数值f（气），而且还用到点Xk-1及其函数值，这就有可能提高迭代法的收敛