Lineární rekurentní sekvence

Lineární opakující se sekvence ( lineární opakování ) je jakákoli číselná posloupnost definovaná lineárním vztahem opakování : $x_{0},x_{1},\tečky$

{\displaystyle x_{n}=a_{1}\cdot x_{n-1}+\tečky +a_{d}\cdot x_{nd))

pro všechny

n\geqslant d

s danými počátečními členy , kde d je pevné přirozené číslo , jsou uvedeny číselné koeficienty, . V tomto případě se číslo d nazývá řád posloupnosti. ${\displaystyle x_{0},\tečky ,x_{d-1))$ $a_{1},\tečky ,a_{d}$ $a_{d}\neq 0$

Lineární rekurentní sekvence se někdy také nazývají rekurentní sekvence .

Teorie lineárních rekurentních sekvencí je přesnou obdobou teorie lineárních diferenciálních rovnic s konstantními koeficienty .

Příklady

Konkrétními případy lineárních rekurentních sekvencí jsou sekvence:

Lucasovy sekvence uspokojující zejména: ${\displaystyle x_{n}=P\cdot x_{n-1}-Q\cdot x_{n-2))$
- aritmetické posloupnosti s ; $(P,Q)=(2,1)$
- geometrický postup s ; $Q=0$
- Fibonacciho čísla s ; $(P,Q)=(1,-1)$
- Lucas čísla s ; $(P,Q)=(1,-1)$
tribonacciho čísla vyhovující . ${\displaystyle x_{n}=x_{n-1}+x_{n-2}+x_{n-3))$

Obecný termínový vzorec

Pro lineární rekurentní posloupnosti existuje vzorec vyjadřující společný člen posloupnosti z hlediska kořenů jejího charakteristického polynomu

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

Jmenovitě je běžný termín vyjádřen jako lineární kombinace sekvencí formuláře $d$

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

kde je kořen charakteristického polynomu a je nezáporné celé číslo menší než násobek . $\lambda_k$ $m$ $\lambda_k$

Pro Fibonacciho čísla je takovým vzorcem Binetův vzorec .

Příklad

Chcete-li najít vzorec pro společný člen sekvence splňující lineární rekurentní rovnici druhého řádu s počátečními hodnotami , je třeba vyřešit charakteristickou rovnici $F_{n}$ ${\displaystyle F_{n}=b\cdot F_{n-1}+c\cdot F_{n-2))$ $F_{1}$ $F_{2}$

q^{2}-bq-c=0

Pokud má rovnice dva různé nenulové kořeny a , pak pro libovolné konstanty a , posloupnost $q_{1}$ $q_{2}$ $A$ $B$

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

splňuje rekurenční vztah; zbývá najít čísla a to $A$ $B$

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

a .

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

Pokud je diskriminant charakteristické rovnice roven nule a rovnice má tedy jeden kořen , pak pro libovolné konstanty a posloupnost $q_{1}$ $A$ $B$

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

splňuje rekurenční vztah; zbývá najít čísla a to $A$ $B$

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

a .

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

Zejména pro sekvenci definovanou následující lineární rekurentní rovnicí druhého řádu

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

; , .

F_{1}=1

F_{2}=-2

kořeny charakteristické rovnice jsou , . Proto $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}) .

Konečně:

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

Aplikace

Lineární rekurentní sekvence přes zbytkové kruhy se tradičně používají ke generování pseudonáhodných čísel .

Historie

Základy teorie lineárních rekurentních sekvencí podali ve dvacátých letech 18. století Abraham de Moivre a Daniel Bernoulli . Leonhard Euler to vysvětlil ve třinácté kapitole svého Úvodu do analýzy infinitesimálů (1748). [1] Později Pafnuty Lvovich Chebyshev a ještě později Andrey Andreevich Markov představili tuto teorii ve svých kurzech o počtu konečných diferencí. [2] [3]

Viz také

Poznámky

↑ L. Euler, Úvod do analýzy infinitesimál, díl I, M. - L., 1936, s. 197–218
↑ P. L. Čebyšev, Teorie pravděpodobnosti, přednášky 1879–1880, M. - L., 1936, s. 139–147
↑ A. A. Markov, Počet konečných diferencí, 2. vyd., Odessa, 1910, s. 209–239

Literatura

A. I. Markuševič . návratové sekvence . - Paní. Nakladatelství technické a teoretické literatury, 1950. - svazek 1. - ( Populární přednášky z matematiky ).
M. M. Glukhov, V. P. Elizarov, A. A. Nechaev. Hlava XXV. Lineární rekurentní posloupnosti // Algebra. - Učebnice. Ve 2 svazcích. - M . : Helios ARV, 2003. - T. 2. - ISBN 8-85438-072-2 .
A. Egorov. Pisot čísla // Kvant . - 2005. - č. 5 . - S. 8-13 .
Chebrakov Yu.V. Kapitola 2.7. Rekurentní rovnice // Teorie magických matic. Vydání TMM-1 . - Petrohrad. , 2010.

Sekvence a řádky
Sekvence	Číselná posloupnost Základní posloupnost Lineární rekurentní sekvence Fibonacciho čísla složená čísla Faktorový Barkerova sekvence sekvence de bruijn
Řádky, základní	Součet řádků Zbytek řady Podmíněná konvergence Střídavé série Vícesekce řádků
Číselné řady ( operace s číselnými řadami )	harmonická řada série Leibniz Řada inverzních čtverců Série recipročních prvočísel Řada Dirichlet série Mercator Řada Grandi 1 - 2 + 3 - 4 + ... 1 + 2 + 3 + 4 + ...
funkční řádky	Taylorova řada série Laurent Fourierova řada Trigonometrické Fourierovy řady trigonometrická řada série Wiener
Jiné typy řádků	Neumannovy řady Řada Puiseux