非线性方程二分法

这篇具有很好参考价值的文章主要介绍了非线性方程二分法。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

非线性方程二分法

优点：算法直观、简单、总能保证收敛；局限：收敛速度慢、一般不单独用它求根，仅为了获取根的粗略近似

1 二分法基本思想

设 $f (x)$ 在 $[a, b]$ 上连续、严格单调、满足条件
$f (a) f (b) < 0$
则在区间 $[a, b]$ 内必有一根 $x^*$ 。通过反复对分有根区间，以极限思想求解出非线性方程的数值解。具体步骤如下：

取 $[a, b]$ 的中点 $x_0=(a+b)/2$ ，计算 $f(x_0)$ ，当
- $f(a)f(x_0)<0$ ，则令 $a_1=a,b_1=x_0$ ;
- $f(x_0)f(b)<0$ ，则令 $a_1=x_0,b_1=b$ ;

通过重复上述步骤，得到一系列有根区间
$[a,b]\supset [a_1,b_1]\supset[a_2,b_2]\supset\dots \supset\dots$
由于后一个区间长度是前一个区间的一半，通过递归公式求解出区间长度的通项公式
$b_k-a_k=\frac{b-a}{2^k}$
当 $k\to \infty$ 时， $||b_k-a_k||\to0$ ，此时序列 $\{a_k\},\{b_k\},\{x^k\} \to x^*$ ，其中
$x^*=\frac{a_k+b_k}{2}$
由于方程根和中点间的距离真包含于 $a_k,b_k]$ ，故收敛速度
$0\le|x^*-x_k|\le(b_k-a_k)/2=(b-a)/2^{k+1}$
当 $k\to \infty$ 时，利用夹逼定理
$\mathop {\lim }\limits_{k\to \infty}0 \le \mathop {\lim }\limits_{k\to \infty}|x^*-x_k|\le\mathop {\lim }\limits_{k\to \infty}(b-a)/2^{k+1}=0$
故有 $x^k\to x^*$ 。给定终止条件 $\varepsilon$ ，当
$(b-a)/2^{k+1}<\varepsilon$
时，可求出满足精度 $\varepsilon$ 的最少二分次数 $k$ 。

2 二分法实现

求解：
$f(x)=2^x+x-2$

function[xstar,index,it] = bisect(fun,a,b,ep)
% 非线性方程二分法
% fun为目标函数
% a,b为初始区间
% ep为精确度，当(b-a)/2<ep循环结束，迭代失败输出两端点函数值
% index指标变量，index = 1，迭代成功，index  = 0表明初始区间不是有根区间
% it迭代次数
if nargin < 4
    ep = 1e-5;
end
fa = feval(fun,a); %计算a处的函数值
fb = feval(fun,b); %计算b处的函数值
if fa*fb>0
    xstar = [fa,fb];
    index = 0;
    it = 0;
    return
end
k = 0;
while abs(b-a)/2 >= ep
    x = (a+b)/2;
    fx = feval(fun,x);
    if fx*fa<0
        b = x;fb = fx;
    else
        a = x;fa = fx;
    end
    k = k +1;
end
xstar = (a+b)/2;index = 1;it = k
%具体函数
function f = fun1(x)
%测试函数
f = 2^x+x-2;  %任意可改
end

format long
[xstar,index,it] = bisect(@fun1,0,2,0.0000001)