Comment puis-je mettre cela en œuvre plus efficacement

Question

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

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

Et je souhaite appliquer cela n fois à une valeur x. Je pourrais l'implémenter de manière récursive:

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

Mais il doit y avoir un moyen de le faire mathématiquement sans recourir à une procédure itérative (récursive ou boucle).

Malheureusement, mes compétences en algèbre sont impénétrables, quelqu'un peut-il aider?

Answer 1

Nous pouvons éliminer complètement les séries de votre formule.

On nous donne:

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

Ceci peut être simplifié en réécrivant comme suit:

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

Effectivement, nous avons transformé cela en récursion de la queue. (Si vous voulez la perspective informatique.)

Cela signifie que:

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

Le gros terme à droite est une série géométrique , ce qui permet de la réduire en tant que 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

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

Answer 2

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

l'appliquer deux fois donne

(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 cela vous aide?

Answer 3

En fait, le message de MarkusQ contient 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 pseudocode fonctionnel ci-dessus, le "n = 0" case 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))

Answer 4

Mes compétences en algèbre sont nulles aussi, mais j’ai décidé de reformuler un peu l’équation et de commencer à examiner certains 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

En gros, si vous commencez à voir le quadratique, vous pouvez commencer à voir la forme cubique et ainsi de suite.

À ce stade, le x n’est utilisé qu’une seule fois et il vous reste à traiter l’exponentiation de tous les sous-termes de la forme (1 - lr) ^ n.