admin管理员组

文章数量:815318

牛顿迭代法 简单入门

引言

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

此算法类似于二分枚举(仅仅感觉上很类似= =)
我们每次枚举一个值 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; 
}

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

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