Prodotto Matrix
Il prodotto matriciale si riferisce alla moltiplicazione di matrici , inizialmente chiamata “composizione di matrici”.
Prodotto a matrice ordinaria
Questo è il modo più comune per moltiplicare le matrici tra di loro.
In algebra lineare , una matrice A di dimensioni m righe e n colonne (matrice m × n ) rappresenta un'applicazione lineare da uno spazio di dimensione n a uno spazio di dimensione m . Una matrice di colonne V di n righe è una matrice n × 1 e rappresenta un vettore v di uno spazio vettoriale di dimensione n . Il prodotto A × V rappresenta ƒ ( v ).
Se A e B rappresentano rispettivamente le mappe lineari e g , allora A × B rappresenta la composizione delle mappe ƒo g .
Questa operazione viene utilizzata in particolare in meccanica durante i calcoli del torso statico , o nell'elaborazione dei dati per la matrice di adiacenza di un grafico.
Il prodotto di due matrici può essere definito solo se il numero di colonne della prima matrice è uguale al numero di righe della seconda matrice, cioè quando sono di tipo compatibile.
Se è una matrice di tipo ed è una matrice di tipo , allora il loro prodotto , notato è una matrice di tipo data da:
A=(aioj){\ displaystyle A = (a_ {ij})}
(m,non){\ stile di visualizzazione (m, n)}
B=(bioj){\ displaystyle B = (b_ {ij})}
(non,p){\ stile di visualizzazione (n, p)}
AB=(vsioj){\ displaystyle AB = (c_ {ij})}
(m,p){\ stile di visualizzazione (m, p)}![(m, p)](https://wikimedia.org/api/rest_v1/media/math/render/svg/ac9c06c928c28ebca304079c6ded976858428af1)
∀io,j:vsioj=ΣK=1nonaioKbKj=aio1b1j+aio2b2j+⋯+aiononbnonj{\ 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}}![\ 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}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/840716c2745c63bd10c38a0b5ecac966faf0b1ff)
La figura seguente mostra come calcolare i coefficienti e la matrice prodotta se è una matrice di tipo ed è una matrice di tipo .
vs12{\ displaystyle c_ {12}}
vs33{\ displaystyle c_ {33}}
AB{\ stile di visualizzazione AB}
A{\ stile di visualizzazione A}
(4,2){\ stile di visualizzazione (4.2)}
B{\ stile di visualizzazione B}
(2,3){\ stile di visualizzazione (2,3)}![(2.3)](https://wikimedia.org/api/rest_v1/media/math/render/svg/b31c93ba409b1d9834540d2a9fa66e8ab5a3d8dc)
vs12=Σr=12a1rbr2=a11b12+a12b22{\ displaystyle {\ color {BrickRed} c_ {12}} = \ sum _ {r = 1} ^ {2} a_ {1r} b_ {r2} = a_ {11} b_ {12} + a_ {12} b_ {22}}
vs33=Σr=12a3rbr3=a31b13+a32b23{\ displaystyle {\ color {NavyBlue} c_ {33}} = \ sum _ {r = 1} ^ {2} a_ {3r} b_ {r3} = a_ {31} b_ {13} + a_ {32} b_ {23}}
Esempi
(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 \ volte 3 + 0 \ volte -2) & (1 \ volte 4 + 0 \ volte -3) \\ (2 \ volte 3 + -1 \ volte -2) & (2 \ volte 4 + -1 \ volte -3) \ end {pmatrix}} = {\ begin {pmatrix} 3 & 4 \\ 8 & 11 \ end {pmatrix}}}
In generale, la moltiplicazione di matrici non è commutativa , cioè non è uguale a , come mostra l'esempio seguente.
AB{\ stile di visualizzazione AB}
BA{\ displaystyle BA}![BA](https://wikimedia.org/api/rest_v1/media/math/render/svg/5b8efb97e621ab9b49f8498a49704690bdeb2698)
(12043-1)(512334)=(97239){\ displaystyle {\ begin {pmatrix} 1 & 2 & 0 \\ 4 & 3 & -1 \\\ end {pmatrix}} {\ begin {pmatrix} 5 & 1 \\ 2 & 3 \\ 3 & 4 \ \\ end {pmatrix}} = {\ begin {pmatrix}} } 9 & 7 \\ 23 & 9 \\\ end {pmatrix}}}![{\ begin {pmatrix} 1 & 2 & 0 \\ 4 & 3 & -1 \\\ end {pmatrix}} {\ begin {pmatrix} 5 & 1 \\ 2 & 3 \\ 3 & 4 \\\ end {pmatrix}} = {\ inizio {pmatrix} 9 & 7 \ \ 23 & 9 \\\ fine {pmatrix}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/65629483342105d447b68ac133981a8f98a59f83)
mentre
(512334)(12043-1)=(913-11413-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 { matrice}}}
Moltiplicazione di matrici per blocco
Se consideriamo le matrici and , dove e sono matrici che soddisfano:
M=(ABVSD){\ displaystyle M = \ left ({\ begin {smallmatrix} A&B \\ C&D \ end {smallmatrix}} \ right)}
NON=(A'B'VS'D'){\ displaystyle N = \ left ({\ begin {smallmatrix} A '& B' \\ C '& D' \ end {smallmatrix}} \ right)}
A,A',B,B',VS,VS'{\ stile di visualizzazione A, A ', B, B', C, C '}
D,D'{\ stile di visualizzazione D, D '}![D, D'](https://wikimedia.org/api/rest_v1/media/math/render/svg/2e2b887c754013186ad0fb182a15f9f1f5084d56)
- Il numero di colonne di e è uguale al numero di righe di andA{\ stile di visualizzazione A}
VS{\ stile di visualizzazione C}
A'{\ stile di visualizzazione A '}
B'{\ stile di visualizzazione B '}
- Il numero di colonne di e è uguale al numero di righe di andB{\ stile di visualizzazione B}
D{\ stile di visualizzazione D}
VS'{\ stile di visualizzazione C '}
D'{\ stile di visualizzazione D '}
allora abbiamo l'uguaglianza
MNON=(AA'+BVS'AB'+BD'VSA'+DVS'VSB'+DD'){\ displaystyle MN = {\ begin {pmatrix} AA '+ BC' & AB '+ BD' \\ CA '+ DC' & CB '+ DD' \ end {pmatrix}}}![MN = {\ begin {pmatrix} AA '+ BC' & AB '+ BD' \\ CA '+ DC' & CB '+ DD' \ end {pmatrix}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/53710a3affb017d7f918508559f02fdcec6211c9)
Si noti l'analogia tra il prodotto della matrice a blocchi e il prodotto di due matrici quadrate di ordine 2.
NB: non si definisce così una nuova forma di moltiplicazione di matrici. Questo è semplicemente un metodo per calcolare il prodotto di matrice ordinaria che può semplificare i calcoli.
Prodotto Hadamard
Per due matrici dello stesso tipo, abbiamo il prodotto di Hadamard o il prodotto componente per componente. Il prodotto di Hadamard di due matrici e di tipo , indicato con A · B = ( c ij ) , è una matrice di tipo data da
A=(aioj){\ displaystyle A = (a_ {ij})}
B=(bioj){\ displaystyle B = (b_ {ij})}
(m,non){\ stile di visualizzazione (m, n)}
(m,non){\ stile di visualizzazione (m, n)}![(m, n)](https://wikimedia.org/api/rest_v1/media/math/render/svg/274d4857135a7d28a94ba9ee8135779615084d43)
vsioj=aioj×bioj.{\ displaystyle c_ {ij} = a_ {ij} \ volte b_ {ij}.}![{\ displaystyle c_ {ij} = a_ {ij} \ volte b_ {ij}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/dd8ac7a3b16e6e8a6d6d4ca8673fe87b7805190c)
Per esempio :
(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 \ times 0 & 3 \ times 0 & 2 \ times 2 \\ 1 \ times 7 & 0 \ times 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 \ fine {pmatrix}}.}![{\ 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 \ times 0 & 3 \ times 0 & 2 \ times 2 \\ 1 \ times 7 & 0 \ times 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 \ fine {pmatrix}}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/bd6bc1b6f505189f3fd8eb66de3069f2f2a20362)
Questo prodotto è una sottomatrice del prodotto Kronecker (vedi sotto).
Prodotto Kronecker
Per due matrici arbitrarie e , abbiamo il prodotto tensoriale o prodotto di Kronecker A ⊗ B che è definito da
A=(aioj){\ displaystyle A = (a_ {ij})}
B{\ stile di visualizzazione B}
(a11Ba12B⋯a1nonB⋮⋮⋱⋮am1Bam2B⋯amnonB){\ 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}}}![{\ 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}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ce82af0d71300caa5d6b3eb22a03829433852311)
Se è una matrice di tipo ed è una matrice di tipo, allora A ⊗ B è una matrice di tipo . Anche questa moltiplicazione non è commutativa.
A{\ stile di visualizzazione A}
(m,non){\ stile di visualizzazione (m, n)}
B{\ stile di visualizzazione B}
(p,r){\ stile di visualizzazione (p, r)}
(mp,nonr){\ stile di visualizzazione (mp, nr)}![(mp, nr)](https://wikimedia.org/api/rest_v1/media/math/render/svg/310c556aea073ccc663b4bfe785f51096c638544)
per esempio
(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 \\\ end {pmatrix}} \ otimes {\ begin {pmatrix} 0 & 3 \\ 2 & 1 \\\ end {pmatrix}} = {\ begin {pmatrix} 1 \ times 0 & 1 \ times 3 & 2 \ times 0 & 2 \ times 3 \\ 1 \ times 2 & 1 \ times 1 & 2 \ times 2 & 2 \ times 1 \\ 3 \ volte 0 & 3 \ volte 3 & 1 \ volte 0 & 1 \ volte 3 \\ 3 \ volte 2 & 3 \ volte 1 & 1 \ volte 2 & 1 \ volte 1 \\\ fine {pmatrix}} = {\ inizio {pmatrix} 0 & 3 & 0 & 6 \\ 2 & 1 & 4 & 2 \\ 0 & 9 & 0 & 3 \\ 6 & 3 & 2 & 1 \ end {pmatrix}}}![{\ begin {pmatrix} 1 & 2 \\ 3 & 1 \\\ end {pmatrix}} \ otimes {\ begin {pmatrix} 0 & 3 \\ 2 & 1 \\\ end {pmatrix}} = {\ begin {pmatrix} 1 \ times 0 & 1 \ times 3 & 2 \ times 0 & 2 \ times 3 \\ 1 \ times 2 & 1 \ times 1 & 2 \ times 2 & 2 \ times 1 \\ 3 \ times 0 & 3 \ times 3 & 1 \ times 0 & 1 \ times 3 \\ 3 \ times 2 & 3 \ times 1 & 1 \ times 2 & 1 \ times 1 \\\ end {pmatrix}} = {\ begin {pmatrix} 0 & 3 & 0 & 6 \\ 2 & 1 & 4 & 2 \\ 0 & 9 & 0 & 3 \\ 6 & 3 & 2 & 1 \ fine {pmatrix}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4154a0b949d4b4b1f74eceab3c62941fd54ea717)
.
Se e sono le matrici delle mappe lineari V 1 → W 1 e V 2 → W 2 , rispettivamente, allora A ⊗ B rappresenta il prodotto tensoriale delle due mappe , V 1 ⊗ V 2 → W 1 ⊗ W 2 .
A{\ stile di visualizzazione A}
B{\ stile di visualizzazione B}![B](https://wikimedia.org/api/rest_v1/media/math/render/svg/47136aad860d145f75f3eed3022df827cee94d7a)
Proprietà comuni
Le tre moltiplicazioni matriciali precedenti sono associative
A×(B×VS)=(A×B)×VS{\ displaystyle A \ times (B \ times C) = (A \ times B) \ times C}![A \ volte (B \ volte C) = (A \ volte B) \ volte C](https://wikimedia.org/api/rest_v1/media/math/render/svg/5d99e08fa401b6f5835113dc2f3313a38f8088bb)
,
distributivo rispetto all'addizione:
A×(B+VS)=A×B+A×VS{\ displaystyle A \ volte (B + C) = A \ volte B + A \ volte C}
(A+B)×VS=A×VS+B×VS{\ displaystyle (A + B) \ volte C = A \ volte C + B \ volte C}
e compatibile con la moltiplicazione per uno scalare:
vs(A×B)=(vsA)×B=A×(vsB){\ displaystyle c (A \ volte B) = (cA) \ volte B = A \ volte (cB)}![c (A \ volte B) = (cA) \ volte B = A \ volte (cB)](https://wikimedia.org/api/rest_v1/media/math/render/svg/82418ab20b35810ecaae0d66f437b06b505ce8c2)
Moltiplicazione per uno scalare
La moltiplicazione scalare di una matrice dà il prodotto
r{\ stile di visualizzazione r}
A=(aioj){\ displaystyle A = (a_ {ij})}![A = (un _ {{ij}})](https://wikimedia.org/api/rest_v1/media/math/render/svg/296ad42d9541f8285979ce822ccb661da56111ca)
rA=(raioj){\ displaystyle rA = (ra_ {ij})}![rA = (ra _ {{ij}})](https://wikimedia.org/api/rest_v1/media/math/render/svg/7d3b2dda4f79509b215ad74b50f0dc2d69c2401a)
.
Se stiamo lavorando con matrici su un anello , allora la moltiplicazione per uno scalare è talvolta chiamata moltiplicazione a sinistra mentre la moltiplicazione a destra è definita da:
Ar=(aiojr){\ displaystyle Ar = (a_ {ij} r)}![Ar = (a _ {{ij}} r)](https://wikimedia.org/api/rest_v1/media/math/render/svg/f2cea9cc38cb0ac15301efc965b9211f7d4a01ea)
.
Quando l'anello fondamentale è un anello commutativo , ad esempio il campo dei reali o dei complessi, le due moltiplicazioni sono identiche.
Tuttavia, se l'anello non è commutativo, come quello dei quaternioni , allora potrebbero essere diversi. per esempio
io(io00j)=(-100K)≠(-100-K)=(io00j)io{\ 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 \\\ end {pmatrix}} i }![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 \\\ end {pmatrix}} i](https://wikimedia.org/api/rest_v1/media/math/render/svg/1615f011be4c6bf032f30ac50a9de707b47f75a5)
Aspetti algoritmici
Moltiplicazione efficiente di due matrici
Il problema che consiste, date due matrici quadrate, di moltiplicarle velocemente, è un problema importante in algoritmica . L'algoritmo che segue dalla definizione ha una complessità temporale in , dove è il numero di righe delle matrici. Un limite inferiore è (perché ciascuno dei coefficienti della matrice deve essere scritto). L'esponente ottimo per la complessità è quindi compreso tra 2 e 3 ma il suo valore esatto è un problema aperto. Molti algoritmi sono stati inventati per questo problema, ad esempio l' algoritmo di Strassen in , il primo ad essere scoperto, e l' algoritmo di Coppersmith-Winograd in . Nel 1993, Bahar et al. ha fornito un algoritmo di moltiplicazione di matrici per matrici rappresentate simbolicamente utilizzando una struttura dati chiamata Algebraic Decision Diagrams (ADD), che è una generalizzazione dei diagrammi decisionali binari .
oh(non3){\ stile di visualizzazione O (n ^ {3})}
non{\ stile di visualizzazione n}
oh(non2){\ stile di visualizzazione O (n ^ {2})}
non2{\ stile di visualizzazione n ^ {2}}
oh(non2,807){\ stile di visualizzazione O (n ^ {2.807})}
oh(non2,376) {\ displaystyle O (n ^ {2,376}) \! \}![{\ displaystyle O (n ^ {2,376}) \! \}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9d90936216dac22435d530ffe341ddd19b31a70f)
Moltiplicazioni di matrici concatenate
Ci diamo una serie di matrici rettangolari e vogliamo calcolare il prodotto (supponiamo che tutte le matrici abbiano una dimensione compatibile, cioè che il prodotto sia ben definito). Essendo il prodotto matriciale associativo , qualsiasi parentesi del prodotto darà lo stesso risultato. Tuttavia, il numero di moltiplicazioni scalari da eseguire dipende dalla parentesi mantenuta se le matrici sono di dimensioni diverse.
⟨A1...,AK⟩{\ displaystyle \ langle A_ {1} \ punti, A_ {k} \ rangle}
A1,non=A1...AK{\ displaystyle A_ {1, n} = A_ {1} \ punti A_ {k}}![{\ displaystyle A_ {1, n} = A_ {1} \ punti A_ {k}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/14bc943da62eb060b7b724652d41e3dd1bf49e55)
Quindi se prendiamo , e
abbiamo = ma il calcolo di richiede 6 moltiplicazioni scalari mentre quello di richiede 18.
A=(a1a2a3){\ 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=(vs1vs2vs3){\ displaystyle C = {\ begin {pmatrix} c_ {1} & c_ {2} & c_ {3} \\\ end {pmatrix}}}
(AB)VS{\ stile di visualizzazione (AB) C}
A(BVS){\ stile di visualizzazione A (BC)}
(AB)VS{\ stile di visualizzazione (AB) C}
A(BVS){\ stile di visualizzazione A (BC)}![{\ stile di visualizzazione A (BC)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1dcc92bb29718d480f29434fcee02fc38d19a176)
Può quindi essere utile eseguire un algoritmo di ottimizzazione del prodotto a matrice concatenata per identificare la parentesi più efficiente prima di eseguire i prodotti effettivi.
Verifica di un prodotto matrice
Per verificare un prodotto matriciale, esistono algoritmi più efficienti del semplice ricalcolo.
Ad esempio, l' algoritmo di Freivalds è un algoritmo probabilistico che consente di verificare il risultato di un prodotto matriciale con la probabilità di errore più bassa desiderata.
oh(non2){\ stile di visualizzazione O (n ^ {2})}![O (n^2)](https://wikimedia.org/api/rest_v1/media/math/render/svg/6cd9594a16cb898b8f2a2dff9227a385ec183392)
Note e riferimenti
-
Alain Connes , Il triangolo dei pensieri , Edizione Odile Jacob, p. 72 .
-
(en) Thomas H. Cormen , Charles E. Leiserson e Ronald L. Rivest , Introduzione agli algoritmi , Paris, Dunod ,2002, XXIX + 1146 pag. ( ISBN 978-2-10-003922-7 , SUDOC 068254024 ) , cap. 28 ("Calcolo matrice").
-
Markus Bläser , “ Moltiplicazione di matrici veloci ”, Teoria dell'informatica , Graduate Surveys , vol. 5,2013, pag. 1-60 ( leggi online ).
-
R. Iris Bahar , Erica A. Frohm , Charles M. Gaona e Gary D. Hachtel , “ Diagrammi decisionali algebrici e loro applicazioni ”, ICCAD '93 Atti della conferenza internazionale IEEE/ACM del 1993 sulla progettazione assistita da computer , IEEE Computer Stampa della società,7 novembre 1993, pag. 188-191 ( ISBN 0818644907 , letto online , consultato il 9 febbraio 2018 )
Vedi anche
Articolo correlato
Addizione di matrice
link esterno
<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">