Înmulțirea matricei

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită la 10 august 2022; verificările necesită 2 modificări .

Înmulțirea matricelor este una dintre operațiile de bază pe matrice . Matricea rezultată din operația de înmulțire se numește produs matriceal . Elementele noii matrice sunt obținute din elementele vechilor matrice conform regulilor ilustrate mai jos .

Matricele și pot fi înmulțite dacă sunt compatibile în sensul că numărul coloanelor matricei este egal cu numărul de rânduri . $A$ $B$ $A$ $B$

Matricele au multe dintre proprietățile de multiplicare algebrică pe care le au numerele obișnuite, cu excepția comutativității .

Pentru matricele pătrate, pe lângă înmulțire, se poate introduce și operația de ridicare a unei matrici la o putere și a matricei inverse .

În timp ce matricele sunt folosite pentru a descrie, în special, transformări ale spațiilor matematice ( rotație , reflexie , întindere și altele), produsul matricelor va descrie compoziția transformărilor .

Definiție

Să fie date două matrice dreptunghiulare și dimensiuni și , respectiv: $A$ $B$ $l\times m$ $m\ori 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}}.

Apoi matricea cu dimensiuni : $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}},

în care:

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

se numește produsul lor .

Operația de înmulțire a două matrice este fezabilă numai dacă numărul de coloane din primul factor este egal cu numărul de rânduri din al doilea; în acest caz se spune că matricele sunt consistente . În special, înmulțirea este întotdeauna fezabilă dacă ambii factori sunt matrici pătrate de același ordin.

Astfel, existența unei opere nu urmează deloc existența unei opere. $AB$ $B.A.$

Ilustrație

Produsul matriceal AB constă din toate combinațiile posibile ale produselor interne ale vectorilor rând ai matricei A și ale vectorilor coloană ai matricei B . Elementul matricei AB cu indici i, j este produsul scalar dintre vectorul i -lea rând al matricei A și vectorul j --lea coloană al matricei B .

Ilustrația din dreapta arată calculul produsului a două matrice A și B , arată cum fiecare intersecție din produsul matriceal corespunde rândurilor matricei A și coloanelor matricei B. Mărimea matricei rezultate este întotdeauna maximul posibil, adică pentru fiecare rând al matricei A și coloană a matricei B există întotdeauna o intersecție corespunzătoare în produsul matricei.

Valorile la intersecțiile marcate cu cercuri vor fi:

${\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}\\{\culoare {Albastru}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{aliniat}}$

În general, produsul matriceal nu este o operație comutativă. De exemplu:

{\overset {3\times 4{\text{ matrix))}{\begin{bmatrix}\cdot &\cdot &\cdot &\cdot \\\cdot &\cdot &\cdot &\cdot \\\color {Albastru}1&\culoare {Albastru}2&\culoare {Albastru}3&\culoare {Albastru}4\\\end{bmatrix}}}{\overset {4\times 5{\text{ matrice}}}{\begin {bmatrix}\cdot &\cdot &\cdot &\color {Roșu}a&\cdot \\\cdot &\cdot &\cdot &\color {Roșu}b&\cdot \\\cdot &\cdot &\cdot & \color {Red}c&\cdot \\\cdot &\cdot &\cdot &\color {Red}d&\cdot \\\end{bmatrix}}}={\overset {3\times 5{\text{ matrice ))}{\begin{bmatrix}\cdot &\cdot &\cdot &\cdot &\cdot \\\cdot &\cdot &\cdot &\cdot &\cdot \\\cdot &\cdot &\cdot &x_ {3,4}&\cdot \\\end{bmatrix}}}

Elementul produsului matricelor de mai sus se calculează după cum urmează $x_{{3,4}}$

x_{3,4}=({\culoare {Albastru}1},{\culoare {Albastru}2},{\culoare {Albastru}3},{\culoare {Albastru}4})\cdot ({\culoare {Roșu}a},{\culoare {Roșu}b},{\culoare {Roșu}c},{\culoare {Roșu}d})={\culoare {Albastru}1}\cdot {\culoare {Roșu} a}+{\culoare {Albastru}2}\cdot {\culoare {Roșu}b}+{\culoare {Albastru}3}\cdot {\color {Roșu}c}+{\culoare {Albastru}4}\ cdot {\culoare {Roșu}d}

Prima coordonată din desemnarea matricei denotă un rând, a doua coordonată denotă o coloană; această ordine este folosită atât pentru indexare, cât și pentru dimensionare. Elementul de la intersecția rândului și coloanei matricei rezultate este produsul scalar al rândului i al primei matrice și al coloanei a i-a a celei de-a doua matrice. Aceasta explică de ce lățimea și înălțimea matricelor înmulțite trebuie să se potrivească: altfel produsul punctual este nedefinit. $x_{{\culoare {Albastru}i}{\culoare {Roșu}j))$ $i$ $j$ $i$ $j$

Discuție

Cel mai ușor este să vedeți motivele pentru regula descrisă a înmulțirii matricei luând în considerare înmulțirea unui vector cu o matrice.

Acesta din urmă este introdus în mod natural pe baza faptului că la descompunerea vectorilor în termeni de bază , acțiunea (orice) operator liniar A dă expresia componentelor vectorului v' = A v :

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

Adică, un operator liniar este reprezentat printr-o matrice, vectorii prin vectori coloană și acțiunea unui operator asupra unui vector prin multiplicarea matriceală a vectorului coloană din stânga cu matricea operatorului (acesta este un caz special de înmulțire a matricei, când una dintre matrice, vectorul coloană, are dimensiunea ). $n\times 1$

(În egală măsură, trecerea la orice bază nouă la schimbarea coordonatelor este reprezentată de o expresie complet similară, doar că în acest caz nu mai este vorba de componentele noului vector din vechea bază, ci de componentele vechiului vector din noua bază. ; în acest caz , elementele matricei de tranziție la noua bază). $v'_{i}$ $A_{{ij}}$

Având în vedere acțiunea secvențială asupra vectorului a doi operatori: mai întâi A , apoi B (sau transformarea bazei A , și apoi transformarea bazei B ), aplicând formula noastră de două ori, obținem:

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

de unde se poate observa că compoziția BA a acțiunii operatorilor liniari A și B (sau o compoziție similară a transformărilor de bază) corespunde unei matrice calculate după regula produsului a matricelor corespunzătoare:

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

Produsul matricelor definite în acest fel se dovedește a fi destul de natural și evident util (oferă o modalitate simplă și universală de a calcula compozițiile unui număr arbitrar de transformări liniare).

Proprietăți

Proprietate asociativă , asociativitate :

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

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

Proprietatea distributivă , distributivitatea în raport cu adunarea :

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

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

Produsul unei matrice și matricea de identitate dintr-un ordin adecvat este egal cu matricea însăși: $\mathbf {E}$

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

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

Produsul dintre o matrice și o matrice zero de dimensiune adecvată este egal cu matricea zero: $\mathbf {0}$

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

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

Dacă și sunt matrici pătrate de același ordin, atunci produsul matriceal are o serie de alte proprietăți. $\mathbf {A}$ $\mathbf {B}$

Înmulțirea matricelor este în general necomutativă :

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

Dacă , atunci matricele și se spune că fac naveta între ele. $\mathbf {AB} =\mathbf {BA}$ $\mathbf {A}$ $\mathbf {B}$

Cele mai simple exemple de matrice de navetă:

orice matrice pătrată - cu ea însăși: (la pătratul matricei); $\mathbf {AA} =\mathbf {AA} =\mathbf {A^{2}}$
orice matrice pătrată — cu matricea identitară de același ordin: ; $\mathbf {AE} =\mathbf {EA} =\mathbf {A}$
orice matrice pătrată — cu o matrice zero de același ordin: ; $\mathbf {A0} =\mathbf {0A} =\mathbf {0}$
orice matrice pătrată nesingulară — cu matricea sa inversă: . $\mathbf {AA^{-1}} =\mathbf {A^{-1}A} =\mathbf {E}$

Determinantul și urma produsului nu depind de ordinea înmulțirii matricei:

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

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

Matrice inversă

O matrice pătrată se numește non- singular ( non- singular ) dacă are o matrice inversă unică astfel încât să fie îndeplinită următoarea condiție: $A$ $A^{{-1}}$

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

În caz contrar, matricea se numește specială ( degenerată ) . $A$

O matrice de ordine este nedegenerată dacă și numai dacă în acest caz există o matrice pătrată de același ordin $A=\stânga[a_{ik}\dreapta]$ $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],

unde este complementul algebric al elementului din determinant $A_{{ik}}$ $a_{{ik}}$ $\det\left[a_{ik}\right].$

Algoritmi de multiplicare rapidă a matricei

Complexitatea calculării produsului matricelor prin definiție este , dar există algoritmi mai eficienți [1] care sunt utilizați pentru matrice mari. Problema vitezei limită de înmulțire a matricelor mari, precum și problema construirii celor mai rapidi și mai stabili algoritmi practici pentru multiplicarea matricelor mari, rămâne una dintre problemele nerezolvate ale algebrei liniare . $\O(n^{3})$

Algoritmul lui Strassen (1969)

Primul algoritm pentru multiplicarea rapidă a matricelor mari a fost dezvoltat de Volker Strassen [2] în 1969. Algoritmul se bazează pe o partiție recursivă a matricelor în blocuri 2X2 . Strassen a demonstrat că matricele 2X2 pot fi înmulțite necomutativ cu șapte înmulțiri, astfel încât șapte înmulțiri sunt efectuate la fiecare pas al recursiei în loc de opt. Ca urmare, complexitatea asimptotică a acestui algoritm este . Dezavantajul acestei metode este complexitatea mai mare a programării în comparație cu algoritmul standard, stabilitatea numerică slabă și o cantitate mai mare de memorie utilizată. Au fost dezvoltați o serie de algoritmi bazați pe metoda Strassen, care îmbunătățesc stabilitatea numerică, rata constantă și alte caracteristici. Cu toate acestea, datorită simplității sale, algoritmul Strassen rămâne unul dintre algoritmii practici pentru multiplicarea matricelor mari. Strassen a mai avansat următoarea conjectura Strassen : pentru arbitrar mic , există un algoritm care, pentru numere naturale suficient de mari n , garantează înmulțirea a două matrici de mărime în operații.

O(n^{\log _{2}7})\aproximativ O(n^{2,81})

\varepsilon >0

n\ ori n

O(n^{2+\varepsilon })

Îmbunătățiri suplimentare ale exponentului ω pentru viteza de multiplicare a matricei

În viitor, estimările ratei de multiplicare a matricelor mari au fost îmbunătățite de multe ori. Cu toate acestea, acești algoritmi au fost teoretici, în mare parte aproximativi. Din cauza instabilității algoritmilor de multiplicare aproximativă, aceștia nu sunt utilizați în prezent în practică.

Algoritmul lui Pan (1978)

În 1978 Pan [3] și-a propus propria metodă de înmulțire a matricei, a cărei complexitate era Θ(n 2,78041 ) .

Algoritmul lui Beanie (1979)

În 1979, un grup de oameni de știință italieni condus de Bini [4] a dezvoltat un algoritm pentru multiplicarea matricelor folosind tensori. Complexitatea sa este Θ(n 2,7799 ) .

Algoritmi Schönhage (1981)

În 1981 Schönhage [5] a introdus o metodă care funcționează cu o rată de Θ(n 2.695 ) . Estimarea se obține folosind o abordare numită înmulțire parțială a matricei . Mai târziu, a reușit să obțină estimarea Θ(n 2,6087 ) . Apoi Schönhage a obținut estimarea complexității Θ(n 2.548 ) pe baza metodei sumelor directe . Romani a putut face downgrade la Θ(n 2.5166 ) , în timp ce Pan a putut să facă downgrade la Θ(n 2.5161 ) .

Algoritmul Coppersmith-Winograd (1990)

În 1990, Coppersmith și Winograd [6] au publicat un algoritm care, așa cum a fost modificat de Williams Wasilewska [7] în 2011, înmulțește matrice cu o rată de O(n 2,3727 ) . Acest algoritm folosește idei similare cu algoritmul lui Strassen. Până în prezent, modificările algoritmului Coppersmith-Winograd sunt cele mai asimptotic rapide. Dar faptul că îmbunătățirile obținute sunt neglijabile ne permite să vorbim despre existența „barierei Coppersmith-Winograd” în estimările asimptotice ale vitezei algoritmilor. Algoritmul Coppersmith-Winograd este eficient doar pe matrici de dimensiuni astronomice și nu poate fi aplicat în practică.

Legătura cu teoria grupurilor (2003)

În 2003, Koch și colaboratorii au considerat algoritmii Strassen și Coppersmith-Winograd în lucrările lor [8] în contextul teoriei grupurilor . Ei au arătat că conjectura lui Strassen este validă (adică, complexitatea minimă este mărginită pentru orice ) dacă una dintre ipotezele teoriei grupurilor [9] este satisfăcută .

O(n^{2+\epsilon })

\epsilon

Puterile matricelor

Matricele pătrate pot fi înmulțite de multe ori cu ele însele în același mod ca numerele obișnuite, deoarece au același număr de rânduri și coloane. O astfel de înmulțire secvențială poate fi numită ridicarea unei matrici la o putere - acesta va fi un caz special al înmulțirii obișnuite a mai multor matrici. Matricele dreptunghiulare au un număr diferit de rânduri și coloane, astfel încât nu pot fi niciodată ridicate la o putere. O matrice n × n A ridicată la o putere este definită prin formula

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

și are următoarele proprietăți ( λ este ceva scalar):

Grad zero:

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

unde E este matricea de identitate . Acest lucru este analog cu faptul că puterea zero a oricărui număr este egală cu unu.

Înmulțirea cu un scalar:

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

Determinant:

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

Cel mai simplu mod de a calcula gradul unei matrice este de a înmulți matricea A k ori cu rezultatul înmulțirii anterioare, pornind de la matricea de identitate, așa cum se face adesea pentru scalari. Pentru matricele diagonalizabile , există o metodă mai bună bazată pe utilizarea descompunerii spectrale a matricei A. O altă metodă, bazată pe teorema Hamilton-Cayley , construiește o expresie mai eficientă pentru Ak , în care scalarul este ridicat la puterea necesară , și nu întreaga matrice .

Matricele diagonale constituie un caz special . Deoarece produsul matricelor diagonale se reduce la înmulțirea elementelor diagonale corespunzătoare, atunci puterea k -a a matricei diagonale A constă din elementele ridicate la puterea necesară:

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

Astfel, nu este dificil să ridici o matrice diagonală la o putere. Când ridicați o matrice arbitrară (nu neapărat diagonală) la o putere, este adesea util să folosiți mai întâi proprietățile matricelor diagonalizabile .

Folosind înmulțirea matricelor și exponențiarea matricelor, pot fi definite alte operații pe matrice. De exemplu, exponentul matricei poate fi definit în termenii unei serii de puteri , logaritmul matricei poate fi definit ca inversul exponentului matricei și așa mai departe.

Vezi și

Literatură

Korn G., Korn T. Matrix Algebra and Matrix Calculus // Manual de matematică. - editia a 4-a. - M . : Nauka, 1978. - S. 392-394.

Note

↑ Colecția cibernetică. Seria noua. Problema. 25. Sat. articole 1983 - 1985: Per. din engleza. - M .: Mir, 1988 - V.B. Alexev. Complexitatea înmulțirii matriceale. Revizuire.
↑ Strassen V. Eliminarea gaussiană nu este optimă // Număr . 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, algoritmul lui Strassen nu este optim - tehnică triliniară de agregare, unire și anulare pentru construirea de algoritmi rapidi pentru operații cu matrice. — Proc. Al 19-lea simpozion anual despre fundamentele informaticii, Ann Arbor, Michigan, 1978
↑ Bini D., Capovani M., Lotti G., Romani F. — complexitate pentru înmulțirea matriceală aproximativă. - informa. proces. Lett., 1979 $O(n^{2,7799})$
↑ Schonhage A. Înmulțirea matriceală parțială și totală. — SIAM J. Comput., 1981
↑ Don Coppersmith și Shmuel Winograd. Înmulțirea matricelor prin progresii aritmetice. Journal of Symbolic Computation , 9:251-280, 1990.
↑ Williams, Virginia (2011), Multiplying matices in O (n 2.3727 time Arhivat la 26 octombrie 2014 la Wayback Machine
↑ Algoritmi teoretici de grup pentru înmulțirea matricelor . Preluat la 26 septembrie 2009. Arhivat din original la 6 august 2011. (nedefinit)
↑ Către un algoritm optim pentru multiplicarea matricelor (link downlink) . Consultat la 26 septembrie 2009. Arhivat din original la 31 martie 2010. (nedefinit)

Vectori și matrici

Vectori

Noțiuni de bază	Vector în geometrie Bază Baza ortogonala Coordonatele vectoriale Coliniaritate Ortogonalitatea Dependență liniară Spațiu coloane
Tipuri de vectori	Vector unitar Vector axial vector izotrop Normal Coliniaritate Vector zero Vector rază Vector propriu
Operații pe vectori	Produs scalar produs vectorial produs mixt Produs pseudoscalar Produs dublu cruce
Tipuri de spațiu	spațiu vectorial spatiu afin Spațiul euclidian Spațiul pseudo-euclidian Spațiu normat Spațiul Minkowski

matrici

Noțiuni de bază	Înmulțirea matricei Matrice transpusă Matricea conjugată hermitiană Matricea simetrică matrice inversă Valoare proprie Polinom caracteristic al unei matrice
Matrici speciale	Matrice de identitate Matrice zero Matricea diagonală matricea lambda
Descompuneri de matrice	descompunerea LU Descompunerea Cholesky Descompunerea QR Descompunerea LUP descompunerea unei valori singulare Descompunerea spectrală a unei matrice

Alte