Matrix multiplikation

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 10. august 2022; checks kræver 2 redigeringer .

Matrix multiplikation er en af de grundlæggende operationer på matricer . Matrixen, der er resultatet af multiplikationsoperationen, kaldes et matrixprodukt . Elementerne i den nye matrix er hentet fra elementerne i de gamle matricer i henhold til reglerne illustreret nedenfor .

Matricerne og kan ganges, hvis de er kompatible i den forstand, at antallet af matrixkolonner er lig med antallet af rækker . $EN$ $B$ $EN$ $B$

Matricer har mange af de algebraiske multiplikationsegenskaber, som almindelige tal har, med undtagelse af kommutativitet .

For kvadratiske matricer, ud over multiplikation, kan operationen med at hæve en matrix til en potens og den inverse matrix introduceres .

Mens matricer bruges til at beskrive især transformationer af matematiske rum ( rotation , refleksion , strækning og andre), vil produktet af matricer beskrive sammensætningen af transformationer .

Definition

Lad to rektangulære matricer og dimensioner og gives henholdsvis: $EN$ $B$ $l\times m$ $m\ gange 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}}.

Derefter matricen 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}},

hvori:

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

kaldes deres produkt .

Operationen med at gange to matricer er kun mulig, hvis antallet af kolonner i den første faktor er lig med antallet af rækker i den anden; i dette tilfælde siges matricerne at være konsistente . Især er multiplikation altid mulig, hvis begge faktorer er kvadratiske matricer af samme orden.

Et værks eksistens følger således slet ikke efter eksistensen af et værk. $AB$ $B.A.$

Illustration

Matrixproduktet AB består af alle mulige kombinationer af de indre produkter af rækkevektorerne i matrix A og kolonnevektorerne i matrix B. Elementet i matrixen AB med indeks i, j er skalarproduktet af den i -te rækkevektor af matrix A og den j -te kolonnevektor af matrix B .

Illustrationen til højre viser udregningen af produktet af to matricer A og B , den viser hvordan hvert skæringspunkt i matrixproduktet svarer til rækkerne i matrix A og søjlerne i matrix B. Størrelsen af den resulterende matrix er altid den maksimale mulige, det vil sige, for hver række af matrix A og kolonne af matrix B er der altid et tilsvarende skæringspunkt i produktet af matrixen.

Værdierne ved krydsene markeret med cirkler vil være:

${\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}\\{\farve {Blå}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}}$

Generelt er matrixprodukt ikke en kommutativ operation. For eksempel:

{\overset {3\ gange 4{\tekst{ matrix))}{\begin{bmatrix}\cdot &\cdot &\cdot &\cdot \\\cdot &\cdot &\cdot &\cdot \\\farve {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}}}={\oversat {3\gange 5{\text{ matrix ))}{\begin{bmatrix}\cdot &\cdot &\cdot &\cdot &\cdot \\\cdot &\cdot &\cdot &\cdot &\cdot \\\cdot &\cdot &\cdot &x_ {3,4}&\cdot \\\end{bmatrix}}}

Elementet af produktet af matricerne ovenfor beregnes som følger $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ørste koordinat i matrixbetegnelsen betegner en række, den anden koordinat betegner en kolonne; denne rækkefølge bruges både til indeksering og til dimensionering. Elementet i skæringspunktet mellem rækken og kolonnen i den resulterende matrix er skalarproduktet af den ite række i den første matrix og den i: te kolonne i den anden matrix. Dette forklarer, hvorfor bredden og højden af de multiplicerede matricer skal matche: ellers er prikproduktet udefineret. $x_{{\color {Blå}i}{\color {Rød}j))$ $jeg$ $j$ $jeg$ $j$

Diskussion

Det er nemmest at se årsagerne til den beskrevne regel om matrixmultiplikation ved at overveje multiplikationen af en vektor med en matrix.

Sidstnævnte introduceres naturligt baseret på det faktum, at når vektorer dekomponeres i form af en basis , giver virkningen af (en hvilken som helst) lineær operator A udtrykket for komponenterne i vektoren v' = Av :

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

Det vil sige, at en lineær operator er repræsenteret af en matrix, vektorer af kolonnevektorer, og en operators handling på en vektor ved matrixmultiplikation af kolonnevektoren til venstre af operatormatricen (dette er et specialtilfælde af matrixmultiplikation, når en af matricerne, søjlevektoren, har størrelse ). $n\ gange 1$

(På samme måde er overgangen til enhver ny basis ved ændring af koordinater repræsenteret af et fuldstændig ens udtryk, kun i dette tilfælde er det ikke længere komponenterne af den nye vektor i den gamle basis, men komponenterne af den gamle vektor i den nye basis ; i dette tilfælde elementerne i overgangsmatrixen til det nye grundlag). $v'_{i}$ $A_{{ij}}$

Efter at have overvejet den sekventielle handling på vektoren af to operatorer: først A og derefter B (eller transformationen af basis A og derefter transformationen af basis B ), ved at anvende vores formel to gange, får vi:

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},

hvorfra det kan ses, at sammensætningen BA af virkningen af lineære operatorer A og B (eller en lignende sammensætning af basistransformationer) svarer til en matrix beregnet af produktreglen for de tilsvarende matricer:

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

Produktet af matricer defineret på denne måde viser sig at være ret naturligt og åbenlyst nyttigt (giver en enkel og universel måde at beregne sammensætninger af et vilkårligt antal lineære transformationer på).

Egenskaber

Associativ egenskab , associativitet :

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

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

Udbredende ejendom , fordelingsevne med hensyn til tilføjelse :

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

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

Produktet af en matrix og identitetsmatrixen af en passende rækkefølge er lig med selve matrixen: $\mathbf {E}$

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

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

Produktet af en matrix og en nulmatrix af passende dimension er lig med nulmatrixen: $\mathbf {0}$

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

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

Hvis og er kvadratiske matricer af samme orden, så har matrixproduktet en række andre egenskaber. $\mathbf {A}$ $\mathbf {B}$

Matrixmultiplikation er generelt ikke- kommutativ :

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

Hvis , så siges matricerne og at pendle med hinanden. $\mathbf {AB} =\mathbf {BA}$ $\mathbf {A}$ $\mathbf {B}$

De enkleste eksempler på pendlingsmatricer:

en hvilken som helst kvadratisk matrix - med sig selv: (kvadrering af matrixen); $\mathbf {AA} =\mathbf {AA} =\mathbf {A^{2}}$
enhver kvadratisk matrix — med identitetsmatrix af samme orden: ; $\mathbf {AE} =\mathbf {EA} =\mathbf {A}$
enhver kvadratisk matrix — med en nulmatrix af samme orden: ; $\mathbf {A0} =\mathbf {0A} =\mathbf {0}$
enhver ikke-singular kvadratisk matrix — med dens inverse matrix: . $\mathbf {AA^{-1}} =\mathbf {A^{-1}A} =\mathbf {E}$

Determinanten og sporet af produktet afhænger ikke af rækkefølgen af matrix multiplikation:

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

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

Invers Matrix

En kvadratisk matrix kaldes ikke- singular ( ikke- singular ), hvis den har en unik invers matrix , således at følgende betingelse er opfyldt: $EN$ $A^{{-1}}$

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

Ellers kaldes matrixen speciel ( degenereret ) . $EN$

En ordrematrix er ikke-degenereret, hvis og kun hvis der i dette tilfælde er en kvadratisk matrix af samme orden $A=\venstre[a_{ik}\right]$ $n$ $\det A=\det \left[a_{ik}\right]\neq 0;$ $A^{{-1}}$ $n:$

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

hvor er det algebraiske komplement af elementet i determinanten $A_{{ik}}$ $a_{{ik}}$ $\det\left[a_{ik}\right].$

Hurtig matrix multiplikation algoritmer

Kompleksiteten ved at beregne produktet af matricer er per definition , men der er mere effektive algoritmer [1] , der bruges til store matricer. Spørgsmålet om den begrænsende hastighed for multiplikation af store matricer, såvel som spørgsmålet om at konstruere de hurtigste og mest stabile praktiske algoritmer til multiplikation af store matricer, forbliver et af de uløste problemer med lineær algebra . $\O(n^{3})$

Strassens algoritme (1969)

Den første algoritme til hurtig multiplikation af store matricer blev udviklet af Volker Strassen [2] i 1969. Algoritmen er baseret på en rekursiv opdeling af matricer i 2X2 blokke . Strassen beviste, at 2X2 -matricer kan multipliceres ikke-kommutativt med syv multiplikationer, så syv multiplikationer udføres på hvert trin af rekursionen i stedet for otte. Som et resultat er den asymptotiske kompleksitet af denne algoritme . Ulempen ved denne metode er den større kompleksitet af programmering sammenlignet med standardalgoritmen, dårlig numerisk stabilitet og en større mængde hukommelse, der bruges. Der er udviklet en række algoritmer baseret på Strassen-metoden, som forbedrer den numeriske stabilitet, den konstante hastighed og andre egenskaber. Ikke desto mindre forbliver Strassen-algoritmen på grund af sin enkelhed en af de praktiske algoritmer til at multiplicere store matricer. Strassen fremsatte også følgende Strassen-formodning : for vilkårlig lille eksisterer der en algoritme, der for tilstrækkeligt store naturlige tal n garanterer multiplikationen af to størrelsesmatricer i operationer.

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

\varepsilon >0

n\ gange n

O(n^{2+\varepsilon })

Yderligere forbedringer af eksponenten ω for hastigheden af matrix multiplikation

I fremtiden blev estimater af multiplikationshastigheden af store matricer forbedret mange gange. Disse algoritmer var dog teoretiske, for det meste omtrentlige. På grund af ustabiliteten af tilnærmede multiplikationsalgoritmer bruges de ikke i praksis i øjeblikket.

Pan's Algorithm (1978)

I 1978 foreslog Pan [3] sin egen metode til matrixmultiplikation, hvis kompleksitet var Θ(n 2,78041 ) .

Beanies algoritme (1979)

I 1979 udviklede en gruppe italienske videnskabsmænd ledet af Bini [4] en algoritme til matrixmultiplikation ved hjælp af tensorer. Dens kompleksitet er Θ(n 2,7799 ) .

Schönhage Algorithms (1981)

I 1981 introducerede Schönhage [5] en metode, der virker med en hastighed på Θ(n 2,695 ) . Estimatet opnås ved hjælp af en metode kaldet partiel matrix multiplikation . Senere lykkedes det ham at få estimatet Θ(n 2,6087 ) . Derefter opnåede Schönhage kompleksitetsestimatet Θ(n 2.548 ) baseret på metoden med direkte summer . Romani var i stand til at nedgradere til Θ(n 2.5166 ) , mens Pan var i stand til at nedgradere til Θ(n 2.5161 ) .

Coppersmith-Winograd algoritme (1990)

I 1990 udgav Coppersmith og Winograd [6] en algoritme, der, som modificeret af Williams Wasilewska [7] i 2011, multiplicerer matricer med en hastighed på O(n 2,3727 ) . Denne algoritme bruger ideer, der ligner Strassens algoritme. Til dato er ændringer af Coppersmith-Winograd-algoritmen de mest asymptotisk hurtige. Men det faktum, at de opnåede forbedringer er ubetydelige, giver os mulighed for at tale om eksistensen af "Coppersmith-Winograd-barrieren" i asymptotiske estimater af algoritmernes hastighed. Coppersmith-Winograd-algoritmen er kun effektiv på matricer af astronomisk størrelse og kan ikke anvendes i praksis.

Forbindelse med gruppeteori (2003)

I 2003 overvejede Koch et al. Strassen og Coppersmith-Winograd algoritmer i deres artikler [8] i forbindelse med gruppeteori . De viste, at Strassens formodning er gyldig (dvs. minimumskompleksiteten er afgrænset for enhver ), hvis en af gruppeteorihypoteserne [9] er opfyldt .

O(n^{2+\epsilon })

\epsilon

Matricers magter

Kvadratiske matricer kan ganges med sig selv mange gange på samme måde som almindelige tal, da de har det samme antal rækker og kolonner. En sådan sekventiel multiplikation kan kaldes at hæve en matrix til en potens - dette vil være et særligt tilfælde af den sædvanlige multiplikation af flere matricer. Rektangulære matricer har et andet antal rækker og kolonner, så de kan aldrig hæves til en potens. En n × n matrix A hævet til en potens defineres af formlen

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

og har følgende egenskaber ( λ er noget skalar):

Nul grader:

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

hvor E er identitetsmatrixen . Dette er analogt med det faktum, at nulpotensen af ethvert tal er lig med en.

Multiplikation med en skalar:

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

Determinant:

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

Den nemmeste måde at beregne graden af en matrix på er at gange matrix A k gange med resultatet af den foregående multiplikation, startende fra identitetsmatrixen, som det ofte gøres for skalarer. For diagonaliserbare matricer er der en bedre metode baseret på at bruge den spektrale nedbrydning af matricen A. En anden metode, baseret på Hamilton-Cayley-sætningen , konstruerer et mere effektivt udtryk for Ak , hvor skalaren hæves til den krævede magt , og ikke hele matrixen .

Diagonale matricer udgør et specialtilfælde . Da produktet af diagonale matricer er reduceret til multiplikationen af de tilsvarende diagonale elementer, så består den k -te potens af diagonalmatricen A af elementerne hævet til den nødvendige potens:

\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 er således ikke svært at hæve en diagonal matrix til en potens. Når man hæver en vilkårlig matrix (ikke nødvendigvis diagonal) til en potens, er det ofte nyttigt først at bruge egenskaberne for diagonaliserbare matricer .

Ved hjælp af matrixmultiplikation og eksponentiering af matricer kan andre operationer på matricer defineres. For eksempel kan matrixeksponenten defineres i form af en potensrække , matrixlogaritmen kan defineres som den inverse af matrixeksponenten , og så videre.

Se også

Litteratur

Korn G., Korn T. Matrix Algebra og Matrix Calculus // Handbook of Mathematics. - 4. udgave. - M . : Nauka, 1978. - S. 392-394.

Noter

↑ Kybernetisk samling. Ny serie. Problem. 25. Lør. artikler 1983 - 1985: Pr. fra engelsk. - M .: Mir, 1988 - V.B. Aleksev. Kompleksiteten af matrix multiplikation. Anmeldelse.
↑ Strassen V. Gaussisk eliminering er ikke 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 algoritme er ikke optimal - trilineær teknik til at aggregere forene og annullere for at konstruere hurtige algoritmer til matrixoperationer. — Proc. 19. årlige symposium om grundlaget for computervidenskab, Ann Arbor, Mich., 1978
↑ Bini D., Capovani M., Lotti G., Romani F. — kompleksitet for omtrentlig matrixmultiplikation. - meddele. behandle. Lett., 1979 $O(n^{2,7799})$
↑ Schonhage A. Partiel og total matrixmultiplikation. — SIAM J. Comput., 1981
↑ Don Coppersmith og Shmuel Winograd. Matrix multiplikation via aritmetiske progressioner. Journal of Symbolic Computation , 9:251-280, 1990.
↑ Williams, Virginia (2011), Multiplikation af matices i O (n 2.3727 tid Arkiveret 26. oktober 2014 på Wayback Machine
↑ Gruppeteoretiske algoritmer til matrixmultiplikation . Hentet 26. september 2009. Arkiveret fra originalen 6. august 2011. (ubestemt)
↑ Mod en optimal algoritme for matrixmultiplikation (downlink) . Hentet 26. september 2009. Arkiveret fra originalen 31. marts 2010. (ubestemt)

Vektorer og matricer

Vektorer

Basale koncepter	Vektor i geometri Basis Ortogonalt grundlag Vektorkoordinater Kolinearitet Ortogonalitet Lineær afhængighed Søjleplads
Slags vektorer	Enhedsvektor Aksial vektor isotrop vektor Normal Kolinearitet Nul vektor Radius vektor Egenvektor
Operationer på vektorer	Skalært produkt vektor produkt blandet produkt Pseudoskalært produkt Dobbelt kryds produkt
Rumtyper	vektor rum affint rum Euklidisk rum Pseudo-euklidisk rum Normeret rum Minkowski plads

matricer

Basale koncepter	Matrix multiplikation Transponeret matrix Hermitisk konjugeret matrix Symmetrisk matrix omvendt matrix Egenværdi Karakteristisk polynomium af en matrix
Særlige matricer	Identitetsmatrix Nul matrix Diagonal matrix lambda matrix
Matrix nedbrydninger	LU nedbrydning Kolesky nedbrydning QR-nedbrydning LUP nedbrydning singular værdi nedbrydning Spektral nedbrydning af en matrix

Andet