Wie kann ich dies umsetzen, effizienter

Question

Also ich habe eine Funktion (ich Schreibe dies in einer pseudo-funktionale Sprache, ich hoffe, klar):

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

Und ich wünschte, die Anwendung dieser n-mal zu einem x-Wert.Ich konnte es umsetzen rekursiv:

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

Aber es muss doch eine Möglichkeit, ich kann es tun, mathematisch, ohne Rückgriff auf eine iterative Verfahren (rekursiv, oder eine Schleife).

Leider ist mein algebra-Fähigkeiten sind rostigen jenseits des Glaubens, kann jemand helfen?

Answer 1

Wir können die Serie von Ihrer Formel vollständig beseitigen.

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

Tatsächlich 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 geometrische Reihe , so dass zusammengeklappt werden kann als gut:

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

Herausgegeben durch einen kleinen Fehler in dem letzten Ausdrücken. +1 bis comingstorm.

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)

Ist diese Hilfe?

Answer 3

Eigentlich hat MarkusQ der Post 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 die Anzahl, wie oft Sie die Funktion anwenden. In Ihrem funktionellen Pseudo-Code oben gilt der „n = 0“ Fall die Funktion einmal, 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))

Answer 4

Mein algebra-Fähigkeiten zu saugen, aber ich beschloss, umgestalten der Gleichung ein wenig und begann, untersucht einige der Fälle, 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 sehen, beginnen die quadratische, können Sie sehen die kubische form und so weiter.

An welcher Stelle steht das x nur einmal verwendet werden, und Sie müssen nur deal mit die Potenzierung aller sub-Bedingungen der form (1 - lr)^n.