二分法（Matlab 示例）

贡献者： addis

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

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

>> f = @(x)x-1;
>>fzero(f, [0,2])
ans = 1

% 二分法求函数的根
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 时跳出循环，最后返回区间中点的函数值。