На этом шаге мы рассмотрим, где и как можно использовать этот полином.

    Однородное рекуррентное соотношение содержит только T-разности:

    T(n) = - a1T(n - 1) - ... - akT(n - k).    

    Первый шаг его решения состоит в переносе всех членов правой части уравнения в левую:

    T(n) + a1T(n - 1) + ... + akT(n - k) = 0           .    

    После этого подстановкой T(n - z) = x^k-z, где z = 0, ..., k, определяется соответствующий ему характеристический полином:

    xk + a1xk-1 + ... + ak-1x + ak.

    Всё, что мы сделали, - заменили T(n) на x^k, T(n - 1) на x^k-1 и т. д. Коэффициент a_k при T-разности с наименьшим аргументом становится константой полинома. Следующий шаг заключается в нахождении k корней характеристического полинома. Если r_i (i = 1, 2, ..., k) - его корни, то полином можно разложить на множители:

    (x - r1)(x - r2)... (x - rk).

    Если все его корни различны, то формула для T будет такой:

    T(n) = C1r1n + ... + Ckrkn     .     (3.34)

    В итоге значения констант C_i зависят от начальных условий T и могут быть найдены из решения системы k линейных уравнений с k неизвестными переменными. Для составления такой системы уравнений нам требуется k начальных значений T (начальных условий T для малых значений n).

    В следующем примере этот подход применяется к функции Фибоначчи (1.2), приведённой в примере (1.3). Её можно записать следующим образом:

           0,                   если n = 0
    T(n) = 1,                   если n = 1                         (3.35)
           T(n - 1) + T(n - 2), если n > 1,

    Т(n) - Т(n - 1) - Т(n - 2) = 0.

    Это однородное рекуррентное соотношение. Его характеристический полином:

    х2 - x - 1,

    r1 = (1 + √5)/2 и r2 = (1 - √5)/2

    Т(п) = C1r1n + C2r2n = C1((1 + √5)/2)n + C2((1 - √5)/2)n.         (3.36)

    Последний шаг - это нахождение значений констант C решением системы линейных уравнений, которые получаются подстановкой в общую формулу (3.36) малых значений n из начальных условий рекурсивной функции (3.35). Первое, самое простое уравнение получается из якобы избыточного начального условия для n = 0, которое было добавлено в рекурсивное определение (3.35). Для второго уравнения используем начальное условие для n = 1. В результате получаем следующую систему линейных уравнений:

    С1+ С2 = 0 = T(0)
    ((1 + √5)/2)С1 + ((1 - √5)/2)C2 = 1 = T(1)

    Её решение:

    C1 = 1/√5 и C2 = - 1/√5.

    Поэтому функцию Фибоначчи можно записать так:

    Т(n) = F(n) = 1/√5(((1 + √5)/2)n - ((1 - √5)/2)n) ∈ Θ(((1 + √5)/2)n),    (3.37) 

    В качестве следующего примера рассмотрим взаимно-рекурсивные функции (1.17) и (1.18). Для применения к ним нашего метода их нужно переопределить исключительно через самих себя. С одной стороны, B(n) = A(n - 1) подразумевает, что B(n - 1) = A(n - 2). Кроме того, A(2) = 1. Таким образом, A(n) можно переопределить как:

           0,                  если n = 1
    A(n) = 1,                  если n = 2                         (3.38)
           A(n -1) + A(n - 2), если n ≥ 3,

    С другой стороны, поскольку A(n - 1) = B(n) и A(n) = B(n + 1), их можно подставить в (1.17), чтобы получить B(n + 1) = B(n) + B(n - 1). Кроме того, поскольку B(2) = 0, то B(n) можно определить как:

           1,                   если n = 1
    B(n) = 0,                   если n = 2                        (3.39)
           B(n - 1) + B(n - 2), если n ≥ 3,

    Обе эти функции имеют вид (3.36), и единственное различие между ними - в значениях констант. А именно:

    A(n) = (1/2 -1/2√5) ((1 + √5)/2)n + (1/2 + 1/2√5) ((1 - √5)/2)n,      (3.40)

    B(n) = (- 1/2 + 3/2√5) ((1 + √5)/2)n + (- 1/2 - 3/2√5) ((1 - √5)/2)n,    (3.41)

    На следующем шаге мы рассмотрим характеристический полином с кратными корнями.

Предыдущий шаг Содержание Следующий шаг