нет. Учебное пособие в оронеж 2011 фгбоу впо Воронежский государственный технический университет
![]()
|
Рекуррентные уравнения1.4.1. Определение рекуррентного уравненияРекуррентным соотношением (уравнением, рекуррентной формулой) называется соотношение вида , которое позволяет вычислить все члены последовательности a0,a1,a2,.., если заданы её первые kчленов. k – порядок рекуррентного уравнения. Примеры. 1) an+1 = an + d -–арифметическая прогрессия. 2) an+1 = q ∙ an -–геометрическая прогрессия. 3) an+2 = an + an+1 -–последовательность чисел Фибоначчи. 1.4.2. Решение линейного однородного рекуррентного уравнения В (1) случае, когда рекуррентное уравнение линейно и однородно, то есть выполняется соотношение вида Последовательность a0,a1,a2,.., удовлетворяющая данному уравнению называется возвратной. М (2) ногочлен называется характеристическим многочленом для возвратной последовательности . Корни этого многочлена называются характеристическими. Множество всех последовательностей, удовлетворяющих рекуррентному уравнению (1) называется его общим решением. Общее решение однородного линейного рекуррентного уравнения имеет аналогию с решением линейного дифференциального уравнения. А именно, справедливы теоремы. Теорема 1. Пусть - корень характеристического многочлена (2), тогда последовательность , где c – производная константа, удовлетворяет уравнению (1). Теорема 2. Если - простые корни характеристического многочлена (2), то общее решение рекуррентного уравнения (1) имеет вид: , где c1,c2,..,ck – произвольные константы. Теорема 3. Если - корень кратности (i= 1,2,..,s) характеристического многочлена (2), то общее решение рекуррентного уравнения (1) имеет вид: где cij– произвольные константы. Зная общее решение рекуррентного уравнения (1), по начальным условиям a0, a1,.., ak-1, можно найти неопределенные постоянные cij, и, тем самым, получить частное уравнении (1) с данными начальными условиями. Пример. Найти последовательность {an}, удовлетворяющую рекуррентному уравнению Характеристический многочлен 1 (2) .4.3. Решение линейного неоднородного рекуррентного уравнения Рассмотрим линейное неоднородное рекуррентное уравнение an+k + p1an+k-1 + … + pkan = f(n), (n = 0, 1, 2,…) (3) Пусть {bn} – общее решение однородного уравнения (1). {cn} – частное (конкретное) решение неоднородного уравнения (3). Тогда последовательность {bn + cn} образует общее решение уравнения (3). Таким образом, справедлива теорема. Теорема 4. Общее решение линейного неоднородного рекуррентного уравнения представляется в виде суммы общего решения соответствующего линейного однородного рекуррентного уравнения и некоторого частного решении неоднородного уравнения. В результате, задача нахождения общего решения неоднородного уравнения (3) сводится к нахождению его частного решения. В отдельных случаях имеются рецепты нахождении частного решения. 1сли f(n) = βn, (где β не является корнем характеристического уравнения), то частное решение следует искать в виде cn = Cβn. Тогда, подставляя его в (3), получаем: . Отсюда В результате, частное решение задаётся формулой 2) Пусть f(n)–многочлен степени rот переменной n, и число 1 не является характеристическим корнем. Тогда и частное решение следует искать в виде Подставляя cn в (3) вместо an, получаем Сравнивая коэффициенты левой и правой частей полученного равенства, найдём соотношения для чисел di, позволяющие эти числа определить. Пример. Найти решение рекуррентного уравнения с начальным условием . Решение. Рассмотрим характеристический многочлен данного рекуррентного уравнения . Его корень . Тогда по теореме 1 общее решение соответствующего однородного рекуррентного уравнения задаётся формулой , где – произвольная константа. Так как , т.е. единица не является корнем характеристического многочлена, а правая часть есть многочлен первой степени, то частное решение неоднородного уравнения ищется в виде полинома первой степени с неопределёнными коэффициентами , где и – неизвестные коэффициенты. Подставив вместо в исходное уравнение, получим или . Приравнивая коэффициенты левой и правой части последнего равенства, получаем систему уравнений для определения неизвестных и : . Отсюда, находим: и . Таким образом, частное решение исходного уравнения имеет вид . По теореме 4 получаем общее решение неоднородного рекуррентного уравнения . Из начального условия . В результате, окончательно имеем: . |