Как я могу это реализовать более эффективно

Question

Так что я функция (я пишу это в псевдо-функциональном языке, я надеюсь, что его ясно):

dampen (lr : Num, x : Num) = x + lr*(1-x) 

И я хочу, чтобы применить это несколько раз к значение x. Я мог бы реализовать рекурсивно:

dampenN (0, lr, x) = dampen(lr, x) 
dampenN (n, lr, x) = dampenN(n-1, lr, dampen(x)) 

Но должно быть так, как я могу сделать это математически, не прибегая к итерационной процедуры (рекурсивной, или петли).

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

Answer 1

Мы можем полностью исключить серию из вашей формулы.

Нам дано:

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 

Большой член справа представляет собой geometric series, так что может быть свернуты, а также:

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 до грозы.

Answer 2

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 

или вообще, п раз дает

x*(1-lr)^n + lr * ((1-lr)^n + (1-lr)^(n-1)...+(1-lr) +1) 

ли это помощь?

Answer 3

Моя алгебра умение сосать, но я решил реорганизовать уравнение немного и начал исследовать некоторые из случаев, 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.

Answer 4

На самом деле, сообщение 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» применяет функцию один раз, а не нулевое время; в соответствии с приведенной выше формулой, это должно было бы пойти:

 
dampenN (0, lr, x) = x 
dampenN (n, lr, x) = dampenN(n-1, lr, dampen(x))