Прогнозировать необходимое количество итераций-взвешенное среднее число итераций

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, вычисляя итеративно средневзвешенное значение x и target с coeff в качестве веса. Он останавливается, когда x достигает 1% от начальной разницы.

Число итераций остается неизменным независимо от начального значения x и target.

Как я могу установить coeff, чтобы предсказать, сколько повторения будут иметь место?

Большое спасибо.

576 2

python math

2 ответов:

Comments

Ничего не найдено.

Artyer · Accepted Answer · 2018-04-16 22:20:28

Давайте сделаем это функцией, 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)
Таким образом, 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 - й корень 1 / 101.

Rory Daulton · Accepted Answer · 2018-04-16 22:45:43

Ваш код уменьшает расстояние между 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
Что верно. Обратите внимание, что обе функции ceil и log находятся в блоке math Python, поэтому не забудьте импортировать эти функции перед выполнением этого вычисления. Также обратите внимание, что вычисления Python с плавающей точкой не точны, поэтому ваше фактическое число циклов может отличаться от этого на единицу, если вы измените значения coeff или 0.01.