Lineær tilbagevendende sekvens

En lineær tilbagevendende sekvens ( lineær gentagelse ) er enhver numerisk sekvens defineret af en lineær gentagelsesrelation : $x_{0},x_{1},\dots$

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

for alle

n\geqslant d

med givne begyndelsesled , hvor d er et fast naturligt tal , gives numeriske koefficienter, . I dette tilfælde kaldes tallet d for rækkefølgen . ${\displaystyle x_{0},\dots ,x_{d-1))$ $a_{1},\dots ,a_{d}$ $a_{d}\neq 0$

Lineære tilbagevendende sekvenser kaldes nogle gange også tilbagevendende sekvenser .

Teorien om lineære tilbagevendende sekvenser er en nøjagtig analog til teorien om lineære differentialligninger med konstante koefficienter .

Eksempler

Særlige tilfælde af lineære tilbagevendende sekvenser er sekvenser:

Lucas-sekvenser , der især tilfredsstiller : ${\displaystyle x_{n}=P\cdot x_{n-1}-Q\cdot x_{n-2))$
- aritmetiske forløb med ; $(P,Q)=(2,1)$
- geometrisk progression med ; $Q=0$
- Fibonacci-tal med ; $(P,Q)=(1,-1)$
- Lucas numre med ; $(P,Q)=(1,-1)$
tribonacci tal tilfredsstillende . ${\displaystyle x_{n}=x_{n-1}+x_{n-2}+x_{n-3))$

Generel udtryksformel

For lineære tilbagevendende sekvenser er der en formel, der udtrykker det almindelige udtryk for sekvensen i form af rødderne af dens karakteristiske polynomium

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

Det almindelige udtryk er nemlig udtrykt som en lineær kombination af sekvenser af formen $d$

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

hvor er roden af det karakteristiske polynomium og er et ikke-negativt heltal mindre end multipliciteten af . $\lambda_k$ $m$ $\lambda_k$

For Fibonacci-tal er en sådan formel Binets formel .

Eksempel

For at finde formlen for det fælles led i sekvensen, der opfylder andenordens lineære tilbagevendende ligning med begyndelsesværdier , skal man løse den karakteristiske ligning $F_{n}$ ${\displaystyle F_{n}=b\cdot F_{n-1}+c\cdot F_{n-2))$ $F_{1}$ $F_{2}$

q^{2}-bq-c=0

Hvis ligningen har to forskellige ikke-nul rødder og , så for vilkårlige konstanter og , rækkefølgen $q_{1}$ $q_{2}$ $EN$ $B$

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

tilfredsstiller gentagelsesforholdet; det er tilbage at finde tallene og det $EN$ $B$

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

og .

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

Hvis diskriminanten af den karakteristiske ligning er lig med nul, og ligningen derfor har en enkelt rod , så for vilkårlige konstanter og sekvensen $q_{1}$ $EN$ $B$

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

tilfredsstiller gentagelsesforholdet; det er tilbage at finde tallene og det $EN$ $B$

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

og .

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

Især for sekvensen defineret af den følgende andenordens lineære tilbagevendende ligning

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

; , .

F_{1}=1

F_{2}=-2

rødderne til den karakteristiske ligning er . Derfor $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}) .

Langt om længe:

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

Ansøgninger

Lineære tilbagevendende sekvenser over restringe bruges traditionelt til at generere pseudo-tilfældige tal .

Historie

Det grundlæggende i teorien om lineære tilbagevendende sekvenser blev givet i tyverne af det attende århundrede af Abraham de Moivre og Daniel Bernoulli . Leonhard Euler forklarede det i det trettende kapitel af hans Introduction to the Analysis of Infinitesimals (1748). [1] Senere præsenterede Pafnuty Lvovich Chebyshev og endnu senere Andrey Andreevich Markov denne teori i deres kurser om beregningen af endelige forskelle. [2] [3]

Se også

Noter

↑ L. Euler, Introduktion til analyse af infinitesimals, bind I, M. - L., 1936, s. 197–218
↑ P. L. Chebyshev, Sandsynlighedsteori, forelæsninger 1879–1880, M. - L., 1936, s. 139–147
↑ A. A. Markov, Calculus of finite differences, 2. udgave, Odessa, 1910, s. 209–239

Litteratur

A. I. Markushevich . returnere sekvenser . - Fru. Forlaget for teknisk og teoretisk litteratur, 1950. - Vol. 1. - ( Populære forelæsninger om matematik ).
M. M. Glukhov, V. P. Elizarov, A. A. Nechaev. Kapitel XXV. Lineære tilbagevendende sekvenser // Algebra. - Lærebog. I 2 bind. - M . : Helios ARV, 2003. - T. 2. - ISBN 8-85438-072-2 .
A. Egorov. Pisottal // Kvant . - 2005. - Nr. 5 . - S. 8-13 .
Chebrakov Yu. V. Kapitel 2.7. Tilbagevendende ligninger // Teori om magiske matricer. Frigivelse af TMM-1 . - Sankt Petersborg. , 2010.

Sekvenser og rækker
Sekvenser	Numerisk rækkefølge Grundlæggende rækkefølge Lineær tilbagevendende sekvens Fibonacci-tal krøllede tal Faktoriel Barker-sekvens de bruijn rækkefølge
Rækker, grundlæggende	Rækkesum Resten af rækken Betinget konvergens Skiftende serie Række multisektion
Talserier ( operationer med talserier )	harmoniske serier Leibniz-serien En række omvendte firkanter En række gensidige primtal Dirichlet række Mercator serien Række Grandi 1 - 2 + 3 - 4 + ... 1 + 2 + 3 + 4 + ...
funktionelle rækker	Taylor-serien Laurent-serien Fourier-serien Trigonometrisk Fourier-serie trigonometriske serier Wiener-serien
Andre rækketyper	Neumann-serien Puiseux række