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

Question

我被要求使用二分法求方程的根，并且只有 for 使用 Python 循环 3. This 线程显示了如何使用该方法，但没有以及 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 "tries" 二分，找到正确答案.

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

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

Answer 1

每次迭代，您将搜索间隔减半。在每次迭代中，您检查中点处的函数值 f(c) 是否为 0，是否在计算机浮点表示的精度范围内。

如果您选择区间 [-101, 99]，您只需 1 次迭代即可获得解决方案，因为这就是您点击 c = -1 时的结果。只要程序足够接近评估出现的实际根，程序就会停止 0.000000

您从宽度为 5 的范围开始。5 除以 2，52 次等于多少？您的实现中浮点数的精度是多少？我敢打赌你接近两个浮点数之间的最小差异。

如果您真的想看到实际效果，请在循环内添加一行简单代码，就在顶部：

print a, b, c, f(c)

这将向您显示查找根的进度。

print 语句是一种低技术含量的有效跟踪程序的方法。

评论回复

好点：我还没有足够努力地指出具体案例。

您完成了 52 次迭代，因为这是程序 "stumble" 跨越正确值所花费的次数。当您更改并在 53 次迭代中以较小的范围完成时……简单的方法就是说您第一次有点幸运。正如我 did 指出的那样，如果您从以 -1 为中点的内容开始，例如 [-101, 99]，那么您将仅以 结束一个 次迭代，尽管间隔更大。

Answer 2

如果你在循环中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。为什么？因为你已经达到了浮点数所能代表的极限。以下是涉及的确切值：

>>> '%.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位。这意味着您损失了小于您价值的 1/2⁵² 的部分。在 52 步之后，您的尺寸 5 的初始范围变成大约尺寸 5/2⁵²。这大约是您的值 -1 的 1/2⁵²。所以在附近，由于不精确，你很有可能偶然发现 -1。

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

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

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

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

Understanding the number of iterations to find a solution using the Bisection method

python

algorithm

for-loop

bisection

python-3.x