数值分析非线性方程的数值解法市公开课获奖课件

1、第二章 非线性方程数值解法 /* Numerical Solutions of Nonlinear Equations*/本章主要内容：1、二分法2、不动点迭代结构及其收敛性鉴定（重点）3、Newton和Steffensen迭代4、弦割法与抛物线法第1页第1页历史背景 代数方程求根问题是一个古老数学问题。理论上， 次代数方程在复数域内一定有 个根(考虑重数)。早在16世纪就找到了三次、四次方程求根公式，但直到19世纪才证实不小于等于5次普通代数方程式不能用代数公式求解，而对于超越方程就复杂多，假如有解，其解也许是一个或几种，也也许是无穷多个。普通也不存在根解析表示式。因此需要研究数值办法求得满

2、足一定精度要求根近似解。 第2页第2页求方程 几何意义基本定理 假如函数 在 上连续，且则至少有一个数 使得 ，若同时 一阶导数 在 内存在且保持定号，即 (或 )则这样 在 内唯一。 abx*第3页第3页1 二分法 /* Bisection Method */原理：若 f Ca, b，且 f (a) f (b) 0，则 f 在 (a, b) 上至少有一实根。基本思想：逐步将区间分半，通过判别区间端点函数值符号，进一步搜索有根区间，将有根区间缩小到充足小，从而求 出满足给定精度根 近似值。终止法则？abx1x2abWhen to stop?或不能确保 x 精度x*第4页第4页 二分法算法给定区

3、间a,b ，求f(x)=0 在该区间上根x.输入: a和b; 允许误差 TOL; 最大对分次数 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

4、 the solution of equation: x; STOP.第5页第5页3、由二分法过程可知：4、对分次数计算公式：1、2、令第6页第6页解：例1：用二分法求方程 在区间 上根，误差限为 ，问至少需对分多少次？第7页第7页简朴; 对f (x) 要求不高(只要连续即可) .无法求复根及偶重根收敛慢 注：用二分法求根，最好先给出 f (x) 草图以拟定根大约位置。或用搜索程序，将a, b分为若干小区间，对每一个满足 f (ak)f (bk) 0 区间调用二分法程序，可找出区间a, b内多个根，且不必要求 f (a)f (b) 0 。长处缺点第8页第8页2 迭代法理论 /* Theory

5、of Iteration 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 根。f (x) 根g (x) 不动点一、不动点迭代 /*Fixed-Point Iteration*/第9页第9页xyy = xxyy = xxyy = xxyy = xx*x*x*x*y=g(x)y=g(x)y=g(x)y=g(x)x0p0 x1p1x0p0 x1p1

6、x0p0 x1p1x0p0 x1p1几何意义第10页第10页例2：已知方程 在 上有一个根（正根）下面选取5种迭代格式：1、即2、即3、即4、即5、即第11页第11页取计算结果下列：法1法4法3法2法5第12页第12页Lipschitz条件成立充足条件考虑方程 x = g(x), 若( I ) 当 xa, b 时， g(x)a, b；( II ) 0 L 1 使得 对 xa, b 成立。则任取 x0a, b，由 xk+1 = g(xk) 得到序列 收敛于g(x) 在a, b上唯一不动点。并且有误差预计式：( k = 1, 2, )且存在极限连续时第13页第13页证实： g(x) 在a, b上存在不动点？令有根 不动点唯一？反证：若不然，设尚有 ，则在和之间。而 当k 时， xk 收敛到 x* ？第14页第14页L 越 收敛越快可用 来控制收敛精度小注：条件 ( II ) 可改为 在a, b 满足Lipschitz条件,定理结论仍然成立(定理2.3)。第15页第15页 算法: 不动点迭代给定初始近似值 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