Secvență liniară recurentă

O secvență liniară recurentă ( recurență liniară ) este orice succesiune numerică definită printr -o relație de recurență liniară : $x_{0},x_{1},\dots$

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

pentru toți

n\geqslant d

cu termeni inițiali dați , unde d este un număr natural fix , sunt dați coeficienți numerici, . În acest caz, numărul d se numește ordinea șirului. $x_{0},\dots,x_{d-1)$ $a_{1},\dots ,a_{d}$ $a_{d}\neq 0$

Secvențele liniare recurente sunt uneori numite și secvențe recurente .

Teoria secvențelor liniare recurente este un analog exact al teoriei ecuațiilor diferențiale liniare cu coeficienți constanți .

Exemple

Cazurile particulare de secvențe liniare recurente sunt secvențele:

Secvențele Lucas satisfăcătoare în special: $x_{n}=P\cdot x_{n-1}-Q\cdot x_{n-2)$
- progresii aritmetice cu ; $(P,Q)=(2,1)$
- progresie geometrică cu ; $Q=0$
- numerele Fibonacci cu ; $(P,Q)=(1,-1)$
- Lucas numere cu ; $(P,Q)=(1,-1)$
numere tribonacci satisfăcătoare . ${\displaystyle x_{n}=x_{n-1}+x_{n-2}+x_{n-3))$

Formula generală a termenului

Pentru secvențele liniare recurente, există o formulă care exprimă termenul comun al secvenței în termeni de rădăcini ale polinomului său caracteristic

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

Și anume, termenul comun este exprimat ca o combinație liniară de secvențe ale formei $d$

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

unde este rădăcina polinomului caracteristic și este un număr întreg nenegativ mai mic decât multiplicitatea lui . $\lambda_k$ $m$ $\lambda_k$

Pentru numerele Fibonacci, o astfel de formulă este formula lui Binet .

Exemplu

Pentru a găsi formula pentru termenul comun al șirului care satisface ecuația recurentă liniară de ordinul doi cu valori inițiale , , ar trebui să rezolvăm ecuația caracteristică $F_{n}$ $F_{n}=b\cdot F_{n-1}+c\cdot F_{n-2)$ $F_{1}$ $F_{2}$

q^{2}-bq-c=0

Dacă ecuația are două rădăcini diferite de zero și , atunci pentru constante arbitrare și , secvența $q_{1}$ $q_{2}$ $A$ $B$

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

satisface relatia de recurenta; rămâne de găsit numerele și asta $A$ $B$

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

și .

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

Dacă discriminantul ecuației caracteristice este egal cu zero și, prin urmare, ecuația are o singură rădăcină , atunci pentru constante arbitrare și , succesiunea $q_{1}$ $A$ $B$

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

satisface relatia de recurenta; rămâne de găsit numerele și asta $A$ $B$

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

și .

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

În special, pentru secvența definită de următoarea ecuație recurentă liniară de ordinul doi

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

; , .

F_{1}=1

F_{2}=-2

rădăcinile ecuației caracteristice sunt , . De aceea $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}) .

In cele din urma:

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

Aplicații

Secvențele liniare recurente peste inelele reziduale sunt utilizate în mod tradițional pentru a genera numere pseudoaleatoare .

Istorie

Fundamentele teoriei secvențelor liniare recurente au fost date în anii douăzeci ai secolului al XVIII-lea de Abraham de Moivre și Daniel Bernoulli . Leonhard Euler a expus-o în capitolul al treisprezecelea din Introducerea sa în analiza infinitezimale (1748). [1] Mai târziu , Pafnuty Lvovich Cebyshev și încă mai târziu Andrey Andreevich Markov au prezentat această teorie în cursurile lor despre calculul diferențelor finite. [2] [3]

Vezi și

Note

↑ L. Euler, Introducere în analiza infinitezimalelor, vol. I, M. - L., 1936, p. 197–218
↑ P. L. Cebyshev, Teoria probabilității, prelegeri 1879–1880, M. - L., 1936, p. 139–147
↑ A. A. Markov, Calculul diferențelor finite, ed. a II-a, Odesa, 1910, p. 209–239

Literatură

A. I. Markusevici . secvențe de returnare . - D-na. Editura de Literatură Tehnică şi Teoretică, 1950. - Vol. 1. - ( Prelegeri populare de matematică ).
M. M. Gluhov, V. P. Elizarov, A. A. Nechaev. Capitolul XXV. Secvențe liniare recurente // Algebră. - Manual. În 2 volume. - M . : Helios ARV, 2003. - T. 2. - ISBN 8-85438-072-2 .
A. Egorov. Numere de pisot // Kvant . - 2005. - Nr 5 . - S. 8-13 .
Cebrakov Yu. V. Capitolul 2.7. Ecuații recurente // Teoria matricelor magice. Lansarea lui TMM-1 . - Sankt Petersburg. , 2010.

Secvențe și rânduri
Secvențe	Succesiunea numerică Secvență fundamentală Secvență liniară recurentă numerele Fibonacci numere ondulate Factorială secvența Barker de bruijn secvenţă
Rânduri, de bază	Suma rândurilor Restul rândului Convergență condiționată Serii alternante Rând multisecțiune
Seria de numere ( operații cu seria de numere )	serie armonică seria Leibniz O serie de pătrate inverse O serie de numere prime reciproce rândul Dirichlet Seria Mercator Row Grandi 1 - 2 + 3 - 4 + ... 1 + 2 + 3 + 4 + ...
rânduri funcționale	Seria Taylor Seria Laurent Seria Fourier Seria Fourier trigonometrică serie trigonometrică Seria Wiener
Alte tipuri de rânduri	Seria Neumann rândul Puiseux