牛顿勘根法的定义

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

求解方程 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;
}