非线性方程数值解法

第一章非线性方程和方程组的数值解法非线性方程根的概念给定非线性方程f(x)=0如果有α使得f(α)=0，则称α为f(x)=0的根或f(x)的零点.设有正整数m使得f(x)=(x-α)mg(x)且g(α)0，则当m2时，称α为f(x)=0的m重根；当m=1时，称α为f(x)=0的单根.若α为f(x)=0的m重根，则f(α)=f(α)==f(m-1)(α)=0,f(m)(α)0这里只讨论实根的求法.求根步骤（1）根的存在性.（2）根的隔离.（3）根的精确化.非线性方程求根的数值方法二分法迭代法单点迭代法(不动点迭代，Newton迭代法)多点迭代法(弦截法）迭代法的一般理论迭代法是一种逐次逼近的方法，它的基本思想是通过构造一个递推关系式(迭代格式)，计算出根的近似值序列,并要求该序列收敛于方程的根.单点迭代法将方程f(x)=0改写成等价形式x=(x)(1)建立迭代公式xk+1=(xk)(2)在根的附近任取一点x0，可得一序列.若收敛，即，且(x)连续，则对(2)两端取极限有α=(α)，从而α为方程(1)的根，也称为(x)的不动点，这种求根算法称为不动点迭代法（Picard迭代法）.(x)称为迭代函数.0kkx0kkxlimkkx多点迭代法建立迭代公式xk+1=(xk-n+1,,xk-2,xk-1,xk)(3)对于迭代法需要考虑一下几个主要问题收敛性收敛速度计算效率迭代法的全局收敛性定义1设为f(x)=0的根，如果x0[a,b]，由迭代法产生的序列都收敛于根，则称该迭代法是全局收敛的.迭代法的局部收敛性定义2设方程x=(x)有根α,如果存在α的某个邻域:x-α，对任意初值x0，迭代过程所产生的序列均收敛于根α，则称该迭代法是局部收敛的.迭代过程的收敛速度定义3设迭代过程xk+1=(xk)产生的序列收敛于方程x=(x)的根α，记ek=α-xk，若则称迭代过程是p阶收敛的.特别地，当p=1时，称为线性收敛；当p1时，称为超线性收敛，当p=2时，称为平方收敛.p越大，收敛越快.1lim0kpkkeCe0kkx效率指数定义3称为效率指数.其中p表示迭代的收敛阶，表示每步迭代的计算量.EI越大，计算效率越高.1pEI不动点迭代法不动点迭代法的整体收敛性定理1.1设(x)满足(1)当x[a,b]时，(x)[a,b]；(2)x1,x2[a,b]，有(x1)-(x2)Lx1-x2，L1则对任意初值x0[a,b],迭代过程xk+1=(xk)收敛于x=(x)在[a,b]上的惟一根，且有误差估计式11011kkkkkLxxxLLxxxL证根的存在性由(2)知(x)连续.令f(x)=x-(x),f(a)0,f(b)0,从而f(x)=0在[a,b]上有根，即x=(x)在[a,b]上有根.根的唯一性设x=(x)在[a,b]上有两根α1,α2，α1α2，α1-α2=(α1)-(α2)Lα1-α2与L1矛盾.故α1=α2序列的收敛性xk+1-α=(xk)-(α)Lxk-α,xk+1-αLk+1x0-α由0L1有limkkx误差估计xk+1-xk=(xk)–(xk-1)Lxk-xk-1xk+2-xk+1=(xk+1)–(xk)L2xk-xk-1xk+p-xk+p-1Lpxk-xk-1xk+p-xkxk+p-xk+p-1+xk+p-1-xk+p-2++xk+1-xk(Lp+Lp-1++L)xk-xk-1=令p，有111pkkLLxxL11011kkkkkLxxxLLxxxL定理1.2设(x)在[a,b]上具有一阶导数，且(1)当x[a,b]时,(x)[a,b]；(1)x[a,b]，有'(x)L1则对任意初值x0[a,b],迭代过程xk+1=(xk)收敛于x=(x)在[a,b]上的惟一根.不动点迭代法的局部收敛性及收敛阶定理1.3若(x)在方程x=(x)的根α的邻域内有一阶连续的导数，且'(α)1,则迭代过程xk+1=(xk)具有局部收敛性证由连续函数性质，存在α的充分小邻域:x-α,使当x时，有'(x)L1由微分中值定理有(x)–α=(x)–(α)='()x-αx-α故(x)，由定理1.2知对任意初值x0均收敛.定理1.4若(x)在方程x=(x)的根α的邻域内有充分阶连续的导数，则迭代过程xk+1=(xk)是p阶收敛的充分且必要条件是(j)(α)=0,j=1,2,,p-1(p)(α)0证充分性1()1lim()0!kppkkxpx1()kkxx()11()()!ppkkxxp(1)1()11()()()()()()()(1)!!ppppkkkxxxpp必要性(反证法)设迭代法xk+1=(xk)是p阶收敛的，如果结论不成立，那么必有最小正整数p0p，使得(j)(α)=0,j=1,2,,p0-1(p0)(α)0由充分性的证明知此迭代法是p0阶收敛的，矛盾.必要性得证.例能不能用迭代法求解方程x=4-2x，如果不能时，试将方程改写成能用迭代法求解的形式.方程为x-4+2x=0.设f(x)=x-4+2x，则f(1)0，f(2)0，f'(x)=1+2xln20,故方程f(x)=0仅在区间(1,2)内有唯一根.题中(x)=4-2x，当时x[1,2]时,'(x)=-2xln22ln21,由定理1.2不能用来迭代求根.把原方程改写为x=ln(4-x)/ln2,此时(x)=ln(4-x)/ln2,则有1°当x[1,2]时，(x)[1,ln3/ln2][1,2]2°x[1,2]，有'(x)=由定理1.2知可用迭代公式xk+1=ln(4-xk)/ln2来求解(1,2)区间内的唯一根.142kxkx1111114ln242ln22ln2x例设F(x)=x+c(x2-3)，应如何选取c才能使迭xk+1=F(xk)代具有局部收敛性？方程x=F(x)的根为，函数F(x)在根附近具有连续一阶导数，又F’(x)=1+2cx，解得解得从而使迭代xk+1=F(xk)具有局部收敛性,则，且c0.令得；令得.这时为平方收敛.故当c取时，这个迭代收敛较快.123,3(3)1231Fc103c1231c13c103c)3(F(3)1230Fc123c(3)1230,Fc123c()20Fxc123例设a0,x00,证明:迭代公式是计算的三阶方法.证法一显然是方程x=x(x2+3a)/(3x2+a)的根.事实上此方程有根0,若a0，x00，则xk0（k=1,2,…）.当x00时，.事实上212(3)3kkkkxxaxxaaaaalimkkxa23122(3)()33kkkkkkxxaaxaxaxaxa23122(3)()33kkkkkkxxaaxaxaxaxa2121333110333110()()()()()()kkkkkkkkaxaxaxaxaxaxaxax300()kkkaxaxaxax令解得由|q|1有即迭代序列收敛于故此迭代式确是求的3阶方法.00axqax331()1kkkqxaq331limlim()1kkkkkqxaaqa12311limlim034()kkkkkaxxaaaxa证法二迭代函数(x)=x(x2+3a)/(3x2+a)故此迭代式是求的3阶方法.()aaa()0a3()02aa()0aNewton迭代法Newton迭代法设有方程f(x)=0，在f(x)=0的根α附近任取一点x0作为初始近似根，由迭代公式逐次逼近方程f(x)=0的根α，这种求根算法称为Newton法（切线法），此公式称为Newton迭代公式.1()(0,1,2,)()kkkkfxxxkfxNewton迭代法的收敛性及收敛阶Newton法的迭代函数是从而由此知若α是f(x)=0的一个单根,f(α)=0,f'(α)0,'(α)=0,''(α)=f''(α)/f'(α),则在根α附近Newton法是局部收敛的,并且是二阶收敛的,即p=2.但如果α是f(x)=0的重根，则Newton法仅是线性收敛的,即p=1.()()()fxxxfx2()()()[()]fxfxxfx1112EI事实上，若α是f(x)=0的重根，设其重数为r,()1()2()1()()()()()rrfxxxrf()()1()lim10,()1xxxr()()()fxxxfx()1()2()1()()rrfxxrf(1)1()1(1)2()1211()()()()()()()(1)!!11()()()()()()()(2)!(1)!rrrrrrrrffxfxfxrrxffxfxfxrrNewton迭代法的全局部收敛性定理1.5设f(x)在有根区间[a,b]上二阶导数存在，且满足(1)f(a)f(b)0;(2)f'(x)0,x[a,b];(3)f''(x)不变号,x[a,b];(4)初值x0[a,b]且使f''(x0)f(x0)0;则Newton迭代法收敛于f(x)=0在[a,b]内的惟一根.例研究求的Newton公式证明：对一切,且序列{xk}是单调递减的，从而迭代过程收敛.证因a0，x00,故xk0(k=1,2,).因此对一切k1,均有,利用这一结果，得故xk+1xk,即{xk}单调递减.根据单调有界原理知,{xk}收敛a101(),0(0,1,2,)2kkkaxxxkx1,2,,kkxa121()21()2kkkkkaxxxaxaaxkxa12/111122222kkkkkkxxaxaaxxxa例设a为正实数，试建立求的Newton迭代公式，要求在迭代函数中不用除法运算，并要求当取初值x0满足时，此算法是收敛的.解考虑方程则为此方程的根，，用Newton法求此方程根的迭代公式为迭代函数不含除法运算.递推可得1a020xa1()0fxax21()fxx1a1()(2)(0,1,2,)()kkkkkkfxxxxaxkfx2111(2)(1)(0,1,2,)kkkkaxaxaxaxk201(1)(0,1,2,)kkaxaxk解得当时，，从而此算法收敛.201[1(1)](0,1,2,)kkxaxka020xa011ax20lim(1)0kkax1limkkxa简化Newton法与Newton下山法简化Newton法一般地，取C=f‘(x0).若是一阶收敛的.Newton下山法其中为下山因子，的选取应满足条件:f(xk+1)f(xk)保证所得序列是收敛的.1(),0,1,2,kkkfxxxkC1()(01),0,1,2,()kkkkfxxxkfx()()11,fxxC重根情形