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

Question

对不起，我可以找到更好的标题。请看这个 super 简单的 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，迭代计算x 和target 的加权平均值，其中coeff 作为权重。当 x 达到初始差异的 1% 时停止。

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

如何设置 coeff 以预测将发生多少次迭代？

非常感谢。

Answer 1

让我们把它变成一个函数，f .

f(0)是初始值( start ，在本例中为 1.0 )。

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

(所以 f(1) 是 x 的下一个值，f(2) 是下一个，依此类推。我们要找到 x 的值，其中 |T - f(x)| < 0.01 * |f(0) - f(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 < 而它应该是 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应设置为 I 1 / 101 的根.