牛顿法求解方程

摘要

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

二分法

以前初中学习平方根的时候，就在思考这个问题。如何计算正实数的平方根，每次在计算的时候心里默念几的平方等于这个数。比如25=5^2,那么26怎么办呢？数学家实在太聪明了，用\sqrt{26}来表示这个数。但是这个带根号的数，似乎不是很直观，具体落在那个范围之内还是很难估计。
于是我还是使用这种笨办法，不断尝试法。比如6^2=36,而26介于5和6的平方之间，因此取区间[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) = x^2 – p, 带入迭代公式得到：

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

通过四次迭代计算基本上可以得到比较理想的解了。
给出测试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，带入迭代公式中得到：

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

推广求解一般方程

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

总结

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