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