第二章 非线性方程(组)的数值解法1

1、第二章第二章 非线性方程（组）的数值解法非线性方程（组）的数值解法 /*Numerical Solutions of Nonlinear Equations（Group） */历史背景历史背景 代数方程的求根问题是一个古老的数学问题。理论上，代数方程的求根问题是一个古老的数学问题。理论上， 次代数方程在复数域内一定有次代数方程在复数域内一定有 个根个根( (考虑重数考虑重数) )。早在。早在1616世纪世纪就找到了三次、四次方程的求根公式，但直到就找到了三次、四次方程的求根公式，但直到1919世纪才证明大世纪才证明大于等于于等于5 5次的一般代数方程式不能用代数公式求解，而对于超次的一般代数方

2、程式不能用代数公式求解，而对于超越方程就复杂的多，如果有解，其解可能是一个或几个，也可越方程就复杂的多，如果有解，其解可能是一个或几个，也可能是无穷多个。一般也不存在根的解析表达式。因此需要研究能是无穷多个。一般也不存在根的解析表达式。因此需要研究数值方法求得满足一定精度要求的根的近似解。数值方法求得满足一定精度要求的根的近似解。 nn求方程求方程 几何意义几何意义0( )f x 基本定理基本定理2 1 .Th 如果函数如果函数 在在 上连续，且上连续，且 ，则至少有一个数则至少有一个数 使得使得 ，若同时，若同时 的一阶的一阶导数导数 在在 内存在且保持定号，即内存在且保持定号，即 ( (或

3、或 ) )则这样的则这样的 在在 内唯一。内唯一。 )(xf,ba0)()(bfaf0)(f)(xf 0( )fx ,ba)(xf,ba0( )fx abx*( )yf x oxy1 1 二分法二分法 /* Bisection Method */原理：原理：若若 f Ca, b，且，且 f (a) f (b) 0，则，则 f 在在 (a, b) 上必上必有一根。有一根。基本思想：基本思想：逐步将区间分半，通过判别区间端点函数值的符号，逐步将区间分半，通过判别区间端点函数值的符号，进一步搜索有根区间，将有根区间缩小到充分小，从而求进一步搜索有根区间，将有根区间缩小到充分小，从而求出满足给定精度的

4、根出满足给定精度的根 的近似值。的近似值。x )(xfy aboxy x 21bax 1b 2112xba 2a 3a 1a32xba 2b3b11,a b22,a b33,a b以此类推以此类推终止法则？终止法则？abx1x2abWhen to stop?11xxkk 2()kf x 或或不能保证不能保证 x 的精的精度度x* 2xx* 11111 222, ,kkkkkabxxxbak 且3、 12lnlnlnbak 由二分法的过程可知：由二分法的过程可知：4、对分次数的计算公式：对分次数的计算公式： 11,kka ba bab 0,kkkkf af bxab 1、 111122kkkkk

5、bababa 2、 1112kkxxba 令令误差误差 分析分析2 2 .Th解解：211 510 ,.;ab，12ln()lnlnban 21 5 11012ln( .)lnln 4.645n例例1 1：用二分法求方程用二分法求方程 在区间在区间 上的上的根，误差限为根，误差限为 ，问至少需对分多少次？，问至少需对分多少次？310 xx 1 1 5 , . 210 简单简单; 对对f (x) 要求不高要求不高(只要连续即可只要连续即可) .无法求复根及无法求复根及偶重根偶重根收敛慢收敛慢 用二分法求根，最好先给出用二分法求根，最好先给出 f (x) 草图以确定根的大草图以确定根的大概位置。或

6、用搜索程序，将概位置。或用搜索程序，将a, b分为若干小区间，对每一分为若干小区间，对每一个满足个满足 f (ak)f (bk) 0 的区间调用二分法程序，可找出区的区间调用二分法程序，可找出区间间a, b内的多个根，且不必要求内的多个根，且不必要求 f (a)f (b) 0 。优点优点缺点缺点2 迭代法的理论迭代法的理论 /* Theory of Iteration Method*/f (x) = 0 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 kkkkxgx limlim1看起来很简单，令人看起来很简单，令人有点不相信，那么问有点不相信，那么问题是什么呢？题是什么呢？谁告诉你这种方法谁告诉你这种方法是收敛的呢？是收敛的呢？f (x) 的根的根x g (x) 的不动点的不动点x 10 1 2(), , ,(*)kkxg xk 一、不动点迭代一、不动点迭代 /*Fixed-Point Iteration*/xyy = x

8、xyy = xxyy = xxyy = xx*x*x*x*y=g(x)y=g(x)y=g(x)y=g(x)x0p0 x1p1 x0p0 x1p1 x0p0 x1p1x0p0 x1p1几何意义几何意义例例2： 已知方程已知方程 在在 上有一个根（正根）上有一个根（正根）324100 xx1 2 , 可以选取可以选取5 5种迭代格式：种迭代格式：1 1、32410 xxxx 即即32410( )g xxxx 2 2、23410 xx 1321102xx 1321102g xx即即3 3、即即2104xxx 12104xxx 12104g xxx4 4、即即12104xx 12104g xx 5 5

9、、即即xxxxxx8310422332241038( )xxg xxxx 取取01 5 .x 计算结果如下：计算结果如下：123840875673246972010275 10.xxxx 法法1 11234451113484013673813649613652613751713652251365230013.xxxxxxx 法法4 412123081650299691865086.( .)xxx 法法3 3123445112912869514025413454613751713751713751713651378211365230013.xxxxxxxx 法法2 212341373331365

10、2613652300141365230013.xxxx 法法5 5Lipschitz条条件件2 3 .Th考虑方程考虑方程 x = g(x), g(x) Ca, b, 若若( I ) 当当 x a, b 时，时， g(x) a, b；( II ) 0 L 1 使得使得 对对 x a, b 成立。成立。则任取则任取 x0 a, b，由，由 xk+1 = g(xk) 得到的序列得到的序列 收收敛于敛于g(x) 在在a, b上的唯一不动点。并且有误差估计式：上的唯一不动点。并且有误差估计式： 0kkx|11|*|1kkkxxLxx 101|*|kkLxxxxL ( k = 1, 2, )且存在极限且

11、存在极限 *lim1xgxxxxkkk 1( )g xL ( )g x 连续时连续时证明：证明： g(x) 在在a, b上存在不动点？上存在不动点？令令xxgxf )()(bxga )(,0)()( aagaf0)()( bbgbf)(xf有根有根 不动点唯一？不动点唯一？反证：若不然，设还有反证：若不然，设还有 ，则，则)(xgx ),*( )()(*)(xxgxgxg xx*在在和和之间。之间。 *xx0)(1)( gxx*而而xxg*1| )(| 当当k 时，时， xk 收敛到收敛到 x* ？ |*|kxx|*| )(| )(*)(|111 kkkxxgxgxg0|*|.|*|01 xx

12、LxxLkk L 越越 收敛越快收敛越快可用可用 来来控制收敛精度控制收敛精度|1kkxx ?|11|*|1kkkxxLxx |*|*|*|*|11kkkkkkxxLxxxxxxxx ?|1|*|01xxLLxxkk |.| )(| )()(|011111xxLxxLxxgxgxgxxkkkkkkkkkk ?*lim1xgxxxxkkk *)(*)*)(lim*lim1xgxxxxgxxxxkkkkkkk 小小定理条件中的定理条件中的( II ) ，可改为，可改为g (x) 在在a, b 满足满足Lipschitz条件条件,定理结论仍然成立。定理结论仍然成立。 算法算法: : 不动点迭代不动点

13、迭代给定初始近似值给定初始近似值 x0 ，求，求x = g(x) 的解的解. .输入输入: : 初始近似值初始近似值 x0; ; 容许误差容许误差 TOL; ; 最大迭代次数最大迭代次数 Nmax.输出输出: 近似解近似解 x 或失败信息或失败信息.Step 1 Set i = 1;Step 2 While ( i Nmax) do steps 3-6Step 3 Set x = g(x0); /* 计算计算 xi */Step 4 If | x x0 | TOL then Output (x); /* 成功成功*/STOP;Step 5 Set i +;Step 6 Set x0 = x ;

14、 /* 更新更新 x0 */Step 7 Output (The method failed after Nmax iterations); /*不成功不成功 */STOP.当当 x 很大时，此很大时，此处可改为处可改为TOLxxx 0二、局部收敛性二、局部收敛性 /*Local Convergence*/（局部收敛性局部收敛性 ）2 1 .Def(),N xxx 若存在若存在 的不动点的不动点 的一个闭邻域的一个闭邻域 对任意的对任意的 ，由迭代法，由迭代法 产生的序列产生的序列 均收敛于均收敛于 ，则称该迭代法局部收敛。，则称该迭代法局部收敛。 gx 0 0()xN x kxx 10 1(

15、), ,kkxg xk 2 4 .Th 设设 为为 的不动点，的不动点， 在在 的某邻域连续，的某邻域连续， 且且 ，则迭代法，则迭代法( (* *) )局部收敛。局部收敛。 x g gx x 1gxL 证明：证明：( )( )()( )()g xxg xg xgxxL xx 因为因为 在在 的某邻域连续，的某邻域连续， gx x 11( )()g xLg xL (),N xxx存在邻域存在邻域( )xg xx()xN x 即对即对0()xN x 则由定理则由定理2.32.3，迭代法，迭代法( (* *) )对对 收敛，即局部收敛收敛，即局部收敛. .注注 11()( )( )()()g xL

16、g xg xg xg xL 例例3 3：已知方程已知方程 在在1.51.5附近有根，把方程写成三附近有根，把方程写成三种不同的等价形式种不同的等价形式(1) (1) 对应迭代格式对应迭代格式 ；(2) (2) 对应迭代格式对应迭代格式 ；(3) (3) 对应对应迭代格式迭代格式 ; ;判断迭代格式在判断迭代格式在 的收敛性，选的收敛性，选一种一种收敛格式收敛格式计算，精确到小数点后计算，精确到小数点后第二位第二位。 321 0 xx 211xx 1211nnxx 321xx 2311nnxx 211xx 111nnxx 01 5 .x 解：解：（1 1） ， ，迭代格式收敛；，迭代格式收敛；

17、32( )g xx 321505926 115( . ).g （2 2） ， ，迭代格式收敛；，迭代格式收敛；223213( )()xg xx 1 50 45581( . ).g （3 3） ， ，迭代格式发散。，迭代格式发散。3121( )()g xx 1 521( . )g kkx选择选择(2)(2)计算计算 0 1 2 3 40 1 2 3 4 1.5 1.481 1.473 1.469 1.467 1.5 1.481 1.473 1.469 1.467（收敛阶（收敛阶/*the order of Convergence*/) )2 2 .Def设序列设序列 收敛到收敛到 ， ，若存在实

18、数，若存在实数 及常及常数数 ，使，使 则称序列则称序列 是是 阶收敛的，阶收敛的， 称为渐近误差常数。当称为渐近误差常数。当 且且 时，时， 称为线称为线性收敛，性收敛， 为超线性收敛，为超线性收敛， 时为平方或二次收敛时为平方或二次收敛. . kxx kkexx 1p 1limkpkkece 0c kxpc1p 01c kx1p 2p 的大小反映了迭代法收敛的快慢，是收敛速度的大小反映了迭代法收敛的快慢，是收敛速度 的一的一 种度量种度量; （2）设迭代函数设迭代函数 满足收敛定理的条件，则产生的序满足收敛定理的条件，则产生的序列满足列满足 ，如果在，如果在 或或 的邻域有的邻域有 若取若

19、取 ，必有，必有 ，此时有，此时有p( )g xlimkkxx , a bx 0( )g x 0 xx 0 1 2(, ,)kxxk 11()()( )kkkkexxg xg xge 10lim()kkkeg xe 2 5 .Th 设迭代法的迭代函数设迭代法的迭代函数 的高阶导数的高阶导数 在不在不 动点动点 的邻域里连续，则式（的邻域里连续，则式（* *）是）是 阶收敛的充要条件阶收敛的充要条件是是 且且 x g1()( )()pgxp p01 210( )()(),(), ,()lpg xxgxlpgx110()lim()!pkpkkegxep 证明：证明：由由Taylor公式：公式：充分

20、性充分性11111()()()()()()()()( )()()!kkppppkkg xg xg xxxgxxxgxxpp kxx 介介于于、之之间间11()( )()!ppkkxxgxxp 110()lim()!pkpkkegxep 取极限得取极限得必要性必要性设迭代式（设迭代式（* *）是）是 阶收敛的，则有阶收敛的，则有 limkkxx p即即0limkke 且且()xg x （反证法反证法）设）设01 21( )(), ,lgxlp 不成立不成立则存在最小正整数则存在最小正整数 ，0()pp 满足满足0001 210()( )(), ,()plgxlpgx 情形一情形一01pp情形二情

21、形二01pp由充分性证明知由充分性证明知，迭代式（，迭代式（*）是）是 阶收敛的阶收敛的0p即即0010011()lim()()()!pkpkkegxpppe 而而的极限不存在的极限不存在00111kkppppkkkeeeee 与与 阶收敛矛盾阶收敛矛盾p证明方法与情形一类似证明方法与情形一类似（自己练习）（自己练习）迭代步数的比较，见教材迭代步数的比较，见教材P22 （2）本节结论可以推广到求方程的复数根（本节结论可以推广到求方程的复数根（ 是复数）。是复数）。0 x一、一、使用两个迭代值的组合方法：使用两个迭代值的组合方法：3 迭代收敛的加速方法迭代收敛的加速方法 /* Accelerat

22、ing Method*/本节讨论本节讨论迭代法加速收敛问题，常用于迭代法加速收敛问题，常用于线性收敛线性收敛迭代法迭代法 将将 x = g(x) 等价地改造为等价地改造为1 ()( )xg xx 当当 和和 时，有时，有0 1 11( ),xg xx 相应的迭代公式为相应的迭代公式为 110 1 21 (), , ,kkkxg xxk 或者或者 10 1 21() (), , ,kkkkxg xg xxk 选取特殊的选取特殊的 ，有，有可能可能使迭代使迭代加速加速。 xyy = xy = g(x)x*如：如：1 迭代公式为迭代公式为 110 1 22 (), , ,kkkxg xxk kx()

23、kg x几何意义几何意义如图示如图示注：注： (1)(1)这种迭代这种迭代对对原迭代公式原迭代公式( (* *) )的的各近似值在根各近似值在根 的的两侧往复两侧往复地趋于地趋于 时较为有效时较为有效；x x 1kx 中中点点(2)(2)只有只有01( )g xL 且且 较大时，加速效果才明显。较大时，加速效果才明显。L又如：又如：()g x 新的迭代函数为新的迭代函数为 11( ) ( )() ()g xg xg xxg x 当当1()g x 时时0()g x 根据定理根据定理2.32.3知，迭代法至少是知，迭代法至少是二二阶的阶的 但由于但由于 不知道不知道，故，故 也也得不到得不到，因此

24、将取作，因此将取作 的的近近似值似值，即，即 x ()g x ()g x ()cg x 从而有从而有 10 1 21()( (), , ,kkkkcxg xg xxkc 11( )( )xg xxg x 二、二、Steffensen( (斯蒂芬森斯蒂芬森) )加速迭代法加速迭代法：（：（三个三个迭代值组合）迭代值组合）xyy = xy = g(x)x*x 21000122()xxxxxxx x00p3p1p1x2x1P从初值从初值 出发，计算出出发，计算出0 x1021(),()xg xxg x在曲线在曲线 上得到上得到两个点两个点 ( )yg x 001112(,),(,)P xxP x x

25、用直线连接用直线连接 、 两点它两点它与与 的交点设为的交点设为 0Pyx 3P3P点的坐标为点的坐标为 ( , )x x20210122x xxxxxx 121010 xxxxxxxx 将将 视为视为新的初值新的初值，重复上述步骤，重复上述步骤 x一般地一般地， 由由 组合得到迭代式组合得到迭代式121,(),()kkkkkxxg xxg x222111222( () ()()( ()kkkkkkkkkkkkkx xxx g g xg xxxxxxg xg g x 21121222()( ()( ()()kkkkkkkkkkkkkxxxxxxxg xxxg g xg xx 或者或者这个方法称

26、为艾特肯这个方法称为艾特肯( (Aitken) )加速收敛方法加速收敛方法 若令若令 0 1 2(),(), , ,kkkkyg xzg yk则得到所谓的斯蒂芬森则得到所谓的斯蒂芬森( (Steffensen) )迭代法：迭代法： 210 1 22(),()(), , ,kkkkkkkkkkkyg xzg yyxxxkzyx Steffensen迭代法的优点：迭代法的优点： 可以改进收敛速度，有时也能把可以改进收敛速度，有时也能把不收敛不收敛的迭的迭代法改进为代法改进为收敛收敛的二阶方法的二阶方法 例例4： 已知方程已知方程 在在 上有一个根（正根）上有一个根（正根）324100 xx1 2

27、, 可以选取可以选取5 5种迭代格式：种迭代格式：1 1、32410 xxxx 即即32410( )g xxxx 2 2、23410 xx 1321102xx 1321102g xx即即3 3、即即2104xxx 12104xxx 12104g xxx显示计算结果显示计算结果2 6 .Th 设不动点迭代设不动点迭代 的迭代函数的迭代函数 在其不动点在其不动点 的某邻域内具有二阶连续导数，的某邻域内具有二阶连续导数， 则斯蒂芬森则斯蒂芬森( (Steffensen) )的迭代技术是二阶收敛的，而的迭代技术是二阶收敛的，而 且其极限仍为且其极限仍为 。 10()g xAA 且且x 1()kkxg x ( )g xx 证明：证明：设斯蒂芬森设斯蒂芬森( (Steffensen) )的迭代为的迭代为1()kkxx 22222()()()()()()()()()()()()xg g xg xxg g xg xxg xxxg g xg xxg xxxg g xg xg xx 其中其中首先证明有首先证明有 相同的不动点相同的不动点 ( )( )g xx 与与()xx 设设220 ()() ( ()()g xxxxg g xg xx 则则()xg x 反之反之，设，设()xg x 22()lim()lim ()()xxxxg xxxxg g xg xx 222()()()lim()()xxx