Predict the number of iterations required - iterated weighted average

Question

Excuse me, but I can find a better name. Take a look at this super simple Python program:

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)

Brief explanation: this program moves xto the side target, calculating an iteratively weighted average value xand targetwith coeffhow weight. It stops when it xreaches 1% of the initial difference.

The number of iterations remains unchanged regardless of the initial value xand target.

How can I set coeffto predict how many iterations will happen?

Many thanks.

Answer 1

Let this function f.

f(0) - (start, 1.0).

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

(So 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)

, n- x 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 th 1 / 101.

Answer 2

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

. , ceil log Python math, . , Python , , coeff 0.01.