【算法】牛顿迭代法求平方根及多次方根

1. 概述

$牛顿迭代法$ 是非常高效的求解方程的根的方法。其求解原理可以参考各文献。大体的思路如下：

通过不断地做切线来逼近真实的根，直到误差小于精度。

可得迭代公式：

$x_{n+1}=x_n-\frac{f(x_n)}{f^{\prime }(x_n)}$

 
通过这种不断地做切线的方法，直到 $|x_n-x_{\ast }|<给定的精度$，在误差范围内可以认为 $x_n$ 就是方程的根了。

2. 牛顿法求平法根

假设我们要求解n的平方根，那么我们可以构建函数 $f(x)=x^2-n$。

那么方程 $x^2-n=0$ 的理论根为 $x=\sqrt{n}$ ，即求解这个方程得到的根就是求的n的平方根。

例如求5的平方根，那么可以构建函数 $f(x)=x^2-5$，方程 $x^2-5=0$ 的理论根即为 $\sqrt{5}$，在误差范围内，用牛顿法求解出方程 $x^2-5=0$ 的根即可认为是5的平方根。

迭代公式

构建函数

$f(x)=x^2-n$

 
那么有：

$f^{\prime }(x)=2x$

 
根据牛顿法的迭代公式有：

$x_{n+1}=x_n-\frac{f(x_n)}{f^{\prime }(x_n)}$
$=x_n-\frac{x_n^2-n}{2x_n}$
 
$=\frac{x_n+n/x_n}{2}$

 
代码

/**
 * @author allen
 * @date 2022/9/19
 */
public class Main2 {
    public static void main(String[] args) {
        double n = 987654321;
        double x = 0.0000001;
        double res = sqrt(n, x);
        System.out.println(res);
    }

    public static double sqrt(double n, double x) {
        double k = n / 2;
        while (Math.abs(k * k - n) > x) {
            k = (k + n / k) / 2;
        }
        return k;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

 
Python3库函数求平方根验证

可见，误差在给定的范围内。

 

3. 牛顿法求多次方根

跟求平方根同理，只是构建的函数不同，例如求解m次方根，那么就需要构建函数

$f(x)=x^m-n$

 
那么就有：

$f^{\prime }(x)=m\ast x^{m-1}$

 
根据牛顿法的迭代公式有：

$x_{n+1}=x_n-\frac{f(x_n)}{f^{\prime }(x_n)}$
 
$=x_n-\frac{x_n^m-n}{m\ast x_n^{m-1}}$

 
例如求解n的3次方根，那么就有：

$x_{n+1}=x_n-\frac{x_n^3-n}{3\ast x_n^2}$

 
代码

package cn.pku.edu.algorithm;

/**
 * @author allen
 * @date 2022/9/19
 */
public class Main2 {
    public static void main(String[] args) {
        double n = 123456789;
        double x = 0.0000001;
        double res = sqrt3(n, x);
        System.out.println(res);
    }

    public static double sqrt3(double n, double x) {
        double k = n / 3;
        double k2, k3;
        do {
            k2 = k * k;
            k3 = k2 * k;
            k = k - (k3 - n) / (3 * k2);
        } while (Math.abs(k * k * k - n) > x);
        return k;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

 
Python3验证123456789开3次方的结果为

可见，误差被控制在给定的范围内。

 

参考文献

[1] 牛顿迭代法.