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

其中f(x)

为非线性函数.如求

f(x)=0的根第八章非线性方程求根1例若干年以前,美国原子能委员会准备将浓缩的放射性废料装入密封的圆桶内沉至海底.但是,当时一些科学家与生态学家都反对这种作法.科学家用实验测定出圆桶能够承受的最大撞击速度为v=12.2m/s,如果圆桶到达海底时的速度超过这个速度,将会因撞击海底而破裂,从而引起严重的核污染.然而原子能委员会却认为不存在这种可能性.根据圆桶的质量,体积以及海水的密度与海底的深度,通过建立数学模型得知圆桶到达海底时的速度v(m/s)满足如下方程:那么圆桶到达海底时的速度究竟会不会超过12.2m/s呢?2§1对分区间法(二分法)原理:若f

C[a,b]，且f(a)·f(b)<0，则f在(a,b)上必有一根.[a,b]

称为f(x)=0的有根区间.下文中,设x*是方程f(x)=0的根.3取不妨设f(a)<0,f(b)>0.①若则②若取③若取以作为新的有根区间继续迭代,得有根区间序列取为的第n个近似值.4abx0x1ab停机准则或不能保证

x

的精度x*2xx*5误差分析：第0步产生的有误差第k步产生的xk

有误差对于给定的精度,可估计二分法所需的步数k：①简单;②对f(x)

要求不高(只要连续即可).①无法求复根及偶重根②收敛慢6例1试用二分法求方程的唯一实根,要求误差不超过解[1,2]为有根区间;f(x)单调增加,方程有唯一根.对分区间次数取n=14.7计算结果如下表:0121.51.6..1.752.8..2...............121.59448251.59472661.59460460.0007...131.59448251.59460461.59454360.0003...141.59454361.59460461.59457411.5211.51.751.6250.54..8f(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的根.§2迭代法9例2用简单迭代法求方程的根,要求精确到0.510-6.解法一：迭代格式:取初值计算得显然此迭代序列发散.10例2用简单迭代法求方程的根,要求精确到0.510-6.解法二：迭代格式:初值故计算得

11例2用简单迭代法求方程的根,要求精确到0.510-6.解法三：迭代格式:初值计算得12例2用简单迭代法求方程的根,要求精确到0.510-6.解法四：迭代格式:初值计算得13上例表明,对同一方程可构造不同的迭代格式，产生的迭代序列收敛性也不同.

迭代法的收敛性与什么有关？

怎样构造具有收敛性的迭代法？14xyy=xxyy=xxyy=xxyy=xx*x*x*x*y=g(x)y=g(x)y=g(x)y=g(x)x0p0x1p1x0p0x1p1x0p0x1p1x0p0x1p115定理考虑方程x=g(x),g(x)C[a,b],若(I)当x[a,b]时，g(x)[a,b]；(II)0L<1使得|g(x)|L

对x[a,b]成立.则任取x0[a,b]，由xk+1=g(xk)得到的序列收敛于g(x)在[a,b]上的唯一不动点.并且有误差估计式：(k=1,2,…)且存在极限k16证明：①g(x)在[a,b]上存在不动点？令有根②不动点唯一？反证：若不然，设还有，则在和之间而17③当k

时，

xk收敛到x*？④可用来控制收敛精度18⑤⑥L越收敛越快小19例2用简单迭代法求方程的根,要求精确到六位小数.解法一：迭代函数解法二：迭代函数对故迭代法收敛.20局部收敛定理如果函数g(x)在x*的某邻域B*={x||xx*|

*}内连续可微，且x*=g(x*)，|g(x*)|<1，则存在正数，

*，由x0B开始的迭代收敛.该定理表明，若|g(x*)|<1，只要初值x0选得离x*足够近，迭代法一定收敛.21xyy=g(x)x*y=x

Aitken加速：x0P(x0,x1)x1x2P(x1,x2)一般地，有：比收敛得快.

Steffensen加速：22取迭代函数按公式计算得n01.51.63265311.579085811.59449471.59458951.594551021.59456211.59456211.5945621例用Steffensen加速方法求的根,取x0=1.5,=106.解一.23例用Steffensen加速方法求的根,取x0=1.5,=106.解二.取迭代函数按公式计算得n01.5-0.125-21.37695311.63454082.346989118.74493721.60218081.73675934.342997031.59485311.59998351.695691141.59456251.59457011.594710651.594562124

收敛速度定义设数列收敛于如果存在正数r和a,使得则称数列是r阶收敛的，或称的收敛阶为r.r=1,称数列为线性收敛的；r>1,称数列为超线性收敛的；r=2,称数列为平方收敛的.收敛阶r的大小刻划了数列的收敛速度，r越大，收敛越快.25定理设迭代函数g(x)在x*邻近有r阶连续导数，且则迭代公式xk+1=g(xk)所产生的迭代数列是r阶收敛的.证明：0故26Aitken加速有超线性收敛.Steffensen加速有r=2，条件是平方收敛.对于简单迭代法,若

则有

线性收敛.27Newton-RaphsonMethod28原理：将非线性方程线性化(Taylor展开)设xn是

x*的第n个近似值,将f(x)在xn做Taylor展开线性

/*linear*/xyx*xn只要f

C1，每一步迭代都有f(xn)0，而且若则

x*就是f的根.令xn+1§3牛顿法29例用牛顿法求方程的根,取x0=1.5.解：迭代公式为代入初值得：可见牛顿法收敛很快.30定理（收敛的充分条件）设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]的唯一根.有根根唯一产生的序列单调有界，保证收敛.31（局部收敛性）设f

C2[a,b]，若x*

为f(x)在[a,b]上的根，且f(x*)0，则存在x*的邻域使得任取初值Newton’sMethod产生的序列{xk}收敛到x*，且满足定理证明：Newton’sMethod事实上是一种特殊的不动点迭代其中则收敛32由Taylor展开：只要f(x*)0,则令可得结论.在单根附近收敛快再证：33注：Newton’sMethod收敛性依赖于x0的选取.x*x0x0x034当x*是方程的m重根时,牛顿迭代法是线性收敛的,且则称x*为方程f(x)=0的m重根.设35求重根的改进Newton法此时迭代函数则迭代法具有2阶收敛，但要知道x*的重数m.其中m为f(x)=0的根的重数.36构造求重根的另一迭代法则故x*是(x)=0的单根.对它用牛顿法，其迭代函数为从而可构造迭代法它是二阶收敛的.37例方程的根是二重根，用上述三种方法求根.解先求出三种方法的迭代公式(3)方法3取初值x0=1.5,计算结果见下表(1)牛顿