牛顿迭代法求平方根

1.先说结论

可这样求得: 令 为任意实数, 执行以下迭代式:

迭代若干次, 当 小于想要的精度时便可停止迭代. 最终的 便可视为 . 根据 (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

如图所示, 对于方程 , 我们任取一个实数 , 过点 作 的切线 交 x 轴于 . 我们有:

重复以上操作, 分别计算出

image

最终 会逼近 的根. 也就是不断执行这个迭代式:

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

用牛顿迭代法求 实际上就是求方程 的根. 带入牛顿迭代公式, 得:

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