非线性方程组迭代法

1、第5章非线性方程（组）迭代法内容5.1 根的搜索5.2 迭代法的构造及收敛性5.3 方程求根的牛顿迭代法5.4 *非线性方程组的迭代法数学物理中许多问题常归结为求解非线性方程或非线性方程组.例如在最优化问题minF(x)中，设函数F(x)在区间I上严格凸并可微，且XIF'(x)=fix),则求其极小点等价于求解方程f(x)=0的根;若f(x)是一个非线性函数，则方程f(x)=0是一个非线性方程。若f(x)=0是一个方程组，且其中至少存在一个方程是非线性的，则称方程组是非线性方程组。本章介绍一些常用的求解非线性方程和非线性方程组近似根的迭代方法。§5.1根的搜索根的存在性：设函

2、数f(x)wC【a,b，且f(a)f(b)<0,则方程f(x)=0在区间(a,b)内一定有实根x*,称】a,b】为方程f(x)=0的有根区间。二分法(是搜索方程f(x)=0的根的一种计算简单的方法)。.!ab基本思想：将有根区间a,b】用其中点x0='分为两半。2如果f(x0)-f(a)>0,记a1=x0,b1=b,方程的根x*e(a1,b1);v如果f(x0)1f(a)<0,记a1=a,'=x0,方程的根x*(a1,b1)。因此，新的有根区间为出入】，其长度为b1-a1-ba,对有根区间司总施行同样的手续，并反复二分下去，得到一系列有根区间1a,bl二【为由

3、I二a，b2kL=:'-ak,bkl=:L其中以也的长度为：口-2卜=中70（当kTg时）上述结果表明，如果二分过程无限地继续下去，这些区间最终必将收缩于f（x）=0的根x”.只要二分足够多次（即k充分大），就能保证有x一xkbk一akb-a2k显然'当k*Ft时,满足精度为'的要求。§ 5.2 非线性方程的迭代法5.2.1 建立迭代公式基本思想：将一元方程f(x)=0等价变形为如下不动点方程x=(x).(5.2.1)选取一个初始近似解x0,构造不动点迭代公式Xk1=(xj,k=0,1,2,L求得迭代序列人。如果4收敛，则极限点是中(x)的不动点x(即满足x=

4、Rx),也是f(x)=0的根.几何意义如图例5.2.1用迭代法求方程x3-x-1=0在区间11,2的实数根，误差不超过10解(1)根的存在唯一性：设f(x)=x3-x-1,则2f(T)f(2)=(-1)5<0,又f(x)=3x-1>0,x(1,2),所以方程x3-x-1=0在区间(1,2)内有唯一的实数根x*.(2)构造迭代公式：将方程等价变形为：x=我”，则迭代公式x1=3x1k=0,1,2,(3)取迭代初始值%=1.5,迭代结果见表。若取6位有效数字，则X7与X8完全相同，这时可近似认为迭代序列已经收敛到了极限点，并将x8作为方程的近似解，表5.2.1kxkkxk01.551.

5、3247611.3572161.3247321.3308671.3247231.3258881.3247241.32494但若对方程做另一种等价变形：x=x3-1,并建立迭代公式xk.1=xk3-1.初值仍取x0=1.5,则有x1=2.375,x2=12.39,L.显然，继续迭代下去xk由不收敛，称迭代公式xk力=双十1是发散的.5.2.2 迭代的收敛性：考察一般情形下迭代过程xk41=平(xk)收敛的条件.分析：设方程x=Rx)在区间a,b内有根X,由微分中值定理Xk-x=Xk)-nX)=e)<Xk-xK其中是x*与xk之间某一点，只要xjIa,b】，则JIa,bo若存在常数L,且0&

6、lt;L<1,使得vxwIa,b】都有"(x)eL.(5.2.2)则xk十-x"=9(xk)中(xELxk-x*.反复递推有xk-xwL0x*x从而limxk=x”。1 x-J注意，上述分析实际上要求中(x)是【a,b】上的压缩映像。定理5.2.1若函数甲(x!Da,b,且满足：(1) vx-Ia,b】有，a4中(x)eb(5.2.3)(2)存在正数L<1,对vxw【a,b，有卜(x)hL<1(5.2.4)则有方程x=Rx)在1a,b】有唯一不动点x; 迭代过程x=平(xj对于任意初值Ia,b】均收敛于x*;、ri、一、.Lk 反差估计式xk-xw-一-|

7、x1-x0|(5.2.5)或k-x“卜-xJ1 -L证明：设g(x)=x-中(x),由零点定理以及函数的单调性，可知x=Rx)在【a,b1有唯一不动点x; 由于口(*)-%丫)|邛节)口7V1,-丫|(0<1<1),邛是压缩映射，由压缩映像原理可得迭代序列xk书=*(xk)收敛于不动点x； 由于|xHi-xkP|cp(xk)-cp(xk-i)L|xk-xk-i|(5.2.6)据此反复递推得：|xkF-xk|MLk|x1-x0|。从而对任意正整数p,有5+p-xk工Xk+p-Xk+p-+Xk+p,-Xk+p_2+L+Xk十一Xkw(Lk'p'+Lk'p=+L+

8、Lk)|X1x0LkKXX。上式中令pTg，注意到limXk+p=x"即得式(5.2.5).p一,：口进一步，对任意正整数p又有Xk+p一XkM(Lp-1+L"+L+1)Xk书-Xk11-L(5.2.7)在上式中令pT始知:由此可见，只要相邻两次计算结果的偏差Xk十-Xk足够小，即可保证近似值Xk具有足够的精度，因此可以通过检查X,-Xk来判断迭代过程应否终止实际应用迭代法时，通常在所求根X的邻近进行考察，研究所谓局部收敛性定义5.2.1若存在X的某个邻域R:x-x*<6,使迭代过程xk十=%xk)对于任意初值Xo乏R均收敛，则称迭代过程xk41=%xk)在根X邻近具

9、有局部收敛性.定理5.2.2(迭代过程局部收敛的一个充分条件)设x*为方程x=(x)的根，甲'(x)在x*的邻近连续且?'(x")|<1,则迭代过程xk十=中(xk)在x率邻近具有局部收敛性.例5.2.2求方程f(x)=x-e-x=0在0,1内的根，要求精度名=10一5.解因为f(0)<0,f(1)>0,且f'(x)=1+e-x>0,所以方程在(0,1)内仅有一个根。用二分法进行简单的搜索，将求根区间缩小为(0.5,0.6)。建立不动点方程x=e-x,构造迭代公式x=e-xk(k=0,1,2,L)。选初始点x0=0.5,显然在根的邻近，

10、(e-x)之0.6<1。因此迭代公式对于初值a=0.5是收敛的.迭代结果见下表，比较相邻两次迭代值，迭代18次满足精度要求，得近似根0.56714.表5.2.2kXkkXkkXk00.570.5684380140.567118810.606530680.5664094150.567157120.545239290.5675596160.567135430.5797031100.5669072170.567147740.5600646110.5672772180.567140750.5711721120.567067360.5648629130.5671863一种迭代过程是有效的，不仅要保

11、证收敛性，还要考察其收敛速度.所谓迭代过程的收敛速度，是指在接近收敛的过程中迭代误差的下降速度.定义5.2.2设迭代过程xk41=中（xk）收敛于方程x=%x）的根X,如果迭代误差ek=xk-x*当k-*8时成立下列渐近关系式与tc（C=0为常数），ep则称该迭代过程是p阶收敛的.特别地，p=i时称为线性收敛，pi时称为超线性收敛，p=2时称为平方收敛.显然，p越大，收敛越快。定理5.2.3（迭代过程p阶收敛的充分条件）对于迭代过程x.=中（xk）,如果中（p）（x）在所求根x*的邻近连续，并且吸（x"）="（x*）=L=KpT）（x"）=0;且邛（p）（x20.

12、则该迭代过程在点x*邻近是p阶收敛的.5.2.3迭代公式的加速设x0是根X的某个预测值，用迭代公式计算一次得Xi=平（X0）,由微分中值定理有：X一X1=X一X0：|：°i:）1X一X0,其中亡介于/与x0之间.假设一（x）改变不大，近似地取某个近似值L,由X-X1LX-x0,（5.2.8）可得x*-X1-x0o再将上式代入（5.2.8）的右端，得到1-L1-LLX-X1X1-x01-LXi类似于（5.2.7）,此式可看作是用x1近似X的后验误差估计。利用此误差对进行校正，将校正值记作x2,即0二1Lx1x1-LLL(5.2.9)更一般地，将每次利用迭代公式计算的值利用后验误差进行一

13、次校正，则有下述加速迭代方案:迭代:校正:xk1xk1xk1L+1-Lxk1一人(5.2.10)例5.2.3利用上面加速迭代方案求解方程x=ex（二x-e-x=0）.解选初始点x0=0.5,在根的邻近，（e-x）定-0.6=L，对应加速迭代系统如下:_ckxk十一e，0.6_xk1;xk丁丁kxk迭代结果见下表：表5.2.3kXkXk00.510.606530.5665820.567460.5671330.567150.56714与例5.2.2相比，这里只要迭代3次即可得到相同精度的结果，加速的效果是相当显著的.但上述加速方案需要知道关于迭代函数中（x）导数的信息L,而在实际中往往难以得到这一

14、信息，造成实际使用不便，因此需要消除L.进而可以构造由不需要求由L的校正一改进系统，如：埃特金（A计ken）方法。该方法除了能够加快收敛速度，有时还能将不收敛的迭代公式改进为收敛的公式.§ 5.3 方程求根的牛顿法5.3.1 牛顿迭代公式及其收敛性设非线性函数f(x)的一个近似零点x0,用f(x)在该点的Taylor展开式的线性部分来近似f(x),即f(x)f(xo)f(xo)x-xo故f(x)=0近似等价于f(x0)+fx0)(x-x0)=0,解由x,并记作为x,即fXo如此反复，得到求解非线性方程f(x)=0的迭代公式xk1fxkx-fxk(k=0J,2L)(5.3.1)称为牛顿

15、迭代公式。显然，牛顿迭代公式要求在根x”的某个邻域内f'(x)#0。牛顿迭代法的几何意义：用f(x)在点xk处的切线y=f(xk)+f'(xk)(x-xk)与x做的交点，作为下一个迭代点xk.因此牛顿法也称为切线法。定理5.3.1(牛顿迭代公式的收敛性)假设x*是f(x)的单重根，f(x)在根的邻域:|x-x*'6内具有二阶连续导数，且对任意xw有f'(x)，0,又初值x°w,则当邻域充分小时，牛顿法(5.3.1)具有2阶收敛速度.例5.3.1用牛顿法解方程xex-1=0.xk解设f(x)=xex-1,其牛顿公式为人力=xk-xk-e。取迭代初值x0=

16、0.5,1xk迭代结果迭代为x1=0.57102,x2=0.56716,x3=0.56714。实际上，本例所给方程是例5.2.2中方程x=e-x的等价形式，与例5.2.2的计算结果相比可以看由，牛顿法的收敛速度是相当快的.5.3.2 牛顿下山法牛顿法是局部收敛的，其收敛性依赖于初值x0的选取，如果x0偏离所求的根x”较远，则牛顿法可能发散.例如，用牛顿法求方程x3-x-1=0在x=1.5附近的根x*.设取初值x0=1.5,用牛顿公式3x=x_xk-xk-1xk+1xk3x2-1计算得：x1=1.34783,x2=1.32520,x3=1.32472.迭代3次得到的结果x3有6位有效数字.但是，

17、如果改用x0=0.6作为迭代初值，则用上面牛顿公式迭代一次得X1=17.9,这个结果反而比x0=0.6更偏离了所求的根x*=1.32472.为了防止迭代发散，对迭代过程附加单调性要求：f（xk41，|f（xk.（5.3.4）满足这项要求的算法称为下山法.将牛顿法与下山法结合起来使用，即可在下山法保证函数值稳定下降的前提下，用牛顿法加快收敛速度.为此，将牛顿法的计算结果xk1=xkfxkfxk与前一步的近似值xk适当加权平均作为新的改进值其中九（0九41）称为下山因子，下山因子应保证单调性（5.3.4）成立.xk1=Xi1-xk(5.3.5)下山因子的选择是个逐步探索的过程.5.3.3 简化牛顿

18、法、弦截法与抛物线法牛顿法在求xk书时不但要求给由函数值f(xk),而且要提供导数值f'(xk).当函数f比较复杂时，提供它的导数值往往是有困难的.下面介绍一些避免求导数的方法。简化牛顿法：这种方法的基本思想是利用一个固定常数M=0代替迭代过程中每点的导数值，公式为fXkxk+1=xk,通吊取M=f(x0)。M弦截法设xk,xk_1是f(x)=0的近似根，利用f(xk),f(xk)构造一次插值多项式pjx),并用Pi(x)=0的根作为f(x)=0新的近似根x3.由于fxk-fxk.P1(x)=f(xk)+-(x-xk),xk-x-1因此有Xki-Xk-k1kfXk-fXjXk-Xk.i

19、(5.3.6)用差商fXk一fXk”人一Xk-1取代的结果.这样导生的迭代公式（5.3.6）可以看作牛顿公式xk=人-上出中的导数f'（xkfXk弦截法与切线法(牛顿法)都是线性化方法，但二者有本质的区别.切线法在计算xk书时只用到前一步的值xk,而弦截法在求xk句时要用到前面两步的结果xk,xk,因此使用这种方法必须先给由两个开始值x0,x1.例5.3.4用弦截法解方程f(x)=xex-1=0.解设取x。=0.5,xi=0.6作为开始值，用弦截法求得的结果x2=0.5632,x3=0.56709,x4=0.56714。比较例5.3.1牛顿法的计算结果可以看由，弦截法的收敛速度也是相当

20、快的.抛物线法已知方程f(x)=0的三个近似根xk,xk_1,xk_2,以这三点为节点构造二次插值多项式p2(x),并适当选取p2(x)的一个零点xk+作为新的近似根，这样确定的迭代过程称抛物线法，亦称密勒(Muller)法.在几何图形上，这种方法的基本思想是用抛物线y=P2(x)与x轴的交点”书作为所求根x*的近似位置.§ 5.4 非线性方程组的迭代法5.4.1 一般迭代法及其收敛条件一般地，一元非线性方程的迭代解法都可以推广到多元非线性方程组。设有非线性方程组flXi,X2,L,Xn=0f2Xi，X2，L,xn=0Mfn(Xi，X2，L,Xn)=0将方程组变形为等价形式：Xi=i

21、Xi,X2,L,XnX2=2Xi，X2，L,Xn(5.4.1)(5.4.2)M由此建立迭代公式x1k、1xik,x2k,L,xnk(5.4.3)x2kFxi'x'LMk0,1,2,LMx-xik,x2k,L,xnk选取一组初值x（Qx20）,L,x,唁，按迭代公式（5.4.3）计算,可得一向量序列（x（k）。在一定条件下向量序列收敛到原方程组的解。设D为含有根x*=（x：,x2,L,x：的闭域，一般情况下，D是以根x”为中心的超长方体:K-x：w&(i=1,2,L,n),或超球体:工(xi-xf)2<ro记jnTx=x1,x2,L,xnaj=maxx三Di,j=1

22、,2,L,n则有下述三个使迭代法收敛的充分条件:n(1) a=max!aij<1;1.1 _n_ijj1n(2) =max"1 jniTaijnn1;(3)八'aj1i=1j=1例5.4.1求解非线性方程组取初值（x?愁）T=（1.2,1.7）T。Xi将原方程组改写为3：x2xj4=272：2二1124x13x43次1（为+4,它们在（渭制）处的值为:(1.2,1.7)二1x2=0.3637(1.2,1.7)2=-0.2935,(1.2,1.7)、4=0.098(1.2,1.7)于是3n=0,a12=0.3637,a21=0.2935,a22=0.098因为a=max&

23、#39;sa12,a21a22二max0.3637,0.3915039151X1k1所以迭代公式：心.5卜x2k)2x2k1=3x2k)+4收敛。经过17次迭代，得到7位有效数526T字的近似解为x17=1.234275,1.6615.4.2牛顿迭代法将一元非线性方程的牛顿法推广到高维情形，即得非线性方程组的牛顿迭代公式。令fixf2xM_fnX则方程组（5.4.1）可写为向量形式(5.4.4)Fx=0F（x）称为向量值函数,其中"x）=fi（x1,x2；'-,xn）设乂（"=（曦2卜九，/）是方程组（5.4.1）的一组近似解，把它的左端在£）处用多元函数

24、的泰勒展式展开，然后取线性部分，使得方程组（5.4.1）的近似方程组fi“F这是关于&x(k)=xF(x)非奇异，则可解得n,L,xnk-j，fiXik,X2k,L,XnkXjk=0(i=1,2,L)(5.4.5)-X(7i=1,2,L,n)的线性方程组，如果它的系数矩阵Ffi(x)T“2(X)TM：Wn(X)TIfCX,IMfXX2ff2；X2M：X2：flXnXnXn(5.4.6)41二f1x2Xn-J|=Mf2f2-fiX1M:f1nx2M:f1nXnM:f1nIL-fn(5.4.7)X2Xnx-)+川，)矩阵(5.4.6)称为向量函数Fix)的Jacobi矩阵，记作F'(x)。又记X，")(i=1,2,L,n),则式(5.4