Chapter3_1_对分法和一般迭代法.

数值分析第三章非线性方程的数值解法数学与统计学院简介（Introduction）•我们知道在实际应用中有许多非线性方程的例子，例如•（1）在光的衍射理论（thetheoryofdiffractionoflight)中,我们需要求x-tanx=0的根•（2）在行星轨道（planetaryorbits）的计算中,对任意的a和b，我们需要求x-asinx=b的根•（3）在数学中，需要求n次多项式xn+a1xn-1+...+an-1x+an＝0的根求f(x)=0的根§3.1对分区间法(BisectionMethod)原理：若f(x)C[a,b]，且f(a)·f(b)0，则f(x)在(a,b)上必有一根。abx1x2a1b2x*b1a2停机条件（terminationcondition）：11εxxkk2)(εxf或误差分析：第1步产生的21bax有误差21abx*||x第k步产生的xk有误差kkabx*||x2对于给定的精度,可估计二分法所需的步数k：2lnlnln2εabkεabk例1用二分法求在(1,2)内的根，要求绝对误差不超过解：f(1)=-50有根区间中点f(2)=140-(1,2)+f(1.25)0(1.25,1.5)f(1.375)0(1.25,1.375)f(1.313)0(1.313,1.375)f(1.344)0(1.344,1.375)f(1.360)0(1.360,1.375)f(1.368)0(1.360,1.368)010423xx21021f(1.5)0(1,1.5)nx1.51x364.1368.1360.1344.1313.1375.125.18765432xxxxxxx12例2，求方程f(x)=x3–e-x=0的一个实根。因为f(0)0,f(1)0。故f(x)在(0,1)内有根用二分法解之，(a,b）=（0,1)’计算结果如表：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＋取x10=0.7729，误差为|x*-x10|=1/211。Remark1：求奇数个根Findsolutionstotheequationontheintervals[0,4]，Usethebisectionmethodtocomputeasolutionwithanaccuracyof10－7.Determinethenumberofiterationstouse..[0,1],[1.5,2.5]and[3,4]，利用前面的公式可计算迭代次数为k=23.Remark2:要区别根与奇异点Considerf(x)=tan(x)ontheinterval(0,3).Usethe20iterationsofthebisectionmethodandseewhathappens.Explaintheresultsthatyouobtained.（如下图）Remark3:二分发不能用来求重根f(x)=0x=g(x)等价变换f(x)的根g(x)的不动点§3.2单个方程的迭代法f(x)=0化为等价方程x=g(x)的方式是不唯一的,有的收敛,有的发散Forexample：2x3-x-1=0321xx(1)如果将原方程化为等价方程由此可见，这种迭代格式是发散的取初值00x310211xx321213xx3322155xx3121kkxx则迭代格式为：321xx(2)如果将原方程化为等价方程00x21031xx3217937.031221xx327937.19644.0仍取初值依此类推,得x3=0.9940x4=0.9990x5=0.9998x6=1.0000x7=1.0000已经收敛,故原方程的解为x=1.0000同样的方程⇒不同的迭代格式有不同的结果什么形式的迭代法能够收敛呢?收敛性分析定义2若存在常数(0≤1),使得对一切x1,x2∈［a,b］,|g(x1)-g(x2)|≤|x1-x2|，(5)则称g(x)是［a,b］上的一个压缩映射，称为压缩系数考虑方程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*有有误差估计式：定理3.2.1*11kkkxxxx*101kkxxxx§3Fixed-PointIteration证明：①g(x)在[a,b]上存在不动点？②不动点唯一？③当k时，xk收敛到x*？|x*-x′|=|g(x*)-g(x′)|≤|x*-x′|.因0≤1，故必有x′=x*若有x′∈［a,b］,满足g(x′)=x′，|xk-x*|=|g(xk-1)-g(x*)|≤|xk-1-x*|≤2|xk-2-x*|≤…≤k|x0-x*|0,令G(x)=g(x)-x,x∈［a,b］，由条件①知G(a)=g(a)-a≥0,G(b)=g(b)-b≤0.由条件②知G(x)在［a,b］上连续，又由介值定理知存在x*∈［a,b］，使G(x*)=0，即x*=g(x*).§3Fixed-PointIteration可用来控制收敛精度||1kkxx越小，收敛越快(4)|xk-x*|=|g(xk-1)-g(x*)|≤|xk-1-x*|≤（|xk-xk-1|+|xk-x*|）,故有|xk-x*|≤/(1-)|xk-xk-1|.这就证明了估计式(6).(5)|xk-xk-1|=|g(xk-1)-g(xk-2)|≤|xk-1-xk-2|≤…≤k-1|x1-x0|联系估计式(6)|xk-x*|≤k-1/(1-)|x1-x0|.即估计式(7)成立Remark：定理条件非必要条件，而且定理3.2.1中的压缩条件不好验证，一般来讲，若知道迭代函数g(x)∈C1『a,b］,并且满足|g′(x)|≤≤1,对任意的x∈［a,b］,则g（x)是［a,b］上的压缩映射例题•已知方程2x-7-lgx＝0，求方程的含根区间，考查用迭代法解此方程的收敛性。在这里我们考查在区间[3.5,4]的迭代法的收敛性•很容易验证：f(3.5)0,f(4)0•将方程变形成等价形式：x＝(lgx+7)/2(lg()7)11()2ln10xgxx1g(x)=23.54max|()|0.0631xgx由定理3.2.1知，迭代格式xk+1＝(lgxk+7)/2在[3.5,4]内收敛局部收敛性定理定理3.2.2设x*为g的不动点，g(x)与g′(x)在包含x*的某邻域U(x*)(即开区间)内连续，且|g′(x*)|1,则存在0，当x0∈［x*-，x*+］时，迭代法(3)产生的序列{xk}［x*-，x*+］且收敛于x*.证明略（作为练习）Wedon’tknowx*,howdoweestimatetheinequality？举例用一般迭代法求x3-x-1=0的正实根x*3x=x+1将方程改写成：3x)=x+1则迭代函数为：g(231x)=3x+1g(（）容易得到：g′(x)在包含x*的某邻域U(x*)内连续，且|g′(x*)|1*3kx=x+1xk+1因此迭代格式在附件收敛例题用一般迭代法求方程x-lnx＝2在区间（2，）内的根，要求|xk-xk-1|/|xk|=10-8解：令f(x)=x-lnx-2f(2)0,f(4)0,故方程在（2,4）内至少有一个根1f(x)=10,2xx又－（，）f(x)=02,2**因此方程在（，）内仅有一个根x且x（，）将方程化为等价方程：x＝2＋lnx1g(x)2lnx(x)|=||0.51,24xx＝＋，|g（，）因此，x0（2，），xk+1＝2＋lnxk产生的序列xk收敛于X*取初值x0＝3.0,计算结果如下：73.14614361183.14617745293.146188209103.146191628113.146192714123.146193060133.146193169143.146193204kxi03.00000000013.09861228923.13095436233.14133786643.14464878153.14570220963.146037143另一种迭代格式：1(1ln)1kkkkxxxx03.00000000013.14791843323.14619344133.146193221程序演示由此可见，对同一个非线性方程的迭代格式，在收敛的情形下，有的收敛快，有的收敛慢。定义1.:设序列{xk}收敛于x*，若存在p≥1和正数c，使得成立则称{xk}为p阶收敛的特别,p=1，要求c1,称线性收敛;1p2,称超线性收敛p=2,称平方收敛。*1*limkpkkxxCxx迭代法的收敛阶(收敛速度)定理3.2.3•设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*)时，由迭代法(3)产生的序列｛xk｝以p阶收敛速度收敛于x*.Prove:•(1)由g′(x*)=0必存在0，当x0∈［x*-，x*+］U(x)时，由迭代格式(3)产生的序列{xk}收敛于x*,并有xk∈［x*-，x*+］•(2)由泰勒公式有xk+1=g(xk)=g(x*）＋g′(x*)(xk-x*)+…+g(p-1)(x*)(xk-x*)p-1/(p-1)!+g(p)(x*+(xk-x*))(xk-x*)p/p!，01.•利用g在x*的各阶导数条件及g(x*)=x*,上式可改写成()****1(()()!ppkkkgxxxxxxxp(11)(3)由于g在x*处p阶连续可微且g(p)(x*)≠0，知必存在x*的某邻域Ｕ(x*)，当x∈U(x*)时，有g(p)(x)≠0.•由于x*+(xk-x*)∈［x*-，x*+］U(x*)，故•g(p)(x*+(xk-x*))≠0，k=0，1,2,….•可见，当初值x0≠x*时，由(11)式可推出诸xk≠x*•于是由(11)式有*()**1*(()!pkkpkxxgxxxpxx•上式令k→∞取极限.*()*1*()lim0!pkpkkxxgxpxx即{xk}有p阶收敛速度.作业（homework)P159：第二题P160：第三题