牛顿迭代法求平方根

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

2.详解

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

image

如图所示, 对于方程 \(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, ...\)

image

最终 \(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) 式.