图

二分法

   二分法 是数值计算中一种求连续一元函数零点的简单方法. 先来看一个显然的结论: 如果我们知道一个连续函数在某个开区间左端的值和右端的值(假设都不为 0)乘积小于 0(即正负号不同), 那么这个函数在该区间内必有至少一个根. 为了进一步缩小这个根所在的区间, 我们在区间中点求函数值, 如果中点处的函数值与区间左端的函数值同号(相乘大于 0), 则函数的根必然在区间中点和区间右端之间, 于是我们可以把区间左端移动到区间中点处, 再来求新区间的中点. 如果区间中点的函数值与区间右端的函数值同号, 同理我们也可以把区间右端移动到区间中点处得到新的区间. 如果区间中点的函数值恰好为 0, 我们便找到了一个根, 另一方面, 如果区间的长度小于我们对根的精度的要求, 那么我们就找到了一个根的近似值.

   Matlab 中自带的 fzero 函数如果按照以下格式使用, 大致可以认为是二分法

1
2
3
>> f = @(x)x-1;
>>fzero(f, [0,2])
ans = 1
fzero 的默认精度是 2.2e-16. 注意要把一个函数作为其他函数的输入变量, 必须使用函数句柄. 下面我们给出一个二分法的 Matlab 程序.

  bisection.m

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
% 二分法求函数的根
function x = bisection(f, int, err)
fl = f(int(1)); fr = f(int(2));
% 两端点是否为 0
if fl == 0
    x = int(1); return;
elseif fr == 0
    x = int(2); return;
end
% 两端点是否同号
if fl * fr > 0
    error('两端点同号');
end
% 主循环
while(int(2) - int(1) > err)
    mid = 0.5*(int(1) + int(2));
    fm = f(mid);
    if fm * fl > 0
        int(1) = mid;
    elseif fm * fr > 0
        int(2) = mid;
    else % fm = 0
        break;
    end
end
x = mid;
end

   我们先来看函数的自变量, 与 fzero 类似, 该函数的前两个输入变量分别是函数句柄和求根区间, 第三个变量是误差值, 当区间的长度小于 err 时, 函数将输出区间中点作为输出. 函数的第 3-13 行做了一些必要的检查, 确保区间两端的函数值为异号. 第 15 行开始主循环, 每循环一次, 函数的区间长度减半, 直到区间中点处的函数值为 0 或区间长度小于 err 时跳出循环, 最后返回区间中点的函数值.

致读者: 小时物理百科一直以来坚持所有内容免费且不做广告,这导致我们处于日渐严重的亏损状态。长此以往很可能会最终导致我们不得不选择商业化,例如大量广告,内容付费,会员制,甚至被收购。因此,我们鼓起勇气在此请求广大读者热心捐款,使网站得以健康发展。如果看到这条信息的每位读者能慷慨捐助 10 元,我们几天内就能脱离亏损状态,并保证网站能在接下来的一整年里向所有读者继续免费提供优质内容。感谢您的支持。
—— 小时(项目创始人)

编辑词条 返回目录 返回主页 捐助项目 © 小时物理百科 保留一切权利