《现在数值分析课件科大现代数值分析15非线性方程求解》由会员分享，可在线阅读，更多相关《现在数值分析课件科大现代数值分析15非线性方程求解（11页珍藏版）》请在金锄头文库上搜索。
1、第四章 非线性方程求根 /* Solutions of Nonlinear Equations */,1 二分法 /* Bisection Method */,求 f (x) = 0 的根,原理：若 f Ca, b，且 f (a) f (b) 0，则 f 在 (a, b) 上必有一根。,2 Bisection Method,x1,x2,a,b,When to stop?,或,不能保证 x 的精度,x*,2,2 Bisection Method,误差 分析：,第 k 步产生的 xk 有误差,对于给定的精度 ,可估计二分法所需的步数 k ：,简单; 对f (x) 要求不高(只要连续即可) .,无法
2、求复根及偶重根 收敛慢,注：用二分法求根，最好先给出 f (x) 草图以确定根的大概位置。或用搜索程序，将a, b分为若干小区间，对每一个满足 f (ak)f (bk) 0 的区间调用二分法程序，可找出区间a, b内的多个根，且不必要求 f (a)f (b) 0 。,2 迭代法 /* Fixed-Point Iteration */,f (x) = 0,x = g (x),f (x) 的根,g (x) 的不动点,思路,从一个初值 x0 出发，计算 x1 = g(x0), x2 = g(x1), , xk+1 = g(xk), 若 收敛，即存在 x* 使得 ，且 g 连续，则由 可知 x* =
3、g(x* )，即x* 是 g 的不动点，也就是f 的根。,So basically we are done! I cant believe its so simple! Whats the problem?,Oh yeah? Who tells you that the method is convergent?,2 Fixed-Point Iteration,2 Fixed-Point Iteration,定理,k,2 Fixed-Point Iteration,证明： g(x) 在a, b上存在不动点？,令,有根, 不动点唯一？,反证：若不然，设还有 ，则,而, 当k 时， xk 收敛到
4、x* ？,2 Fixed-Point Iteration,可用 来控制收敛精度,L 越 收敛越快,小,注：定理条件非必要条件，可将a, b缩小，定义局部收敛性：若在 x* 的某 领域 B = x | | x x* | 有 gC1a, b 且 | g(x*) | 1，则由x0B 开始的迭代收敛。即调整初值可得到收敛的结果。,3 Fixed-Point Iteration,Algorithm: Fixed-Point Iteration Find a solution to x = g(x) given an initial approximation x0. Input: initial app
5、roximation x0; tolerance TOL; maximum number of iterations Nmax. Output: approximate solution x or message of failure. Step 1 Set i = 1; Step 2 While ( i Nmax) do steps 3-6 Step 3 Set x = g(x0); /* compute xi */ Step 4 If | x x0 | TOL then Output (x); /* successful */ STOP; Step 5 Set i +; Step 6 Se
6、t x0 = x ; /* update x0 */ Step 7 Output (The method failed after Nmax iterations); /* unsuccessful */ STOP.,当 x 很大时，此处可改为, 待定参数法：,若 | g(x) | 1，则将 x = g(x) 等价地改造为,求K，使得,例：求 在 (1, 2) 的实根。,如果用 进行迭代，则在(1, 2)中有,现令,在 (1, 2) 上可取任意 ，例如K = 0.5，则对应 即产生收敛序列。, Aitken 加速（两点组合）,3 加速收敛方法,P(x0, x1),P(x1, x2),一般地，有：,比 收敛得略快。, Steffensen 加速：,
