牛顿法(Newton's Method)

牛顿迭代法（简称牛顿法）由英国著名的数学家牛顿爵士最早提出。

1. 原理：将目标函数f(x) 在x(k)处展开,：

若忽略二次项以上，得到：

导数：

2. 应用，求解平方根

下面介绍使用牛顿迭代法求方根的例子。牛顿迭代法是已知的实现求方根最快的方法之一,只需要迭代几次后就能得到相当精确的结果。

以math.h中sqrt(x)求平方根为例，将m = 2, 带入上式，代码如下：

const float EPS = 0.00001; int sqrt(double x) { if(x == 0) return 0; double result = x; /*Use double to avoid possible overflow*/ double lastValue; do{ lastValue = result; result = result * 0.5 + 0.5 * x / result; }while(fabs(result - lastValue) > EPS); return (double)result; }

更快的方法：

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; }

2.引申，忽略三次项以上

它可以求取函数的极值，或应用到非线性最小二乘问题(LM算法)；