Что такое рекуррентная формула

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

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

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

Содержание

Примеры

Приложения

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

См. также

Примечания

Полезное

Смотреть что такое «Рекуррентная формула» в других словарях:

рекуррентная формула — — [Л.Г.Суменко. Англо русский словарь по информационным технологиям. М.: ГП ЦНИИС, 2003.] Тематики информационные технологии в целом EN recurrence formularecursion formula … Справочник технического переводчика

рекуррентная формула — rekurentinė formulė statusas T sritis fizika atitikmenys: angl. recurrence formula vok. Rekursionsformel, f rus. рекуррентная формула, f pranc. formule de récurrence, f … Fizikos terminų žodynas

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

РЕКУРРЕНТНАЯ ТОЧКА — д и н а м и ч е с к о й с и с т е м ы точка хдинамич. системы ft (или, в иных обозначениях, f(t,.), см. [2]), заданной на метрич. пространстве S, удовлетворяющая условию: для всякого e>0 найдется T>0 такое, что все точки траектории ftx… … Математическая энциклопедия

Математическая формула — Эта статья об обозначениях элементарной математики; Для более общего контекста см.: Математические обозначения. Математическая формула (от лат. formula уменьшительное от forma образ, вид) принятая в математике (а также… … Википедия

Источник

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

Смотреть что такое «рекуррентная формула» в других словарях:

Источник

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

Содержание

Определения [ править ]

[math] F_0 = 0,\qquad F_1 = 1,\qquad F_ = F_ + F_, \quad n\geqslant 2, \quad n\in Z[/math]

Для этого можно использовать метод производящих функций (англ. generating function method).

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

Примеры [ править ]

[math]1[/math] пример [ править ]

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

Задано линейное однородное рекуррентное соотношение порядка [math]2[/math] с постоянными коэффициентами:
[math]\begin a_0&<>=<>&0,\\ a_1&<>=<>&1,\\ a_n&<>=<>&5a_-6a_, \quad n\geqslant2.\\ \end [/math]

Будем искать производящую функцию последовательности в виде
[math] G(z)=\displaystyle\sum_^ <\infty>a_nz^n = a_0+a_1z+a_2z^2+\cdots, [/math]

Теперь сложим все уравнения для всех значений [math]n[/math] :
[math] \underbrace^<\infty>a_nz^n>_ <=>z+5\displaystyle\sum_^<\infty>a_z^n-6\displaystyle\sum_^<\infty>a_z^n. [/math]

Аналогичные манипуляции со второй суммой дают нам выражение
[math] \displaystyle\sum_^<\infty>a_z^n = z^2\displaystyle\sum_^<\infty>a_z^ = z^2\displaystyle\sum_^<\infty>a_z^=z^2G(z). [/math]

откуда получаем производящую функцию последовательности в замкнутом виде:
[math] G(z) = \dfrac<1-5z+6z^2>. [/math]

Теперь разобьём дробь на сумму простых дробей:
[math] \dfrac <(1-3z)(1-2z)>= \dfrac<1> <1-3z>— \dfrac<1><1-2z>. [/math]

Из этого разложения следует, что
[math] \dfrac<1><1-3z>= \displaystyle\sum_^<\infty>(3z)^n \quad\mbox< и >\quad \dfrac<1><1-2z>= \displaystyle\sum_^<\infty>(2z)^n. [/math]

С другой стороны, мы искали [math]G(z)[/math] в виде
[math] G(z)=\displaystyle\sum_^ <\infty>a_nz^n, [/math]
поэтому, в силу равенства рядов, [math]a_n=3^n-2^n[/math] (для [math]n\geqslant 0[/math] ).

[math]2[/math] пример: числа Фибоначчи [ править ]

Рассмотрим рекуррентное соотношение для чисел Фибоначчи:
[math]\begin f_0&<>=<>&0,\\ f_1&<>=<>&1,\\ f_n&<>=<>&f_+f_, \quad n\geqslant2.\\ \end [/math]

Первый шаг алгоритма мы уже выполнили, записав рекуррентное соотношение. Выполним второй шаг:
[math]\begin 1\cdot f_0&<>=<>&0\cdot 1,\\ z\cdot f_1&<>=<>&1\cdot z,\\ z^n\cdot f_n&<>=<>&(f_+f_)\cdot z^n, \quad n\geqslant2.\\ \end [/math]

Складываем все строчки:
[math] f_0 + f_1 z + \displaystyle\sum_^<\infty>f_nz^n = z + \displaystyle\sum_^<\infty>f_z^n+\displaystyle\sum_^<\infty>f_z^n. [/math]

Третий шаг алгоритма требует привести все суммы к замкнутому виду:
[math]\begin G(z) &<>=<>& z + z\displaystyle\sum_^<\infty>f_z^+z^2\displaystyle\sum_^<\infty>f_z^, \\ G(z) &<>=<>& z + z\displaystyle\sum_^<\infty>f_z^n+z^2\displaystyle\sum_^<\infty>f_z^n, \\ G(z)&<>=<>& \displaystyle z + z(G(z)-f_0)+z^2G(z),\\ G(z)&<>=<>& \displaystyle z + zG(z)+z^2G(z),\\ \end [/math]

откуда получаем замкнутое выражение для производящей функции:
[math] G(z) = \dfrac<1-z-z^2>. [/math]

Осталось разложить её в ряд (чего требует четвёртый шаг алгоритма). С этой целью нужно разложить знаменатель на множители. Найдем корни уравнения:
[math]\displaylines< 1-z-z^2 = 0 \cr z_1=-\dfrac<1-\sqrt<5>><2>, z_2=-\dfrac<1+\sqrt<5>><2>. > [/math]

Нам известно разложение следующей рациональной функции:
[math] \dfrac<1> <1-z>= \displaystyle\sum_^<\infty>z^n = 1 + z + z^2 + z^3 + \cdots. [/math]

Рассмотрим первую дробь и поделим в ней числитель и знаменатель на [math]z_1[/math] :
[math] \dfrac = \dfrac1\dfrac<1><1-\dfrac> = \dfrac1\displaystyle\sum_^<\infty>\dfrac. [/math]

Аналогично (но с делением на [math]z_2[/math] ) поступим со второй дробью:
[math] \dfrac = \dfrac1\dfrac1<1-\dfrac> = \dfrac1\displaystyle\sum_^<\infty>\dfrac. [/math]

[math]3[/math] пример [ править ]

Рекуррентное соотношение:
[math] \begin a_0 = f_0^2 = 1 \\ a_1 = f_1^2 = 1 \\ a_2 = f_2^2 = 4 \\ a_n = 2a_ + 2a_ — a_, \quad n\geqslant3.\\ \end [/math]

[math]4[/math] пример [ править ]

Рассмотрим следующее рекуррентное соотношение:
[math]\begin a_0&<>=<>&1,\\ a_1&<>=<>&2,\\ a_n&<>=<>&6a_-8a_+n, \quad n\geqslant2.\\ \end [/math]

Вспомним, что
[math] (z^n)’ = nz^, [/math]

поэтому
[math] \displaystyle\sum_^<\infty>nz^n=z\displaystyle\sum_^<\infty>nz^=z\displaystyle\sum_^<\infty>(z^n)’=z\biggl(\displaystyle\sum_^<\infty>z^n\biggr)’. [/math]

Последняя сумма может быть свёрнута:
[math] \displaystyle\sum_^<\infty>z^n=\displaystyle\sum_^<\infty>z^n-1-z=\dfrac<1><1-z>-1-z=\dfrac<1-z>. [/math]

Подставив свёрнутое выражение обратно, имеем,
[math] z\biggl(\displaystyle\sum_^<\infty>z^n\biggr)’ = z \biggl(\dfrac<1-z>\biggr)’=\dfrac<(1-z)^2>. [/math]

Это уравнение для производящей функции. Из него выражаем [math]G(z)[/math] :
[math] G(z) = \dfrac<1-6z+11z^2-5z^3><(1-6z+8z^2)(1-z)^2>. [/math]

Дальше мы знаем что делать со всеми этими дробями, кроме, разве лишь, первой. Рассмотрим её (без множителя) подробнее:
[math] \dfrac<1> <(1-z)^2>=(1-z)^ <-2>=\displaystyle\sum_^<\infty>\binom<-2>(-z)^n=\displaystyle\sum_^<\infty>(-1)^n\binom<1>(-z)^n =\displaystyle\sum_^<\infty>(n+1)z^n. [/math]

Источник

Дискретная математика — рекуррентное соотношение

Определение

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

Линейные рекуррентные отношения

Линейное рекуррентное уравнение степени k или порядка k — это рекуррентное уравнение в формате x n = A 1 x n − 1 + A 2 x n − 1 + A 3 x n − 1 + d o t s A k x n k ( A n — константа, а A k n e q 0 ) на последовательности чисел как полинома первой степени.

Вот некоторые примеры линейных рекуррентных уравнений —

Рецидив отношений	Начальные значения	Решения
F _n = F _n-1 + F _n-2	a ₁ = a ₂ = 1	Число Фибоначчи
F _n = F _n-1 + F _n-2	а ₁ = 1, а ₂ = 3	Номер Лукаса
F _n = F _n-2 + F _n-3	a ₁ = a ₂ = a ₃ = 1	Падовская последовательность
F _n = 2F _n-1 + F _n-2	a ₁ = 0, a ₂ = 1	Число Пелла

Как решить линейное рекуррентное соотношение

Характеристическое уравнение для вышеуказанного рекуррентного соотношения —

Три случая могут возникнуть при поиске корней —

Характеристическое уравнение рекуррентного соотношения —

Итак, ( x − 3 ) ( x − 2 ) = 0

Корни реальны и различны. Итак, это в форме дела 1

F n = a x n 1 + b x n 2

Здесь F n = a 3 n + b 2 n ( A s x 1 = 3 a n d x 2 = 2 )

1 = F 0 = a 3 0 + b 2 0 = a + b

4 = F 1 = a 3 1 + b 2 1 = 3 a + 2 b

Решая эти два уравнения, мы получаем a = 2 и b = − 1

Следовательно, окончательное решение —

Характеристическое уравнение рекуррентного соотношения —

Следовательно, существует один действительный корень x 1 = 5

Поскольку существует единый действительный корень, он имеет вид случая 2

F n = a x n 1 + b n x n 1

Решая эти два уравнения, мы получаем a = 3 и b = 2 / 5

Характеристическое уравнение рекуррентного соотношения —

Источник

РЕКУРРЕНТНОЕ СООТНОШЕНИЕ

рекуррентная формула,- соотношение вида

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

Лит.:[1] М а р к у ш е в и ч А. И., Возвратные последовательности, 2 изд., М., 1975. С. Н. Артемов.

Смотреть что такое «РЕКУРРЕНТНОЕ СООТНОШЕНИЕ» в других словарях:

рекуррентное соотношение — — [[http://www.rfcmd.ru/glossword/1.8/index.php?a=index d=23]] Тематики защита информации EN recurrence relation … Справочник технического переводчика

линейное рекуррентное соотношение — — [http://www.iks media.ru/glossary/index.html?glossid=2400324] Тематики электросвязь, основные понятия EN linear recurrence … Справочник технического переводчика

Многочлены Эрмита — Многочлены Эрмита определённого вида последовательность многочленов одной вещественной переменной. Многочлены Эрмита возникают в теории вероятностей, в комбинаторике, физике. Эти многочлены названы в честь Шарля Эрмита. Содержание 1… … Википедия

Правильная скобочная последовательность — (ПСП) частный случай скобочной последовательности. Правильные скобочные последовательности образуют язык Дика и формально определяются следующим образом: (пустая строка) ПСП ПСП, взятая в скобки одного типа ПСП ПСП, к которой… … Википедия

Ортогональные многочлены — Пафнутий Львович Чебышёв В математике последовательностью ортогональных многочленов называют бесконечную последовательность действительных многочленов … Википедия

Фибоначчи — (Fibonacci) Фибоначчи первый крупный математик средневековой Европы Десятичная система счисления, арабские цифры, числа, последовательность, уровни, ряд, линии и спираль Фибоначчи Содержание >>>>>>>>> … Энциклопедия инвестора

ВАРИАЦИОННОЕ ИСЧИСЛЕНИЕ — численные методы раздел вычислительной математики, посвященный методам отыскания экстремальных значений функционалов. Численные методы В. и. принято разделять на два больших класса: непрямые и прямые методы. Непрямые методы основаны на… … Математическая энциклопедия

ВОЛЬТЕРРА УРАВНЕНИЕ — интегральное уравнение вида (линейное интегральное В. у. I рода) или вида (линейное интегральное В. у. II род а). Здесь х, s, a действительные числа, (вообще говоря) комплексный параметр, неизвестная функция, заданные функции, суммируемые с… … Математическая энциклопедия

Задача о порядке перемножения матриц — Задача о порядке перемножения матриц классическая задача динамического программирования, в которой дана последовательность матриц и требуется минимизировать количество скалярных операций для вычисления их произведения. Матрицы… … Википедия

Число Стирлинга первого рода — Числа Стирлинга первого рода количество перестановок из n предметов, имеющие ровно k циклов. Содержание 1 Определение 2 Рекуррентное соотношение 3 Пример 4 Свойст … Википедия

Источник