Как я могу реализовать это более эффективно

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» применяет функцию один раз, а не ноль раз; чтобы соответствовать приведенной выше формуле, она должна идти:

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.