预测所需迭代次数 - 迭代加权平均

Question

不好意思，我找不到更好的标题。请看这个超级简单的Python程序:

x = start = 1.0
target = 0.1

coeff = 0.999

for c in range(100000):

    print('{:5d} {:f}'.format(c, x))
    if abs(target - x) < abs((x - start) * 0.01):
        break

    x = x * coeff + target * (1 - coeff)

简要说明：该程序通过迭代计算x和target的加权平均值，以coeff作为权重，将x移向target。当x到达初始差异的1％时，程序停止。

无论x和target的初始值是什么，迭代次数都保持不变。

我该如何设置coeff以预测迭代会进行多少次？

非常感谢。

- Claudio

---

我对这里的目标有点困惑。你所说的“设置系数以预测将进行多少次迭代”是什么意思？ - Ryan Lim

我认为他的意思是，如果有一个名为coeff的函数，它可以映射到所需迭代次数的数量。 - pythonic833

@RyanLim：我猜他想知道循环将运行多少次，给定start、target和coeff的值，这需要解决一个不等式多项式，形式为k0 * start * coeff^n + target * (k1 * coeff^n + k2 * coeff^(n-1) + ... + kn) < k。 - fferri

通过一些代数运算可以证明，在进行了n次迭代后，变量x的值由以下公式给出：x_val = lambda n: start*(coeff**n) + target*(1-coeff)*(sum(coeff**i for i in range(n)))。您需要找到解决条件的最小n值。 - pault

我的意思是，当coeff为0.999时，迭代次数为4613。我正在寻找获得0.999的公式，以便从4613开始。此外，存在某种对数关系：0.99->460，0.999->4613，0.9999->46149。 - user6369958

Answer 1

让我们把这个变成一个函数，称之为f。 f(0)是初始值（在这里是1.0）。 f(x) = f(x - 1) * c + T * (1 - c)。

（所以f(1)是x的下一个值，f(2)是其后一个值，以此类推。我们要找到满足条件|T - f(x)| < 0.01 * |f(0) - f(x)|的x的值）

因此，让我们将f(x)重写为线性的形式：

f(x) = f(x - 1) * c + T * (1 - c)
     = (f(x - 2) * c + T * (1 - c)) * c + T * (1 - c)
     = (f(x - 2) * c ** 2 + T * c * (1 - c)) + T * (1 - c)
     = ((f(x - 3) * c + T * (1 - c)) * c ** 2 + T * c * (1 - c)) + T * (1 - c)
     = f(x - 3) * c ** 3 + T * c ** 2 * (1 - c) + T * c * (1 - c) + T * (1 - c)

     = f(0) * c ** x + T * c ** (x - 1) * (1 - c) + T * c ** (x - 2) * (1 - c) + ... + T * c * (1 - c) + T * (1 - c)

     = f(0) * c ** x + (T * (1 - c)) [(sum r = 0 to x - 1) (c ** r)]
  # Summation of a geometric series
     = f(0) * c ** x + (T * (1 - c)) ((1 - c ** x) / (1 - c))
     = f(0) * c ** x + T (1 - c ** x)

因此，x 的第 n 个值将为 start * c ** n + target * (1 - c ** n)。

我们希望：

|T - f(x)| < 0.01 * |f(0) - f(x)|
|T - f(0) * c ** x - T (1 - c ** x)| < 0.01 * |f(0) - f(0) * c ** x - T (1 - c ** x)|
|(c ** x) * T - (c ** x) f(0)| < 0.01 * |(1 - c ** x) * f(0) - (1 - c ** x) * T|
(c ** x) * |T - f(0)| < 0.01 * (1 - c ** x) * |T - f(0)|
c ** x < 0.01 * (1 - c ** x)
c ** x < 0.01 - 0.01 * c ** x
1.01 * c ** x < 0.01
c ** x < 1 / 101
x < log (1 / 101) / log c

一些文字似乎出现了错误，正确应该是“x >”，但它给出了正确的答案。当 c = 0.999 时，x > 4612.8，并在第 4613 步终止。

最终结果与 start 和 target 无关。

此外，对于一般的百分比差异 p，

c ** x > p * (1 - c ** x)
c ** x > p - p c ** x
(1 + p) c ** x > p
c ** x > p / (1 + p)
x > log (p / (1 + p)) / log c

因此，对于系数 c ，将会有log（1/101）/ log c 步骤。

如果您知道所需的步骤数量I，则可以使用以下公式：

I = log_c(1 / 101)
c ** I = 1 / 101
c = (1 / 101) ** (1 / I)

因此，应将 c 设置为 1/101 的 I 次根。

- Artyer

---

我真的非常印象深刻。谢谢1000。 - user6369958

Answer 2

你的代码在每次循环中将x与目标之间的距离缩小了coeff倍。因此，如果start大于target，我们可以得到以下公式：

target - x = (x - start) * coeff ** c

其中c是我们完成循环的次数。

如果start大于target，则您的结束准则为：

x - target < (start - x) * 0.01

通过代数运算求解x，我们得到

x > (target + 0.01 * s) / (1 + 0.01)

将其代入我们的第一个表达式并稍微简化一下，使得start和target都从不等式中消失 - 现在你可以看到为什么这些值并不重要 - 我们得到了以下结果。

0.01 / (1 + 0.01) < coeff ** c

解决 c 的问题，我们得到

c > log(0.01 / (1 + 0.01), coeff)

因此，循环次数的最终答案为：

ceil(log(0.01 / (1 + 0.01), coeff))

或者，如果您不喜欢任意底数的对数，可以选择以下方法：

ceil(log(0.01 / (1 + 0.01)) / log(coeff))

你可以将最后一个表达式中的第一个对数替换为其结果，但我保留它以查看如果将结束标准中的常量更改为0.01之外的值，您将获得不同的结果。

在您的特定情况下，该表达式的结果为：

4613

这是正确的。请注意，Python的math模块中都包含了ceil和log函数，因此在进行计算之前，请记得导入这些函数。同时请注意，Python的浮点数计算并不精确，如果您更改coeff或0.01的值，则实际的循环次数可能会比预期的多一个。

- Rory Daulton