\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{7} \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\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 Násobení matic \bigskip\bigskip * je asociativní, není komutativní * k regulárním maticím existují inverzní matice \n --------------------------------------------------------------- \g Maticové násobení {\bf Definice:} Pro matice $\A\in\R^{m,n}$ a $\B\in\R^{n,p}$ existuje maticový součin $\A\cdot\B=\C\in\R^{m,p}$ (v tomto pořadí). Jednotlivé prvky součinu $c_{i,k}$ jsou dány vzorcem: $$ c_{i,k} = a_{i,1}b_{1,k}+a_{i,2}b_{2,k}+\cdots+a_{i,n}b_{n,k} = \sum_{j=1}^n a_{i,j}b_{j,k}. $$ {\bf Příklad:} Je-li $\A\in\R^{3,4}$ a $\B\in\R^{4,5}$, pak $\A\cdot\B$ je definováno, ale $\B\cdot\A$ není definováno. {\bf Pozorování:} Aby bylo definováno $\A\cdot\B$, musí mít $\A$ stejný počet sloupců jako má $\B$ řádků. Výsledná matice má tolik řádků, jako má řádků matice $\A$ a tolik sloupců, jako má sloupců matice $\B$. \n --------------------------------------------------------------- \g Příklady násobení $$\pmatrix{1&2&3}\cdot\pmatrix{4\cr5\cr6} = \pmatrix{1\cdot4+2\cdot5+3\cdot6}$$ $$\pmatrix{4\cr5\cr6}\cdot\pmatrix{1&2&3} = \pmatrix{4&8&12\cr5&10&15\cr6&12&18}$$ $$\pmatrix{1&1\cr-1&-1}\cdot\pmatrix{1&1\cr1&1} = \pmatrix{2&2\cr-2&-2}$$ $$\pmatrix{1&1\cr1&1}\cdot\pmatrix{1&1\cr-1&-1} = \pmatrix{0&0\cr0&0}$$ \n ----------------------------------------------------------------- \g Poznatky z předchozích příkladů: * Maticové násobení není komutativní ani pro čtvercové matice * Neplatí pravidlo: součin nenulových matic musí být nenulová matice * Co tedy platí? \dots \n ------------------------------------------------------------------ \g Vlastnosti maticového násobení: * $(\A\cdot\B)\cdot\C = \A\cdot(\B\cdot\C)$ \dots\ asociativní zákon * $(\A+\B)\cdot\C = \A\cdot\C + \B\cdot\C$ \dots\ distributivní zákon * $\C\cdot(\A+\B) = \C\cdot\A + \C\cdot\B$ \dots\ distributivní zákon * $\alpha(\A\cdot\B) = (\alpha\A)\cdot\B = \A\cdot(\alpha\B)$ \dots\ konstanta * $(\A\cdot\B)^T = \B^T\cdot \A^T$ \dots\ transponovaná matice \n ---------------------------------------------------------------- \g Příklad: soustavy lin. rovnic Nechť $\A\in\R^{m,n}$. $$\A\cdot\pmatrix{x_1\cr x_2\cr \vdots\cr x_n} = \pmatrix{b_1\cr b_2\cr \vdots\cr b_m}$$ Toto je soustava lineárních rovnic s $m$ rovnicemi a $n$ neznámými. Stručně zapisujeme: $\A\cdot{\bf x} = {\bf b}$. Matice $\A$ se nazývá {\em matice soustavy}, jednosloupcová matice ${\bf b}$ je {\em vektor pravých stran}. Úkolem je nalézt všechny jednosloupcové matice ${\bf x}$, které vyhovují maticové rovnici. \n ----------------------------------------------------------------- \g Blokové násobení Nechť $\A$ a $\B$ jsou matice sestavené po blocích takto: $$ \A = \pmatrix {\A_{1,1}& \A_{1,2} \cr \A_{2,1} & \A_{2,2}}, \quad \B = \pmatrix {\B_{1,1}& \B_{1,2} \cr \B_{2,1} & \B_{2,2}} $$ Nechť uvedené bloky jsou matice takového typu, že násobení matic $\A_{i,j}\cdot\B_{j,k}$ je definováno pro všechny případy, které se vyskytují v~následujícím vzorci. Pak $$ \A\cdot \B = \pmatrix {\A_{1,1}\cdot\B_{1,1}+ \A_{1,2}\cdot\B_{2,1}&\ \A_{1,1}\cdot\B_{1,2}+ \A_{1,2}\cdot\B_{2,2}\cr \A_{2,1}\cdot\B_{1,1}+ \A_{2,2}\cdot\B_{2,1}&\ \A_{2,1}\cdot\B_{1,2}+ \A_{2,2}\cdot\B_{2,2}} $$ \dots\ analogicky pro jinak vytvořené bloky. Například: $$\A\cdot\pmatrix{\B_1&\B_2&\ldots&\B_p} = \pmatrix{\A\cdot\B_1&\A\cdot\B_2&\ldots&\A\cdot\B_p}$$ \n ----------------------------------------------------------- \g Výpočetní složitost maticového násobení Předpokládejme dvě matice $\A,\B\in\R^{n,n}$. K výpočtu $\A\cdot\B$ (podle definice) potřebujeme $n^3$ operací (násobení dvou čísel). Nedalo by se ušetřit? * {\bf Rekurzivní algoritmus násobení matic:} vychází z blokového násobení. Potřebuje $F(n)$ operací: $$ \eqalign{ F(n) &= 8F(n/2) = 8(8F(n/4)) = 8(8(8F(n/2^3))) = \cr &= \cdots = 8^m F(n/2^m) = 8^mF(1) =\cr &= 8^m = (2^3)^m = 2^{3m} = (2^m)^3 = n^3. } $$ * {\bf Rekurzivní Strassenův algoritmus:} vychází z blokového násobení, ale vystačí si se sedmi součiny. Potřebuje $F(n)$ operací: $$ \eqalign{ F(n) &= 7F(n/2) = 7(7F(n/4)) = 7(7(7F(n/2^3))) = \cr &= \cdots = 7^m F(n/2^m) = 7^mF(1) =\cr &= 7^m = (2^{\log_2 7})^{\log_2 n} = 2^{\log_2 7\,\cdot\,\log_2 n} = n^{\log_2 7} \doteq n^{2{,}807}. } $$ \n ------------------------------------------------------------- \g Strassenův algoritmus $$ \eqalign{ &\X_1 = (\A_1 + \A_4)\cdot(\B_1+\B_4), \cr &\X_2 = (\A_3 + \A_4)\cdot\B_1, \cr &\X_3 = \A_1\cdot(\B_2-\B_4), \cr &\X_4 = \A_4\cdot(\B_3-\B_1), \cr &\X_5 = (\A_1+\A_2)\cdot\B_4, \cr &\X_6 = (\A_3-\A_1)\cdot(\B_1+\B_2), \cr &\X_7 = (\A_2-\A_4)\cdot(\B_3+\B_4) } $$ Dá se ověřit, že platí: $$ \pmatrix{\A_1 &\A_2\cr \A_3&\A_4}\! \cdot\! \pmatrix{\B_1 &\B_2\cr \B_3&\B_4} = \pmatrix{\X_1+\X_4-\X_5+\X_7\ & \X_3+\X_5\cr \X_2+\X_4& \X_1-\X_2+\X_3+\X_6} $$ \n ---------------------------------------------------------------- \g Komutující matice Když platí: $\A\cdot\B = \B\cdot\A$, říkáme, že matice $\B$ komutuje s maticí $\A$. {\bf Pozorování:} Komutovat mohou pouze čtvercové matice stejného typu. {\bf Úloha:} Je pevně dána čtvercová matice $\A$, je třeba najít k ní množinu všech matic $\B$, které komutují s $\A$. {\bf Pozorovaní:} Uvedená množina matic $\B$, které komutují s danou maticí $\A$, tvoří lineární podprostor lineárního prostoru matic $\R^{n,n}$. \n --------------------------------------------------------------- \g Inverzní matice Čtvercovou matici s jedničkami na diagonále a nulami jinde značíme $\E$ a říkáme ji {\em jednotková matice}. {\bf Pozorování:} $\A\cdot\E = \E\cdot\A = \A$, analogie s čísly: $a\cdot1 = 1\cdot a = a$. {\bf Definice:} {\em Inverzí matice\/} ke čtvercové matici $\A$ je taková matice $\B$, pro kterou je $$\A\cdot\B=\B\cdot\A=\E.$$ (viz též analogie s čísly). Invezní matici značíme $\A^{-1}$. {\bf Pozorování:} Pokud k matici $\A$ inverzní matice existuje, pak je určena jednoznačně. Důvod je zde: $$ \B_1 = \E\cdot\B_1 = (\B_2\cdot\A)\cdot\B_1 = \B_2\cdot(\A\cdot\B_1) = \B_2\cdot\E = \B_2 $$ {\bf Otázka:} Jak poznáme existenci inverzní matice k matici $\A$? \n --------------------------------------------------------------- \g Regulární a singulární matice {\bf Definice:} Čtvercová matice je {\em regulární}, pokud má inverzní matici. Čtvercová matice je {\em singulární}, pokud nemá inverzní matici. {\bf Pozorování:} Součin regulárních matic je regulární matice. Má-li matice $\A$ inverzní matici $\A^{-1}$ a dále má-li matice $\B$ inverzní matici $\B^{-1}$, pak inverzní matice k $\A\cdot\B$ je $\B^{-1}\cdot\A^{-1}$. Platí totiž: $$\displaylines{ (\B^{-1}\cdot\A^{-1})\cdot(\A\cdot\B) = \B^{-1}\cdot(\A^{-1}\cdot\A)\cdot\B = \B^{-1}\cdot\E\cdot\B = \B^{-1}\cdot\B = \E, \cr (\A\cdot\B)\cdot(\B^{-1}\cdot\A^{-1}) = \A\cdot(\B\cdot\B^{-1})\cdot\A^{-1} = \A\cdot\E\cdot\A^{-1} = \A\cdot\A^{-1} = \E .} $$ \n ---------------------------------------------------------------- \g Výpočet inverzní matice eliminací {\bf Algoritmus:} Má-li $\A$ lineárně nezávislé řádky, pak existuje $\A^{-1}$ a lze ji vypočítat takto: $$ (\A\,|\,\E) \sim (\E\,|\,\A^{-1}) $$ Ke zdůvodnění této metody potřebujeme zavést tři typy čtvercových matic, které (pokud jimi násobíme vybranou matici zleva) \uv{emulují} jednotlivé kroky eliminační metody. Součin těchto elementárních matic emulující všechny provedené kroky je matice $\P$, pro kterou platí: {\bf Věta:} Je-li $\A\sim\B$, pak existuje regulární $\P$ taková, že $\B=\P\cdot\A$. \n -------------------------------------------------------------- \g Podmínky regularity matice Následující podmínky jsou ekvivalentní s regularitou matice $\A\in\R^{n,n}$: * $\A$ má inverzní matici (viz definice). * Maticová rovnice $\A\cdot\X=\B$ má řešení pro každou $\B\in\R^{n,m}$. * Matice $\A$ má lineárně nezávislé řádky. * $\hod\A=n$. * existuje eliminační proces, který provede $\A\sim\E$. * $\det\A\not=0$ (o determinantech pohovoříme později) \n ----------------------------------------------------------------- \g Hodnost součinu {\bf Věta:} Je-li $\P$ regulární a platí-li $\B=\P\cdot\A$, pak $\A\sim\B$. Důkaz: $\P\sim\E$ a stejné kroky eliminace použijeme na $(\P\,|\,\B)$, tj.: $$ (\P\,|\,\B) = (\P\,|\,\P\cdot\A) \sim (\E\,|\,\X) = \P^{-1}(\P\,|\,\P\cdot\A) = (\E\,|\,\A), $$ takže $\A\sim\B$. {\bf Věta:} Násobíme-li matici $\A$ jakoukoli regulární maticí, nezmění se hodnost. Tedy: $\hod\A = \hod(\P\cdot\A)$. {\bf Věta:} $\hod(\A\cdot\B) \le \min(\hod\A,\hod\B)$ Důkaz\char`\*: $\hod\A=k$, tj. $\A\sim\C$, $\C$ má $k$ nenulových řádků. Existuje tedy $\P$ regulární, že $\A=\P\cdot\C$. Dále platí: $$ \hod(\A\cdot\B) = \hod(\P\cdot\C\cdot\B) = \hod(\C\cdot\B) \le k. $$ \end