数值分析第八章非线性方程解法

1其中f(x)为非线性函数.如求f(x)=0的根,123)(45xxxxf.2)ln(sin)(12xxexfx第八章非线性方程求根2例若干年以前,美国原子能委员会准备将浓缩的放射性废料装入密封的圆桶内沉至海底.但是,当时一些科学家与生态学家都反对这种作法.科学家用实验测定出圆桶能够承受的最大撞击速度为v=12.2m/s,如果圆桶到达海底时的速度超过这个速度,将会因撞击海底而破裂,从而引起严重的核污染.然而原子能委员会却认为不存在这种可能性.根据圆桶的质量,体积以及海水的密度与海底的深度,通过建立数学模型得知圆桶到达海底时的速度v(m/s)满足如下方程:那么圆桶到达海底时的速度究竟会不会超过12.2m/s呢?.088.1240)17.1261ln(08.223vv3§1对分区间法(二分法)原理:若fC[a,b]，且f(a)·f(b)0，则f在(a,b)上必有一根.[a,b]称为f(x)=0的有根区间.下文中,设x*是方程f(x)=0的根.4取,20bax不妨设f(a)0,f(b)0.①若,0)(0xf则;0*xx②若,0)(0xf取,01xa;1bb③若,0)(0xf.01xb取,1aa以][1,1ba作为新的有根区间继续迭代,得有根区间序列.],[],[],[11nnbababa取2nnnbax为*x的第n个近似值.5abx0x1ab停机准则11εxxkk21)(εxfk或不能保证x的精度x*2xx*6误差分析：第0步产生的20bax有误差20abx*||x第k步产生的xk有误差12kkabx*||x对于给定的精度,可估计二分法所需的步数k：12lnlnln21εabkεabk①简单;②对f(x)要求不高(只要连续即可).①无法求复根及偶重根②收敛慢7例1试用二分法求方程02010)(3xxxf的唯一实根,要求误差不超过.105.04解,09)1(f,08)2(f[1,2]为有根区间;,0103)('2xxff(x)单调增加,方程有唯一根.对分区间次数.288.1312ln)105.0ln()12ln(4n取n=14.8计算结果如下表:nnanbnx)(nxf0121.51.6..1.752.8..2...............121.59448251.59472661.59460460.0007...131.59448251.59460461.59454360.0003...141.59454361.59460461.594574102010)(3xxxf1.5211.51.751.6250.54..9f(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1limkkx,limkkxg§2迭代法10例2用简单迭代法求方程02010)(3xxxf的根,要求精确到0.510-6.解法一：20110)(3xxxxf迭代格式:,201131nnnxxx取初值计算得,5.10x,125.01x,376953.212x,861.100233x显然此迭代序列发散.11例2用简单迭代法求方程02010)(3xxxf的根,要求精确到0.510-6.解法二：10200)(2xxxf迭代格式:,102021nnxx初值,5.10x故,6326531.11x,5790858.12x,5945629.113x,5945618.114x,5945622.115x61415105.0||xx计算得.5945622.115*xx12例2用简单迭代法求方程02010)(3xxxf的根,要求精确到0.510-6.解法三：xxxxf4.010204.110)(2迭代格式:初值,5.10x,4.010204.1121nnnxxx,5947522.1,5.110xx,5945621.14x,5945621.1,5945614.132xx计算得13例2用简单迭代法求方程02010)(3xxxf的根,要求精确到0.510-6.解法四：,1020)(3xxxf迭代格式:初值,5.10x,10231nnxx,6625.1,5.110xx,5961283.1,5925062.11514xx计算得,5945619.1,5945624.14847xx14上例表明,对同一方程可构造不同的迭代格式，产生的迭代序列收敛性也不同.迭代法的收敛性与什么有关？怎样构造具有收敛性的迭代法？15xyy=xxyy=xxyy=xxyy=xx*x*x*x*y=g(x)y=g(x)y=g(x)y=g(x)x0p0x1p1x0p0x1p1x0p0x1p1x0p0x1p116定理考虑方程x=g(x),g(x)C[a,b],若(I)当x[a,b]时，g(x)[a,b]；(II)0L1使得|g(x)|L对x[a,b]成立.则任取x0[a,b]，由xk+1=g(xk)得到的序列收敛于g(x)在[a,b]上的唯一不动点.并且有误差估计式：0kkx||11|*|1kkkxxLxx(k=1,2,…)且存在极限***lim1xgxxxxkkk||1|*|01xxLLxxkk17证明：①g(x)在[a,b]上存在不动点？令xxgxf)()(bxga)(,0)()(aagaf0)()(bbgbf)(xf有根②不动点唯一？反证：若不然，设还有，则)~(~xgx),~*()()~(*)(xxξgxgxgxx*~在和之间*xx~0))(1)(~(ξgxx*而xxξg~*1|)(|18③当k时，xk收敛到x*？|*|kxx|*||)(||)(*)(|111kkkxxξgxgxg0|*|......|*|01xxLxxLkk④?||11|*|1kkkxxLxx|*||*||*||*|||11kkkkkkxxLxxxxxxxx可用来控制收敛精度||1kkxx19?||1|*|01xxLLxxkk⑤||......|||))((||)()(|||011111xxLxxLxxξgxgxgxxkkkkkkkkkk?***lim1xgxxxxkkk⑥*)(*)*)((lim**lim1xgxxxxξgxxxxkkkkkkkL越收敛越快小20例2用简单迭代法求方程02010)(3xxxf的根,要求精确到六位小数.解法一：2011)(3xxxg迭代函数14113)('2xxg解法二：1020)(2xxg迭代函数,11180)10(40|)('|222xxxg对],2,1[x21120)(14201xg故迭代法收敛.21局部收敛定理如果函数g(x)在x*的某邻域B*={x||xx*|*}内连续可微，且x*=g(x*)，|g(x*)|1，则存在正数，*，由x0B开始的迭代收敛.该定理表明，若|g(x*)|1，只要初值x0选得离x*足够近，迭代法一定收敛.22xyy=g(x)x*y=xAitken加速：x0P(x0,x1)x1x2xˆP(x1,x2)21020102)(ˆxxxxxxx一般地，有：21212)(ˆKKKKKKKxxxxxxx比收敛得快.KxˆKxSteffensen加速：.2)(),(),(,21nnnzyxyxxxygzxgyxnnnnnnnnn23取迭代函数,1020)(2xxg按公式.2)(),(),(,21nnnzyxyxxxygzxgyxnnnnnnnnn计算得nnxnynz01.51.63265311.579085811.59449471.59458951.594551021.59456211.59456211.5945621例用Steffensen加速方法求的根,取x0=1.5,=106.02010)(3xxxf解一.24例用Steffensen加速方法求的根,取x0=1.5,=106.02010)(3xxxf解二.取迭代函数,2011)(3xxxg按公式.2)(),(),(,21nnnzyxyxxxygzxgyxnnnnnnnnn计算得nnxnynz01.5-0.125-21.37695311.63454082.346989118.74493721.60218081.73675934.342997031.59485311.59998351.695691141.59456251.59457011.594710651.594562125收敛速度定义设数列nx收敛于,*x如果存在正数r和a,使得axxxxrnnn||||lim**1则称数列nx是r阶收敛的，或称nx的收敛阶为r.r=1,称数列为线性收敛的；r1,称数列为超线性收敛的；r=2,称数列为平方收敛的.收敛阶r的大小刻划了数列的收敛速度，r越大，收敛越快.nx26定理设迭代函数g(x)在x*邻近有r阶连续导数，且,0)(,0)()('),(*)(*)1(***xgxgxgxgxrr则迭代公式xk+1=g(xk)所产生的迭代数列是r阶收敛的.证明：)(1kkxgxrkkrkxxrgxxxgxg*)(!)(...*)*)((*)()(*x0k0!)(*)(rxgr故.!)()(lim*)(**1rxgxxxxrrkkk27Aitken加速有超线性收敛.,0**ˆlimxxxxkkkSteffensen加速有r=2，条件是平方收敛.,1*)(xg对于简单迭代法,若则有线性收敛.,0|*)(||*||*|lim1xgxxxxkkk,0)('*xg28Newton-RaphsonMethod29原理：将非线性方程线性化(Taylor展开)设xn是x*的第n个近似值,将f(x)在xn做Taylor展开))(()()(0nnnxxxfxfxf)()(*nnnxfxfxx线性/*linear*/xyx*xn)()(1nnnnxfxfxx只要fC1，每一步迭代都有f(xn)0，而且若则x*就是f的根.*,limxxnn令xn+1§3牛顿法30例用牛顿法求方程02010)(3xxxf的根,取x0=1.5.解：迭代公式为1032010231nnnnnxxxxx代入初值得：,5945637.1,5970149.121xx.5945621.1,5945621.143xx可见牛顿法收敛很快.31定理（收敛的充分条件）设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]的唯一根.有根根唯一产生的序列单调有界，保证收敛.32（局部收敛性）设f