Newton Method

用某点的切线来拟合该点的曲线，利用这个切线的零点更接近曲线的零点。

牛顿迭代法是一种直觉，这种直觉在一定情况下却是收敛于零点。

牛顿迭代法求平方根

a 为给定值，求其平方根，得到 $f(x) = x^2 - a$ 。

$f(x)$ 的泰勒展开：

$$f(x) = f(x_{0}) + f^{'}(x_{0})(x - x_{0})$$

当 f(x) = 0 时得到

$$x = x_{0} - \frac{f(x_{0})}{f^{'}(x_{0})} = \frac{1}{2}(x_{0}+\frac{a}{x_{0}})$$

反复迭代就好了。

代码实现

public double sqrt(double x) {
    double eps = 1e-12;
    double t = x;
    while (Math.abs(t - x/t) > eps * t) {
        t = (t + x / t) / 2.0;
    }
    return t;
}