msleziak.com

Na konci cvika sme sa pozreli na úlohu:$\newcommand{\inv}[1]{{#1}^{-1}}$

Nájdite $A^{100}$, ak $A=
\begin{pmatrix}
4 & 3 \\
1 & 2
\end{pmatrix}$.

Chceli by sme to vyrátať nejakým spôsobom využívajúcim to, čo vieme o maticiach.

Samozrejme mohli by sme jednoducho počítať matice $A$, $A^2$, $A^3$ atď.
Alebo si to urýchliť tak, že vypočítame:
$A$
$A^2$
$A^3=A^2A$
$A^6=(A^3)^2$
$A^{12}=(A^6)^2$
$A^{24}=(A^{12})^2$
$A^{25}=A^{24}A$
$A^{50}=(A^{25})^2$
$A^{100}=(A^{50})^2$
Exponentiation by squaring - túto metódu som už spomínal tu: viewtopic.php?f=29&t=640

Skúsme sa však pozrieť, čo vieme o matici $A^{100}$ povedať z toho, čo sme sa naučili na lineárnej algebre.

Diagonalizácia

Máme
$\chi_A(x)=\begin{vmatrix}
x-4&-3 \\
-1 &x-2
\end{vmatrix}=x^2-6x+8-3=x^2-6x+5=(x-5)(x-1)$.

Teda vieme, že táto matica je podobná s diagonálnou maticou $D=\operatorname{diag}(1,5)$.

Ak vyrátame vlastné vektory, tak vieme nájsť aj príslušnú maticu prechodu. Dostaneme, že pre maticu $P=
\begin{pmatrix}
1 &-3 \\
1 & 1
\end{pmatrix}$
platí $PA\inv P=D$.

Teda ak označíme $Q=\inv P=\frac14
\begin{pmatrix}
1 & 3 \\
-1 & 1
\end{pmatrix}$
tak máme $A=QD\inv Q$.

Teraz vieme vypočítať pre ľubovoľné $n$
$$A^n=(QD\inv Q)^n=QD^n\inv Q=
\frac14
\begin{pmatrix}
1 & 3 \\
-1 & 1
\end{pmatrix}
\begin{pmatrix}
1 & 0 \\
0 & 5^n
\end{pmatrix}
\begin{pmatrix}
1 &-3 \\
1 & 1
\end{pmatrix}=
\frac14
\begin{pmatrix}
1 & 3\cdot5^n \\
-1 & 5^n
\end{pmatrix}
\begin{pmatrix}
1 &-3 \\
1 & 1
\end{pmatrix}=
\frac14
\begin{pmatrix}
1+3\cdot5^n & -3+3\cdot5^n \\
-1+5^n & 3+5^n
\end{pmatrix}
$$


Lineárna rekurencia
Skúsme iný prístup.
Všimnime si, že platí $A^2-6A+5I=0$. (Podľa Cayley-Hamiltonovej vety).
To znamená, že
$A^2=6A-5I$.

Ak vynásobíme túto rovnicu $A$, dostaneme
$A^3=6A^2-5A=6(6A-5I)-5A=31A-30$

Podobne by sme mohli postupovať ďalej, ľubovoľnú mocninu matica $A$ vieme vyjadriť ako lineárnu kombináciu $A$ a $I$.

Konkrétne ak platí $A^n=a_nA+b_nI$, tak
$A^{n+1}=a_nA^2+b_nA=a_n(6A-5I)+b_nA=(6a_n+b_n)A-5a_nI$.

Zistili sme teda, že pre koeficienty platí:
$a_{n+1}=6a_n+b_n$
$b_{n+1}=-5a_n$

Ak využijeme $b_n=-5a_{n-1}$ a dosadíme to do prvej rovnice, dostaneme
$a_{n+1}=6a_n-5a_{n-1}$.
Je jasné, že ak poznáme hodnoty $a_1$, $a_2$ (alebo $a_0$, $a_1$), tak touto rovnosťou sú už všetky ďalšie hodnoty jednoznačne určené.

Z toho, čo ste sa možno už učili/možno len budete učiť o riešení takýchto rovníc (=lineárnych homogénnych rekurentných rovníc s konštantnými koeficientami) vieme, že stačí nájsť korene charakteristickej rovnice $x^2-6x+5$, čo sú v našom prípade $1$ a $5$. Ak nemáme násobné korene, tak všetky riešenie budú tvaru $c_11^n+c_25^n$, t.j. $$a_n=c_1+c_25^n.$$
Aj ak ste sa o týchto rovniciach zatiaľ neučili nič, tak overiť, že každé takéto riešenie skutočne vyhovuje zadanej rekurencii je pomerne jednoduché. Skúsme ešte, či vieme nájsť $c_1$, $c_2$ tak, aby platilo $a_0=0$, $a_1=1$, $a_2=6$.
Chceme teda
$c_1+c_2=0$
$c_1+5c_2=1$
Z čoho dostaneme $c_2=\frac14$, $c_1=-\frac14$.
Teda $$a_n=\frac14(-1+5^n).$$

Potom dostávame
$$A^n=a_nA+b_nI=a_nA-5a_{n-1}I=
\begin{pmatrix}
4a_n-5a_{n-1} & 3a_n \\
a_n & 2a_n-5a_{n-1}
\end{pmatrix}
$$
Uvedené výrazy môžeme trochu upravovať až kým sa nám nepodarí túto maticu zjednodušiť. Po úprave dostaneme:
$A^n=
\begin{pmatrix}
\frac{1+3\cdot5^n}4 & \frac{-3+3\cdot5^n}4 \\
\frac{-1+5^n}4 & \frac{3+5^n}4
\end{pmatrix}$
Dostali sme ten istý výsledok ako pri predchádzajúcom postupe.

Martin Sleziak wrote: Z toho, čo ste sa možno už učili/možno len budete učiť o riešení takýchto rovníc (=lineárnych homogénnych rekurentných rovníc s konštantnými koeficientami) vieme, že stačí nájsť korene charakteristickej rovnice

Ak si chcete niekde pozrieť nejaké základné veci o lineárnych rekurenciách, tak tu sú nejaké linky:

• Lineární rekurence - Martin Mareš
• Metódy riešenia rekurentných rovníc - Michal Winczer
• Niečo nájdete aj v časti 3.5.1 v tomto texte: http://msleziak.com/vyuka/2014/alg3/alg3.pdf