Рекуррентная формула
— формула вида
, выражающая каждый член последовательности
через
предыдущих членов и номер члена последовательности
.
Общая проблематика
вычислений
с использованием рекуррентных формул является предметом теории
рекурсивных функций
.
Рекуррентным уравнением
называется уравнение, связывающее несколько подряд идущих членов некоторой числовой последовательности. Последовательность, удовлетворяющая такому уравнению, называется
рекуррентной последовательностью
.
Примеры
-
Функция
факториала
натурального числа
удовлетворяет рекуррентной формуле:
-
-
Значение
интеграла
удовлетворяет рекуррентной формуле:
-
-
Чтобы определить коэффициенты
, достаточно установить, что
для всех
. После чего сразу получается известный результат:
-
-
Длина стороны при удвоении числа сторон вписанного
правильного
n
-угольника
:
-
-
где
— радиус
описанной окружности
.
Линейные рекуррентные уравнения
Линейное рекуррентное уравнение с постоянными коэффициентами имеет вид:
-
Здесь
— неотрицательные целые числа,
— последовательность чисел,
— постоянные числа,
,
— заданная функция от
.
Однородные линейные рекуррентные уравнения
Предположим, что последовательность чисел
удовлетворяет однородному линейному рекуррентному уравнению
, где
— неотрицательные целые числа,
— заданные постоянные числа и
.
Обозначим через
производящую функцию
последовательности
. Построим многочлен
. Этот многочлен можно рассматривать как производящую функцию последовательности
. Рассмотрим произведение производящих функций
. Коэффициент
при
и
определяется соотношением
и равен нулю. Это означает, что многочлен
имеет степень самое большее
, следовательно степень числителя рациональной функции
меньше степени знаменателя.
Характеристическим многочленом линейного рекуррентного уравнения называется многочлен
. Корни этого многочлена называются характеристическими. Характеристический многочлен можно представить в виде
, где
— различные характеристические корни,
— кратности характеристических корней,
.
Характеристический многочлен
и многочлен
связаны между собой соотношением
. Таким образом,
-
Рациональную функцию можно представить в виде суммы дробей:
-
Каждая дробь в этом выражении имеет вид
, поэтому её можно разложить в степенной ряд следующего вида
-
.
Коэффициент при
в этом ряду равен
-
Следовательно, производящая функция
и
является общим решением линейного рекуррентного уравнения, где
— многочлен от
степени самое большее
.
-
Пример
Пусть требуется найти решение уравнения
c граничными условиями
и
.
Данное уравнение имеет характеристический многочлен
, где
,
. Общее решение имеет вид
. Подставляя
, получаем
,
. Получаем значения
,
. Таким образом
.
Приложения
Существует формула, выражающая общий член
линейной рекуррентной последовательности
через корни её характеристического многочлена. Например, для
последовательности Фибоначчи
такой формулой является
формула Бине
.
Рекуррентные формулы используются для описания времени работы алгоритма, рекурсивно обращающегося к самому себе. В такой формуле время, требуемое для решения задачи объемом ввода
, выражается через время решения вспомогательных подзадач.
См. также
Примечания
-
Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн.
Алгоритмы. Построение и анализ = Introduction To Algorithms / И. Красиков. — Издательский дом "Вильямс", 2005. — С. 79. — 1296 с.
Литература
-
Фудзисава Т., Касами Т.
Математика для радиоинженеров: теория дискретных структур. —
М.
, издательство=Радио и связь, 1984. — 240 с.