Come posso implementarlo in modo più efficiente

Question

Quindi ho una funzione (sto scrivendo questo in un linguaggio pseudo-funzionale, spero sia chiaro):

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

E desidero applicare questo n volte a un valore x. Potrei implementarlo in modo ricorsivo:

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

Ma ci deve essere un modo per farlo matematicamente senza ricorrere a una procedura iterativa (ricorsiva o a ciclo continuo).

Purtroppo le mie capacità di algebra sono arrugginite oltre ogni immaginazione, qualcuno può aiutare?

Answer 1

Possiamo eliminare completamente le serie dalla tua formula.

Ci viene dato:

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

Ciò può essere semplificato riscrivendo come segue:

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

In effetti, abbiamo trasformato questo in ricorsione della coda. (Se vuoi la prospettiva informatica.)

Ciò significa che:

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

Il grande termine a destra è una serie geometrica , in modo che possa essere compresso come bene:

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

Modificato a causa di un piccolo errore nelle espressioni finali. +1 alla tempesta in arrivo.

Answer 2

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

applicandolo due volte dà

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

e tre volte

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

o in generale, n volte dà

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

Aiuta?

Answer 3

In realtà, il post di MarkusQ ha un errore. La formula corretta è:

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

Inoltre, tieni presente che " n " è il numero di volte in cui si applica la funzione. Nel tuo pseudocodice funzionale sopra, lo "quot = n = 0" case applica la funzione una volta, non zero volte; per abbinare la formula sopra, dovrebbe andare:

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

Answer 4

Anche la mia abilità algebrica fa schifo, ma ho deciso di riformattare un po 'l'equazione e ho iniziato ad esaminare alcuni dei casi, d0 e 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

Fondamentalmente se inizi a vedere la quadratica, puoi iniziare a vedere la forma cubica e così via.

A quel punto la x viene usata una sola volta e devi solo affrontare l'espiazione di tutti i termini secondari del modulo (1 - lr) ^ n.