第三章非线性方程求根 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?