\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