如何更高效地实现这个？

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

但是必须有一种数学方法可以做到这一点，而不需要采用迭代过程（递归或循环）。

不幸的是，我的代数技能非常生疏，有人可以帮忙吗？

- sanity

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)

这有帮助吗？

- MarkusQ

---

你可以进一步注意到，(1-lr)^n + (1-lr)^(n-1)...+(1-lr) +1是等比数列的和，并且可以使用公式计算。 - vava

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 给 comingstorm。

- Rob

---

你的数列中不包含(1-lr)^n，你能解释一下为什么吗？我在MarkusQ的解决方案中看到了这个术语。 - Niyaz

是的。从x1 = (1-lr)x0 + r开始，x2 = (1 - lr)x1 + r，因此x2 = (1 - lr)^2 x0 + (1 - lr) * r，依此类推。 - Rob Lachlan

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”情况应用了一次函数，而不是零次；为了匹配上述公式，它必须如下进行：

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

- comingstorm

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的子项的指数运算。

- Saem