Interested Article - Рекуррентная формула

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

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

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

Примеры

  • Значение интеграла удовлетворяет рекуррентной формуле:
Чтобы определить коэффициенты , достаточно установить, что для всех . После чего сразу получается известный результат:
  • Длина стороны при удвоении числа сторон вписанного правильного n -угольника :
где — радиус описанной окружности .

Линейные рекуррентные уравнения

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

Здесь — неотрицательные целые числа, — последовательность чисел, — постоянные числа, , — заданная функция от .

Однородные линейные рекуррентные уравнения

Предположим, что последовательность чисел удовлетворяет однородному линейному рекуррентному уравнению , где — неотрицательные целые числа, — заданные постоянные числа и .

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

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

Характеристический многочлен и многочлен связаны между собой соотношением . Таким образом,

Рациональную функцию можно представить в виде суммы дробей:

Каждая дробь в этом выражении имеет вид , поэтому её можно разложить в степенной ряд следующего вида

.

Коэффициент при в этом ряду равен

Следовательно, производящая функция и является общим решением линейного рекуррентного уравнения, где — многочлен от степени самое большее .

Пример

Пусть требуется найти решение уравнения c граничными условиями и .

Данное уравнение имеет характеристический многочлен , где , . Общее решение имеет вид . Подставляя , получаем , . Получаем значения , . Таким образом .

Приложения

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

См. также

Примечания

  1. Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн. Алгоритмы. Построение и анализ = Introduction To Algorithms / И. Красиков. — Издательский дом "Вильямс", 2005. — С. 79. — 1296 с.

Литература

  • Фудзисава Т., Касами Т. Математика для радиоинженеров: теория дискретных структур. — М. , издательство=Радио и связь, 1984. — 240 с.
Источник —

Same as Рекуррентная формула