これをより効率的に実装するにはどうすればよいですか

Question

だから私は関数を持っています（これを擬似関数型言語で書いています、それが明確であることを願っています）：

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

そして、これを値xにn回適用したいと思います。再帰的に実装できます：

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

しかし、反復手順（再帰、またはループ）に頼らずに数学的にそれを行う方法がなければなりません。

残念ながら、私の代数スキルは信じられないほど錆びていますが、誰でも助けてもらえますか？

Answer 1

数式からシリーズを完全に削除できます。

与えられたもの：

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

これは、次のように書き直すことで簡単にできます。

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

効果的に、これを末尾再帰に変換しました。 （コンピューターサイエンスの観点が必要な場合。）

これは次のことを意味します。

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

右側の大きな用語は幾何シリーズです。よく：

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

最終式の小さなエラーのために編集されました。 comingstormへの+1。

Answer 2

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

2回適用すると

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

3回

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

または一般的に、n回与える

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

それは役立ちますか？

Answer 3

実際、MarkusQの投稿にはエラーがあります。正しい式は次のとおりです。

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

また、＆quot; n＆quot;関数を適用する回数です。上記の機能的な擬似コードでは、「n = 0」 caseは、関数をゼロ回ではなく1回適用します。上記の式と一致させるには、次のようにする必要があります。

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

Answer 4

私の代数スキルも下手ですが、方程式を少しリファクタリングすることを決め、いくつかのケース、d0、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

基本的に2次の表示を開始した場合、3次の表示などを開始できます。

xは1回だけ使用され、（1-lr）^ nの形式のすべてのサブ項のべき乗を処理する必要があります。