牛顿法求解方程

摘要

本文简述牛顿法求算术平方根,进而推导出求一个数的n次方根,尝试推到出一般n次方程的数值解,并给出相应的代码实现。

二分法

以前初中学习平方根的时候,就在思考这个问题。如何计算正实数的平方根,每次在计算的时候心里默念几的平方等于这个数。比如25=5^2,那么26怎么办呢?数学家实在太聪明了,用\sqrt{26}来表示这个数。但是这个带根号的数,似乎不是很直观,具体落在那个范围之内还是很难估计。
于是我还是使用这种笨办法,不断尝试法。比如6^2=36,而26介于56的平方之间,因此取区间[5,6]的中点计算5.5^2=30.25>26发现还是大了,再取区间[5,5.5]的中点5.25^2=27.5625>26,于是我们再取[5,5.25]区间的中点,计算5.125^2=26.265625>26,于是取区间[5,5.125]的中点计算,以此计算下去直到非常接近26为止。多年以后发现,原来这就是二分法。

牛顿迭代法

大牛(牛顿)看了以后,这种方法虽然简单,但是low了一点,需要反复计算那么多次才能达到比较理想的解,于是牛顿迭代法这样出来了。

先考虑平方根问题,f(x)=x^2 – p(p>0),那么函数的零点就是p的算术平方根。

假设f(x)在点(x_n, f(x_n))的切线与x轴的交点为x_{n+1},于是根据斜率得到:

f'(x_n) = \frac{f(x_n) – 0}{x_n – x_{n+1}}

得到迭代公式:

x_{n+1} = x_n – \frac{f(x_n)}{f'(x_n)}

对于f(x) = x^2 – p, 带入迭代公式得到:

x_{n+1} = x_n – \frac{x_n^2 – p}{2 x_n} = \frac{1}{2}(x_n + \frac{p}{x_n})

现在我们开始计算\sqrt{26}的值,此时p=26,初始迭代值x_1 = 1,于是计算

x_2 = \frac{1}{2}(x_1 + \frac{26}{x_1}) = 13.5 \\
x_3 = \frac{1}{2}(x_2 + \frac{26}{x_2}) = 7.713 \\
x_4 = \frac{1}{2}(x_3 + \frac{26}{x_3}) = 5.542 \\
x_5 = \frac{1}{2}(x_4 + \frac{26}{x_4}) = 5.117

通过四次迭代计算基本上可以得到比较理想的解了。
给出测试Java代码:

package com.learn;

public class SimpleTest {
    public static double NewTonMethod(double x) {
        double eps = 2e-50;
        double x0 = 2;
        double res = 1;

        while (abs(res - x0) > eps) {
            x0 = res;
            res = 1.0 / 2 * (x0 + x / x0);  // 平方根
            System.out.println(res);
        }

        return res;
    }

    public static double abs(double x) {
        return x > 0 ? x : -x;
    }

    public static void main(String[] args) {
        // 牛顿法求解算术平方根
        System.out.println(NewTonMethod(26));
    }
}

程序输出为:

13.5
7.712962962962963
5.541955671157352
5.116720163987656
5.099050130180595
5.099019513684702
5.0990195135927845
5.0990195135927845
5.0990195135927845

推广到n次根式的求解

其实就是构造函数f(x) = x^n – p,这里考虑n \ge 2, p > 0,带入迭代公式中得到:

x_{k+1} = x_k – \frac{f(x_k)}{f'(x_k)} = x_k – \frac{x_k ^n-p}{n x_k^{n-1}},x_1=t

收敛的条件设为迭代前后的值相差给定的很小数\epsilon,即:

|x_{n+1} – x_n| < \epsilon

推广求解一般方程

前面构造f(x) = x^2 – p,求解方程的根,此处可以进一步推广一般方程f(x)=0的情况,在x_0附近的根,无论函数的形式如何。

总结

牛顿迭代法也存在不足之处,在使用迭代之前必须制定迭代初始值,也就是只能求出初始值附近的根,无法求解出函数所有的根,个人认为这是牛顿法最大的局限。

关注机器学习和算法的码农,喜欢编程和读书
文章已创建 74

一个回复在 “牛顿法求解方程

发表评论

电子邮件地址不会被公开。

相关文章

开始在上面输入您的搜索词,然后按回车进行搜索。按ESC取消。

返回顶部