Wie kann ich implementieren diese effiziente

Question

So habe ich eine Funktion (Ich schreibe dies in einer pseudo-funktionalen Sprache, ich seine klare Hoffnung):

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

Und ich mag diese n-mal gelten ein Wert x. Ich konnte es rekursiv implementieren:

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

Aber es muss ein Weg sein, die ich es mathematisch ohne Rückgriff auf ein iteratives Vorgehen tun können (rekursiv oder eine Schleife).

Leider sind meine Algebra Fähigkeiten rostig, kann jemand helfen?

Answer 1

Wir können die Serie vollständig aus Ihrer Formel entfernen.

Wir sind gegeben:

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

Dies kann durch Umschreiben einfacher gemacht werden, wie folgt:

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

Effektiv haben wir diese in Endrekursion umgewandelt. (. Wenn Sie die Informatik Perspektive wollen)

Das bedeutet:

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

Der große Term auf der rechten Seite ist ein geometric series, so dass auch zusammengeklappt werden kann:

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 

Bearbeitet wegen eines kleinen Fehlers in den endgültigen Ausdrücken. +1 zum kommendenSturm.

Answer 2

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

Anwendung zweimal gibt

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

und dreimal

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

oder allgemein n-mal gibt

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

diese Hilfe tut?

Answer 3

Meine Algebra Fähigkeiten saugen auch, aber ich beschlossen, die Gleichung ein wenig Refactoring und begann einige der Fälle untersuchen, d0 und 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 

Grundsätzlich, wenn Sie die quadratische sehen beginnen, können Sie beginnen die kubische Form sehen und so weiter.

An diesem Punkt wird das x nur einmal verwendet, und Sie müssen nur mit der Potenzierung aller Unterbegriffe der Form (1 - lr)^n umgehen.

Answer 4

Eigentlich hat MarkusQ's Beitrag einen Fehler. Die richtige Formel lautet:

 
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 

Beachten Sie auch, dass "n" ist, wie oft Sie die Funktion anwenden.In Ihrem obigen funktionalen Pseudocode wendet der Fall "n = 0" die Funktion einmal an, nicht null mal; die obige Formel entspricht, würde es gehen:

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