Comment puis-je mettre en œuvre cette plus efficace

Question

J'ai donc une fonction (j'écris ceci dans un langage pseudo-fonctionnel, je l'espère son clair):

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

Et je veux appliquer cette n fois à une valeur x. Je pourrais le mettre en œuvre récursive:

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

Mais il doit y avoir une manière que je peux le faire mathématiquement sans avoir recours à une procédure itérative (récursif, ou une boucle).

Malheureusement, mes compétences en algèbre sont rouillées au-delà de toute croyance, quelqu'un peut-il m'aider?

Answer 1

Nous pouvons éliminer complètement la série de votre formule.

Nous sommes donnés:

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

Cela peut être fait plus simple en réécrivant comme suit:

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

En effet, nous avons transformé cela en récursion queue. (. Si vous voulez que le point de vue de la science informatique)

Cela signifie que:

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

Le grand terme à droite est un geometric series, de sorte que peut être effondrés ainsi:

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 

Edité en raison d'une petite erreur dans les expressions finales. +1 à la tempête

Answer 2

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

application donne deux fois

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

et trois fois

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

ou en général, n fois donne

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

Est-ce que l'aide?

Answer 3

Mon habileté d'algèbre sucent aussi, mais j'ai décidé de remanier l'équation un peu et a commencé à examiner certains des cas, d0 et 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 

Fondamentalement, si vous commencez à voir le second degré, vous pouvez commencer voir la forme cubique et ainsi de suite. A ce point, le x n'est utilisé qu'une seule fois, et il suffit de traiter l'exponentiation de tous les sous-termes de la forme (1 - lr)^n.

Answer 4

En fait, le message de MarkusQ comporte une erreur. La formule correcte est:

 
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 

Notez également que "n" est le nombre de fois que vous appliquez la fonction.Dans votre pseudo-code fonctionnel ci-dessus, le cas "n = 0" applique la fonction une fois, pas zéro fois; pour correspondre à la formule ci-dessus, il faudrait aller:

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