Отношение повторяемости

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

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

Термин разностное уравнение иногда (и для целей этой статьи) относится к определенному типу рекуррентного отношения. Однако «разностное уравнение» часто используется для обозначения любого рекуррентного отношения.

• 1 Определение
• 2 Примеры
  • 2.1 Факториал
  • 2.2 Логистическая карта
  • 2.3 Числа Фибоначчи
  • 2.4 Биномиальные коэффициенты
• 3 Узкое определение отношения к разностным уравнениям
  • 3.1 От последовательностей к сеткам
• 4 Решение
  • 4.1 Решение однородных линейных рекуррентных потоков с постоянными коэффициентами
    • 4.1.1 Корни характерного многочлена
    • 4.1.2 Решение с помощью линейной алгебры
    • 4.1.3 Решение с z-преобразователи
  • 4.2 Решение неоднородных линейных рекуррентных векторов с постоянными коэффициентами
  • 4.3 Решение неоднородных рекуррентных первого порядка с переменными коэффициентами
  • 4.4 Решение общих однородных линейных рекуррентных функций
  • 4.5 Первое решение -порядковые рациональные разностные уравнения
• 5 Устойчивость
  • 5.1 Устойчивость линейных рекуррентных представлений порядка
  • 5.2 Устойчивость линейных рекуррентных представлений первого п орядка
  • 5.3 Устойчивость нелинейных рекуррентных представлений первого порядка
• 6 Связь с дифференциальными уравнениями
• 7 Приложения
  • 7.1 Биология
  • 7.2 Информатика
  • 7.3 Цифровая обработка сигналов
  • 7.4 Экономика
• 8 См. Также
• 9 Примечания
• 10 Ссылки
• 11 Внешние ссылки

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

$un\; =\; \phi \; (n,\; un\; -\; 1)\; для\; n>0,\; \{\backslash \; displaystyle\; u\_\; \{n\}\; =\; \backslash \; varphi\; (n,\; u\_\; \{n\; -1\})\; \backslash \; quad\; \{\backslash \; text\; \{for\}\}\; \backslash \; quad\; n>0,\}$

где

$\phi :\; N\; \times \; X\; \to \; X\; \{\backslash \; displaystyle\; \backslash \; varphi\; \{N\}\; mathbb\}\; \backslash \; times\; X\; Для\; любого$ u\; 0\; \in \; X\; \{\backslash \; displaystyle\; u\_\; \{0\}\; \backslash \; in\; X\}$$, это определяет уникальную последовательность с $u\; 0\; \{\backslash \; displaystyle\; u\_\; \{0\}\}$в качестве первого элемента, называемого начальным значением.

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

Это определяет рекуррентное отношение первого порядка. рядка k имеет вид

$un\; =\; \phi \; (n,\; un\; -\; 1,\; раз\; -\; 2,\dots ,\; un\; -\; k)\; для\; n\; \ge \; K,\; \{\backslash \; displaystyle\; u\_\; \{n\}\; =\; \backslash \; varphi\; (n,\; u\_\; \{n-1\; \},\; u\_\; \{n-2\},\; \backslash \; ldots,\; u\_\; \{nk\})\; \backslash \; quad\; \{\backslash \; text\; \{for\}\}\; \backslash \; quad\; n\; \backslash \; geq\; k,\}$

где $\phi :\; N\; \times \; X\; k\; \to \; X\; \{\; \backslash \; displaystyle\; \backslash \; varphi:\; \backslash \; mathbb\; \{N\}\; \backslash \; times\; X\; ^\; \{k\}\; \backslash \; to\; X\}$- это функция, которая включает в себя последовательные элементы последовательность. В этом случае для установки необходимы k начальных значений.

Примеры

Факториал

Факториал определен рекуррентным использованием

$n!\; =\; п\; (п\; -\; 1)!\; для\; п>0,\; \{\backslash \; displaystyle\; n!\; =\; п\; (п-1)!\; \backslash \; quad\; \{\backslash \; text\; \{for\}\}\; \backslash \; quad\; n>0,\}$

и начальное условие

$0!\; =\; 1.\; \{\backslash \; displaystyle\; 0!\; =\; 1.\}$

Логистическая карта

Примером рекуррентного отношения является логистическая карта :

$xn\; +\; 1\; =\; rxn\; (1\; -\; xn),\; \{\backslash \; displaystyle\; x\_\; \{n\; +\; 1\}\; =\; rx\_\; \{n\}\; (1-x\_\; \{n\}),\}$

с заданной константой r; с учетом начального члена x 0 каждый последующий член определяет этим новым.

Решение рекуррентного отношения означает получение решения в закрытой форме : нерекурсивной функции от n.

Числа Фибоначчи

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

$F\; n\; =\; F\; п\; -\; 1\; +\; F\; п\; -\; 2\; \{\backslash \; displaystyle\; F\_\; \{n\}\; =\; F\_\; \{n-1\}\; +\; F\_\; \{n-2\}\}$

с начальными условиями (начальные значения)

$F\; 0\; =\; 0\; \{\backslash \; displaystyle\; F\_\; \{0\}\; =\; 0\}$

$F\; 1\; =\; 1.\; \{\backslash \; displaystyle\; F\_\; \{1\}\; =\; 1.\}$

В явном виде повторение дает уравнения

$F\; 2\; =\; F\; 1\; +\; F\; 0\; \{\backslash \; Displaystyle\; F\_\; \{2\}\; =\; F\_\; \{1\}\; +\; F\_\; \{0\}\}$

$F\; 3\; =\; F\; 2\; +\; F\; 1\; \{\backslash \; displaystyle\; F\_\; \{3\}\; =\; F\_\; \{2\}\; +\; F\_\; \{1\; \}\}$

$F\; 4\; =\; F\; 3\; +\; F\; 2\; \{\backslash \; displaystyle\; F\_\; \{4\}\; =\; F\_\; \{3\}\; +\; F\_\; \{2\}\}$

и т. Д.

Получаем последовательность чисел Фибоначчи, которая начинается с

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89,...

рекуррентность может быть решена с помощью методов, описанных ниже, что дает формулу Бине, которая включает степени двух корней характерного многочлена t = t + 1; производящая функция последовательность - это рациональная функция

$t\; 1\; -\; t\; -\; t\; 2.\; \{\backslash \; displaystyle\; \{\backslash \; frac\; \{t\}\; \{1-tt\; ^\; \{2\}\}\}.\}$

Биномиальные коэффициенты

Простой пример многомерного рекуррентного отношения дается биномиальными коэффициентами $(nk)\; \{\backslash \; displaystyle\; \{\backslash \; tbinom\; \{n\}\; \{k\}\}\}$, которые подсчитывают количество способов выбора k элементов из набора n элементов. Их можно вычислить по рекуррентному применению

$(nk)\; =\; (n\; -\; 1\; k\; -\; 1)\; +\; (n\; -\; 1\; k),\; \{\backslash \; displaystyle\; \{\backslash \; binom\; \{n\}\; \{k\}\}\; =\; \{\backslash \; binom\; \{n\; -1\; \}\; \{k-1\}\}\; +\; \{\backslash \; binom\; \{n-1\}\; \{k\}\},\}$

с базовыми случаями $(n\; 0)\; =\; (nn)\; =\; 1\; \{\backslash \; displaystyle\; \{\backslash \; tbinom\; \{n\}\; \{0\}\}\; =\; \{\backslash \; tbinom\; \{n\}\; \{n\}\}\; =\; 1\}$. Использование этой формулы для вычислений значений всех биномиальных средств создания бесконечный массив, называемый треугольником Паскаля. Те же значения также могут быть вычислены напрямую по другой формуле, которая не является повторением, но требует умножения, а не просто сложения для вычислений: $(n\; k)\; =\; n!\; к!\; (п\; -\; к)!.\; \{\backslash \; displaystyle\; \{\backslash \; binom\; \{n\}\; \{k\}\}\; =\; \{\backslash \; frac\; \{n!\}\; \{k!\; (nk)!\}\}.\}$

Отношение к разностным уравнениям в узкомопределении

Учитывая упорядоченное последовательность $\{an\}\; n\; =\; 1\; \infty \; \{\backslash \; displaystyle\; \backslash \; left\; \backslash \; \{\; a\_\; \{n\}\; \backslash \; right\; \backslash \}\; \_\; \{n\; =\; 1\}\; ^\; \{\backslash \; infty\}\}$из действительных чисел : первая разность $\Delta \; (an)\; \{\backslash \; displaystyle\; \backslash \; Delta\; (a\_\; \{n\})\}$означает как

$\Delta \; (an)\; =\; an\; +\; 1\; -\; an.\; \{\backslash \; displaystyle\; \backslash \; Delta\; (a\_\; \{n\})\; =\; a\_\; \{n\; +\; 1\}\; -a\_\; \{n\}.\}$

секундная разница $\Delta \; 2\; (an)\; \{\backslash \; displaystyle\; \backslash \; Delta\; ^\; \{2\}\; (a\_\; \{n\})\}$определяется как

$\Delta \; 2\; (an)\; =\; \Delta \; (an\; +\; 1)\; -\; \Delta \; (an),\; \{\backslash \; displaystyle\; \backslash \; Delta\; ^\; \{2\}\; (a\_\; \{n\})\; =\; \backslash \; Delta\; (a\_\; \{n\; +\; 1\})\; -\; \backslash \; Delta\; (a\_\; \{n\}),\}$

, которое может быть упрощено до

$\Delta \; 2\; (an)\; =\; an\; +\; 2\; -\; 2\; ан\; +\; 1\; +\; ан.\; \{\backslash \; displaystyle\; \backslash \; Delta\; ^\; \{2\}\; (a\_\; \{n\})\; =\; a\_\; \{n\; +\; 2\}\; -2a\_\; \{n\; +\; 1\}\; +\; a\_\; \{n\}.\}$

В общем: k-я разница следовать a n, записанной как $\Delta \; k\; (an)\; \{\backslash \; displaystyle\; \backslash \; Delta\; ^\; \{k\}\; (a\_\; \{n\})\}$рекурсивно определяется как

$\Delta \; k\; (an)\; =\; \Delta \; k\; -\; 1\; (an\; +\; 1)\; -\; \Delta \; k\; -\; 1\; (an)\; =\; \sum \; t\; =\; 0\; k\; (kt)\; (-\; 1)\; tan\; +\; k\; -\; t.\; \{\backslash \; displaystyle\; \backslash \; Delta\; ^\; \{k\}\; (a\_\; \{n\})\; =\; \backslash \; Delta\; ^\; \{k-1\}\; (a\_\; \{n\; +\; 1\})\; -\; \backslash \; Delta\; ^\; \{k-1\}\; (a\_\; \{n\})\; =\; \backslash \; сумма\; \_\; \{t\; =\; 0\}\; ^\; \{k\}\; \{\backslash \; binom\; \{k\}\; \{t\}\}\; (-\; 1)\; ^\; \{t\}\; a\_\; \{n\; +\; kt\}.\}$

(Последовательность и ее различия связаны между собой биномиальное преобразование.) Более ограничительное определение разностного уравнения - это уравнение, составленное из n и его разностей k. (Широко используемое более широкое определение трактует «разностное уравнение» как синоним «рекуррентного отношения». См.,, уравнение рациональных разностей и матричное разностное уравнение.)

Фактически, легко видеть, что,

$an\; +\; k\; =\; (k\; 0)\; an\; +\; (k\; 1)\; \Delta \; (an)\; +\; \cdots \; +\; (kk)\; \Delta \; k\; (an).\; \{\backslash \; displaystyle\; a\_\; \{n\; +\; k\}\; =\; \{k\; \backslash \; choose\; 0\}\; a\_\; \{n\}\; +\; \{k\; \backslash \; choose\; 1\}\; \backslash \; Delta\; (a\_\; \{n\})\; +\; \backslash \; cdots\; +\; \{k\; \backslash \; choose\; k\}\; \backslash \; Delta\; ^\; \{k\; \}\; (a\_\; \{n\}).\}$

Таким образом, разностное уравнение может быть определено как уравнение, которое включает n, a n-1, a n - 2 и т. Д. (или эквивалентно a n, a n + 1, a n + 2 и т. д.)

Времен разностные уравнения являются очень распространенной повторения, некоторые используют эти два термина как синонимы. Например, разностное уравнение

$3\; \Delta \; 2\; (an)\; +\; 2\; \Delta \; (an)\; +\; 7\; an\; =\; 0\; \{\backslash \; displaystyle\; 3\; \backslash \; Delta\; ^\; \{2\}\; (a\_\; \{n\})\; +\; 2\; \backslash \; Delta\; (a\_\; \{n\})\; +\; 7a\_\; \{n\}\; =\; 0\}$

эквивалентно рекуррентному изданию

$3\; an\; +\; 2\; =\; 4\; an\; +\; 1\; -\; 8\; an.\; \{\backslash \; displaystyle\; 3a\_\; \{n\; +\; 2\}\; =\; 4a\_\; \{n\; +\; 1\}\; -8a\_\; \{n\}.\}$

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

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

Уравнения суммирования к разностным уравнениям как интеграл уравнения отношения к различным уравнениям.

От последовательностей к сеткам

Однопеременные или одномерные рекуррентные отношения между к последовательностям (т. Е. Функции, определенным на одномерных сетках). Многопараметрические или n-мерные рекуррентные отношения к n-мерным сеткам. Функции, на n-сетках, также могут быть изучены с помощью уравнения в частных разностях .

Решение

Решение однородных линейных рекуррентных функций с постоянными коэффициентами

Корни соответствующего полинома

Порядок-d однородная линейная повторяемость с постоянными коэффициентами - это уравнение вида

$an\; =\; c\; 1\; an\; -\; 1\; +\; c\; 2\; an\; -\; 2\; +\; \cdots \; +\; cdan\; -\; d,\; \{\backslash \; displaystyle\; a\_\; \{n\}\; =\; c\_\; \{1\}\; a\_\; \{n-1\}\; +\; c\_\; \{2\}\; a\_\; \{n-2\}\; +\; \backslash \; cdots\; +\; c\_\; \{d\}\; a\_\; \{nd\},\}$

где коэффициенты dc i (для всех i) - константы, а $cd\; \ne \; 0\; \{\backslash \; displaystyle\; c\_\; \{d\}\; \backslash \; neq\; 0\}$.

A константно-рекурсивная последовательность - последовательность, удовлетворяющая повторение этой формы. Существует d степеней свободы для этой проблемы, то есть начальные значения $a\; 0,\dots ,\; ad\; -\; 1\; \{\backslash \; displaystyle\; a\_\; \{0\},\; \backslash \; dots,\; a\_\; \{d-1\}\}$можно принять любые значения, но тогда повторение однозначно определяет последовательность.

Те же коэффициенты дают характеристический многочлен (также «вспомогательный многочлен»)

$p\; (t)\; =\; td\; -\; c\; 1\; td\; -\; 1\; -\; c\; 2\; td\; -\; 2\; -\; \cdots \; -\; cd\; \{\backslash \; displaystyle\; p\; (t)\; =\; t\; ^\; \{d\}\; -c\_\; \{1\}\; t\; ^\; \{d-1\}\; -c\_\; \{2\}\; t\; ^\; \{d-2\}\; -\; \backslash \; cdots\; -c\_\; \{d\}\}$

чьи корни играют решающую роль в поиске и понимании последовательностей, удовлетворяющих повторению. Если корни r 1, r 2,... все разные, каждое решение рекурсии принимает форму

$an\; =\; k\; 1\; r\; 1\; n\; +\; k\; 2\; р\; 2\; N\; +\; \cdots \; +\; kdrdn,\; \{\backslash \; displaystyle\; a\_\; \{n\}\; =\; k\_\; \{1\}\; r\_\; \{1\}\; ^\; \{n\}\; +\; k\_\; \{2\}\; r\_\; \{2\}\; ^\; \{n\}\; +\; \backslash \; cdots\; +\; k\_\; \{d\}\; r\_\; \{d\}\; ^\; \{\; n\},\}$

, где коэффициенты k i соответствуют условиям, соответствующим начальным повторения. Когда одни и те же корни попадают в несколько различных членов этой формулы, соответствующие вторым и последующим вхождения одного и того же корня, умножаются на возрастающие степени n. Например, если характерный многочлен, можно разложить на множители как (x - r), причем один и тот же корень r три встречается раза, то решение будет иметь вид

$an\; =\; k\; 1\; rn\; +\; k\; 2\; nrn\; +\; k\; 3\; n\; 2\; рн.\; \{\backslash \; displaystyle\; a\_\; \{n\}\; =\; k\_\; \{1\}\; r\; ^\; \{n\}\; +\; k\_\; \{2\}\; nr\; ^\; \{n\}\; +\; k\_\; \{3\}\; n\; ^\; \{2\}\; r\; ^\; \{n\}.\}$

А также Фибоначчи, другие константно-рекурсивные числа включают числа Люка и следовать Люка, числа Якобсталя, числа Пелла числа и в более общем плане решения уравнения Пелла.

Для порядка 1 повторение

$an\; =\; выполнено\; -\; 1\; \{\backslash \; displaystyle\; a\_\; \{n\}\; =\; ra\_\; \{n-1\}\}$

имеет решение a n = r с 0 = 1, и наиболее общим решением является n = kr с 0 = k. Характеристический полином, приравненный к нулю (характеристическое уравнение ), равенство просто t - r = 0.

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

Рассмотрим, например, рекуррентное отношение

$an\; =\; A\; an\; -\; 1\; +\; B\; an\; -\; 2.\; \{\backslash \; displaystyle\; a\_\; \{n\}\; =\; Aa\_\; \{n-1\}\; +\; Ba\_\; \{n-2\}.\; \}$

Когда у него есть решение той же общей формы, что и n = r? Подставляя это предположение (анзац ) в рекуррентное соотношение, мы находим, что

$rn\; =\; A\; rn\; -\; 1\; +\; B\; rn\; -\; 2\; \{\backslash \; displaystyle\; r\; ^\; \{n\}\; =\; Ar\; ^\; \{n-1\}\; +\; Br\; ^\; \{n-2\}\}$

должно быть истинным для всех n>1.

Разделив на r, мы получим, что все эти уравнения сводятся к одному и тому же:

$r\; 2\; =\; A\; r\; +\; B,\; \{\backslash \; displaystyle\; r\; ^\; \{2\}\; =\; Ar\; +\; B,\}$

$r\; 2\; -\; A\; r\; -\; B\; =\; 0,\; \{\backslash \; displaystyle\; r\; ^\; \{2\}\; -Ar-B\; =\; 0,\}$

, которое является типичным уравнением рекуррентного отношения. Решите относительно r, чтобы получить два корня λ 1, λ 2 : эти корни известны как характеристические корни или собственные значения анализическое уравнение. В зависимости от природы корней получаются разные решения: если эти корни разные, мы имеем общее решение

$an\; =\; C\; \lambda \; 1\; n\; +\; D\; \lambda \; 2\; n\; \{\backslash \; displaystyle\; a\_\; \{n\}\; =\; C\; \backslash \; lambda\; \_\; \{1\}\; ^\; \{n\; \}\; +\; D\; \backslash \; lambda\; \_\; \{2\}\; ^\; \{n\}\}$

, а если они идентичны (когда A + 4B = 0), мы имеем

$an\; =\; C\; \lambda \; n\; +\; D\; \lambda \; n\; \{\backslash \; displaystyle\; a\_\; \{n\}\; =\; C\; \backslash \; lambda\; ^\; \{n\}\; +\; Dn\; \backslash \; lambda\; ^\; \{n\}\}$

Это наиболее общее общее решение; две константы C и D могут быть выбраны на основе двух заданных начальных условий a 0 и 1 для получения конкретного решения.

В случае комплексных собственных значений (которые также приводят к комплексным значениям для параметров решения C и D) использование комплексных чисел можно исключить, переписать решение в тригонометрической форме. В этом случае мы можем записать собственные значения как $\lambda \; 1,\; \lambda \; 2\; =\; \alpha \; \pm \; \beta \; i.\; \{\backslash \; displaystyle\; \backslash \; lambda\; \_\; \{1\},\; \backslash \; lambda\; \_\; \{2\}\; =\; \backslash \; alpha\; \backslash \; pm\; \backslash \; beta\; i.\}$Тогда можно показать, что

$an\; =\; C\; \lambda \; 1\; n\; +\; D\; \lambda \; 2\; n\; \{\backslash \; displaystyle\; a\_\; \{n\}\; =\; C\; \backslash \; lambda\; \_\; \{1\}\; ^\; \{n\}\; +\; D\; \backslash \; lambda\; \_\; \{2\}\; ^\; \{n\}\}$

можно переписать как

$an\; =\; 2\; M\; n\; (E\; соз\; \; (\theta \; n)\; +\; F\; грех\; \; (\theta \; n))\; =\; 2\; GM\; n\; соз\; \; (\theta \; n\; -\; \delta ),\; \{\backslash \; displaystyle\; a\_\; \{n\}\; =\; 2M\; ^\; \{n\}\; \backslash \; left\; (E\; \backslash \; cos\; (\backslash \; theta\; n)\; +\; F\; \backslash \; sin\; (\backslash \; theta\; n)\; \backslash \; right)\; =\; 2GM\; ^\; \{n\}\; \backslash \; cos\; (\backslash \; theta\; n-\; \backslash \; delta),\}$

где

$M\; =\; \alpha \; 2\; +\; \beta \; 2\; cos\; \; (\theta )\; знак\; равно\; \alpha \; M\; грех\; \; (\theta )\; =\; \beta \; MC,\; D\; =\; E\; \mp \; F\; я\; G\; =\; E\; 2\; +\; F\; 2\; соз\; \; (\delta )\; =\; EG\; sin\; \; (\delta )\; =\; FG\; \{\backslash \; displaystyle\; \{\backslash \; begin\; \{array\}\; \{\; lcl\}\; M\; =\; \{\backslash \; sqrt\; \{\backslash \; alpha\; ^\; \{2\}\; +\; \backslash \; beta\; ^\; \{2\}\}\}\; \backslash \; cos\; (\backslash \; theta)\; =\; \{\backslash \; tfrac\; \{\backslash \; alpha\}\; \{M\}\}\; и\; \backslash \; sin\; (\backslash \; theta)\; =\; \{\backslash \; tfrac\; \{\backslash \; beta\}\; \{M\}\}\; \backslash \backslash \; C,\; D\; =\; E\; \backslash \; mp\; Fi\; \backslash \backslash \; G\; =\; \{\backslash \; sqrt\; \{E\; ^\; \{2\}\; +\; F\; ^\; \{2\}\}\}\; \backslash \; cos\; (\backslash \; delta)\; =\; \{\backslash \; tfrac\; \{E\}\; \{G\}\}\; \backslash \; sin\; (\backslash \; delta)\; =\; \{\backslash \; tfrac\; \{F\}\; \{G\}\}\; \backslash \; end\; \{array\}\}\}$

Здесь E и F (или, что эквивалентно, G и δ) - действительные константы, зависящие от начальных усл овий. Используя

$\lambda \; 1\; +\; \lambda \; 2\; =\; 2\; \alpha \; =\; A,\; \{\backslash \; displaystyle\; \backslash \; lambda\; \_\; \{1\}\; +\; \backslash \; lambda\; \_\; \{2\}\; =\; 2\; \backslash \; alpha\; =\; A,\}$

$\lambda \; 1\; \cdot \; \lambda \; 2\; =\; \alpha \; 2\; +\; \beta \; 2\; =\; -\; B,\; \{\backslash \; displaystyle\; \backslash \; lambda\; \_\; \{1\}\; \backslash \; cdot\; \backslash \; lambda\; \_\; \{2\}\; =\; \backslash \; alpha\; ^\; \{2\}\; +\; \backslash \; beta\; ^\; \{2\}\; =\; -\; B,\}$

можно упростить решение, данное выше как

$an\; =\; (-\; B)\; n\; 2\; (E\; cos\; \; (\theta \; n)\; +\; F\; sin\; \; (\theta \; n)),\; \{\backslash \; displaystyle\; a\_\; \{n\}\; =\; (-\; B)\; ^\; \{\backslash \; frac\; \{n\; \}\; \{2\}\}\; \backslash \; left\; (E\; \backslash \; cos\; (\backslash \; theta\; n)\; +\; F\; \backslash \; sin\; (\backslash \; theta\; n)\; \backslash \; right),\}$

где a 1 и a 2 - начальные условия, а

$E\; =\; -\; A\; a\; 1\; +\; a\; 2\; BF\; =\; -\; i\; A\; 2\; a\; 1\; -\; A\; a\; 2\; +\; 2\; a\; 1\; BBA\; 2\; +\; 4\; B\; \theta \; =\; arccos\; \; (A\; 2\; -\; B)\; \{\; \backslash \; displaystyle\; \{\backslash \; begin\; \{align\}\; E\; =\; \{\backslash \; frac\; \{-Aa\_\; \{1\}\; +\; a\_\; \{2\}\}\; \{B\}\}\; \backslash \backslash \; F\; =\; -\; i\; \{\backslash \; frac\; \{A\; ^\; \{2\}\; a\_\; \{1\}\; -\; Aa\_\; \{2\}\; +\; 2a\_\; \{1\}\; B\}\; \{B\; \{\backslash \; sqrt\; \{A\; ^\; \{2\}\; +\; 4B\}\}\}\}\; \backslash \backslash \backslash \; theta\; =\; \backslash \; arccos\; \backslash \; left\; (\{\backslash \; frac\; \{A\}\; \{2\; \{\backslash \; sqrt\; \{-B\}\}\}\}\; \backslash \; right)\; \backslash \; end\; \{align\}\}\}$

Таким образом, нет необходимости решать для λ 1 и λ 2.

Во всех случаях - действующие существующие собственные значения, действительные дублир ованные собственные значения и комплексно сопряженные собственные значения - уравнение устойчиво (то есть переменная сходится к фиксированное значение [в частности, ноль]) тогда и только тогда, когда оба значения меньше единицы в абсолютном значении. В этом случае второго порядка можно показать, что это условие на собственные значения эквивалентно | А | < 1 − B < 2, which is equivalent to |B| < 1 and |A| < 1 − B.

Уравнение в приведенном выше примере однородным в том смысле, что не было постоянного члена. Если начать с неоднородного повторения

$bn\; =\; A\; bn\; -\; 1\; +\; B\; bn\; -\; 2\; +\; K\; \{\backslash \; displaystyle\; b\_\; \{n\}\; =\; Ab\_\; \{n-1\}\; +\; Bb\_\; \{n-2\}\; +\; K\}$

с постоянным членом K, это можно преобразовать в однородную форму следующим образом: установившееся состояние находится путем установки b n = b n - 1 = b n - 2 = b *, чтобы получить

$b\; \ast \; =\; K\; 1\; -\; A\; -\; B.\; \{\backslash \; displaystyle\; b\; ^\; \{*\}\; =\; \{\backslash \; frac\; \{K\}\; \{1-AB\}\}.\}$

Тогда неоднородное повторение можно переписать в однородной форме как

$[bn\; -\; b\; \ast ]\; =\; A\; [bn\; -\; 1\; -\; b\; *]\; +\; B\; [bn\; -\; 2\; -\; b\; *],\; \{\backslash \; displaystyle\; [b\_\; \{n\}\; -b\; ^\; \{*\; \}]\; =\; A\; [b\_\; \{n-1\}\; -b\; ^\; \{*\}]\; +\; B\; [b\_\; \{n-2\}\; -b\; ^\; \{*\}],\}$

который можно решить, как указано выше.

Условие устойчивости, указанное в приведенных выше условиях для случая второго порядка, остается в силе для общего случая n-го порядка: уравнение устойчиво устойчивым тогда и только тогда, когда все собственные значения уравнения меньше единицы в абсолютная величина.

Для данного однородного вспомогательного рекуррентного отношения с постоянными факторами порядка d, пусть p (t) будет характерным многочленом (также «линейным многочленом»)

$td\; -\; c\; 1\; td\; -\; 1\; -\; с\; 2\; td\; -\; 2\; -\; \cdots \; -\; cd\; =\; 0\; \{\backslash \; displaystyle\; t\; ^\; \{d\}\; -c\_\; \{1\}\; t\; ^\; \{d-1\}\; -c\_\; \{2\}\; t\; ^\; \{d-2\}\; -\; \backslash \; cdots\; -c\_\; \{d\; \}\; =\; 0\}$

, так что каждый c i соответствует каждому c i в исходном рекуррентном (см. Общую формулу выше). Предположим, что λ - корень p (t), имеющий кратность r. Это означает, что (t - λ) делит p (t). Выполняются следующие два свойства:

1. Каждая из последовательностей $\lambda \; n,\; n\; \lambda \; n,\; n\; 2\; \lambda \; n,\dots ,\; nr\; -\; 1\; \lambda \; n\; \{\backslash \; displaystyle\; \backslash \; lambda\; ^\; \{n\},\; n\; \backslash \; lambda\; ^\; \{n\; \},\; n\; ^\; \{2\}\; \backslash \; lambda\; ^\; \{n\},\; \backslash \; dots,\; n\; ^\; \{r-1\}\; \backslash \; lambda\; ^\; \{n\}\}$удовлетворяет рекуррентному применению.
2. Любую последовательность, удовлетворяющую рекуррентному записать, можно однозначно выполнить линейную комбинацию решений, построенных в части 1, когда λ изменяется по всем различным корням p (t).

В результате теоремы однородное линейное рекуррентное соотношение с постоянными коэффициентами можно решить следующим образом:

1. Найдите характерный многочлен p (t).
2. Найдите корни p (t) с учетом кратности.
3. Запишите n как линейную комбинацию всех корней (с учетом краткости, как показано в теореме выше) с неизвестными коэффициентами b i.

$an\; =\; (b\; 1\; \lambda \; 1\; n\; +\; b\; 2\; n\; \lambda \; 1\; n\; +\; b\; 3\; n\; 2\; \lambda \; 1\; n\; +\; \cdots \; +\; brnr\; -\; 1\; \lambda \; 1\; n)\; +\; \cdots \; +\; (bd\; -\; q\; +\; 1\; \lambda \; \ast \; n\; +\; \cdots \; +\; bdnq\; -\; 1\; \lambda \; \ast \; n)\; \{\backslash \; displaystyle\; a\_\; \{n\}\; =\; \backslash \; left\; (b\_\; \{1\}\; \backslash \; lambda\; \_\; \{1\}\; ^\; \{n\}\; +\; b\_\; \{2\}\; n\; \backslash \; lambda\; \_\; \{1\}\; ^\; \{n\}\; +\; b\_\; \{3\}\; n\; ^\; \{2\}\; \backslash \; lambda\; \_\; \{1\}\; ^\; \{n\}\; +\; \backslash \; cdots\; +\; b\_\; \{r\}\; n\; ^\; \{r-1\}\; \backslash \; lambda\; \_\; \{1\}\; ^\; \{n\}\; \backslash \; right)\; +\; \backslash \; cdots\; +\; \backslash \; left\; (b\_\; \{dq\; +\; 1\}\; \backslash \; lambda\; \_\; \{*\}\; ^\; \{n\}\; +\; \backslash \; cdots\; +\; b\_\; \{d\}\; n\; ^\; \{q-1\}\; \backslash \; lambda\; \_\; \{*\}\; ^\; \{n\}\; \backslash \; right)\}$

Это общее решение исходного рекуррентного отношения. (q - кратность λ *)

4. Приравнять каждое $a\; 0,\; a\; 1,\dots ,\; ad\; \{\backslash \; displaystyle\; a\_\; \{0\},\; a\_\; \{1\},\; \backslash \; dots,\; a\_\; \{d\}\}$из части 3 (включение n = 0,..., d в общее решение рекуррентного отношения) с известными значениями $a\; 0,\; a\; 1,\dots ,\; ad\; \{\backslash \; displaystyle\; a\_\; \{0\},\; a\_\; \{1\},\; \backslash \; dots,\; a\_\; \{d\}\}$из исходного рекуррентного отношения. Однако значения a n из исходного используемого рекуррентного отношения обычно не обязательно должны быть смежные: за исключением исключительных случаев, необходимо всего d из них (т. е. для исходного однородного линейного рекуррентного отношения порядка 3 можно использовать значения a 0, a 1, a 4). В результате этого процесса будет получена линейная система уравнений d с d неизвестными. Решение этих уравнений относительно неизвестных коэффициентов $b\; 1,\; b\; 2,\dots ,\; bd\; \{\backslash \; displaystyle\; b\_\; \{1\},\; b\_\; \{2\},\; \backslash \; dots,\; b\_\; \{d\}\}$общего решения и включение этих значений обратно в общее решение приведет к частному ре шению исходного r отношение повторяемости, которое соответствует начальным условиям исходного отношения повторяемости (а также всем последующим значениям $a\; 0,\; a\; 1,\; a\; 2,\dots \; \{\backslash \; displaystyle\; a\_\; \{0\},\; a\_\; \{1\},\; a\_\; \{2\},\; \backslash \; dots\; \}$исходного рекуррентного соотношения).

Метод решения линейных дифференциальных уравнений аналогичен описанному выше методу - «интеллектуальное предположение» (анзац ) для линейных дифференциальных уравнений с постоянными коэффициентами является e, где λ - комплексное число, которое определяется путем подстановки предположения в дифференциальное уравнение.

Это не совпадение. Учитывая ряд Тейлора решения линейного дифференциального уравнения:

$\sum \; n\; =\; 0\; \infty \; f\; (n)\; (a)\; n!\; (Икс\; -\; а)\; п\; \{\backslash \; Displaystyle\; \backslash \; сумма\; \_\; \{п\; =\; 0\}\; ^\; \{\backslash \; infty\}\; \{\backslash \; гидроразрыва\; \{е\; ^\; \{(п)\}\; (а)\}\; \{п!\}\}\; (ха)\; ^\; \{п\}\}$

видно, что коэффициенты ряда задаются производной n функции f (x), вычисленной в точке a. Дифференциальное уравнение представляет собой линейное разностное уравнение, связывающее эти коэффициенты.

Эту эквивалентность можно использовать для быстрого решения рекуррентной зависимости для коэффициентов в решении линейного дифференциального уравнения степенного ряда.

Практическое правило (для уравнений, в которых многочлен, умножающий первый член, не равен нулю на ноль):

$y\; [k]\; \to \; f\; [n\; +\; k]\; \{\backslash \; displaystyle\; y\; ^\; \{[k]\}\; \backslash \; к\; f\; [n\; +\; k]\}$

и в более общем смысле

$xm\; \ast \; y\; [k]\; \to \; n\; (n\; -\; 1)...\; (N\; -\; м\; +\; 1)\; е\; [N\; +\; К\; -\; м]\; \{\backslash \; Displaystyle\; x\; ^\; \{m\}\; *\; y\; ^\; \{[k]\}\; \backslash \; к\; п\; (п-1)...\; (п-м\; +\; 1)\; е\; [n\; +\; km]\}$

Пример: Рекуррентное соотношение для коэффициентов ряда Тейлора уравнения:

$(x\; 2\; +\; 3\; x\; -\; 4)\; y\; [3]\; -\; (3\; x\; +\; 1)\; y\; [2]\; +\; 2\; y\; =\; 0\; \{\backslash \; displaystyle\; (x\; ^\; \{2\}\; +\; 3x-4)\; y\; ^\; \{[3]\}\; -\; (3x\; +\; 1)\; y\; ^\; \{[2]\}\; +\; 2y\; =\; 0\}$

задается как

$n\; (n\; -\; 1)\; f\; [n\; +\; 1]\; +\; 3\; nf\; [n\; +\; 2]\; -\; 4\; f\; [n\; +\; 3]\; -\; 3\; nf\; [n\; +\; 1]\; -\; f\; [n\; +\; 2]\; +\; 2\; е\; [N]\; знак\; равно\; 0\; \{\backslash \; Displaystyle\; п\; (п-1)\; е\; [п\; +\; 1]\; +\; 3nf\; [n\; +\; 2]\; -4f\; [n\; +\; 3]\; -3nf\; [n\; +\; 1]\; -f\; [n\; +\; 2]\; +\; 2f\; [n]\; =\; 0\}$

или

$-\; 4\; f\; [n\; +\; 3]\; +\; 2\; nf\; [n\; +\; 2]\; +\; n\; (n\; -\; 4)\; f\; [n\; +\; 1]\; +\; 2\; f\; [n]\; =\; 0.\; \{\backslash \; displaystyle\; -4f\; [n\; +\; 3]\; +\; 2nf\; [n\; +\; 2]\; +\; n\; (n-4)\; f\; [n\; +\; 1]\; +\; 2f\; [n]\; =\; 0.\}$

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

Пример: Дифференциальное уравнение

$a\; y\; ″\; +\; b\; y\; \prime \; +\; c\; y\; =\; 0\; \{\backslash \; displaystyle\; ay\; \text{'}\text{'}\; +\; by\; \text{'}+\; cy\; =\; 0\}$

имеет решение

$y\; =\; e\; a\; x.\; \{\backslash \; displaystyle\; y\; =\; e\; ^\; \{ax\}.\}$

Преобразование дифференциального уравнения в разностное уравнение для коэффициентов Тейлора:

$af\; [n\; +\; 2]\; +\; bf\; [n\; +\; 1]\; +\; cf\; [n\; ]\; =\; 0.\; \{\backslash \; displaystyle\; af\; [n\; +\; 2]\; +\; bf\; [n\; +\; 1]\; +\; cf\; [n]\; =\; 0.\}$

Легко видеть, что n-я производная от e, вычисленная в 0, равна

Решение с помощью линейной алгебры

Линейно рекурсивная последовательность y порядка n

$yn\; +\; k\; -\; cn\; -\; 1\; yn\; -\; 1\; +\; k\; -\; cn\; -\; 2\; yn\; -\; 2\; +\; k\; +\; \cdots \; -\; c\; 0\; yk\; =\; 0\; \{\backslash \; displaystyle\; y\_\; \{n\; +\; k\}\; -c\_\; \{n-1\}\; y\_\; \{n-1\; +\; k\}\; -c\_\; \{n-2\}\; y\_\; \{n-2\; +\; k\}\; +\; \backslash \; cdots\; -c\_\; \{0\; \}\; y\_\; \{k\}\; =\; 0\}$

идентично

$yn\; =\; cn\; -\; 1\; yn\; -\; 1\; +\; cn\; -\; 2\; yn\; -\; 2\; +\; \cdots \; +\; c\; 0\; y\; 0.\; \{\backslash \; displaystyle\; y\_\; \{n\}\; =\; c\_\; \{n-1\}\; y\_\; \{n-1\}\; +\; c\_\; \{n-2\}\; y\_\; \{n-2\}\; +\; \backslash \; cdots\; +\; c\_\; \{0\}\; y\_\; \{0\}.\}$

Расширено n-1 идентичностями вида $yn\; -\; k\; =\; yn\; -\; k,\; \{\backslash \; displaystyle\; y\_\; \{nk\}\; =\; y\_\; \{nk\},\}$это уравнение n-го порядка преобразуется в матричное разностное уравнение система n линейных уравнений первого порядка,

$y\; \to \; n\; =\; [ynyn\; -\; 1\; ⋮\; ⋮\; y\; 1]\; =\; [cn\; -\; 1\; cn\; -\; 2\; \cdots \; \cdots \; c\; 0\; 1\; 0\; \cdots \; \cdots \; 0\; 0\; \ddots \; \ddots \; ⋮\; ⋮\; \ddots \; \ddots \; ⋮\; 0\; \cdots \; 0\; 1\; 0]\; [yn\; -\; 1\; yn\; -\; 2\; ⋮\; ⋮\; y\; 0]\; =\; C\; y\; \to \; n\; -\; 1\; =\; C\; ny\; \to \; 0.\; \{\backslash \; displaystyle\; \{\backslash \; vec\; \{y\}\}\; \_\; \{n\}\; =\; \{\backslash \; begin\; \{bmatrix\}\; y\_\; \{n\}\; \backslash \backslash \; y\_\; \{n-1\}\; \backslash \backslash \backslash \; vdots\; \backslash \backslash \backslash \; vdots\; \backslash \backslash \; y\_\; \{1\}\; \backslash \; end\; \{\; bmatrix\}\}\; =\; \{\backslash \; begin\; \{bmatrix\}\; c\_\; \{n-1\}\; c\_\; \{n-2\}\; \backslash \; cdots\; \backslash \; cdots\; c\_\; \{0\}\; \backslash \backslash \; 1\; 0\; \backslash \; cdots\; \backslash \; cdots\; 0\; \backslash \backslash \; 0\; \backslash \; ddots\; \backslash \; ddots\; \backslash \; vdots\; \backslash \backslash \backslash \; vdots\; \backslash \; ddots\; \backslash \; ddots\; \backslash \; ddots\; \backslash \; vdots\; \backslash \backslash \; 0\; \backslash \; cdots\; 0\; 1\; 0\; \backslash \; end\; \{bmatrix\}\}\; \{\backslash \; begin\; \{bmatrix\}\; y\_\; \{n-1\}\; \backslash \backslash \; y\_\; \{n-2\}\; \backslash \backslash \backslash \; vdots\; \backslash \backslash \backslash \; vdots\; \backslash \backslash \; y\_\; \{0\}\; \backslash \; end\; \{bmatrix\}\}\; =\; C\; \backslash \; \{\backslash \; vec\; \{y\}\}\; \_\; \{n-1\}\; =\; C\; ^\; \{n\}\; \{\backslash \; vec\; \{y\}\}\; \_\; \{0\}.\}$

Обратите внимание, что вектор $y\; \to \; n\; \{\backslash \; displaystyle\; \{\backslash \; vec\; \{y\}\}\; \_\; \{n\}\}$может быть вычислен n приложениями сопутствующая матрица, C, к вектору начального состояния, $y\; 0\; \{\backslash \; displaystyle\; y\_\; \{0\}\}$. Таким образом, n-я запись искомой последовательности y является верхним компонентом $y\; \to \; n,\; yn\; =\; y\; \to \; n\; [n]\; \{\backslash \; displaystyle\; \{\backslash \; vec\; \{y\}\}\; \_\; \{n\},\; y\_\; \{n\; \}\; =\; \{\backslash \; vec\; \{y\}\}\; \_\; \{n\}\; [n]\}$.

Собственное разложение, $y\; \to \; n\; =\; C\; ny\; \to \; 0\; =\; a\; 1\; \lambda \; 1\; ne\; \to \; 1\; +\; a\; 2\; \lambda \; 2\; ne\; \to \; 2\; +\; \cdots \; +\; \lambda \; nne\; \to \; n\; \{\backslash \; displaystyle\; \{\backslash \; vec\; \{y\}\}\; \_\; \{n\}\; =\; C\; ^\; \{n\}\; \backslash ,\; \{\backslash \; vec\; \{y\}\}\; \_\; \{0\}\; =\; a\_\; \{1\}\; \backslash ,\; \backslash \; lambda\; \_\; \{1\}\; ^\; \{n\}\; \backslash ,\; \{\backslash \; vec\; \{e\}\}\; \_\; \{1\}\; +\; a\_\; \{2\}\; \backslash ,\; \backslash \; lambda\; \_\; \{2\}\; ^\; \{n\}\; \backslash ,\; \{\backslash \; vec\; \{e\}\}\; \_\; \{2\}\; +\; \backslash \; cdots\; +\; a\_\; \{n\}\; \backslash ,\; \backslash \; lambda\; \_\; \{n\}\; ^\; \{n\}\; \backslash ,\; \{\backslash \; vec\; \{e\}\}\; \_\; \{n\}\}$в собственные значения, $\lambda \; 1,\; \lambda \; 2,\dots ,\; \lambda \; n\; \{\backslash \; displaystyle\; \backslash \; lambda\; \_\; \{1\},\; \backslash \; lambda\; \_\; \{2\},\; \backslash \; ldots,\; \backslash \; lambda\; \_\; \{n\}\}$и собственные векторы, $e\; \to \; 1,\; e\; \to \; 2,\dots ,\; e\; \to \; n\; \{\backslash \; displaystyle\; \{\backslash \; vec\; \{e\}\}\; \_\; \{1\},\; \{\backslash \; vec\; \{e\}\}\; \_\; \{2\},\; \backslash \; ldots,\; \{\backslash \; vec\; \{e\}\}\; \_\; \{n\}\}$, используется для вычисления $y\; \to \; n.\; \{\backslash \; displaystyle\; \{\backslash \; vec\; \{y\}\}\; \_\; \{n\}.\}$Благодаря тому важному факту, что система C сдвигает во времени каждый собственный вектор, e, просто масштабируя его компоненты в λ раз,

$C\; е\; \to \; я\; знак\; равно\; \lambda \; ie\; \to \; я\; знак\; равно\; C\; [ei,\; nei,\; n\; -\; 1\; ⋮\; ei,\; 1]\; =\; [\lambda \; iei,\; n\; \lambda \; iei,\; n\; -\; 1\; ⋮\; \lambda \; iei,\; 1]\; \{\backslash \; displaystyle\; C\; \backslash ,\; \{\backslash \; vec\; \{e\}\}\; \_\; \{i\}\; =\; \backslash \; lambda\; \_\; \{i\}\; \{\backslash \; vec\; \{e\}\}\; \_\; \{i\}\; =\; C\; \{\backslash \; begin\; \{bmatrix\}\; e\_\; \{i,\; n\}\; \backslash \backslash \; e\_\; \{i,\; n-1\}\; \backslash \backslash \backslash \; vdots\; \backslash \backslash \; e\_\; \{i,\; 1\}\; \backslash \; end\; \{bmatrix\}\}\; =\; \{\backslash \; begin\; \{bmatrix\}\; \backslash \; lambda\; \_\; \{i\}\; \backslash ,\; e\_\; \{i,\; n\}\; \backslash \backslash \backslash \; lambda\; \_\; \{i\}\; \backslash ,\; e\_\; \{i,\; n-1\}\; \backslash \backslash \backslash \; vdots\; \backslash \backslash \backslash \; lambda\; \_\; \{i\}\; \backslash ,\; e\_\; \{i,\; 1\}\; \backslash \; end\; \{bmatrix\}\}\}$

то есть версия собственного вектора со сдвигом во времени, e, имеет компоненты в λ раз больше, компоненты собственных векторов являются степенями λ, $e\; \to \; i\; =\; [\lambda \; in\; -\; 1\; \cdots \; \lambda \; i\; 2\; \lambda \; i\; 1]\; T,\; \{\backslash \; displaystyle\; \{\backslash \; vec\; \{e\}\}\; \_\; \{i\}\; =\; \{\backslash \; begin\; \{bmatrix\}\; \backslash \; lambda\; \_\; \{i\}\; ^\; \{n-1\}\; \backslash \; cdots\; \backslash \; lambda\; \_\; \{i\}\; ^\; \{2\}\; \backslash \; lambda\; \_\; \{i\}\; 1\; \backslash \; end\; \{bmatrix\}\}\; ^\; \{T\},\}$и, таким образом, решение рекуррентного однор одного линейного уравнения представляет собой комбинацию экспоненциальных функций, $y\; \to \; n\; =\; \sum \; 1\; nci\; \lambda \; ine\; \to \; i\; \{\backslash \; displaystyle\; \{\backslash \; vec\; \{y\}\}\; \_\; \{\; n\}\; =\; \backslash \; sum\; \_\; \{1\}\; ^\; \{n\}\; \{c\_\; \{i\; \}\; \backslash ,\; \backslash \; lambda\; \_\; \{i\}\; ^\; \{n\}\; \backslash ,\; \{\backslash \; vec\; \{e\}\}\; \_\; \{i\}\}\}$. Компоненты $ci\; \{\backslash \; displaystyle\; c\_\; \{i\}\}$могут быть определены из начальных условий:

$y\; \to \; 0\; =\; [y\; 0\; y\; -\; 1\; ⋮\; y\; -\; n\; +\; 1]\; =\; \sum \; я\; знак\; равно\; 1\; nci\; \lambda \; я\; 0\; е\; \to \; я\; =\; [е\; \to \; 1\; е\; \to \; 2\; \cdots \; е\; \to \; n]\; [c\; 1\; c\; 2\; \cdots \; cn]\; =\; E\; [c\; 1\; c\; 2\; \cdots \; cn]\; \{\backslash \; displaystyle\; \{\backslash \; vec\; \{y\}\; \}\; \_\; \{0\}\; =\; \{\backslash \; begin\; \{bmatrix\}\; y\_\; \{0\}\; \backslash \backslash \; y\; \_\; \{-\; 1\}\; \backslash \backslash \backslash \; vdots\; \backslash \backslash \; y\; \_\; \{-\; n\; +\; 1\}\; \backslash \; end\; \{bmatrix\}\}\; =\; \backslash \; sum\; \_\; \{i\; =\; 1\; \}\; ^\; \{n\}\; \{c\_\; \{i\}\; \backslash ,\; \backslash \; lambda\; \_\; \{i\}\; ^\; \{0\}\; \backslash ,\; \{\backslash \; vec\; \{e\}\}\; \_\; \{i\}\}\; =\; \{\backslash \; begin\; \{bmatrix\}\; \{\backslash \; vec\; \{e\}\}\; \_\; \{1\}\; \{\backslash \; vec\; \{e\}\}\; \_\; \{2\}\; \backslash \; cdots\; \{\backslash \; vec\; \{e\}\}\; \_\; \{n\}\; \backslash \; end\; \{bmatrix\}\}\; \backslash ,\; \{\backslash \; begin\; \{bmatrix\}\; c\_\; \{1\}\; \backslash \; \backslash \; c\_\; \{2\}\; \backslash \backslash \backslash \; cdots\; \backslash \backslash \; c\_\; \{n\}\; \backslash \; end\; \{bmatrix\}\}\; =\; E\; \backslash ,\; \{\backslash \; begin\; \{bmatrix\}\; c\_\; \{1\}\; \backslash \backslash \; c\_\; \{2\}\; \backslash \backslash \backslash \; cdots\; \backslash \backslash \; c\_\; \{n\; \}\; \backslash \; end\; \{bmatrix\}\}\}$

Решение для коэффициентов,

$[c\; 1\; c\; 2\; \cdots \; cn]\; =\; E\; -\; 1\; y\; \to \; 0\; =\; [\lambda \; 1\; n\; -\; 1\; \lambda \; 2\; n\; -\; 1\; \cdots \; \lambda \; nn\; -\; 1\; ⋮\; \ddots \; \lambda \; 1\; \lambda \; 2\; \cdots \; \lambda \; n\; 1\; 1\; \cdots \; 1]\; -\; 1\; [y\; 0\; y\; -\; 1\; ⋮\; y\; -\; n\; +\; 1].\; \{\backslash \; Displaystyle\; \{\backslash \; begin\; \{bmatrix\}\; c\_\; \{1\}\; \backslash \backslash \; c\_\; \{2\}\; \backslash \backslash \backslash \; cdots\; \backslash \backslash \; c\_\; \{n\}\; \backslash \; end\; \{bmatrix\}\}\; =\; E\; ^\; \{-\; 1\}\; \{\backslash \; vec\; \{y\}\}\; \_\; \{0\}\; =\; \{\backslash \; begin\; \{bmatrix\}\; \backslash \; lambda\; \_\; \{1\}\; ^\; \{n-1\}\; \backslash \; lambda\; \_\; \{2\}\; ^\; \{n-1\}\; \backslash \; cdots\; \backslash \; lambda\; \_\; \{n\}\; ^\; \{n-1\; \}\; \backslash \backslash \backslash \; vdots\; \backslash \; vdots\; \backslash \; ddots\; \backslash \; vdots\; \backslash \backslash \backslash \; lambda\; \_\; \{1\}\; \backslash \; lambda\; \_\; \{2\}\; \backslash \; cdots\; \backslash \; lambda\; \_\; \{n\}\; \backslash \backslash \; 1\; 1\; \backslash \; cdots\; 1\; \backslash \; end\; \{bmatrix\}\; \}\; ^\; \{-\; 1\}\; \backslash ,\; \{\backslash \; begin\; \{bmatrix\}\; y\_\; \{0\}\; \backslash \backslash \; y\; \_\; \{-\; 1\}\; \backslash \backslash \backslash \; vdots\; \backslash \backslash \; y\; \_\; \{-\; n\; +\; 1\}\; \backslash \; end\; \{bmatrix\}\}.\}$

Это также работает с произвольными граничными условиями $ya,\; yb,\dots \; ⏟\; n\; \{\backslash \; displaystyle\; \backslash \; underbrace\; \{y\_\; \{a\},\; y\_\; \{b\},\; \backslash \; ldots\}\; \_\; \{\backslash \; text\; \{n\}\}\}$, не обязательно начальные,

$[yayb\; ⋮]\; =\; [y\; \to \; a\; [n]\; y\; \to \; b\; [n]\; ⋮]\; =\; [\sum \; i\; =\; 1\; nci\; \lambda \; iae\; \to \; i\; [n]\; \sum \; i\; =\; 1\; nci\; \lambda \; ibe\; \to \; я\; [n]\; ⋮]\; =\; [\sum \; я\; =\; 1\; nci\; \lambda \; ia\; \lambda \; in\; -\; 1\; \sum \; i\; =\; 1\; nci\; \lambda \; ib\; \lambda \; in\; -\; 1\; ⋮]\; =\; \{\backslash \; displaystyle\; \{\backslash \; begin\; \{bmatrix\}\; y\_\; \{a\}\; \backslash \backslash \; y\_\; \{b\}\; \backslash \backslash \backslash \; vdots\; \backslash \; end\; \{bmatrix\}\}\; =\; \{\backslash \; begin\; \{bmatrix\}\; \{\backslash \; vec\; \{y\}\}\; \_\; \{a\}\; [n]\; \backslash \backslash \; \{\backslash \; vec\; \{y\}\}\; \_\; \{b\}\; [n\; ]\; \backslash \backslash \backslash \; vdots\; \backslash \; end\; \{bmatrix\}\}\; =\; \{\backslash \; begin\; \{bmatr\; ix\}\; \backslash \; sum\; \_\; \{i\; =\; 1\}\; ^\; \{n\}\; \{c\_\; \{i\}\; \backslash ,\; \backslash \; lambda\; \_\; \{i\}\; ^\; \{a\}\; \backslash ,\; \{\; \backslash \; vec\; \{e\}\}\; \_\; \{i\}\; [n]\}\; \backslash \backslash \backslash \; sum\; \_\; \{i\; =\; 1\}\; ^\; \{n\}\; \{c\_\; \{i\}\; \backslash ,\; \backslash \; lambda\; \_\; \{i\}\; ^\; \{b\}\; \backslash ,\; \{\backslash \; ve\; c\; \{e\}\}\; \_\; \{i\}\; [n]\}\; \backslash \backslash \backslash \; vdots\; \backslash \; end\; \{bmatrix\}\}\; =\; \{\backslash \; begin\; \{bmatrix\}\; \backslash \; sum\; \_\; \{i\; =\; 1\}\; ^\; \{n\}\; \{c\_\; \{i\}\; \backslash ,\; \backslash \; лямбда\; \_\; \{i\}\; ^\; \{a\}\; \backslash ,\; \backslash \; lambda\; \_\; \{i\}\; ^\; \{n-1\}\}\; \backslash \backslash \backslash \; сумма\; \_\; \{i\; =\; 1\}\; ^\; \{n\}\; \{c\_\; \{i\}\; \backslash ,\; \backslash \; lambda\; \_\; \{i\; \}\; ^\; \{b\}\; \backslash ,\; \backslash \; lambda\; \_\; \{i\}\; ^\; \{n-1\}\}\; \backslash \backslash \backslash \; vdots\; \backslash \; end\; \{bmatrix\}\}\; =\}$

$=\; [\sum \; ci\; \lambda \; ia\; +\; n\; -\; 1\; \sum \; ci\; \lambda \; ib\; +\; n\; -\; 1\; ⋮]\; =\; [\lambda \; 1\; a\; +\; n\; -\; 1\; \lambda \; 2\; a\; +\; n\; -\; 1\; \cdots \; \lambda \; na\; +\; n\; -\; 1\; \lambda \; 1\; b\; +\; n\; -\; 1\; \lambda \; 2\; b\; +\; n\; -\; 1\; \cdots \; \lambda \; nb\; +\; n\; -\; 1\; ⋮\; ⋮\; \ddots \; ⋮]\; [c\; 1\; c\; 2\; ⋮\; cn].\; \{\backslash \; displaystyle\; =\; \{\backslash \; begin\; \{bmatrix\}\; \backslash \; sum\; \{c\_\; \{i\}\; \backslash ,\; \backslash \; lambda\; \_\; \{i\}\; ^\; \{a\; +\; n-1\}\}\; \backslash \backslash \backslash \; sum\; \{c\_\; \{i\}\; \backslash ,\; \backslash \; lambda\; \_\; \{i\; \}\; ^\; \{b\; +\; n-1\}\}\; \backslash \backslash \backslash \; vdots\; \backslash \; end\; \{bmatrix\}\}\; =\; \{\backslash \; begin\; \{bmatrix\}\; \backslash \; lambda\; \_\; \{1\}\; ^\; \{a\; +\; n-1\}\; \backslash \; lambda\; \_\; \{2\}\; ^\; \{\; a\; +\; n-1\}\; \backslash \; cdots\; \backslash \; lambda\; \_\; \{n\}\; ^\; \{a\; +\; n-1\}\; \backslash \backslash \backslash \; lambda\; \_\; \{1\}\; ^\; \{b\; +\; n-1\}\; \backslash \; lambda\; \_\; \{2\}\; ^\; \{b\; +\; n-1\}\; \backslash \; cdots\; \backslash \; lambda\; \_\; \{n\}\; ^\; \{b\; +\; n-1\}\; \backslash \backslash \backslash \; vdots\; \backslash \; vdots\; \backslash \; ddots\; \backslash \; vdots\; \backslash \; end\; \{bmatrix\}\}\; \backslash ,\; \{\backslash \; begin\; \{bmatrix\}\; c\_\; \{1\}\; \backslash \backslash \; c\_\; \{2\}\; \backslash \backslash \backslash \; vdots\; \backslash \backslash \; c\_\; \{n\}\; \backslash \; end\; \{bmatrix\}\}.\}$

Это описание действительно не отличается от общего метода, приведенного выше, однако оно более краткое. Он также хорошо работает в таких ситуациях, как

$\{a\; n\; =\; a\; n\; -\; 1\; -\; b\; n\; -\; 1\; b\; n\; =\; 2\; a\; n\; -\; 1\; +\; b\; n\; -\; 1.\; \{\backslash \; displaystyle\; \{\backslash \; begin\; \{cases\}\; a\_\; \{n\}\; =\; a\_\; \{n-1\}\; -b\_\; \{n-1\}\; \backslash \backslash \; b\_\; \{n\}\; =\; 2a\_\; \{n-1\}\; +\; b\_\; \{n-1\}.\; \backslash \; end\; \{case\}\}\}$

, где есть несколько связанных повторений.

Решение с помощью z-преобразований

Некоторые разностные уравнения, в частности, линейный постоянный коэффициент разностные уравнения - можно решить с помощью z-преобразований. Z-преобразования - это класс интегральных преобразований, которые приводят к более удобным алгебраическим манипуляциям и более прямым решениям. Бывают случаи, когда получение прямого решения практически невозможно, но решить проблему с помощью тщательно подобранного интегрального преобразования несложно.

Решение неоднородных линейных рекуррентных соотношений с постоянными коэффициентами

Если рекуррентность неоднородна, частное решение может быть найдено с помощью метода неопределенных коэффициентов и Решение - это сумма решения однородного и частного решений. Другой метод решения неоднородной рекуррентности - это метод символического дифференцирования. Например, рассмотрим следующее повторение:

$a\; n\; +\; 1\; =\; a\; n\; +\; 1\; \{\backslash \; displaystyle\; a\_\; \{n\; +\; 1\}\; =\; a\_\; \{n\}\; +1\}$

Это неоднородное повторение. Если мы подставим n ↦ n + 1, мы получим повторение

$an\; +\; 2\; =\; an\; +\; 1\; +\; 1\; \{\backslash \; displaystyle\; a\_\; \{n\; +\; 2\}\; =\; a\_\; \{n\; +\; 1\}\; +1\}$

Вычитание исходного повторение из этого уравнения дает

$an\; +\; 2\; -\; an\; +\; 1\; =\; an\; +\; 1\; -\; an\; \{\backslash \; displaystyle\; a\_\; \{n\; +\; 2\}\; -a\_\; \{n\; +\; 1\}\; =\; a\_\; \{n\; +\; 1\}\; -a\_\; \{n\}\}$

или эквивалентно

$an\; +\; 2\; =\; 2\; an\; +\; 1\; -\; an\; \{\backslash \; displaystyle\; a\_\; \{n\; +\; 2\}\; =\; 2a\_\; \{n\; +\; 1\}\; -a\_\; \{n\}\}$

Это однородное повторение, которое может быть решена описанными выше методами. In general, if a linear recurrence has the form

$a\; n\; +\; k\; =\; \lambda \; k\; -\; 1\; a\; n\; +\; k\; -\; 1\; +\; \lambda \; k\; -\; 2\; a\; n\; +\; k\; -\; 2\; +\; \cdots \; +\; \lambda \; 1\; a\; n\; +\; 1\; +\; \lambda \; 0\; a\; n\; +\; p\; (\; n)\; \{\backslash displaystyle\; a\_\{n+k\}=\backslash lambda\; \_\{k-1\}a\_\{n+k-1\}+\backslash lambda\; \_\{k-2\}a\_\{n+k-2\}+\backslash cdots\; +\backslash lambda\; \_\{1\}a\_\{n+1\}+\backslash lambda\; \_\{0\}a\_\{n\}+p(n)\}$

where $\lambda \; 0,\; \lambda \; 1,\; \dots ,\; \lambda \; k\; -\; 1\; \{\backslash displaystyle\; \backslash lambda\; \_\{0\},\backslash lambda\; \_\{1\},\backslash dots,\backslash lambda\; \_\{k-1\}\}$are constant coefficients and p(n) is the inhomogeneity, then if p(n) is a polynomial with degree r, then this non-homogeneous recurrence can be reduced to a homogeneous recurrence by applying the method of symbolic differencing r times.

If

$P\; (\; x)\; =\; \sum \; n\; =\; 0\; \infty \; p\; n\; x\; n\; \{\backslash displaystyle\; P(x)=\backslash sum\; \_\{n=0\}^\{\backslash infty\; \}p\_\{n\}x^\{n\}\}$

is the generating function of the inhomogeneity, the generating function

$A\; (\; x)\; =\; \sum \; n\; =\; 0\; \infty \; a\; (\; n)\; x\; n\; \{\backslash displaystyle\; A(x)=\backslash sum\; \_\{n=0\}^\{\backslash infty\; \}a(n)x^\{n\}\}$

of the non-homogeneous recurrence

$a\; n\; =\; \sum \; i\; =\; 1\; s\; c\; i\; a\; n\; -\; i\; +\; p\; n,\; n\; \ge \; n\; r,\; \{\backslash displaystyle\; a\_\{n\}=\backslash sum\; \_\{i=1\}^\{s\}c\_\{i\}a\_\{n-i\}+p\_\{n\},\backslash quad\; n\backslash geq\; n\_\{r\},\}$

with constant coefficients ciis derived from

$(\; 1\; -\; \sum \; i\; =\; 1\; s\; c\; i\; x\; i)\; A\; (\; x)\; =\; P\; (\; x)\; +\; \sum \; n\; =\; 0\; n\; r\; -\; 1\; [\; a\; n\; -\; p\; n\; ]\; x\; n\; -\; \sum \; i\; =\; 1\; s\; c\; i\; x\; i\; \sum \; n\; =\; 0\; n\; r\; -\; i\; -\; 1\; a\; n\; x\; n.\; \{\backslash displaystyle\; \backslash left(1-\backslash sum\; \_\{i=1\}^\{s\}c\_\{i\}x^\{i\}\backslash right)A(x)=P(x)+\backslash sum\; \_\{n=0\}^\{n\_\{r\}-1\}[a\_\{n\}-p\_\{n\}]x^\{n\}-\backslash sum\; \_\{i=1\}^\{s\}c\_\{i\}x^\{i\}\backslash sum\; \_\{n=0\}^\{n\_\{r\}-i-1\}a\_\{n\}x^\{n\}.\}$

If P(x) is a rational generating function, A(x) is also one. The case discussed above, where pn= K is a constant, emerges as one example of this formula, with P(x) = K/(1−x). Another example, the recurrence $a\; n\; =\; 10\; a\; n\; -\; 1\; +\; n\; \{\backslash displaystyle\; a\_\{n\}=10a\_\{n-1\}+n\}$with linear inhomogeneity, arises in the definition of the schizophrenic numbers. The solution of homogeneous recurrences is incorporated as p = P = 0.

Solving first-order non-homogeneous recurrence relations with variable coefficients

Moreover, for the general first-order non-hom Ogeneous линейное рекуррентное отношение с переменными коэффициентами:

$an\; +\; 1\; =\; fnan\; +\; gn,\; fn\; \ne \; 0,\; \{\backslash \; displaystyle\; a\_\; \{n\; +\; 1\}\; =\; f\_\; \{n\}\; a\_\; \{n\}\; +\; g\_\; \{n\},\; \backslash \; qquad\; f\_\; \{n\}\; \backslash \; neq\; 0,\}$

есть еще хороший способ решить эту проблему:

$an\; +\; 1\; -\; fnan\; =\; gn\; \{\backslash \; displaystyle\; a\_\; \{n\; +\; 1\}\; -f\_\; \{n\}\; a\_\; \{n\}\; =\; g\_\; \{n\}\}$

$an\; +\; 1\; \prod \; k\; =\; 0\; nfk\; -\; fnan\; \prod \; k\; =\; 0\; nfk\; =\; gn\; \prod \; k\; =\; 0\; nfk\; \{\backslash \; displaystyle\; \{\backslash \; frac\; \{a\_\; \{n\; +\; 1\}\}\; \{\backslash \; prod\; \_\; \{k\; =\; 0\}\; ^\; \{n\}\; f\_\; \{k\}\}\}\; -\; \{\backslash \; frac\; \{f\_\; \{n\}\; a\_\; \{n\}\}\; \{\backslash \; prod\; \_\; \{k\; =\; 0\}\; ^\; \{n\}\; f\_\; \{k\}\}\}\; =\; \{\backslash \; frac\; \{g\_\; \{n\}\}\; \{\backslash \; prod\; \_\; \{k\; =\; 0\}\; ^\; \{n\}\; f\_\; \{k\}\}\}\}$

$an\; +\; 1\; \prod \; k\; =\; 0\; nfk\; -\; an\; k\; =\; 0\; n\; -\; 1\; fk\; =\; gn\; \prod \; к\; =\; 0\; nfk\; \{\backslash \; displaystyle\; \{\backslash \; frac\; \{a\_\; \{n\; +\; 1\}\}\; \{\backslash \; prod\; \_\; \{k\; =\; 0\}\; ^\; \{n\}\; f\_\; \{k\}\}\}\; -\; \{\backslash \; frac\; \{a\_\; \{n\}\}\; \{\backslash \; prod\; \_\; \{k\; =\; 0\}\; ^\; \{n-1\}\; f\_\; \{k\}\}\}\; =\; \{\backslash \; frac\; \{g\_\; \{n\}\}\; \{\backslash \; prod\; \_\; \{k\; =\; 0\}\; ^\; \{n\}\; f\_\; \{k\}\}\}\}$

Пусть

$A\; n\; =\; an\; \prod \; k\; =\; 0\; n\; -\; 1\; fk,\; \{\backslash \; displaystyle\; A\_\; \{n\}\; =\; \{\backslash \; frac\; \{a\_\; \{n\}\}\; \{\backslash \; prod\; \_\; \{k\; =\; 0\}\; ^\; \{n-1\}\; f\_\; \{k\}\}\},\}$

Тогда

$A\; n\; +\; 1\; -\; A\; n\; =\; gn\; \prod \; k\; =\; 0\; nfk\; \{\backslash \; displaystyle\; A\_\; \{n\; +\; 1\}\; -A\_\; \{n\}\; =\; \{\backslash \; frac\; \{g\_\; \{\; n\}\}\; \{\backslash \; prod\; \_\; \{k\; =\; 0\}\; ^\; \{n\}\; f\_\; \{k\}\}\}\}$

$\sum \; m\; =\; 0\; n\; -\; 1\; (A\; m\; +\; 1\; -\; A\; m)\; =\; A\; n\; -\; A\; 0\; =\; \sum \; m\; =\; 0\; n\; -\; 1\; г\; ·\; м\; k\; Знак\; равно\; 0\; mfk\; \{\backslash \; displaystyle\; \backslash \; sum\; \_\; \{m\; =\; 0\}\; ^\; \{n-1\}\; (A\_\; \{m\; +\; 1\}\; -A\_\; \{m\})\; =\; A\_\; \{n\}\; -A\_\; \{0\}\; =\; \backslash \; sum\; \_\; \{m\; =\; 0\}\; ^\; \{n-1\}\; \{\backslash \; frac\; \{g\_\; \{m\}\}\; \{\backslash \; prod\; \_\; \{k\; =\; 0\}\; ^\; \{m\}\; f\_\; \{k\}\}\}\}$

$an\; \prod \; k\; =\; 0\; n\; -\; 1\; fk\; =\; A\; 0\; +\; \sum \; м\; знак\; равно\; 0\; N\; -\; 1\; г\; К\; знак\; равно\; 0\; mfk\; \{\backslash \; displaystyle\; \{\backslash \; frac\; \{a\_\; \{n\}\}\; \{\backslash \; prod\; \_\; \{k\; =\; 0\}\; ^\; \{n-1\}\; f\_\; \{k\}\}\}\; =\; A\_\; \{0\}\; +\; \backslash \; sum\; \_\; \{m\; =\; 0\}\; ^\; \{n-1\}\; \{\backslash \; frac\; \{g\_\; \{m\}\}\; \{\backslash \; prod\; \_\; \{k\; =\; 0\}\; ^\; \{m\}\; f\_\; \{k\}\}\}\}$

$an\; =\; (\prod \; К\; =\; 0\; N\; -\; 1\; fk)\; (A\; 0\; +\; \sum \; m\; =\; 0\; n\; -\; 1\; г\; k\; =\; 0\; mfk)\; \{\backslash \; displaystyle\; a\_\; \{n\}\; =\; \backslash \; left\; (\backslash \; prod\; \_\; \{k\; =\; 0\}\; ^\; \{n-1\}\; f\_\; \{k\}\; \backslash \; right)\; \backslash \; left\; (A\_\; \{0\}\; +\; \backslash \; sum\; \_\; \{m\; =\; 0\}\; ^\; \{n-1\}\; \{\backslash \; frac\; \{g\_\; \{m\}\}\; \{\backslash \; prod\; \_\; \{k\; =\; 0\}\; ^\; \{m\}\; f\_\; \{k\}\}\}\; \backslash \; right)\}$

Если мы применим формулу к $an\; +\; 1\; =\; (1\; +\; hfnh)\; an\; +\; hgnh\; \{\backslash \; displaystyle\; a\_\; \{n\; +\; 1\}\; =\; (1\; +\; hf\_\; \{nh\})\; a\_\; \{n\}\; +\; hg\_\; \{nh\}\}$и взяв предел h → 0, мы получаем формулу для линейных дифференциальных уравнений первого порядка с переменные коэффициенты; сумма становится интегралом, а произведение становится экспоненциальной функцией интеграла.

Решение общих однородных линейных рекуррентных соотношений

Многие однородные линейные рекуррентные соотношения могут быть решены с помощью обобщенного гипергеометрического ряда. Их частные случаи приводят к рекуррентным соотношениям для ортогональных многочленов и многих специальных функций. Например, решение

$J\; n\; +\; 1\; =\; 2\; nz\; J\; n\; -\; J\; n\; -\; 1\; \{\backslash \; displaystyle\; J\_\; \{n\; +\; 1\}\; =\; \{\backslash \; frac\; \{2n\}\; \{z\}\}\; J\_\; \{n\}\; -J\_\; \{\; n-1\}\}$

задается как

$J\; n\; =\; J\; n\; (z),\; \{\backslash \; displaystyle\; J\_\; \{n\}\; =\; J\_\; \{n\}\; (z),\}$

функция Бесселя, а

$(b\; -\; n)\; M\; n\; -\; 1\; +\; (2\; n\; -\; b\; -\; z)\; M\; n\; -\; n\; M\; n\; +\; 1\; =\; 0\; \{\backslash \; displaystyle\; (bn)\; M\_\; \{n-1\}\; +\; (2n\; -bz)\; M\_\; \{n\}\; -nM\_\; \{n\; +\; 1\}\; =\; 0\}$