非线性方程组迭代法

1、Renchun-li,XidianUniversityPage of3111/15/20187:13:31AM第5章非线性方程（组）迭代法第5章非线性方程（组）迭代法内容根的搜索迭代法的构造及收敛性方程求根的牛顿迭代法*非线性方程组的迭代法第5章非线性方程(组)迭代法Renchun-li,XidianUniversityPage of3111/15/20187:13:31AM数学物理中许多问题常归结为求解非线性方程或非线性方程组.例如在最优化问题minF(x)中，设函数F(x)在区间I上严格凸并可微，且xelFx)=f(x)，则求其极小点等价于求解方程f(x)=0的根；若f(x)是一个非线性函

2、数，则方程f(x)=0是一个非线性方程。若f(x)=0是一个方程组，且其中至少存在一个方程是非线性的，则称方程组是非线性方程组。本章介绍一些常用的求解非线性方程和非线性方程组近似根的迭代方法。5.1根的搜索根的存在性：设函数f(x)eCa,b，且f(a)f(b)0，记a=x,b=b，方程的根x*g(a,b)；010111Y如果f(x)-f(a)0，记a=a,b=x，方程的根x*g(a,b)。.011011因此，新的有根区间为a,b，其长度为b-a=匕对有根区间a,b施1111211行同样的手续，并反复二分下去，得到一系列有根区间a,boa,boa,boL二a,boL1122kk其中a,b的长度

3、为：b-a=匕aT0(当kTa时)。kkkk2k上述结果表明，如果二分过程无限地继续下去，这些区间最终必将收缩于f(x)=0的根x*只要二分足够多次(即k充分大)，就能保证有b一ax*xbakkkW时,In2满足精度为的要求。k5.2非线性方程的迭代法5.2.1建立迭代公式基本思想：将一元方程f(x)=0等价变形为如下不动点方程x=9(x).(5.2.1)选取一个初始近似解X，构造不动点迭代公式0 x=9(x),k=0,1,2,Lk+1k求得迭代序列x。如果x收敛，则极限点是9(x)的不动点X*(即满足kkx*=9(x*)，也是f(x)=0的根.几何意义如图例5.2.1用迭代法求方程x3-x-

4、1=0在区间11,2的实数根，误差不超过io-5。解根的存在唯一性：设f(x)=x3-x-1，贝f(-1)-f=(-1)-50,xe(1,2),所以方程x3-x-1=0在区间(1,2)内有唯一的实数根x*(2)构造迭代公式：将方程等价变形为：x=3厅TT，则迭代公式x=3!x+1(k=0,1,L2).k+1k(3)取迭代初始值x=1.5，迭代结果见表。若取6位有效数字，贝吐与x完全078相同，这时可近似认为迭代序列已经收敛到了极限点，并将x作为方程的近似解.8表5.2.1kxkkxk01.551.3247611.3572161.3247321.3308671.3247231.3258881.3

5、247241.32494但若对方程做另一种等价变形：x=x3-】，并建立迭代公式k+i=Xk3-1初值仍取x=1.5，则有x=2.375,x=12.39,L.012显然，继续迭代下去不收敛，称迭代公式冲二疔+T是发散的.5.2.2迭代的收敛性：考察一般情形下迭代过程x=,(x)收敛的条件k+1k分析：设方程x=9(x)在区间a,b内有根x*,由微分中值定理xk+1-X*=9(x)-9(x*)kk其中g是x*与x之间某一点，只要xea,b,则匕ea,b。kk若存在常数L,且0L1，则使得Vxea,b都有9(x)L.=9(x)-9(x*)Lx-x(5.2.2)x-x*k+1反复递推有x-xLx-*

6、x从而limx=x*。k0k注意，上述分析实际上要求p(x)是a,b上的压缩映像。定理5.2.1若函数9(x)eDa,b，且满足：(5.2.3)(5.2.4)Vxea,b有，a9(x)b存在正数L1，对Vxea,b，有|p(x)L1则有方程X=9(x)在a,b有唯一不动点x*；迭代过程x=9(x)对于任意初值xea,b均收敛于x*；k+1k0误差估计式x-x*Lx-xk1-L10或x-x*Lx-xk1Lkk-1(5.2.5)证明：设g(x)=x-9(x)，由零点定理以及函数的单调性，可知=9(x)在a,b有唯一不动点x*；由于9(x)9(y)9纟)|卩yLfy(0L1)，9是压缩映射，由压缩映

7、像原理可得迭代序歹列x=9(x)收敛于不动点x*；k+1k由于xxk+1k9(x)-9(xkk-1Llx-xkk-1(5.2.6)据此反复递推得：x-xLkx-xk+1k10。从而对任意正整数p，有第5章非线性方程(组)迭代法Renchun-li,XidianUniversityPage of3111/15/20187:13:31AMRenchun-li,XidianUniversityPage of3111/15/20187:13:31AM第5章非线性方程（组）迭代法X一XX一X+k+pk/k+pk+p1X一Xk+p-1弋+p2Lk+pi+Lk+p-2+L+Lk)X-X+L+X一Xk+1kX

8、一X0=X*即得式(5.2.5).XXClp-i+Lp-2+L+1)x-xk+pkk+ik1XX.1一Lk+1kTa矢口：X*X1|X一X.k1L1k+1k在上式中令p进一步，对任意正整数p又有(5.2.7)101L1上式中令pTa，注意到limxpgk+p由此可见，只要相邻两次计算结果的偏差足够小，即可保证近似值xkXXk+1k具有足够的精度，因此可以通过检查XX|来判断迭代过程应否终止k+1kI实际应用迭代法时，通常在所求根*的邻近进行考察，研究所谓局部收敛性定义5.2.1若存在x*的某个邻域R:x-x*8,使迭代过程=申(x)对于TOC o 1-5 h zk+1k任意初值xeR均收敛，则

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

10、2时称为平方收敛显然，p越大，收敛越快。k+1k定理5.2.3（迭代过程p阶收敛的充分条件）对于迭代过程x=（x），如果cp（p）（x）在所求根x*的邻近连续，并且C*）=）=L=（p-i）（x*）=0；且申（p）C*）h0则该迭代过程在点x*邻近是p阶收敛的.第5章非线性方程(组)迭代法Renchun-li,XidianUniversityPage of3111/15/20187:13:31AM5.2.3迭代公式的加速设x是根x*的某个预测值，用迭代公式计算一次得0 x=申(x)，10由微分中值定理有：x*-x=fC*)-申(x)=0(g)C*-x),100其中g介于x*与x之间假设cp(x

11、)改变不大，近似地取某个近似值,由(5.2.8)0()x*xuLx*x丿，101L可得x*uIx_x。再将上式代入(5.2.8)的右端，得到1L11L0 x*xU厶(xx)11L10类似于(527)，此式可看作是用近似x*的后验误差估计。利用此误差对x11进行校正，将校正值记作x,2)=01Lx一x1L1一L(5.2.9)更一般地，将每次利用迭代公式计算的值利用后验误差进行一次校正,则有下述加速迭代方案：厂迭代：x=申(x)k+1k校正：x=x+厶(xx)(5.2.10)k+1k+11Lk+1k例5.2.3利用上面加速迭代方案求解方程x=e-x(oxe-x=0).解选初始点x=0.5,在根的邻

12、近,C-x)-0.6=L，对应加速迭代系统如下:0 xk+1xk+1=exk,0.6=xxxk+11.6+k1).k迭代结果见下表：表5.2.3kxkxk00.510.606530.5665820.567460.5671330.567150.56714与例5.2.2相比，这里只要迭代3次即可得到相同精度的结果，加速的效果是相当显著的但上述加速方案需要知道关于迭代函数(x)导数的信息L,而在实际中往往难以得到这一信息，造成实际使用不便，因此需要消除进而可以构造出不需要求出L的校正一改进系统如：埃特金(Aitken)方法。该方法除了能够加快收敛速度,有时还能将不收敛的迭代公式改进为收敛的公式.5.

13、3方程求根的牛顿法5.3.1牛顿迭代公式及其收敛性设非线性函数f(x)的一个近似零点x，用f(x)在该点的Taylor展开式的线性0部分来近似f(x)，即f(x)沁f(x)+广(x)(x-x)000故f(x)=0近似等价于f(x)+f(x)(x-x)=0，解出x，并记作为x，即00f(x)x=x-0_x10ff(x)0如此反复，得到求解非线性方程f(x)=0的迭代公式(5.3.1)f(x)x=xk(k=0,1,2L)k+ikfx)k称为牛顿迭代公式。显然，牛顿迭代公式要求在根*的某个邻域内ff(x)主0。牛顿迭代法的几何意义：用f(x)在点x处的切线y=f(x)+f(x)(x-x)kkkk与x

14、做的交点，作为下一个迭代点x，因此牛顿法也称为切线法。定理5.3.1(牛顿迭代公式的收敛性)假设x堤f(x)的单重根，f(x)在根的邻域A:x-x*8内具有二阶连续导数，且对任意xeA有f(x)H0，又初值xeA，则当邻域A充分小时，牛顿法5.3.1)具有2阶收敛速度.0例5.3.1用牛顿法解方程xex-1=0解设f(x)=xex-1，其牛顿公式为x=x-._-讯。取迭代初值x=0.5，k+1k1+x0kRenchun-li,XidianUniversityPage of3111/15/20187:13:31AM第5章非线性方程（组）迭代法迭代结果迭代为x=0.57102,x=0.56716,

15、x=0.56714。123实际上，本例所给方程是例5.2.2中方程x=e-x的等价形式，与例5.2.2的计算结果相比可以看出，牛顿法的收敛速度是相当快的5.3.2牛顿下山法牛顿法是局部收敛的其收敛性依赖于初值x的选取，如果x偏离所求的根00 x*较远，则牛顿法可能发散例如，用牛顿法求方程x3x1=0在x=1.5附近的根x*设取初值x=1.5，用牛顿公式0 x3x1x=xkkk+1k3x21k计算得：x=1.34783,x=1.32520,x=1.32472迭代3次得到的结果x有6位1233有效数字但是，如果改用x=0.6作为迭代初值，则用上面牛顿公式迭代一次0第5章非线性方程(组)迭代法Ren

16、chun-li,XidianUniversityPage of3111/15/20187:13:31AM得x=17.9，这个结果反而比x=0.6更偏离了所求的根x*=1.32472.10为了防止迭代发散，对迭代过程附加单调性要求:(5.3.4)f(x)vf(x)|k+1k满足这项要求的算法称为下山法.将牛顿法与下山法结合起来使用，即可在下山法保证函数值稳定下降的前提下，用牛顿法加快收敛速度为此，将牛顿法的计算结果f(x)x=x-Lak+lkff(x)k与前一步的近似值x适当加权平均作为新的改进值k(5.3.5)x=九x+(1九)xk+1k+1k其中九(0X1)称为下山因子，下山因子应保证单调性

17、(5.3.4)成立.下山因子的选择是个逐步探索的过程533简化牛顿法、弦截法与抛物线法牛顿法在求x时不但要求给出函数值f(x),而且要提供导数值广(x)当k+1kk函数f比较复杂时,提供它的导数值往往是有困难的下面介绍一些避免求导数的方法。简化牛顿法：这种方法的基本思想是利用一个固定常数M丰0代替迭代过程中每点的导数值,公式为x=x-),通常取M=ff(x)。TOC o 1-5 h zk+1kM0弦截法设x,x是f(x)=0的近似根，利用f(x),f(x)构造一次插值多项式kk-1kk-1p(x),并用p(x)=0的根作为f(x)=0新的近似根x由于11k+1p(x)=f(x)+f(xk)-f

18、(xk-1)(x-x), HYPERLINK l bookmark159 o Current Document 1kx-xkkk-1因此有xk+1f(x)xk-f(x)-f(x)kk-1(5.3.6)x-xTOC o 1-5 h zkk-1 HYPERLINK l bookmark163 o Current Document 这样导出的迭代公式(5.3.6)可以看作牛顿公式x=x-一中的导数f(x)k+1kff(x)kk用差商f5)-f5-11取代的结果.x-xkk-1弦截法与切线法(牛顿法)都是线性化方法，但二者有本质的区别切线法在计算x时只用到前一步的值x，而弦截法在求x时要用到前面两步的

19、结果k+1kk+1x,x，因此使用这种方法必须先给出两个开始值,xkk-101例534用弦截法解方程f(x)解设取x=0.5,x=0.6作为开始值，用弦截法求得的结果x=0.5632,012x=0.56709,x=0.56714。比较例5.3.1牛顿法的计算结果可以看出，弦截法的34收敛速度也是相当快的抛物线法已知方程f(x)=0的三个近似根x,x,x,以这三点为节点构造二次插值多kk-1k-2项式p(x),并适当选取p(x)的一个零点x作为新的近似根，这样确定的迭代22k+1过程称抛物线法，亦称密勒(Mfiller)法在几何图形上，这种方法的基本思想是用抛物线y=p(x)与x轴的交点x作为所

20、求根x*的近似位置.2k+1第5章非线性方程（组）迭代法Renchun-li,XidianUniversityPage of3111/15/20187:13:31AM5.4非线性方程组的迭代法5.4.1一般迭代法及其收敛条件般地，一元非线性方程的迭代解法都可以推广到多元非线性方程组。设有非线性方程组212n(5.4.1)n1,x,L,x2n)=0将方程组变形为等价形式：x=申(x,x,L,x)1112n(5.4.2)x=9(x,x,L,x)2212nMx=9nn(x,x,L,x)第5章非线性方程(组)迭代法Renchun-li,XidianUniversityPage of3111/15/20

21、187:13:31AM由此建立迭代公式X（k+1）=申11Cx（k）,x（k）,L,x（k）X（k+1）=申V2212nw（k）,x（k）,L,x（k）12nk=0,1,2,L（5.4.3）X（k+1）=申3nMCx（k）,x（k）,L,x（k）12n选取一组初值x(o),x(o),L,x(o)后，按迭代公式(5.4.3)计算，可得一向量序列（k）在一定条件下向量序列收敛到原方程组的解。设D为含有根x*=C*,x*,L,x)的闭域，一般情况下，D是以根x*为中心的12n超长方体：x-x*d（=1,2,L,n），或超球体:iiir。x=（x,x,L,x12n第5章非线性方程（组）迭代法Rench

22、un-li,XidianUniversityPage of3111/15/20187:13:31AMi,j=1,2,L,na=maxijxeDSXj则有下述三个使迭代法收敛的充分条件(1)a=max工a1；ijj=1=max1in1jni=1a1；(3)ij=工Ya21iji=1j=1例5.4.1求解非线性方程组呼%寿1-0，取初值（X（o）,x（o）=（1.2,1.7加。Ixx3x4=012122则解2二dx12dx21133x(x+4)2它们在C（0）,x（0）处的值为d申dx2(1.2,1.7)=0.3637122=-0.2935,1(1.2,1.7)dx2(1.2,1.7)=0.098

23、于是a=0,a=0.3637,1112因为a=maxa+a,a+a11122122a=0.2935,a=0.0982122=max).3637,0.3915=).3915i所以迭代公式：字的近似解为x(i7)=(1.234275,1.661526)TRenchun-li,XidianUniversityPage of3111/15/20187:13:31AM第5章非线性方程(组)迭代法5.4.2牛顿迭代法将一元非线性方程的牛顿法推广到高维情形，即得非线性方程组的牛顿迭代公式。令f(x)x0_F(x)=f(x)2,x=1x2,0=0MMMf(x)nxn0则方程组(5.4.1)可写为向量形式(5.

24、4.4)F(兀)=0F(x)称为向量值函数，其中f(x)=f(x,x,x)。ii12n设x(k)=Ck),x(k),L,x(k)是方程组(541)的一组近似解，把它的左端在x(k)处12n用多元函数的泰勒展式展开，然后取线性部分，便得方程组(5.4.1)的近似方程组第5章非线性方程（组）迭代法Renchun-li,XidianUniversityPage of3/5/2087:3:3AM(、dfCx(k),x(k),L,x(k)TOC o 1-5 h zfx(k),x(k),L,x(k)+才i12Ax(k)=0(i=1,2,L)(545)i12nQxj冃j如果它的系数矩阵这是关于Ax(k)二x-x(k)(i二1,2,L,n)的线性方程组，iiF(x)二Vf(x)t1Vf(x)T2M曾axaxMLL乞ax2ax2M645.Vf(x)TnQfnQxnQfQfTQxQx12非奇异，则可解得Renchun-li,XidianUniversityPage of3111/15/20187:13:31AM第5章非线性方程(组)迭代法Ax(k)1Ax(k)2MAx(k)ndx1dx1Mdfndx1df1dx2df22dx2Mdfndx2df1dxndf2dxnMdfndxn-1(5.4.7)iii矩阵(546淋为向量函数F(兀)的Jacobi矩阵，记作Fr