Matrismultiplikation

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 10 augusti 2022; kontroller kräver 2 redigeringar .

Matrismultiplikation är en av de grundläggande operationerna på matriser . Matrisen som blir resultatet av multiplikationsoperationen kallas en matrisprodukt . Elementen i den nya matrisen erhålls från elementen i de gamla matriserna enligt reglerna som illustreras nedan .

Matriserna och kan multipliceras om de är kompatibla i den meningen att antalet matriskolumner är lika med antalet rader . $A$ $B$ $A$ $B$

Matriser har många av de algebraiska multiplikationsegenskaperna som vanliga tal har, med undantag för kommutativitet .

För kvadratiska matriser, förutom multiplikation, kan operationen att höja en matris till en potens och den inversa matrisen introduceras .

Medan matriser används för att beskriva i synnerhet transformationer av matematiska rum ( rotation , reflektion , sträckning och andra), kommer produkten av matriser att beskriva sammansättningen av transformationer .

Definition

Låt två rektangulära matriser och dimensioner och ges, respektive: $A$ $B$ $l\times m$ $m\ gånger 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}}.

Sedan matrisen med dimensioner : $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}},

vart i:

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

kallas deras produkt .

Operationen att multiplicera två matriser är möjlig endast om antalet kolumner i den första faktorn är lika med antalet rader i den andra; i detta fall sägs matriserna vara konsekventa . I synnerhet är multiplikation alltid möjlig om båda faktorerna är kvadratiska matriser av samma ordning.

Existensen av ett verk följer alltså inte alls efter existensen av ett verk. $AB$ $B.A.$

Illustration

Matrisprodukten AB består av alla möjliga kombinationer av de inre produkterna av radvektorerna i matris A och kolumnvektorerna för matris B. Elementet i matrisen AB med indexen i, j är skalärprodukten av den i : te radensvektorn i matrisen A och den j : te kolumnvektorn i matrisen B .

Illustrationen till höger visar beräkningen av produkten av två matriser A och B , den visar hur varje skärningspunkt i matrisprodukten motsvarar raderna i matris A och kolumnerna i matris B. Storleken på den resulterande matrisen är alltid den maximala möjliga, det vill säga för varje rad av matris A och kolumn i matris B finns det alltid en motsvarande skärningspunkt i produkten av matrisen.

Värdena vid korsningarna markerade med cirklar kommer att vara:

${\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{aligned}}$

I allmänhet är matrisprodukt inte en kommutativ operation. Till exempel:

{\översatt {3\ gånger 4{\text{ matris))}{\begin{bmatrix}\cdot &\cdot &\cdot &\cdot \\\cdot &\cdot &\cdot &\cdot \\\färg {Blå}1&\color {Blå}2&\color {Blå}3&\color {Blå}4\\\end{bmatrix}}}{\overset {4\times 5{\text{ matrix}}}{\begin {bmatrix}\cdot &\cdot &\cdot &\color {Röd}a&\cdot \\\cdot &\cdot &\cdot &\color {Röd}b&\cdot \\\cdot &\cdot &\cdot & \color {Röd}c&\cdot \\\cdot &\cdot &\cdot &\color {Röd}d&\cdot \\\end{bmatrix}}}={\översatt {3\ gånger 5{\text{ matris ))}{\begin{bmatrix}\cdot &\cdot &\cdot &\cdot &\cdot \\\cdot &\cdot &\cdot &\cdot &\cdot \\\cdot &\cdot &\cdot &x_ {3,4}&\cdot \\\end{bmatrix}}}

Elementet av produkten av matriserna ovan beräknas enligt följande $x_{{3,4}}$

x_{3,4}=({\color {Blå}1},{\color {Blå}2},{\color {Blå}3},{\color {Blå}4})\cdot ({\color {Röd}a},{\color {Röd}b},{\color {Röd}c},{\color {Röd}d})={\color {Blå}1}\cdot {\color {Röd} a}+{\color {Blå}2}\cdot {\color {Röd}b}+{\color {Blå}3}\cdot {\color {Röd}c}+{\color {Blå}4}\ cdot {\color {Röd}d}

Den första koordinaten i matrisbeteckningen betecknar en rad, den andra koordinaten betecknar en kolumn; denna ordning används både för indexering och för dimensionering. Elementet i skärningspunkten mellan raden och kolumnen i den resulterande matrisen är skalärprodukten av den i: te raden i den första matrisen och den i: te kolumnen i den andra matrisen. Detta förklarar varför de multiplicerade matrisernas bredd och höjd måste matcha: annars är prickprodukten odefinierad. $x_{{\color {Blå}i}{\color {Röd}j))$ $i$ $j$ $i$ $j$

Diskussion

Det är lättast att se orsakerna till den beskrivna regeln för matrismultiplikation genom att överväga multiplikationen av en vektor med en matris.

Det senare introduceras naturligtvis baserat på det faktum att när vektorer sönderdelas i termer av en bas ger verkan av (valfri) linjär operator A uttrycket för komponenterna i vektorn v ' = Av :

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

Det vill säga, en linjär operator representeras av en matris, vektorer av kolumnvektorer, och verkan av en operator på en vektor genom matrismultiplikation av kolumnvektorn till vänster av operatormatrisen (detta är ett specialfall av matrismultiplikation, när en av matriserna, kolumnvektorn, har storlek ). $n\ gånger 1$

(På samma sätt representeras övergången till vilken ny bas som helst vid ändring av koordinater av ett helt liknande uttryck, bara i detta fall är det inte längre komponenterna i den nya vektorn i den gamla basen, utan komponenterna i den gamla vektorn i den nya basen ; i det här fallet elementen i övergångsmatrisen till den nya basen). $v'_{i}$ $A_{{ij}}$

Efter att ha övervägt den sekventiella åtgärden på vektorn av två operatorer: först A och sedan B (eller transformationen av basen A och sedan transformationen av basen B ), genom att tillämpa vår formel två gånger, får vi:

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

varav det kan ses att sammansättningen BA av verkan av linjära operatorer A och B (eller en liknande sammansättning av bastransformationer) motsvarar en matris som beräknas med produktregeln för motsvarande matriser:

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

Produkten av matriser som definieras på detta sätt visar sig vara ganska naturlig och uppenbarligen användbar (ger ett enkelt och universellt sätt att beräkna sammansättningar av ett godtyckligt antal linjära transformationer).

Egenskaper

Associativ egenskap , associativitet :

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

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

Fördelningsegendom , fördelningsfördelning med avseende på tillägg :

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

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

Produkten av en matris och identitetsmatrisen av en lämplig ordning är lika med själva matrisen: $\mathbf {E}$

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

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

Produkten av en matris och en nollmatris med lämplig dimension är lika med nollmatrisen: $\mathbf {0}$

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

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

Om och är kvadratiska matriser av samma ordning, så har matrisprodukten ett antal andra egenskaper. $\mathbf {A}$ $\mathbf {B}$

Matrismultiplikation är i allmänhet icke- kommutativ :

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

Om , då sägs matriserna och pendla med varandra. $\mathbf {AB} =\mathbf {BA}$ $\mathbf {A}$ $\mathbf {B}$

De enklaste exemplen på pendlingsmatriser:

vilken kvadratisk matris som helst - med sig själv: (kvadrera matrisen); $\mathbf {AA} =\mathbf {AA} =\mathbf {A^{2}}$
valfri kvadratisk matris — med identitetsmatrisen av samma ordning: ; $\mathbf {AE} =\mathbf {EA} =\mathbf {A}$
valfri kvadratisk matris — med en nollmatris av samma ordning: ; $\mathbf {A0} =\mathbf {0A} =\mathbf {0}$
valfri icke-singular kvadratisk matris — med dess inversa matris: . $\mathbf {AA^{-1}} =\mathbf {A^{-1}A} =\mathbf {E}$

Determinanten och spåret av produkten beror inte på ordningen för matrismultiplikation:

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

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

Invers matris

En kvadratisk matris kallas icke- singular ( icke- singular ) om den har en unik invers matris så att följande villkor är uppfyllt: $A$ $A^{{-1}}$

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

Annars kallas matrisen speciell ( degenererad ) . $A$

En ordermatris är icke-degenererad om och endast om det i detta fall finns en kvadratisk matris av samma ordning $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],

var är det algebraiska komplementet av elementet i determinanten $A_{{ik}}$ $a_{{ik}}$ $\det\left[a_{ik}\right].$

Algoritmer för snabb matrismultiplikation

Komplexiteten i att beräkna produkten av matriser per definition är , men det finns mer effektiva algoritmer [1] som används för stora matriser. Frågan om den begränsande hastigheten för multiplikation av stora matriser, såväl som frågan om att konstruera de snabbaste och mest stabila praktiska algoritmerna för multiplikation av stora matriser, förblir ett av de olösta problemen med linjär algebra . $\O(n^{3})$

Strassens algoritm (1969)

Den första algoritmen för snabb multiplikation av stora matriser utvecklades av Volker Strassen [2] 1969. Algoritmen är baserad på en rekursiv uppdelning av matriser i 2X2 block . Strassen bevisade att 2X2- matriser kan multipliceras icke-kommutativt med sju multiplikationer, så sju multiplikationer utförs vid varje steg av rekursionen istället för åtta. Som ett resultat är den asymptotiska komplexiteten för denna algoritm . Nackdelen med denna metod är den större komplexiteten i programmeringen jämfört med standardalgoritmen, dålig numerisk stabilitet och en större mängd minne som används. Ett antal algoritmer baserade på Strassen-metoden har utvecklats, som förbättrar den numeriska stabiliteten, den konstanta hastigheten och andra egenskaper. Ändå, på grund av sin enkelhet, förblir Strassen-algoritmen en av de praktiska algoritmerna för att multiplicera stora matriser. Strassen lade också fram följande Strassen-förmodan : för godtyckligt liten finns det en algoritm som, för tillräckligt stora naturliga tal n , garanterar multiplikationen av två matriser av storlek i operationer.

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

\varepsilon >0

n\ gånger n

O(n^{2+\varepsilon })

Ytterligare förbättringar av exponenten ω för hastigheten för matrismultiplikation

I framtiden förbättrades uppskattningarna av multiplikationshastigheten för stora matriser många gånger om. Dessa algoritmer var dock teoretiska, mestadels ungefärliga. På grund av instabiliteten hos ungefärliga multiplikationsalgoritmer används de för närvarande inte i praktiken.

Pan's Algorithm (1978)

1978 föreslog Pan [3] sin egen metod för matrismultiplikation, vars komplexitet var Θ(n 2,78041 ) .

Beanies algoritm (1979)

1979 utvecklade en grupp italienska forskare under ledning av Bini [4] en algoritm för matrismultiplikation med hjälp av tensorer. Dess komplexitet är Θ(n 2,7799 ) .

Schönhage Algorithms (1981)

1981 introducerade Schönhage [5] en metod som fungerar med en hastighet av Θ(n 2,695 ) . Uppskattningen erhålls med hjälp av en metod som kallas partiell matrismultiplikation . Senare lyckades han få uppskattningen Θ(n 2,6087 ) . Sedan fick Schönhage komplexitetsuppskattningen Θ(n 2,548 ) baserat på metoden för direkta summor . Romani kunde nedgradera till Θ(n 2,5166 ) , medan Pan kunde nedgradera till Θ(n 2,5161 ) .

Coppersmith-Winograd algoritm (1990)

År 1990 publicerade Coppersmith och Winograd [6] en algoritm som, modifierad av Williams Wasilewska [7] 2011, multiplicerar matriser med en hastighet av O(n 2,3727 ) . Denna algoritm använder idéer som liknar Strassens algoritm. Hittills är ändringar av Coppersmith-Winograd-algoritmen de mest asymptotiskt snabba. Men det faktum att de erhållna förbättringarna är försumbara gör att vi kan tala om existensen av "Coppersmith-Winograd-barriären" i asymptotiska uppskattningar av algoritmernas hastighet. Coppersmith-Winograd-algoritmen är endast effektiv på matriser av astronomisk storlek och kan inte tillämpas i praktiken.

Samband med gruppteori (2003)

År 2003 betraktade Koch et al. Strassen och Coppersmith-Winograd algoritmer i sina uppsatser [8] i samband med gruppteori . De visade att Strassens gissning är giltig (d.v.s. den minsta komplexiteten är begränsad för någon ) om en av gruppteoretisk hypotes [9] är uppfylld .

O(n^{2+\epsilon })

\epsilon

Matriser

Kvadratiska matriser kan multipliceras med sig själva många gånger på samma sätt som vanliga tal, eftersom de har samma antal rader och kolumner. Sådan sekventiell multiplikation kan kallas att höja en matris till en potens - detta kommer att vara ett specialfall av den vanliga multiplikationen av flera matriser. Rektangulära matriser har olika antal rader och kolumner, så de kan aldrig höjas till en potens. En n × n matris A upphöjd till en potens definieras av formeln

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

och har följande egenskaper ( λ är någon skalär):

Noll grader:

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

där E är identitetsmatrisen . Detta är analogt med det faktum att nollpotensen för ett tal är lika med ett.

Multiplikation med en skalär:

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

Determinant:

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

Det enklaste sättet att beräkna graden av en matris är att multiplicera matrisen A k gånger med resultatet av föregående multiplikation, utgående från identitetsmatrisen, som ofta görs för skalärer. För diagonaliserbara matriser finns det en bättre metod baserad på att använda den spektrala nedbrytningen av matrisen A. En annan metod, baserad på Hamilton-Cayleys teorem , konstruerar ett mer effektivt uttryck för Ak , där skalären höjs till den önskade styrkan , och inte hela matrisen .

Diagonala matriser utgör ett specialfall . Eftersom produkten av diagonala matriser reduceras till multiplikationen av motsvarande diagonala element, så består den k -: te potensen av diagonalmatrisen A av elementen upphöjda till den erforderliga potensen:

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

Det är alltså inte svårt att höja en diagonal matris till en potens. När man höjer en godtycklig matris (inte nödvändigtvis diagonal) till en potens, är det ofta användbart att först använda egenskaperna för diagonaliserbara matriser .

Med hjälp av matrismultiplikation och exponentiering av matriser kan andra operationer på matriser definieras. Till exempel kan matrisexponenten definieras i termer av en potensserie , matrislogaritmen kan definieras som inversen av matrisexponenten , och så vidare.

Se även

Litteratur

Korn G., Korn T. Matrix Algebra och Matrix Calculus // Handbok i matematik. - 4:e upplagan. - M . : Nauka, 1978. - S. 392-394.

Anteckningar

↑ Cybernetisk samling. Ny serie. Problem. 25. Lör. artiklar 1983 - 1985: Per. från engelska. - M .: Mir, 1988 - V.B. Aleksev. Matrismultiplikationens komplexitet. Recension.
↑ Strassen V. Gaussisk eliminering är inte optimal // Antal . Math / F. Brezzi - Springer Science + Business Media , 1969. - Vol. 13, Iss. 4. - s. 354-356. — ISSN 0029-599X ; 0945-3245 - doi:10.1007/BF02165411
↑ Pan V. Ya, Strassens algoritm är inte optimal - trilinjär teknik för att aggregera förena och avbryta för att konstruera snabba algoritmer för matrisoperationer. — Proc. 19th Annual Symposium on Foundations of Computer Science, Ann Arbor, Mich., 1978
↑ Bini D., Capovani M., Lotti G., Romani F. — komplexitet för ungefärlig matrismultiplikation. - underrätta. bearbeta. Lett., 1979 $O(n^{2,7799})$
↑ Schonhage A. Partiell och total matrismultiplikation. — SIAM J. Comput., 1981
↑ Don Coppersmith och Shmuel Winograd. Matrismultiplikation via aritmetiska progressioner. Journal of Symbolic Computation , 9:251-280, 1990.
↑ Williams, Virginia (2011), Multiplicera matices i O(n 2,3727 tid Arkiverad 26 oktober 2014 på Wayback Machine
↑ Gruppteoretiska algoritmer för matrismultiplikation . Hämtad 26 september 2009. Arkiverad från originalet 6 augusti 2011. (obestämd)
↑ Mot en optimal algoritm för matrismultiplikation (nedlänk) . Hämtad 26 september 2009. Arkiverad från originalet 31 mars 2010. (obestämd)

Vektorer och matriser

Vektorer

Grundläggande koncept	Vektor i geometri Grund Ortogonal grund Vektorkoordinater Kolinearitet Ortogonalitet Linjärt beroende Kolumnutrymme
Typer av vektorer	Enhet vektor Axiell vektor isotrop vektor Vanligt Kolinearitet Noll vektor Radie vektor Egenvektor
Operationer på vektorer	Skalär produkt vektor produkt blandad produkt Pseudoskalär produkt Dubbelkorsprodukt
Utrymmestyper	vektor utrymme affint utrymme Euklidiskt utrymme Pseudo-euklidiskt utrymme Normerat utrymme Minkowski utrymme

matriser

Grundläggande koncept	Matrismultiplikation Transponerad matris Hermitisk konjugatmatris Symmetrisk matris invers matris Eget värde Karakteristiskt polynom för en matris
Specialmatriser	Identitetsmatris Noll matris Diagonal matris lambda matris
Matrisnedbrytningar	LU-nedbrytning Cholesky nedbrytning QR-sönderdelning LUP-nedbrytning singulärvärdesfaktorisering Spektral nedbrytning av en matris

Övrig