二分法也称对分区间法、对分法等，是最简单的求根方法，属于区间法求根类型。
利用连续函数零点定理，将含根区间逐次减半缩小构造点列来逼近根。
设连续函数 f ( x ) f(x) f(x)在 [ a , b ] [a,b] [a,b]只有一个根，满足 f ( a ) f ( b ) < 0 f(a)f(b)<0 f(a)f(b)<0。
记第
k
k
k次二分得到的含根区间为
I
k
=
[
a
k
,
b
k
]
I_k=[a_k,b_k]
Ik=[ak,bk]，则二分法对应的求根数列算式为
x
k
=
0.5
(
a
k
+
b
k
)
x_k=0.5(a_k+b_k)
xk=0.5(ak+bk)
由于
x
∗
∈
I
k
,
k
=
0
,
1
,
⋯
⇒
I
0
⊃
I
1
⊃
I
2
⋯
x^*\in I_k,k=0,1,\cdots \Rightarrow I_0\supset I_1\supset I_2\cdots
x∗∈Ik,k=0,1,⋯⇒I0⊃I1⊃I2⋯
因此
∣
x
∗
−
x
k
∣
≤
1
2
(
b
k
−
a
k
)
=
1
2
2
(
b
k
−
1
−
a
k
−
1
)
=
⋯
=
1
2
k
+
1
(
b
−
a
)
|x^*-x_k|\le\frac12(b_k-a_k)=\frac{1}{2^2}(b_{k-1}-a_{k-1})=\cdots =\frac{1}{2^{k+1}}(b-a)
∣x∗−xk∣≤21(bk−ak)=221(bk−1−ak−1)=⋯=2k+11(b−a)
故
1
2
k
+
1
(
b
−
a
)
→
0
⇒
x
k
→
x
∗
\frac{1}{2^{k+1}}(b-a)\to 0\Rightarrow x_k\to x^*
2k+11(b−a)→0⇒xk→x∗
由于
∣
x
∗
−
x
k
∣
≤
1
2
k
+
1
(
b
−
a
)
|x^*-x_k|\le \frac{1}{2^{k+1}}(b-a)
∣x∗−xk∣≤2k+11(b−a)
对给定的计算精度
ϵ
>
0
\epsilon\gt 0
ϵ>0，要成立
∣
x
∗
−
x
k
∣
<
ϵ
|x^*-x_k|\lt\epsilon
∣x∗−xk∣<ϵ ，让
1
2
k
+
1
(
b
−
a
)
≤
ϵ
⇒
k
>
ln
(
b
−
a
)
−
ln
ϵ
ln
2
−
1
\frac{1}{2^{k+1}}(b-a)\le \epsilon\Rightarrow k\gt\frac{\ln(b-a)-\ln\epsilon}{\ln2}-1
2k+11(b−a)≤ϵ⇒k>ln2ln(b−a)−lnϵ−1
即满足精度要求的二分次数为
k
>
ln
(
b
−
a
)
−
ln
ϵ
ln
2
−
1
k\gt\frac{\ln(b-a)-\ln\epsilon}{\ln2}-1
k>ln2ln(b−a)−lnϵ−1
又由于
∣
b
k
−
a
k
∣
=
2
∣
x
k
−
x
k
−
1
∣
⇒
∣
x
∗
−
x
k
∣
≤
∣
x
k
−
x
k
−
1
∣
|b_k-a_k|=2|x_k-x_{k-1}|\Rightarrow |x^*-x_k|\le|x_k-x_{k-1}|
∣bk−ak∣=2∣xk−xk−1∣⇒∣x∗−xk∣≤∣xk−xk−1∣
于是，满足精度的根可取使
∣
x
k
−
x
k
−
1
∣
≤
ϵ
|x_k-x_{k-1}|\le\epsilon
∣xk−xk−1∣≤ϵ成立的
x
k
x_k
xk 。
事先估计：
k
>
ln
(
b
−
a
)
−
ln
ϵ
ln
2
−
1
k\gt\frac{\ln(b-a)-\ln\epsilon}{\ln2}-1
k>ln2ln(b−a)−lnϵ−1
事后估计：
∣
x
∗
−
x
k
∣
≤
∣
x
k
−
x
k
−
1
∣
|x^*-x_k|\le|x_k-x_{k-1}|
∣x∗−xk∣≤∣xk−xk−1∣
事先估计的
k
k
k往往偏大，主要用于理论估计。
事后估计的
k
k
k往往较小，主要用于实际控制。
用二分法求方程 2 x 3 − 5 x − 1 = 0 2x^3-5x-1=0 2x3−5x−1=0在区间 [ 1 , 2 ] [1,2] [1,2]内的根，绝对误差 ϵ ≤ 1 0 − 2 \epsilon\le10^{-2} ϵ≤10−2。
% 二分法求方程在[a,b]区间、误差小于等于epsilon下的近似根
function result = dichotomy(epsilon,a,b)
f=@(x)2*x^3-5*x-1;
m=(a+b)/2;
while ~(abs(a-b)<epsilon || f(m)==0)
m = (a+b)/2;
if f(a)*f(m) < 0
b = m;
else
a = m;
end
end
result = (a+b)/2;
fprintf("近似解为：%.6f",result);
end
因篇幅问题不能全部显示，请点此查看更多更全内容