本节书摘来自华章出版社《数值分析（原书第2版）》一 书中的第1章，第1.1节，作者：（美）Timothy Sauer，更多章节内容可以访问云栖社区“华章计算机”公众号查看。

1.1　二分法

你如何在一个陌生的电话簿中找一个人名？如果搜索“Smith”，你可能会根据***的猜测打开电话簿，比如在字母Q，然后你可能翻过好多页到了字母U.现在把Smith这个名字放到了一个大括号里，然后需要去找越来越小的括号，直到最后得到要找的名字.二分法对应这样的推理过程，尽可能有效地实施.

1.1.1　把根括住

定义1.1　如果f（r）=0，函数f（x）在x=r时有一个根.
求解方程的第一步是确定根是否存在.一种方式是看是否能把根括在一个区间中:在实数轴上寻找一个区间［a，b］对应的一对函数值{f（a），f（b）}，一个是正数，而另外一个是负数.这种情况也可以表达为f（a）f（b）<0.如果f是一个连续函数，则存在一个根:a和b之间存在r，满足f（r）=0.下面的中值定理0.4的推论中将总结这种现象.
定理1.2　令f是区间［a，b］上的连续函数，满足f（a）f（b）<0，则f在a和b之间存在一个根，也就是说，存在数字r，满足a在图1.1中，f（0）f（1）=（-1）（1）<0.在略小于0.7的地方有一个根.用什么办法才能更精确地估计根的位置呢？
我们可以从函数的曲线大概看出解的位置.用类似的方法，我们也可以设计一种数值求解方法.一种不太可行的方法是，从左到右逐个检查所有区间，直到到达根的位置.另一种更好的方法是，先大概确定根的位置，判断它是位于现有区间的左半部分还是右半部分.然后再进一步细分根所在的区间，这样就能提高解的精度，类似于在电话簿中查找一个名字.这种方法被称为二分法，见图1.2

二分法.第一步，检查f（c0）的符号.由于f（c0）f（b0）<0，令a1=c0,b1=b0，区间更新为右半部分［a1,b1］.第二步，区间进一步更新为［a2,b2］
检查函数在区间中点c=（a+b）/2位置的值.由于f（a）和f（b）符号相反，所以f（c）的取值要么满足f（c）=0（这时我们已经找到根了）；要么和f（a）或f（b）其中的一个符号相反.如果f（c）f（a）<0，我们就可以确定解在区间［a，c］上，新区间的长度变成了原来区间［a，b］的一半.反过来，如果f（c）f（b）<0，同理新区间变为［c，b］.无论哪种情况，每步操作都可以把根所在的区间长度减半.循环使用这种操作就可以使解的精度越来越高.
在每一步中，解的区间都会变得更小，解的位置的不确定性也随之降低.在这个过程中并不需要知道函数f的整个曲线.我们只需要在必要的位置上计算函数的值.
例1.1　利用二分法在区间［0，1］上找到函数f（x）=x3+x-1的解.
确认f(a0)f(b0)=(-1)(1)<0，则在这个区间上存在解.区间的中点为c0=1/2.第一步，计算函数值f（1/2）=-3/8<0，f（1/2）f（1）<0，26因此新区间选择［a1，b1］=［1/2，1］.第二步，计算f（c1）=f（3/4）=11/64>0，则新区间选择［a2，b2］=［1/2，3/4］.继续运算得到以下的一系列区间：

从上表中可知，函数的解是在a9≈0.6816和c9≈0.6826之间.区间中点c10≈0.6821即是我们最终得到的根的***估计值.
虽然我们的目标是找到根的位置，但是实际得到的是一个含有根的区间［0.6816，0.6826］；换句话说，根是r=0.6821±0.0005.我们只能在其中选择一个估计值.当然，如果需要更高的精度，通过增加二分法的迭代次数就能实现.
二分法的每一步中我们都需要计算现有区间［ai，bi］的中值点ci=(ai+bi)/2，函数值f(ci)，并比较符号.如果f(ci)f(ai)<0，则ai+1=ai，bi+1=ci,反之，如果f(ci)f(ai)>0，则ai+1=ci,bi+1=bi.每一步中都需要计算一次函数值并二分包含根的那部分区间，使得区间长度变为原来的一半.计算c和f（c）n次之后，我们一共计算函数值n+2次，而解的***估计是最终那个区间的中点.算法可以写成以下MATLAB代码：

要使用bisect.m，首先需要定义MATLAB函数：

这条命令实际上定义了一个“函数句柄”f，它可以作为另一个MATLAB函数的输入.更多关于MATLAB函数和函数句柄的信息参考附录B.命令

返回一个误差范围为0.00005的解.

1.1.2　多准？多快

假设［a，b］是初始区间，在n次二分之后，得到的最终区间［an，bn］的长度为（b-a）/2n.选择中点xc=(an+bn)/2作为解的最优估计值，与真实值之间的误差不会超过区间长度的一半.总之，n步二分法操作后，我们得到求解误差=xc-r定义1.3　如果误差小于0.5×10-p，解精确到小数点后p位.
例1.2　用二分法求解函数f（x）=cosx-x在区间［0，1］上的解，精确到小数点后6位.
首先确定需要多少次二分才能达到需要的精度.根据公式（1.1），n次后的误差为(b-a)/2n+1=1/2n+1.参考精确到小数点后p位的定义，我们需要满足

精确到小数点后6位的估计值为0.739085.
对于二分法而言，确定迭代次数十分简单——只要确定了期望的精度就可以通过公式（1.1）计算得到必需的迭代次数.以后我们会了解到那些更有效的算法通常很难估计迭代次数和精度的关系，也不会有类似公式（1.1）这样的对应关系.在那些情况下，我们需要明确给出“结束条件”，告诉算法在什么情况下停止操作.即使对于二分法而言，计算机的算术精度也限制了解的最终精度.这个问题我们会在1.3节具体分析.
1.1节习题
1.使用中值定理找到长度为1的区间包含如下方程的根.
(a) x3=9(b) 3x3+x2=x+5(c) cos2x+6=x
2.使用中值定理找到长度为1的区间包含如下方程的根.
(a) x5+x=1(b) sinx=6x+5(c) lnx+x2=3
3.考虑习题1中的方程.使用二分法两步找到和真实解误差在1/8以内的近似解.
4.考虑习题2中的方程.使用二分法两步找到和真实解误差在1/8以内的近似解.
5.考虑方程x4=x3+10.
（a） 寻找长度为1的区间［a，b］，其中包含方程的解.
（b） 从区间［a，b］开始，二分法需要计算多少步才能让解在10-10以内？给出一个计算步数的整数结果.
6.假设二分法从区间［-2，1］开始，寻找函数f（x）=1/x的根.这种方法会收敛到一个实数吗？这个实数是根吗？29
1.1节编程问题
1.使用二分法求解方程，精确到小数点后6位.
(a) x3=9(b) 3x3+x2=x+5(c) cos2x+6=x
2.使用二分法求解方程，精确到小数点后8位.
(a) x5+x=1(b) sinx=6x+5(c) lnx+x2=3
3.使用二分法寻找下列所有方程的解.使用MATLAB的plot命令画出函数并确定三个长度为1包含解的区间.找出精确到小数点后6位的根.
(a) 2x3-6x-1=0(b) ex-2+x3-x=0(c) 1+5x-6x3-e2x=0
4.计算下列数字的平方根，要求使用二分法精确到小数点后8位，x2-A=0，其中A是（a） 2，（b） 3，（c） 5.说明开始区间以及需要的步数.
5.计算下列数字的立方根，要求使用二分法精确到小数点后8位，x3-A=0，其中A是（a） 2，（b） 3，（c） 5.说明开始区间以及需要的步数.
6.使用二分法计算方程cosx=sinx在区间［0，1］中的解，要求精确到小数点后6位.
7.使用二分法找到两个实数x，精确到小数点后6位，使得矩阵A=123x
45x6
7x89
x101112的值等于1000.对于每个找到的解，通过计算矩阵对应的值进行测试，并报告使用计算得的x矩阵的值可以具有多少准确的小数位（在小数点后）.（在1.2节，我们将把这称为“向后误差”，该误差和近似解相关.）你可以使用MATLAB命令det计算矩阵的值.
8.希尔伯特Hilbert矩阵是一个n×n矩阵，其对应的第ij个元素的值是1/（i+j-1）.令A表示5×5希尔伯特矩阵.它最大的特征值是1.567.使用二分法确定如何改变左上元素A11，使得A的最大特征值等于π.确定A11，精确到小数点后6位.可以使用MATLAB命令hilb、pi、eig和max简化计算任务.
9.寻找1m3水在一个半径为1m的球形槽中所能够达到的高度.给出你的答案误差±1mm.（提示:首先注意到球体没有半满.下面H米的半径为R的半球的体积是πH2(R-1/3H).）