¿Cómo puedo implementar esto de manera más eficiente?

Question

Tengo una función (escribo esto en un lenguaje pseudo-funcional, espero que esté claro):

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

Y deseo aplicar esto n veces a un valor x. Podría implementarlo recursivamente:

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

Pero debe haber una manera en que pueda hacerlo matemáticamente sin recurrir a un procedimiento iterativo (recursivo, o un bucle).

Desafortunadamente, mis habilidades de álgebra están oxidadas más allá de lo que se puede creer, ¿alguien puede ayudar?

Answer 1

Podemos eliminar la serie de su fórmula por completo.

Nos dan:

x_(n+1) = x_n + lr(1-x_n)

Esto se puede hacer más simple reescribiendo lo siguiente:

x_(n+1) = (1-lr)x_n + lr

Efectivamente, hemos transformado esto en recursión de la cola. (Si quieres la perspectiva de la informática).

Esto significa que:

x_n = (1-lr)^n * x_0    +   ((1-lr)^(n-1) + (1-lr)^(n-2) + ... + 1)*lr 

El gran término a la derecha es una serie geométrica , por lo que se puede contraer como bien:

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

Editado debido a un pequeño error en las expresiones finales. +1 a la tormenta venidera.

Answer 2

x + lr*(1-x) 
= x + lr - lr*x 
= x*(1-lr)+lr

aplicarlo dos veces da

(x*(1-lr)+lr)*(1-lr)+lr 
= x*(1-lr)^2 + lr*(1-lr) + lr

y tres veces

(x*(1-lr)+lr)*(1-lr)^2 + lr*(1-lr) + lr 
= x*(1-lr)^3 + lr*(1-lr)^2 + lr*(1-lr) + lr

o en general, n veces da

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

¿Eso ayuda?

Answer 3

En realidad, la publicación de MarkusQ tiene un error. La fórmula correcta es:

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

También, ten en cuenta que " n " Es el número de veces que aplicas la función. En su pseudocódigo funcional anterior, el " n = 0 " caso aplica la función una vez, no cero veces; para que coincida con la fórmula anterior, tendría que ir:

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

Answer 4

Mi habilidad de álgebra también apesta, pero decidí refactorizar un poco la ecuación y comencé a examinar algunos de los casos, d0 y 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

Básicamente, si empiezas a ver la cuadrática, puedes comenzar a ver la forma cúbica y así sucesivamente.

En ese punto, la x solo se usa una vez, y solo debes lidiar con la exponenciación de todos los sub términos de la forma (1 - lr) ^ n.