牛顿迭代法求平方根

1.先说结论

$\sqrt{a}$ 可这样求得: 令 $x_0$ 为任意实数, 执行以下迭代式:

$$ x_i = \frac{x_{i-1}+\frac{a}{x_{i-1}}}{2} \tag{1} $$

迭代若干次, 当 $|x_i-x_{i-1}|$ 小于想要的精度时便可停止迭代. 最终的 $x_i$ 便可视为 $\sqrt{a}$. 根据 (1) 式我们可以很快写出求平方根的代码:

def sqrt(a):
    x = 1.0
    while True:
        pre = x
        x = (x + a / x) / 2
        if abs(x - pre) < 1e-6:
            break

    return x

牛顿迭代法是一种近似求多项式方程根的一种方法.

如图所示, 对于方程 $f(x) = 0$ , 我们任取一个实数 $x_0$, 过点 $(x_0, f(x_0))$ 作 $f(x)$ 的切线 $l$ 交 x 轴于 $x_1$ . 我们有:

$$ f'(x_0) = \frac{\mathrm{d}f(x_0)}{\mathrm{d}x_0} = \frac{f(x_0)}{x_0-x_1} $$

$$ x_1 = x_0 - \frac{f(x_0)}{f'(x_0)} $$

重复以上操作, 分别计算出 $x_2, x_3, …$

最终 $x_n$ 会逼近 $f(x) = 0$ 的根. 也就是不断执行这个迭代式:

$$ x_i = x_{i-1} - \frac{f(x_{i-1})}{f'(x_{i-1})} \tag{2} $$

(2) 式被称为牛顿迭代公式

用牛顿迭代法求 $\sqrt{a}$ 实际上就是求方程 $x^2-a=0$ 的根. 带入牛顿迭代公式, 得:

$$ x_i = x_{i-1} - \frac{x_{i-1}^2 - a}{2x_{i-1}} = \frac{2x_{i-1}}{2} - \frac{x_{i-1}-\frac{a}{x_{i-1}}}{2} = \frac{x_{i-1}+\frac{a}{x_{i-1}}}{2} $$

也就得到了文章开头所列出的 (1) 式.