Matrise produkt
Det matriseprodukt refererer til multiplikasjon av matriser , opprinnelig kalt den “preparat av arrays”.
Vanlig matriksprodukt
Dette er den vanligste måten å multiplisere matriser mellom seg.
I lineær algebra representerer en matrise A med dimensjoner m rader og n kolonner ( m × n matrise ) et lineært kart ƒ fra et rom med dimensjon n til et rom med dimensjon m . En kolonnematrise V på n rader er en n × 1 matrise , og representerer en vektor v i et vektorrom med dimensjonen n . Produktet A × V representerer ƒ ( v ).
Hvis A og B representerer de lineære kartene henholdsvis ƒ og g , representerer A × B sammensetningen av kartene ƒo g .
Denne operasjonen blir brukt spesielt i mekanikk under statiske torsor beregninger , eller i databehandlings for naboskapsmatrisen av en graf.
Produktet av to matriser kan bare defineres hvis antall kolonner i den første matrisen er det samme som antall rader i den andre matrisen, det vil si når de er av kompatibel type.
Hvis er en typematrise og er en typematrise , er deres produkt , bemerket , en typematrise gitt av:
PÅ=(påJegj){\ displaystyle A = (a_ {ij})}(m,ikke){\ displaystyle (m, n)}B=(bJegj){\ displaystyle B = (b_ {ij})}(ikke,s){\ displaystyle (n, p)}PÅB=(vs.Jegj){\ displaystyle AB = (c_ {ij})}(m,s){\ displaystyle (m, p)}
∀Jeg,j:vs.Jegj=∑k=1ikkepåJegkbkj=påJeg1b1j+påJeg2b2j+⋯+påJegikkebikkej{\ displaystyle \ forall i, j: c_ {ij} = \ sum _ {k = 1} ^ {n} a_ {ik} b_ {kj} = a_ {i1} b_ {1j} + a_ {i2} b_ { 2j} + \ cdots + a_ {in} b_ {nj}}Følgende figur viser hvordan man beregner koeffisientene og matrisen som produseres hvis er en typematrise , og er en typematrise .
vs.12{\ displaystyle c_ {12}}vs.33{\ displaystyle c_ {33}}PÅB{\ displaystyle AB}PÅ{\ displaystyle A}(4,2){\ displaystyle (4.2)}B{\ displaystyle B}(2,3){\ displaystyle (2,3)}
vs.12=∑r=12på1rbr2=på11b12+på12b22{\ displaystyle {\ color {BrickRed} c_ {12}} = \ sum _ {r = 1} ^ {2} a_ {1r} b_ {r2} = a_ {11} b_ {12} + a_ {12} b_ {22}}
vs.33=∑r=12på3rbr3=på31b1. 3+på32b23{\ displaystyle {\ color {NavyBlue} c_ {33}} = \ sum _ {r = 1} ^ {2} a_ {3r} b_ {r3} = a_ {31} b_ {13} + a_ {32} b_ {23}}
Eksempler
(102-1)×(34-2-3){\ displaystyle {\ begin {pmatrix} 1 & 0 \\ 2 & -1 \ end {pmatrix}} \ times {\ begin {pmatrix} 3 & 4 \\ - 2 & -3 \\\ end {pmatrix}} }
=((1×3+0×-2)(1×4+0×-3)(2×3+-1×-2)(2×4+-1×-3))=(34811){\ displaystyle = {\ begin {pmatrix} (1 \ ganger 3 + 0 \ ganger -2) & (1 \ ganger 4 + 0 \ ganger -3) \\ (2 \ ganger 3 + -1 \ ganger -2) & (2 \ times 4 + -1 \ times -3) \ end {pmatrix}} = {\ begin {pmatrix} 3 & 4 \\ 8 & 11 \ end {pmatrix}}}
Generelt er matriksmultiplikasjon ikke kommutativ , det vil si at den ikke er lik , som eksemplet nedenfor viser.
PÅB{\ displaystyle AB}BPÅ{\ displaystyle BA}
(12043-1)(512334)=(97239){\ displaystyle {\ begin {pmatrix} 1 & 2 & 0 \\ 4 & 3 & -1 \\\ slutt {pmatrix}} {\ begin {pmatrix} 5 & 1 \\ 2 & 3 \\ 3 & 4 \ \\ end {pmatrix}} = {\ begin {pmatrix}}} 9 og 7 \\ 23 & 9 \\\ end {pmatrix}}} samtidig som
(512334)(12043-1)=(91. 3-1141. 3-31918-4){\ displaystyle {\ begin {pmatrix} 5 & 1 \\ 2 & 3 \\ 3 & 4 \\\ end {pmatrix}} {\ begin {pmatrix} 1 & 2 & 0 \\ 4 & 3 & -1 \ \\ end {pmatrix}} = {\ begin {pmatrix}} = {\ begin {pmatrix}} 9 & 13 & -1 \\ 14 & 13 & -3 \\ 19 & 18 & -4 \\\ end { pmatrix}}}
Multiplikasjon av matriser per blokk
Hvis vi vurderer matriser og , hvor og er matriser tilfredsstillende:
M=(PÅBVSD){\ displaystyle M = \ left ({\ begin {smallmatrix} A&B \\ C&D \ end {smallmatrix}} \ right)}IKKE=(PÅ′B′VS′D′){\ displaystyle N = \ left ({\ begin {smallmatrix} A '& B' \\ C '& D' \ end {smallmatrix}} \ right)}PÅ,PÅ′,B,B′,VS,VS′{\ displaystyle A, A ', B, B', C, C '}D,D′{\ displaystyle D, D '}
- Antall kolonner med og er lik antall rader med ogPÅ{\ displaystyle A}VS{\ displaystyle C}PÅ′{\ displaystyle A '}B′{\ displaystyle B '}
- Antall kolonner med og er lik antall rader med ogB{\ displaystyle B}D{\ displaystyle D}VS′{\ displaystyle C '}D′{\ displaystyle D '}
vi har da likeverd
MIKKE=(PÅPÅ′+BVS′PÅB′+BD′VSPÅ′+DVS′VSB′+DD′){\ displaystyle MN = {\ begin {pmatrix} AA '+ BC' & AB '+ BD' \\ CA '+ DC' & CB '+ DD' \ end {pmatrix}}}Legg merke til analogien mellom blokkmatriseproduktet og produktet av to firkantede matriser av ordre 2.
NB: man definerer altså ikke en ny form for multiplikasjon av matriser. Dette er ganske enkelt en metode for å beregne det vanlige matriksproduktet som kan forenkle beregningene.
Hadamard-produkt
For to matriser av samme type har vi Hadamard- produktet eller komponent for komponentprodukt. Den Hadamard produkt av to matriser og av type , betegnet A · B = ( c ij ) , er en type matrise gitt etter
PÅ=(påJegj){\ displaystyle A = (a_ {ij})}B=(bJegj){\ displaystyle B = (b_ {ij})}(m,ikke){\ displaystyle (m, n)}(m,ikke){\ displaystyle (m, n)}
vs.Jegj=påJegj×bJegj.{\ displaystyle c_ {ij} = a_ {ij} \ times b_ {ij}.}For eksempel :
(132100122)⋅(002750211)=(1×03×02×21×70×50×01×22×12×1)=(004700222).{\ displaystyle {\ begin {pmatrix} 1 & 3 & 2 \\ 1 & 0 & 0 \\ 1 & 2 & 2 \ end {pmatrix}} \ cdot {\ begin {pmatrix} 0 & 0 & 2 \\ 7 & 5 & 0 \ 2 & 1 & 1 \ end {pmatrix}} = {\ begin {pmatrix} 1 \ ganger 0 & 3 \ ganger 0 & 2 \ ganger 2 \\ 1 \ ganger 7 & 0 \ ganger 5 & 0 \ times 0 \\ 1 \ times 2 & 2 \ times 1 & 2 \ times 1 \ end {pmatrix}} = {\ begin {pmatrix} 0 & 0 & 4 \\ 7 & 0 & 0 \\ 2 & 2 & 2 \ end {pmatrix}}.}Dette produktet er en undermatrise av Kronecker-produktet (se nedenfor).
Kronecker-produkt
For to vilkårlige matriser og har vi tensorproduktet eller Kronecker-produktet A ⊗ B som er definert av
PÅ=(påJegj){\ displaystyle A = (a_ {ij})}B{\ displaystyle B}
(på11Bpå12B⋯på1ikkeB⋮⋮⋱⋮påm1Bpåm2B⋯påmikkeB){\ displaystyle {\ begin {pmatrix} a_ {11} B & a_ {12} B & \ cdots & a_ {1n} B \\\ vdots & \ vdots & \ ddots & \ vdots \\ a_ {m1} B & a_ {m2} B & \ cdots & a_ {mn} B \ end {pmatrix}}}Hvis er en typematrise og er en typematrise, så er A ⊗ B en typematrise . Igjen er denne multiplikasjonen ikke kommutativ.
PÅ{\ displaystyle A}(m,ikke){\ displaystyle (m, n)}B{\ displaystyle B}(s,r){\ displaystyle (p, r)}(ms,ikker){\ displaystyle (mp, nr)}
for eksempel
(1231)⊗(0321)=(1×01×32×02×31×21×12×22×13×03×31×01×33×23×11×21×1)=(0306214209036321){\ displaystyle {\ begin {pmatrix} 1 & 2 \\ 3 & 1 \\\ slutt {pmatrix}} \ tid {\ begin {pmatrix} 0 og 3 \\ 2 & 1 \\\ slutt {pmatrix}} = {\ begin {pmatrix} 1 \ ganger 0 & 1 \ ganger 3 & 2 \ ganger 0 & 2 \ ganger 3 \\ 1 \ ganger 2 & 1 \ ganger 1 & 2 \ ganger 2 og 2 \ ganger 1 \\ 3 \ ganger 0 & 3 \ ganger 3 & 1 \ ganger 0 & 1 \ ganger 3 \\ 3 \ ganger 2 & 3 \ ganger 1 & 1 \ ganger 2 & 1 \ ganger 1 \\\ slutt {pmatrix}} = {\ begin {pmatrix} 0 & 3 & 0 & 6 \\ 2 & 1 & 4 & 2 \\ 0 & 9 & 0 & 3 \\ 6 & 3 & 2 & 1 \ end {pmatrix}}}.
Dersom og er de matriser av lineær transformasjon V 1 → W 1 og V- 2 → W 2 , henholdsvis, deretter A ⊗ B representerer tensorprodukt av de to kartene , V 1 ⊗ V 2 → W 1 ⊗ W 2 .
PÅ{\ displaystyle A}B{\ displaystyle B}
Vanlige egenskaper
De tre foregående matrisemultiplikasjonene er assosiative
PÅ×(B×VS)=(PÅ×B)×VS{\ displaystyle A \ times (B \ times C) = (A \ times B) \ times C},
distribuerende med hensyn til tillegg:
PÅ×(B+VS)=PÅ×B+PÅ×VS{\ displaystyle A \ times (B + C) = A \ times B + A \ times C}
(PÅ+B)×VS=PÅ×VS+B×VS{\ displaystyle (A + B) \ times C = A \ times C + B \ times C}
og kompatibel med multiplikasjon med en skalar:
vs.(PÅ×B)=(vs.PÅ)×B=PÅ×(vs.B){\ displaystyle c (A \ times B) = (cA) \ times B = A \ times (cB)}Multiplikasjon med en skalar
Den skalære multiplikasjonen av en matrise gir produktet
r{\ displaystyle r}PÅ=(påJegj){\ displaystyle A = (a_ {ij})}
rPÅ=(rpåJegj){\ displaystyle rA = (ra_ {ij})}.
Hvis vi jobber med matriser på en ring , blir multiplikasjonen med en skalar noen ganger kalt venstre multiplikasjon mens høyre multiplikasjon er definert av:
PÅr=(påJegjr){\ displaystyle Ar = (a_ {ij} r)}.
Når den grunnleggende ringen er en kommutativ ring , for eksempel feltet reals eller komplekser, er de to multiplikasjonene identiske.
Imidlertid, hvis ringen ikke er kommutativ, slik som for quaternions , så kan de være forskjellige. for eksempel
Jeg(Jeg00j)=(-100k)≠(-100-k)=(Jeg00j)Jeg{\ displaystyle i {\ begin {pmatrix} i & 0 \\ 0 & j \\\ end {pmatrix}} = {\ begin {pmatrix} -1 & 0 \\ 0 & k \\\ end {pmatrix}} \ neq {\ begin {pmatrix} -1 & 0 \\ 0 & -k \\\ end {pmatrix}} = {\ begin {pmatrix} i & 0 \\ 0 & j \\\ slutt {pmatrix}} i }Algoritmiske aspekter
Effektiv multiplikasjon av to matriser
Problemet som består, gitt to firkantede matriser, for å multiplisere dem raskt, er et viktig problem i algoritmikk . Algoritmen som følger fra definisjonen har en tidskompleksitet i , hvor er antall rader i matrisene. En nedre grense er (fordi hver av koeffisientene til matrisen må skrives). Den optimale eksponenten for kompleksiteten er derfor mellom 2 og 3, men den eksakte verdien er et åpent problem. Mange algoritmer er oppfunnet for dette problemet, for eksempel Strassen-algoritmen i , den første som ble oppdaget, og Coppersmith-Winograd-algoritmen i . I 1993, Bahar et al. ga en matrisemultiplikasjonsalgoritme for matriser symbolsk representert ved hjelp av en datastruktur kalt Algebraic Decision Diagrams (ADD), som er en generalisering av binære beslutningsdiagrammer .
O(ikke3){\ displaystyle O (n ^ {3})}ikke{\ displaystyle n}O(ikke2){\ displaystyle O (n ^ {2})}ikke2{\ displaystyle n ^ {2}}O(ikke2,807){\ displaystyle O (n ^ {2 807})}O(ikke2,376) {\ displaystyle O (n ^ {2,376}) \! \}
Kjedet matriks multiplikasjoner
Vi gir oss selv en serie med rektangulære matriser, og vi vil beregne produktet (vi antar at alle matrisene har en kompatibel størrelse, det vil si at produktet er veldefinert). Matriseproduktet er assosiativt , hvilken som helst parentes av produktet gir det samme resultatet. Antall skalære multiplikasjoner som skal utføres, avhenger imidlertid av parentesen som beholdes hvis matrisene er av forskjellige størrelser.
⟨PÅ1...,PÅk⟩{\ displaystyle \ langle A_ {1} \ prikker, A_ {k} \ rangle}PÅ1,ikke=PÅ1...PÅk{\ displaystyle A_ {1, n} = A_ {1} \ prikker A_ {k}}
Så hvis vi tar , og
vi har = men beregningen av krever 6 skalar multiplikasjoner mens den for krever 18.
PÅ=(på1på2på3){\ displaystyle A = {\ begin {pmatrix} a_ {1} & a_ {2} & a_ {3} \\\ end {pmatrix}}}B=(b1b2b3){\ displaystyle B = {\ begin {pmatrix} b_ {1} \\ b_ {2} \\ b_ {3} \\\ end {pmatrix}}}VS=(vs.1vs.2vs.3){\ displaystyle C = {\ begin {pmatrix} c_ {1} & c_ {2} & c_ {3} \\\ end {pmatrix}}}(PÅB)VS{\ displaystyle (AB) C}PÅ(BVS){\ displaystyle A (BC)}(PÅB)VS{\ displaystyle (AB) C}PÅ(BVS){\ displaystyle A (BC)}
Det kan derfor være nyttig å kjøre en sammenkoblet algoritme for matriseproduktoptimalisering for å identifisere den mest effektive parentesen før du utfører de faktiske produktene.
Verifisering av et matriksprodukt
For å verifisere et matriksprodukt, er det mer effektive algoritmer enn bare å beregne det på nytt.
For eksempel er Freivalds-algoritmen en sannsynlighetsalgoritme som gjør det mulig å verifisere resultatet av et matriksprodukt med så lav sannsynlighet for feil som ønsket.
O(ikke2){\ displaystyle O (n ^ {2})}
Merknader og referanser
-
Alain Connes , Tankens trekant , Odile Jacob Edition, s. 72 .
-
(en) Thomas H. Cormen , Charles E. Leiserson og Ronald L. Rivest , Introduksjon til algoritmikk , Paris, Dunod ,2002, xxix + 1146 s. ( ISBN 978-2-10-003922-7 , SUDOC 068254024 ) , kap. 28 ("Matriseberegning").
-
Markus Bläser , “ Fast Matrix Multiplication ”, Theory of Computing, Graduate Surveys , vol. 5,2013, s. 1-60 ( les online ).
-
R. Iris Bahar , Erica A. Frohm , Charles M. Gaona og Gary D. Hachtel , “ Algebraic decision diagrams and their applications ”, ICCAD '93 Proceedings of the 1993 IEEE / ACM international conference on Computer-aided design , IEEE Computer Society Press,7. november 1993, s. 188–191 ( ISBN 0818644907 , lest online , åpnet 9. februar 2018 )
Se også
Relatert artikkel
Matrisetilsetning
Eksterne linker
<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">