轻松理解牛顿迭代法且用其求平方根 今天药忘吃喽~ 2023-01-10 14:34 407阅读 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
还没有评论,来说两句吧...