非线性方程求解之牛顿法

介绍

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

分析

牛顿法的核心思想是将非线性问题转化为线性问题处理。对于非线性方程 $f (x) = 0$ ，假设已知有近似根 $x_{k}$ （假定 $f^{‘} (x_{k}) \neq 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