01NM:Kapitola4: Porovnání verzí

Z WikiSkripta FJFI ČVUT v Praze
Přejít na: navigace, hledání
 
Řádka 1: Řádka 1:
 +
%\wikiskriptum{01NM}
 +
 
\section{Úplný problém vlastních čísel}
 
\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.
 
Úkolem je nalézt v\ sechna vlastní čísla a případně i všechny vlastní vektory dané regulární matice.
Řádka 533: Řádka 535:
 
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)$.
 
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}
 
\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
 

Aktuální verze z 1. 8. 2010, 10:25

PDF [ znovu generovat, výstup z překladu ] Kompletní WikiSkriptum včetně všech podkapitol.
PDF Této kapitoly [ znovu generovat, výstup z překladu ] Přeložení pouze této kaptioly.
ZIPKompletní zdrojový kód včetně obrázků.

Součásti dokumentu 01NM

součástakcepopisposlední editacesoubor
Hlavní dokument editovatHlavní stránka dokumentu 01NMAdmin 1. 8. 201010:22
Řídící stránka editovatDefiniční stránka dokumentu a vložených obrázkůAdmin 7. 9. 201513:47
Header editovatHlavičkový souborKlinkjak 1. 9. 201522:49 header.tex
Kapitola1 editovatFinitní metodyAdmin 1. 8. 201010:24 kapitola1.tex
Kapitola2 editovatIterační metody řešení soustav lineárních algebraických rovnicKlinkjak 3. 9. 201519:49 kapitola2.tex
Kapitola3 editovatČástečný problém vlastních číselAdmin 1. 8. 201010:25 kapitola3.tex
Kapitola4 editovatÚplný problém vlastních číselAdmin 1. 8. 201010:25 kapitola4.tex
Kapitola5 editovatIterační metody řešení rovnice tvaru f(x)=0Admin 1. 8. 201010:25 kapitola5.tex
Kapitola6 editovatIterační metody pro řešení systémů nelineárních algebraických a transcendentních rovnicAdmin 1. 8. 201010:25 kapitola6.tex
Kapitola7 editovatLagrangeova interpolaceAdmin 1. 8. 201010:25 kapitola7.tex
Kapitola8 editovatNumerický výpočet derivaceAdmin 1. 8. 201010:25 kapitola8.tex
Kapitola9 editovatNumerický výpočet integrálu Admin 1. 8. 201010:25 kapitola9.tex

Zdrojový kód

%\wikiskriptum{01NM}
 
\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}