Введение

Образец, определяющий бесконечную последовательность чисел.

В математике рекуррентное соотношение — это уравнение, согласно которому n-й член последовательности чисел равен некоторой комбинации предыдущих членов. Часто в уравнении участвуют только k предыдущих членов последовательности, где k — параметр, не зависящий от n; это число k называется порядком соотношения. Если значения первых k чисел в последовательности заданы, то остальные члены последовательности можно вычислить, многократно применяя уравнение. В линейных рекурренциях n-й член приравнивается к линейной функции от k предыдущих членов. Известным примером является рекуррентное соотношение для чисел Фибоначчи, где порядок равен двум, а линейная функция просто складывает два предыдущих члена. Этот пример представляет собой линейное рекуррентное соотношение с постоянными коэффициентами, поскольку коэффициенты линейной функции (1 и 1) являются константами, не зависящими от n. Для таких соотношений можно выразить общий член последовательности в виде формулы в замкнутой форме. Также важны линейные рекуррентные соотношения с полиномиальными коэффициентами, зависящими от n, поскольку многие распространенные элементарные и специальные функции имеют ряд Тейлора, коэффициенты которого удовлетворяют такому рекуррентному соотношению (см. голономная функция). Решение рекуррентного соотношения означает нахождение решения в замкнутой форме: нерекурсивной функции от n. Концепция рекуррентного соотношения может быть расширена на многомерные массивы, то есть индексированные семейства, индексируемые кортежами натуральных чисел.

От последовательностей к сетям

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

Решение рациональных дифференциальных уравнений первого порядка

Рациональное разностное уравнение первого порядка имеет вид: такое уравнение можно решить, представив его как нелинейное преобразование другой переменной, которая сама эволюционирует линейно. Затем можно использовать стандартные методы для решения линейного разностного уравнения относительно .

Математическая биология

Некоторые из наиболее известных разностных уравнений возникли в результате попыток моделировать динамику популяций. Например, числа Фибоначчи когда-то использовались как модель для роста популяции кроликов. Логистическое отображение используется либо непосредственно для моделирования роста популяции, либо как отправная точка для более детальных моделей динамики популяций. В этом контексте системы разностных уравнений часто используются для моделирования взаимодействия двух или более популяций. Например, модель Николсона-Бейли для взаимодействия хозяина и паразита задается выражением

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

Информатика

Отношения повторения также имеют фундаментальное значение в анализе алгоритмов. Если алгоритм разработан таким образом, что он разбивает проблему на более мелкие подзадачи (принцип "разделяй и властвуй"), его время выполнения описывается рекуррентным соотношением. Простой пример – время, которое алгоритм затрачивает на поиск элемента в упорядоченном векторе из *n* элементов в худшем случае. Наивный алгоритм будет осуществлять поиск слева направо, по одному элементу за раз. Наихудший сценарий возникает, когда искомый элемент находится в конце, поэтому количество сравнений равно *n*.

Более эффективный алгоритм называется двоичным поиском. Однако он требует, чтобы вектор был отсортирован. Алгоритм сначала проверяет, находится ли элемент в середине вектора. Если нет, то он проверяет, больше или меньше ли средний элемент, чем искомый. В этот момент половину вектора можно исключить, и алгоритм можно повторно применить к оставшейся половине. Количество сравнений будет определяться выражением

,

временная сложность которого составит .

Экономика

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