数值分析课件第二章非线性方程的数值解法1

1、第二章第二章 非线性方程的数值解法非线性方程的数值解法 /* numerical solutions of nonlinear equations*/本章主要内容：本章主要内容：1 1、二分法、二分法2 2、不动点迭代的构造及其收敛性判定、不动点迭代的构造及其收敛性判定（重点）（重点）3 3、newton和和steffensen迭代迭代4 4、弦割法与抛物线法、弦割法与抛物线法历史背景历史背景 代数方程的求根问题是一个古老的数学问题。理论上，代数方程的求根问题是一个古老的数学问题。理论上， 次代数方程在复数域内一定有次代数方程在复数域内一定有 个根个根( (考虑重数考虑重数) )。早在。早在1

2、616世纪世纪就找到了三次、四次方程的求根公式，但直到就找到了三次、四次方程的求根公式，但直到1919世纪才证明大世纪才证明大于等于于等于5 5次的一般代数方程式不能用代数公式求解，而对于超次的一般代数方程式不能用代数公式求解，而对于超越方程就复杂的多，如果有解，其解可能是一个或几个，也可越方程就复杂的多，如果有解，其解可能是一个或几个，也可能是无穷多个。一般也不存在根的解析表达式。因此需要研究能是无穷多个。一般也不存在根的解析表达式。因此需要研究数值方法求得满足一定精度要求的根的近似解。数值方法求得满足一定精度要求的根的近似解。 nn求方程求方程 几何意义几何意义0( )f x 基本定理基本

3、定理2 1 .th 如果函数如果函数 在在 上连续，且上连续，且则至少有一个数则至少有一个数 使得使得 ，若同时，若同时 的一阶的一阶导数导数 在在 内存在且保持定号，即内存在且保持定号，即 ( (或或 ) )则这样的则这样的 在在 内唯一。内唯一。 ( )f x , a b( ) ( )0f a f b ( )0f ( )fx ( )0fx , a b( )f x , a b0( )fx abx*( )yf x oxy1 1 二分法二分法 /* bisection method */原理：原理：若若 f ca, b，且，且 f (a) f (b) 0，则，则 f 在在 (a, b) 上至上至

4、少有一实根。少有一实根。基本思想：基本思想：逐步将区间分半，通过判别区间端点函数值的符号，逐步将区间分半，通过判别区间端点函数值的符号，进一步搜索有根区间，将有根区间缩小到充分小，从而求进一步搜索有根区间，将有根区间缩小到充分小，从而求 出满足给定精度的根出满足给定精度的根 的近似值。的近似值。x 终止法则？终止法则？abx1x2abwhen to stop?11xxkk 2()kf x 或或不能保证不能保证 x 的精度的精度x* 二分法算法二分法算法给定区间给定区间a,b ，求，求f(x)=0 在该区间上的根在该区间上的根x. .输入输入: : a和和b; ; 容许误差容许误差 tol; ;

5、 最大对分次数最大对分次数 nmax.输出输出: 近似根近似根 x.step 1 set k = 1;step 2 compute x=f(a+b)/2);step 3 while ( k nmax) do steps 4-6 step 4 if |x| tol , stop; output the solution x. step 5 if x*f(a)0 , set b=x; else set a=x; step 6 set k=k+1; compute x=f(a+b)/2);go to step 3 ;step 7 output the solution of equation: x;

6、 stop. 11111 222, ,kkkkkabxxxbak 且3、 12lnlnlnbak 由二分法的过程可知：由二分法的过程可知：4、对分次数的计算公式：对分次数的计算公式： 11,kka ba bab 0,kkkkf af bxab 1、 111122kkkkkbababa 2、 1112kkxxba 令令解解：211 510 ,.;ab，12ln()lnlnban 21 5 11012ln( .)lnln 4.645n例例1 1：用二分法求方程用二分法求方程 在区间在区间 上的上的根，误差限为根，误差限为 ，问至少需对分多少次？，问至少需对分多少次？310 xx 1 1 5 , .

7、 210 简单简单; 对对f (x) 要求不高要求不高(只要连续即可只要连续即可) .无法求复根及无法求复根及偶重根偶重根收敛慢收敛慢 用二分法求根，最好先给出用二分法求根，最好先给出 f (x) 草图以确定根的大草图以确定根的大概位置。或用搜索程序，将概位置。或用搜索程序，将a, b分为若干小区间，对每一分为若干小区间，对每一个满足个满足 f (ak)f (bk) 0 的区间调用二分法程序，可找出区的区间调用二分法程序，可找出区间间a, b内的多个根，且不必要求内的多个根，且不必要求 f (a)f (b) 0 。优点优点缺点缺点2 迭代法的理论迭代法的理论 /* theory of iter

8、ation method*/f (x) = 0 x = g (x)（迭代函数）（迭代函数）等价变换等价变换思思路路从一个初值从一个初值 x0 出发，计算出发，计算 x1 = g(x0), x2 = g(x1), , xk+1 = g(xk), 若若 收敛，即存在收敛，即存在 x* 使得使得 ，且，且 g 连续，则由连续，则由 可可知知 x* = g(x* )，即，即x* 是是 g 的不动点，也就是的不动点，也就是f 的根。的根。 0kkx*limxxkk kkkkxgx limlim1f (x) 的根的根x g (x) 的不动点的不动点x 10 1 2(), , ,(*)kkxg xk 一、不

9、动点迭代一、不动点迭代 /*fixed-point iteration*/xyy = xxyy = xxyy = xxyy = xx*x*x*x*y=g(x)y=g(x)y=g(x)y=g(x)x0p0 x1p1x0p0 x1p1x0p0 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 1210

10、4xxx 12104g xxx4 4、即即12104xx 12104g xx 5 5、即即xxxxxx83104223( )( )( )f xg xxfx 取取01 5 .x 计算结果如下：计算结果如下：123840875673246972010275 10.xxxx 法法1 11234451113484013673813649613652613751713652251365230013.xxxxxxx 法法4 412123081650299691865086.( .)xxx 法法3 3123445112912869514025413454613751713751713751713651378

11、211365230013.xxxxxxxx 法法2 2123413733313652613652300141365230013.xxxx 法法5 5lipschitz条件成条件成立的充分条件立的充分条件2 3 .th 考虑方程考虑方程 x = g(x), 若若( 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|*|

12、1kkkxxlxx 101|*|kklxxxxl ( k = 1, 2, )且存在极限且存在极限 *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* ？ |*|

13、kxx|*| )(| )(*)(|111 kkkxxgxgxg0|*|.|*|01 xxlxxlkkl 越越 收敛越快收敛越快可用可用 来来控制收敛精度控制收敛精度|1kkxx ?|11|*|1kkkxxlxx 11111|*|*|*|kkkkkkkkkxxxxxxxxl xxxx ?|1|*|01xxllxxkk |.| )(| )()(|011111xxlxxlxxgxgxgxxkkkkkkkkkk 1lim()?kkkxxg xxx *)(*)*)(lim*lim1xgxxxxgxxxxkkkkkkk 小小条件条件 ( ii ) 可改为可改为 在在a, b 满足满足lipschitz条件

14、条件,定理结论仍然成立定理结论仍然成立(定理定理2.3)。 算法算法: : 不动点迭代不动点迭代给定初始近似值给定初始近似值 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 | 1)(1)阶收敛的方法，阶收敛的方法，改用改用stefensen迭代方法优点不多。迭代方法优点不多。取取01 5.x 计算结果如下：计算结果如下：12341361886136522