Maticové násobení

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 10. srpna 2022; kontroly vyžadují 2 úpravy .

Násobení matic je jednou ze základních operací s maticemi . Matice vyplývající z operace násobení se nazývá maticový součin . Prvky nové matice se získají z prvků starých matic podle níže uvedených pravidel .

Matice a lze násobit, pokud jsou kompatibilní v tom smyslu, že počet sloupců matice se rovná počtu řádků . $A$ $B$ $A$ $B$

Matice mají mnoho vlastností algebraického násobení , které mají obyčejná čísla, s výjimkou komutativnosti .

Pro čtvercové matice lze kromě násobení zavést operaci zvýšení matice na mocninu a inverzní matici .

Zatímco matice se používají k popisu zejména transformací matematických prostorů ( rotace , odraz , roztahování a další ), součin matic bude popisovat složení transformací .

Definice

Nechť jsou dány dvě obdélníkové matice a rozměry a : $A$ $B$ $l\times m$ $m\krát n$

A={\begin{bmatrix}a_{11}&a_{12}&\cdots &a_{1m}\\a_{21}&a_{22}&\cdots &a_{2m}\\\vdots &\vdots &\ddots &\vdots \\a_{l1}&a_{l2}&\cdots &a_{lm}\end{bmatrix}},\;\;\;B={\begin{bmatrix}b_{11}&b_{ 12}&\cdots &b_{1n}\\b_{21}&b_{22}&\cdots &b_{2n}\\\vdots &\vdots &\ddots &\vdots \\b_{m1}&b_{m2}& \cdots &b_{mn}\end{bmatrix}}.

Potom matice s rozměry : $C$ $l\times n$

C={\begin{bmatrix}c_{11}&c_{12}&\cdots &c_{1n}\\c_{21}&c_{22}&\cdots &c_{2n}\\\vdots &\vdots &\ddots &\vdots \\c_{l1}&c_{l2}&\cdots &c_{ln}\end{bmatrix}},

kde:

c_{ij}=\sum _{r=1}^{m}a_{ir}b_{rj}\;\;\;\left(i=1,2,\ldots l;\;j =1,2,\ldots n\right).

se nazývá jejich produkt .

Operace násobení dvou matic je proveditelná pouze tehdy, je-li počet sloupců v prvním faktoru roven počtu řádků ve druhém; v tomto případě se říká, že matice jsou konzistentní . Zejména násobení je vždy proveditelné, pokud jsou oba faktory čtvercové matice stejného řádu.

Existence díla tedy vůbec nenavazuje na existenci díla. $AB$ $B.A.$

Ilustrace

Maticový součin AB se skládá ze všech možných kombinací vnitřních součinů řádkových vektorů matice A a sloupcových vektorů matice B . Prvek matice AB s indexy i, j je skalárním součinem i -tého řádkového vektoru matice A a j -tého sloupcového vektoru matice B .

Obrázek vpravo ukazuje výpočet součinu dvou matic A a B , ukazuje, jak každý průsečík v součinu matice odpovídá řádkům matice A a sloupcům matice B. Velikost výsledné matice je vždy maximální možná, to znamená, že pro každý řádek matice A a sloupec matice B je vždy odpovídající průsečík v součinu matice.

Hodnoty na křižovatkách označených kroužky budou:

${\begin{aligned}{\color {Red}x_{1,2}}&=(a_{1,1},a_{1,2})\cdot (b_{1,2},b_{2, 2})\\&=a_{1,1}b_{1,2}+a_{1,2}b_{2,2}\\{\barva {Modrá}x_{3,3}}&=( a_{3,1},a_{3,2})\cdot (b_{1,3},b_{2,3})\\&=a_{3,1}b_{1,3}+a_{ 3,2}b_{2,3}\end{aligned}}$

Obecně platí, že maticový součin není komutativní operace. Například:

{\overset {3\times 4{\text{ matrix))}{\begin{bmatrix}\cdot &\cdot &\cdot &\cdot \\\cdot &\cdot &\cdot &\cdot \\\color {Modrá}1&\barva {Modrá}2&\barva {Modrá}3&\barva {Modrá}4\\\end{bmatrix}}}{\overset {4\times 5{\text{ matrix}}}{\začátek {bmatrix}\cdot &\cdot &\cdot &\color {Červená}a&\cdot \\\cdot &\cdot &\cdot &\color {Červená}b&\cdot \\\cdot &\cdot &\cdot & \color {Red}c&\cdot \\\cdot &\cdot &\cdot &\color {Red}d&\cdot \\\end{bmatrix}}}={\overset {3\times 5{\text{ matrix ))}{\begin{bmatrix}\cdot &\cdot &\cdot &\cdot &\cdot \\\cdot &\cdot &\cdot &\cdot &\cdot \\\cdot &\cdot &\cdot &x_ {3,4}&\cdot \\\end{bmatrix}}}

Prvek součinu výše uvedených matic se vypočítá následovně $x_{{3,4}}$

x_{3,4}=({\color {Blue}1},{\color {Blue}2},{\color {Blue}3},{\color {Blue}4})\cdot ({\color {Červená}a},{\barva {Červená}b},{\barva {Červená}c},{\barva {Červená}d})={\barva {Modrá}1}\cdot {\barva {Červená} a}+{\color {Modrá}2}\cdot {\color {Červená}b}+{\barva {Modrá}3}\cdot {\color {Červená}c}+{\barva {Modrá}4}\ cdot {\color {červená}d}

První souřadnice v označení matice označuje řádek, druhá souřadnice označuje sloupec; toto pořadí se používá jak pro indexování, tak pro dimenzování. Prvek na průsečíku řádku a sloupce výsledné matice je skalárním součinem i -tého řádku první matice a i -tého sloupce druhé matice. To vysvětluje, proč se musí šířka a výška vynásobených matic shodovat: jinak je bodový součin nedefinovaný. $x_{{\color {Blue}i}{\color {Red}j))$ $i$ $j$ $i$ $j$

Diskuse

Důvody pro popsané pravidlo násobení matic je nejsnáze vidět na uvažování násobení vektoru maticí.

Posledně jmenovaný je přirozeně zaveden na základě skutečnosti, že při rozkladu vektorů z hlediska báze dává akce (jakéhokoli) lineárního operátoru A výraz pro složky vektoru v' = A v :

v'_{i}=\sum \limits _{j}A_{ij}v_{j}

To znamená, že lineární operátor je reprezentován maticí, vektory sloupcovými vektory a působení operátoru na vektor maticovým násobením sloupcového vektoru vlevo operátorovou maticí (toto je speciální případ násobení matic, když jedna z matic, sloupcový vektor, má velikost ). $n\times 1$

(Stejně tak přechod na jakoukoli novou bázi při změně souřadnic je reprezentován zcela podobným výrazem, pouze v tomto případě se již nejedná o složky nového vektoru ve staré bázi, ale složky starého vektoru v nové bázi v tomto případě prvky přechodové matice na nový základ). $v'_{i}$ $A_{{ij}}$

Po zvážení sekvenční akce na vektor dvou operátorů: nejprve A a poté B (nebo transformace báze A a poté transformace báze B ), aplikováním našeho vzorce dvakrát, dostaneme:

v''_{i}=\součet \limity _{j}B_{ij}\součet \limits _{k}A_{jk}v_{k}=\součet \limity _{j}\součet \limits _ {k}B_{ij}A_{jk}v_{k}=\součet \limits _{k}\součet \limits _{j}(B_{ij}A_{jk})v_{k},

odkud je vidět, že složení BA působení lineárních operátorů A a B (nebo podobné složení bázových transformací) odpovídá matici vypočítané podle pravidla součinu odpovídajících matic:

(BA)_{ik}=\součet \limits _{j}B_{ij}A_{jk}.

Takto definovaný součin matic se ukazuje jako zcela přirozený a zjevně užitečný (poskytuje jednoduchý a univerzální způsob výpočtu složení libovolného počtu lineárních transformací).

Vlastnosti

Asociativní vlastnost , asociativita :

\mathbf {A} (\mathbf {BC} )=(\mathbf {AB} )\mathbf {C} ;

\alpha (\mathbf {AB} )=(\alpha \mathbf {A} )\mathbf {B} =\mathbf {A} (\alpha \mathbf {B} ).

Distributivní vlastnost , distributivita s ohledem na sčítání :

\mathbf {A} (\mathbf {B} +\mathbf {C} )=\mathbf {AB} +\mathbf {AC} ;

(\mathbf {A} +\mathbf {B} )\mathbf {C} =\mathbf {AC} +\mathbf {BC} .

Součin matice a matice identity vhodného řádu je roven matici samotné: $\mathbf {E}$

\mathbf {EA} =\mathbf {A} ;

\mathbf {AE} =\mathbf {A} .

Součin matice a nulové matice vhodného rozměru se rovná nulové matici: $\mathbf {0}$

\mathbf {0A} =\mathbf {0} ;

\mathbf {A0} =\mathbf {0} .

Jestliže a jsou čtvercové matice stejného řádu, pak maticový součin má řadu dalších vlastností. $\mathbf {A}$ $\mathbf {B}$

Maticové násobení je obecně nekomutativní :

\mathbf {AB} \neq \mathbf {BA} .

Pokud , tak matice a prý spolu pendlují. $\mathbf {AB} =\mathbf {BA}$ $\mathbf {A}$ $\mathbf {B}$

Nejjednodušší příklady matic dojíždění:

libovolná čtvercová matice - sama se sebou: (kvadratura matice); $\mathbf {AA} =\mathbf {AA} =\mathbf {A^{2}}$
jakákoli čtvercová matice — s maticí identity stejného řádu: ; $\mathbf {AE} =\mathbf {EA} =\mathbf {A}$
jakákoli čtvercová matice — s nulovou maticí stejného řádu: ; $\mathbf {A0} =\mathbf {0A} =\mathbf {0}$
jakákoli nesingulární čtvercová matice — s její inverzní maticí: . $\mathbf {AA^{-1}} =\mathbf {A^{-1}A} =\mathbf {E}$

Determinant a stopa produktu nezávisí na pořadí násobení matrice:

\det(\mathbf {AB} )=\det(\mathbf {BA} )=\det \mathbf {A} \cdot \det \mathbf {B} ;

{\mbox{tr}}(\mathbf {AB} )={\mbox{tr}}(\mathbf {BA} ).

Inverzní matice

Čtvercová matice se nazývá nesingulární ( nesingulární ) , pokud má jedinečnou inverzní matici tak, že je splněna následující podmínka: $A$ $A^{{-1}}$

AA^{-1}=A^{-1}A=E.

Jinak se matrice nazývá speciální ( degenerovaná ) . $A$

Matice řádu je nedegenerovaná právě tehdy, když v tomto případě existuje čtvercová matice stejného řádu $A=\left[a_{ik}\right]$ $n$ $\det A=\det \left[a_{ik}\right]\neq 0;$ $A^{{-1}}$ $n:$

A^{-1}=\left[a_{ik}\right]^{-1}=\left[{\frac {A_{ki}}{\det A}}\right],

kde je algebraický doplněk prvku v determinantu $A_{{ik}}$ $a_{{ik}}$ $\det\left[a_{ik}\right].$

Rychlé algoritmy násobení matic

Složitost výpočtu součinu matic podle definice je , ale existují efektivnější algoritmy [1] , které se používají pro velké matice. Otázka mezní rychlosti násobení velkých matic, stejně jako otázka konstrukce nejrychlejších a nejstabilnějších praktických algoritmů pro násobení velkých matic, zůstává jedním z nevyřešených problémů lineární algebry . $\O(n^{3})$

Strassenův algoritmus (1969)

První algoritmus pro rychlé násobení velkých matic byl vyvinut Volkerem Strassenem [2] v roce 1969. Algoritmus je založen na rekurzivním rozdělení matic do bloků 2X2 . Strassen dokázal, že matice 2X2 lze nekomutativně násobit sedmi násobeními, takže se v každém kroku rekurze provádí sedm násobení místo osmi. V důsledku toho je asymptotická složitost tohoto algoritmu . Nevýhodou této metody je větší složitost programování oproti standardnímu algoritmu, špatná numerická stabilita a větší množství použité paměti. Byla vyvinuta řada algoritmů založených na Strassenově metodě, které zlepšují numerickou stabilitu, konstantní rychlost a další charakteristiky. Nicméně díky své jednoduchosti zůstává Strassenův algoritmus jedním z praktických algoritmů pro násobení velkých matic. Strassen také předložil následující Strassenovu domněnku : pro libovolně malý existuje algoritmus, který pro dostatečně velká přirozená čísla n zaručuje násobení dvou matic velikosti v operacích.

O(n^{\log _{2}7})\přibližně O(n^{2,81})

\varepsilon >0

n\krát n

O(n^{2+\varepsilon })

Další vylepšení exponentu ω pro rychlost násobení matic

V budoucnu byly odhady míry násobení velkých matic mnohonásobně zlepšeny. Tyto algoritmy však byly teoretické, většinou přibližné. Vzhledem k nestabilitě přibližných násobicích algoritmů se v současné době v praxi nepoužívají.

Pan's Algorithm (1978)

V roce 1978 Pan [3] navrhl vlastní metodu násobení matic, jejíž složitost byla Θ(n 2,78041 ) .

Beanieho algoritmus (1979)

V roce 1979 skupina italských vědců vedená Bini [4] vyvinula algoritmus pro násobení matic pomocí tenzorů. Jeho složitost je Θ(n 2,7799 ) .

Schönhageovy algoritmy (1981)

V roce 1981 Schönhage [5] představil metodu, která pracuje s rychlostí Θ(n 2,695 ) . Odhad je získán pomocí přístupu zvaného násobení parciální matice . Později se mu podařilo získat odhad Θ(n 2,6087 ) . Poté Schönhage získal odhad složitosti Θ(n 2,548 ) na základě metody přímých součtů . Romani dokázal snížit hodnocení na Θ(n 2,5166 ) , zatímco Pan dokázal snížit hodnocení na Θ(n 2,5161 ) .

Coppersmith-Winograd algorithm (1990)

V roce 1990 publikovali Coppersmith a Winograd [6] algoritmus, který podle modifikace Williamsem Wasilewskou [7] v roce 2011 násobí matice rychlostí O(n 2,3727 ) . Tento algoritmus využívá myšlenky podobné Strassenovu algoritmu. K dnešnímu dni jsou úpravy Coppersmith-Winogradova algoritmu asymptoticky nejrychlejší. Ale skutečnost, že získaná zlepšení jsou zanedbatelná, umožňuje hovořit o existenci "Coppersmith-Winogradské bariéry" v asymptotických odhadech rychlosti algoritmů. Coppersmith-Winogradův algoritmus je účinný pouze na matice astronomické velikosti a nelze jej prakticky aplikovat.

Spojení s teorií grup (2003)

V roce 2003 Koch et al uvažovali Strassenův a Coppersmith-Winogradův algoritmus ve svých pracích [8] v kontextu teorie grup . Ukázali, že Strassenova domněnka je platná (tj. minimální složitost je omezena pro jakoukoli ), pokud je splněna jedna z hypotéz teorie grup [9] .

O(n^{2+\epsilon })

\epsilon

Mocniny matic

Čtvercové matice lze samy násobit mnohokrát stejným způsobem jako běžná čísla, protože mají stejný počet řádků a sloupců. Takové sekvenční násobení lze nazvat zvýšením matice na mocninu - to bude speciální případ obvyklého násobení několika matic. Obdélníkové matice mají různý počet řádků a sloupců, takže je nelze nikdy umocnit. Matice n × n A umocněná na mocninu je definována vzorcem

{\displaystyle \mathbf {A} ^{k}=\underbrace {\mathbf {A} \mathbf {A} \cdots \mathbf {A} } _{k))

a má následující vlastnosti ( λ je nějaký skalární):

Nulový stupeň:

\mathbf {A} ^{0}=\mathbf {E}

kde E je matice identity . To je analogické se skutečností, že nulová mocnina libovolného čísla je rovna jedné.

Násobení skalárem:

(\lambda \mathbf {A} )^{k}=\lambda ^{k}\mathbf {A} ^{k}

Determinant:

\det(\mathbf {A} ^{k})=\det(\mathbf {A} )^{k}

Nejjednodušší způsob, jak vypočítat stupeň matice, je vynásobit matici A k krát výsledkem předchozího násobení, počínaje maticí identity, jak se to často dělá u skalárů. Pro diagonalizovatelné matice existuje lepší metoda založená na použití spektrálního rozkladu matice A . Jiná metoda, založená na Hamiltonově-Cayleyově větě , konstruuje efektivnější výraz pro Ak , ve kterém je umocněn skalár a ne celá matice .

Speciálním případem jsou diagonální matice . Protože součin diagonálních matic je redukován na násobení odpovídajících diagonálních prvků, pak se k -tá mocnina diagonální matice A skládá z prvků umocněných na požadovanou mocninu:

\mathbf {A} ^{k}={\begin{pmatrix}a_{11}&0&\cdots &0\\0&a_{22}&\cdots &0\\\vdots &\vdots &\ddots &\vdots \\0&0& \cdots &a_{nn}\end{pmatrix}}^{k}={\begin{pmatrix}a_{11}^{k}&0&\cdots &0\\0&a_{22}^{k}&\cdots &0\ \\vdots &\vdots &\ddots &\vdots \\0&0&\cdots &a_{nn}^{k}\end{pmatrix}}.

Není tedy těžké pozvednout diagonální matici na mocninu. Při zvýšení libovolné matice (ne nutně diagonální) na mocninu je často užitečné nejprve použít vlastnosti diagonalizovatelných matic .

Pomocí násobení matic a umocňování matic lze definovat další operace s maticemi. Například exponent matice lze definovat jako mocninnou řadu , logaritmus matice lze definovat jako převrácenou hodnotu exponentu matice a tak dále.

Viz také

Literatura

Korn G., Korn T. Maticová algebra a maticový počet // Handbook of Mathematics. - 4. vydání. - M .: Nauka, 1978. - S. 392-394.

Poznámky

↑ Kybernetická sbírka. Nová série. Problém. 25. so. články 1983 - 1985: Per. z angličtiny. - M .: Mir, 1988 - V.B. Aleksev. Složitost násobení matic. Posouzení.
↑ Strassen V. Gaussova eliminace není optimální // Počet . Matematika / F. Brezzi - Springer Science + Business Media , 1969. - Sv. 13, Iss. 4. - S. 354-356. — ISSN 0029-599X ; 0945-3245 - doi:10.1007/BF02165411
↑ Pan V. Ya, Strassenův algoritmus není optimální - trilineární technika agregačního sjednocování a rušení pro konstrukci rychlých algoritmů pro maticové operace. — Proc. 19. výroční symposium o základech počítačových věd, Ann Arbor, Michigan, 1978
↑ Bini D., Capovani M., Lotti G., Romani F. — složitost pro přibližné násobení matic. — informovat. proces. Lett., 1979 $O(n^{2,7799})$
↑ Schonhage A. Parciální a totální násobení matic. — SIAM J. Comput., 1981
↑ Don Coppersmith a Shmuel Winograd. Násobení matic pomocí aritmetických posloupností. Journal of Symbolic Computation , 9:251-280, 1990.
↑ Williams, Virginia (2011), Multiplying matices in O(n 2,3727 time Archived 26. října 2014 na Wayback Machine
↑ Skupinově teoretické algoritmy pro násobení matic . Získáno 26. září 2009. Archivováno z originálu 6. srpna 2011. (neurčitý)
↑ Směrem k optimálnímu algoritmu pro násobení matic (downlink) . Získáno 26. září 2009. Archivováno z originálu 31. března 2010. (neurčitý)

Vektory a matice

vektory

Základní pojmy	Vektor v geometrii Základ Ortogonální základ Vektorové souřadnice Kolinearita Ortogonalita Lineární závislost Prostor sloupců
Druhy vektorů	Jednotkový vektor Axiální vektor izotropní vektor Normální Kolinearita Nulový vektor Vektor poloměru Vlastní vektor
Operace s vektory	Skalární součin vektorový produkt smíšený produkt Pseudoskalární produkt Dvojitý křížový produkt
Typy prostoru	vektorový prostor afinní prostor Euklidovský prostor Pseudoeuklidovský prostor Normovaný prostor Minkowského prostor

matrice

Základní pojmy	Maticové násobení Transponovaná matice Hermitovská konjugovaná matice Symetrická matice inverzní matice Vlastní hodnota Charakteristický polynom matice
Speciální matrice	Matice identity Nulová matice Diagonální matice lambda matrice
Maticové rozklady	LU rozklad Choleský rozklad QR rozklad rozklad LUP singulární rozklad hodnoty Spektrální rozklad matice

jiný