对分法 Bisection

即两分法, 二分法.

其实最初接触到的二分法是用于查找具有某种单调性质的数列. 不过本质是一样的.

% 初始化参数
l = 2; % 区间左端点
r = 4; % 区间右端点
tol = 1e-2; % 允许误差

% 迭代求解
fl = myFunc(l); % 计算函数值
fr = myFunc(r); % 计算函数值

% x和m需要有初始值, 并且一定要大于tol
x = l;
m = r;
fprintf('正在赋值给初始变量......\n');
times = 1;

while abs(x - m) > tol
    x = m; % 存储当前即上一步的x的值
    m = (l + r) / 2; % 求出区间中点
    fm = myFunc(m); % 计算middle函数值
    if sign(fm) == sign(fl) % 根在右半区间
        l = m;
        fl = fm;
    else % 根在左半区间
        r = m;
        fr = fm;
    end
    fprintf('第%d次迭代结束, 最新根m = %.5f, 次新根x = %.5f\n', times, m, x);
    times = times + 1;
end

% 输出结果
root = m;
fprintf('方程 x + 5sin(x) - 1 = 0 的根在区间 [2,4] 内为: %.4f\n', root);

% 定义函数
function y = myFunc(x)
    y = x + 5 * sin(x) - 1;
end

迭代法 Iterative

根据所求方程构建迭代式. 每次使用迭代式修正结果, 直至两次相邻结果相差小于某个值.

迭代法需要证明迭代式是收敛的.

% 初始化参数
x0 = 0; % 区间左端点
x1 = 1; % 区间右端点
eps = 1e-5; % 允许误差

times = 1;
% 迭代求解
xn1 = (x0 + x1) / 2; % 由左右端点来初始化迭代变量
fprintf('初始化迭代变量为%.8f\n', xn1);
fprintf('开始进行第%d次迭代......\n', times);
xn = toBesolved(xn1); % 第一次迭代
fprintf('第%d次迭代结果为%.8f\n', times, xn);
% 每次的xn都是新迭代结果

while abs(xn - xn1) > eps % 判断是否达到精度要求
    times = times + 1;
    xn1 = xn; % 更新迭代变量
    xn = toBesolved(xn1); % 进行迭代计算
    fprintf('第%d次迭代结果为%.8f\n', times, xn);
end

% 输出结果
fprintf('方程x+5sinx-1=0在区间[2,4]内的一个根为：%.8f\n', xn);

% 定义迭代函数
function xn = toBesolved(xn1)
    xn = (2 * xn1 + 5) ^ (1/3);
end

steffensen加速算法

在朴素迭代法及其加速的基础上增加两点:

补偿误差.
避免求导.

$$ \left\{ \begin{gather} y_k = g(x_k) \\ z_k = g(y_k) \\ \end{gather} \right . $$

由上面两个式子对迭代进行补偿.

再由下面的计算公式避免求导直接加速.

$$ \begin{gather} x_{k+1} = x_k - \frac {(y_k - x_k) ^ 2} {z_k - 2y_k + x_k} \\ \end{gather} $$

得到 steffensen加速迭代法.

x0 = 1.5; % 定义一个迭代初始值
eps = 1e-5;

% 下面开始第一次迭代
times = 1;
y = toBesolved(x0);
z = toBesolved(y);
x = x0 - (y - x0) ^ 2 / (z - 2 * y + x0);
fprintf('第%d次迭代结束. x=%.8f, y=%.8f, z=%.8f\n', times, x, y, z);

while abs(x - x0) > eps
    x0 = x; % 存储上一步的x.
    times = times + 1;
    y = toBesolved(x);
    z = toBesolved(y);
    x = x - (y - x) ^ 2 / (z - 2 * y + x);
    fprintf('第%d次迭代结束. x=%.8f, y=%.8f, z=%.8f\n', times, x, y, z);
end

% 定义迭代函数
function gx = toBesolved(x)
    gx = x ^ 3 - 1;
end

牛顿法

迭代式的构造会影响收敛速度. 甚至影响是否收敛.

牛顿法提出了一种迭代式的结构. 是否收敛依赖于 x0的选取.

$$ \begin{gather} x_{k+1} = x_k - \frac {f(x_k)} {f^{'}(x_k)} \end{gather} $$

牛顿法也被称为切线法.

x0 = 1; % 定义一个迭代初始值
eps = 1e-5;

% 下面开始第一次迭代
times = 1;
x = x0 - f(x0) / df(x0);
fprintf('第%d次迭代结束. x=%.8f\n', times, x);

while abs(x0 - x) > eps
    x0 = x;
    times = times + 1;
    x = x - f(x) / df(x);
    fprintf('第%d次迭代结束. x=%.8f\n', times, x);
end

% 定义函数和导数
function fx = f(x)
    fx = x ^ 3 + 2 * x ^ 2 + 10 * x - 20;
end

function dfx = df(x)
    dfx = 3 * x ^ 2 + 4 * x + 10;
end

显然牛顿法也无法避免求导, 所以我们可以有更加优化的算法.

割线法

牛顿法的改进. 用差商代替导数.

割线法是二步格式, 收敛速度比 Newton迭代法慢.

$$ \begin{gather} x_{k+1} = x_k - \frac {f(x_k)} {\frac {f(x_k) - f(x_{k-1})} {(x_k - x_{k-1}) }} \end{gather} $$

x00 = 1; % 定义两个迭代初始值
x0 = 2;
eps = 1e-5;

% 下面开始第一次迭代
times = 1;
x = x0 - f(x0) * (x0 - x00) / (f(x0) - f(x00));
fprintf('第%d次迭代结束. x=%.8f\n', times, x);

while abs(x0 - x) > eps
    x00 = x0;
    x0 = x;
    times = times + 1;
    x = x0 - f(x0) * (x0 - x00) / (f(x0) - f(x00));
    fprintf('第%d次迭代结束. x=%.8f\n', times, x);
end

% 定义函数和导数
function fx = f(x)
    fx = x - sin(x) - 0.5;
end

『matlab』使用二分法和迭代法求解方程