\chyph

\hoffset=-1cm \voffset=-1.2cm \hsize=18cm

\ifx\pdfoutput\undefined \else
\pdfpagewidth=21cm
\pdfpageheight=15cm
\fi

\font\logocvut=lev scaled400

\ifx\zkratka\undefined\edef\zkratka{\jobname}\fi
\def\cislo{8}

\headline={\setfonts[/10]\rm
   \ifnum\pageno>1 
   \hfill {\setfonts[/7] BI-LIN, \zkratka, \cislo, P. Ol��k \quad}\else
   \firstpage\hfill\fi [\the\pageno]}
\footline={}

\def\firstpage{\vbox to0pt{\kern13.7cm\hbox{%
\setfonts[/8] a) \zkratka, \cislo, b) P. Ol��k, FEL �VUT, c) P. Ol��k 2010,
  d) BI-LIN, e) L, f) 2009/2010, g) \lower1pt\hbox{\logocvut L}. 
  Viz p. d. 4/2010
}\vss}}

\input ofs [a35]  %\def\fomenc{CM}  

%\showfonts \end
%\displayfontmessages
\setfonts[NewCentury/17]  \setmath[17/12/8]  
\baselineskip=22pt \normalbaselineskip=\baselineskip

\message{\fontname\tenit}

\medskipamount=9pt
\let\ms=\medskip

\parskip=\medskipamount

\def\n#1\par{\vfill\break}

\def\g#1\par{{\null \vskip-31pt \baselineskip=30pt\setfonts[/23]\bf #1\par}\medskip}
\def\gg#1\par{{\setfonts[/55]\bf #1}\medskip}
\def\hb{\hfil\break}

\def\emerge{{\emergencystretch=2em\par}}

\parindent=0pt

\catcode`\*=13 
\def* {\par \hangindent=15pt \hangafter=1 
   \noindent \hbox to\hangindent {$\bullet$\hss}}

\let\em=\it

\def\C{{\bf C}}
\def\R{{\bf R}}
\def\Q{{\bf Q}}
\def\a{{A}}
\def\A{{\bf A}}
\def\B{{\bf B}}
\def\E{{\bf E}}
\def\P{{\bf P}}
\def\L{{\bf L}}
\def\U{{\bf U}}
\def\X{{\bf X}}
\def\ker{\mathop{\rm Ker}}
\def\st{\mathop{\rm St}}
\def\hod{\mathop{\rm hod}}
\def\vecc #1_#2{\vec#1_1, \vec#1_2, \ldots, \vec#1_{#2}}
\def\lob<#1>{\langle #1\rangle}

% ===============================================================

\vglue 2cm

\gg LU rozklad

\bigskip\bigskip

* $\A = \L\cdot\U$

* n�kdy je t�eba prohodit sloupce/��dky


\n ---------------------------------------------------------------

\g Terminologie

{\bf Definice:} �tvercov� matice je {\em horn� troj�heln�kov�},
pokud m� nenulov� prvky soust�ed�ny jen v horn�m troj�heln�ku, jin�mi
slovy, pokud m� pod diagon�lou jen nulov� prvky.

�tvercov� matice se naz�v� {\em doln� troj�heln�kov�},
pokud m� nenulov� prvky soust�ed�ny v doln�m troj�heln�ku, jin�mi
slovy, pokud m� nad diagon�lou jen nulov� prvky.

{\bf Pozorov�n�:} �tvercovou matici lze p��m�m chodem elimina�n�
metody p�ev�st na horn� troj�heln�kovou matici. Schodovit� �tvercov�
matice je toti� horn� troj�heln�kov�.


\n ---------------------------------------------------------------


\g Na co LU rozklad

Nech� $\A$ je regul�rn� �tvercov� matice. P�edpokl�dejme, �e se poda�� naj�t
doln� troj�heln�kov� matice $\L$ a horn� troj�heln�kov� matice $\U$
tak, �e $\A=\L\cdot\U$. M�me za �kol �e�it soustavu
$$
  \A\cdot{\bf x} = {\bf b}
$$
Nahrad�me v soustav� matici $\A$ sou�inem $\L\cdot\U$ a ozna��me
$\U\cdot{\bf x} = {\bf z}$. Dost�v�me:
$$
  \L\cdot\U\cdot{\bf x} = {\bf b} \quad
  \hbox{pr�v� kdy�}\quad
  \L\cdot{\bf z} = {\bf b}, \quad \U\cdot{\bf x} = {\bf z}.
$$
Nejprve vy�e��me soustavu $\L\cdot{\bf z} = {\bf b}$ dop�ednou
substituc� a potom dosad�me ${\bf z}$ do prav� strany soustavy
$\U\cdot{\bf x} = {\bf z}$, kterou �e��me zp�tnou substituc�.


\n -----------------------------------------------------------------

\g Algoritmus LU rozkladu

Na matici $\A$ prov�d�me jen jeden typ elimina�n� �pravy: p�i�ten�
$\alpha$-n�sobku n�jak�ho ��dku k jin�mu, kter� je naps�n pod n�m.
Tuto �pravu lze \uv{emulovat} n�soben�m zleva matic� $\L_i$, kter�
je jist� doln� troj�heln�kov�.
$$
  \eqalign{
  \A &\sim \A_1 = \L_1\A \sim \A_2 = \L_2(\L_1\A) \sim \cr &\sim
  \A_3 = \L_3(\L_2(\L_1\A)) \sim \cdots \sim \U =
  (\L_k\cdots\L_3\L_2\L_1)\A
}
$$
Sou�in doln�ch troj�heln�kov�ch matic s jedni�kami na diagon�le je
doln� troj�heln�kov� matice s jedni�kami na diagon�le. Inverze doln�
troj�heln�kov� matice s jedni�kami na diagon�le je doln�
troj�heln�kov� matice s jedni�kami na diagon�le. Tak�e:
$$
  \L'\A = \U, \qquad \A = (\L')^{-1}\U = \L\U.
$$

\n -------------------------------------------------------

\g P��klad

$$
  \eqalign{
  &\A = \pmatrix{1&2&3\cr2&3&1\cr4&2&0}
    \sim \pmatrix{1&2&3\cr0&-1&-5\cr0&-6&-12} =
     \pmatrix{1&0&0\cr-2&1&0\cr-4&0&1}\cdot\A
     \sim \cr\noalign{\medskip} &\sim
     \pmatrix{1&2&3\cr0&-1&-5\cr0&0&18} =
     \pmatrix{1&0&0\cr0&1&0\cr0&-6&1}\cdot 
     \pmatrix{1&0&0\cr-2&1&0\cr-4&0&1}\cdot
     \A = \L_2\cdot\L_1\cdot\A
}
$$
$$
  \L\ =\ \L_1^{-1}\cdot\L_2^{-1} =
       \pmatrix{1&0&0\cr2&1&0\cr4&0&1}\cdot
       \pmatrix{1&0&0\cr0&1&0\cr0&6&1} =
       \pmatrix{1&0&0\cr2&1&0\cr4&6&1}
$$
$$
  \U = \pmatrix{1&2&3\cr0&-1&-5\cr0&0&18}
$$

\n ------------------------------------------------------------------

\g Jak vznik� matice L

Plat� $\L =(\L_k\cdots\L_3\L_2\L_1)^{-1} = 
\L_1^{-1}\L_2^{-1}\L_3^{-1}\cdots\L_k^{-1}$. Je:
$$
\L_i^{-1} =  \pmatrix {1&0&\ldots&0&\ldots&0\cr
            0&1&\ldots&0&\ldots&0\cr
             & &\ldots& &\ldots& \cr
            0&0&\ldots&1&\ldots&0\cr
             & &\ldots& &\ldots& \cr
            0&0&\ldots&-\alpha&\ldots&0\cr
             & &\ldots& &\ldots& \cr
            0&0&\ldots&0&\ldots&1},
$$
kde $\alpha_i$ je koeficient elimina�n�ho kroku.
Celkov� sou�in matic 
$\L_1^{-1}\L_2^{-1}\L_3^{-1}\cdots\L_k^{-1}$ (v uveden�m po�ad�)
obsahuje pod diagon�lou na odpov�daj�c�ch m�stech opa�n� hodnoty 
koeficient� v�ech elimina�n�ch krok�, kter� byly v eliminaci provedeny.

\n ------------------------------------------------------------------

\g Jin� p��klad

$$
\A = \pmatrix{1&2&3\cr2&4&1\cr4&2&0}
    \sim \pmatrix{1&2&3\cr0&0&-5\cr0&-6&-12}
$$

Nelze pokra�ovat v eliminaci bez prohozen� ��dk�\dots

\n ------------------------------------------------------------------

\g Probl�m

P�esto�e $\A$ je regul�rn�, m��e se st�t, �e b�hem eliminace se objev�
nulov� diagon�ln� prvek. Klasick� eliminace pak dovoluje prohodit
��dky. To je ale emulov�no n�soben�m zleva permuta�n� matic� 
$\P_{i,j}$, kter� nen� doln� troj�heln�kov�. V�sledn� sou�in emula�n�ch
matic pak nen� doln� troj�heln�kov� matice.

Je tedy t�eba prohodit ��dky matice $\A$ tak, aby nov�
matice $\A'$ tento probl�m nem�la a dala se rozlo�it na $\L\cdot\U$.
Nech�~\ $\P'$ je vhodn� permuta�n� matice. Pak $\P'\cdot\A$ prohazuje
��dky. P�edpokl�dejme:
$$
  \A'=\P'\cdot \A = \L\cdot\U.
$$
Ozna�me $(\P')^{-1} = \P$. To je tak� permuta�n� matice. 
Plat� toti� $(\P')^{-1} = (\P')^T$. S t�mto ozna�en�m dost�v�me
rozklad:
$$
  \A = \P\cdot\L\cdot\U
$$


\n ----------------------------------------------------------------

\g Ot�zka

Nech� $\A$ je regul�rn�.

P�jde v�dy naj�t takov� prohozen� ��dk� matice $\A$, aby pak eliminace
s~jedin�m povolen�m typem operace (p�i�ten� $\alpha$-n�sobku ��dku k
��dku pod n�m) dovedla p�ev�st matici na horn� troj�heln�kovou?

{\bf Odpov��}: Ano. 

Zd�vodn�n�: pokud naraz�me p�i eliminaci na pot�ebu prohodit ��dky,
prohod�me je ve v�choz� matici $\A$ a eliminujeme znovu od za��tku.
Tuto metodu \uv{pokus-omyl} opakujeme tak dlouho, a� se povede matici
$\A$ s prohozen�mi ��dky eliminovat na $\U$. 

\n -----------------------------------------------------------------

\g Praktick� v�po�et LU rozkladu

se samoz�ejm� ned�l� metodou pokus-omyl. Koeficienty elimina�n�ch
krok� n�sob�me $-1$ a ukl�d�me postupn� do matice $\L$, kter� je na
po��tku eliminace jednotkov�. P�i pot�eb�
prohodit ��dky prohod�me tak� ��dky v matici $\L$, ale necel�:
p�i prohazov�n� \hbox{$k$-t�ho} ��dku s $(k+j)$-t�m v eliminovan� matici
prohod�me v matici $\L$ tyt� ��dky, ale jen po sloupec $k-1$.

Dal�� vylep�en� numerick� metody LU rozkladu maj� stejnou slo�itost
jako algoritmus pro maticov� n�soben�.


\n -----------------------------------------------------------------

\g Shrnut�

{\bf V�ta:} Ke ka�d� regul�rn� matici $\A$ existuj� matice:

* $\P$ \dots\ permuta�n� matice,
* $\L$ \dots\ doln� troj�heln�kov� matice s jedni�kami na diagon�le,
* $\U$ \dots\ horn� troj�heln�kov� matice,

tak, �e $\A = \P\cdot\L\cdot\U$.

{\bf Pozn�mka:} p�i v�skytu nulov�ho prvku na diagon�le lze tak� m�sto ��dk�
prohodit sloupce. Pak se permuta�n� matice $\P_{i,j}$ \uv{nem�chaj�} s
maticemi $\L_i$, nebo� n�sob� matici $\A$ zprava. Dost�v�me pak
vzorec: $\A = \L\cdot\U\cdot\P$.

 


\end
