Come posso implementare questa in modo più efficiente

Question

Così ho una funzione (sto scrivendo questo in un linguaggio pseudo-funzionali, spero che il suo chiaro):

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

E desidero applicare questo n volte a un valore x. Mi potrebbe implementare 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 un loop).

Sfortunatamente le mie abilità di algebra sono arrugginite oltre ogni immaginazione, qualcuno può aiutarmi?

Answer 1

Possiamo eliminare completamente la serie dalla tua formula.

ci viene dato:

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

questo può essere reso più semplice riscrivendo la seguente:

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

In effetti, abbiamo trasformato questo in coda ricorsione. (. Se si desidera che la prospettiva informatica)

Ciò significa che:

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

La grande termine a destra è un geometric series, in modo che possono essere crollato così:

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.

Answer 2

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

applicandola dà due volte

(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) 

fa questo aiuto?

Answer 3

La mia abilità algebra succhiare troppo, ma ho deciso di refactoring l'equazione un po 'e ha iniziato a esaminare alcuni 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 

In sostanza, se si inizia a vedere la quadratica, si può iniziare vedendo la forma cubica e così via.

A questo punto la x viene utilizzata solo una volta e devi solo occuparti dell'esponenziazione di tutti i termini secondari del modulo (1 - lr)^n.

Answer 4

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, si noti che "n" è il numero di volte in cui si applica la funzione.Nel tuo pseudocodice funzionale sopra, il caso "n = 0" 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))