Рекуррентное соотношение

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

История

Идея рекуррентного определения последовательностей восходит к древним математикам. В XIII веке итальянский математик Леонардо Пизанский (Фибоначчи) в своей книге «Liber Abaci» (1202 год) описал последовательность, в которой каждое число равно сумме двух предыдущих: 0, 1, 1, 2, 3, 5, 8, 13, … Эта последовательность, названная впоследствии числами Фибоначчи, стала классическим примером рекуррентного соотношения. В XVII–XVIII веках рекуррентные соотношения систематически изучались в связи с решением разностных уравнений. Значительный вклад в теорию рекуррентных соотношений внесли математики Леонард Эйлер, Пьер-Симон Лаплас и Огюстен-Луи Коши. В XX веке с развитием вычислительной техники рекуррентные соотношения стали основой для построения алгоритмов и анализа их сложности.

Определение и форма записи

Рекуррентное соотношение для последовательности \( a_n \) (где \( n \) — натуральное число) обычно записывается в виде:

\[ a_n = f(a_{n-1}, a_{n-2}, \dots, a_{n-k}), \quad n > k, \]

где \( k \) — порядок соотношения (количество предыдущих членов, от которых зависит текущий), а \( f \) — некоторая функция. Для однозначного задания последовательности необходимо также указать начальные условия — значения первых \( k \) членов (например, \( a_0, a_1, \dots, a_{k-1} \)).

Примеры

• Числа Фибоначчи: \( F_n = F_{n-1} + F_{n-2} \), с начальными условиями \( F_0 = 0, F_1 = 1 \). Порядок — 2.
• Факториал: \( n! = n \cdot (n-1)! \), с начальным условием \( 0! = 1 \). Порядок — 1.
• Арифметическая прогрессия: \( a_n = a_{n-1} + d \), где \( d \) — разность. Порядок — 1.
• Геометрическая прогрессия: \( a_n = q \cdot a_{n-1} \), где \( q \) — знаменатель. Порядок — 1.

Классификация

Рекуррентные соотношения классифицируются по нескольким признакам.

По порядку

• Первого порядка: каждый член зависит только от одного предыдущего (например, \( a_n = 2a_{n-1} + 1 \)).
• Второго порядка: каждый член зависит от двух предыдущих (например, числа Фибоначчи).
• Высокого порядка: зависимость от трёх и более предыдущих членов.

По линейности

• Линейные рекуррентные соотношения: функция \( f \) является линейной комбинацией предыдущих членов, возможно, с добавлением неоднородного члена. Общий вид: \( a_n = c_1 a_{n-1} + c_2 a_{n-2} + \dots + c_k a_{n-k} + g(n) \), где \( c_i \) — константы, \( g(n) \) — функция от \( n \). Если \( g(n) = 0 \), соотношение называется однородным, иначе — неоднородным.
• Нелинейные рекуррентные соотношения: включают произведения, степени или другие нелинейные операции над предыдущими членами. Пример: \( a_n = a_{n-1} \cdot a_{n-2} + 1 \).

По постоянству коэффициентов

• С постоянными коэффициентами: коэффициенты \( c_i \) не зависят от \( n \).
• С переменными коэффициентами: коэффициенты зависят от \( n \). Пример: \( a_n = n \cdot a_{n-1} \).

По однородности

• Однородные: \( g(n) = 0 \).
• Неоднородные: \( g(n) \neq 0 \).

Решение рекуррентных соотношений

Решение рекуррентного соотношения — это нахождение явной формулы для \( a_n \), не содержащей рекурсии. Методы решения зависят от типа соотношения.

Линейные однородные с постоянными коэффициентами

Для соотношения \( a_n = c_1 a_{n-1} + c_2 a_{n-2} + \dots + c_k a_{n-k} \) составляется характеристическое уравнение:

\[ r^k - c_1 r^{k-1} - c_2 r^{k-2} - \dots - c_k = 0. \]

Если корни \( r_1, r_2, \dots, r_k \) различны, то общее решение имеет вид:

\[ a_n = A_1 r_1^n + A_2 r_2^n + \dots + A_k r_k^n, \]

где \( A_i \) — константы, определяемые из начальных условий. При наличии кратных корней в решение добавляются множители в виде полиномов от \( n \).

Пример: Для чисел Фибоначчи (\( F_n = F_{n-1} + F_{n-2} \)) характеристическое уравнение: \( r^2 - r - 1 = 0 \). Его корни: \( \varphi = \frac{1+\sqrt{5}}{2} \) (золотое сечение) и \( \psi = \frac{1-\sqrt{5}}{2} \). Общее решение: \( F_n = A \varphi^n + B \psi^n \). Из начальных условий \( F_0 = 0, F_1 = 1 \) получаем формулу Бине:

\[ F_n = \frac{\varphi^n - \psi^n}{\sqrt{5}}. \]

Линейные неоднородные с постоянными коэффициентами

Решение ищется как сумма общего решения однородного уравнения и частного решения неоднородного. Частное решение подбирается в зависимости от вида \( g(n) \) (например, если \( g(n) \) — полином, то частное решение ищется в виде полинома той же степени).

Метод производящих функций

Универсальный метод для линейных рекуррентных соотношений. Последовательности \( a_n \) ставится в соответствие формальный степенной ряд \( A(x) = \sum_{n=0}^\infty a_n x^n \). Рекуррентное соотношение преобразуется в уравнение относительно \( A(x) \), которое затем решается, и коэффициенты разложения дают явную формулу.

Метод подстановки (итерации)

Применяется для простых соотношений первого порядка. Например, для \( a_n = 2a_{n-1} + 1 \) с \( a_0 = 0 \) последовательная подстановка даёт \( a_n = 2^n - 1 \).

Применение

Рекуррентные соотношения широко используются в различных областях.

Комбинаторика

Многие комбинаторные числа определяются рекуррентно. Например, числа Каталана \( C_n \) удовлетворяют соотношению \( C_0 = 1 \), \( C_{n+1} = \sum_{i=0}^n C_i C_{n-i} \) и описывают количество правильных скобочных последовательностей, бинарных деревьев и других комбинаторных структур. Числа Стирлинга, числа Белла, числа Эйлера также задаются рекуррентными формулами.

Теория алгоритмов

Рекуррентные соотношения используются для анализа временной сложности рекурсивных алгоритмов. Например, для алгоритма сортировки слиянием (merge sort) время работы \( T(n) \) удовлетворяет соотношению \( T(n) = 2T(n/2) + O(n) \), решение которого даёт \( T(n) = O(n \log n) \). Для алгоритма быстрой сортировки (quick sort) в среднем случае \( T(n) = T(k) + T(n-k-1) + O(n) \). Метод мастер-теоремы (master theorem) позволяет находить асимптотические решения для многих рекуррентных соотношений вида \( T(n) = aT(n/b) + f(n) \).

Численные методы

Рекуррентные соотношения лежат в основе многих численных алгоритмов. Например, метод Ньютона для нахождения корней уравнения \( f(x) = 0 \) задаётся рекуррентной формулой \( x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)} \). Метод прогонки для решения систем линейных уравнений с трёхдиагональной матрицей также использует рекуррентные вычисления.

Дискретная математика и теория вероятностей

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

Физика и инженерия

В задачах динамики, обработки сигналов, теории управления рекуррентные соотношения описывают дискретные системы. Например, цифровые фильтры (БИХ-фильтры) реализуются с помощью рекуррентных формул вида \( y_n = \sum_{i=0}^M b_i x_{n-i} - \sum_{j=1}^N a_j y_{n-j} \).

Интересные факты

• Числа Фибоначчи, задаваемые простейшим рекуррентным соотношением, встречаются в природе: в расположении листьев на стебле, спиралях подсолнуха, раковинах моллюсков.
• Рекуррентные соотношения могут порождать хаотическое поведение. Например, логистическое отображение \( x_{n+1} = r x_n (1 - x_n) \) при определённых значениях параметра \( r \) демонстрирует детерминированный хаос.
• Для некоторых рекуррентных соотношений, таких как \( a_n = a_{n-1} + a_{n-2} \), существует явная формула (формула Бине), но для многих нелинейных соотношений явное решение найти невозможно, и их исследуют численно.
• В программировании рекуррентные соотношения часто реализуются с помощью рекурсивных функций, но для эффективности их обычно преобразуют в итеративные алгоритмы с использованием динамического программирования (например, вычисление чисел Фибоначчи за линейное время вместо экспоненциального).

Источники

• Грэхем Р., Кнут Д., Паташник О. Конкретная математика. Основание информатики. — М.: Мир, 1998.
• Виноградов И. М. Основы теории чисел. — М.: Наука, 1981.
• Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. Алгоритмы: построение и анализ. — М.: Вильямс, 2013.
• Самарский А. А., Гулин А. В. Численные методы. — М.: Наука, 1989.
• Энциклопедический словарь юного математика / Сост. А. П. Савин. — М.: Педагогика, 1985.