对分法的本质是将区间[a_k,b_k ]的中点x_k作为方程根x^*的近似值,由上述过程,可以得到序列

x_0,x_1,x_(2,),⋯

误差1.1（对分法）

设c_n表示算法中c的第n次值.则容易得出,

x^*=(lim)┬(n→∞)⁡〖c_n 〗

|x^*-c_n |≤(1/2)^n (b-a),               （1.1.1）

这里的(b-a)是输入到算法中原始的区间长度.实际误差也许不是每一步以1⁄2因子下降,但由式（1.1.1）,平均下降速度是1⁄2.

根据对分法的基本思想给出算法.考虑到a,b都很大或者f(a),f(b)都很大的情况,为避免溢出, x_k用□(a_k/2+)  b_k/2计算,用f(a_k )和f(x_k )的符号相异来判断f(a_k )  f(x_k )<0.

算法1.1（对分法）Bisct, (f,a,b,root,ε)

定义; c=a⁄2+b⁄2;

若b-a≤ε或者|f(c)|≤ε,取root=c,停止算法;

若sign(f(a))=sign(f(c)),令a=c,否则b=c;

转步骤1).

这个算法每循环一次就将区间[a,b]折半,且由第3)步,[a,b]总包含f(x)的一个根.因根x^*在[a,b]中,它必定位于[a,c]或[c,b]中,于是