数值分析(研究生)第八章非线性方程求根

第八章非线性方程求根第一节根的隔离与二分法第二节迭代法第三节迭代过程的加速第四节牛顿法第五节弦截法与抛物线法上页下页返回§1根的隔离与二分法求f(x)=0的根根的隔离零点定理：若fC[a,b]，且f(a)·f(b)0，则f在(a,b)上必有一根.单调区间的判定定理.上页下页返回abx1x2ab11εxxkk2)(εxf或不能保证x的精度x*2xx*二分法上页下页返回误差分析：第1步产生的21bax有误差21abx*||x第k步产生的xk有误差kkabx*||x2对于给定的精度,可估计二分法所需的步数k：2lnlnln2εabkεabk①简单;②对f(x)要求不高(只要连续即可).①无法求复根及偶重根②收敛慢注：用二分法求根，最好先给出f(x)草图以确定根的大概位置.或用搜索程序，将[a,b]分为若干小区间，对每一个满足f(ak)·f(bk)0的区间调用二分法程序，可找出区间[a,b]内的多个根，且不必要求f(a)·f(b)0.上页下页返回§2迭代法f(x)=0x=g(x)等价变换f(x)的根g(x)的不动点思路从一个初值x0出发，计算x1=g(x0),x2=g(x1),…,xk+1=g(xk),…若收敛，即存在x*使得，且g连续，则由可知x*=g(x*)，即x*是g的不动点，也就是f的根。0kkx*limxxkkkkkkxgxlimlim1上页下页返回xyy=xxyy=xxyy=xxyy=xx*x*x*x*y=g(x)y=g(x)y=g(x)y=g(x)x0p0x1p1x0p0x1p1x0p0x1p1x0p0x1p1上页下页返回定理考虑方程x=g(x),g(x)C[a,b],若(I)当x[a,b]时，g(x)[a,b]；(II)0L1使得|g’(x)|L1对x[a,b]成立.则任取x0[a,b]，由xk+1=g(xk)得到的序列收敛于g(x)在[a,b]上的唯一不动点.并且有误差估计式：0kkx||11|*|1kkkxxLxx||1|*|01xxLLxxk(k=1,2,…)且存在极限***lim1xgxxxxkkkk上页下页返回证明：①g(x)在[a,b]上存在不动点？令xxgxf)()(bxga)(,0)()(aagaf0)()(bbgbf)(xf有根②不动点唯一？反证：若不然，设还有，则)~(~xgx),~*()()~(*)(xxξgxgxgxx*~在和之间。*xx~0))(1)(~(ξgxx*而xxξg~*1|)(|③当k时，xk收敛到x*？|*|kxx|*||)(||)(*)(|111kkkxxξgxgxg0|*|......|*|01xxLxxLkk上页下页返回④?||11|*|1kkkxxLxx|*||*||*||*|||11kkkkkkxxLxxxxxxxx?||1|*|01xxLLxxkk⑤||......|||))((||)()(|||011111xxLxxLxxξgxgxgxxkkkkkkkkkk?***lim1xgxxxxkkk⑥*)(*)*)((lim**lim1xgxxxxξgxxxxkkkkkkk可用来控制收敛精度||1kkxxL越收敛越快小注：定理条件非必要条件，可将[a,b]缩小，定义局部收敛性：若在x*的某领域B={x||xx*|}有gC1[a,b]且|g’(x*)|1，则由x0B开始的迭代收敛。即调整初值可得到收敛的结果.上页下页返回迭代过程的收敛速度定义设迭代xk+1=g(xk)收敛到g(x)的不动点x*.设ek=xkx*，若，则称该迭代为p阶收敛，其中C称为渐近误差常数.0||||lim1Ceepkkk一般Fixed-PointIteration有，称为线性收敛，这时p=1，0C1.0|*)(|||||lim1xgeekkk注：超线性收敛不一定有p1.例如xn=1/nn超线性收敛到0，但对任何p1都没有p阶收敛.Aitken加速有;称为超线性收敛.0**ˆlimxxxxkkk0||||lim1kkkee上页下页返回Steffensen加速有p=2，条件是，称为平方收敛.1*)(xgNewton’sMethod有,只要，就有p2.重根是线性收敛的.*)(2*)(||||lim21xfxfeekkk0*)(xfQ:如何实际确定收敛阶和渐进误差常数？定理设x*为x=g(x)的不动点，若，p2；，且，则xk+1=g(xk)在内p阶收敛.*))((xBCgp0*)(...*)()1(xgxgp0*)()(xgp*)(xB证明：pkkpkkkxxpgxxxgxgxgx*)(!)(...*)*)((*)()()(1x*kC上页下页返回.1020131313-0331的收敛，并证明该迭代是线性为附近的实根，使其精度在求方程用迭代公式例xxxxxkk上页下页返回待定参数法：若|g’(x)|1，则将x=g(x)等价地改造为)()()1()(xxKgxKxKgKxxx1|)(1||)(|xgKKx求K，使得例：求在(1,2)的实根.013)(3xxxf)()1(313xgxx如果用进行迭代，则在(1,2)中有1|||)(|2xxg现令)1(3)1()()1()(3xKxKxKgxKx希望1|1||)(|2KxKx0122Kx，即在(1,2)上可取任意，例如K=0.5，则对应即产生收敛序列.032K)1(61233xxx§3迭代过程的加速上页下页返回Aitken加速：xyy=xy=g(x)x*x0P(x0,x1)x1x2xˆP(x1,x2)21020102)(ˆxxxxxxx一般地，有：21212)(ˆKKKKKKKxxxxxxx......),(,ˆ),(,ˆ),(),(,34123012010xgxxxgxxxgxxgxx比收敛得略快.KxˆKxSteffensen加速：......,ˆˆ),(),ˆ(,ˆ),(),(,01201012010xxgxxgxxxgxxgxx上页下页返回§4牛顿法原理：将非线性方程线性化——Taylor展开取x0x*，将f(x)在x0做一阶Taylor展开:20000)(!2)())(()()(xxfxxxfxfxf，在x0和x之间.将(x*x0)2看成高阶小量，则有：)*)(()(*)(0000xxxfxfxf)()(*000xfxfxx线性/*linear*/xyx*x0)()(1kkkkxfxfxx只要fC1，每一步迭代都有f’(xk)0，而且，则x*就是f的根.*limxxkk一、牛顿法上页下页返回定理（收敛的充分条件）设fC2[a,b]，若(1)f(a)f(b)0；(2)在整个[a,b]上f”不变号且f’(x)0；(3)选取x0[a,b]使得f(x0)f”(x0)0；则Newton’sMethod产生的序列{xk}收敛到f(x)在[a,b]的唯一根.有根根唯一产生的序列单调有界，保证收敛.定理（局部收敛性）设fC2[a,b]，若x*为f(x)在[a,b]上的根，且f’(x*)0，则存在x*的邻域使得任取初值，Newton’sMethod产生的序列{xk}收敛到x*，且满足*)(xB*)(0xBx*)(2*)()*(*lim21xfxfxxxxkkk上页下页返回证明：Newton’sMethod事实上是一种特殊的不动点迭代其中，则)()()(xfxfxxg10*)(*)(*)(*)(2xfxfxfxg收敛由Taylor展开：2)*(!2)()*)(()(*)(0kkkkkxxfxxxfxfxf2)*()(!2)()()(*kkkkkkxxxffxfxfxx1kx)(2)()*(*21kkkkxffxxxx只要f’(x*)0，则令可得结论.k在单根附近收敛快上页下页返回注：Newton’sMethod收敛性依赖于x0的选取.x*x0x0x0上页下页返回改进与推广重根加速收敛法：Q1:若，Newton’sMethod是否仍收敛？0*)(xf设x*是f的n重根，则：且.)(*)()(xqxxxfn0*)(xq因为Newton’sMethod事实上是一种特殊的不动点迭代，其中，则)()()(xfxfxxg22*)(*)(*)(*)(1|*)(|xfxfxfxfxg111nA1:有局部收敛性，但重数n越高，收敛越慢.Q2:如何加速重根的收敛？A2:将求f的重根转化为求另一函数的单根.令，则f的重根=的单根.)()()(xfxfx上页下页返回求复根——Newton公式中的自变量可以是复数记z=x+iy,z0为初值，同样有)()(1kkkkzfzfzzkkkkkkDiCzfBiAzf)(,)(设代入公式，令实、虚部对应相等，可得;221kkkkkkkkDCDBCAxx.221kkkkkkkkDCCBDAyy上页下页返回二、牛顿下山法——Newton’sMethod局部微调：原理：若由xk得到的xk+1不能使|f|减小，则在xk和xk+1之间找一个更好的点，使得.1kx)()(1kkxfxfxkxk+1,)1(1kkxx]1,0[)()()1(])()([1kkkkkkkkxfxfxxxfxfxx注：=1时就是Newton’sMethod公式.当=1代入效果不好时，将减半计算.上页下页返回一、弦截法Newton’sMethod一步要计算f和f’，相当于2个函数值，比较费时.现用f的值近似f’，可少算一个函数值.x0x1切线弦线切线斜率弦线斜率11)()()(kkkkkxxxfxfxf)()())((111kkkkkkkxfxfxxxfxx需要2个初值x0和x1.收敛比Newton’sMethod慢，收敛阶为p=1.618，且对初值要求同样高.§5弦截法与抛物线法上页下页返回二、抛物线法抛物线法需要已知f(x)=0的根的三个近似值xk-2、xk-1、xk，以它们为节点作抛物插值多项式，取其零点中离xk较近的零点作为f(x)=0的新的近似值xk＋1.x0x2切线抛物线收敛比Newton’sMethod慢，收敛的阶为p=1.84，且对初值要求更高.x1