Lineární opakující se posloupnost

V matematiky , říkáme lineární opakující se sled objednávky p jakoukoliv sekvenci s hodnotami v komutativním pole K (například ℝ nebo ℂ ; umístíme pouze sebe v tomto případě v tomto článku) je definována pro všechny pomocí lineární vztah opakování formuláře $n \ geq n_ {0}$

{\ displaystyle \ forall n \ geq n_ {0} \ quad u_ {n + p} = a_ {0} u_ {n} + a_ {1} u_ {n + 1} + \ cdots + a_ {p-1} u_ {n + p-1}}

kde , , ... , jsou p skalární sada K ( nenulovou). $a_0$ $a_1$ $a _ {{p-1}}$ $a_0$

Taková sekvence je úplně určen údajů svých p prvních podmínek a ve vztahu opakování.

Lineární rekurentní sekvence řádu 1 jsou geometrické sekvence .

Studium lineárních rekurentních sekvencí vyššího řádu se dostává k problému lineární algebry . Vyjádření obecného pojmu takové posloupnosti je možné za předpokladu, že je schopen faktorizovat polynom, který je s ním spojen, nazývaný charakteristický polynom; charakteristický polynom spojený se sekvencí splňující výše uvedenou relaci opakování je:

P (X) = X ^ {p} - \ sum _ {{i = 0}} ^ {{p-1}} a_ {i} X ^ {i} = X ^ {p} -a _ {{p - 1}} X ^ {{p-1}} - a _ {{p-2}} X ^ {{p-2}} - \ dots -a_ {1} X-a_ {0}.

Jeho stupeň se tedy rovná řádu relace opakování. Zejména v případě sekvencí řádu 2 má polynom 2. stupně, a lze jej tedy faktorizovat pomocí diskriminačního výpočtu . Obecný člen lineárních rekurentních posloupností řádu 2 lze tedy vyjádřit pouze pomocí prvních dvou členů, některých konstantních hodnot, některých základních aritmetických operací (sčítání, odčítání, násobení, exponenciální) a sínusových a kosinových funkcí (pokud pole skaláry je pole skutečností). Jednou ze sekvencí tohoto typu je slavná Fibonacciho sekvence , kterou lze vyjádřit ze sil zahrnujících zlatý řez .

Lineární opakující se posloupnost řádu 1

Lineární rekurentní sekvence řádu 1 jsou geometrické sekvence .

Pokud je relace opakování , obecný termín je . ${\ displaystyle u_ {n + 1} = qu_ {n}}$ ${\ displaystyle u_ {n} = u_ {n_ {0}} q ^ {n-n_ {0}}}$

Lineární opakující se posloupnost řádu 2

a a b jsou dva pevné skaláry K s b ne nula, relace rekurence je

{\ displaystyle u_ {n + 2} = au_ {n + 1} + bu_ {n} \ quad (R).}

Skaláry r tak, aby posloupnost splňovala $($ $R$ $),$ jsou řešením kvadratické rovnice . Polynom se pak nazývá charakteristický polynom posloupnosti. Je to diskriminační . Poté bude nutné rozlišit několik případů podle počtu kořenů charakteristického polynomu. ${\ displaystyle (r ^ {n}) _ {n \ in \ mathbb {N}}}$ ${\ displaystyle r ^ {2} -ar-b = 0}$ ${\ displaystyle X ^ {2} -aX-b}$ ${\ displaystyle \ Delta = a ^ {2} + 4b}$

Věta - Obecný pojem posloupnosti s hodnotami v K a vyhovující ( R ) je:

$\ lambda r_ {1} ^ {n} + \ mu r_ {2} ^ {n}$ jestliže a jsou dva odlišné kořeny (v K ) polynomu , $r_1$ $r_2$ $X ^ {2} -aX-b$
$(\ lambda + \ mu n) r_ {0} ^ {n}$ pokud je dvojitý kořen polynomu , $r_ {0}$ $X ^ {2} -aX-b$

s parametry v K určenými prvními dvěma hodnotami v pořadí. $\ lambda, \ mu$

Případ 1 nastává například tehdy a v případě, že diskriminující je přísně pozitivní, nebo zda a . Kromě toho, pokud jsou dva kořeny polynomu dva konjugované komplexy a pak je také napsán obecný termín takové posloupnosti: ${\ displaystyle K = \ mathbb {R}}$ ${\ displaystyle \ Delta = a ^ {2} + 4b}$ ${\ displaystyle K = \ mathbb {C}}$ ${\ displaystyle \ Delta \ neq 0}$ $r_ {1}, r_ {2}$ $X ^ {2} -aX-b$ ${\ displaystyle \ rho \ mathrm {e} ^ {\ mathrm {i} \ theta}}$ ${\ displaystyle \ rho \ mathrm {e} ^ {- \ mathrm {i} \ theta}}$

${\ displaystyle \ rho ^ {n} (A \ cos (n \ theta) + B \ sin (n \ theta))}$ s parametry A a B v K ( nebo , v závislosti na tom, zda nás zajímají reálné nebo složité sekvence) určené prvními dvěma hodnotami sekvence. ${\ displaystyle = \ mathbb {R}}$ $\ mathbb {C}$

Případ 2 nastane, když je dvojitý kořen . $\ Delta = 0$ ${\ displaystyle r_ {0} = {\ frac {a} {2}}}$

Na obecnosti posloupnosti nic neztrácíme za předpokladu, že tato je definována na všech ℕ a nejen že začíná . Studie posloupnosti $u,$ která je definována pouze z, se ve skutečnosti redukuje na posloupnost $v$ definovanou na ℕ . $n_ {0}$ $n_ {0}$ $v_ {n} = u _ {{n + n_ {0}}}$

Pozoruhodné identity

Pokud posloupnost $u$ vyhovuje

{\ displaystyle \ forall n \ in \ mathbb {N} \ quad u_ {n + 2} = au_ {n + 1} + bu_ {n} \ quad (R)}

poté může být rozšířen na záporné indexy a souvisí s mocnostmi matice (nazývá se doprovodná matice charakteristického polynomu)

{\ displaystyle P: = {\ begin {pmatrix} a & b \\ 1 & 0 \ end {pmatrix}}}

( invertible since $b \neq 0$ ) by:

{\ displaystyle \ forall n \ in \ mathbb {Z} \ quad {\ begin {pmatrix} u_ {n + 1} \\ u_ {n} \ end {pmatrix}} = P ^ {n} {\ begin {pmatrix } u_ {1} \\ u_ {0} \ end {pmatrix}}}

To nám umožňuje ukázat, že pro $objem$ rovná $U$ nebo na jiné sekvence, splňující stejný vztah opakování $( R )$ a pro všechny celá čísla $i$ , $j$ , $k-$ , $l$ a $r$ :

{\ displaystyle i + j = k + l \ Rightarrow u_ {i + r} v_ {j + r} -u_ {k + r} v_ {l + r} = (- b) ^ {r} (u_ {i } v_ {j} -u_ {k} v_ {l})}

Zejména :

{\ displaystyle {\ text {si}} u_ {0} = 0 {\ text {then}} \ quad \ forall m, n, r \ in \ mathbb {Z} \ quad u_ {n} v_ {m + r } -u_ {r} v_ {m + n} = (- b) ^ {r} u_ {nr} v_ {m}}

Opakující se pořadí objednávky $str$

$P-$ dimenzionální vektorový podprostor

Pokud zavoláme relaci opakování: $(R_ {p})$

pro celé číslo n ,

u _ {{n + p}} = a_ {0} u_ {n} + a_ {1} u _ {{n + 1}} + \ cdots + a _ {{p-1}} u _ {{n + p-1}}

a pokud se označují sadu sekvencí s hodnotami v K a uspokojující , je ukázáno, že je podprostor v prostoru sekvencí s hodnotami v K . To je způsobeno linearitou relace opakování. $E _ {{R_ {p}}}$ $(R_ {p})$ $E _ {{R_ {p}}}$

Navíc tento podprostor má rozměr p . Ve skutečnosti existuje izomorfismus vektorových prostorů mezi a : s každou sekvenci $u$ všech , budeme spojovat p -tuplet . Postačuje pak znát volný rodinu o p ověření sekvence , soubor je pak vytvořen tohoto volného rodiny. $E _ {{R_ {p}}}$ $K ^ {p}$ $E _ {{R_ {p}}}$ $(u_ {0}, u_ {1}, \ cdots, u _ {{p-1}})$ $(R_ {p})$ $E _ {{R_ {p}}}$

Obecný termín

Hledání obecného výrazu a konkrétních sad se provádí prací na . Ke každé sekvenci přiřadíme sekvenci definovanou $K ^ {p}$ $(u_ {n}) _ {{n \ in \ mathbb {N}}}$ ${\ displaystyle (U_ {n}) _ {n \ in \ mathbb {N}}}$

{\ displaystyle U_ {n} = {\ begin {pmatrix} u_ {n} \\ u_ {n + 1} \\\ vdots \\ u_ {n + p-1} \ end {pmatrix}}.}

Vztah opakování na vyvolá vztah opakování na $(u_ {n}) _ {{n \ in \ mathbb {N}}}$ ${\ displaystyle (U_ {n}) _ {n \ in \ mathbb {N}}}$

U _ {{n + 1}} = AU_ {n}

nebo

A = {\ begin {pmatrix} 0 & 1 & 0 & \ cdots & 0 \\ 0 & 0 & 1 & \ cdots & 0 \\\ vdots & \ ddots & \ ddots & \ cdots & \ vdots \\ 0 & \ cdots & \ cdots & 0 & 1 \\ a_ {0} & a_ {1} & \ cdots & \ cdots & a _ {{p-1}} \ end {pmatrix}}

( A je doprovodná matice charakteristického polynomu posloupnosti).

Obecný člen posloupnosti U je poté určen vztahem

{\ displaystyle U_ {n} = A ^ {n} U_ {0}.}

Zdá se tedy, že problém je u konce. Ale skutečný problém pak spočívá v tom, výpočet ... Dáváme přednost stanovení základu z . $A ^ {n}$ $E _ {{R_ {p}}}$

Hledání základny

Charakteristický polynom z matice A je . Není náhodou, že jej najdeme k charakterizaci ověřovacích sekvencí . $P (X) = X ^ {p} - \ sum _ {{i = 0}} ^ {{p-1}} a_ {i} X ^ {i}$ ${\ displaystyle u = (u_ {n}) _ {n \ in \ mathbb {N}}}$ $R_ {p}$

Označíme f lineární transformaci, která k posloupnosti přidruží posloupnost definovanou . Podmínka „ $u$ splňuje “ má pak za následek P ( f ) ( $u$ ) = 0. Souprava je tedy jádro z P ( f ). V případě, že polynom P je dělená přes K (což je vždy platí, pokud K = ℂ), je psáno , kde jsou kořeny P a jejich příslušné příkazy z opakování. Jádro P ( f ) je potom přímým součtem jader z . Proto je dostatečné najít základnu každého z těchto jader k určení báze . ${\ displaystyle u = (u_ {n}) _ {n \ in \ mathbb {N}}}$ ${\ displaystyle v = (v_ {n}) _ {n \ in \ mathbb {N}}}$ $v_ {n} = u _ {{n + 1}}$ $R_ {p}$ $E _ {{R_ {p}}}$ $P = \ prod _ {{i = 1}} ^ {k} (X-r_ {i}) ^ {{\ alpha _ {i}}}$ ${\ displaystyle r_ {1}, r_ {2}, \ tečky, r_ {k}}$ ${\ displaystyle \ alpha _ {1}, \ alpha _ {2}, \ tečky, \ alpha _ {k}}$ $(f-r_ {i} Id) ^ {{\ alpha _ {i}}}$ $E _ {{R_ {p}}}$

Můžeme ukázat, že jakákoli posloupnost obecných výrazů je prvkem jádra , pokud je stupeň Q přísně menší než . Tato demonstrace se provádí indukcí dne . Protože posloupnosti , pro j = 0 až , tvoří volnou část prvků, posloupnosti , pro j od 0 do a i od 1 do k , tvoří volnou rodinu prvků (dimenze p ), proto základ . Prvky jsou tedy součty posloupností, jejichž obecný člen je se stupněm Q přísně menší než . $Q (n) r_ {i} ^ {n}$ $(f-r_ {i} Id) ^ {{\ alpha _ {i}}}$ $\ alpha_i$ $\ alpha_i$ ${\ displaystyle (n ^ {j} r_ {i} ^ {n}) _ {n \ in \ mathbb {N}}}$ ${\ displaystyle \ alpha _ {i} -1}$ $\ alpha_i$ ${\ displaystyle (n ^ {j} r_ {i} ^ {n}) _ {n \ in \ mathbb {N}}}$ $\ alpha _ {i} -1$ ${\ displaystyle \ alpha _ {1} + \ alpha _ {2} + \ cdots + \ alpha _ {k} = p}$ $E _ {{R_ {p}}}$ $E _ {{R_ {p}}}$ $E _ {{R_ {p}}}$ $Q (n) r_ {i} ^ {n}$ $\ alpha_i$

Vraťte se k opakování 2. řádu

Pokud se charakteristický polynom rozdělí na, pak jsou polynomy Q stupně 0 a prvky jsou sekvence, jejichž obecný termín je . $(X-r_ {1}) (X-r_ {2})$ $E _ {{R_ {2}}}$ $\ lambda _ {1} r_ {1} ^ {n} + \ lambda _ {2} r_ {2} ^ {n}$

Pokud se charakteristický polynom rozdělí na, pak mají polynomy Q stupeň 1 a prvky jsou sekvence, jejichž obecný termín je . $(X-r_ {0}) ^ {2}$ $E _ {{R_ {2}}}$ $(\ lambda _ {1} n + \ lambda _ {2}) r_ {0} ^ {n}$

Poznámky a odkazy

Důkaz viz například kapitola „Afinní opakování řádu 2“ na Wikiversity .
(in) Robert C. Johnson, „ Fibonacciho čísla a matice “ na Durham University ,2009, str. 40 (A.10).
Demonstraci najdete například v odpovídajícím opraveném cvičení na Wikiversity .
Jean-Marie Monier, Algebra a geometrie PC - PSI - PT : Kurzy, metody a opravená cvičení , Dunod ,2008, 5 th ed. ( číst online ) , s. 125.
Ve skutečnosti je tento výsledek pravdivý pouze tehdy , ale případ nulového kořene lze snadno ošetřit posunem indexu. $r_ {i} \ neq 0$

Související články