西安建筑科技大学：《高等数学计算方法》课程电子教案（PPT教学课件）第3章 非线性方程与方程组的数值解法（非线性方程求根）

第三章非线性方程求根 Solutions of Nonlinear Equations * 求f(x)=0的根 §1多项式基础/ Polynomials”(自习) §2二分法/ Bisection Method 原理:若∫∈CIa,b,且f(a)·∫(b)<0,则/在(a,b)上必 一根

第三章 非线性方程求根 /* Solutions of Nonlinear Equations */ §1 多项式基础 /* Polynomials */ （自习） §2 二分法 /* Bisection Method */ 求 f (x) = 0 的根 原理：若 f C[a, b]，且 f (a) · f (b) < 0，则 f 在 (a, b) 上必 有一根

nen to stop b x4-x<E1或f(x)<E2 不能保证x的精 度

a b x1 x2 a b When to stop? 1 1 x x ε k+ − k  2 或 f (x)  ε 不能保证 x 的精 度 x*  2 x* x

误差)分析: 第k步产生的x4有误差-b a+b 第1步产生的x 有误差r1-x 对于给定的精度E,可估计二分法所需的步数k -a In(b-a)-In e] 2 In 2 ①简单: ②对(x)要求不高只要连续即可) ①无法求复根及偶重根 ②收敛慢 注:用二分法求根,最好先给出∫(x)草图以确定根的大概 位置。或用搜索程序,将a,b分为若干小区间,对每一个 ￠满足的与Q、0的区图词用二分法程序,可找出区间 L

误差 分析： 第1步产生的 2 1 a b x + = 有误差 2 1 b a |x x*| − −  第 k 步产生的 xk 有误差 k k b a |x x*| 2 − −  对于给定的精度  ,可估计二分法所需的步数 k ：  ( )  ln 2 ln ln 2 b a ε ε k b a k − −    − ①简单; ② 对f (x) 要求不高(只要连续即可) . ①无法求复根及偶重根 ② 收敛慢 注：用二分法求根，最好先给出 f (x) 草图以确定根的大概 位置。或用搜索程序，将[a, b]分为若干小区间，对每一个 满足 f (ak )·f (bk ) < 0 的区间调用二分法程序，可找出区间 [a, b]内的多个根，且不必要求 f (a)·f (b) < 0

>试位法 / Regula Falsi Method * Is it really better than Bisection method? (b,∫(b) (a+b)/2 f∫(a) (a,(a) X=a f∫(b)-∫(a) 注:试位法每次迭代比二分法多算一次乘法,而且不保证 收敛

➢ 试位法 /* Regula Falsi Method */ a b (a+b)/2 x* (a, f (a)) (b, f (b)) (b a) f b f a f a x a  − − = − ( ) ( ) ( ) Is it really better than Bisection Method? 注：试位法每次迭代比二分法多算一次乘法，而且不保证 收敛

§3迭代法/ Fixed-Point Iteration 等价变换 ∫(x)=0 x=g(r) f(x)的根 g(x)的不动点 从一个初值x出发,计算x1=g(x),x2=g(x1…, 思x1=g(x),若{x}n收敛,即存在x*使得 路mx=x,且g连续,则由imx,=问阳Xx) gx*),即x*是g的不动点,也就是f的根 Oh yeah? who tells you that the method is convergent? id blem?

§3 迭代法 /* 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* = g(x* )，即x* 是 g 的不动点，也就是f 的根。    k k=0 x lim x x * k k = → ( ) k k k k x g x → + → lim 1 = lim So basically we are done! I can’t believe it’s so simple! What’s the problem? Oh yeah? Who tells you that the method is convergent?

y=x y=glr) y=gr P1 y=x y=gun y=g(x) P1

x y y = x x y y = x x y y = x x y y = x x* x* x* x* y=g(x) y=g(x) y=g(x) y=g(x) x0 p0 x1 p1 ✓ x0 p0 x1 p1 ✓ x0 p0 x1 p1  x0 p0 x1 p1 

定理|考虑方程x-=8,80若 (1Ⅰ)当x∈{a,b时,g(x)∈|ab (I)彐0≤L<1使得|g:(x)|≤L<1对x∈a,b成立 则任取xe∈la,b,由x1=g(x)得到的序列{x,收 敛于g(x)在lab上的唯不点。并且有误差估计式: ① -r 1-L k+1 k ( k ②|x*-xk L 0 极限imx+19g(x)

定理 考虑方程 x = g(x), g(x)C[a, b], 若 ( I ) 当 x[a, b] 时， g(x)[a, b]； ( II )  0  L < 1 使得 | g’(x) |  L < 1 对  x[a, b] 成立。 则任取 x0[a, b]，由 xk+1 = g(xk ) 得到的序列 收 敛于g(x) 在[a, b]上的唯一不动点。并且有误差估计式：    k k=0 x | | 1 1 | * | k k 1 k x x L x x − −  −  +  | | 1 | * | x1 x0 L L x xk − − −  ( k = 1, 2, … ) 且存在极限 ( *) * * lim 1 g x x x x x k k k =  − − + →       k

证明:①g(x)在[a,b上存在不动点? 令∫(x)=g(x)-x…a≤g(x)≤b ∫(a)=g(a)-a≥0,∫(b=g(b)-b≤0 →f(x)有根√ ②不动点唯一? 反证:若不然,设还有x=g(x),则 x*一=8(x)-8(X)=g()(x*-x),5在x和x之间 →(x*-x)(1-g(3)=0而|g(3)1∴x= ③当k→∞时,x收敛到x*? k|=|g(x)-g(x)=|(k1)x*-xk ≤L|x*-xk-1|≤…|x →0

证明：① g(x) 在[a, b]上存在不动点？ 令 f (x) = g(x) − x  a  g(x)  b  f (a) = g(a) − a  0 , f (b) = g(b) − b  0  f (x) 有根 ② 不动点唯一？ 反证：若不然，设还有 x ~ = g(x ~ ) ，则 ), ~ ) ( )( * ~ x* − x ~ = g(x*) − g(x = g ξ x −x  在 x* 和 x ~ 之间。 )(1 ( )) 0 ~  (x* − x − g ξ = 而 g ξ x x ~ | ( )|  1  * = ③ 当k →  时， xk 收敛到 x* ？ | x*−xk | = | ( *) ( )| | ( )| | * | −1 −1 − −1 − =   k k k g x g x g ξ x x  L| x *−x −1 |  ......  L | x *−x0 | → 0 k k ✓ ✓ ✓

④|x*-x|s1r1xk+1- L X-x x"- ⑥|x*-xk|≤ 可用|xk+-xk来 L 控制收敛精度 xk+1-xk|=g(xA)v.-1)=g(5k八→k→k-1 ≤L|yL越小收敛越快 k+1 8t k→ x k lim 8(sk)0 g(x)√ k→∞X k 注:定理条件非必要条件,可将a,b缩小,定义局部收 敛性:若在x的某δ领域Bs={x||x-x*|≤δ}有 g∈C[a,b且|g:(x)|<1,则由vx∈B开始的送代 收敛。即调整初值可得到收敛的结果

④ | | ? 1 1 | * | k k 1 k x x L x x − − −  + | | | * | | * | | * | | * | k 1 k k k 1 k k x − x  x −x − x −x  x −x −L x −x + + ✓ | | ? 1 | * | x1 x0 L L x x k k − − ⑤ −  | | ...... | | | | | ( ) ( )| | ( )( )| 1 1 0 1 1 1 L x x L x x x x g x g x g ξ x x k k k k k k k k k k  −   − − = − =  − − + − − ✓ ( *) ? * * lim 1 g x x x x x k k k =  − − + → ⑥ ( *) * ( )( * ) lim * * lim 1 g x x x g ξ x x x x x x k k k k k k k =  −  − = − − → + → ✓ 可用 来 控制收敛精度 | | k 1 k x − x + L 越小 收敛越快 注：定理条件非必要条件，可将[a, b]缩小，定义局部收 敛性：若在 x* 的某 领域 B= { x | | x − x* |   } 有 gC1 [a, b] 且 | g’(x*) | < 1，则由x0B开始的迭代 收敛。即调整初值可得到收敛的结果

改进、加速收敛* accelerating convergence >待定参数法: 着|g!(x)|≥1,则将x=g(x)等价地改造为 x=x-kx+kg(r)=(1-K)x+kg r=p(r) 求K,使得|φ(x)|=|1-K+kg(x)1 现令g(x)=(1-K)x+kg(x)=(1-K)x+(x3+1) 希里|()=1-k+A1<1,即x二1<K<0 ,2)上可取任意-2<k刚如K=-0.5,则对应 即产生收敛列

改进、加速收敛 /* accelerating convergence */ ➢ 待定参数法： 若 | g’(x) |  1，则将 x = g(x) 等价地改造为 x = x − Kx + Kg(x) = (1− K)x + Kg(x) = (x) 求K，使得 |(x)| = |1− K + Kg(x)|  1 例：求 ( ) 3 1 0 在 (1, 2) 的实根。 3 f x = x − x + = ( 1) ( ) 3 1 3 如果用 x = x + 进行迭代，则在 = g x (1, 2)中有 | ( )| | | 1 2 g x = x  现令 ( 1) 3 ( ) (1 ) ( ) (1 ) 3 = − + = − + x + K  x K x Kg x K x 希望 | ( )| |1 | 1 2  x = − K + Kx  0 1 2 2   − − K x ，即 在 (1, 2) 上可取任意 ，例如K = −0.5，则对应 即产生收敛序列。 0 3 2 −  K  ( 1) 6 1 2 3 3 x = x − x +