如何更有效地实现这一点

Question

所以我有一个函数（我用伪函数式语言写这个，我希望它清楚）：

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

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

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

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

Answer 2

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

应用它两次

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

和三次

(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

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

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

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

此时x只使用一次，你只需要处理表格中所有子项的取幂（1 - lr）^ n。