牛顿勘根法的定义

牛顿勘根法（牛顿迭代法）求方程的解。是完全仰仗天才的直觉而发现的求解方程的策略。

求解方程 f(x) = 0 在几何意义上就是求函数 y = f(x) 与 x =0 的交点。

牛顿勘根法的几何图示

首先选择一个接近函数 f(x) 的零点 x0，计算相应的 f(x0) 的切线斜率 f'(x0)； 然后计算穿过点 (x0, f(x0)) 并且斜率为 f'(x0) 的直线与x轴的交点的x坐标，也就是求下面方程的解：

或者更加一般化的表达式：

将新得到的点的x坐标名为x1， 通常 x1 会比 x0 更接近方程 f(x) = 0 的解，由此，我们现在可以利用 x1 开始下一轮的迭代，迭代公式简化为：

算法的Javascript实现

从上一步”牛顿勘根法“的迭代公式：

迭代求根公式

从 Xn 演化到 Xn-1，很容易看出是"不动点公式”，帮你精通JavaScript：不动点函数求任何方程的解

由此，先写一个不动点的方程：

let tolerance = 0.00001;function fixed_point(f, first_guess) {    function close_enough(x, y) {        return abs(x - y) < tolerance;    }    function try_with(guess) {        let next = f(guess);        return close_enough(guess, next) ? next               : try_with(next);    }    return try_with(first_guess);}

然后，在根据求导公式的定义，写出微分求导方程：

求导公式的定义

let dx = 0.00001;function deriv(f) {    return x => (f(x + dx) - f(x)) / dx;}

在求导公式的基础上，便能写出将普通函数写成“不动点函数的”转换公式：

function newton_transform(g) {  return x => x - g(x) / deriv(g)(x);}

综上所述，抽象出来最终的解法：

 function fixed_point_of_transform(g, transform, guess) {    return fixed_point(transform(g), guess);}

验证求平方根sqrt：

function sqrt(x) {    return fixed_point_of_transform(               y => y**2- x,               newton_transform,               1);}sqrt(6);//  2.4494897427970397

我们最后得到的函数适用于所有方程的求解：

 function fixed_point_of_transform(g, transform, guess) {    return fixed_point(transform(g), guess);}

小试牛刀，求方程 x^3 + a*x^2 + ax + c = 0的解：

function cubic(a, b, c) {    return x => cube(x) + a * square(x) + b * x + c;}function cube(x) {  return x ** 3;}function square(x) {  return x ** 2;}