《二分法 讲义》由会员分享，可在线阅读，更多相关《二分法 讲义（34页珍藏版）》请在金锄头文库上搜索。
1、二分法对于在区间a,b上连续不断、且f(a)*f(b)O的函数y=f(x)，通过不断把函数f(x)的零点所在区间一分为二，使区间的两个端点逐步逼近零点, 进而得到零点近似值的方法叫二分法。1、确定区间a,b，验证f(a)*f(b)O,给定精确度2、求区间(a,b)的中点x13、计算 f(x1);(1) 若 f(x1)=0, 则 x1 就是函数的零点(2) 若 f(x1)0,则令 b= x1(此时零点 xOu(a,x1)(3) 若 f(x1)0,则令 a= x1(此时零点 xOu(x1,b)4、判断是否达到精确度，即若|a-b| ，则得到零点的近似值a(或b)；否则得复24什么是二分法？从数学角
2、度看,二分法, 又称分半法, 是一种方程式根的近似值求法.若要求已知函数 f(x) = 0 的根 (x 的解), 则: 先定义一个区间 a, b, 使其包含著方程式的根.求该区间的中点, 并找出 f(m) 的值若 f(m) 与 f(a) 正负号相同则取 m, b 为新的区间, 否则取 a, m. 重覆第 2 步至理想精确度为止.从哲学角度就是考虑问题的方法,要懂得考虑问题的利弊或正反两面.“二分法”求二元方程的解前面说到了用“精确迭代法”求两个数的最大公约数，这里的“ 二分法”也属于 迭代法近似迭代 。另外还有“ 牛顿迭代”也属于 近似迭代。思想：二分法属于数学问题，但为了说清楚问题就再说一下
3、原理。先取二元方程f(x)的两个初略解x1和x2，若f(xl)与f(x2)的符号相反，则方程f(x)=o在xl, x2区间至少有一个根；若f(x)在xl, x2区间单调，则至少有一个实根；所以取x3=(x1+x2)/2，并在xl和x2中舍去和f(x3)同号者，那么解就在x3和另外那个没有舍去的初略解组成的区间里；如此反复取舍，直到xn与xn-1之差满足要求时，那么xn便是方程f(x)的近似根。所以有算法：wh订e (误差给定误差)if (f (x) =0)x就是根，不在迭代；else if (f (x) *f (xl)0)/*这里的x相当于上面所说的x3*/x2=x;elsexl=x;例：用二
4、分法求方程x2-2-x=0在0, 3区间的根。 float f(float x)return (x*x-x-2);#include#includemain ()/给定精度/求根float xl=0, x2=3, x, root; const float err=.5e-5 while(fabs(xlx2)err)if (f (xl)=O)root=xl;break;if (f (x2)=0)root=x2;break;x= (xl+x2)/2;if (f (x)=0)root=x;break;if (f (x) *f (xl)0)x2=x;elsexl=x;root=xl;coutThe ro
5、ot is:rootendl;二分法就是一种很高效的算法。比如就是查找，就有二分查找 总之我也说不清楚了，你自己看程序吧。 顺序表的二分查找： 在顺序表(2，5，7，10，14，15，18，23，35，41，52)中，用二分法查找 12，所需的关键码比较的次数为 4 program binarysearch;const n=20；type arr=array1.n of integer;var a:arr;first,last,I,x:integer;procedure search(x,top,bot:integer);var mid:integer;beginif top= bot the
6、nbeginmid:=(top+bot)div 2;if x=amid then writeln(mid) 递归终止返回 else if x ttincludevoid main()double a, xO, xl;printf(Input a:rT);scanf&a) ;/ 为什么在 VC6. 0 中不能写成“scanf (%f, &a) ; ?if(a=le6);printf(ResuIt:n);printf (sqrt (%g) =%gn，/, a, xl);求平方根的迭代公式：xl=l/2*(x0+a/x0)。算法：1. 先自定一个初值x0，作为a的平方根值，在我们的 程序中取a/2作为a的初值；利用迭代公式求出一个x1。此值与真正的a的平方根 值相比，误差很大。2. 把新求得的x1代入x0中
