研究生数值分析(5)

'()()()()kkkfxfxfxxx则近似方程转化为'()()()0kkkfxfxxx设，上式解为'()0fx'()()kkkfxxxfx5牛顿(Newton)迭代法（1）牛顿迭代公式设xk是非线性方程f(x)=0的一个近似根，把f(x)在xk处作一阶泰勒展开，即用前两项近似代替于是方程f(x)=0的新的近似根xk+1，可由牛顿迭代公式1'()0,1,2,()kkkkfxxxkfx牛顿迭代公式具有明显的几何意义。方程是曲线y=f(x)在点'()()()kkkyfxfxxx(,())kkxfx处的切线方程，迭代公式就是切线与x轴交点的横坐标。因此，牛顿迭代法又称为切线法。求出（2）牛顿迭代法收敛的充分条件'()0fx'()()fxxxfx()0fx具有相同的根。因此，牛顿迭代法是一种以'()()()fxgxxfx为迭代函数的迭代法。当时，方程与定理４对于方程，若存在区间，使()0fx(,)ab1、在内存在方程的单根；(,)ab*x''()fx2、在内连续。(,)ab*x则牛顿迭代法在附近具有局部收敛性。证明：由迭代函数得''''2()()()[()]fxfxgxfx*x()0fx(,)ab所以且*'*()0,()0fxfx*(,)xab由条件（2），必存在区间，(,)cd*(,)xcd'()gx(,)cd使，在内连，且。'()1gx*x根据定理2，牛顿迭代公式在附近局部收敛。因为是在内的单根，'()()()fxgxxfx定理５对方程，若存在区间，使()0fx[,]ab''()fx[,]ab（3）对任意，都有；()()0fafb[,]xab'()0fx''()fx[,]ab0[,]xab''00()()0fxfx{}kx()0fx在上的唯一实根。[,]ab*x（1）在上连续；（2）；（4）在上保号，则当初值，且时，牛顿迭代公式产生的迭代序列收敛于方程定理５的简要几何说明：条件（2）保证了方程y=f(x)在[a,b]内至少有一实根；条件（3）说明在[a,b]上恒有或'()0fx'()0fx即f(x)=单调，f(x)=0在[a,b]内最多有一实根。由条件(1)、(2)、(3)知，方程f(x)=0在[a,b]内有唯一实根。*x条件（4）表明曲线y=f(x)在[a,b]内凹向不变。条件（1）保证了曲线y=f(x)的连续性和光滑性；a*x1x2xb0x''()0fx'()0fxxya*x1x2xb0x''()0fx'()0fxxya*x1x2xb0x''()0fx'()0fxxya*x1x2xb0x''()0fx'()0fxxy0000a*x1x2xb0x''()0fx'()0fxxya*x1x2xb0x''()0fx'()0fxxya*x1x2xb0x''()0fx'()0fxxya*x1x2xb0x''()0fx'()0fxxya*x1x2xb0x''()0fx'()0fxxya*x1x2xb0x''()0fx'()0fxxya*x1x2xb0x''()0fx'()0fxxya*x1x2xb0x''()0fx'()0fxxy0000不难看出，只要初始近似值满足条件及，则迭代过程必收敛。0[,]xab''00()()0fxfx曲线y=f(x)在[a,b]上只有下图四种情形。的实根，要求准确到cos0xx5110kkxx解：设，则()cosfxxx'''()1sin,()cosfxxfxx容易验证在[0，3]上()cosfxxx01[0,3]x''00()()0fxfx例4用牛顿迭代法求方程满足定理５的条件当时牛顿迭代公式收敛1cos(0,1,2,)1sinkkkkkxxxxkx计算结果如下10.750364x20.739113x30.739086x40.739085x因为，所以5430.00000110xx40.739085x为满足精度要求的近似根。例5给出用牛顿迭代法求平方根的迭代公式，并计算(0)cc135.607使其精确至7位有效数字。2()fxxc*xc()0fx的牛顿迭代公式为21'()1()0,1,2,()22kkkkkkkkkfxxccxxxxkfxxx解：作函数，则f(x)=0的正根就是现在分析迭代公式的收敛性，考虑区间(0,)（1），故(00)0,(0)0ff(00)(0)0ff（2）当时，；(0,)x'()0fx（3）当时，，连续；(0,)x''()20fx满足定理５条件，牛顿迭代公式收敛。211()2kkkxcxcx事实上，由迭代公式可得211()2kkkxcxcx两式相除得到，211()kkkkxcxcxcxc200()kkkxcxcxcxc令，于是000xcrxc20kkkxcrxc202021kkkrxccr对任意，总有，0(0,)x01rkkxc说明对任意初值，迭代公式都是收敛的。0(0,)x所以当时，解得由此递推可得利用迭代公式，取012x计算结果111.65029167x精确至7位有效数字，135.60711.64504与精确值135.60711.64504186比较，可知牛顿迭代公式只需迭代3次就能达到精度要求。211.64504303x311.64504186x**'*1()()()()kkkkxxgxgxgxx*(kkxx在与之间）当迭代过程收敛，且连续时,'()gx有*1''*limlim()()kkkkkxxggxxx'*()0gx这表明当时,简单迭代法是线性收敛的。例6分析简单迭代法与牛顿迭代法的收敛速度。解：对于简单迭代法，由对于牛顿迭代法，（1）若是方程的单根（即）*x()0fx*'*()0,()0fxfx则由'()()()fxgxxfx容易验证，当所涉及到的各阶导数在附近连续时*x''*'*''*'*()()0,()()fxgxgxfx这表明牛顿迭代法用于求单根时至少是二阶收敛的。（2）若是方程的重根，*x()0fx(2)mm*()()()mfxxxqx*(()0)qx**'''*''2()()()lim()lim[()]xxxxfxfxgxgxfx**'*2''*'2()[(1)()2()()()()]lim[()()()]xxqxmmqxmxxqxxxqxmqxxxqx110m这表明直接用牛顿迭代法对方程求重根只有线性收敛速度。()0fx即此时有*x对是方程重根的情形，如将方程改写成()0fx()0Fx'(()()/()Fxfxfx其中）*x则是方程的单根，再对()0Fx()0Fx用牛顿迭代法求就具有二阶收敛速度。*x对于一般的线性收敛序列,可通过下述方法加速：{}kx设序列收敛于且{}kx*x*1*lim(01)kkkxxccxx则当充分大时，k**12**1kkkkxxxxxxxx解出，得*x2*121()2kkkkkkxxxxxxx这样又获得了一个由确定的新近似值。12,,kkkxxx2kx*x{}kx通过算式有可能产生一个收敛速度较快的新序列.这种加速方法称为埃特肯(Aitken)加速方法.只要ｋ充分大，这个新近似值就有可能比更好地逼近。根据这个原理，在收敛速度较慢的序列的基础上，'()gx*0xx与的距离又较大时埃特肯加速可能失效。注意：当变化幅度大，kkkkkkkxxxxxxx12212)(~}~{kx将埃特肯加速方法用于迭代法，可得如下算式1()()()()()()2kkkkkkkkkkkygxzgyyxxxzyx迭代迭代加速(0,1,2,)k称为埃特肯算法。例７用迭代法求方程在[0，1]内根()20xfxx*x的近似值，精确到4110kkxx解：取初始近似根00.5x1.用简单迭代法12(0,1,2,)kxkxk2.用牛顿迭代法12(0,1,2,)12ln2kkxkkkxxxxk3.用埃特肯算法2122(0,1,2,)()2kkxkykkkkkkkkyzkyxxxzyx（1）kkxkkxkkx01230.50.7071070.6125470.65404145670.6354980.6437190.6400610.6414868910110.6409640.6412850.6411420.641205（2）kkx01230.50.6389680.6411850.641186（3）kxyz01230.50.6421880.6411860.6411860.7071070.6407410.6411860.6125470.6413840.641186分别求出满足精度要求的近似根，如下表6求方程m重根的Newton法设s是方程f(x)=0的m重根(m≥2),f(x)在s的某邻域内有m阶连续导数,这时0)(,0)()()()()1(sfsfsfsfmm由Taylor公式,得mmsxmfxf)(!)()(1)(12)()()!1()()(mmsxmfxf23)()()!2()()(mmsxmfxf其中321,,都在x与s之间。由Newton法的迭代函数)(/)()(xfxfxx可得smffsxxxsmmsxsx)()()(lim)(lim)(2)(1)(mfmfmxfxfxfxsmmsxsxsx11)]([)()1(lim)]([)()(lim)(lim)(22)(3)(2由此可见，方程f(x)=0的m重根s仍然是其等价方程x=φ(x)的根。由于1)(0s，所以，只要充分靠近s，}{kx1'()0,1,2,()kkkkfxxxkfx由Newton法产生的序列0x仍收敛于s，但是只有线性的收敛速度。若把迭代函数修改为)()()(~xfxmfxx则有sffsxxxsmmsxsx)()()(lim)(~lim)(~2)(1)(0)11(1})]([)()(1{lim)(~lim)(~2mmmxfxfxmfmxssxsx等式说明，当s是方程f(x)=0的m重根时,变形的Newton法),2,1,0()()(1kxfxmfxxkkkk不仅可以收敛于s，且还具有二阶的收敛速度。在重根的情况下，一般重数m是不知道的。因此，使用变形的Newton法公式就有困难。为此，构造函数u(x)：当x=s时，u(x)=0；当时sx)()()(xfxfxu因s是f(x)的m重零点，故，s是u(x)mxu1)(的单零点求解方程u(x)=0的Newton法迭代函数为)()()]([)()()()()(2xfxfxfxfxfxxuxuxxg于是，迭代公式),1,0()()()]([)()(21kxfxfxfxfxfxxkkkkkkk产生的序列}{kx如果收敛于方程f(x)=0的m重根s,就至少是二阶收敛的。它的缺点是要计算)(xf例如，已知方程0512.0408.148.04.1)(234xxxxxf有一个三重根s=0.8，这里408.196.02.44)(23xxxxf96.04.812)(2xxxf如果使用Newton法),2,1,0()()(1kxfxfxxkkkk进行迭代，并取初值，则有10x803649381.0,80