python - 了解使用二分法找到解决方案的迭代次数

Question

我被要求使用二分法求方程的根，并且只使用 Python 3 的 for 循环。This thread 显示了如何使用该方法，但没有说明 range() 中的数字。

例如，我有函数

f(x) = x² - 2*x - 3

我想找到它的负根，从区间 [-4, 1] 开始。

我设法用 for 循环编写函数，但我不明白我应该使用哪个范围，或者如何想出它。

这是我的代码，解决了这个问题:

...
a = -4
b = 1
c = (a + b)/2

for i in range(1000):
    if f(c) == 0:
        break
    if f(a) * f(c) < 0:
        b = c
    elif f(a) * f(c) > 0:
        a = c
    c = (a + b) / 2

return c, f(c), i

c = -1(找到负根)，f(c) = 0 确认程序有效，i = 52 表示经过 52 次二分“尝试”后，它找到了正确的答案。

我在 range() 中放入了一个非常大的数字以确保找到根，但为什么它只需要 52 次迭代？

此外，如果我的间隔更改为 [-2, 1]，我将需要尝试 53 次。 为什么会这样？

Answer 1

如果您在循环中print([a, b])，您可以看到范围演变:

[-4, 1]
[-1.5, 1]
[-1.5, -0.25]
[-1.5, -0.875]
[-1.1875, -0.875]
[-1.03125, -0.875]
...
...
...
[-1.0000000000000284, -0.9999999999999929]
[-1.0000000000000107, -0.9999999999999929]
[-1.0000000000000018, -0.9999999999999929]
[-1.0000000000000018, -0.9999999999999973]
[-1.0000000000000018, -0.9999999999999996]
[-1.0000000000000007, -0.9999999999999996]

-1.0000000000000007 和 -0.9999999999999996 的计算平均值正好是 -1。为什么？因为你已经达到了 float 所能代表的极限。以下是所涉及的确切值:

>>> '%.60f' % -1.0000000000000007
'-1.000000000000000666133814775093924254179000854492187500000000'

>>> '%.60f' % -0.9999999999999996
'-0.999999999999999555910790149937383830547332763671875000000000'

>>> '%.60f' % (-1.0000000000000007 + -0.9999999999999996)
'-2.000000000000000000000000000000000000000000000000000000000000'

>>> '%.60f' % ((-1.0000000000000007 + -0.9999999999999996) / 2)
'-1.000000000000000000000000000000000000000000000000000000000000'

花车商店 52 bits of fraction ，表示前导 1 位之后的 52 位。这意味着您损失的金额小于您值(value)的 1/2⁵²。在 52 步之后，您的初始尺寸 5 范围变成大约尺寸 5/2⁵²。这大约是您的值 -1 的 1/2⁵²。所以在附近，由于不精确，您很有可能偶然发现 -1。

它可能需要两步或三步，因为 5/2⁵² 仍然比 1/2⁵² 大一点。你在那里很幸运。使用其他初始范围 [-2, 1] 你就没那么幸运了。你的范围缩小到 [-1.0000000000000002, -0.999999999999999999999999] 才达到 -1。

如果您从 [-4000000, 1] 开始，那么您将需要 72 个步骤。多了 20 步，因为初始范围大了一百万倍，大约是 2²⁰。

另一种情况:如果您使用函数 x**2 - 1000000 和初始范围 [999.3, 1000.3]，则需要 41 步。为什么？最终值(即根)为 1000，初始范围的大小为 1。即 1/1000，因此约为 1/2¹⁰。所以要达到 1/2⁵² 你只需要大约 42 个二等分。