Verze z 6. 3. 2010, 15:27

\section{Úplný problém vlastních čísel} Úkolem je nalézt v\ sechna vlastní čísla a případně i všechny vlastní vektory dané regulární matice. \subsection{Trojúhelníková metoda a LR-algoritmus} \subsubsection{Trojúhelníková metoda} Konstruujeme dvě posloupnosti matic $(L_s)\, (R_s)$ tak, že $L_0$ zvolíme a matice $L_1\, R_1$ získáme z rozkladu matice $AL_0$ na součin dolní trojúhelníkové matice s jedničkami na diagonále a horní trojúhelníkové matice: $AL_0=L_1 R_1$. Předpokládejme, že matice $AL_0$ je silně regulární, aby byl tento rozklad jednoznačný. Dále postupujeme analogicky: \begin{equation} \label{trojuhel} AL_k=L_{k+1} R_{k+1}, \end{equation} přičemž $L_{k+1}$ je dolní trojúhelníková matice s jedničkami na diagonále a $R_{k+1}$ horní trojúhelníková matice.

Za příznivých okolností posloupnost $(L_s)$ konverguje a potom vlastní čísla a vektory matice $A$ najdeme snadno: \begin{tvrz} Nechť posloupnost $(L_s)$ konverguje k matici $L$. Potom konverguje i posloupnost $(R_s)$, a označíme-li $R$ limitní matici této posloupnosti, platí: \begin{enumerate} \item Diagonální prvky matice $R$ jsou vlastní čísla matice $A$. \item Je-li $\vec y$ vlastní vektor matice $R$, potom $L\vec y$ je vlastní vektor matice $A$. \end{enumerate} \begin{proof} Z (\ref{trojuhel}) vyplývá $R_{k+1}=L_{k+1}^{-1} A L_k$, a konverguje-li posloupnost $(L_s)$, potom zřejmě konverguje i posloupnost $(L_s^{-1})$, takže musí konvergovat i posloupnost $(R_s)$. Zlimicením tohoto vztahu dostaneme $R=L^{-1} A L$. \begin{enumerate} \item Poslední rovnost znamená, že matice $R$ je podobná matici $A$, a tudíž má stejná vlastní čísla. Protože všechny členy posloupnosti $(R_s)$ jsou horní trojúhelníkové matice, musí být podle definice \ref{poslvek} matice $R$ též horní trojúhelníková a vlastními čísly trojúhelníkové matice jsou její diagonální prvky. \item Platí $R\vec y^{(i)}=\lambda_i \vec y^{(i)}$, ale $R=L^{-1} A L$, takže $AL\vec y^{(i)}=\lambda_i L \vec y^{(i)}$. \end{enumerate} \end{proof} \end{tvrz} \subsubsection{LR-algoritmus} Konstruujeme tři posloupnosti matic $(A_s)\, (\bar L_s)\, (\bar R_s)$ tak, že položíme $A_1=A$ a matice $\bar L_1\, \bar R_1$ získáme z rozkladu matice $A_1$ na součin dolní trojúhelníkové matice s jedničkami na diagonále a horní trojúhelníkové matice: $A_1=\bar L_1 \bar R_1$. Předpokládejme, že matice $A$ je silně regulární, aby byl tento rozklad jednoznačný. Matici $A_2$ získáme takto: $A_2=\bar R_1 \bar L_1$. Dále postupujeme analogicky: \begin{equation} \label{eler} A_{k+1}=\bar R_k \bar L_k\longrightarrow A_{k+1}=\bar L_{k+1} \bar R_{k+1}. \end{equation} Z druhé rovnice v (\ref{eler}) plyne $\bar R_k=\bar L_k^{-1} A_k$. Tento vztah dosadíme do první rovnice tamtéž a máme $A_{k+1}=\bar L_k^{-1} A_k \bar L_k$. To znamená, že všechny matice $A_k$ jsou si podobné. Za příznivých okolností konverguje posloupnost $(A_s)$ k horní trojúhelníkové matici; za méně příznivých alespoň některé prvky matic $A_k$ pod diagonálou konvergují k nule a díky tomu dokážeme vlastní čísla určit i tehdy.

\subsubsection{Odvození vzorců pro rozklad} Buďte $A=(a_{ij})$, \[ L= \left( \begin{matrix} 1\\ l_{21} & 1\\ \vdots & \vdots & \ddots\\ l_{n1} & l_{n2} & \hdots & 1\\ \end{matrix} \right) \, R= \left( \begin{matrix} r_{11} & r_{12} & \hdots & r_{1n}\\ & r_{22} & \hdots & r_{2n}\\ & & \ddots & \vdots\\ & & & r_{nn}\\ \end{matrix} \right) . \] Z rovnosti $A=LR$ dostaneme \[ \begin{array}{ll} a_{ij}=l_{i1} r_{1j}+l_{i2} r_{2j}+\hdots+l_{ii-1} r_{i-1j}+r_{ij} & \text{pro }i\le j\, j\in\hat n,\\ a_{ij}=l_{i1} r_{1j}+l_{i2} r_{2j}+\hdots+l_{ij-1} r_{j-1j}+l_{ij} r_{jj} & \text{pro }i>j\, i\in\hat n \end{array} \] a odtud plyne \[ \begin{array}{rll} r_{ij}= & a_{ij}-(l_{i1} r_{1j}+l_{i2} r_{2j}+\hdots+l_{ii-1} r_{i-1j}) & \text{pro }i\le j\, j\in\hat n,\\ l_{ij}= & \frac{1}{r_{jj}}[a_{ij}-(l_{i1} r_{1j}+l_{i2} r_{2j}+\hdots+l_{ij-1} r_{j-1j})] & \text{pro }i>j\, i\in\hat n. \end{array} \]

Prvky $r_{ij}\, l_{ij}$ je možné zapisovat hned po výpočtu na místa, kde byly předtím prvky $a_{ij}$, a to v pořadí naznačeném ve schématu: \[ \begin{matrix} r_{11} & r_{12} & r_{13} & \hdots & r_{1n} & r_{1n+1} & \leftarrow & \text{1. krok}\\ %\cline{1-6}\\ %% TOTO NEJAK NEFUNGUJE - l_{21} & r_{22} & r_{23} & \hdots & r_{2n} & r_{2n+1} & \leftarrow & \text{3. krok}\\ %\cline{2-6}\\ %% l_{31} & l_{32} \\ \vdots & \vdots \\ l_{n1} & l_{n2} \\ \uparrow & \uparrow \\ \text{2. krok} & \text{4. krok} \end{matrix} \] \begin{remark}[porovnání metod] \begin{enumerate} \item Rychlost obou metod je stejná. \item Trojúhelníková metoda má na rozdíl od LR-algoritmu samoopravnou schopnost, neboť matici $L_0$ lze volit téměř libovolně (dokonce nemusí být ani trojúhelníková). \item Trojúhelníková metoda má větší paměťové nároky: Jsou potřeba dvě pole o rozměrech $n\times n$ (v jednom musí být po celou dobu uložena matice soustavy). U LR-algoritmu stačí jediné pole o rozměrech $n\times n$. Je-li matice soustavy např. tridiagonální, potom může mít toto pole rozměry dokonce jen $3\times n$. \end{enumerate} \end{remark} \subsubsection{Konvergence} \begin{tvrz} \label{tvrokonv} Nechť je matice $A^sL_0$ silně regulární a buď $A^sL_0=\mathcal L_s\mathcal R_s$ její rozklad na dolní trojúhelníkovou matici s jedničkami na diagonále $\mathcal L_s$ a horní trojúhelníkovou matici $\mathcal R_s$. Potom platí \[ \mathcal L_s=L_s, \mathcal R_s=R_s\hdots R_1, \] kde $L_s$, resp. $R_s$ jsou příslušné členy posloupností matic $(L_k)$, resp. $(R_k)$ v trojúhelníkové metodě. \begin{proof} Podle (\ref{trojuhel}) platí $A^sL_0=A^{s-1}AL_0=A^{s-1}L_1R_1=A^{s-2}AL_1R_1=$\linebreak[4]$=A^{s-2}L_2R_2R_1=\hdots=L_sR_s\hdots R_2R_1$. Tvrzení vyplývá z jednoznačnosti rozkladu. \end{proof} \end{tvrz}

\begin{tvrz} Buďte \begin{enumerate} \item matice $A^s$ silně regulární, \item $(L_k)\, (R_k)$ posloupnosti matic z trojúhelníkové metody při volbě $L_0=I$, \item $(\bar L_k)\, (\bar R_k)$ posloupnosti matic z LR-algoritmu. \end{enumerate} Potom platí $L_s=\bar L_1\hdots\bar L_s\, R_s=\bar R_s$. \begin{proof} Podle (\ref{eler}) je \[ A^s=\underbrace{A_1\hdots A_1}_{s\text{-krát}}=\bar L_1\underbrace{\bar R_1\bar L_1}_{A_2}\bar R_1\hdots\bar L_1\underbrace{\bar R_1\bar L_1}_{A_2}\bar R_1= \] \[ =\bar L_1\bar L_2\underbrace{\bar R_2\bar L_2}_{A_3}\bar R_2\hdots\bar L_2\underbrace{\bar R_2\bar L_2}_{A_3}\bar R_2\bar R_1=\hdots=\bar L_1\hdots\bar L_s\bar R_s\hdots\bar R_1. \] Položíme-li v důkazu předchozího tvrzení $L_0=I$, vyplyne tvrzení opět z jednoznačnosti rozkladu. \end{proof} \end{tvrz} \begin{dusl} \label{trojLR} Konverguje-li trojúhelníková metoda při volbě $L_0=I$, potom posloupnost $(A_s)$ v LR-algoritmu konverguje k horní trojúhelníkové matici. \begin{proof} Podle předchozího tvrzení je $L_s=L_{s-1}\bar L_s\, R_s=\bar R_s$. Odtud $A_s=\bar L_s\bar R_s=L_{s-1}^{-1} L_s R_s$. Podle předpokladu je $L_s\rightarrow L\, R_s\rightarrow R$, a tak $A_s\rightarrow R$. \end{proof} \end{dusl} Od této chvíle budeme předpokládat, že matice $A$ má vlastní čísla $\lambda_1\, \hdots\, \lambda_n$, přičemž algebraická i geometrická násobnost každého z těchto vlastních čísel je stejná, a že platí \begin{equation} \label{vlc} \abs{\lambda_1}\ge\abs{\lambda_2}\ge\hdots\ge\abs{\lambda_n}. \end{equation} Podle Jordanovy věty je tedy matice $A$ podobná diagonální matici \[ D=\left( \begin{matrix} \lambda_1\\ & \ddots\\ & & \lambda_n \end{matrix} \right), \] tj. existuje taková regulární matice $X$, že platí $A=XDX^{-1}$. Toto značení si rovněž podržme až do konce kapitoly.

Nyní rozebereme tři případy. U prvních dvou se budeme soustředit na trojúhelníkovou metodu --- z předchozího důsledku je zřejmé, že konverguje-li tato metoda, konverguje i LR-algoritmus. V posledním případě trojúhelníková metoda nekonverguje, a proto se omezíme na popis chování LR-algoritmu. Napřed si ještě vyslovíme důležitou lemmu. \begin{lemma} \label{lerozklad} Buď $A$ matice tvaru $A=I+F$ a nechť $\nor F$ je dostatečně malá. Potom existuje dolní trojúhelníková matice $L$ s jedničkami na diagonále a horní trojúhelníková matice $R$ tak, že $A=LR$, a platí $L\rightarrow I\, R\rightarrow I$ pro $\nor F\rightarrow 0$. \begin{proof} Bez důkazů uveďme, že jsou-li $L=(l_{ij})\, D=(d_{ij})\, R=(r_{ij})$ matice z trojúhelníkového rozkladu matice $A$, protom platí \[ l_{ij}=\frac{\det A_{ij}}{\det A_{ii}}\; (j<i)\, d_{ij}=\frac{\det A_{ii}}{\det A_{i-1i-1}}\; (j=i)\, r_{ij}=\frac{\det A_{ij}}{\det A_{jj}}\; (j>i), \] kde $A_{ij}$ je matice, která vznikne z $A$ v případě $i\le j$ vynecháním řádků $i+1\, \hdots\, n$ a sloupců $i\, i+1\, \hdots\, j-1\, j+1\, \hdots\, n$ a v případě $i>j$ vynecháním řádků $j\, j+1\, \hdots\, i-1\, i+1\, \hdots\, n$ a sloupců $j+1\, \hdots\, n$. Z definice determinantu je zřejmé, že jde o spojité funkce proměnných $a_{ij}$ (jsou to racionální funkce, tj. podíly polynomů a ,,polynom je ta nejspojitější funkce, jaká může bejt"). To znamená, že má-li matice $A$ rozklad, potom má rozklad i matice $B$, která se ,,příliš neliší" od $A$, a rozklad této matice $B$ se ,,příliš neliší" od rozkladu matice $A$. \end{proof} \end{lemma} \begin{tvrz} \label{trko1} \begin{enumerate} \item Nechť jsou všechna vlastní čísla matice $A$ jednoduchá a různá co do absolutních hodnot (tj. všechny nerovnosti v (\ref{vlc}) jsou ostré). \item Nechť jsou obě matice $X\, X^{-1}L_0$ silně regulární. \end{enumerate} Potom trojúhelníková metoda konverguje. \begin{proof} Podle předpokladu existuje jednoznačný rozklad $X^{-1}L_0=L_YR_Y$, kde $L_Y$ je dolní trojúhelníková matice s jedničkami na diagonále a $R_Y$ horní trojúhelníková matice. Proto platí \begin{equation} \label{anas} A^sL_0=XD^sX^{-1}L_0=XD^sL_YR_Y=XD^sL_YD^{-s}D^sR_Y, \end{equation} kde $D^{-s}$ je zkrácené označení matice $(D^{-1})^s$ --- tato matice určitě existuje, neboť předpokládáme, že matice $A$ je regulární. Zkoumejme matici $D^sL_YD^{-s}$: S využitím vět \ref{maticetrojsouc} a \ref{maticetrojinv} dostáváme \[ [D^sL_YD^{-s}]_{ij}= \begin{cases} 0 & j>i, \\ 1 & j=i, \\ \left[L_Y\right]_{ij}\left(\frac{\lambda_i}{\lambda_j}\right)^s & j<i. \end{cases} \] Z předpokladu 1 vyplývá, že pro $i>j$ je $\abs{\frac{\lambda_i}{\lambda_j}}<1$, takže prvky pod diagonálou konvergují k nule, a proto můžeme psát $D^sL_YD^{-s}=I+F_s$, kde $F_s$ je dolní trojúhelníková matice s nulami na diagonále. Tento vztah dosadíme do (\ref{anas}) a zároveň provedeme rozklad $X=L_XR_X$, kde $L_X$ je dolní trojúhelníková matice s jedničkami na diagonále a $R_X$ horní trojúhelníková matice. Dostaneme \[ A^sL_0=L_XR_X(I+F_s)D^sR_Y=L_X(R_X+R_XF_s)D^sR_Y=L_X(I+R_XF_sR_X^{-1})R_XD^sR_Y. \] Označme $G_s=R_XF_sR_X^{-1}$. Protože $F_s\stackrel{s\rightarrow\infty}{\longrightarrow}O$, je i $G_s\stackrel{s\rightarrow\infty}{\longrightarrow}O$ a pro vysoká $s$ existuje podle lemmy \ref{lerozklad} rozklad \[ I+G_s=(I+L_G^{(s)})(I+R_G^{(s)}), \] kde $L_G^{(s)}$ je dolní trojúhelníková matice s nulami na diagonále, $L_G^{(s)}\stackrel{s\rightarrow\infty}{\longrightarrow}O$, a $R_G^{(s)}$ je horní trojúhelníková matice, $R_G^{(s)}\stackrel{s\rightarrow\infty}{\longrightarrow}O$. Získali jsme vztah \[ A^sL_0=L_X(I+L_G^{(s)})(I+R_G^{(s)})R_XD^sR_Y. \] To je ovšem rozklad matice $A^sL_0$ na součin dolní trojúhelníkové matici s jedničkami na diagonále a horní trojúhelníkové matice. Protože je tento rozklad za daných předpokladů jednoznačný, musí podle tvrzení \ref{tvrokonv} platit $L_X(I+L_G^{(s)})=L_s$, kde $L_s$ je příslušná matice z posloupnosti $(L_k)$ v trojúhelníkové metodě. Zlimicením tohoto vztahu dostaneme $L_s\rightarrow L_X$, tj. trojúhelníková metoda konverguje. \end{proof} \end{tvrz} \begin{remark}[důsledky důkazu] \begin{enumerate} \item Z důkazu předchozího tvrzení vyplývá existence takového $p\in\N$, že jsou-li matice $AL_0\, AL_1\, \hdots\, AL_p$ silně regulární, potom je zaručena existence rozkladu (\ref{trojuhel}) matic $AL_{p+1}\, AL_{p+2}\, \hdots$ \item Rychlost konvergence závisí na rychlosti konvergence $\left(\frac{\lambda_i}{\lambda_j}\right)^s\rightarrow 0\, i>j$, tj. konvergence je tím rychlejší, čím více se liší absolutní hodnoty vlastních čísel matice $A$. \item Vlastní čísla budou na diagonále limitní matice posloupnosti $(R_s)$ z trojúhelníkové metody srovnána podle velikosti. \end{enumerate} \begin{proof} Dokážeme poslední tvrzení: Podle (\ref{trojuhel}) platí $R_s=L_s^{-1}AL_{s-1}$. Označíme-li $R$ limitní matici posloupnosti $(R_k)$ v trojúhelníkové metodě, potom zlimicením tohoto vztahu dostaneme \[ R=L_X^{-1}AL_X=L_X^{-1}XDX^{-1}L_X=R_XDR_X^{-1}. \] Tvrzení vyplývá z vět \ref{maticetrojsouc} a \ref{maticetrojinv}. \end{proof} \end{remark} \begin{dusl} Je-li splněn předpoklad 1 tvrzení \ref{trko1} a jsou-li matice $X\, X^{-1}$ silně regulární, potom posloupnost $(A_s)$ v LR-algoritmu konverguje k horní trojúhelníkové matici. \begin{proof} Tvrzení plyne z důsledku \ref{trojLR}. \end{proof} \end{dusl} \begin{tvrz} \begin{enumerate} \item Nechť má matice $A$ jedno vlastní číslo násobné a ostatní její vlastní čísla nechť jsou jednoduchá a různá co do absolutních hodnot, tj. platí $\lambda_r=\lambda_{r+1}=\hdots=\lambda_t$ a jinak všechny nerovnosti v (\ref{vlc}) jsou ostré. \item Nechť jsou matice $X^{-1}L_0\, X\tilde L$ silně regulární (význam matice $\tilde L$ viz důkaz). \end{enumerate} Potom trojúhelníková metoda konverguje. \begin{proof} Podle předpokladu existuje jednoznačný rozklad $X^{-1}L_0=L_YR_Y$, kde $L_Y$ je dolní trojúhelníková matice s jedničkami na diagonále a $R_Y$ horní trojúhelníková matice. Proto opět platí (\ref{anas}) a \[ [D^sL_YD^{-s}]_{ij}= \begin{cases} 0 & j>i, \\ 1 & j=i, \\ \left[L_Y\right]_{ij}\left(\frac{\lambda_i}{\lambda_j}\right)^s & j<i. \end{cases} \] Tentokrát však k nule nekonvergují všechny prvky pod diagonálou, ale pouze ty z nich, které leží ve sloupcích $1\, \hdots\, r-1$ nebo v řádcích $t+1\, \hdots\, n$. Označme $\tilde L$ matici, která vznikne z $D^sL_YD^{-s}$ tak, že prvky, které konvergují k nule, nahradíme nulami. Je tedy $D^sL_YD^{-s}=\tilde L+\tilde F_s$, kde $\tilde F_s\rightarrow O$. Tento vztah dosadíme do (\ref{anas}) a zároveň provedeme rozklad $X\tilde L=L_XR_X$, kde $L_X$ je dolní trojúhelníková matice s jedničkami na diagonále a $R_X$ horní trojúhelníková matice. Dostaneme \[ A^sL_0=X(\tilde L+\tilde F_s)D^sR_Y=X\tilde L(I+\tilde L^{-1}\tilde F_s)D^sR_Y=L_X(I+R_X\tilde L^{-1}\tilde F_sR_X^{-1})R_XD^sR_Y. \] Označme $K_s=R_X\tilde L^{-1}\tilde F_sR_X^{-1}$. Protože $F_s\stackrel{s\rightarrow\infty}{\longrightarrow}O$, je i $K_s\stackrel{s\rightarrow\infty}{\longrightarrow}O$ a pro vysoká $s$ existuje podle lemmy \ref{lerozklad} rozklad \[ I+K_s=(I+L_K^{(s)})(I+R_K^{(s)}), \] kde $L_K^{(s)}$ je dolní trojúhelníková matice s nulami na diagonále, $L_K^{(s)}\stackrel{s\rightarrow\infty}{\longrightarrow}O$, a $R_K^{(s)}$ je horní trojúhelníková matice, $R_K^{(s)}\stackrel{s\rightarrow\infty}{\longrightarrow}O$. Získali jsme vztah \[ A^sL_0=L_X(I+L_K^{(s)})(I+R_K^{(s)})R_XD^sR_Y. \] Stejnou úvahou jako v důkazu tvrzení \ref{trko1} zjistíme, že $L_s\rightarrow L_X$. \end{proof} \end{tvrz} \begin{remark} Vlastní čísla budou na diagonále limitní matice posloupnosti $(R_s)$ z trojúhelníkové metody opět srovnána podle velikosti. \begin{proof} Z (\ref{trojuhel}) vyplývá $R_s=L_s^{-1}AL_{s-1}$. Zlimicením tohoto vztahu dostaneme \[ R=L_X^{-1}XDX^{-1}L_X=L_X^{-1}X\tilde L\tilde L^{-1}D\tilde L\tilde L^{-1}X^{-1}L_X=R_X(\tilde L^{-1}D\tilde L)R_X^{-1}. \] Zkoumejme matici $\tilde L^{-1}D\tilde L$: Matice $D\, \tilde L$ pišme v blokovém tvaru \[ D=\left( \begin{matrix} D_1\\ & \lambda_r I\\ & & D_2 \end{matrix} \right)\, \tilde L=\left( \begin{matrix} I\\ & L^+\\ & & I \end{matrix} \right), \] kde $L^+$ je dolní trojúhelníková matice řádu $t-r+1$. Potom platí \[ \tilde L^{-1}D\tilde L=\left( \begin{matrix} I\\ & L^+\\ & & I \end{matrix} \right)^{-1}\left( \begin{matrix} D_1\\ & \lambda_r I\\ & & D_2 \end{matrix} \right)\left( \begin{matrix} I\\ & L^+\\ & & I \end{matrix} \right)=\left( \begin{matrix} D_1\\ & \lambda_r I\\ & & D_2 \end{matrix} \right)=D, \] takže $R=R_XDR_X^{-1}$ a tvrzení opět vyplývá z vět \ref{maticetrojsouc} a \ref{maticetrojinv}. \end{proof} \end{remark} Poslední případ rozebereme slovně. \begin{enumerate} \item Nechť v (\ref{vlc}) platí $\abs{\lambda_r}=\abs{\lambda_{r+1}}=\hdots=\abs{\lambda_t}$ a ostatní nerovnosti jsou ostré. \item Nechť jsou matice $X\, X^{-1}$ silně regulární. \item Nechť $\forall s\in\N$ existuje rozklad $X\tilde L_s=L_s^* R_s^*$ a prvky matic $L_s^*\, R_s^*$ jsou omezené nezávisle na $s$ (význam matic $\tilde L_s$ viz dále). \item Nechť $\forall s\in\N$ existuje rozklad $R_{22}L_s^+=\hat L_s\hat R_s$ (význam matic $R_{22}\, L_s^+$ viz dále). \end{enumerate} Jak jsme předeslali, trojúhelníková metoda v tomto případě nekonverguje, a proto se omezíme na popis chování LR-algoritmu. Ten sice také nekonverguje, ale konvergovat budou alespoň některé prvky matic $(A_s)$.

Proveďme rozklad $X^{-1}=L_YR_Y$. Potom \begin{equation} \label{slovne} A^s=XD^sX^{-1}=XD^sL_YR_Y=XD^sL_YD^{-s}D^sR_Y \end{equation} a pro prvky matice $D^sL_YD^{-s}$ opět platí \[ [D^sL_YD^{-s}]_{ij}= \begin{cases} 0 & j>i, \\ 1 & j=i, \\ \left[L_Y\right]_{ij}\left(\frac{\lambda_i}{\lambda_j}\right)^s & j<i. \end{cases} \] Posloupnost $\left(\frac{\lambda_i}{\lambda_j}\right)^s$ je pro $i\, j\in\{r\, r+1\, \hdots\, t\}\, i>j$ zřejmě divergentní --- členy posloupnosti ,,se točí" v jednotkové kružnici. Ostatní prvky pod diagonálou však konvergují k nule, a tak můžeme tentokrát psát $D^sL_YD^{-s}=\tilde L_s+\tilde F_s$, kde $\tilde F_s\rightarrow O$. Matice $\tilde L_s=D^s\tilde LD^{-s}$ je dolní trojúhelníková s jedničkami na diagonále a všechny její mimodiagonální prvky mají stejnou absolutní hodnotu (matice $\tilde L$ má stejný význam jako v důkazu předchozího tvrzení). Předchozí vztah dosadíme do (\ref{slovne}) a provedeme rozklad podle bodu 3: \[ A^s=X(\tilde L_s+\tilde F_s)D^sR_Y=X\tilde L_s(I+\tilde L_s^{-1}\tilde F_s)D^sR_Y=L_s^*R_s^*(I+\tilde L_s^{-1}\tilde F_s)D^sR_Y= \] \[ =L_s^*(I+R_s^*\tilde L_s^{-1}\tilde F_sR_s^{*-1})R_s^*D^sR_Y. \] Označme $G_s=R_s^*\tilde L_s^{-1}\tilde F_sR_s^{*-1}$. Protože $F_s\stackrel{s\rightarrow\infty}{\longrightarrow}O$, je i $G_s\stackrel{s\rightarrow\infty}{\longrightarrow}O$ a pro vysoká $s$ existuje podle lemmy \ref{lerozklad} rozklad \[ I+G_s=(I+L_G^{(s)})(I+R_G^{(s)}), \] kde $L_G^{(s)}$ je dolní trojúhelníková matice s nulami na diagonále, $L_G^{(s)}\stackrel{s\rightarrow\infty}{\longrightarrow}O$, a $R_G^{(s)}$ je horní trojúhelníková matice, $R_G^{(s)}\stackrel{s\rightarrow\infty}{\longrightarrow}O$. Získali jsme vztah \[ A^s=L_s^*(I+L_G^{(s)})(I+R_G^{(s)})R_s^*D^sR_Y. \] Proveďme rozklad matice $A^s=\mathcal L_s\mathcal R_s$, kde $\mathcal L_s$ je dolní trojúhelníková matice s jedničkami na diagonále a $\mathcal R_s$ horní trojúhelníková matice. Z jednoznačnosti tohoto rozkladu vyplývá $\mathcal L_s=L_s^*(I+L_G^{(s)})$, takže pro vysoká $s$ je $\mathcal L_s\approx L_s^*$ (posloupnost $(L_k^*)$ nemusí konvergovat, proto nepíšeme $\mathcal L_s\rightarrow L_s^*$). Dále víme, že podle (\ref{eler}) je \[ A_{s+1}=\bar L_s^{-1}A_s\bar L_s=\bar L_s^{-1}\hdots\bar L_1^{-1}A_1\bar L_1\hdots\bar L_s=\mathcal L_s^{-1}A_1\mathcal L_s, \] a tak po dosazení $L_s^*$ za $\mathcal L_s$ máme \[ A_{s+1}\approx L_s^{*-1}AL_s^*=L_s^{*-1}XDX^{-1}L_s^*=L_s^{*-1}X\tilde L_s\tilde L_s^{-1}D\tilde L_s\tilde L_s^{-1}X^{-1}L_s^*= \] \[ =L_s^{*-1}L_s^*R_s^*\tilde L_s^{-1}D\tilde L_s R_s^{*-1}L_s^{*-1}L_s^*=R_s^*\tilde L_s^{-1}D\tilde L_s\tilde R_s^{*-1}. \] Zbývá najít vhodné vyjádření matice $R_s^*$. Platí $L_s^*R_s^*=X\tilde L_s=L_XR_X\tilde L_s$. Rozdělme matice z posledního výrazu na bloky \[ L_X=\left( \begin{matrix} L_{11}\\ L_{21} & L_{22}\\ L_{31} & L_{32} & L_{33} \end{matrix} \right)\, R_X=\left( \begin{matrix} R_{11} & R_{12} & R_{13}\\ & R_{22} & R_{23}\\ & & R_{33} \end{matrix} \right)\, \tilde L_s=\left( \begin{matrix} I\\ & L_s^+\\ & & I \end{matrix} \right). \] Potom je \[ L_XR_X\tilde L_s=\left( \begin{matrix} L_{11}\\ L_{21} & L_{22}\\ L_{31} & L_{32} & L_{33} \end{matrix} \right) \left( \begin{matrix} R_{11} & R_{12} & R_{13}\\ & R_{22} & R_{23}\\ & & R_{33} \end{matrix} \right) \left( \begin{matrix} I\\ & L_s^+\\ & & I \end{matrix} \right) = \] \[ =\left( \begin{matrix} L_{11}\\ L_{21} & L_{22}\\ L_{31} & L_{32} & L_{33} \end{matrix} \right) \left( \begin{matrix} R_{11} & R_{12}L_s^+ & R_{13}\\ & R_{22}L_s^+ & R_{23}\\ & & R_{33} \end{matrix} \right). \] Potíž je v tom, že blok $R_{22}L_s^+$ není diagonální. Podle bodu 4 však můžeme provést jeho rozklad $R_{22}L_s^+=\hat L_s\hat R_s$ a odtud \[ L_s^*=L_X\left( \begin{matrix} I\\ & \hat L_s\\ & & I \end{matrix} \right)\, R_s^*=\left( \begin{matrix} I\\ & \hat L_s^{-1}\\ & & I \end{matrix} \right)R_X\tilde L_s. \] Po dosazení dostaneme \[ A_{s+1}\approx\left( \begin{matrix} I\\ & \hat L_s^{-1}\\ & & I \end{matrix} \right) R_X\tilde L_s\tilde L_s^{-1}D\tilde L_s(R_X\tilde L_s)^{-1}\left( \begin{matrix} I\\ & \hat L_s^{-1}\\ & & I \end{matrix} \right)^{-1}= \] \[ =\left( \begin{matrix} I\\ & \hat L_s^{-1}\\ & & I \end{matrix} \right) R_XDR_X^{-1}\left( \begin{matrix} I\\ & \hat L_s\\ & & I \end{matrix} \right) = \] \[ =\left( \begin{matrix} I\\ & \hat L_s^{-1}\\ & & I \end{matrix} \right) \left( \begin{matrix} \tilde R_{11} & \tilde R_{12} & \tilde R_{13}\\ & \tilde R_{22} & \tilde R_{23}\\ & & \tilde R_{33} \end{matrix} \right) \left( \begin{matrix} I\\ & \hat L_s\\ & & I \end{matrix} \right)=\left( \begin{matrix} \tilde R_{11} & \tilde R_{12}\hat L_s & \tilde R_{13}\\ & \hat L_s^{-1}\tilde R_{22}\hat L_s & \hat L_s^{-1}\tilde R_{23}\\ & & \tilde R_{33} \end{matrix} \right), \] kde \[ \tilde R_{11}=\left( \begin{matrix} \lambda_1\\ & \ddots\\ & & \lambda_{r-1} \end{matrix} \right)\, \tilde R_{22}=\left( \begin{matrix} \lambda_r\\ & \ddots\\ & & \lambda_t \end{matrix} \right)\, \tilde R_{33}=\left( \begin{matrix} \lambda_{t+1}\\ & \ddots\\ & & \lambda_n \end{matrix} \right). \] \newline \newline {\bf Shrnutí.} Posloupnost $(A_s)$ se pro vysoká $s$ chová takto: \begin{enumerate} \item Diagonální prvky ve sloupcích $1\, \hdots\, r-1\, t+1\, \hdots\, n$ konvergují k vlastním číslům $\lambda_1\, \hdots\, \lambda_{r-1}\, \lambda_{t+1}\, \hdots\, \lambda_n$ a prvky pod diagonálou v těchto sloupcích konvergují k nule. \item Ve sloupcích $r\, \hdots\, t$ konvergují k nule obecně pouze prvky v řádcích \linebreak[4]$t+1\, \hdots\, n$. \item Zbylá vlastní čísla jsou vlastními čísly submatice, která vznikne z matice $A_s$ vynecháním řádků a sloupců $1\, \hdots\, r-1\, t+1\, \hdots\, n$. \end{enumerate} \begin{remark} Podobná situace nastane, má-li matice $A$ komplexně sdružené dvojice vlastních čísel, tj. existují-li vzájemně různá čísla $k_1\, \hdots\, k_p\in\widehat{n-1}$ tak, že \linebreak[4]$(\forall i\in\hat p)(\lambda_{k_i}=\overline{\lambda_{k_{i+1}}})$ a jinak všechny nerovnosti v (\ref{vlc}) jsou ostré. Potom budou matice $A_s$ pro vysoká $s$ ,,téměř diagonální", ovšem na diagonále budou mít $p$ bločků o rozměrech $2\times 2$, jejichž vlastními čísly budou dvojice $\lambda_{k_i}\, \overline{\lambda_{k_i}}$ $(i\in\hat p)$. \end{remark}

% následující řádky upravují pouze zobrazení stránky na wiki na obsah dokumentu nemají vliv - prosím neměnit ! %\parentlatexfile{01NMskriptum} %\usewikiobsah{01NM:Obsah} %\parentlatexpreamble{01NM:Preamble} .................................. odkaz na hlavičkovou stránku dokumentu, jehož vložení umožní překlad částečného pdf, tj. pdf, které vznikne pouze z této stránky