2.3.1 Newton迭代方法的计算公式

1、 0 3牛顿(Newton)迭代方法一、Newton迭代方法的计算公式牛顿迭代法计算公式的推导过程本节所讨论的是：f(x)=0。设兀*是f(x)=0的根，f(x)在兀*的邻域内具有二阶连续导数，在兀*的邻域内取一点x，0使f(x0)丰0，将它在x0点二阶Taylor展开得：f(x)f(x0)+f(x0)(x-x0)+f2；)(x-x0)2沁f(x)+f，(x)(x-x)000又f(x)=0，则有：f(x0)+八x0)(x一x0)0f(x)=0的近似解xQx0f(x)0，记x100f(x0)类似，在点x处Taylor展开，可得：1f(x)f(x)X沁X一1记：X=X一11f(刃，记.21f(对1

2、1依次往下做，可得一般的迭代格式：x=x了丫n,(n=0丄A)n+1nff(x)n上述迭代格式称为求f(x)=0的解的牛顿迭代法。几何意义在点(x0，f(Xo)处作/(x)的切线，交x轴于一点，求该点的横坐标。此切线方程为：yf(x)=ff(x)(xx),当y=0时,ooof(x)得：x=x0一八；)，正是xI的值。0依次类推，在点(x,f(x)作函数/(x)nn的切线，交x轴于一点，切线方程为：yf(x)=f(x)(xx)，当y=0时,nnn得：f(x)XxnnfZ(X-)n正是Xn+1的值。牛顿迭代法又称为切线求根法。迭代法收敛的条件与收敛速度(针对单根而言)定理：设f(X*)Of(x*)

3、工0，且/(x)在x*的邻域内具有二阶连续导数，则由牛顿迭代法产生的迭代序列xx了丫n,(n0,1,A)n+1nf(x)n局部收敛于x，且为平方收敛。证明：在牛顿迭代法的迭代格式中，迭代函数为：(x)xfX0数，即f(x)在x*的邻域内具有二阶连续导(x)=1-(f(x)2-f(x)f(x)fW_f(x)f(x)(八x)2又f(x*)_0，0(x*)_0vl.牛顿迭代法局部收敛于x(由定理2)22(x)=f(x)f(x)f(x)+f(x)f(x)厂2f(x)f(x)ff(x)4-f(x)-0(x*)=f(x*)工0即有：牛顿迭代法具有二阶(平方)收敛速度(由定理3)。说明，只要x充分接近x*,

4、按照牛顿迭代格式0计算的迭代序列总是收敛于兀*的，且收敛的速度为平方收敛。但是，充分的程度没有具体的描述，而且，若x0的值没有取好，有可能得不到收敛的结果。牛顿迭代法收敛的一个保证条件。补充定理：设f(x)在a,b区间上的二阶导数存在，且满足：f(a)f(b)0；Vxga,b,f(x)不变号；Vxga,b,f(x)保持符号不变。初始值x0ga,b,f(x0)f(x0)0，则牛顿迭代法产生的迭代序列收敛于nf(x)-0在a,b区间的唯一根。证明：由知方程f(x)=0在区间有且只有一个根，记为x*。不失一般性，设f(a)0,f(b)0,f(x)0,f(x)0.其他情形可类似证明。按应取x0ga,b

5、,f(x0)0由f(x)0知f(x)为单调增函数，从而知 10 以x为初值，迭代一次0f(x)x=x一0 x10f(x)00另一方面，将f(x*)在x0处作泰勒展开，得f(x*)=f(x)+f(x)(x*-x)0001+f(.)(x*-x)2=0200其中0介于x*和x0之间。将上式两边除以f(x0)，得f(x*)=f(x0)+(x*-x)+严0)(x*-x0)2=0W702f(x)000移项得x*一因而f()(x*x)2/002f(x)0f(x0)x*一x01x*xx一般的，若x*x，同理可证x*xx*。kgkf(x)再对迭代格式x=x-m两边取极限，k+ikf(x7kx_xf(x)x=xT

6、W由此推得f(x)=0,即丁为f(x)=0的根。又f(x)=0在a，b内有唯一根x*，故必有x*=x,即limx=x*。kgk例1.用Newton迭代法建立求、(c0)的迭代公式.解：关键：找到方程f(x)=0，使、厂是它的根.而f(x)=x、c=0满足、厂是方程的根，最好不要出现根号，故作函数f(x)=x2c，则f(x)=0的正根就是下：xn+1f(x)XnXnf(x)nnX2一cn2xn(n0,1,2A)f（x）=x2c=0的Newton迭代公式如o1cx(x+),(n0,1,2A)n+12nxn当x0时，f(X)2X0,f(X)20:Vx0作初始值，X.0（由补充定理得）例2.用简单迭代

7、法和牛顿迭代法求方程xe-x在x0.5附近的根，取X0.5,10-60.解：用简单迭代法：对方程x一e-x0建立迭代格式： 3 x=e-xn,（n=0丄2A）n+1取x0=0.5，计算可得：X25=X26=05671433,（在第26步才达到要求）用牛顿迭代法：对方程X-e-X=0建立迭代格式：xn+1-Xf(X)xnnn(n0,1,2A)x一e-xnn1+e-xn取x005，计算可得:x0.5663111,x0.56714312x0.5671431在第三步就已经达到了要求。显然后者比前者（收敛阶为1）的速度快很多。例3给定方程f(x)=x1+a-x=0,(0vav1)显然有两个根X=0,x2

8、=1。求出用牛顿法解这个方程的收敛的阶。解：牛顿迭代公式为xj+a-Xkaxj+ax二x-kk二kk+1k(1+a)xf-1(1+a)xf-1注意到f(x)=(1+a)xa-1,f(x)=a(1+a)xa-1,f(1)=a,f=a(a+!)存在，因此该迭代法至少是二阶收敛的，又由于申(1)=需=1+a0因此该迭代格式一定是二阶收敛的。a(1+a)在x=0处，由于f(0)=丄不存在，只能用01-a定义求出收敛的阶。由迭代格式：x1+a-Xkax1+ax二x-kk二kk+1k(1+a)xf-1(1+a)xXjk-1两边除以xk+a，得ek+1=xk+1=axk+a(1+a)xf-1此时牛顿法的收敛

9、阶为1+a。例4确定常数p,q,r使迭代公式TOC o 1-5 h z2caa3xk+1=Px+q丁+厂弋产生的序列收敛到严，xkxk并使收敛的阶尽可能高。解：迭代函数22539应使o(x)=px+qa/x+ra/x,x*=要使迭代序列收敛阶尽可能高，fHx*=申(x*),申(x*)=0,申(x*)=0,x*=cp(x*)n=p3a+qa/a2+ra/a即P+q+r=1(1),TOC o 1-5 h z由(x*)=0np-2q-5r=0(2),!同样由申(x*)=0nq+5r=0(3),51由(1),(2),(3)得到p=q=.r=-，而且99!由于(x*)丰0知该迭代是三阶收敛的。2例5应用牛顿法于方程1-a/x2=0，导出求f的迭代公式，由此求f。解：建立迭代格式1-a/xk22a