Halo

A magic place for coding

0%

非线性方程求解之二分法

介绍

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

分析

  ** 二分法 ** 的实现思想是通过迭代的方法来缩小有根区间,最终这个区间必收敛到一点 $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 代码:

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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
% 二分法 
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 版) 李庆扬,王能超,易大义 * 编 *

Welcome to my other publishing channels