Как я могу реализовать это более эффективно
Вопрос
Итак, у меня есть функция (я пишу это на псевдофункциональном языке, надеюсь, она понятна):
dampen (lr : Num, x : Num) = x + lr*(1-x)
И я хочу применить это n раз к значению х. Я мог бы реализовать это рекурсивно:
dampenN (0, lr, x) = dampen(lr, x)
dampenN (n, lr, x) = dampenN(n-1, lr, dampen(x))
Но должен быть способ, которым я могу сделать это математически, не прибегая к итерационным процедурам (рекурсивным или циклам). Р>
К сожалению, мои навыки алгебры ржавые до предела, кто-нибудь может помочь?
Решение
Мы можем полностью исключить ряд из вашей формулы. Р>
Нам дают:
x_(n+1) = x_n + lr(1-x_n)
Это можно упростить, переписав следующим образом:
x_(n+1) = (1-lr)x_n + lr
По сути, мы превратили это в хвостовую рекурсию. (Если вам нужна перспектива информатики.)
Это означает, что:
x_n = (1-lr)^n * x_0 + ((1-lr)^(n-1) + (1-lr)^(n-2) + ... + 1)*lr
Большой термин справа - это геометрический ряд , поэтому его можно свернуть как а также:
x_n = (1-lr)^n * x_0 + lr * (1 - (1-lr)^n) / (1- (1 -lr))
x_n = (1-lr)^n * x_0 + 1 - (1 - lr)^n
Отредактировано из-за небольшой ошибки в окончательных выражениях. +1 к наступающему шторму. Р>
Другие советы
x + lr*(1-x)
= x + lr - lr*x
= x*(1-lr)+lr
применение его дважды дает
(x*(1-lr)+lr)*(1-lr)+lr
= x*(1-lr)^2 + lr*(1-lr) + lr
и три раза
(x*(1-lr)+lr)*(1-lr)^2 + lr*(1-lr) + lr
= x*(1-lr)^3 + lr*(1-lr)^2 + lr*(1-lr) + lr
или вообще, n раз дает
x*(1-lr)^n + lr * ( (1-lr)^n + (1-lr)^(n-1)...+(1-lr) +1)
Это помогает?
На самом деле сообщение MarkusQ содержит ошибку. Правильная формула:
x * (1-lr)^n + lr * ( (1-lr)^(n-1) + (1-lr)^n-2 + ... + (1-lr) + 1 ) = x * (1-lr)^n + lr * ( 1 - (1-lr)^n )/(1 - (1-lr)) = x * (1-lr)^n + (lr/lr) * (1 - (1-lr)^n) = (x-1) * (1-lr)^n + 1
Также обратите внимание, что " n " это количество раз, когда вы применяете функцию. В приведенном выше функциональном псевдокоде " n = 0 " case применяет функцию один раз, а не ноль раз; чтобы соответствовать приведенной выше формуле, она должна идти:
dampenN (0, lr, x) = x dampenN (n, lr, x) = dampenN(n-1, lr, dampen(x))
Мои навыки алгебры тоже отстойные, но я решил немного реорганизовать уравнение и начал изучать некоторые случаи, d0 и d1:
d0 = x + lr(1-x) => x + lr - lr*x => (1 - lr)x + lr
d1 = (1 - lr)[(1 - lr)x + lr] + lr => (1 - lr)^2 x + lr(1 - lr) + lr
В основном, если вы начнете видеть квадратик, вы можете начать видеть кубическую форму и т. д.
В этот момент x используется только один раз, и вам нужно иметь дело с возведением в степень всех подслов в форме (1 - lr) ^ n.