chapter04非线性方程的迭代解法

非线性方程的迭代解法第4章.],[)(,baCxfRx其中设非线性方程0)(xf（4.1）若常数s使f(s)=0,则称s是方程(4.1)的根，亦称其为函数f(s)的零点。可以分解为如果)(xf),()()(xgsxxfm.0为正整数其中msg,|)(|.重零点的为则称mxfs)(.)(,)()()()()(001sfsfsfsfmm重零点的充要条件是的为充分可导时，当mxfsxf)()(,)()(],,[)(0bfafbaCxf若则可用搜索法求有根区间..0的有根区间求方程xexx−1012f(x)的符号−−++求根问题的三个方面：存在性，分布，精确化。例11对分法有惟一解。）上且在设00xfbabfaf(],[,)()(2000.,)()(./)(停止的零点，那么输出是假如取xxfxfbax假若不然，1010;,)()(bbxaxfaf同号，则与若.,011xbaa否则,],[],[],[kkbababa11故2,/)(sbaxkkk221./)(/)(||kkkkababsx.].,.[位小数点后内的一个实根，准确到在求25101013xx例2kakbkxkf(xk)符号1.0-1.5+01234561.01.251.31251.32031.51.3751.34381.32811.251.3751.31251.34381.32811.32031.3242−+−++−−注1对分法对多个零点的情况，只能算出其中一个零点。注2即使f(x)在[a,b]上有零点，也未必有f(a)f(b)0。2简单迭代法及其收敛性(4.2)0).()(xxxf化为等价形式将非线性方程)0sssf()(.)(不动点的一个为函数称xs0,x给定初始近似值),(01xx),(12xx),(23xx式如此反复，得到迭代公(4.3)210),1.,,,(kxxkk.为迭代函数称)(x有极限得到的迭代序列由如果对任何初值}).(],,[kxbax{220,sxkklim.收敛则称迭代公式(4.2).34不动点迭代法为，也称由于).()(ss..sxx附近的根在求51013例32101511310).,,,(,.kxxxkk，）（解：kxk012345671.51.357211.330861.325881.324941.324761.324731.32472.,39.12,375.2,5.1,1(2)21031xxxxxkk迭代法何时收敛？xyy=xxyy=xxyy=xxyy=xssssy=(x)y=(x)y=(x)y=(x)x0p0x1p1x0p0x1p1x0p0x1p1x0p0x1p1定理4.1考虑方程x=(x),(x)C[a,b],在(a,b)内可导，且(I)当x[a,b]时，(x)[a,b]；(II)0L1使|′(x)|L1对x[a,b]成立。则方程x=(x)在[a,b]上有唯一解s。对于任意的x0[a,b]，由xk+1=(xk)得到的迭代序列{xk}收敛于s，并且;|||11|(1)kkkxxLLsx(事后估计式).|||011|(2)xxLLsxkk(事前估计式)证明：),()(xxxF设(1)],,[)(baCxF则并且有条件(I)可知,)()(0aaaF.)()(0bbbF如果上面两个不等式中有一个等号成立，则方程(4.2)有根s=a,或s=b.如果两个都是严格不等式，则根据介值定理，必存在s(a,b),使F(s)=s-(s)=0,即方程(4.2)有根s(a,b).现设另有x=(x)的一个根t(a,b).由微分学中值定理及(II)得，||ts|)()(|ts|))((|ts||tsL即||||tsLts10L但是0||ts故.ts即(2)因为x0[a,b],由条件(I)可知xk[a,b].又由条件(II)得到||sxk|)()(|sxk1|))((|sxkk之间）与介于（sxkk||sxLk1||||sxLsxkk1||sxLk22||sxLk010L因为,0kkLlim.limsxkk从而因为)()(sxxxsxkkkk11)()()()(sxxxkkk1而))(()()(kkkkkxxxx11kkkxx~~1)(kkxxL1)()(sxk))((sxkksxkk~~)(sxLk,sxLxxsxkkkk1L.1L-1Lkkkxxsx211Lkkkkxxxx322Lkkxx011-kLxx.01kL-1Lxxsxk证毕。已知一个三次方程为例4310xx试在1.5附近讨论根的存在惟一性，再用其计算该方程在1.5附近的一个根.并构造的收敛迭代格式，,)(13xxxf13)(2xxf时，当1x是严格单调递增的。)(xf05)2(,01)1(ff,)(31xxx解：设所以f(x)=0在（1,2）内有唯一的根。将方程变形为,,,,)(210131kxxxkkk建立下面的迭代格式：下面验证此格式是收敛的。321131)()(xx时，当],[21x1310)(x(x)是单调递增的，,)(121323)2(3121)(x故迭代法收敛。用此格式计算得到：x0=1.5x1=1.35721x2=1.33086x3=1.32588x4=1.32494x5=1.32476x6=1.32473X7=1.32472x8=1.32472局部收敛性局收敛性；上的收敛性通常称为全在迭代序列],[}{baxk。不容易由定理作出判断.局部收敛性附近考察收敛性，称为应用上经常只在不动点s定义：.(4.3)0则称迭代序列局部收敛均收敛于迭代序列使得如果),(),(),,(sssUxsU定理4.2.341,是局部收敛的则迭代法且导数的某邻域内有连续在的不动点为迭代函数若).(,|)(|)(,)(ssxxs证明：1)(s.)(1LLs使得取常数由于导数的连续性，.)(),(),,(LxsUxsUs时，有使得当的领域存在由微分学中值定理，时，当],[ssxsx)()()(sx))((xsxsL].,[)(],[ssxssx时，即当由定理4.1，迭代法收敛。.3032sx的根用迭代法求方程1132123121;)()(sxxxxxkkk，，）（;133221)()(sxxxxkk，，）（134023121341321;.)()()(sxxxxxkkk，，）（.03121)321421)()()((sxxxxxkkk，，）（kxk迭代法(1)迭代法(2)迭代法(3)迭代法(4)0123׃x0x1x2x3׃23987׃21.521.5׃21.751.734751.732631׃21.751.7321431.732051׃例53简单迭代法的收敛速度),,,,(,}{2100ksxesxkkk并且收敛于设序列定义：使得和常数如果存在常数,01Cp1,Ceelimpkkk成立，或存在某个K0,使得当kK时1,Ceepkk则称序列{xk}收敛于s时具有p阶收敛速度。.211.)11时为平方收敛当时为超线性收敛；当时迭代法为线性收敛；当特别地，阶收敛则称迭代过程为若误差收敛于设迭代过程ppppCeesxesxxpkkkkkkk,lim,,(定理4.3设(x)C[a,b],在(a,b)内连续可导，且(1)当x[a,b]时，(x)[a,b]；(2)0L1使0|′(x)|L1对x[a,b]成立。对于任意的x0[a,b]，由xk+1=(xk)得到的迭代序列{xk}收敛于s，并且当x0s时，迭代法是线性收敛的。证明：定理4.1已经完成了收敛性证明。下证收敛阶是线性的。,)(),(0xbax时，当))((sxsxkk1于是。就一定有所以只要),,(,2100ksxsxk由Taylor公式，有10),))((()()(sxsxssxkkkkkkeese)(1即)))(((sxsxssxkkk101)()(limlimseseekkkkk故收敛阶是线性的。并且阶连续导数邻近具有的根在如果迭代函数,psxxx)()(定理4.4.,)()()()()()(阶收敛的附近是那么迭代过程在，pssssspp001.00,10平方收敛时当迭代法线性收敛时特别地，当,)(,*)(;|)(|sxs4.迭代收敛的加速方法一、埃特金(Aitken)加速收敛方法法迭代一次得的某个近似值，用迭代是不动点设sx0),(01xx).(12xx再迭代一次得则变化不大如果,,)()(Lxx).-),-112001sxLsxsxsxLsxsx()()(()()(sxsxsxsx1021,2020221212ssxsxxxssxx01221022xxxxxxs0122102201002022xxxxxxxxxxxx.20122010xxxxxx)(:(加速迭代方法于是得到埃特金2Aitken).20122010xxxxxxs)(,121xsxx的新近似，记作为之后，可用上式右端作和在计算了),(kkxx1)(12kkxxkkkkkkkxxxxxxx122112)(./22kkkxxx)(Aitken加速：xyy=xy=(x)sx0P(x0,x1)x1x2xˆP(x1,x2)21020102)(ˆxxxxxxx一般地，有：21212KKKKKKKxxxxxxx)(ˆ......),(,ˆ),(,ˆ),(),(,34223112010xxxxxxxxxxx比收敛得略快。KxˆKx二、斯蒂芬森(Steffensen)迭代法Aitken方法不管原序列{xk}是怎样产生的，对{xk}进行加速计算，得到序列。}{kx把Aitken方法与不动点迭代法结合，则可得到下面的迭代法：),,,(,)()(),(210221kxyzxyxxyzxykkkkkkkkkkk迭代法。称之为斯蒂芬森)(Steffensen改写为另一种形式2101),,,,()(kxxkk.22xxxxxxx)())(())(()(其中，.21)(阶收敛的迭代法是的不动点，且斯蒂芬森为，则存在的不动点，设为反之，的不动点为则的不动点为若)(,)()(.)(,)(xssxxsxsxs定理4.5.101313kkxxxx的迭代将斯蒂芬森法用于解例6解：.,.有收敛结果法计算现用发散指出例nSteffensxxkke1331kxkykzk0123451.51.416291.355651.329851.324801.324722.375001.840921.491401.347101.3251812