Linjärt återfall med konstanta koefficienter

Ytterligare information: Konstant-rekursiv sekvens

I matematik (inklusive kombinatorik , linjär algebra och dynamiska system ) sätter ett linjärt återfall med konstanta koefficienter (även känt som ett linjärt återkommande förhållande eller linjär skillnadsekvation ) lika med 0 ett polynom som är linjärt i de olika iterationerna av en variabel - det vill säga i värdena för elementen i en sekvens . Polynomets linjäritet betyder att var och en av dess termer har grad 0 eller 1. Ett linjärt återfall betecknar utvecklingen av någon variabel över tiden, med den aktuella tidsperioden eller det diskreta ögonblicket i tiden betecknad som t , en period tidigare betecknad som t − 1 , en period senare som t + 1 osv.

Lösningen av en sådan ekvation är en funktion av t , och inte av några itererade värden , vilket ger värdet av iterationen när som helst. För att hitta lösningen är det nödvändigt att känna till de specifika värdena (kända som initialvillkor ) för n av iteraten, och normalt är dessa de n iteraten som är äldst. Ekvationen eller dess variabel sägs vara stabil om variabelns gräns när tiden går till oändlighet existerar från någon uppsättning initiala villkor; denna gräns kallas steady state .

, såsom inom ekonomi för att modellera utvecklingen genom tiden av variabler som bruttonationalprodukten , inflationstakten , växelkursen etc. De används vid modellering av sådana tidsserier eftersom värden på dessa variabler mäts endast med diskreta intervall. I ekonometriska tillämpningar modelleras linjära differensekvationer med stokastiska termer i form av autoregressiva (AR) modeller och i modeller som vektorautoregression (VAR) och autoregressivt glidande medelvärde (ARMA) som kombinerar AR med andra funktioner.

Definitioner

Ett linjärt återfall med konstanta koefficienter är en ekvation av följande form, skriven i termer av parametrarna a ₁ , …, a _n och b :

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

eller motsvarande

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

Det positiva heltal $n$ kallas ordningen för återkommande och anger den längsta tidsförskjutningen mellan iterationerna. Ekvationen kallas homogen om b = 0 och ohomogen om b ≠ 0 .

Om ekvationen är homogen bestämmer koefficienterna det karakteristiska polynomet (även "hjälppolynom" eller "kompanjonspolynom")

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

vars rötter spelar en avgörande roll för att hitta och förstå de sekvenser som tillfredsställer upprepningen.

Omvandling till homogen form

Om b ≠ 0 , ekvationen

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

sägs vara icke-homogena . För att lösa denna ekvation är det lämpligt att konvertera den till homogen form, utan konstant term. Detta görs genom att först hitta ekvationens stabila tillståndsvärde — ett värde y * så att, om n på varandra följande iterationer alla hade detta värde, så skulle alla framtida värden också. Detta värde hittas genom att sätta alla värden på y lika med y * i differensekvationen, och lösa, på så sätt erhålla

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

antar att nämnaren inte är 0. Om den är noll existerar inte stationärt tillstånd.

Givet det stationära tillståndet kan differensekvationen skrivas om i termer av avvikelser av iteraten från det stationära tillståndet, som

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

som inte har någon konstant term, och som kan skrivas mer kortfattat som

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

där x är lika med y − y * . Detta är den homogena formen.

Om det inte finns något stabilt tillstånd, differensekvationen

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

kan kombineras med dess motsvarande form

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

att få (genom att lösa båda för b )

$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)}$

där lika termer kan kombineras för att ge en homogen ekvation av en ordning högre än originalet.

Lösningsexempel för små beställningar

Rötterna till det karakteristiska polynomet spelar en avgörande roll för att hitta och förstå de sekvenser som tillfredsställer upprepningen. Om det finns $d$ distinkta rötter $r_{1},r_{2},\ldots ,r_{d},$ så är varje lösning på upprepningen tar formen

$a_{n}=k_{1}r_{1}^{n}+k_{2}r_{ 2}^{n}+\cdots +k_{d}r_{d}^{n},$

där koefficienterna $k_{i}$ bestäms för att passa de initiala villkoren för återfallet. När samma rötter förekommer flera gånger, multipliceras termerna i denna formel som motsvarar den andra och senare förekomsten av samma rot med ökande potenser av $n$ . Till exempel, om det karakteristiska polynomet kan faktoriseras som ${\displaystyle (xr)^{3}} ,$ där samma rot $r$ förekommer tre gånger, så skulle lösningen ha formen

$a_{n}=k_{1}r^{n}+k_{2}nr^{n}+k_{3}n^{2}r^{n}.$

Beställning 1

För order 1, upprepningen

$a_{n}=ra_{n-1}$

har lösningen $a_{n}=r^{n}$ med $a_{0}=1$ och den mest allmänna lösningen är ${\ displaystyle a_{n}=kr^{n}}$ med $a_{0}=k$ . Det karakteristiska polynomet som är lika med noll (den karakteristiska ekvationen ) är helt enkelt $tr=0$ .

Beställning 2

Lösningar på sådana återkommande relationer av högre ordning hittas på systematiska sätt, ofta med det faktum att $a_{n}=r^{n}$ är en lösning för återkommande exakt när ${ \displaystyle t=r}$ är en rot av det karakteristiska polynomet. Detta kan närma sig direkt eller med hjälp av genereringsfunktioner ( formella effektserier) eller matriser.

Betrakta till exempel en återkommande relation av formen

$a_{n}=Aa_{n-1}+Ba_{n-2}.$

När har den en lösning av samma allmänna form som $a_{n}=r^{n}$ ? Genom att ersätta denna gissning ( ansatz ) i återfallsrelationen finner vi det

$r^{n}=Ar^{n-1}+Br^{n-2}$

måste vara sant för alla $n>1$ .

Genom att dividera med $r^{n-2}$ får vi att alla dessa ekvationer reduceras till samma sak:

$r^{2}=Ar+B,$

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

som är den karakteristiska ekvationen för återfallsrelationen. Lös för $r$ för att erhålla de två rötterna ${\displaystyle \lambda _{1}} ,$ λ $\displaystyle \lambda _{2}}$ : dessa rötter är kända som de karakteristiska rötterna eller egenvärdena för den karakteristiska ekvationen. Olika lösningar erhålls beroende på rötternas natur: Om dessa rötter är distinkta har vi den allmänna lösningen

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

medan om de är identiska (när $A^{2}+4B=0$ ), har vi

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

Detta är den mest allmänna lösningen; de två konstanterna $C$ och $D$ kan väljas baserat på två givna initiala villkor $a_{0}$ och $a_{1}$ för att producera en specifik lösning .

När det gäller komplexa egenvärden (som också ger upphov till komplexa värden för lösningsparametrarna $C$ och $D$ ), kan användningen av komplexa tal elimineras genom att skriva om lösningen i trigonometrisk form. I detta fall kan vi skriva egenvärdena som $\lambda _{1},\lambda _{2}=\alpha \pm \beta i.$ Då kan det visas att

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

kan skrivas om som

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

var

${\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}}$

Här är $E$ och $F$ (eller motsvarande, $G$ och $\delta$ ) reella konstanter som beror på initialförhållandena. Använder sig av

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

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

man kan förenkla lösningen ovan som

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

där $a_{1}$ och $a_{2}$ är initialvillkoren och

${\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}}$

På detta sätt finns det inget behov av att lösa för $\lambda _{1}$ och $\lambda _{2}$ .

I alla fall – reella distinkta egenvärden, reella duplicerade egenvärden och komplexa konjugerade egenvärden – är ekvationen stabil (det vill säga variabeln $a$ konvergerar till ett fast värde [specifikt noll]) om och endast om båda egenvärdena är mindre än ett i absolut värde . I detta andra ordningens fall kan detta villkor på egenvärdena visas vara ekvivalent med $|A|<1-B<2$ , vilket är ekvivalent med $|B|<1$ och $|A|<1-B$ .

Allmän lösning

Se även: Återkommande ekvation § Lösa homogena linjära återfallsrelationer med konstanta koefficienter

Karakteristiskt polynom och rötter

Löser den homogena ekvationen

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

innebär att först lösa dess karakteristiska polynom

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

för dess karakteristiska rötter λ ₁ , ..., λ _n . Dessa rötter kan lösas för algebraiskt om n ≤ 4 , men inte nödvändigtvis annars . Om lösningen ska användas numeriskt kan alla rötter till denna karakteristiska ekvation hittas med numeriska metoder . Men för användning i ett teoretiskt sammanhang kan det vara så att den enda information som krävs om rötterna är om någon av dem är större än eller lika med 1 i absolut värde .

Det kan vara så att alla rötter är reella eller istället kan det finnas några som är komplexa tal . I det senare fallet kommer alla komplexa rötter i komplexa konjugerade par.

Lösning med distinkta karakteristiska rötter

Om alla karakteristiska rötter är distinkta, lösningen av den homogena linjära återkomsten

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

kan skrivas i termer av de karakteristiska rötterna som

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

där koefficienterna c _i kan hittas genom att åberopa initialvillkoren. Specifikt, för varje tidsperiod för vilken ett iterationsvärde är känt, kan detta värde och dess motsvarande värde på t ersättas i lösningsekvationen för att erhålla en linjär ekvation i de n ännu okända parametrarna; n sådana ekvationer, en för varje initialtillstånd, kan lösas samtidigt för de n parametervärdena. Om alla karakteristiska rötter är reella, så kommer alla koefficientvärdena c _i också att vara reella; men med icke-reella komplexa rötter, i allmänhet kommer vissa av dessa koefficienter också att vara icke-reella.

Konvertera komplex lösning till trigonometrisk form

Om det finns komplexa rötter kommer de i konjugerade par och det gör även de komplexa termerna i lösningsekvationen. Om två av dessa komplexa termer är c _​​j λ
^t _j och c _{j +1} λ
^t _{j +1} , kan rötterna λ _j skrivas som

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

där i är den imaginära enheten och M är modulen för rötterna:

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

Då kan de två komplexa termerna i lösningsekvationen skrivas som

${\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 ti\sin \theta t\right){\bigr )}\end{aligned}}$

där θ är vinkeln vars cosinus är α / M och vars sinus är β / M ; den sista jämlikheten här använde sig av de Moivres formel .

Nu garanterar processen att hitta koefficienterna c _j och c _{j +1} att de också är komplexa konjugat, som kan skrivas som γ ± δi . Att använda detta i den sista ekvationen ger detta uttryck för de två komplexa termerna i lösningsekvationen:

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

som också kan skrivas som

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

där ψ är vinkeln vars cosinus är γ / √ γ ² + δ ² och vars sinus är δ / √ γ ² + δ ² .

Cyklisitet

Beroende på de initiala förhållandena, även med alla rötter verkliga, kan iterationerna uppleva en övergående tendens att gå över och under steady state-värdet. Men sann cyklicitet innebär en permanent tendens att fluktuera, och detta inträffar om det finns minst ett par av komplexa konjugerade karakteristiska rötter. Detta kan ses i den trigonometriska formen av deras bidrag till lösningsekvationen, som involverar cos θt och sin θt .

Lösning med dubbla karakteristiska rötter

I andra ordningens fall, om de två rötterna är identiska ( λ ₁ = λ ₂ ), kan de båda betecknas som λ och en lösning kan ha formen

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

Lösning genom konvertering till matrisform

En alternativ lösningsmetod innefattar att konvertera n: te ordningens differensekvation till en första ordningens matrisdifferensekvation . Detta görs genom att skriva 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} , och så vidare . Sedan den ursprungliga enda n :te ordningens ekvation

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

kan ersättas av följande n första ordningens ekvationer:

${\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}}$

Definiera vektorn w _i as

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

detta kan sättas i matrisform som

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

Här är A en n × n matris där den första raden innehåller a _{1 ,} ..., a _n och alla andra rader har en enda 1 där alla andra element är 0, och b är en kolumnvektor med första elementet b och med resten av dess element är 0.

Denna matrisekvation kan lösas med metoderna i artikeln Matrisdifferensekvation . I det homogena fallet y _i en para-permanent av en lägre triangulär matris

Lösning med genererande funktioner

Upprepningen

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

kan lösas med hjälp av teorin om genererande funktioner . Först skriver vi $Y(x)=\summa _{t\geq 0}y_{t}x^{t}$ . Upprepningen är då ekvivalent med följande genererande funktionsekvation:

$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)$

där $p(x)$ är ett polynom med högst grad $n-1$ som korrigerar de initiala termerna. Från denna ekvation kan vi lösa för att få

$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}}}.$

Med andra ord, utan att oroa dig för de exakta koefficienterna, $Y(x)$ kan uttryckas som en rationell funktion $Y(x)={\frac {f(x)}{g(x)}}.$

Den slutna formen kan sedan härledas via partiell fraktionssönderdelning . Specifikt om genereringsfunktionen skrivs som

${\frac {f(x)}{g(x)}}=\summa _{i} {\frac {f_{i}(x)}{(x-r_{i})^{m_{i}}}}$

sedan bestämmer polynomet $p(x)$ den initiala uppsättningen av korrigeringar $z(n)$ , nämnaren $(x-r_ {i})^{m}$ bestämmer exponentialtermen $r_{i}^{n}$ och graden $m$ tillsammans med täljaren $f_{i}(x)$ bestäm polynomkoefficienten $k_{i}(n)$ .

Relation till lösning av differentialekvationer

Metoden för att lösa linjära differentialekvationer liknar metoden ovan — den "intelligenta gissningen" ( ansatz ) för linjära differentialekvationer med konstanta koefficienter är $e^{\lambda x}$ där $\ lambda$ är ett komplext tal som bestäms genom att ersätta gissningen i differentialekvationen.

Detta är ingen slump. Med tanke på Taylor-serien av lösningen till en linjär differentialekvation:

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

det kan ses att koefficienterna för serien ges av den $n$ -th derivatan av $f(x)$ utvärderad vid punkten $a$ . Differentialekvationen tillhandahåller en linjär skillnadsekvation som relaterar dessa koefficienter.

Denna ekvivalens kan användas för att snabbt lösa upprepningssambandet för koefficienterna i potensserielösningen av en linjär differentialekvation.

Tumregeln (för ekvationer där polynomet som multiplicerar den första termen är icke-noll vid noll) är att:

$y^{[k]}\to f[n+k]$

och mer allmänt

$x^{m}*y^{[k]}\to n(n-1)...(n-m+1)f [n+km]$

Exempel: Upprepningssambandet för Taylor-seriens koefficienter i ekvationen:

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

ges av

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

eller

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

Detta exempel visar hur problem som generellt löses med hjälp av effektserielösningsmetoden som lärs ut i normala differentialekvationsklasser kan lösas på ett mycket enklare sätt.

Exempel: Differentialekvationen

$ay''+by'+cy=0$

har lösning

$y=e^{ax}.$

Omvandlingen av differentialekvationen till en differensekvation av Taylor-koefficienterna är

$af[n+2]+bf[n+1]+cf[n]=0.$

Det är lätt att se att den $n$ -te derivatan av $e^{ax}$ utvärderad vid $0$ är $a^{n}$ .

Lösning med z-transformers

Vissa differensekvationer - i synnerhet linjära konstantkoefficientdifferensekvationer - kan lösas med z-transformer . Z - transformerna är en klass av integrerade transformationer som leder till mer bekväma algebraiska manipulationer och enklare lösningar. Det finns fall där det är nästan omöjligt att få en direkt lösning, men det är enkelt att lösa problemet via en genomtänkt vald integrerad transformation.

Stabilitet

I lösningsekvationen

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

en term med reella karakteristiska rötter konvergerar till 0 när t växer oändligt stort om det absoluta värdet av den karakteristiska roten är mindre än 1. Om det absoluta värdet är lika med 1 kommer termen att förbli konstant när t växer om roten är +1 men fluktuera mellan två värden om roten är −1. Om rotens absoluta värde är större än 1 kommer termen att bli större och större med tiden. Ett par termer med komplexa konjugerade karakteristiska rötter kommer att konvergera till 0 med dämpande fluktuationer om det absoluta värdet av rötternas modul M är mindre än 1; om modulen är lika med 1 kommer konstanta amplitudfluktuationer i de kombinerade termerna att kvarstå; och om modulen är större än 1, kommer de kombinerade termerna att visa fluktuationer med ständigt ökande storlek.

Således kommer den utvecklande variabeln x att konvergera till 0 om alla de karakteristiska rötterna har en magnitud mindre än 1.

Om den största roten har absolutvärdet 1 kommer varken konvergens till 0 eller divergens till oändlighet att ske. Om alla rötter med magnitud 1 är reella och positiva, x att konvergera till summan av deras konstanta termer c _i ; till skillnad från i det stabila fallet beror detta konvergerade värde på initialförhållandena; olika utgångspunkter leder till olika poäng i längden. Om någon rot är −1, kommer dess term att bidra med permanenta fluktuationer mellan två värden. Om någon av enhetsstorleksrötterna är komplexa kommer konstantamplitudfluktuationer av x att kvarstå.

Slutligen, om någon karakteristisk rot har en magnitud större än 1, så kommer x att divergera till oändligheten när tiden går till oändligheten, eller kommer att fluktuera mellan allt större positiva och negativa värden.

En teorem av Issai Schur säger att alla rötter har en magnitud mindre än 1 (det stabila fallet) om och endast om en viss sträng av determinanter alla är positiva.

Om en icke-homogen linjär differensekvation har omvandlats till homogen form som har analyserats enligt ovan, kommer stabilitets- och cyklikalitetsegenskaperna för den ursprungliga icke-homogena ekvationen att vara desamma som för den härledda homogena formen, med konvergens i stabilt fall är till värdet y * i stationärt tillstånd istället för till 0.

Se även

• Återkommande förhållande
• Linjär differentialekvation
• Skolem–Mahler–Lech-satsen
• Skolem problem