轻松理解牛顿迭代法且用其求平方根

今天药忘吃喽~ 2023-01-10 14:34 450阅读 0赞

## 牛顿迭代法概述 ##

牛顿迭代法（Newton’s method）又称为牛顿-拉弗森方法（Newton-Raphson method），它是牛顿在17世纪提出的一种在实数域和复数域上近似求解方程的方法。

## 牛顿迭代公式 ##

设 r r r是 f ( x ) = 0 f(x)=0 f(x)=0的根，选取 x 0 x\_0 x0作为 r r r的初始近似值。

过点 ( x 0 , f ( x 0 ) ) (x\_0, f(x\_0)) (x0,f(x0))做曲线 y = f ( x ) y=f(x) y=f(x)的切线 L 1 L\_1 L1， L 1 : y = f ( x 0 ) + f ′ ( x 0 ) ( x − x 0 ) L\_1:y = f(x\_0)+f'(x\_0)(x-x\_0) L1:y=f(x0)\+f′(x0)(x−x0)，则 L 1 L\_1 L1与 x x x轴交点的横坐标 x 1 = x 0 − f ( x 0 ) f ′ ( x 0 ) x\_1 = x\_0 - \\frac\{f(x\_0)\}\{f'(x\_0)\} x1=x0−f′(x0)f(x0)，称 x 1 x\_1 x1为 r r r的一次近似值。

过点 ( x 1 , f ( x 1 ) ) (x\_1, f(x\_1)) (x1,f(x1))做曲线 y = f ( x ) y=f(x) y=f(x)的切线 L 2 L\_2 L2， L 2 : y = f ( x 1 ) + f ′ ( x 1 ) ( x − x 1 ) L\_2:y = f(x\_1)+f'(x\_1)(x-x\_1) L2:y=f(x1)\+f′(x1)(x−x1)，则 L 2 L\_2 L2与 x x x轴交点的横坐标 x 2 = x 1 − f ( x 1 ) f ′ ( x 1 ) x\_2=x\_1-\\frac\{f(x\_1)\}\{f'(x\_1)\} x2=x1−f′(x1)f(x1)，称 x 2 x\_2 x2为 r r r的二次近似值。

重复以上过程，得 r r r的近似值序列，其中， x n + 1 = x n − f ( x n ) f ′ ( x n ) x\_\{n+1\}=x\_n-\\frac\{f(x\_n)\}\{f'(x\_n)\} xn\+1=xn−f′(xn)f(xn)称为 r r r的 n + 1 n+1 n\+1次近似值，上式称为**牛顿迭代公式**。

## 举个例子 ##

### 题目 ###

用牛顿迭代法求出 2 \\sqrt\{2\} 2的二次正近似值（初始近似值 x 0 = 2 x\_0=2 x0=2）。

### 解答 ###

x = 2 ⇒ x 2 − 2 = 0 x=\\sqrt\{2\}\\Rightarrow x^2-2=0 x=2⇒x2−2=0

f ( x ) = x 2 − 2 f(x)=x^2-2 f(x)=x2−2

f ′ ( x ) = 2 x f'(x)=2x f′(x)=2x

设 r r r是 f ( x ) = 0 f(x)=0 f(x)=0的正根， x 0 = 2 x\_0=2 x0=2作为 r r r的初始近似值。

f ( x ) f(x) f(x)过点 A ( 2 , f ( 2 ) ) ⇒ A ( 2 , 2 ) A(2,f(2))\\Rightarrow A(2,2) A(2,f(2))⇒A(2,2)。

过点 A A A作曲线 y = f ( x ) y=f(x) y=f(x)的切线 L 1 L\_1 L1：

L 1 : y = f ( x 0 ) + f ′ ( x 0 ) ( x − x 0 ) L\_1:y = f(x\_0)+f'(x\_0)(x-x\_0) L1:y=f(x0)\+f′(x0)(x−x0)

y = 2 + 2 ⋅ 2 ⋅ ( x − 2 ) y=2+2\\cdot2\\cdot(x-2) y=2\+2⋅2⋅(x−2)

y = 4 x − 6 y=4x-6 y=4x−6

则 L 1 L\_1 L1与 x x x轴交点的横坐标 x 1 x\_1 x1:

0 = 4 x 1 − 6 0=4x\_1-6 0=4x1−6

x 1 = 3 2 x\_1=\\frac\{3\}\{2\} x1=23

或者直接用牛顿迭代公式:

x 1 = x 0 − f ( x 0 ) f ′ ( x 0 ) = 2 − 2 2 − 2 2 ⋅ 2 = 2 − 1 2 = 3 2 x\_1=x\_0-\\frac\{f(x\_0)\}\{f'(x\_0)\}=2-\\frac\{2^2-2\}\{2\\cdot2\}=2-\\frac\{1\}\{2\}=\\frac\{3\}\{2\} x1=x0−f′(x0)f(x0)=2−2⋅222−2=2−21=23

x 1 x\_1 x1为 r r r的一次近似值。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTE4NjMwMjQ_size_16_color_FFFFFF_t_70_pic_center]

--------------------

f ( x ) f(x) f(x)过点 B ( 3 2 , f ( 3 2 ) ) ⇒ B ( 3 2 , 1 4 ) B(\\frac\{3\}\{2\}, f(\\frac\{3\}\{2\}))\\Rightarrow B(\\frac\{3\}\{2\},\\frac\{1\}\{4\}) B(23,f(23))⇒B(23,41)。

过点 B B B作曲线 y = f ( x ) y=f(x) y=f(x)的切线 L 2 L\_2 L2：

L 2 : y = f ( x 1 ) + f ′ ( x 1 ) ( x − x 1 ) L\_2:y = f(x\_1)+f'(x\_1)(x-x\_1) L2:y=f(x1)\+f′(x1)(x−x1)

y = 1 4 + 2 ⋅ 3 2 ⋅ ( x − 3 2 ) y=\\frac\{1\}\{4\}+2\\cdot\\frac\{3\}\{2\}\\cdot(x-\\frac\{3\}\{2\}) y=41\+2⋅23⋅(x−23)

y = 3 x − 17 4 y=3x-\\frac\{17\}\{4\} y=3x−417

则 L 2 L\_2 L2与 x x x轴交点的横坐标 x 2 x\_2 x2:

0 = 3 x 2 − 17 4 0=3x\_2-\\frac\{17\}\{4\} 0=3x2−417

x 2 = 17 12 = 1.4166666 6 ˙ x\_2=\\frac\{17\}\{12\}=1.4166666\\dot\{6\} x2=1217=1.41666666˙

或者直接用牛顿迭代公式:

x 2 = x 1 − f ( x 1 ) f ′ ( x 1 ) = 3 2 − ( 3 2 ) 2 − 2 2 ⋅ 3 2 = 3 2 − 1 12 = 17 12 x\_2=x\_1-\\frac\{f(x\_1)\}\{f'(x\_1)\}=\\frac\{3\}\{2\}-\\frac\{(\\frac\{3\}\{2\})^2-2\}\{2\\cdot \\frac\{3\}\{2\}\}=\\frac\{3\}\{2\}-\\frac\{1\}\{12\}=\\frac\{17\}\{12\} x2=x1−f′(x1)f(x1)=23−2⋅23(23)2−2=23−121=1217

x 2 x\_2 x2为 r r r的二次近似值。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTE4NjMwMjQ_size_16_color_FFFFFF_t_70_pic_center 1]

综上所述， 2 \\sqrt\{2\} 2的二次正近似值为 17 12 = 1.4166666 6 ˙ \\frac\{17\}\{12\}=1.4166666\\dot\{6\} 1217=1.41666666˙。

## 用牛顿迭代法求平方根的Java程序实现 ##

假设你想用程序实现求出 a a a的正平方根。

已知三个公式：

1.  牛顿迭代公式  x n + 1 = x n − f ( x n ) f ′ ( x n ) x\_\{n+1\}=x\_n-\\frac\{f(x\_n)\}\{f'(x\_n)\} xn\+1=xn−f′(xn)f(xn)
2.   f ( x ) = x 2 − a f(x)=x^2-a f(x)=x2−a
3.   f ′ ( x ) = 2 x f'(x)=2x f′(x)=2x

由三个公式可得：

x n + 1 = x n − x n 2 − a 2 x n x\_\{n+1\}=x\_n-\\frac\{x\_n^2-a\}\{2x\_n\} xn\+1=xn−2xnxn2−a

x n + 1 = x n 2 + a 2 x n x\_\{n+1\}=\\frac\{x\_n^2+a\}\{2x\_n\} xn\+1=2xnxn2\+a

x n + 1 = x n + a x n 2 x\_\{n+1\}=\\frac\{x\_n+\\frac\{a\}\{x\_n\}\}\{2\} xn\+1=2xn\+xna

因此，容易编写出以下程序：

public class Sqrt { 
        public static void main(String[] args) { 
            System.out.println(sqrt(2));
        }
    
        private static double sqrt(double a) { 
            if (num < 0)
                throw new IllegalArgumentException();
            double err = 1E-15;
            double cur = a;
            while (Math.abs(a - cur * cur) > err)//精度越来越高
                cur = (cur + a / cur) / 2;
            return cur;
        }
    }

## 参考资料 ##

1.  [牛顿迭代法\_百度百科][Link 1]
2.  [如何通俗易懂地讲解牛顿迭代法求开方？数值分析？ - 知乎][-]
3.  [牛顿迭代法快速寻找平方根][Link 2]
4.  [牛顿求根法][Link 3]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTE4NjMwMjQ_size_16_color_FFFFFF_t_70_pic_center]: /images/20221119/7f8ca19ddd7e445f96ba0094e3a5858f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTE4NjMwMjQ_size_16_color_FFFFFF_t_70_pic_center 1]: https://img-blog.csdnimg.cn/20210125161240295.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTE4NjMwMjQ=,size_16,color_FFFFFF,t_70#pic_center
[Link 1]: https://baike.baidu.com/item/%E7%89%9B%E9%A1%BF%E8%BF%AD%E4%BB%A3%E6%B3%95/10887580?fr=aladdin
[-]: https://www.zhihu.com/question/20690553
[Link 2]: http://www.matrix67.com/blog/archives/361
[Link 3]: https://www.bilibili.com/video/BV1Nt411T7HT