1、其中其中f(x)为非线性函数为非线性函数.如如求求 f(x)=0 的根的根,123)(45 xxxxf.2)ln(sin)(12 xxexfx第八章第八章 非线性方程求根非线性方程求根1例例 若干年以前若干年以前,美国原子能委员会准备将浓缩的放美国原子能委员会准备将浓缩的放射性废料装入密封的圆桶内沉至海底射性废料装入密封的圆桶内沉至海底.但是但是,当时一些当时一些科学家与生态学家都反对这种作法科学家与生态学家都反对这种作法.科学家用实验测科学家用实验测定出圆桶能够承受的最大撞击速度为定出圆桶能够承受的最大撞击速度为v=12.2 m/s,如果如果圆桶到达海底时的速度超过这个速度圆桶到达海底时的速
2、度超过这个速度,将会因撞击海将会因撞击海底而破裂底而破裂,从而引起严重的核污染从而引起严重的核污染.然而原子能委员会然而原子能委员会却认为不存在这种可能性却认为不存在这种可能性.根据圆桶的质量根据圆桶的质量,体积以及体积以及海水的密度与海底的深度海水的密度与海底的深度,通过建立数学模型得知圆通过建立数学模型得知圆桶到达海底时的速度桶到达海底时的速度v(m/s)满足如下方程满足如下方程:那么圆桶到达海底时的速度究竟会不会超过那么圆桶到达海底时的速度究竟会不会超过12.2 m/s呢呢?.088.1240)17.1261ln(08.223 vv21 对分区间法对分区间法(二分法二分法)原理原理:若若
3、 f Ca,b,且且 f(a)f(b)0,则则 f 在在(a,b)上必有一根上必有一根.a,b 称为称为 f(x)=0的的有根区间有根区间.下文中下文中,设设 x*是方程是方程 f(x)=0的根的根.3取取,20bax 不妨设不妨设 f(a)0.若若 ,0)(0 xf则则;0*xx 若若,0)(0 xf取取,01xa ;1bb 若若,0)(0 xf.01xb 取取,1aa 以以1,1ba作为新的有根区间继续迭代作为新的有根区间继续迭代,得有根区间序列得有根区间序列.,11 nnbababa 取取2nnnbax 为为*x的第的第n个近似值个近似值.4abx0 x1ab停机准则停机准则11xxkk
4、 21)(xfk 或或不能保证不能保证 x 的精度的精度x*2xx*5误差误差 分析:分析:第第0步产生的步产生的20bax 有有误差误差20abx*|x 第第 k 步产生的步产生的 xk 有有误差误差12 kkabx*|x对于给定的精度对于给定的精度 ,可估计二分法所需的步数可估计二分法所需的步数 k:12lnlnln21 abkabk简单简单;对对 f(x)要求不高要求不高(只要连续即可只要连续即可).无法求复根及偶重根无法求复根及偶重根 收敛慢收敛慢 6例例1 试用二分法求方程试用二分法求方程02010)(3 xxxf的唯一实根的唯一实根,要求误差不超过要求误差不超过.105.04 解解
5、,09)1(f,08)2(f1,2为有根区间为有根区间;,0103)(2 xxff(x)单调增加单调增加,方程有唯一根方程有唯一根.对分区间次数对分区间次数.288.1312ln)105.0ln()12ln(4 n取取 n=14.7计算结果如下表计算结果如下表:nnanbnx)(nxf0 1 2 1.5 1.6.1.75 2.8.2.12 1.5944825 1.5947266 1.5946046 0.0007.13 1.5944825 1.5946046 1.5945436 0.0003.14 1.5945436 1.5946046 1.594574102010)(3 xxxf1.5 211
6、.5 1.75 1.625 0.54.8f(x)=0 x=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 迭代法迭代法9例例2 用简单迭代法求方程用简单迭代法求方程02010)(3 xxxf的根的根,要求精确到要求精确到0.5 10-
7、6.解法一:解法一:20110)(3 xxxxf迭代格式迭代格式:,201131 nnnxxx取初值取初值 计算得计算得,5.10 x,125.01 x,376953.212 x,861.100233 x显然此迭代序列发散显然此迭代序列发散.10例例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.
8、115 x61415105.0|xx计算得计算得.5945622.115*xx 11例例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计算得计算得12例例2 用简单迭代法求方程用简单迭代法求方程02010)(3 xxxf的根的根,要求精确到要求精确到0.5 10-6.解法四:解法
9、四:,1020)(3xxxf 迭代格式迭代格式:初值初值,5.10 x,10231nnxx ,6625.1,5.110 xx,5961283.1,5925062.11514 xx计算得计算得,5945619.1,5945624.14847 xx13上例表明上例表明,对同一方程可构造不同的迭代格式,对同一方程可构造不同的迭代格式,产生的迭代序列收敛性也不同产生的迭代序列收敛性也不同.迭代法的迭代法的收敛性收敛性与什么有关?与什么有关?怎样构造具有怎样构造具有收敛性收敛性的迭代法?的迭代法?14xyy=xxyy=xxyy=xxyy=xx*x*x*x*y=g(x)y=g(x)y=g(x)y=g(x)
10、x0p0 x1p1 x0p0 x1p1 x0p0 x1p1x0p0 x1p115定理定理考虑方程考虑方程 x=g(x),g(x)Ca,b,若若(I)当当 x a,b 时,时,g(x)a,b;(II)0 L 1 使得使得|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 k16证明:证明:g(x)在
11、在a,b上存在不动点?上存在不动点?令令xxgxf )()(bxga )(,0)()(aagaf0)()(bbgbf)(xf有根有根 不动点唯一?不动点唯一?反证:若不然,设还有反证:若不然,设还有 ,则,则)(xgx ),*()()(*)(xxgxgxg xx*在在和和 之间之间*xx0)(1)(gxx*而而xxg*1|)(|17 当当k 时,时,xk 收敛到收敛到 x*?|*|kxx|*|)(|)(*)(|111 kkkxxgxgxg0|*|.|*|01 xxLxxLkk?|11|*|1kkkxxLxx|*|*|*|*|11kkkkkkxxLxxxxxxxx 可用可用 来来控制收敛精度控制
12、收敛精度|1kkxx 18?|1|*|01xxLLxxkk|.|)(|)()(|011111xxLxxLxxgxgxgxxkkkkkkkkkk?*lim1xgxxxxkkk *)(*)*)(lim*lim1xgxxxxgxxxxkkkkkkk L 越越 收敛越收敛越快快小小19例例2 用简单迭代法求方程用简单迭代法求方程02010)(3 xxxf的根的根,要求精确到六位小数要求精确到六位小数.解法一:解法一:2011)(3 xxxg迭代函数迭代函数14113)(2 xxg 解法二:解法二:1020)(2 xxg迭代函数迭代函数,11180)10(40|)(|222 xxxg对对,2,1 x21
13、120)(14201 xg故迭代法收敛故迭代法收敛.20局部收敛定理局部收敛定理如果函数如果函数 g(x)在在x*的某的某 邻域邻域B *=x|x x*|*内连续可微内连续可微,且且 x*=g(x*),|g (x*)|1,则存在正数则存在正数 ,*,由由 x0 B 开开始的迭代收敛始的迭代收敛.该定理表明,若该定理表明,若|g (x*)|1,称数列为称数列为超线性收敛超线性收敛的;的;r=2,称数列为称数列为平方收敛平方收敛的的.收敛阶收敛阶r 的大小刻划了数列的大小刻划了数列 的收敛速度,的收敛速度,r越大,越大,收敛越快收敛越快.nx25定理定理设迭代函数设迭代函数 g(x)在在 x*邻近
14、有邻近有r阶连续导数,且阶连续导数,且,0)(,0)()(),(*)(*)1(*xgxgxgxgxrr则迭代公式则迭代公式 xk+1=g(xk)所产生的迭代数列是所产生的迭代数列是 r阶收敛的阶收敛的.证明:证明:)(1kkxgx rkkrkxxrgxxxgxg*)(!)(.*)*)(*)()(*x0 k0!)(*)(rxgr故故.!)()(lim*)(*1rxgxxxxrrkkk 26 Aitken 加速有加速有 超线性收敛超线性收敛.,0*lim xxxxkkkSteffensen 加速加速有有 r=2,条件是条件是 平方平方 收敛收敛.,1*)(xg 对于对于简单迭代法简单迭代法,若若则
15、有则有 线性收敛线性收敛.,0|*)(|*|*|lim1 xgxxxxkkk,0)(*xg2728原理:原理:将非线性方程线性化将非线性方程线性化 (Taylor 展开展开)设设 xn是是 x*的第的第n个近似值个近似值,将将 f(x)在在 xn 做做Taylor展开展开)()()(0nnnxxxfxfxf )()(*nnnxfxfxx 线性线性/*linear*/xyx*xn)()(1nnnnxfxfxx 只要只要 f C1,每一步迭代都每一步迭代都有有 f (xn)0,而且若而且若 则则 x*就是就是 f 的根的根.*,limxxnn 令令xn+13 牛顿法牛顿法29例例 用牛顿法求方程用
16、牛顿法求方程02010)(3 xxxf的根的根,取取 x0=1.5.解:解:迭代公式为迭代公式为1032010231 nnnnnxxxxx代入初值得:代入初值得:,5945637.1,5970149.121 xx.5945621.1,5945621.143 xx可见牛顿法收敛很快可见牛顿法收敛很快.30定理定理 (收敛的充分条件收敛的充分条件)设)设 f C2a,b,若若(1)f(a)f(b)0;则则Newtons Method产生的序列产生的序列 xk 收敛到收敛到 f(x)在在 a,b 的唯一根的唯一根.有根有根根根唯一唯一产生的序列单调有产生的序列单调有界,保证收敛界,保证收敛.31 (
17、局部收敛性局部收敛性)设)设 f C2a,b,若,若 x*为为 f(x)在在a,b上的根,且上的根,且 f (x*)0,则,则存在存在 x*的的邻域邻域 使得任取初值使得任取初值 Newtons Method产生的序列产生的序列 xk 收敛到收敛到x*,且,且满足满足*)(xB*),(0 xBx *)(2*)()*(*lim21xfxfxxxxkkk 定理定理证明:证明:Newtons Method 事实上是一种特殊的不事实上是一种特殊的不动点迭代其中动点迭代其中 则则,)()()(xfxfxxg 10*)(*)(*)(*)(2xfxfxfxg收敛收敛 32由由 Taylor 展开:展开:2)
18、*(!2)()*)()(*)(0kkkkkxxfxxxfxfxf 2)*()(!2)()()(*kkkkkkxxxffxfxfxx 1 kx)(2)()*(*21kkkkxffxxxx 只要只要 f (x*)0,则令则令 可得结论可得结论.k在在单单根根 附近收敛快附近收敛快再证:再证:.)(2)()()(lim*2*1*xfxfxxxxkkk 33Newtons Method 收敛性依赖于收敛性依赖于x0 的选取的选取.x*x0 x0 x034 当当x*是方程的是方程的m重根时重根时,牛顿迭代法是牛顿迭代法是线性收敛线性收敛的的,且且mmxxxxnnn1|*|*|lim1 ),(*)()(x
19、hxxxfm ,0*)(2 xhm,整数整数则称则称 x*为方程为方程 f(x)=0的的m重根重根.设设35 求重根的改进求重根的改进Newton法法),2,1,0(,)()(1 nxfxfmxxnnnn此时迭代函数此时迭代函数)()()(xfxfmxx 则则.0*)(x 迭代法具有迭代法具有2阶收敛阶收敛,但要知道,但要知道x*的重数的重数m.其中其中m为为 f(x)=0的根的重数的根的重数.36 构造求重根的另一迭代法构造求重根的另一迭代法,)()()(xfxfx 令令则则,)(*)()()(*)()(xhxxxmhxhxxx 故故x*是是 (x)=0的单根的单根.对它用牛顿法,其迭代函数
20、为对它用牛顿法,其迭代函数为 .)()()()()()()()(2xfxfxfxfxfxxxxx 从而可构造迭代法从而可构造迭代法 .)()()()()(21nnnnnnnxfxfxfxfxfxx 它是它是二阶收敛二阶收敛的的.37例例 方程方程 的根的根 是二重根,用是二重根,用上述三种方法求根上述三种方法求根.04424 xx2*x解解 先求出三种方法的迭代公式先求出三种方法的迭代公式(3)方法方法3.4221nnnnxxxx .2221nnnnxxxx .2)2(221 nnnnnxxxxx取初值取初值 x0=1.5,计算结果见下表计算结果见下表(1)牛顿法牛顿法(2)方法方法238三种
21、方法数值结果三种方法数值结果n123nx1x2x3x方法方法(1)方法方法(2)方法方法(3)1.4583333331.4366071431.4254976191.4166666671.4142156861.4142135621.4117647061.4142114381.414213562 计算三步计算三步,方法方法(2)及及(3)均达到均达到10位有效数字位有效数字,而用而用牛顿法只有线性收敛牛顿法只有线性收敛,要达到同样精度需迭代要达到同样精度需迭代30次次.39Matlab函数函数rootsfzerofsolvefminfminsfminu40上机作业:上机作业:求下列方程的非零根求下列方程的非零根 .00918.014006651.05136651.0513ln)(xxxxf41