admin 管理员组

文章数量: 1086019

牛顿迭代法 简单入门

引言

牛顿迭代法是在计算机编程领域广泛用来求解方程的算法。

此算法类似于二分枚举（仅仅感觉上很类似= =）
我们每次枚举一个值 X 0 X_0 X0​，代入方程看是否为根，不是的话则将 X 0 X_0 X0​的值变为：
X 0 = X 0 − F ( X 0 ) / F ′ ( X 0 ) X_0 = X_0 - F(X_0)/F'(X_0) X0​=X0​−F(X0​)/F′(X0​) （其中 F ′ ( x ) F'(x) F′(x) 为 F ( x ) F(x) F(x) 的导数）

其证明过程借用了高数中的基本知识泰勒级数，此处不再赘述。

看起来很简单对吗？事实上就是这么简单。

应用一

下面比如我们要求出下面方程的一个根：
F ( x ) = 5 x 3 + 4 x 2 + 2 F(x) = 5x^3 + 4x^2 + 2 F(x)=5x3+4x2+2

代码如下：

const double eps = 1e-6;
double F(double x){return 5*x*x*x + 4*x*x + 2;}
double F1(double x){return 15*x*x + 8*x;}       //F(x)的导函数
int newton(double x){                           //x是初始枚举值while(fabs(F(x)) > eps) x -= F(x)/F1(x);    //牛顿迭代return x;
}

如果想求出一个范围内的所有的根，则可以在该范围内枚举初始值x，来逼近根的值。

应用二

对于ACM 竞赛，牛顿迭代最重要的应用还是在于其能用于求根号。

你可能会有疑惑，求根号不是有 s q r t ( ) sqrt() sqrt() 函数吗，为什么要自己写。
这是因为可能存在下面的两种情形：

（一）高精度开根号：
51nod 1166
BZOJ 1213

对于该问题我们可以使用牛顿迭代+高精度除法。
我们以开平方根举例
对于一个已知的数 a，开根号本质上是求一个 X 0 X_0 X0​ 使得 X 0 2 = a X_0 ^2 = a X02​=a
也就是求函数
F ( x ) = x 2 − a F(x) = x^2 - a F(x)=x2−a 的根
因为 F ′ ( x ) = 2 x F'(x) = 2x F′(x)=2x

故每次迭代，x的变化值为：
x = x − ( x 2 − a ) / ( 2 x ) = ( x + a / x ) / 2 x = x - (x^2-a)/(2x) = (x+a/x)/2 x=x−(x2−a)/(2x)=(x+a/x)/2
所以再套一个高精度除法或者Java的BigInteger就好啦

//51Nod 1166
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.math.BigDecimal;
import java.math.RoundingMode;
public class Main{public static void main(String[] args) throws Exception {BufferedReader reader = new BufferedReader(new InputStreamReader(System.in), 1 << 16);String nStr = reader.readLine();BigDecimal n = new BigDecimal(nStr);BigDecimal ans = new BigDecimal(nStr.substring(0, nStr.length() / 2));BigDecimal tmp = BigDecimal.ONE;BigDecimal two = new BigDecimal("2");int length = 2;while(true){tmp = ans.add(n.divide(ans, length, RoundingMode.HALF_DOWN)).divide(two, length, RoundingMode.HALF_DOWN);if(tmp.subtract(ans).abs().compareTo(BigDecimal.ONE) == -1)break;ans = tmp;}String str = ans.toString();System.out.println(str.substring(0, str.length() - length - 1));}}

（二）底层优化
虽然 s q r t ( ) sqrt() sqrt() 已经很方便，但确实是存在比其更强大的手写算法，这个黑科技来自游戏雷神之锤3的源代码：（细节见末尾推荐文章）

int sqrt(float x) { if(x == 0) return 0; float result = x; float xhalf = 0.5f*result; int i = *(int*)&result; i = 0x5f375a86- (i>>1); // what the fuck? result = *(float*)&i; result = result*(1.5f-xhalf*result*result); // Newton step, repeating increases accuracy result = result*(1.5f-xhalf*result*result); return 1.0f/result; 
}

推荐文章：
马同学的详细讲解
百度百科
黑科技来源

本文标签： 牛顿迭代法 简单入门

版权声明：本文标题：牛顿迭代法 简单入门 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.roclinux.cn/b/1686560960a10445.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。