第二章非线性方程求根 Solutions of Nonlinear Equations * 求(=0的根 §1多项式基础/ Polynomialsη(自习) §2二分法/ Bisection Method 原理:若∫∈CIa,b,且f(a)·∫(b)<0,则f在(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) 上必 有一根
§2 Bisection method When to stop? b k1-xA<61或(x)<62 不能保证x的精 度
§2 Bisection Method a b x1 x2 a b When to stop? 1 1 x x ε k+ − k 2 或 f (x) ε 不能保证 x 的精 度 x* 2 x* x
§2 Bisection method 误差)分析: 第k步产生的x有误差kx小 第步产生的x=2有误差k-x2n 对于给定的精度E,可估计二分法所需的步数k 2<→k、[n(6-a)-lal -a In 2 ①简单: ②对(x)要求不高(只要连续即可) ①无法求复根及偶重很 HW:p.16#1 ②收敛慢 注:用二分法求根,最好先给出∫(x)草图以确定根的大概 位置。或用搜索程序,将a,b分为若干小区间,对每一个 满足f(a)f(b)<0的区间调用二分法程序,可找出区间 a,b内的多个根,且不必要求f(a)f(b)<0
§2 Bisection Method 误差 分析： 第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 。 HW: p.16 #1
§2 Bisection method Lab 02. bisection method Use the Bisection method to find on m given intervals the m real roots of a given polynomial of degree5≥n≥m,p(x)=cnx+cn-1x+…+c1x+Co Input There are severalsets ofinputs. For each set The 1st line contains an integer n which is the degree of a polynomial. n=-l signals the end of file. The 2nd line contains n+l real numbers cn. C Co which are the coefficients of the polynomial. The numbers are separated by spaces. The 3rd line contains an integer Max and two real numbers epsl and eps2, where Max is the maximum number of iterations, eps l is the accuracy bound for x and eps 2 is the accuracy bound forp(x). The 4th line contains an integer m(n2 m20), followed by m pairs of real numbers a bi...am bm which are the end points of the intervals Ia1,b1l…Iam,bml
§2 Bisection Method Lab 02. Bisection Method Use the Bisection method to find on m given intervals the m real roots of a given polynomial of degree 5 n m, . Input There are severalsets of inputs. For each set: The 1 st line contains an integer n which is the degree of a polynomial. n = −1 signalsthe end of file. The 2 nd line contains n+1 real numbers which are the coefficients of the polynomial. The numbers are separated by spaces. The 3 rd line contains an integer Max and two real numbers eps1 and eps2, where Max is the maximum number of iterations, eps1 is the accuracy bound for x and eps2 is the accuracy bound for p(x). The 4 th line contains an integer m (n m 0), followed by m pairs of real numbers a1 b1 …am bm which are the end points of the intervals [ a1 , b1 ] …[ am , bm ]. 1 0 1 1 p(x) c x c x ... c x c n n n = n + + + + − − 1 0 c ... c c n
$2 Bisection Method Output Each root is to be printed as in the c fprintf fprintf(outfile, 912.7f", root ) / here represents a space * If there is no root found in an interval, simply print“no■root■” The output of the next set must be printed in a new line. Sample Input(a represents a space) 1■0■-1 1000■0.00000001■0.00000001 2■-2■-0.5■0.5■2 1■0■0■-1 1000■0.00000001■0.00000001 2■-1■0■0■2 Sample output (a represents a space) ■■-1.0000000■■■■1.0000000■ no■root■■■■1.0000000■
Output Each root is to be printed as in the C fprintf: fprintf(outfile, "%12.7f", root); /* here represents a space */ If there is no root found in an interval,simply print “noroot”. The output of the next set must be printed in a new line. Sample Input ( represents a space) 2 10−1 10000.000000010.00000001 2−2−0.50.52 3 100−1 10000.000000010.00000001 2−1002 −1 Sample Output ( represents a space) −1.00000001.0000000 noroot1.0000000 §2 Bisection Method
§2 Bisection method 试位法/ 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? 注：试位法每次迭代比二分法多算一次乘法，而且不保证 收敛。 §2 Bisection Method
§3迭代法/ Fixed-Point iteration 等价变换 ∫(x)=0 x=g(x) f(x)的根 g(x)的不动点 从一个初值x出发,计算x1=g(x),x2=g(x1),…, 思xk+1=g(x),… 若{x}收敛,即存在x使得 路加mx=x*,且g连续,则由 lim x=呵知x) 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?
&3 Fixed-Point Iteration y=x y=x y=g(r) glx P1 J y=gun y=g(r) P P
§3 Fixed-Point Iteration 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
&3 Fixed-Point Iteration 定理|考虑方程x=8,80若 (I)当x∈[a,b时,g(x)∈|a,b; (I)彐0≤L<1使得|g(x)|≤L<1对x∈[a,b成立 则任取x∈[,b,由xk+1=g(x)得到的序列{xk}收 敛于g(x)在a,b上的唯不动点。并且有误差估计式: ①|x*-x x L k+1 k (k=1,2,…) ②|x*-xk L 0 , 且存在极限im k+1 g
§3 Fixed-Point Iteration 定理 考虑方程 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
&3 Fixed-Point Iteration 证明:①g(x)在|a,b上存在不动点? 令f(x)=g(x)-xa≤g(x)≤b ∴∫(a)=g(a)-a≥0,∫(b)=g(b-b≤0 →f(x)有根√ ②不动点唯一? 反证:若不然,设还有x=g(x),则 x*一x=8(x*)-8(X)=g()(x*-x),5在x和x之间 →(x-x)(1-g(5)=0而|g(5)0
§3 Fixed-Point Iteration 证明：① 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 ✓ ✓ ✓