Mátrixszorzás

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2022. augusztus 10-én felülvizsgált verziótól ; az ellenőrzések 2 szerkesztést igényelnek .

A mátrixszorzás a mátrixok egyik alapvető művelete . A szorzási művelet eredményeként kapott mátrixot mátrixszorzatnak nevezzük . Az új mátrix elemeit a régi mátrixok elemeiből kapjuk az alábbiakban bemutatott szabályok szerint .

A és mátrixok szorozhatók, ha kompatibilisek abban az értelemben, hogy a mátrix oszlopainak száma megegyezik a sorok számával . $A$ $B$ $A$ $B$

A mátrixoknak sok olyan algebrai szorzási tulajdonságuk van, mint a közönséges számoknak, kivéve a kommutativitást .

Négyzetes mátrixoknál a szorzás mellett bevezethető a mátrix hatványra emelésének művelete és az inverz mátrix .

Míg a mátrixokat különösen a matematikai terek transzformációinak leírására használják ( forgás , tükrözés , nyújtás és mások), a mátrixok szorzata a transzformációk összetételét írja le .

Definíció

Legyen két téglalap alakú mátrix és méret , és legyen megadva : $A$ $B$ $l\times m$ $m\szer n$

A={\begin{bmatrix}a_{11}&a_{12}&\cdots &a_{1m}\\a_{21}&a_{22}&\cdots &a_{2m}\\\vponts &\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}}.

Ezután a mátrix a méretekkel : $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}},

ahol:

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

terméküknek nevezik .

Két mátrix szorzásának művelete csak akkor valósítható meg, ha az első tényező oszlopainak száma megegyezik a második sorainak számával; ebben az esetben a mátrixokat konzisztensnek mondjuk . Különösen a szorzás mindig megvalósítható, ha mindkét tényező azonos sorrendű négyzetmátrix .

Így egy mű létezése egyáltalán nem követi a mű létét. $AB$ $B.A.$

Illusztráció

Az AB mátrixszorzat az A mátrix sorvektorai és a B mátrix oszlopvektorai belső szorzatainak összes lehetséges kombinációjából áll . Az AB mátrix i, j indexű eleme az A mátrix i-edik sorvektorának és a B mátrix j - edik oszlopvektorának skaláris szorzata .

A jobb oldali ábra két A és B mátrix szorzatának kiszámítását mutatja be, megmutatja, hogy a mátrixszorzat egyes metszéspontjai hogyan felelnek meg az A mátrix sorainak és a B mátrix oszlopainak . A kapott mátrix mérete mindig a lehető legnagyobb, vagyis az A mátrix minden sorához és a B mátrix oszlopához mindig van egy megfelelő metszéspont a mátrix szorzatában.

A körökkel jelölt metszéspontokban a következő értékek lesznek:

${\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}\\{\color {Blue}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{igazított}}$

Általában a mátrixszorzat nem kommutatív művelet. Például:

{\overset {3\times 4{\text{ mátrix))}{\begin{bmatrix}\cdot &\cdot &\cdot &\cdot \\\cdot &\cdot &\cdot &\cdot \\\szín {Kék}1&\szín {Kék}2&\szín {Kék}3&\szín {Kék}4\\\end{bmátrix}}}{\overset {4\times 5{\text{ matrix}}}{\begin {bmátrix}\cdot &\cdot &\cdot &\color {Piros}a&\cdot \\\cdot &\cdot &\cdot &\color {Red}b&\cdot \\\cdot &\cdot &\cdot & \color {Red}c&\cdot \\\cdot &\cdot &\cdot &\color {Red}d&\cdot \\\end{bmatrix}}}={\overset {3\times 5{\text{ mátrix ))}{\begin{bmátrix}\cdot &\cdot &\cdot &\cdot &\cdot \\\cdot &\cdot &\cdot &\cdot &\cdot \\\cdot &\cdot &\cdot &x_ {3,4}&\cdot \\\end{bmátrix}}}

A fenti mátrixok szorzatának elemét a következőképpen számítjuk ki $x_{{3,4}}$

x_{3,4}=({\szín {kék}1},{\szín {kék}2},{\szín {kék}3},{\szín {kék}4})\cdot ({\szín {piros}a},{\szín {piros}b},{\szín {piros}c},{\szín {piros}d})={\szín {Kék}1}\cdot {\szín {piros} a}+{\color {Blue}2}\cdot {\color {Piros}b}+{\color {Blue}3}\cdot {\color {Red}c}+{\color {Blue}4}\ cdot {\color {piros}d}

A mátrixjelölésben az első koordináta egy sort, a második koordináta egy oszlopot jelöl; ez a sorrend az indexelésnél és a méretezésnél is használatos. Az eredményül kapott mátrix sorának és oszlopának metszéspontjában lévő elem az első mátrix i-edik sorának és a második mátrix i-edik oszlopának skaláris szorzata . Ez megmagyarázza, hogy a szorzott mátrixok szélességének és magasságának meg kell egyeznie: ellenkező esetben a pontszorzat definiálatlan. $x_{{\color {Blue}i}{\color {piros}j))$ $én$ $j$ $én$ $j$

Vita

A mátrixszorzás leírt szabályának okait a vektor mátrixszal való szorzását tekintve a legkönnyebb átlátni .

Ez utóbbit természetesen az a tény vezeti be, hogy a vektorok bázis szerinti felbontásakor az A lineáris operátor (bármely) művelete megadja a v' = A v vektor komponenseinek kifejezését :

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

Vagyis a lineáris operátort egy mátrix, a vektorokat oszlopvektorokkal, az operátor működését a vektorral pedig a bal oldali oszlopvektor operátormátrixszal való mátrixszorzásával ábrázoljuk (ez a mátrixszorzás speciális esete, ha az egyik mátrix, az oszlopvektor mérete ). $n\times 1$

(Ugyanúgy a koordináták megváltoztatásakor bármilyen új bázisra való átmenetet egy teljesen hasonló kifejezés reprezentálja, csak ebben az esetben már nem az új vektor komponensei a régi bázisban, hanem a régi vektor komponensei az új bázisban ebben az esetben az új bázisra való átmenet mátrix elemei ). $v'_{i}$ $A_{{ij}}$

Ha figyelembe vesszük a két operátor vektorán végrehajtott szekvenciális műveletet: először A , majd B (vagy az A bázis transzformációját , majd a B bázis transzformációját ), képletünket kétszer alkalmazva kapjuk:

v''_{i}=\sum \limits _{j}B_{ij}\sum \limits _{k}A_{jk}v_{k}=\sum \limits _{j}\sum \limits _ {k}B_{ij}A_{jk}v_{k}=\sum \limits _{k}\sum \limits _{j}(B_{ij}A_{jk})v_{k},

ahonnan látható, hogy az A és B lineáris operátorok működésének BA összetétele (vagy a bázistranszformációk hasonló összetétele) megfelel egy mátrixnak, amelyet a megfelelő mátrixok szorzatának szabálya alapján számítanak ki:

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

Az így definiált mátrixok szorzata meglehetősen természetesnek és nyilvánvalóan hasznosnak bizonyul (egyszerű és univerzális módot biztosít tetszőleges számú lineáris transzformáció összetételének kiszámítására).

Tulajdonságok

Asszociatív tulajdonság , asszociativitás :

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

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

Elosztó tulajdonság , eloszlás az összeadás tekintetében :

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

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

Egy mátrix és egy megfelelő sorrendű azonosságmátrix szorzata egyenlő magával a mátrixszal: $\mathbf {E}$

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

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

Egy mátrix és egy megfelelő méretű nulla mátrix szorzata egyenlő a nulla mátrixszal: $\mathbf {0}$

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

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

Ha a és azonos sorrendű négyzetmátrixok , akkor a mátrixszorzatnak számos egyéb tulajdonsága is van. $\mathbf {A}$ $\mathbf {B}$

A mátrixszorzás általában nem kommutatív :

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

Ha , akkor a és mátrixok azt mondják, hogy ingáznak egymással. $\mathbf {AB} =\mathbf {BA}$ $\mathbf {A}$ $\mathbf {B}$

A legegyszerűbb példák ingázási mátrixokra:

tetszőleges négyzetmátrix - önmagával: (a mátrix négyzetre emelése); $\mathbf {AA} =\mathbf {AA} =\mathbf {A^{2}}$
tetszőleges négyzetmátrix — azonos sorrendű azonossági mátrixszal: ; $\mathbf {AE} =\mathbf {EA} =\mathbf {A}$
tetszőleges négyzetmátrix — azonos sorrendű nulla mátrixszal: ; $\mathbf {A0} =\mathbf {0A} =\mathbf {0}$
bármely nem szinguláris négyzetmátrix — inverz mátrixával: . $\mathbf {AA^{-1}} =\mathbf {A^{-1}A} =\mathbf {E}$

A szorzat determinánsa és nyoma nem függ a mátrixszorzás sorrendjétől:

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

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

Inverz mátrix

Egy négyzetes mátrixot nem szingulárisnak ( nem szingulárisnak ) nevezünk , ha egyedi inverz mátrixa van, és teljesül a következő feltétel: $A$ $A^{{-1}}$

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

Egyébként a mátrixot speciálisnak ( degeneráltnak ) nevezik . $A$

Egy sorrendi mátrix akkor és csak akkor nem degenerált, ha ebben az esetben van egy ugyanolyan rendű négyzetmátrix $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],

ahol az elem algebrai komplementere a determinánsban $A_{{ik}}$ $a_{{ik}}$ $\det\left[a_{ik}\right].$

Gyors mátrixszorzó algoritmusok

A mátrixok szorzatának kiszámításának bonyolultsága definíció szerint , de vannak hatékonyabb algoritmusok [1] , amelyeket nagy mátrixokhoz használnak. A nagy mátrixok szorzási sebességének korlátozása, valamint a nagy mátrixok szorzására szolgáló leggyorsabb és legstabilabb gyakorlati algoritmusok megalkotásának kérdése továbbra is a lineáris algebra egyik megoldatlan problémája . $\O(n^{3})$

Strassen algoritmusa (1969)

Az első algoritmust a nagy mátrixok gyors szorzására Volker Strassen [2] fejlesztette ki 1969-ben. Az algoritmus a mátrixok 2X2 blokkokra való rekurzív felosztásán alapul . Strassen bebizonyította, hogy 2X2 mátrix nem kommutatív módon szorozható hét szorzással, így a rekurzió minden lépésében hét szorzás történik nyolc helyett. Ennek eredményeképpen ennek az algoritmusnak aszimptotikus összetettsége . Ennek a módszernek a hátránya a standard algoritmushoz képest bonyolultabb programozás, rossz numerikus stabilitás és nagyobb memóriahasználat. Számos Strassen-módszeren alapuló algoritmust fejlesztettek ki, amelyek javítják a numerikus stabilitást, az állandó sebességet és egyéb jellemzőket. Ennek ellenére egyszerűsége miatt a Strassen-algoritmus továbbra is az egyik gyakorlati algoritmus a nagy mátrixok szorzására. Strassen a következő Strassen-sejtést is felvetette : tetszőlegesen kicsire létezik egy algoritmus, amely kellően nagy n természetes számok esetén garantálja két méretű mátrix megszorzását műveletekben .

O(n^{\log _{2}7})\kb O(n^{2.81})

\varepsilon >0

n\szer n

O(n^{2+\varepszilon })

A mátrixszorzás sebességének ω kitevőjének további fejlesztései

A jövőben a nagy mátrixok szorzási sebességére vonatkozó becsléseket többszörösen javították. Ezek az algoritmusok azonban elméletiek voltak, többnyire hozzávetőlegesek. A közelítő szorzási algoritmusok instabilitása miatt a gyakorlatban jelenleg nem használatosak.

Pan's Algorithm (1978)

1978-ban Pan [3] saját mátrixszorzási módszerét javasolta, melynek összetettsége Θ(n 2,78041 ) volt .

Beanie algoritmusa (1979)

1979-ben olasz tudósok egy csoportja Bini [4] vezetésével algoritmust dolgozott ki tenzoros mátrixszorzáshoz. Bonyolultsága Θ(n 2,7799 ) .

Schönhage algoritmusok (1981)

1981-ben Schönhage [5] bevezetett egy módszert, amely Θ(n 2,695 ) sebességgel működik . A becslést a részleges mátrixszorzásnak nevezett megközelítéssel kapjuk meg . Később sikerült megkapnia a Θ(n 2,6087 ) becslést . Ekkor Schönhage megkapta a Θ(n 2,548 ) komplexitásbecslést a közvetlen összegek módszere alapján . Romani képes volt leminősíteni Θ(n 2.5166 ) értékre , míg Pan képes volt visszaminősíteni Θ(n 2.5161 ) értékre .

Coppersmith-Winograd algoritmus (1990)

1990-ben Coppersmith és Winograd [6] közzétett egy algoritmust, amely Williams Wasilewska [7] 2011-ben módosítottaként O(n 2,3727 ) sebességgel szorozza a mátrixokat . Ez az algoritmus Strassen algoritmusához hasonló ötleteket használ. A mai napig a Coppersmith-Winograd algoritmus módosításai aszimptotikusan a leggyorsabbak. De az a tény, hogy a kapott fejlesztések elhanyagolhatóak, lehetővé teszi, hogy az algoritmusok sebességének aszimptotikus becslésében a "Coppersmith-Winograd akadály" létezéséről beszéljünk. A Coppersmith-Winograd algoritmus csak csillagászati méretű mátrixokon hatékony, a gyakorlatban nem alkalmazható.

Kapcsolat a csoportelmélettel (2003)

2003-ban Koch és munkatársai a Strassen és Coppersmith-Winograd algoritmusokat tanulmányaikban [8] a csoportelmélet összefüggésében vizsgálták . Megmutatták, hogy Strassen sejtése érvényes (azaz a minimális komplexitás korlátos bármely ), ha a csoportelméleti hipotézisek [9] egyike teljesül .

O(n^{2+\epsilon })

\epsilon

Mátrixok hatványai

A négyzetes mátrixok önmagukban sokszorosára szorozhatók, ugyanúgy, mint a közönséges számok, mivel azonos számú sorból és oszlopból állnak. Az ilyen szekvenciális szorzást egy mátrix hatványra emelésének nevezhetjük - ez a több mátrix szokásos szorzásának speciális esete lesz. A téglalap alakú mátrixok sorai és oszlopai eltérőek, ezért soha nem emelhetők hatványra. A hatványra emelt n × n A mátrixot a képlet határozza meg

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

és a következő tulajdonságokkal rendelkezik ( λ valamilyen skalár):

Nulla fokozat:

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

ahol E az azonosságmátrix . Ez analóg azzal a ténnyel, hogy bármely szám nulla hatványa egyenlő eggyel.

Szorzás skalárral:

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

Döntő:

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

A mátrix fokszámának kiszámításának legegyszerűbb módja az A mátrix k - szoros szorzása az előző szorzás eredményével, az identitásmátrixból kiindulva, ahogy ezt gyakran teszik skalároknál. A diagonalizálható mátrixok esetében van egy jobb módszer, amely az A mátrix spektrális dekompozícióján alapul . Egy másik módszer, amely a Hamilton-Cayley-tételen alapul , egy hatékonyabb kifejezést alkot Ak -ra , amelyben a skalárt a kívánt teljesítményre emeljük , és nem a teljes mátrixot .

Az átlós mátrixok speciális esetet alkotnak . Mivel az átlós mátrixok szorzatát a megfelelő átlóelemek szorzatára redukáljuk, így az A átlós mátrix k - edik hatványa a szükséges hatványra emelt elemekből áll:

\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}}.

Így nem nehéz egy átlós mátrixot hatványra emelni. Egy tetszőleges (nem feltétlenül átlós) mátrix hatványra emelésekor gyakran hasznos először a diagonalizálható mátrixok tulajdonságait használni .

A mátrixok mátrixszorzásával és hatványozásával más műveletek is definiálhatók a mátrixokon. Például a mátrix kitevője definiálható hatványsor formájában , a mátrix logaritmus a mátrix kitevőjének inverzeként , és így tovább.

Lásd még

Irodalom

Korn G., Korn T. Mátrixalgebra és mátrixszámítás // Matematika kézikönyve. - 4. kiadás. - M .: Nauka, 1978. - S. 392-394.

Jegyzetek

↑ Kibernetikus gyűjtemény. Új sorozat. Probléma. 25. Szo. cikkek 1983-1985: Per. angolról. - M .: Mir, 1988 - V.B. Aleksev. A mátrixszorzás összetettsége. Felülvizsgálat.
↑ Strassen V. A Gauss-elimináció nem optimális // Szám . Math / F. Brezzi - Springer Science + Business Media , 1969. - Vol. 13, Iss. 4. - P. 354-356. — ISSN 0029-599X ; 0945-3245 - doi:10.1007/BF02165411
↑ Pan V. Ya, Strassen algoritmusa nem optimális – aggregáló egyesítés és törlés trilineáris technikája a mátrixműveletek gyors algoritmusainak felépítéséhez. — Proc. 19th Annual Symposium on Foundations of Computer Science, Ann Arbor, Mich., 1978
↑ Bini D., Capovani M., Lotti G., Romani F. — komplexitás közelítő mátrixszorzáshoz. - tájékoztat. folyamat. Lett., 1979 $O(n^{2,7799})$
↑ Schonhage A. Részleges és teljes mátrixszorzás. – SIAM J. Comput., 1981
↑ Don Coppersmith és Shmuel Winograd. Mátrixszorzás aritmetikai progresszióval. Journal of Symbolic Computation , 9:251-280, 1990.
↑ Williams, Virginia (2011), Multiplying matices in O(n 2,3727 idő Archivált : 2014. október 26. a Wayback Machine -nél
↑ Csoportelméleti algoritmusok mátrixszorzáshoz . Letöltve: 2009. szeptember 26. Az eredetiből archiválva : 2011. augusztus 6.. (határozatlan)
↑ Egy optimális mátrixszorzási algoritmus felé (lefelé irányuló kapcsolat) . Letöltve: 2009. szeptember 26. Az eredetiből archiválva : 2010. március 31.. (határozatlan)

Vektorok és mátrixok

Vektorok

Alapfogalmak	Vektor a geometriában Alap Ortogonális alap Vektor koordináták Kollinearitás Ortogonalitás Lineáris függőség Oszlopköz
A vektorok fajtái	Egységvektor Axiális vektor izotróp vektor Normál Kollinearitás Nulla vektor Sugár vektor Sajátvektor
Műveletek vektorokon	Skaláris szorzat vektor termék vegyes termék Pszeudoszkaláris termék Kettős kereszttermék
Tértípusok	vektor tér affin tér Euklideszi tér Pszeudoeuklideszi tér Normált tér Minkowski tér

mátrixok

Alapfogalmak	Mátrixszorzás Transzponált mátrix Hermitikus konjugált mátrix Szimmetrikus mátrix inverz mátrix Sajátérték Mátrix karakterisztikus polinomja
Speciális mátrixok	Identitásmátrix Nulla mátrix Átlós mátrix lambda mátrix
Mátrix dekompozíciók	LU bomlás Cholesky-bomlás QR-bontás LUP bomlás szinguláris érték felbontás Mátrix spektrális lebontása

Egyéb