algorithm - 我怎样才能更有效地实现这一点

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 + 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 2

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

我们得到：

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 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, lr, x) = x
阻尼N（n，lr，x）=阻尼N（n-1，lr，阻尼（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 形式的所有子项的幂运算。