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

В математике (включая комбинаторику , линейную алгебру и динамические системы ) линейная рекуррентность с постоянными коэффициентами ^{[1] : гл. 17  [2] : гл. 10} (также известная как линейное рекуррентное соотношение или линейное разностное уравнение ) приравнивает к 0 многочлен , который линеен относительно различных итераций переменной — то есть относительно значений элементов последовательности . Линейность многочлена означает, что каждый из его членов имеет степень 0 или 1. Линейная рекуррентность обозначает эволюцию некоторой переменной с течением времени, при этом текущий период времени или дискретный момент времени обозначается как t , один период ранее обозначается как t − 1 , один период позже как t + 1 и т. д.

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

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

Линейная рекуррентность с постоянными коэффициентами — это уравнение следующего вида, записанное через параметры a ₁ , ..., a _n и b :

$${\displaystyle y_{t}=a_{1}y_{t-1}+\cdots +a_{n}y_{tn}+b,}$$

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

$${\displaystyle y_{t+n}=a_{1}y_{t+n-1}+\cdots +a_{n}y_{t}+b.}$$

Положительное целое число называется порядком повторения и обозначает самый большой временной лаг между итерациями. Уравнение называется однородным, если b = 0 , и неоднородным, если b ≠ 0 .${\displaystyle n}$

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

$${\displaystyle p(\lambda )=\lambda ^{n}-a_{1}\lambda ^{n-1}-a_{2}\lambda ^{n-2}-\cdots -a_{n}}$$

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

Если b ≠ 0 , уравнение

$${\displaystyle y_{t}=a_{1}y_{t-1}+\cdots +a_{n}y_{tn}+b}$$

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

$${\displaystyle y^{*}={\frac {b}{1-a_{1}-\cdots -a_{n}}}}$$

при условии, что знаменатель не равен 0. Если он равен нулю, то стационарного состояния не существует.

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

$${\displaystyle \left(y_{t}-y^{*}\right)=a_{1}\left(y_{t-1}-y^{*}\right)+\cdots +a_{n}\left(y_{tn}-y^{*}\right)}$$

которая не имеет постоянного члена и которую можно записать более кратко как

$${\displaystyle x_{t}=a_{1}x_{t-1}+\cdots +a_{n}x_{tn}}$$

где x равен y − y * . Это однородная форма.

Если стационарного состояния нет, то разностное уравнение

$${\displaystyle y_{t}=a_{1}y_{t-1}+\cdots +a_{n}y_{tn}+b}$$

может быть объединен с эквивалентной формой

$${\displaystyle y_{t-1}=a_{1}y_{t-2}+\cdots +a_{n}y_{t-(n+1)}+b}$$

получить (решив оба для b )

$${\displaystyle y_{t}-a_{1}y_{t-1}-\cdots -a_{n}y_{tn}=y_{t-1}-a_{1}y_{t-2}-\cdots -a_{n}y_{t-(n+1)}}$$

в котором подобные члены могут быть объединены для получения однородного уравнения на один порядок выше исходного.

Корни характеристического многочлена играют решающую роль в поиске и понимании последовательностей, удовлетворяющих рекуррентности. Если есть различные корни , то каждое решение рекуррентности принимает форму , где коэффициенты определяются для того, чтобы соответствовать начальным условиям рекуррентности. Когда одни и те же корни встречаются несколько раз, члены в этой формуле, соответствующие второму и последующим появлениям одного и того же корня, умножаются на возрастающие степени . Например, если характеристический многочлен можно разложить на множители как , с одним и тем же корнем , встречающимся три раза, то решение примет форму ^[3]${\displaystyle д}$${\displaystyle r_{1},r_{2},\ldots ,r_{d},}$$${\displaystyle a_{n}=k_{1}r_{1}^{n}+k_{2}r_{2}^{n}+\cdots +k_{d}r_{d}^{n},}$$${\displaystyle k_{i}}$${\displaystyle n}$${\displaystyle (xr)^{3}}$${\displaystyle r}$$${\displaystyle a_{n}=k_{1}r^{n}+k_{2}nr^{n}+k_{3}n^{2}r^{n}.}$$

Для порядка 1 рекуррентное уравнение имеет решение с и наиболее общее решение с . Характеристический многочлен, приравненный к нулю ( характеристическое уравнение ), просто .$${\displaystyle a_{n}=ra_{n-1}}$$${\displaystyle a_{n}=r^{n}}$${\displaystyle a_{0}=1}$${\displaystyle a_{n}=kr^{n}}$${\displaystyle a_{0}=k}$${\displaystyle t-r=0}$

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

Рассмотрим, например, рекуррентное соотношение вида$${\displaystyle a_{n}=Aa_{n-1}+Ba_{n-2}.}$$

Когда оно имеет решение того же общего вида, что и ? Подставляя это предположение ( анзац ) в рекуррентное соотношение, мы обнаруживаем, что должно быть верно для всех .${\displaystyle a_{n}=r^{n}}$$${\displaystyle r^{n}=Ar^{n-1}+Br^{n-2}}$$ ${\displaystyle n>1}$

Разделив на , получаем, что все эти уравнения сводятся к одному и тому же:${\displaystyle r^{n-2}}$

$${\displaystyle {\begin{aligned}r^{2}&=Ar+B,\\r^{2}-Ar-B&=0,\end{aligned}}}$$

которое является характеристическим уравнением рекуррентного соотношения. Решите для получения двух корней , : эти корни известны как характеристические корни или собственные значения характеристического уравнения. Различные решения получаются в зависимости от природы корней: Если эти корни различны, мы имеем общее решение${\displaystyle r}$${\displaystyle \lambda _{1}}$${\displaystyle \lambda _{2}}$

$${\displaystyle a_{n}=C\lambda _{1}^{n}+D\lambda _{2}^{n}}$$

в то время как если они идентичны (когда ), мы имеем${\displaystyle A^{2}+4B=0}$

$${\displaystyle a_{n}=C\lambda ^{n}+Dn\lambda ^{n}}$$

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

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

$${\displaystyle a_{n}=C\lambda _{1}^{n}+D\lambda _{2}^{n}}$$

можно переписать как ^{[4] : ​​576–585}

$${\displaystyle a_{n}=2M^{n}\left(E\cos(\theta n)+F\sin(\theta n)\right)=2GM^{n}\cos(\theta n-\delta ),}$$

где

$${\displaystyle {\begin{array}{lcl}M={\sqrt {\alpha ^{2}+\beta ^{2}}}&\cos(\theta )={\tfrac {\alpha }{M}}&\sin(\theta )={\tfrac {\beta }{M}}\\C,D=E\mp Fi&&\\G={\sqrt {E^{2}+F^{2}}}&\cos(\delta )={\tfrac {E}{G}}&\sin(\delta )={\tfrac {F}{G}}\end{array}}}$$

Здесь и (или, что то же самое, и ) — действительные константы, зависящие от начальных условий. Используя ${\displaystyle E}$${\displaystyle F}$${\displaystyle G}$${\displaystyle \delta }$$${\displaystyle \lambda _{1}+\lambda _{2}=2\alpha =A,}$$$${\displaystyle \lambda _{1}\cdot \lambda _{2}=\alpha ^{2}+\beta ^{2}=-B,}$$

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

$${\displaystyle a_{n}=(-B)^{\frac {n}{2}}\left(E\cos(\theta n)+F\sin(\theta n)\right),}$$

где и — начальные условия и${\displaystyle a_{1}}$${\displaystyle a_{2}}$

$${\displaystyle {\begin{aligned}E&={\frac {-Aa_{1}+a_{2}}{B}}\\F&=-i{\frac {A^{2}a_{1}-Aa_{2}+2a_{1}B}{B{\sqrt {A^{2}+4B}}}}\\\theta &=\arccos \left({\frac {A}{2{\sqrt {-B}}}}\right)\end{aligned}}}$$

Таким образом, нет необходимости решать для и .${\displaystyle \lambda _{1}}$${\displaystyle \lambda _{2}}$

Во всех случаях — действительных различных собственных значений, действительных удвоенных собственных значений и комплексно сопряженных собственных значений — уравнение устойчиво (то есть переменная сходится к фиксированному значению [в частности, нулю]) тогда и только тогда, когда оба собственных значения меньше единицы по абсолютной величине . В этом случае второго порядка можно показать ^[5] , что это условие на собственные значения эквивалентно , что эквивалентно и .${\displaystyle a}$${\displaystyle |A|<1-B<2}$${\displaystyle |B|<1}$${\displaystyle |A|<1-B}$

Решение однородного уравнения

$${\displaystyle x_{t}=a_{1}x_{t-1}+\cdots +a_{n}x_{t-n}}$$

включает в себя сначала решение его характеристического многочлена

$${\displaystyle \lambda ^{n}=a_{1}\lambda ^{n-1}+\cdots +a_{n-2}\lambda ^{2}+a_{n-1}\lambda +a_{n}}$$

для его характеристических корней λ ₁ , ..., λ _n . Эти корни могут быть решены для алгебраически , если n ≤ 4 , но не обязательно в противном случае . Если решение должно быть использовано численно, все корни этого характеристического уравнения могут быть найдены численными методами . Однако для использования в теоретическом контексте может оказаться, что единственной требуемой информацией о корнях является то, больше ли или равен ли какой-либо из них 1 по абсолютной величине .

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

Если все характеристические корни различны, то решение однородного линейного рекуррентного уравнения

$${\displaystyle x_{t}=a_{1}x_{t-1}+\cdots +a_{n}x_{t-n}}$$

можно записать в терминах характеристических корней как

$${\displaystyle x_{t}=c_{1}\lambda _{1}^{t}+\cdots +c_{n}\lambda _{n}^{t}}$$

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

Если есть комплексные корни, они входят в сопряженные пары, как и комплексные члены в уравнении решения. Если два из этих комплексных членов c _j λ^т
_джи c _{j +1} λ^т
_{дж +1}, корни λ _j можно записать как

$${\displaystyle \lambda _{j},\lambda _{j+1}=\alpha \pm \beta i=M\left({\frac {\alpha }{M}}\pm {\frac {\beta }{M}}i\right)}$$

где i — мнимая единица , а M — модуль корней:

$${\displaystyle M={\sqrt {\alpha ^{2}+\beta ^{2}}}.}$$

Тогда два комплексных члена в уравнении решения можно записать как

$${\displaystyle {\begin{aligned}c_{j}\lambda _{j}^{t}+c_{j+1}\lambda _{j+1}^{t}&=M^{t}\left(c_{j}\left({\frac {\alpha }{M}}+{\frac {\beta }{M}}i\right)^{t}+c_{j+1}\left({\frac {\alpha }{M}}-{\frac {\beta }{M}}i\right)^{t}\right)\\[6pt]&=M^{t}\left(c_{j}\left(\cos \theta +i\sin \theta \right)^{t}+c_{j+1}\left(\cos \theta -i\sin \theta \right)^{t}\right)\\[6pt]&=M^{t}{\bigl (}c_{j}\left(\cos \theta t+i\sin \theta t\right)+c_{j+1}\left(\cos \theta t-i\sin \theta t\right){\bigr )}\end{aligned}}}$$

где θ — угол, косинус которого равен ⁠α/М⁠ и синус которого равен ⁠β/М⁠ ; последнее равенство здесь получено с использованием формулы Муавра .

Теперь процесс нахождения коэффициентов c _j и c _{j +1} гарантирует, что они также являются комплексно сопряженными, что можно записать как γ ± δi . Использование этого в последнем уравнении дает это выражение для двух комплексных членов в уравнении решения:

$${\displaystyle 2M^{t}\left(\gamma \cos \theta t-\delta \sin \theta t\right)}$$

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

$${\displaystyle 2{\sqrt {\gamma ^{2}+\delta ^{2}}}M^{t}\cos(\theta t+\psi )}$$

где ψ — угол, косинус которого равен ⁠γ/√ γ ² + δ ²⁠ и синус которого равен ⁠δ/√ γ ² + δ ²⁠ .

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

В случае второго порядка, если два корня идентичны ( λ ₁ = λ ₂ ), их оба можно обозначить как λ , и решение может иметь вид

$${\displaystyle x_{t}=c_{1}\lambda ^{t}+c_{2}t\lambda ^{t}.}$$

Альтернативный метод решения включает преобразование уравнения разности n- го порядка в матричное уравнение разности первого порядка . Это достигается путем записи w _{1, t} = y _t , w _{2, t} = y _{t −1} = w _{1, t −1} , w _{3, t} = y _{t −2} = w _{2, t −1} и т. д. Тогда исходное уравнение n- го порядка

$${\displaystyle y_{t}=a_{1}y_{t-1}+a_{2}y_{t-2}+\cdots +a_{n}y_{t-n}+b}$$

можно заменить следующими n уравнениями первого порядка:

$${\displaystyle {\begin{aligned}w_{1,t}&=a_{1}w_{1,t-1}+a_{2}w_{2,t-1}+\cdots +a_{n}w_{n,t-1}+b\\w_{2,t}&=w_{1,t-1}\\&\,\,\,\vdots \\w_{n,t}&=w_{n-1,t-1}.\end{aligned}}}$$

Определение вектора w _i как

$${\displaystyle \mathbf {w} _{i}={\begin{bmatrix}w_{1,i}\\w_{2,i}\\\vdots \\w_{n,i}\end{bmatrix}}}$$

это можно представить в виде матрицы как

$${\displaystyle \mathbf {w} _{t}=\mathbf {A} \mathbf {w} _{t-1}+\mathbf {b} }$$

Здесь A — матрица размера n  ×  n , в которой первая строка содержит a ₁ , ..., a _n , а все остальные строки содержат одну единицу, а все остальные элементы равны 0, а b — вектор-столбец с первым элементом b и остальными элементами, равными 0.

Это матричное уравнение можно решить с помощью методов из статьи Матричное разностное уравнение . В однородном случае y _i является параперманентом нижней треугольной матрицы ^[6]

Рецидив

$${\displaystyle y_{t}=a_{1}y_{t-1}+\cdots +a_{n}y_{t-n}+b,}$$

можно решить с помощью теории производящих функций . Сначала запишем . Тогда рекуррентность эквивалентна следующему уравнению производящей функции:${\textstyle Y(x)=\sum _{t\geq 0}y_{t}x^{t}}$

$${\displaystyle Y(x)=a_{1}xY(x)+a_{2}x^{2}Y(x)+\cdots +a_{n}x^{n}Y(x)+{\frac {b}{1-x}}+p(x)}$$

где - многочлен степени не выше, корректирующий начальные члены. Из этого уравнения мы можем решить, чтобы получить${\displaystyle p(x)}$${\displaystyle n-1}$

$${\displaystyle Y(x)=\left({\frac {b}{1-x}}+p(x)\right)\cdot {\frac {1}{1-a_{1}x-a_{2}x^{2}-\cdots -a_{n}x^{n}}}.}$$

Другими словами, не беспокоясь о точных коэффициентах, можно выразить как рациональную функцию${\displaystyle Y(x)}$ ${\displaystyle Y(x)={\frac {f(x)}{g(x)}}.}$

Замкнутая форма может быть получена посредством разложения дроби . В частности, если производящая функция записана как$${\displaystyle {\frac {f(x)}{g(x)}}=\sum _{i}{\frac {f_{i}(x)}{(x-r_{i})^{m_{i}}}}}$$

тогда полином определяет начальный набор поправок , знаменатель определяет экспоненциальный член , а степень вместе с числителем определяют коэффициент полинома .${\displaystyle p(x)}$${\displaystyle z(n)}$${\displaystyle (x-r_{i})^{m}}$${\displaystyle r_{i}^{n}}$${\displaystyle m}$${\displaystyle f_{i}(x)}$${\displaystyle k_{i}(n)}$

Метод решения линейных дифференциальных уравнений аналогичен методу, описанному выше — «интеллектуальная догадка» ( анзац ) для линейных дифференциальных уравнений с постоянными коэффициентами имеет вид , где — комплексное число, которое определяется путем подстановки догадки в дифференциальное уравнение.${\displaystyle e^{\lambda x}}$${\displaystyle \lambda }$

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

$${\displaystyle \sum _{n=0}^{\infty }{\frac {f^{(n)}(a)}{n!}}(x-a)^{n}}$$

можно видеть, что коэффициенты ряда задаются -й производной от , оцененной в точке . Дифференциальное уравнение дает линейное разностное уравнение, связывающее эти коэффициенты.${\displaystyle n}$${\displaystyle f(x)}$${\displaystyle a}$

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

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

$${\displaystyle y^{[k]}\to f[n+k]}$$и в более общем плане$${\displaystyle x^{m}*y^{[k]}\to n(n-1)...(n-m+1)f[n+k-m]}$$

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

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

дается

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

или

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

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

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

$${\displaystyle ay''+by'+cy=0}$$

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

$${\displaystyle y=e^{ax}.}$$

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

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

Легко видеть, что -я производная от вычисляется при .${\displaystyle n}$${\displaystyle e^{ax}}$${\displaystyle 0}$${\displaystyle a^{n}}$

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

В уравнении решения

$${\displaystyle x_{t}=c_{1}\lambda _{1}^{t}+\cdots +c_{n}\lambda _{n}^{t},}$$

член с действительными характеристическими корнями сходится к 0, когда t растет бесконечно, если абсолютное значение характеристического корня меньше 1. Если абсолютное значение равно 1, член останется постоянным, когда t растет, если корень равен +1, но будет колебаться между двумя значениями, если корень равен −1. Если абсолютное значение корня больше 1, член будет становиться все больше и больше с течением времени. Пара членов с комплексно-сопряженными характеристическими корнями будет сходиться к 0 с затухающими колебаниями, если абсолютное значение модуля M корней меньше 1; если модуль равен 1, то постоянные амплитудные колебания в объединенных членах сохранятся; а если модуль больше 1, объединенные члены будут демонстрировать колебания все возрастающей величины.

Таким образом, эволюционирующая переменная x будет стремиться к 0, если все характеристические корни имеют величину меньше 1.

Если наибольший корень имеет абсолютное значение 1, то не произойдет ни сходимости к 0, ни расходимости к бесконечности. Если все корни с величиной 1 действительны и положительны, x будет сходиться к сумме своих постоянных членов c _i ; в отличие от устойчивого случая, это сходимое значение зависит от начальных условий; различные начальные точки приводят к различным точкам в долгосрочной перспективе. Если какой-либо корень равен −1, его член будет вносить постоянные колебания между двумя значениями. Если какие-либо из корней единичной величины являются комплексными, то колебания x с постоянной амплитудой сохранятся.

Наконец, если какой-либо характеристический корень имеет величину больше 1, то x будет стремиться к бесконечности с течением времени или будет колебаться между все большими положительными и отрицательными значениями.

Теорема Иссаи Шура утверждает, что все корни имеют величину меньше 1 (устойчивый случай) тогда и только тогда, когда конкретная строка определителей все положительна. ^{[2] : 247}

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

• Рекуррентное соотношение
• Линейное дифференциальное уравнение
• Теорема Скулема–Малера–Леха
• проблема Сколема