¿Cómo puedo poner en práctica esta manera más eficiente

Question

Así que tienen una función (estoy escribiendo esto en un lenguaje pseudo-funcional, espero que sea clara):

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

Y deseen aplicar este n veces a un valor x. Podría ponerlo en práctica de forma recursiva:

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

Pero tiene que haber alguna manera de hacerlo matemáticamente sin tener que recurrir a un procedimiento iterativo (recursivo, o un bucle).

Desafortunadamente, mis habilidades de álgebra están muy oxidadas, ¿alguien puede ayudarme?

Answer 1

Podemos eliminar completamente la serie de su fórmula.

se nos da:

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

Esto se puede hacer más simple reescribiendo la siguiente manera:

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

Efectivamente, hemos transformado esto en la recursión de cola. (. Si desea que el punto de vista 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 de la derecha es una geometric series, de manera que se pueden contraer, así:

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 llegada.

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) 

ayuda eso?

Answer 3

Mi habilidad álgebra chupar también, pero decidió refactorizar la ecuación un poco y empezó 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 usted comienza a ver el segundo grado, puede empezar viendo la forma cúbica, etc.

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

Answer 4

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 

Además, tenga en cuenta que "n" es el número de veces que se aplica la función.En su pseudocódigo funcional anterior, el caso "n = 0" 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))