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

1、1其中其中f (x) 为非线性函数为非线性函数. 如如求求 f (x) = 0 的根的根, 123)(45 xxxxf. 2)ln(sin)(12 xxexfx第八章第八章 非线性方程求根非线性方程求根2上机作业：上机作业：求下列方程的非零根求下列方程的非零根 . 00918. 014006651. 05136651. 0513ln)( xxxxf3例例 若干年以前若干年以前, 美国原子能委员会准备将浓缩的放美国原子能委员会准备将浓缩的放射性废料装入密封的圆桶内沉至海底射性废料装入密封的圆桶内沉至海底. 但是但是, 当时一些当时一些科学家与生态学家都反对这种作法科学家与生态学家都反对这种作法.

2、 科学家用实验测科学家用实验测定出圆桶能够承受的最大撞击速度为定出圆桶能够承受的最大撞击速度为v=12.2 m/s, 如果如果圆桶到达海底时的速度超过这个速度圆桶到达海底时的速度超过这个速度, 将会因撞击海将会因撞击海底而破裂底而破裂, 从而引起严重的核污染从而引起严重的核污染. 然而原子能委员会然而原子能委员会却认为不存在这种可能性却认为不存在这种可能性. 根据圆桶的质量根据圆桶的质量, 体积以及体积以及海水的密度与海底的深度海水的密度与海底的深度, 通过建立数学模型得知圆通过建立数学模型得知圆桶到达海底时的速度桶到达海底时的速度v (m/s)满足如下方程满足如下方程:那么圆桶到达海底时的速

3、度究竟会不会超过那么圆桶到达海底时的速度究竟会不会超过12.2 m/s呢呢? . 088.1240)17. 1261ln(08.223 vv41 对分区间法对分区间法(二分法二分法)原理原理: 若若 f Ca, b，且，且 f (a) f (b) 0，则，则 f 在在(a, b) 上必有一根上必有一根. a, b 称为称为 f (x)=0的的有根区间有根区间.下文中下文中, 设设 x* 是方程是方程 f (x)=0的根的根.5取取,20bax 不妨设不妨设 f (a) 0. 若若 , 0)(0 xf则则;0*xx 若若, 0)(0 xf取取,01xa ;1bb 若若, 0)(0 xf.01xb

4、 取取,1aa 以以1, 1ba作为新的有根区间继续迭代作为新的有根区间继续迭代, 得有根区间序列得有根区间序列.,11 nnbababa 取取2nnnbax 为为*x的第的第n个近似值个近似值. 6abx0 x1ab停机准则停机准则11xxkk 21)(xfk 或或不能保证不能保证 x 的精度的精度x* 2xx*7误差误差 分析：分析：第第0步产生的步产生的20bax 有误差有误差20abx*|x 第第 k 步产生的步产生的 xk 有误差有误差12 kkabx*|x对于给定的精度对于给定的精度 ,可估计二分法所需的步数可估计二分法所需的步数 k ： 12lnlnln21 abkabk简单简单

5、; 对对 f (x) 要求不高要求不高(只要连续即可只要连续即可) .无法求复根及偶重根无法求复根及偶重根 收敛慢收敛慢 8例例1 试用二分法求方程试用二分法求方程02010)(3 xxxf的唯一实根的唯一实根, 要求误差不超过要求误差不超过.105 . 04 解解, 09)1( f, 08)2( f1, 2为有根区间为有根区间;, 0103)( 2 xxff (x)单调增加单调增加, 方程有唯一根方程有唯一根.对分区间次数对分区间次数.288.1312ln)105 . 0ln()12ln(4 n取取 n=14.9计算结果如下表计算结果如下表:nnanbnx)(nxf0 1 2 1.5 1.6

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.5 1.75 1.625 0.54.10f (x) = 0 x = g (x)等价变换等价变换f (x) 的根的根g (x) 的不动点的不动点思思路路从一个初值从一个初值 x0 出发出发, , 计算计算 x1 = g(x0), x2 = g(x1), , xk+1 = g(xk), 若若 收

7、敛收敛, 即存在即存在 x* 使得使得 且且 g 连续连续, , 则则由由 可知可知 x* = g(x* ),即即x* 是是 g 的不动点，也就是的不动点，也就是 f 的根的根. 0kkx*,limxxkk 1lim kkx ,limkkxg 2 迭代法迭代法11例例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显然此

8、迭代序列发散显然此迭代序列发散.12例例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 x61415105 . 0| xx计算得计算得.5945622. 115* xx 13例例2 用简单迭代法求方程用简单迭代法求方程02010)(3 xxxf的根的根, 要求精确到要求

9、精确到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计算得计算得14例例2 用简单迭代法求方程用简单迭代法求方程02010)(3 xxxf的根的根, 要求精确到要求精确到0.5 10-6. 解法四：解法四：,1020)(3xxxf 迭代格式迭代格式:初值初值, 5 . 10 x,10231nnxx ,6625. 1, 5 . 110

10、xx,5961283. 1,5925062. 11514 xx计算得计算得,5945619. 1,5945624. 14847 xx15上例表明上例表明, 对同一方程可构造不同的迭代格式，对同一方程可构造不同的迭代格式，产生的迭代序列收敛性也不同产生的迭代序列收敛性也不同. 迭代法的迭代法的收敛性收敛性与什么有关？与什么有关？ 怎样构造具有怎样构造具有收敛性收敛性的迭代法？的迭代法？16xyy = xxyy = xxyy = xxyy = xx*x*x*x*y=g(x)y=g(x)y=g(x)y=g(x)x0p0 x1p1 x0p0 x1p1 x0p0 x1p1x0p0 x1p117定理定理考

11、虑方程考虑方程 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 k18证明：证明： g(x) 在在a, b上存

12、在不动点？上存在不动点？令令xxgxf )()(bxga )(,0)()( aagaf0)()( bbgbf)(xf有根有根 不动点唯一？不动点唯一？反证：若不然，设还有反证：若不然，设还有 ，则，则)(xgx ),*( )()(*)(xxgxgxg xx*在在和和 之间之间 *xx0)(1)( gxx*而而xxg*1| )(| 19 当当k 时，时， xk 收敛到收敛到 x* ？ |*|kxx|*| )(| )(*)(|111 kkkxxgxgxg0|*|.|*|01 xxLxxLkk ?|11|*|1kkkxxLxx |*|*|*|*|11kkkkkkxxLxxxxxxxx 可用可用 来来

13、控制收敛精度控制收敛精度|1kkxx 20?|1|*|01xxLLxxkk |.| )(| )()(|011111xxLxxLxxgxgxgxxkkkkkkkkkk ?*lim1xgxxxxkkk *)(*)*)(lim*lim1xgxxxxgxxxxkkkkkkk L 越越 收敛越收敛越快快小小21例例2 用简单迭代法求方程用简单迭代法求方程02010)(3 xxxf的根的根, 要求精确到六位小数要求精确到六位小数. 解法一：解法一：2011)(3 xxxg迭代函数迭代函数14113)( 2 xxg 解法二：解法二：1020)(2 xxg迭代函数迭代函数, 11180)10(40| )( |

14、222 xxxg对对,2 , 1 x21120)(14201 xg故迭代法收敛故迭代法收敛. 22局部收敛定理局部收敛定理如果函数如果函数 g (x) 在在x* 的某的某 邻域邻域B * = x | | x x* | *内连续可微，且内连续可微，且 x*= g(x*)， | g (x*) | 1，则存在正数，则存在正数 ， *，由，由 x0 B 开开始的迭代收敛始的迭代收敛.该定理表明，若该定理表明，若| g (x*) | 1, 称数列为称数列为超线性收敛超线性收敛的；的；r =2, 称数列为称数列为平方收敛平方收敛的的.收敛阶收敛阶r 的大小刻划了数列的大小刻划了数列 的收敛速度，的收敛速度

15、，r越大，越大，收敛越快收敛越快. nx27定理定理设迭代函数设迭代函数 g(x)在在 x*邻近有邻近有r阶连续导数，且阶连续导数，且, 0)(, 0)()( ),(*)(*)1(* xgxgxgxgxrr则迭代公式则迭代公式 xk+1=g(xk) 所产生的迭代数列是所产生的迭代数列是 r阶收敛的阶收敛的.证明：证明：)(1kkxgx rkkrkxxrgxxxgxg*)(!)(.*)*)(*)()( *x0 k0!)(*)( rxgr故故.!)()(lim*)(*1rxgxxxxrrkkk 28 Aitken 加速有加速有 超线性收敛超线性收敛 .,0*lim xxxxkkkSteffense

16、n 加速加速有有 r = 2，条件是，条件是 平方平方 收敛收敛 ., 1*)( xg 对于对于简单迭代法简单迭代法, 若若则有则有 线性收敛线性收敛., 0|*)(|*|*|lim1 xgxxxxkkk, 0)( * xg2930原理：原理：将非线性方程线性化将非线性方程线性化 ( Taylor 展开展开 )设设 xn是是 x* 的第的第n个近似值个近似值, 将将 f (x)在在 xn 做做Taylor展开展开)()()(0nnnxxxfxfxf )()(*nnnxfxfxx 线性线性 /* linear */xyx*xn)()(1nnnnxfxfxx 只要只要 f C1，每一步迭代都，每一

17、步迭代都有有 f ( xn ) 0， 而且若而且若 则则 x*就是就是 f 的根的根.*,limxxnn 令令xn+13 牛顿法牛顿法31例例 用牛顿法求方程用牛顿法求方程02010)(3 xxxf的根的根, 取取 x0=1.5.解：解： 迭代公式为迭代公式为1032010231 nnnnnxxxxx代入初值得：代入初值得：,5945637. 1,5970149. 121 xx.5945621. 1,5945621. 143 xx可见牛顿法收敛很快可见牛顿法收敛很快.32定理定理 （收敛的充分条件收敛的充分条件）设）设 f C2a, b，若，若(1) f (a) f (b) 0；则则Newto

18、ns Method产生的序列产生的序列 xk 收敛到收敛到 f (x) 在在 a, b 的唯一根的唯一根.有根有根根唯一根唯一产生的序列单调有产生的序列单调有界，保证收敛界，保证收敛.33 （局部收敛性局部收敛性）设）设 f C2a, b，若，若 x* 为为 f (x) 在在a, b上的根，且上的根，且 f (x*) 0，则存在，则存在 x* 的邻域的邻域 使得任取初值使得任取初值 Newtons Method产生的序列产生的序列 xk 收敛到收敛到x*，且满足，且满足*)(xB *),(0 xBx *)(2*)()*(*lim21xfxfxxxxkkk 定理定理证明：证明：Newtons M

19、ethod 事实上是一种特殊的不事实上是一种特殊的不动点迭代其中动点迭代其中 则则,)()()(xfxfxxg 10*)(*)(*)(*)(2xfxfxfxg收敛收敛 34由由 Taylor 展开：展开：2)*(!2)()*)()(*)(0kkkkkxxfxxxfxfxf 2)*()(! 2)()()(*kkkkkkxxxffxfxfxx 1 kx)(2)()*(*21kkkkxffxxxx 只要只要 f (x*) 0, 则令则令 可得结论可得结论. k在在单根单根 附近收敛快附近收敛快再证：再证：.)( 2)( )()(lim*2*1*xfxfxxxxkkk 35Newtons Method

20、 收敛性依赖于收敛性依赖于x0 的选取的选取.x*x0 x0 x036 当当x*是方程的是方程的m重根时重根时, 牛顿迭代法是牛顿迭代法是线性收敛线性收敛的的, 且且mmxxxxnnn1|*|*|lim1 ),(*)()(xhxxxfm , 0*)(2 xhm，整数整数则称则称 x*为方程为方程 f (x)=0的的m重根重根. 设设37 求重根的改进求重根的改进Newton法法), 2 , 1 , 0(,)( )(1 nxfxfmxxnnnn此时迭代函数此时迭代函数)( )()(xfxfmxx 则则. 0*)( x 迭代法具有迭代法具有2阶收敛阶收敛，但要知道，但要知道x*的重数的重数m.其中

21、其中m为为 f (x)=0的根的重数的根的重数.38 构造求重根的另一迭代法构造求重根的另一迭代法,)( )()(xfxfx 令令则则,)( *)()()(*)()(xhxxxmhxhxxx 故故x*是是 (x)=0的单根的单根. 对它用牛顿法，其迭代函数为对它用牛顿法，其迭代函数为 .)( )()( )( )()( )()(2xfxfxfxfxfxxxxx 从而可构造迭代法从而可构造迭代法 .)( )()( )( )(21nnnnnnnxfxfxfxfxfxx 它是它是二阶收敛二阶收敛的的.39例例 方程方程 的根的根 是二重根，用是二重根，用上述三种方法求根上述三种方法求根.04424 x

22、x2* x解解 先求出三种方法的迭代公式先求出三种方法的迭代公式(3) 方法方法3.4221nnnnxxxx .2221nnnnxxxx .2)2(221 nnnnnxxxxx取初值取初值 x0=1.5, 计算结果见下表计算结果见下表(1) 牛顿法牛顿法(2) 方法方法240三种方法数值结果三种方法数值结果n123nx1x2x3x方法方法(1)方法方法(2)方法方法(3)1.4583333331.4366071431.4254976191.4166666671.4142156861.4142135621.4117647061.4142114381.414213562 计算三步计算三步, 方法方

23、法(2)及及(3)均达到均达到10位有效数字位有效数字, 而用而用牛顿法只有线性收敛牛顿法只有线性收敛, 要达到同样精度需迭代要达到同样精度需迭代30次次.41 弦截法弦截法(割线法割线法, 线性插值法线性插值法) Newtons Method 一步要计算一步要计算 f 和和 f ，相当于，相当于2个函数值，比较费时个函数值，比较费时. 现用现用 f 的值近似的值近似 f ，可少算，可少算一个函数值一个函数值. 在在Newton迭代法中用差商迭代法中用差商 代替导数代替导数11)()( nnnnxxxfxf)( nxf得到迭代公式得到迭代公式,.)3, 2, 1(,)()()(111 nxfx

24、fxxxfxxnnnnnnn弦截法弦截法 须两个初始点须两个初始点x0, x1, 通常可取有根区间的两个端点通常可取有根区间的两个端点.4243过曲线上两点过曲线上两点 的直线为的直线为)(,(),(,(11nnnnxfxxfx )()()()(11nnnnnnxxxxxfxfxfy 它与它与x轴的交点为轴的交点为)()()(11 nnnnnnxfxfxxxfxx1 nx以割线近似曲线，故弦截法又称为以割线近似曲线，故弦截法又称为割线法割线法.44 设设 f (x)在在 x*邻近二阶连续可导，且邻近二阶连续可导，且 f (x*)=0, f (x*) 0, 则存在则存在 0，当，当x0 , x1

25、 x* ，x*+ 时，时，由弦截法产生的数列由弦截法产生的数列xn收敛于收敛于x*, 且收敛阶为且收敛阶为1.618. (方程方程 的正根的正根)定理定理012 xx45例例 用弦截法求下列方程的根用弦截法求下列方程的根.02010)(3 xxxf解解 因为因为 f (1.5)0, 1.5, 2为有根区间为有根区间. 取取. 2, 5 . 110 xx按弦截法计算公式求按弦截法计算公式求, 结果如下结果如下,5844156. 12 x,5934795. 13 x,5945651. 14 x,5945621. 15 x 此计算结果表明此计算结果表明, 迭迭代代5次所得近似解精确次所得近似解精确到

26、到8位有效数字位有效数字. 它的收它的收敛速度比敛速度比Newton法慢法慢.464 抛物线法抛物线法(Mller法）法）基本思想基本思想: 过过)(,(),(,(),(,(1122nnnnnnxfxxfxxfx 作一抛物线作一抛物线 P2(x), 该抛物线与该抛物线与x轴的一个交点轴的一个交点 xn+1作为根作为根x*的下一个近似的下一个近似.4748y(x)xSecant linex1Fit a parabola (quadratic) to exact curvex2x3Parabola49过过)(,(),(,(),(,(1122nnnnnnxfxxfxxfx )(,)(,)()(121

27、12 nnnnnnnnnxxxxxxxfxxxxfxfxP或或,)()()(22nnnnncxxbxxaxP 其中其中,21 nnnnxxxfa)(,1211 nnnnnnnnxxxxxfxxfb)(nnxfc 的抛物线的抛物线 P2(x)50该抛物线与该抛物线与x轴的交点为，轴的交点为，nnnnnnnnnnnnncabbcxacabbxx4224221 在在xn , xn 1 , xn 2三个近似根中三个近似根中, 自然假定自然假定xn更接近所更接近所求的根求的根x*, 这时为了保证精度，选上式中较接近这时为了保证精度，选上式中较接近xn的的一个值作为新的近似根一个值作为新的近似根. 为此，

28、只要取根式前的符为此，只要取根式前的符号与号与 bn的符号相同的符号相同, 即即 0,420,42221nnnnnnnnnnnnnnnbcabbcxbcabbcxx抛物线法抛物线法 Mller法法 二次插值法二次插值法51y(x)xx1Two roots for quadratic function pick the one closest to the previous estimate x2x3Two Roots52例例 用抛物线法求下列方程的根用抛物线法求下列方程的根.02010)(3 xxxf解：解：取取 x0=1.5, x1=1.75, x2=2.0, 则则. 8,859375. 2

29、,625. 1210 fff按抛物线法计算公式按抛物线法计算公式, 8)2(,875.21)75. 12(75. 1, 2,25. 55 . 1,75. 1, 2 fcafbfa5949003. 1825. 54)875.21(875.2182223 x,5945609. 14 x,5945621. 15 x.5945621. 16 x53 在一定条件下可以证明在一定条件下可以证明, 对于抛物线法对于抛物线法, 收敛阶收敛阶为为 p=1.840 (是方程是方程 x3x2x1=0的根的根), 收敛速收敛速度比弦截法快但比度比弦截法快但比Newton法慢法慢. 从抛物线法的计算公式可以看出，即使从

30、抛物线法的计算公式可以看出，即使xn , xn 1 , xn 2均为实数，均为实数，xn+1也可以是复数，所以抛物线法可也可以是复数，所以抛物线法可适用于求多项式的实根和复根适用于求多项式的实根和复根.545 解非线性方程组的牛顿迭代法解非线性方程组的牛顿迭代法考虑方程组考虑方程组 . 0),(, 0),(, 0),(21212211nnnnxxxfxxxfxxxf其中其中f1 , f2 , , fn均为均为(x1, x2, ., xn)的的n元函数元函数. 当当n1，且，且 fi ( i=1, 2, , n)中至少有一个是自变量中至少有一个是自变量xi (i=1, 2, , n)的非线性函数

31、时的非线性函数时, 则称方程组为则称方程组为非线非线性方程组性方程组.55 非线性方程组的求根问题是前面介绍的方程非线性方程组的求根问题是前面介绍的方程 ( n=1)求根的直接推广求根的直接推广. )()(2)(1)(knkkkxxxx将方程组的每个方程将方程组的每个方程 fi (x)在在 x(k)用多元函数的用多元函数的Taylor展开展开, 并取线性部分并取线性部分, 得到近似线性方程组得到近似线性方程组, 此方程组的解作为下一个近似解此方程组的解作为下一个近似解x(k+1). 设已给出方程组的一个近似根设已给出方程组的一个近似根56)(),()(),(),(),(byybafaxxbaf

32、bafyxf 二元函数二元函数 f (x, y)在在(a, b)点用线性函数近似点用线性函数近似57两个方程两个未知数的非线性方程组两个方程两个未知数的非线性方程组 . 0),(, 0),(yxgyxf精确解精确解*)*,(yx设设(xk, yk) 为为(x*, y*)的第的第 k 个近似个近似, 将将 f (x, y), g(x, y)在在(xk, yk)点处用线性函数近似点处用线性函数近似 ),(),(00yxgyxf )(),()(),(),()(),()(),(),(kkkkkkkkkkkkkkkkyyyyxgxxxyxgyxgyyyyxfxxxyxfyxf58即即 ),(),(),(

33、),(),(),(kkkkkkkkkkkkkkyxgyxfyyxxyyxgxyxgyyxfxyxf ),(),(1),(kkkkkkkkyxgyxfyxygxgyfxfyxyx 11kkyx59,),(),(),( yxgyxfyxF ygxgyfxfyxF),( 记记则则),(),( 111kkkkkkkkyxFyxFyxyx 60)(),()(),()(),(),()()()(2)(1)(222)()(2)(1)(111)()(2)(1)()(2)(1knnnknkkikknkkikknkkiknkkixxxxxxfxxxxxxfxxxxxxfxxxf 即即 njkjjjkikiixxxx

34、fxfxf1)()()()()()()(将将n元函数元函数 fi (x1, x2 , , xn)在在 x(k)点用线性函数近似点用线性函数近似 ),(21nixxxfn个方程个方程n个未知数的非线性方程组个未知数的非线性方程组61将方程组的每个方程将方程组的每个方程 fi (x)在在 x(k)点用点用线性函数近线性函数近似似. 非线性方程组用下述线性方程组近似代替非线性方程组用下述线性方程组近似代替 . 0)()()(, 0)()()(, 0)()()(1)()()(1)()(2)(21)()(1)(1njkjjjknknnjkjjjkknjkjjjkkxxxxfxfxxxxfxfxxxxfxf62写成矩阵形式即为写成矩阵形式即为)()()()()()()()()()()()()()(21)()(22)(11212221212111kkxxnknnkkxxnnnnnnxfxfxfxxxxxxxxfxxfxxfxxfxxfxxfxxfxxfxxf 63记记,)()()()(21 xfxfxfxF