非线性方程求解之二分法

介绍

  当我们对一个非线性方程进行求根的时候，一般采用的是迭代法，通过迭代法的收敛性质，最终求得一个逼近精确解的近似解。这里介绍的是其中一种方法–二分法。

分析

  二分法的实现思想是通过迭代的方法来缩小有根区间，最终这个区间必收敛到一点$x^*$，这点就是我们要求的根。在我们实际求解的过程中，没有必要求出这一点$x^*$，我们只需要确定一个误差范围，让这个有根区间的长度小于这个误差即可。
  二分法的核心是如何确定有根区间，首先给出一个较大的有根区间，然后通过不断地二分，通过比对端点值与中点值得正负，来判断根所在的区间。下面给出算法步骤：
① 准备：计算$f(x)$在有根区间$[a,b]$端点处的值$f(a)$，$f(b)$。
② 二分：计算$f(x)$在区间中点$\frac{a+b}{2}$处的值$f(\frac{a+b}{2})$
③ 判断：若$f(\frac{a+b}{2})$ = 0，则$\frac{a+b}{2}$就是该非线性方程的根，计算结束，否则检验；若$f(\frac{a+b}{2})f(a)$ < 0，则以$\frac{a+b}{2}$代替$b$成为区间上界，否则以$\frac{a+b}{2}$代替$a$成为区间下界。
重复执行步骤②和步骤③，直至计算结束或区间长度小于规定的误差，此时中点$\frac{a+b}{2}$为所求的近似根。

代码实现

Matlab代码：

% 二分法
function [y, count, error, time] = dichotomy(a, b)
format long;
count = []; %输出迭代次数的数组
error = []; %输出误差的数组
time = []; % 输出迭代时间的数组
err = 0; % 误差变量
k = 0; % 迭代次数变量
e = 0.000001; % 精度控制

x = (a + b) / 2;
f1 = myFun(a);
f2 = myFun(b);
fx = myFun(x);
y = a;

if (fx == 0)
    y = x;
end

tic
while (b-a) > (2*e)
    fx = myFun(x);
    % 得出精确解
    if (fx == 0)
      y = x;
      break;
    elseif (f1 * fx < 0)
        b = x;
        f2 = fx;
    else
        a = x;
        f1 = fx;
    end
    y_old = y;
    y = x;
    k = k + 1;
    count(k) = k;
    x = (a + b) / 2;
    err = abs(y-y_old)/y;
    error(k) = err;
end
toc

% 均分时间间隔
temp = toc / k;
for i=1:k
    time(i) = i*temp;
end

end

% 求解函数
function [y] = myFun(x)
y = x*x - 115;
end

小结

  二分法的思想很简单，实现起来也很方便，而且我们总是可以找到收敛的一个点，但其缺点是收敛速度过慢，在计算复杂的数据的时候会花费大量的时间。因此一般不单独使用二分法去求根。

---

参考资料：

1.数值分析（第5版） 李庆扬，王能超，易大义 编