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

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

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

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

Определения

Линейная рекуррентная система с постоянными коэффициентами представляет собой уравнение следующего вида, записанное через параметры 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 п}$

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

${\ 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_{t-n}+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_{t-n}-y^{*}\right)}$

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

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

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

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

${\displaystyle y_{t}=a_{1}y_{t-1}+\cdots +a_{n}y_{t-n}+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_{t-n}=y_{t-1}-a_{1}y_{t-2}-\cdots -a_{n}y_{t-(n+1)}}$

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

Пример решения для небольших заказов

Корни характеристического многочлена играют решающую роль в поиске и понимании последовательностей, удовлетворяющих рекуррентности. Если существуют различные корни , то каждое решение рекуррентности принимает вид${\displaystyle d}$${\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 (x-r)^{3}}$${\displaystyle r}$

${\displaystyle a_{n}=k_{1}r^{n}+k_{2}nr^{n}+k_{3}n^{2}r^{n}.}$^[3]

Заказать 1

Для порядка 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}$

Заказать 2

Решения таких рекуррентных соотношений более высокого порядка находятся систематическим путем, часто с использованием того факта, что рекуррентное решение является именно тогда, когда является корнем характеристического многочлена. К этому можно подойти напрямую или с помощью производящих функций ( формальные степенные ряды ) или матриц.${\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 r^{2}=Ar+B,}$

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

которое является характеристическим уравнением рекуррентного соотношения. Решите для , чтобы получить два корня , : эти корни известны как характеристические корни или собственные значения характеристического уравнения. В зависимости от характера корней получаются разные решения: если эти корни различны, мы имеем общее решение${\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}}}$

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

Теперь процесс нахождения коэффициентов 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 -го порядка в матричное разностное уравнение первого порядка . Это достигается записью _{w1 , t} = yt , w2 _{, t} = yt− 1 ₌ w1 , _{t − 1} , w3 _{, t} = _{yt − 2} = w2 _{, 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.

Это матричное уравнение можно решить с помощью методов, описанных в статье Матричное разностное уравнение .

Решение с использованием производящих функций

Повторение

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

можно решить с помощью теории производящих функций . Во-первых, мы пишем . Повторение тогда эквивалентно следующему уравнению производящей функции:${\displaystyle 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-преобразований . 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.

Смотрите также

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

использованная литература