Înmulțirea matricilor
![](https://upload.wikimedia.org/wikipedia/commons/thumb/1/18/Matrix_multiplication_qtl1.svg/220px-Matrix_multiplication_qtl1.svg.png)
În matematică, în special în algebra liniară, înmulțirea matricilor sau înmulțirea matricială[1] este o operație binară care produce o matrice din două matrici. La înmulțirea matricială, numărul de coloane din prima matrice trebuie să fie egal cu numărul de linii din a doua matrice. Matricea rezultată, cunoscută sub numele de produs matricial, are numărul de linii ale primei matrice și numărul de coloane ale celei de-a doua matrice. Produsul matricilor A și B este notat AB.[2]
Înmulțirea matricială a fost descrisă pentru prima dată de matematicianul francez Jacques Philippe Marie Binet în 1812,[3] pentru a reprezenta compunerea funcțiilor(d) de transformări liniare care sunt reprezentate cu ajutorul matricilor. Astfel, înmulțirea matricială a devenit un instrument de bază al algebrei liniare și, ca atare, are numeroase aplicații în multe domenii ale matematicii, precum și în matematica aplicată, statistică, fizică, economie și inginerie.[4][5] Calculul produselor matriciale este o operație centrală în toate aplicațiile algebrei liniare.
Notație
[modificare | modificare sursă]În acest articol convențiile privind notațiile sunt următoarele: matricile sunt reprezentate prin litere majuscule grase (bold), de exemplu A; vectorii cu litere minuscule grase, de exemplu a; iar elementele vectorilor și matricilor cu italice, de exemplu A sau a. Notația indexată este adesea cel mai clar mod de a exprima definițiile și este notația standard folosit în literatura de specialitate. Linia din matrice este indicată de indicele i, iar coloana de indicele j. Elementul matricei A este indicat prin (A)ij, Aij sau aij. Prin excepție, un singur indice, de exemplu A1, A2, se folosește pentru a indica o matrice (nu un element al unei matrice) dintr-o colecție de matrici.
Definiție
[modificare | modificare sursă]Dacă A este o matrice m × n iar B este o matrice n × p,
Produsul matricial C = AB (notat fără punct sau semnul înmulțirii) este definit ca fiind matricea m × p [6][7][8][9]
asfel încât
pentru i = 1, ..., m și j = 1, ..., p.
Adică elementul cij al produsului se obține prin înmulțirea termen cu termen a elementelor din linia i a matricei A cu cele din coloana j a matricei B și sumând aceste n produse. Altfel spus, cij este produsul scalar al liniei i a matricei A cu coloana j a matricei B.
Prin urmare AB poate fi scris și ca
Astfel produsul AB este definit dacă și numai dacă numărul de coloane din A este egal cu numărul de linii din B,[2] în acest caz n.
În majoritatea cazurilor elementele matricilor sunt numere, dar pot fi orice fel de obiecte matematice pentru care sunt definite o adunare și o înmulțire, care sunt asociative, adunarea să fie comutativă, iar înmulțirea să fie distributivă în raport cu adunarea. În particular, elementele pot fi ele înseși matrici.
Ilustrare
[modificare | modificare sursă]![](https://upload.wikimedia.org/wikipedia/commons/thumb/e/eb/Matrix_multiplication_diagram_2.svg/220px-Matrix_multiplication_diagram_2.svg.png)
Figura din dreapta ilustrează schematic produsul a două matrice A și B, arătând cum fiecare intersecție din matricea produsului corespunde cu o linie din A și o coloană din B.
Valorile de la intersecții, marcate cu cercuri în figura din dreapta, sunt:
Principalele aplicații
[modificare | modificare sursă]Istoric, înmulțirea matricilor a fost introdusă pentru a facilita și clarifica calculele din algebra liniară. Această relație strânsă între înmulțirea matricilor și algebra liniară rămâne fundamentală în toate ramurile matematicii, precum și în fizică, chimie, inginerie și informatică.
Aplicații liniare
[modificare | modificare sursă]Dacă un spațiu vectorial are o bază finită, orice vector este reprezentat în mod unic printr-un șir finit de scalari, numit componentele vectorului, ale cărui elemente sunt coordonatele vectorului în acea bază. Aceste componente formează un alt spațiu vectorial, care este izomorf cu spațiul vectorial inițial. Componentele vectorului sunt plasate de obicei într-o matrice coloană (numită și vector coloană), care este o matrice cu o singură coloană. Deci, un vector coloană reprezintă atât componentele vectorului, cât și un vector din spațiului vectorial inițial.
O aplicație liniară A dintr-un spațiu vectorial de dimensiune n într-un spațiu vectorial de dimensiune m aplică un vector coloană
pe vectorul coloană
Aplicația liniară A este astfel definită de matricea
și aplică vectorul coloană pe produsul matricial
Dacă B este o altă aplicație liniară din spațiul vectorial precedent de dimensiunea m, într-un spațiu vectorial de dimensiunea p, este reprezentată printr-o matrice (p × m). Un calcul simplu arată că matricea compunerii este produsul matricial Formula generală care definește funcția compusă este prezentată aici ca un caz particular de asociativitate al produsului matricial:
Rotațiile geometrice
[modificare | modificare sursă]Folosind un sistem de coordonate carteziene într-un plan euclidian, rotația cu un unghi în jurul originii este o aplicație liniară. Mai exact,
unde punctul inițial și imaginea sa sunt scrise ca vectori coloană.
Compunerea rotației cu unghiul și cea cu unghiul corespunde apoi cu produsul matricial
în care membrul drept al ultimei identități conține identitățile trigonometrice pentru sinusul și cosinusul sumei și diferenței unghiurilor, compunerea corespunde rotației cu unghiul , cum era de așteptat.
Alocarea resurselor în economie
[modificare | modificare sursă]![](https://upload.wikimedia.org/wikipedia/commons/thumb/3/30/Mmult_factory_svg.svg/400px-Mmult_factory_svg.svg.png)
De exemplu, o fabrică fictivă folosește 4 tipuri de materii prime, pentru a produce 3 tipuri de bunuri intermediare , , care la rândul lor sunt folosite pentru a produce 3 tipuri de produse finite, . Matricile
- și
furnizează cantitatea de materii prime necesare pentru o anumită cantitate de bunuri intermediare și, respectiv, cantitatea de bunuri intermediare necesară pentru o anumită cantitate de produse finite. De exemplu, pentru a produce o unitate de bun intermediar , sunt necesare o unitate de materie primă , două unități de , nicio unitate de și o unitate de , corespunzătoare primei coloane din .
Folosind înmulțirea matricilor se calculează
această matrice indică direct cantitățile de materii prime necesare pentru cantități date de produse finite. De exemplu, intrarea din stânga jos a este calculată ca fiind , reflectând faptul că pentru a produce o unitate de sunt necesare unități de . Efectiv, este necesară o unitate de pentru , 2 pentru și pentru fiecare dintre cele două unități care intră în unitatea , vezi imaginea.
Pentru a produce de exemplu 100 de unități din produsul final , 80 de unități de și 60 de unități de , cantitățile necesare de materii prime pot fi calculate prin
adică unități de , unități de , unități de și unități de . Similar, matricea produsului poate fi utilizată pentru a calcula cantitățile necesare de materii prime pentru alte date privind cantitățile de produse finale.[10]
Sisteme de ecuații liniare
[modificare | modificare sursă]Forma generală a unui sistem de ecuații liniare este:
Folosind aceeași notație ca mai sus, un astfel de sistem este echivalent cu o singură ecuație matricială:
Produsul scalar, forma biliniară și sesquiliniară
[modificare | modificare sursă]Produsul scalar al doi vectori coloană este elementul unic al produsului matricial
unde este vectorul linie obținut prin transpunerea . (De obicei o matrice 1×1 este identificată prin unicul său element.)
În general, orice formă biliniară pe un spațiu vectorial de dimensiune finită poate fi exprimată ca produs matricial:
și orice altă formă sesquiliniară(d) poate fi exprimată prin
unde este adjuncta lui (transpusa conjugată).
Proprietăți generale
[modificare | modificare sursă]Înmulțirea matricială are unele proprietăți asemănătoare cu înmulțirea obișnuită. Totuși, înmulțirea matricială nu este definită dacă numărul de coloane al primului factor diferă de numărul de linii al celui de-al doilea factor și este necomutativă,[11] chiar și când produsul rămâne definit după schimbarea ordinii factorilor.[12][13]
Necomutativitatea
[modificare | modificare sursă]O operație este comutativă dacă, fiind date două elemente A și B astfel încât produsul este definit, atunci este definit și
Înmulțirea matricială a două matrici A și B al căror produs matricial este definit, ar fi comutativă dacă produsul este și el definit, iar
Dacă A și B sunt matrici de dimensiunile m×n respectiv p×q, atunci este definit dacă n = p, iar este definit dacă m = q. Prin urmare, dacă unul dintre produse este definit, celălalt ar trebui să fie nedefinit. Dacă , cele două produse sunt definite, dar au dimensiuni diferite; astfel că ele nu pot fi egale. Doar dacă m = q= n= p, adică dacă A și B sunt ambele pătrate, de aceeași dimensiune, ambele produse sunt definite și au aceeași dimensiune. Chiar și în acest caz, în general
De exemplu
dar
Acest exemplu poate fi extins pentru a arăta că dacă A este o matrice n×n cu elementele într-un corp F, atunci pentru orice matrice B n×n cu elementele din F dacă și numai dacă unde și I este matricea unitate n×n. Dacă, în loc de un corp, se presupune că elementele aparțin unui inel, atunci trebuie adăugată condiția ca c să aparțină centrului inelului.
Un caz particular în care comutativitatea apare este atunci când D și E sunt două matrici diagonale pătrate de aceeași mărime. Atunci DE = ED.[11] Din nou, dacă matricile sunt peste un inel generic în loc de a fi peste un corp, elementele corespunzătoare ale fiecăreia trebuie, de asemenea, să fie comutative unul față de celălalt pentru ca acest lucru să fie valabil.
Distributivitatea
[modificare | modificare sursă]Produsul matricial este distributiv față de adunarea matricilor. Adică dacă A, B, C, D sunt matrici de dimensiunile respective m×n, n×p, n×p, și p×q, există atât distributivitatea la stânga[11]
cât și la dreapta[11]
Aceasta rezultă din distributivitatea coeficienților
Asociativitatea
[modificare | modificare sursă]Fiind date matricile A, B și C, produsele (AB)C și A(BC) sunt definite dacă și numai dacă numărul de coloane din A este egal cu numărul de linii din B și numărul de coloane din B este egal cu numărul de linii din C (în special, dacă unul dintre produse este definit, atunci celălalt este și el definit). În acest caz există asociativitatea
Ca la orice operație asociativă, aceasta permite omiterea parantezelor și scrierea produselor de mai sus ca
Aceasta se extinde natural la produsul a oricâte matrici, cu condiția ca dimensiunile să se potrivească. Adică dacă A1, A2, ... , A n sunt matrici astfel încât numărul de coloane ale Ai este egal numărul de linii ale Ai + 1 pentru i = 1, ... , n−1, atunci produsul
este definit și nu depinde de ordinea în care se fac înmulțirile, cât timp ordinea matricilor este păstrată fixă.
Aceste proprietăți pot fi demonstrate prin operații de adunare simple, dar lungi. Acest rezultat rezultă și din faptul că matricile sunt aplicații liniare. Prin urmare, proprietatea asociativă a matricilor este pur și simplu un caz particular al proprietății asociative a compunerii funcțiilor(d).
Produsul cu un scalar
[modificare | modificare sursă]Dacă A este o matrice și c un scalar, atunci matricile și se obțin înmulțind la stânga sau la dreapta toate elementele lui A cu c. Dacă scalarii sunt comutativi, atunci
Dacă produsul este definit (adică numărul de coloane din A este egal cu numărul de linii din B), atunci
- și
Dacă scalarii sunt comutativi, atunci toate cele patru matrici sunt egale. În general, toate cele patru sunt egale dacă c aparține centrului unui inel care conține elementele matricei, deoarece în acest caz, c X = X c pentru toate matricile X.
Aceste proprietăți rezultă din biliniaritatea produsului scalarilor:
Operații cu matricea transpusă
[modificare | modificare sursă]Dacă scalarii sunt comutativi, transpusa produsului matricial este produsul, în ordine inversă, al transpuselor factorilor. Acesta este
unde cu T este notată transpusa.
Această identitate nu este valabilă pentru elementele necomutative, deoarece ordinea dintre elementele lui A și B este inversată atunci când se extinde definirea produsului matricial.
Conjugata complexă
[modificare | modificare sursă]Dacă A și B au elemente complexe, atunci
unde cu * sunt notate conjugatele complexe ale elementelor matricei.
Acest lucru rezultă din aplicarea la definiția produsului matricial a faptului că conjugatul unei sume este suma conjugatelor sumelor, iar conjugatul unui produs este produsul conjugatelor factorilor.
Transpunerea acționează asupra indicilor elementelor, în timp ce conjugarea acționează independent asupra elementelor în sine. Rezultă că, dacă A și B au elemente complexe, există
unde cu † sunt notate adjunctele (conjugatele transpuselor, sau, echivalent, transpusele conjugatelor).
Matrici pătrate
[modificare | modificare sursă]Fie mulțimea de matrici pătrate n×n cu elementele din inelul R, care, în practică, este adesea un corp.
În , produsul este definit pentru fiecare pereche de matrici. Acest lucru face din un inel, care are matricea unitate I ca element neutru (matricea ale cărei elemente pe diagonala principală sunt egale cu 1 și toate celelalte elemente sunt 0). Acest inel este, de asemenea, o R-algebră asociativă(d).
Dacă n > 1, multe matrici nu au o inversă multiplicativă. De exemplu, o matrice care are toate elementele unei linii (sau unei coloane) 0 nu are inversă. Dacă există, inversa unei matrice A se notează A−1 și verifică relația
O matrice care are o inversă este o matrice inversabilă. În caz contrar, este o matrice singulară.
Un produs matricial este inversabil dacă și numai dacă fiecare factor este inversabil. În acest caz există relația
Când R este comutativ și, în special, când este un corp, determinantul unui produs este produsul determinanților. Deoarece determinanții sunt scalari, iar scalarii sunt comutativi, există relația
Ceilalți invarianți(d) matriciali nu se comportă la fel de bine cu produsele. Totuși, dacă R este comutativ, AB și BA au aceeași urmă, același polinom caracteristic(d) și aceleași valori proprii cu aceleași multiplicități. Totuși, vectorii proprii sunt în general diferiți dacă AB ≠ BA.
Puterea unei matrice pătrate
[modificare | modificare sursă]O matrice pătrată poate fi ridicată la orice putere întreagă nenegativă înmulțind-o cu ea însăși în mod repetat, în același mod ca pentru numerele obișnuite. Acesta este,
Calcularea celei de a k-a putere a unei matrice, dacă se face cu algoritmul trivial (înmulțire repetată) necesită de k−1 ori timpul unei singure înmulțiri matriciale. Deoarece acest lucru consumă foarte mult timp, se preferă metoda ridicării la putere rapide(d), care necesită mai puțin de 2 log2 k înmulțiri matriciale, deci este mult mai eficientă.
Un caz ușor de ridicare la putere este cel al unei matrice diagonale. Deoarece produsul matricilor diagonale echivalează cu simpla înmulțire a elementelor diagonale corespunzătoare, a k-a putere a unei matrici diagonale se obține prin ridicarea elementelor ei la puterea k:
Aplicație la matrici asemenea
[modificare | modificare sursă]Orice matrice inversabilă definește o transformare de asemănare (pe matrici pătrate de aceeași dimensiune ca )
Transformările de asemănare aplică produsul la factori, adică
De fapt,
Complexitatea de calcul
[modificare | modificare sursă]![](https://upload.wikimedia.org/wikipedia/commons/thumb/5/5b/MatrixMultComplexity_svg.svg/440px-MatrixMultComplexity_svg.svg.png)
Un algoritm de înmulțire a matricilor care rezultă din definiție necesită în cazul cel mai rău n3 înmulțiri și (n−1)n2 adunări de scalari pentru a calcula produsul a două matrice pătrate n×n. Într-un model de calcul în care operațiile scalare au timp constant complexitatea sa de calcul(d) este deci O(n3).
Surprinzător, această complexitate nu este optimă, așa cum a arătat în 1969 Volker Strassen, care a furnizat un algoritm, numit acum algoritmul Strassen(d), cu o complexitate de [14]
Din 2020, cel mai bun algoritm de înmulțire matricială era cel dat de Josh Alman și Virginia Vassilevska Williams, cu complexitatea O(n2.3728596).[15]
Nu se știe dacă înmulțirea matricială poate fi efectuată în timp n2 + o(1). Acest lucru ar fi optim, deoarece trebuie citite cele n2 elementele unei matrice pentru a o înmulți cu o altă matrice.
Deoarece înmulțirea matricială formează baza pentru mulți algoritmi și multe operații pe matrici chiar au aceeași complexitate ca și înmulțirea matricială (până la o constantă multiplicativă), complexitatea de calcul a înmulțirii matriciale este o chestiune importantă în algebra liniară numerică(d) și informatica teoretică(d).
Complexitatea de calcul în funcție de ordinea operațiilor
[modificare | modificare sursă]Deși rezultatul unei secvențe de produse matrice nu depinde de ordinea efectuării produselor (cu condiția ca ordinea matricelor să nu fie schimbată), complexitatea de calcul poate depinde mult de această ordine.
De exemplu, dacă A, B și C sunt matrici cu dimensiunile 10×30, 30×5, 5×60, calculul (AB)C necesită 10×30×5 + 10×5×60 = 4500 de înmulțiri, în timp ce calculul A(BC) necesită 30×5×60 + 10×30×60 = 27 000 de înmulțiri.
Au fost concepuți algoritmi pentru alegerea ordinii optime de efectuare a produselor, adică printr-un număr minim de operații. Când numărul n de matrici crește, s-a demonstrat că alegerea ordinii optime are o complexitate de
Alte tipuri de produse ale matricilor
[modificare | modificare sursă]Înmulțirea „standard” a matricilor prezentată în articolul de față este singurul mod de înmulțire al matricilor studiat în învățământul preuniversitar din România.[16] Însă există și alte tipuri de produse de matrici:
- produs cracovian, definit drept A ∧ B = BTA
- produs interior Frobenius, produs scalar al matricilor considerate drept vectori, sau, echivalent suma produselor Hadamard ale elementelor
- produs Hadamard, elementele produsului sunt produsele element cu element
- produs Kronecker și produs tensorial, generalizare a precedentelor
- produs Khatri–Rao
- produs extern (sau produs diadic) a două matrici coloană,
Note
[modificare | modificare sursă]- ^ Anca Ignat, Calcul numeric Arhivat în , la Wayback Machine. (curs 2, 2022, p. 2), Universitatea „Alexandru Ioan Cuza” din Iași, accesat 2023-06-13
- ^ a b en Nykamp, Duane. „Multiplying matrices and vectors”. Math Insight. Accesat în .
- ^ en O'Connor, John J.; Robertson, Edmund F., „Jacques Philippe Marie Binet”, MacTutor History of Mathematics archive, University of St Andrews.
- ^ en Lerner, Rita G.; Trigg, G. L. (). Encyclopaedia of Physics (ed. 2nd). VHC publishers. ISBN 978-3-527-26954-9.
- ^ en Parker, C. B. (). McGraw Hill Encyclopaedia of Physics
(ed. 2nd). ISBN 978-0-07-051400-3.
- ^ en Lipschutz, S.; Lipson, M. (). Linear Algebra. Schaum's Outlines (ed. 4th). McGraw Hill (USA). pp. 30–31. ISBN 978-0-07-154352-1.
- ^ en Riley, K. F.; Hobson, M. P.; Bence, S. J. (). Mathematical methods for physics and engineering
. Cambridge University Press. ISBN 978-0-521-86153-3.
- ^ en Adams, R. A. (). Calculus, A Complete Course (ed. 3rd). Addison Wesley. p. 627. ISBN 0-201-82823-5.
- ^ en Horn, Johnson (). Matrix Analysis (ed. 2nd). Cambridge University Press. p. 6. ISBN 978-0-521-54823-6.
- ^ de Peter Stingl (). Mathematik für Fachhochschulen – Technik und Informatik (ed. 5th). München: Carl Hanser Verlag. ISBN 3-446-18668-9. Here: Exm. 5.4.10, pp. 205–206
- ^ a b c d en Weisstein, Eric W. „Matrix Multiplication”. mathworld.wolfram.com. Accesat în .
- ^ en Lipcshutz, S.; Lipson, M. (). „2”. Linear Algebra. Schaum's Outlines (ed. 4th). McGraw Hill (USA). ISBN 978-0-07-154352-1.
- ^ en Horn, Johnson (). „Chapter 0”. Matrix Analysis (ed. 2nd). Cambridge University Press. ISBN 978-0-521-54823-6.
- ^ Volker Strassen (). „Gaussian elimination is not optimal”. Numerische Mathematik. 13 (4): 354–356. doi:10.1007/BF02165411.
- ^
Alman, Josh; Williams, Virginia Vassilevska (), „A Refined Laser Method and Faster Matrix Multiplication”, 32nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2021), arXiv:2010.05846
- ^ Burtea, Marius; Burtea, Georgeta (). Carminis, ed. Matematică: Manual pentru clasa a XI-a (PDF). Pitești. pp. 22–26, accesat 2023–03–18. ISBN 978-973-123-417-5. Arhivat din original (PDF) la . Accesat în .
Bibliografie
[modificare | modificare sursă]- en Henry Cohn, Robert Kleinberg, Balázs Szegedy, and Chris Umans. Group-theoretic Algorithms for Matrix Multiplication. arΧiv:math.GR/0511460. Proceedings of the 46th Annual Symposium on Foundations of Computer Science, 23–25 October 2005, Pittsburgh, PA, IEEE Computer Society, pp. 379–388.
- en Henry Cohn, Chris Umans. A Group-theoretic Approach to Fast Matrix Multiplication. arΧiv:math.GR/0307321. Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, 11–14 October 2003, Cambridge, MA, IEEE Computer Society, pp. 438–449.
- en Coppersmith, D.; Winograd, S. (). „Matrix multiplication via arithmetic progressions”. J. Symbolic Comput. 9 (3): 251–280. doi:10.1016/s0747-7171(08)80013-2
.
- en Horn, Roger A.; Johnson, Charles R. (), Topics in Matrix Analysis, Cambridge University Press, ISBN 978-0-521-46713-1
- en Knuth, D.E., The Art of Computer Programming Volume 2: Seminumerical Algorithms. Addison-Wesley Professional; 3 edition (November 14, 1997). ISBN: 978-0-201-89684-8. p. 501
- en Press, William H.; Flannery, Brian P.; Teukolsky, Saul A.; Vetterling, William T. (), Numerical Recipes: The Art of Scientific Computing (ed. 3rd), Cambridge University Press, ISBN 978-0-521-88068-8
- en Ran Raz, On the complexity of matrix product. In Proceedings of the thirty-fourth annual ACM symposium on Theory of computing. ACM Press, 2002 doi:10.1145/509907.509932.
- en Robinson, Sara, Toward an Optimal Algorithm for Matrix Multiplication, SIAM News 38(9), November 2005. PDF
- en Strassen, Volker, Gaussian Elimination is not Optimal, Numer. Math. 13, p. 354-356, 1969
- en Styan, George P. H. (), „Hadamard Products and Multivariate Statistical Analysis” (PDF), Linear Algebra and Its Applications, 6: 217–240, doi:10.1016/0024-3795(73)90023-2
- en Williams, Virginia Vassilevska (). „Multiplying matrices faster than coppersmith-winograd”. Proceedings of the 44th symposium on Theory of Computing - STOC '12. ACM. pp. 887–898. CiteSeerX 10.1.1.297.2680
. doi:10.1145/2213977.2214056. ISBN 9781450312455.
Legături externe
[modificare | modificare sursă]Materiale media legate de înmulțirea matricilor la Wikimedia Commons
|
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.