如何更有效地实现这一点

So I have a function (I'm writing this in a pseudo-functional language, I hope its clear):

所以我有一个函数(我用伪函数语言写这个,我希望它清楚):

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

And I wish to apply this n times to a value x. I could implement it recursively:

我希望将这n次应用于值x。我可以递归地实现它:

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

But there must be a way I can do it mathematically without resorting to an iterative procedure (recursive, or a loop).

但是必须有一种方法可以在不使用迭代过程(递归或循环)的情况下以数学方式进行。

Unfortunately my algebra skills are rusty beyond belief, can anyone help?

不幸的是,我的代数技能已经超乎想象了,任何人都可以帮忙吗?

4 个解决方案

#1

We can eliminate the series from your formula entirely.

我们可以完全从您的公式中删除该系列。

We are given:

我们得到:

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

This can be made simpler by rewriting as follows:

通过重写如下可以使这更简单:

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

Effectively, we've transformed this into tail recursion. (If you want the computer science perspective.)

实际上,我们已将其转换为尾递归。 (如果你想要计算机科学的观点。)

This means that:

这意味着:

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

The big term on the right is a geometric series, so that can be collapsed as well:

右边的重要术语是几何系列,因此也可以折叠:

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

Edited due to a small error in the final expressions. +1 to comingstorm.

由于最终表达式中的小错误而编辑。 +1来到暴君。

#2

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

applying it twice gives

应用它两次给

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

and three times

和三次

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

or in general, n times gives

或者一般来说,n次给出

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

Does that help?

这有帮助吗?

#3

Actually, MarkusQ's post has an error. The correct formula is:

实际上,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

Also, note that "n" is the number of times you apply the function. In your functional pseudocode above, the "n=0" case applies the function once, not zero times; to match the above formula, it would have to go:

另请注意,“n”是您应用该功能的次数。在上面的功能伪代码中,“n = 0”情况应用函数一次,而不是零次;为了匹配上面的公式,它必须去:

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

#4

My algebra skill suck too, but I decided to refactor the equation a bit and started examining some of the cases, d0, and d1:

我的代数技能也很糟糕,但我决定稍微重构一下这个等式并开始检查一些情况,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

Basically if you start seeing the quadratic, you can start seeing the cubic form and so on.

基本上,如果你开始看到二次方,你可以开始看到立方形式等等。

At which point the x is only used once, and you just have to deal with the exponentiation of all the sub terms of the form (1 - lr)^n.

此时x只使用一次,你只需处理表格(1 - lr)^ n的所有子项的取幂。

#1