Chapter6_1_对分法和一般迭代法

第六章非线性方程的数值解法(NumericalMethodsForNon-linearEquation)我们知道在实际应用中有许多非线性方程的例子，例如（1）在光的衍射理论（thetheoryofdiffractionoflight)中,我们需要求x-tanx=0的根（2）在行星轨道（planetaryorbits）的计算中,对任意的a和b，我们需要求x-asinx=b的根（3）在数学中，需要求n次多项式xn+a1xn-1+...+an-1x+an＝0的根引言/*Introduction*/abx1x2a1b2x*b1a2终止条件（terminationcondition）：11εxxkk2)(εxf或§1对分区间法/*BisectionMethod*/若f(x)C[a,b]，且f(a)·f(b)0，则f(x)在(a,b)上必有一根。原理误差分析：第1步产生的21bax有误差21abx*||x第k步产生的xk有误差kkabx*||x2对于给定的精度,可估计二分法所需的步数k：2lnlnln2εabkεabk例1解010423xx21021用二分法求在(1,2)内的根，要求绝对误差不超过f(1)=-50有根区间中点xnf(2)=140(1,2)f(1.5)0(1,1.5)x1=1.5x2=1.5f(1.25)0(1.25,1.5)x3=1.375f(1.375)0(1.25,1.375)x4=1.313f(1.313)0(1.313,1.375)x5=1.344f(1.344)0(1.344,1.375)x6=1.360f(1.360)0(1.360,1.375)x7=1.368f(1.368)0(1.360,1.368)x8=1.364f(x)=x3+4x2-10所以x≈x8=1.364取x10=0.7729，误差为|x*-x10|=1/211。kabkxkf(xk)符号0010.5000－10.5000－0.7500－20.7500－0.8750＋3－0.87500.8125＋4－0.81250.7812＋5－0.78120.7656－60.7656－0.7734＋7－0.77340.7695－80.7695－0.7714－90.7714－0.7724－100.7724－0.7729＋求方程f(x)=x3–e-x=0的一个实根。因为f(0)0,f(1)0,故f(x)在(0,1)内有根用二分法解之，(a,b）=(0,1)计算结果如表：例2解Findsolutionstotheequationx3-6x2+10x-4=0ontheintervals[0,4]，Usethebisectionmethodtocomputeasolutionwithanaccuracyof10－7.Determinethenumberofiterationstouse..Remark1求奇数个根[0,1],[1.5,2.5]and[3,4]，利用前面的公式可计算迭代次数为k=23.Considerf(x)=tan(x)ontheinterval(0,3).Usethe20iterationsofthebisectionmethodandseewhathappens.Explaintheresultsthatyouobtained.(如下图)Remark2要区别根与奇异点Remark3二分发不能用来求重根f(x)=0x=g(x)等价变换f(x)的根g(x)的不动点§2单个方程的迭代法f(x)=0化为等价方程x=g(x)的方式是不唯一的,有的收敛,有的发散Forexample：2x3-x-1=0一、不动点迭代由此可见，这种迭代格式是发散的则迭代格式为1231kkxx(1)如果将原方程化为等价方程123xx取初值00x112301xx312312xx5512323xx(2)如果将原方程化为等价方程321xx仍取初值00x7937.021213301xxx3=0.9940x4=0.9990x5=0.9998x6=1.0000x7=1.0000已经收敛,故原方程的解为x=1.0000同样的方程⇒不同的迭代格式有不同的结果什么形式的迭代法能够收敛呢?9644.027937.1213312xx依此类推,得二、收敛性分析若存在常数(0≤1),使得对一切x1,x2∈[a,b]成立不等式|g(x1)-g(x2)|≤|x1-x2|,则称g(x)是[a,b]上的一个压缩映射,称为压缩系数.定义1考虑方程x=g(x),g(x)C[a,b],若(I)当x[a,b]时，g(x)[a,b]；(II)在[a,b]上成立不等式:|g(x1)-g(x2)|≤|x1-x2|则（1）g在[a,b]上存在惟一不动点x*（2）任取x0[a,b],由xk+1=g(xk)得到的序列{xk}（[a,b]）收敛于x*（3）k次迭代所得到的近似不动点xk与精确不动点x*有有误差估计式：11*kkkxxxx011*xxxxkk定理1|xk-x*|=|g(xk-1)-g(x*)|≤|xk-1-x*|≤2|xk-2-x*|≤…≤k|x0-x*|0|x*-x’|=|g(x*)-g(x’)|≤|x*-x’|.因0≤1,故必有x’=x*由条件②知G(x)在[a,b]上连续,又由介值定理知存在x*∈[a,b],使G(x*)=0，即x*=g(x*).①g(x)在[a,b]上存在不动点？②不动点唯一？③当k时,xk收敛到x*？若有x’∈[a,b],满足g(x’)=x’，令G(x)=g(x)-x,x∈[a,b],由条件①知G(a)=g(a)-a≥0,G(b)=g(b)-b≤0.证明§3Fixed-PointIteration可用来控制收敛精度||1kkxx越小，收敛越快⑤|xk-xk-1|=|g(xk-1)-g(xk-2)|≤|xk-1-xk-2|≤…≤k-1|x1-x0|④|xk-x*|=|g(xk-1)-g(x*)|≤|xk-1-x*|≤(|xk-xk-1|+|xk-x*|),故有11*kkkxxxx联系④中估计式可得011*xxxxkk这就证明了估计式.即估计式成立定理条件非必要条件,而且定理中的压缩条件不好验证，一般来讲,若知道迭代函数g(x)∈C1[a,b],并且满足|g’(x)|≤≤1,对任意的x∈[a,b],则g(x)是[a,b]上的压缩映射Remark12345-6-4-22已知方程2x-7-lgx＝0,求方程的含根区间,考查用迭代法解此方程的收敛性y1=2x-7y2=lgx在这里我们考查在区间[3.5,4]的迭代法的收敛性很容易验证：f(3.5)0,f(4)0将方程变形成等价形式：x＝(lgx+7)/2例3由定理知，迭代格式xk+1＝(lgxk+7)/2在[3.5,4]内收敛)7)((21)(xlgxgxlnxg11021)(1063.0|)(|max45.3xgx局部收敛性定理设x*为g的不动点,g(x)与g’(x)在包含x*的某邻域U(x*)(即开区间)内连续,且|g’(x*)|1,则存在0,当x0∈[x*-,x*+]时,迭代法产生的序列{xk}[x*-,x*+]且收敛于x*.定理2用一般迭代法求x3-x-1=0的正实根x*容易得到:g’(x)在包含x*的某邻域U(x*)内连续，且|g’(x*)|1将方程变形成等价形式：31xx则迭代函数为:31)(xxg32)1(31)(xxg因此迭代格式在x*附近收敛311kkxx例4解用一般迭代法求方程x-lnx＝2在区间(2,)内的根，要求|xk-xk-1|/|xk|=10-8令f(x)=x-lnx-2f(2)0,f(4)0,故方程在(2,4)内至少有一个根又011)(xxfx∈(2,)因此f(x)=0在(2,)内仅有一个根x*将方程化为等价方程：x＝2＋lnxxxgln2)(5.0|1||)(|xxgx∈(2,4)例5解因此，x0(2,),xk+1＝2＋lnxk产生的序列xk收敛于x*取初值x0＝3.0,计算结果如下：kxi03.00000000013.09861228923.13095436233.14133786643.14464878153.14570220963.14603714373.14614361183.14617745293.146188209103.146191628113.146192714123.146193060133.146193169143.146193204另一种迭代格式1)1(1kkkkxlnxxx03.00000000013.14791843323.14619344133.146193221设序列{xk}收敛于x*，若存在p≥1和正数c，使得成立则称{xk}为p阶收敛的特别,p=1，要求c1,称线性收敛;1p2,称超线性收敛p=2,称平方收敛。三、迭代法的收敛阶(收敛速度)cxxxxlimpkkk|*||*|1定义2设x*为g的不动点,p≥2为正整数,g在x*的某邻域Ｕ(x*)内p阶连续可微，且g’(x*)=g’’(x*)=…=g(p-1)(x*)=0，而g(p)(x*)≠0，则存在0，当x0∈[x*-,x*+](x0≠x*)时，由迭代法产生的序列{xk}以p阶收敛速度收敛于x*.(1)由g’(x*)=0必存在0,当x0∈[x*-,x*+］U(x)时,由迭代格式产生的序列{xk}收敛于x*,并有xk∈[x*-,x*+］定理3证明(2)由泰勒公式有pkkpkxxpxxxgxx*)(!*))(*(*)(1)(1kkxgx1)1(*)()!1(*)(*)*)((*)(pkpkxxpxgxxxgxgpkkpxxpxxxg*)(!*))(*()(利用g在x*的各阶导数条件及g(x*)=x*,上式可改写成(3)由于g在x*处p阶连续可微且g(p)(x*)≠0,知必存在x*的某邻域Ｕ(x*),当x∈U(x*)时,有g(p)(x)≠0.上式令k→∞取极限.即{xk}有p阶收敛速度.0!*)(|*||*|)(1pxgxxxxlimppkkk由于x*+(xk-x*)∈[x*-,x*+]U(x*)，故g(p)(x*+(xk-x*))≠0,k=0,1,2,….可见,当初值x0≠x*时,可推出诸xk≠x*!*))(*(|*||*|)(1pxxxgxxxxkppkk于是有