Рекуррентные вычисления

Введение

Рекуррентной формулой приведения является формула, которая сводит вычисление n-го члена какой-нибудь последовательности (обычно числовой) к вычислению некоторого количества ее предыдущих членов. Как правило, эти члены расположены в изучаемой последовательности достаточно близко от ее n-го члена, их количество от n не зависит, а n-й член может быть выражен через них относительно просто. Однако следует отметить, что вероятны рекуррентные формулы, обладающие и более сложной структурой.

Рекурсивные функции являются одним из самых распространенных вариантов описания общего понятия арифметического алгоритма, то есть такого алгоритма, возможные начальные данные которого выступают как система натуральных чисел, а вероятные результаты использования являются натуральными числами.

Каждая рекурсивная функция может быть задана конечной системой равенств точно определенного типа в том смысле, что ее значения могут быть вычислены при помощи этой системы равенств по четко сформулированным правилам, причем так, что в результате для вычисления значений заданной рекурсивной функции формируется алгоритм необходимого типа.

Арифметические функции, для определения значений которых существуют какие-нибудь алгоритмы, являются вычислимыми. Вычислимые функции призваны играть в математике важнейшие роли. Рекурсивные функции уже по своему определению могут считаться вычислимыми. В некотором смысле верным является и обратное утверждение, а именно, что математическое по своей природе определение рекурсивности может считаться точным аналогом несколько расплывчатого понятия вычислимости.

Рекуррентные вычисления

Рассмотрим простой пример. Популяция лягушек в озере возрастает в четыре раза в течение каждого года. В последний день каждого года сто лягушек вылавливают и отправляют в другие озера. Предположим, что в начале первого года в озере было пятьдесят лягушек. Необходимо определить количество лягушек в начале любых последующих годов.

Обозначим через $a_n$ количество лягушек в начале (n+1)-го года, исходное количество $a_0 = 50$. Тогда, является очевидным, что:

$a_1 = 4 • 50 - 100 = 100, a_2 = 4 • 100 - 100 = 300$,

а в общем случае

$a_{n+1} = 4 • a_n - 100, n = 0,1, 2,...$

Сформированное равенство может считаться самым простым примером рекуррентного соотношения.

Пусть $a_0, a_1 , a_2, . . .$ является произвольной числовой последовательностью. Если для любого $n ≥m$ число $a_{n+m}$ является определенной функцией от m предыдущих членов последовательности, то есть:

$a_{n+m} = f (a_n , a_{n+1}, . . . , a_{n+m-1})$,

то такая последовательность представляет из себя рекуррентную последовательность, а приведенное выше соотношение является рекуррентным соотношением m-го порядка.

В конкретном варианте с линейной функцией f получаем, так называемое, линейное рекуррентное соотношение:

$a_{n+m} = b_1 (n) a_{n+m-1} + b_2 (n) a_{n+m-2} + . . . + b_{m-1} (n) a_{n+1} + b_m (n) a_n + u_n$.

В случае, когда $u_n = 0$ рекуррентное соотношение является однородным, иначе оно будет считаться неоднородным.

Самым простым случаем рекуррентного соотношения является линейное однородное рекуррентное соотношение с постоянными коэффициентами:

$a_{n+m} = b_1 a_{n+m-1} + b_2 a_{n+m-2} + . . . + b_{m-1} a_{n+1} + b_m a_n$ (1)

Можно считать очевидным, что для однозначного задания всех $a_n$ следует вместе с самим рекуррентным соотношением задавать и первые m членов $a_0 , a_1 , . . . , a_{m-1}$ этой последовательности, то есть, это означает, что необходимо выполнить задание начальных условий для рекуррентного соотношения.

Таким образом, если есть рекуррентное соотношение и начальные условия, то это предоставляет возможность последовательно, шаг за шагом, вычислить необходимое наперед заданное количество n членов рекуррентной числовой последовательности. Часто это все, что необходимо иметь при постановке задачи. Другими словами, определение рекуррентного соотношения для исследуемой числовой последовательности $a_n$ может считаться вполне приемлемым, а чаще всего и самым удобным с вычислительной точки зрения решением поставленной комбинаторной задачи.

Но следует заметить, что бывают случаи, когда требуется сформировать в явном виде аналитическое выражение для общего члена an этой последовательности, или, иначе говоря, осуществить решение данного рекуррентного соотношения.

Перед тем как рассмотреть общий случай уравнения (1), необходимо рассмотреть самый простой его вариант, а именно, линейное однородное рекуррентное соотношение первого порядка:

$a_{n+1} = b_1• a_n, n = 0, 1, 2,…$ (2)

$a_0$ является заданным числом.

Решить данное уравнения достаточно просто. В самом деле:

$a_1 = b_1•a_0$;

$a_2 = b_1•a_1 = b_1^2 * a_0; … a_n = b_1^n • a_0$:

Далее сделаем предположение, что известен вид решения, а именно, что решение данного уравнения (2) имеет определенную зависимость от n, а именно:

$a_n = r^n$ для некоторого r.

Используя это предположение, следует подставить это выражение в начальное рекуррентное соотношение (2). В итоге получится следующее равенство:

$r ^{n+1} = b_1 • r^ n$,

из которого непосредственно вытекает, что $r = b_1$, а значение $a_n$ в таком случае получается равно $b_1^n$. Получается, что при $n = 0$ число $a_o = b_1^0 = 1$.

Говоря иначе, $a_n = b_1^n$ является решением поставленной задачи (2), в частности:

$a_0 = 1$.

По этой причине данное решение может считаться частным решением уравнения (2).

Далее необходимо на основании частного решения, сформировать общее решение задачи (2). Прежде всего следует отметить, что каждое частное решение уравнения (2), при умножении на произвольную постоянную «c», по прежнему этому уравнению должно удовлетворять:

$c • b_1^{n+1} = c • b_1 • b_1^n$. Решение типа $c • b_1^n$ предоставляет возможность удовлетворения любым начальным условиям. И в самом деле, если подставить его в начальное условие для уравнения (2), то получается:

$c • b_1^0=a_0, c=a_0, a_n=a_0 • b_1^n$.

Это означает, что решение типа $c • b_1^n$ может считаться общим решением уравнения (2).