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

Рекурентна формула - формула виду $a\_n\; =\; f\; (n,\; a\_,\; a\_,\; \backslash \; dots,\; a\_)$, виражає кожен член послідовності $a\_n$ через $p$ попередніх членів і можливо номер члена послідовності $n$.

Загальна проблематика обчислень з використанням рекурентних формул є предметом теорії рекурсивних функцій.

Рекурентним рівнянням називається рівняння, що зв'язує кілька поспіль членів деякої числової послідовності. Послідовність, яка задовольнить такого рівняння, називається рекуррентной послідовністю.

1, n = 0; \\ (n-1)! \ Cdot n, n \ geqslant 1. \ end

1, n = 1; \\ F_ + F_, n \ geqslant 2. \ end

• значення інтеграла $\backslash \; Textstyle\; I\_n\; =\; \backslash \; int\; \backslash \; sin\; ^\; n\; x\; \backslash ,\; dx$ задовольняє рекуррентной формулою: $I\_n\; =\; \backslash \; frac\; x>\; +\; \backslash \; fracI\_.$

• Рішення диференціального рівняння Бесселя $y\; +\; (1\; /\; x)\; y\; \text{'}+\; (1\; \backslash \; nu\; ^\; 2\; /\; x\; ^\; 2)\; y\; =\; 0$ може бути записано у вигляді статечного ряду: $y\; =\; \backslash \; sum\; \backslash \; limits\_\; ^\; a\_n\; x\; ^.$

Щоб визначити коефіцієнти $a\_n$, досить встановити, що $4n\; (n\; +\; \backslash \; nu)\; a\_n\; +\; a\_\; =\; 0$ для всіх n ⩾ 1. Після чого відразу виходить відомий результат: $a\_n\; =\; \backslash \; fracn!\; (1+\; \backslash \; nu)\; (2\; +\; \backslash \; nu)\; \backslash \; cdots\; (n\; +\; \backslash \; nu)>.$

• Довжина сторони при подвоєнні числа сторін вписаного правильного n -угольніка. $a\; \_\; =\; \backslash \; sqrt\; >>,\; \backslash \; qquad\; n\; \backslash \; ge\; 2,$

де R - радіус описаного кола.

Лінійні рекурентні рівняння

Лінійне рекурентне співвідношення з постійними коефіцієнтами має вигляд:

тут $n$ - невід'ємні цілі числа, $f\_$ - послідовність чисел, $a\_,\; a\_,\; \backslash \; ldots,\; a\_$ - постійні числа, $a\_\; \backslash \; ne\; 0$, $\backslash \; Varphi\; (n)$ - задана функція від $n$.

Однорідні лінійні рекурентні рівняння

Припустимо, що послідовність чисел $f\_,\; f\_,\; \backslash \; dots$ задовольняє однорідному лінійному рекурентному рівняння $f\_\; +\; a\_f\_\; +\; a\_f\_\; +\; \backslash \; ldots\; +\; a\_f\_\; =\; 0$, де $n$ - невід'ємні цілі числа, $a\_,\; \backslash \; ldots,\; a\_$ - задані постійні числа і $a\_\; \backslash \; ne\; 0$.

позначимо через $F\; (z)$ виробляє функцію послідовності $f\_,\; f\_,\; \backslash \; dots$. побудуємо багаточлен $K\; (z)\; =\; 1\; +\; a\_z\; +\; a\_z\; ^\; +\; \backslash \; ldots\; +\; a\_z\; ^$. Цей многочлен можна розглядати як виробляє функцію послідовності $1,\; a\_,\; a\_,\; \backslash \; ldots,\; a\_,\; 0,\; 0,\; \backslash \; dots$. Розглянемо твір виробляють функцій $C\; (z)\; =\; F\; (z)\; K\; (z)$. коефіцієнт $c\_$ при $z\; ^$ і $r>\; 0$ визначається співвідношенням $c\_\; =\; f\_\; 0\; +\; \backslash \; ldots\; +\; f\_\; 0\; +\; f\_\; a\_\; +\; \backslash \; ldots\; +\; f\_\; 1\; =\; f\_\; +\; a\_f\_\; +\; \backslash \; ldots\; +\; a\_f\_$ і дорівнює нулю. Це означає, що многочлен $C\; (z)$ має ступінь щонайбільше $r-1$, отже ступінь чисельника раціональної функції $F\; (z)\; =\; \backslash \; frac$ менше ступеня знаменника.

Характеристичним многочленом лінійного рекурентного рівняння називається многочлен $g\; (z)\; =\; z\; ^\; +\; a\_z\; ^\; +\; \backslash \; ldots\; +\; a\_$. Коріння цього многочлена називаються характеристичними. Характеристичний многочлен можна представити у вигляді $g\; (z)\; =\; (z-\; \backslash \; alpha\; \_)\; ^>\; (z-\; \backslash \; alpha\; \_)\; ^>\; \backslash \; cdots\; (z-\; \backslash \; alpha\; \_)\; ^>$, де $\backslash \; Alpha\_,\; \backslash \; ldots,\; \backslash \; alpha\_$ - різні характеристичні корені, $e\_,\; \backslash \; ldots,\; e\_$ - кратності характеристичних коренів, $e\_\; +\; e\; \_\; +\; \backslash \; ldots\; +\; e\_\; =\; r$.

характеристичний многочлен $g\; (z)$ і многочлен $K\; (z)$ пов'язані між собою співвідношенням $K\; (z)\; =\; z\; ^\; g\; (\backslash \; frac)$. Таким чином,

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

Кожна дріб в цьому виразі має вигляд $\backslash \; Beta\; (1\; \backslash \; alpha\; z)\; ^$, тому її можна розкласти в степеневий ряд такого вигляду

коефіцієнт при $z\; ^\; n$ в цьому ряді дорівнює

Отже, що виробляє функція $F\; (z)\; =\; \backslash \; sum\; \_\; ^\; (\backslash \; sum\_\; ^\; p\_\; (n)\; \backslash \; alpha\; \_\; ^)\; z\; ^$ і $f\; \_\; =\; \backslash \; sum\_\; ^\; p\_\; (n)\; \backslash \; alpha\_\; ^$ є загальним рішенням лінійного рекурентного рівняння, де $p\_\; (n)$ - многочлен від $n$ ступеня щонайбільше $e\_-1$.

Нехай потрібно знайти рішення рівняння $f\_-f\_\; +\; f\_\; =\; 0$ c граничними умовами $f\_\; =\; 1$ і $f\_\; =\; 1$.

додатки

Існує формула, що виражає загальний член лінійної рекурентної послідовності через коріння її характеристичного многочлена. Наприклад, для послідовності Фібоначчі такою формулою є формула Біне. Рекурентні формули використовуються для опису часу роботи алгоритму, рекурсивно звертається до самого себе. У такій формулі час, необхідний для вирішення задачі обсягом введення n. виражається через час вирішення допоміжних підзадач. [1]

Примітки

література