非线性方程求解之牛顿法

介绍

之前我介绍了使用二分法求解一个非线性方程，今天，我就来介绍另一种方法–牛顿法。

分析

牛顿法的核心思想是将非线性问题转化为线性问题处理。对于非线性方程$f(x)=0$，假设已知有近似根$x_k$（假定$f^{‘}(x_k) \ne 0$）,将函数$f(x)$在点$x_k$进行泰勒展开，有
$$
f(x) \approx f(x_k) + f^{‘}(x_k)(x-x_k)，
$$
于是方程$f(x) = 0$可以近似地表示为
$$
f(x_k) + f^{‘}(x_k)(x-x_k) = 0,
$$
上面这个是一个线性方程，记其根为$x_{k+1}$，则求得$x_{k+1}$的计算公式为：
$$
x_{k+1} = x_k - \frac{f(x_k)}{f^{‘}(x_k)},
$$
以上的迭代方法就称为牛顿法。

代码实现

Matlab代码：

% 牛顿法
function [y, count, error, time] = Newton(x, e)
    % y为最终结果
    % x为开始迭代的初始坐标
    % e为迭代精度

    del_x = 0.0000001; % 用于求函数导数值的极小量
    count = [];% 输出迭代次数的数组
    time = []; % 输出迭代时间的数组
    error = [];% 输出误差的数组
    k = 0; % 迭代次数变量
    err = 0;% 误差变量
    y = x;
    x = y + 1000; % 保证迭代能开始
    n = 50; % n为最大迭代次数
    tic
    while 1
        if (abs(y-x) <= e)
            disp('满足迭代精度');
            break;
        elseif (k > n)
            disp('迭代次数过多，迭代结束');
            break;
        else
            x = y;
            if((myFun(x+del_x) - myFun(x)) == 0)
                disp('导数为0');
                break;
            else
                y_deriv = (myFun(x+del_x) - myFun(x)) / del_x; %x点的导数值
                y = x - myFun(x) / y_deriv; % 牛顿迭代
                k = k + 1; %迭代次数加1
                count(k) = k;
                err = abs(y-x) / y;
                error(k) = err;
            end
        end
    end
    toc

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

    disp('牛顿迭代结束');
end


function [y] = myFun(x)
y = x*x - 115;
end