Linjär återkommande sekvens

En linjär återkommande sekvens ( linjär återkommande ) är vilken numerisk sekvens som helst som definieras av en linjär återkommande relation : $x_{0},x_{1},\dots$

{\displaystyle x_{n}=a_{1}\cdot x_{n-1}+\dots +a_{d}\cdot x_{nd))

för alla

n\geqslant d

med givna initiala termer , där d är ett fast naturligt tal , ges numeriska koefficienter, . I det här fallet kallas talet d för sekvensen . ${\displaystyle x_{0},\dots ,x_{d-1))$ $a_{1},\dots ,a_{d}$ $a_{d}\neq 0$

Linjära återkommande sekvenser kallas ibland också för återkommande sekvenser .

Teorin om linjära återkommande sekvenser är en exakt analog till teorin om linjära differentialekvationer med konstanta koefficienter .

Exempel

Särskilda fall av linjära återkommande sekvenser är sekvenser:

Lucas-sekvenser som tillfredsställer särskilt: ${\displaystyle x_{n}=P\cdot x_{n-1}-Q\cdot x_{n-2))$
- aritmetiska progressioner med ; $(P,Q)=(2,1)$
- geometrisk progression med ; $Q=0$
- Fibonacci-tal med ; $(P,Q)=(1,-1)$
- Lucas nummer med ; $(P,Q)=(1,-1)$
tribonacci siffror tillfredsställande . ${\displaystyle x_{n}=x_{n-1}+x_{n-2}+x_{n-3))$

Formel för allmän term

För linjära återkommande sekvenser finns det en formel som uttrycker den vanliga termen för sekvensen i termer av rötterna till dess karakteristiska polynom

\lambda ^{d}-a_{1}\lambda ^{d-1}-\dots -a_{d-1}\lambda -a_{d}.

Den vanliga termen uttrycks nämligen som en linjär kombination av sekvenser av formen $d$

x_{n}=\lambda _{k}^{n}\cdot n^{m},

där är roten till det karakteristiska polynomet och är ett icke-negativt heltal mindre än multipliciteten av . $\lambda_k$ $m$ $\lambda_k$

För Fibonacci-tal är en sådan formel Binets formel .

Exempel

För att hitta formeln för den gemensamma termen för sekvensen som uppfyller den andra ordningens linjära återkommande ekvationen med initiala värden , bör man lösa den karakteristiska ekvationen $F_{n}$ ${\displaystyle F_{n}=b\cdot F_{n-1}+c\cdot F_{n-2))$ $F_{1}$ $F_{2}$

q^{2}-bq-c=0

Om ekvationen har två olika icke-nollrötter och , då för godtyckliga konstanter och , sekvensen $q_{1}$ $q_{2}$ $A$ $B$

F_{n}=A\cdot q_{1}^{n}+B\cdot q_{2}^{n},

tillfredsställer återfallsrelationen; det återstår att hitta siffrorna och så $A$ $B$

{\displaystyle F_{1}=A\cdot q_{1}+B\cdot q_{2))

och .

F_{2}=A\cdot q_{1}^{2}+B\cdot q_{2}^{2}

Om diskriminanten för den karakteristiska ekvationen är lika med noll och därför ekvationen har en enda rot , då för godtyckliga konstanter och , sekvensen $q_{1}$ $A$ $B$

{\displaystyle F_{n}=(A+B\cdot n)\cdot q_{1}^{n))

tillfredsställer återfallsrelationen; det återstår att hitta siffrorna och så $A$ $B$

{\displaystyle F_{1}=(A+B)\cdot q_{1))

och .

F_{2}=(A+B\cdot 2)\cdot q_{1}^{2}

I synnerhet för den sekvens som definieras av följande linjära återkommande ekvation av andra ordningen

F_{n}=5\cdot F_{n-1}-6\cdot F_{n-2}

; , .

F_{1}=1

F_{2}=-2

rötterna till den karakteristiska ekvationen är , . Det är därför $q^{2}-5\cdot q+6=0$ $q_{1}=2$ $q_{2}=3$

F_{n}=-2\cdot (3^{n-1}-2^{n-1})-6\cdot (3^{n-2}-2^{n-2}) .

Till sist:

F_{n}=5\cdot 2^{n-1}-4\cdot 3^{n-1}.

Applikationer

Linjära återkommande sekvenser över restringar används traditionellt för att generera pseudoslumptal .

Historik

Grunderna i teorin om linjära återkommande sekvenser gavs på tjugotalet av artonhundratalet av Abraham de Moivre och Daniel Bernoulli . Leonhard Euler förklarade det i det trettonde kapitlet i hans Introduktion till analysen av infinitesimals (1748). [1] Senare presenterade Pafnuty Lvovich Chebyshev och ännu senare Andrey Andreevich Markov denna teori i sina kurser om kalkylen för ändliga skillnader. [2] [3]

Se även

Anteckningar

↑ L. Euler, Introduction to the analysis of infinitesimals, vol. I, M. - L., 1936, s. 197–218
↑ P. L. Chebyshev, Sannolikhetsteori, föreläsningar 1879–1880, M. - L., 1936, s. 139–147
↑ A. A. Markov, Calculus of finite differences, 2:a uppl., Odessa, 1910, s. 209–239

Litteratur

A. I. Markushevich . returnera sekvenser . - Fru. Publishing House of Technical and Theoretical Literature, 1950. - Vol. 1. - ( Populära föreläsningar om matematik ).
M. M. Glukhov, V. P. Elizarov, A. A. Nechaev. Kapitel XXV. Linjära återkommande sekvenser // Algebra. - Lärobok. I 2 volymer. - M . : Helios ARV, 2003. - T. 2. - ISBN 8-85438-072-2 .
A. Egorov. Pisotnummer // Kvant . - 2005. - Nr 5 . - S. 8-13 .
Chebrakov Yu. V. Kapitel 2.7. Återkommande ekvationer // Teori om magiska matriser. Utgivning av TMM-1 . - St Petersburg. , 2010.

Sekvenser och rader
Sekvenser	Numerisk sekvens Grundläggande sekvens Linjär återkommande sekvens Fibonacci-siffror lockiga siffror Faktoriell Barker-sekvens de bruijn sekvens
Rader, grundläggande	Radsumma Resten av raden Villkorlig konvergens Omväxlande serie Rad flersektion
Nummerserier ( operationer med nummerserier )	harmonisk serie Leibniz-serien En serie omvända kvadrater En serie ömsesidiga primtal Dirichlet rad Mercator-serien Rad Grandi 1 - 2 + 3 - 4 + ... 1 + 2 + 3 + 4 + ...
funktionella rader	Taylor-serien Laurent-serien Fourier-serier Trigonometrisk Fourier-serie trigonometrisk serie Wiener-serien
Andra radtyper	Neumann-serien Puiseux rad