Как решить рекуррентное отношение, развернув? - PullRequest
Новая
       52

Как решить рекуррентное отношение, развернув?

0 голосов
/ 20 февраля 2020

Если у меня есть T (n) = T (n-1) + T (n-2) + cn; T (1) = T (2) = d

Как я могу применить раскрутку для решения закрытой формы для T (n)?

Когда я пытаюсь развернуть это заменой, мой уравнение становится действительно длинным и трудным для отслеживания.

Ответы [ 2 ]

1 голос
/ 21 февраля 2020

Давайте изменим это на

T (n) - T (n-1) - T (n-2) = cn

С левой стороны сторона T линейна в T, существует стандартный метод решения: найдите общее решение, найдите любое конкретное решение, а затем найдите правильный экземпляр общего решения, которое нужно добавить к конкретному решению, чтобы соответствовать граничным условиям T (1) = T (2) = d.

Общее решение

Мы хотим найти все решения для T ′ (n) - T ′ (n-1) - T ′ (n-2) = 0. Решение для T ′ (n) не является решением исходной задачи, поскольку правая часть равна нулю; но полезно решить это уравнение, потому что с помощью линейности решение исходной задачи плюс любое решение проблемы «равно нулю» дает другое решение исходной задачи.

Это линейное рекуррентное соотношение, поэтому мы Можно предположить, что решение имеет вид T ′ (n) = x n для некоторого x ≠ 0. Подстановка дает x n - x n-1 - x n-2 = 0 и деление на x n-2 дает квадратное c уравнение x 2 - x - 1 = 0. Применяя В квадратичной формуле c это уравнение имеет два решения: золотое сечение x = φ и x = -1 / φ.

So T ′ (n) = φ n и T ′ (n) = (-1 / φ) n оба являются решениями, и, поскольку уравнение является линейным, любая линейная комбинация из них также является решением. Общая форма T ′ (n) = aφ n + b (-1 / φ) n , где a и b - произвольные постоянные.

Частное решение

Мы хотим найти любое решение для T (n) - T (n-1) - T (n-2) = cn. Поскольку правая часть является полиномом степени 1 от n, мы можем догадаться, что решение имеет вид T (n) = pn + q для некоторого p, q. Подстановка этого в дает

(pn + q) - (pn - p + q) - (pn - 2p + q) = cn

Эквивалентные коэффициенты, -pn = cn и 3p - q = 0, поэтому мы имеем p = - c и q = -3 c, и, следовательно, конкретным решением является T (n) = -cn - 3 c.

Граничные условия

Итак, мы ищем значения a и b, такие что

T (n) = aφ n + b (-1 / φ) n - cn - 3 c

удовлетворяет граничным условиям T (1) = T (2) = d. Подставляя, получаем:

  • aφ + b (-1 / φ) - c - 3 c = d
  • aφ 2 + b (-1 / φ) 2 - 2 c - 3 c = d

Поскольку c, d и φ являются константами, это система два линейных уравнения от двух переменных a и b. Это можно решить, применяя стандартную технику, такую ​​как исключение или замена, или просто , подключенный к Wolfram Alpha , что дает уникальное решение

solution for a and b

Это, безусловно, можно упростить, чтобы исключить квадратные корни в знаменателях, но я не думаю, что это необходимо для демонстрации метода решения.

1 голос
/ 20 февраля 2020

Вы можете использовать математическую библиотеку sympy, Python symboli c для записи терминов. 

from sympy.abc import c, d

def T(n):
    if n <= 0:
        return None
    elif n <= 2:
        return d
    else:
        return T(n-1) + T(n-2) + c*n

for i in range(1, 11):
    print(i, T(i))

Это дает: 

1 d
2 d
3 3*c + 2*d
4 7*c + 3*d
5 15*c + 5*d
6 28*c + 8*d
7 50*c + 13*d
8 86*c + 21*d
9 145*c + 34*d
10 241*c + 55*d

Коэффициенты для d являются явно числами Фибоначчи. Коэффициенты для c можно посмотреть в oeis , ведущем к A023552 . Это дает длинную явную формулу, а также Fibonacci(n+2) + 2*Fibonacci(n) - (n+3).

Замена Fibonacci формулой B inet с использованием sqrt(5), приводит к следующему выражению для T(n): 

-2**(-n)*(c*(20*2**n*n + 60*2**n + 8*sqrt(5)*((1 - sqrt(5))**n - (1 + sqrt(5))**n) + sqrt(5)*((1 - sqrt(5))**(n + 2) - (1 + sqrt(5))**(n + 2))) + 4*sqrt(5)*d*((1 - sqrt(5))**n - (1 + sqrt(5))**n))/20

Эта формула хорошо совпадает со значениями выше для n = 1 .. 10. Но это не похоже на формулу, которая рассчитывается «вручную». (Обратите внимание, что Python использует ** для мощности и резервы ^ для эксклюзивного или.)

В качестве альтернативы можно попробовать Sympy's rsolve, чтобы получить явную формулу: 

from sympy import Function, rsolve
from sympy.abc import n, c, d

f = Function('f')
T = f(n) - f(n-1) - f(n-2) - c*n
s = rsolve(T, f(n), {f(1): d, f(2): d})
print (s.simplify())

Какие выходы: 

2**(1 - n)*d*(-2**n*c*n - 2**(n + 1)*c + c*(1 + sqrt(5))**n - (1 - sqrt(5))**n + (1 + sqrt(5))**n)/(-5*c + sqrt(5)*c + 2*sqrt(5))

и которые, к сожалению, кажутся неправильными.

...