4.2 近似平方根

原文：Approximating square root

译者：飞龙

协议：CC BY-NC-SA 4.0

有许多有用的函数没有闭式解，这意味着我们不能只进行计算并返回值。 相反，我们需要使用迭代方法来近似函数值。 我们可以用它来近似正弦（用泰勒级数展开），近似平方根（我们将在本课程中做），或优化成本或误差函数（下一讲的梯度下降）。

与之前的统一随机变量讲座一样，我们必须将递归关系转换为 Python。 我们将寻找收敛序列，而不是返回递推序列中的单个值。 换句话说，如果我们将序列计算得足够远，x_{i + 1}将接近xi，使xi成为平方根的非常准确的近似值。 这将教会我们迭代计算的基础知识，并为更复杂的函数优化材料做好准备。

巴比伦方法

为了近似平方根，我们的想法是选择一个初始估计值x0，然后使用巴比伦方法来更好地的估计和迭代值xi。递归关系：

x{i+1} = 1/2 (xi + n/xi)

网上有很多东西你可以阅读，来更多了解为什么这个过程有效，但它依赖于xi和n / xi的平均值（中点），让我们更接近n的平方根。很酷的是迭代很快收敛。

我们的目标是编写一个函数，它接受一个数字并将其返回平方根。 在开始编码之前我们对这个函数了解多少？ 好吧，根据我们的函数工作计划，我们有一个明确的问题描述，我们也有我们想要的函数签名：

def sqrt(n):

因为我们正在实现递归关系，所以我们知道我们将有一个循环，从xi计算x{i + 1}。

收敛

循环的终止条件是当我们达到收敛或接近收敛。 收敛只意味着x{i + 1}非常接近xi。 因为我们永远无法比较实数，所以我们必须检查差异是否小于某些精度，如 0.00000001。

迭代方法的大纲

正如我们有一个分析程序的大纲，迭代方法都共享相同的基本大纲。 （我在这里假设x{i + 1}仅取决于一个先前的值，并且i在循环转换时隐式递增。）

• 将x0设为初始值
• 重复：
  • function-giving-next-value(xi)
• 直到abs(x{i+1} - xi) < precision
• 返回x{i+1}

因为 Python 没有do-while循环，所以我们用一个包含条件的无限循环来伪造它，这会在收敛时中断：

• 将x0设为初始值
• while True:
  • function-giving-next-value(xi)
  • 如果abs(x{i+1} - xi) < precision
    • 返回x{i+1}

这是一个相当简单的递归关系实现，但你会注意到，我们实际上不需要保留所有先前的xi，除了新值和前一个值。 这是一个 Python 实现，它只跟踪两个值并遵循无限循环模式：

def sqrt(n):
    "compute square root of n"
    PRECISION = 0.00000001 # stop iterating when we converge with this delta
    x_0 = 1.0 # pick any old initial value
    x_prev = x_0
    while True: # Python doesn't have repeat-until loop so fake it
        #print(x_prev)
        x_new = 0.5 * (x_prev + n/x_prev)
        if abs(x_new - x_prev) < PRECISION:
            return x_new
        x_prev = x_new # x_i+1 becomes x_i (previous value)

'''
1.0
50.5
26.24009900990099
15.025530119986813
10.840434673026925
10.032578510960604
10.000052895642693
10.000000000139897
'''

sqrt(100)

# 10.0

为了测试我们的平方根近似，我们可以将它与math.sqrt()进行比较，并使用 numpy 的isclose来进行比较。

import numpy as np
def check(n):
    assert np.isclose(sqrt(n), np.sqrt(n))
def test_sqrt():
    check(125348)
    check(89.2342)
    check(100)
    check(1)
    check(0)

test_sqrt()

如您所见，我们可以在函数中定义函数。 除了test_sqrt()之外的代码看不到函数check()之外，它没有任何特殊之处。 另一方面，check()可以看到test_sqrt()之外的符号，比如我们的sqrt()。

练习

输入（不要剪切/粘贴）sqrt(n)函数并测试，例如，sqrt(125348.0)。 确保得到正确的答案（354.045195），然后添加print语句，以便您可以看到xi值的序列。 我得到了：

1.0
62674.5
31338.249992
15671.1249162
7839.56178812
3927.77547356
1979.84435152
1021.5781996
572.139273508
395.612894667
356.228988269
354.051888518
354.045194918
354.045194855

注意它收敛得多快！

def sqrt_with_trace(n):
    "compute square root of n"
    PRECISION = 0.00000001 # stop iterating when we converge with this delta
    x_0 = 1.0 # pick any old initial value
    x_prev = x_0
    while True: # Python doesn't have repeat-until loop so fake it
        print(x_prev)
        x_new = 0.5 * (x_prev + n/x_prev)
        if abs(x_new - x_prev) < PRECISION:
            return x_new
        x_prev = x_new

sqrt_with_trace(125348.000000)

'''
1.0
62674.5
31338.249992022273
15671.12491623693
7839.561788117747
3927.7754735639414
1979.844351517673
1021.5781996033152
572.1392735077299
395.612894666841
356.2289882689982
354.0518885182295
354.04519491839494
354.04519485512014
354.04519485512014
'''

现在我们知道了如何实现收敛的递归关系，让我们来看看函数优化。 乍一看，它看起来完全不同，但使用了迭代方法的相同抽象。