Cesko.wiki Násobení matic
Author
Albert FloresNásobení matic nebo též maticové násobení je v matematice zobecnění násobení čísel na matice. Formálně se dá definovat jako binární operace nad množinou matic. Využívá se v matematice, fyzice a jejich aplikacích pro popis skládání lineárních zobrazení.
Speciálním případem násobení matic je násobení vektoru maticí - jde vlastně o maticové násobení matice o rozměrech n × 1 (sloupcový vektor) zleva maticí o rozměrech m × n, které můžeme interpretovat jako aplikaci lineárního zobrazení reprezentovaného transformační maticí na vektor.
Formální definice
Pokud A je matice o rozměrech m × n a B je matice n × p, jejich součin A \cdot B je matice s rozměry m × p definována vztahem
: (A\cdot B)_{ij} = \sum_{r=1}^n a_{ir}b_{rj} = a_{i1}b_{1j} + a_{i2}b_{2j} + \cdots + a_{in}b_{nj}.
pro všechny prvky (i , j) výsledné matice.
Prvek v i-tém řádku a j-tém sloupci výsledné matice lze také chápat jako skalární součin vektoru i-tého řádku první matice s vektorem j-tého sloupce druhé matice.
Tečka \cdot se obvykle vynechává a píše se pouze AB.
Příklad výpočtu
náhled Mají se znásobit matice:
\mathbf{A}= \begin{pmatrix} \color{blue}1 & \color{blue}2 & \color{blue}3 \\ \color{orange}4 & \color{orange}5 & \color{orange}6 \\ \end{pmatrix},
\mathbf{B}= \begin{pmatrix} \color{red}1 & \color{green}2 \\ \color{red}3 & \color{green}4 \\ \color{red}5 & \color{green}6 \\ \end{pmatrix}. Jejich součin je : \mathbf{A}\cdot\mathbf{B}=\begin{pmatrix} ({\color{blue}1} \cdot {\color{red}1}+{\color{blue}2} \cdot {\color{red}3}+{\color{blue}3} \cdot {\color{red}5}) & ({\color{blue}1} \cdot {\color{green}2}+{\color{blue}2} \cdot {\color{green}4}+{\color{blue}3} \cdot {\color{green}6})\\ ({\color{orange}4} \cdot {\color{red}1}+{\color{orange}5} \cdot {\color{red}3}+{\color{orange}6} \cdot {\color{red}5}) & ({\color{orange}4} \cdot {\color{green}2}+{\color{orange}5} \cdot {\color{green}4}+{\color{orange}6} \cdot {\color{green}6})\\ \end{pmatrix}= \begin{pmatrix} 22 & 28\\ 49 & 64 \end{pmatrix}
:(Tj. prvky matice A zůstávají v řádcích tak, jak jsou, a prvky v matici B se rozmístí opět do levého a pravého sloupce.)
Vlastnosti
Maticové násobení odpovídá skládání lineárních zobrazení, které matice reprezentují. * Maticové násobení je distributivní vůči sčítání, tj. +more \mathbf{A}\cdot\left(\mathbf{B}+\mathbf{C}\right)= \mathbf{A}\cdot\mathbf{B}+\mathbf{A}\cdot\mathbf{C} pro všechny matice, pro které má rovnice smysl. * Násobení reálných resp. komplexních matic je lineární vůči násobení reálným resp. komplexním číslem, tj. \mathbf{A} \cdot \left( c \mathbf{B} \right) = (c \mathbf{A}) \cdot \mathbf{B}=c(\mathbf{A}\cdot\mathbf{B}), pokud má rovnice smysl. * Matice vzhledem k součinu můžou být dělitelé nuly, tj. součin dvou nenulových matic může být nulová matice. * Maticové násobení není komutativní, tedy obecně \mathbf{A} \cdot \mathbf{B} \neq\mathbf{B} \cdot \mathbf{A}. * Násobení matice \mathbf{A} jednotkovou maticí \mathbf{E} zprava i zleva je identické zobrazení, tj. \mathbf{E} \cdot \mathbf{A} = \mathbf{A} \cdot \mathbf{E} = \mathbf{A}, pokud má rovnice smysl. * Maticové násobení je asociativní, tedy \mathbf{A} \cdot (\mathbf{B} \cdot \mathbf{C}) =(\mathbf{A} \cdot \mathbf{B}) \cdot \mathbf{C}, pokud prvky matice jsou z asociativního okruhu (např. reálná nebo komplexní čísla). * Pro čtvercové matice platí \det (\mathbf{A}\cdot\mathbf{B})=\det \mathbf{A}\,\det \mathbf{B}, tj. determinant součinu je součin determinantů. * Transpozice součinu matic je součin transponovaných matic v opačném pořadí, tj. {(\mathbf{A} \cdot \mathbf{B})}^T = \mathbf{B}^T \cdot \mathbf{A}^T * Inverzní matice součinu regulárních matic je součin inverzních matic v opačném pořadí, tj. {(\mathbf{A} \cdot \mathbf{B})}^{-1} = \mathbf{B}^{-1} \cdot \mathbf{A}^{-1} * Hermitovské sdružení součinu matic je součin hermitovsky sdružených matic v opačném pořadí, tj. {(\mathbf{A} \cdot \mathbf{B})}^+ = \mathbf{B}^+ \cdot \mathbf{A}^+.
Výpočetní náročnost
Výpočetní náročnost výše popsaného algoritmu je O( n^3 ) \,\. (počítáme n2 čísel; pro každé potřebujeme n násobení). +more Existují však algoritmy s nižší složitostí vhodné pro matice vyšších řádů. Nejpoužívanější z nich je Strassenův algoritmus se složitostí O( n^{\log_2{7}} ) \approx O(n^{2. 807}) . Nižší složitost u tohoto algoritmu však získáváme za cenu snížené numerické stability. Asymptoticky nejrychlejší ze známých algoritmů je Coppersmithův-Winogradův algoritmus (O( n^{2. 376} ) \,\. ), který je však použitelný až pro matice tak velkých řádů, že je nelze zpracovávat pomocí současných počítačůRobinson, Sara (2005), "[url=http://www. siam. org/pdf/news/174. pdf]Toward an Optimal Algorithm for Matrix Multiplication[/url] ", SIAM News 38 (9), http://www. siam. org/pdf/news/174. pdf .
Teoreticky by se dala složitost ještě zmenšit, ale nikdy nemůže být menší než O( n^2 ) \,\!, neboť počítáme n2 čísel.
Hledání nejkratší cesty v grafu
Algoritmy pro násobení matic s malou výpočetní složitostí lze využít i pro hledání nejkratší cesty v grafu z každého do každého vrcholu. To má v nejjednodušší podobě složitost O( n^3 ) \,\. +more V tomto případě se však nepoužívá zde popsané násobení matic, ale upravená verze, kde je místo sčítání výběr nejmenšího prvku a místo násobení sčítání, proto nelze použít například Strassenův algoritmus, který využívá operaci odčítání jako inverzní operaci ke sčítání, která k operaci \operatorname{min} není.
Graf lze popsat maticí vzdáleností A. Pokud je pro výpočty operace sčítání dvou čísel definována jako jejich minimum, a místo násobení se použije sčítání, je možno matici nejkratších cest B získat jako (A^n) kde n je řád matice vzdáleností. +more Při reálném výpočtu není třeba cyklicky násobit původní maticí, ale vždy se vynásobí vzniklé výsledky - nejkratší cesty jsou získány po log2(n) násobeních. Je-li použit pro násobení algoritmus se složitostí menší než O( \frac{n^3}{\log_2(n)} ) \,\. , složitost hledání cest se tímto postupem sníží.
Odkazy
Reference
Související články
Strassenův algoritmus * Součin * Skalární součin, Vnitřní součin * Vektorový součin, Dvojitý vektorový součin * Smíšený součin * Tenzorový součin, Vnější součin * Hadamardův součin * Matice
Externí odkazy
[url=http://www.umat.feec.vutbr.cz/~novakm/algebra_matic/cz]Lineární algebra: algebra matic[/url] Aplikace, která násobí a sčítá matice zadané uživatelem a zobrazuje postup výpočtu.