第章我线性方程的数值解法 copyright@湘潭大学数学与计算科学学院 上一真下一真
1 上一页 下一页 第七章 非线性方程的数值解法
G求f(x)=0的根 §1二分法 原理:若∫∈C{,b,且f(a)·f(b)<0,则f在(a,b)上必 有一根。 copyright@湘潭大学数学与计算科学学院 上一真下一真
2 上一页 下一页 §1 二分法 求 f (x) = 0 的根 原理：若 f C[a, b]，且 f (a) · f (b) < 0，则 f 在 (a, b) 上必 有一根
G求f(x)=0的根 §0多项式基础 §1二分法 原理:若∫∈C{,b,且f(a)·f(b)<0,则f在(a,b)上必 有一根。 copyright@湘潭大学数学与计算科学学院 上一真下一真
3 上一页 下一页 §0 多项式基础 §1 二分法 求 f (x) = 0 的根 原理：若 f C[a, b]，且 f (a) · f (b) < 0，则 f 在 (a, b) 上必 有一根
什么时候停止? b x4-x<E1或f(x)< 不能保证x的精 度一 4 copyright@湘潭大学数学与计算科学学院 上一真下一真
4 上一页 下一页 a b x1 x2 a b 什么时候停止? 1 1 x x ε k+ − k 2 或 f (x) ε 不能保证 x 的精 度 x* 2 x* x
很差)分析 第1步产生的x=2有误差Nx-a a+b 第k步产生的x有误差-x≤b-a 对于给定的精度E,可估计二分法所需的步数k b=a <E→k In(b-a)-In 2 k In 2 ①简单: ②对(x)要求不高(只要连续即可) ①无法求复根及偶重根 ②收敛慢 注:用二分法求根,最好先给出∫(x)草图以确定根的大概 位置。或用搜索程序,将a,b分为若干小区间,对每一个 满足f(a)f(b)<0的区间调用二分法程序,可找出区间 a,b内的多个根,且不必要求f(a)∫(b)<0。 页
5 上一页 下一页 误差 分析： 第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
§2迭代法 等价变换 f(x)=0 x=g(x) f(x)的根 g(x)的不动点 从一个初值x出发,计算x=g(x),x2=g(x1), 思xk1=g(x),若{x}n收敛,即存在x使得 路加mx=x*,且g连续,则由 lim x=呵知x) gx*),即x是g的不动点,也就是f的根。 copyright@湘潭大学数学与计算科学学院 上一真下一真
6 上一页 下一页 §2 迭代法 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
y=x y-x y=g(x) glx P1 y=glr J y=glr P P1 copyright@湘潭大学数学与计算科学学院 上一真下一真
7 上一页 下一页 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
定理考虑方程x8,8∈从若 (I)当x∈a,b时,gx)∈a,b; (Ⅱ彐0≤L<1使得|g(x)|≤L<1对x∈[a,b成立 则任取x∈a,b,由xk1=g(x)得到的序列{x}收敛 于g(x)在|a,b上的唯一不动点。并且有误差估计式: ①|x*-x|S,,|xk+1-xk ②x-/s、 (k=1,2 x, L 一0 且存在极限lim k+1 g copyright@湘潭大学数学与计算科学学院 上一真下一真
8 上一页 下一页 定理 考虑方程 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上存在不动点? 令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=8(x2)-g(x)=8(2)(x*-x,5在x*和飞之间 →(x ()=0而|g()|0 copyright@湘潭大学数学与计算科学学院 上一真下一真
9 上一页 下一页 证明：① 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*-xk ? 1-L ③x*-x,|1,x1-x1?可用1x余√ k+1 ≥|x*-xk|-|x I v 控制收敛精度 k+1 k=lg(xk) )=|g(5k八→k→k-1月 ≤L|yL越小收敛越快 ⑥li k+1 8t k→∞x一x *一xk+=lim8(k)(x*一x =g(x*)√ k→>xx-xkk→ k 注:定理条件非必要条件,可将a,b缩小,定义局部收敛性: 若g(x)在x*的某δ邻城B:={x||x-x*|≤6}内连续可微 且|g(x)<1,则由x∈BB开始的迭代收敛。即调整初 值可得到收敛的结果。 0 copyright@湘潭大学数学与计算科学学院
10 上一页 下一页 ④ | | ? 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]缩小，定义局部收敛性： 若g(x)在 x* 的某 邻域 B= { x | | x − x* | } 内连续可微 且 | g’(x*) | < 1，则由x0B开始的迭代收敛。即调整初 值可得到收敛的结果