La multiplication de matrices

Saviez-vous ...

SOS Enfants a fait cette s??lection Wikipedia aux c??t??s d'autres ??coles des ressources . Un lien rapide pour le parrainage d'enfants est http://www.sponsor-a-child.org.uk/

En math??matiques , la multiplication de matrices est l'op??ration consistant ?? multiplier un matrice soit avec un scalaire ou une autre matrice. Cet article donne un aper??u des diff??rentes fa??ons d'effectuer la multiplication de matrices.

Produit matriciel ordinaire

Ce est le moyen le plus souvent utilis?? et le plus important de multiplier les matrices. Il est d??fini entre deux matrices que si le nombre de colonnes de la premi??re matrice est le m??me que le nombre de rang??es de la deuxi??me matrice. Si A est une matrice m -by- n et B est une matrice n -by- p, puis leur produit est une matrice de m -by- p d??sign?? par AB (ou parfois A ?? B). Si C = AB et C _{i, j} d??signe l'entr??e en C ?? la position (i, j), puis

$c_ {i, j} = \ sum_ {r = 1} ^ n a_ {i, r} b_ {r, j} = a_ {i, 1} b_ {1, j} + a_ {i, 2} {b_ 2, j} + \ cdots + a_ {i, n} b_ {n, j}.$

pour chaque paire i et j avec 1 ≤ i ≤ M et 1 ≤ j ≤ p. Le syst??me alg??brique " unit??s de la matrice "r??sume les propri??t??s abstraites de ce genre de multiplication.

Calcul directement ?? partir de la d??finition

L'image de gauche montre comment calculer le (1,2) et l'??l??ment (3,3) ??l??ment de AB si A est une matrice 4 ?? 2, et B est une matrice 2 ?? 3. Les ??l??ments de chaque matrice sont appari??s dans la direction des fl??ches; chaque paire est multipli??, et les produits sont ajout??s. L'emplacement du nombre r??sultant en AB correspond ?? la ligne et de la colonne qui ont ??t?? pris en consid??ration.

$(\ Mathbf {AB}) _ {1,2} = \ sum_ {r = 1} ^ 2 a_ {1, r} B_ {r, 2} = {1,1} a_ b_ {1,2} + a_ {1,2} {2,2} b_$

$(\ Mathbf {AB}) _ {3,3} = \ sum_ {r = 1} ^ 2 a_ {3, r} B_ {R, 3} = {3,1} a_ b_ {1,3} + a_ {3,2} {2,3} b_$

Par exemple:

$\ Begin {} bmatrix 1 & 0 & 2 -1 \\ & 3 & 1 \ end {bmatrix} \ cdot \ begin {} bmatrix 3 & 1 \\ 2 & 1 \\ 1 & 0 \ end {} bmatrix = \ begin {} bmatrix 1 \ 3 fois + 0 \ times 2 + 2 \ times 1 & 1 \ times 1 + 0 \ times 1 + 2 \ fois 0 -1 \\ \ fois 3 + 3 \ times 2 + 1 \ times 1 & -1 \ times 1 + 3 \ times 1 + 1 \ fois 0 \ end {} bmatrix = \ begin {} bmatrix 5 & 1 \\ 4 & 2 \ end {} bmatrix$

Proc??d?? coefficients vecteurs

Cette multiplication de matrice peut ??galement ??tre consid??r??e du point de vue l??g??rement diff??rent: il ajoute des vecteurs ainsi apr??s avoir ??t?? multipli?? par diff??rents coefficients. Si A et B sont des matrices donn??s par:

$\ Mathbf {A} = \ begin {} bmatrix a_ {1,1} & a_ {1,2} \ & points \\ a_ {2,1} et {2,2} a_ \ & points \\ \ & vdots \ & vdots \ ddots \ end {} bmatrix$ et $\ Mathbf {B} = \ begin {} bmatrix b_ {1,1} & b_ {1,2} \ & points \\ b_ {2,1} et {2,2} b_ & \ dots \\ \ & vdots \ & vdots \ ddots \ end {} bmatrix = \ begin {} bmatrix B_1 \\ B_2 \\ \ vdots \ end {} bmatrix$

puis

$\ Mathbf {AB} = \ begin {} bmatrix a_ {1,1} B_1 + a_ {1,2} B_2 + \ cdots de la a_ {2,1} B_1 + a_ {2,2} B_2 + \ cdots \\ \ vdots \ end {} bmatrix$

L'exemple revisit??:

$\ Begin {} bmatrix 1 & 0 & 2 -1 \\ & 3 & 1 \ end {bmatrix} \ cdot \ begin {} bmatrix 3 & 1 \\ 2 & 1 \\ 1 & 0 \ end {} bmatrix = \ begin {} bmatrix 1 \ begin {} bmatrix 3 & 1 \ end {} bmatrix + 0 \ begin {} bmatrix 2 & 1 \ end {} bmatrix + 2 \ begin {} bmatrix 1 & 0 \ end {} \\ bmatrix -1 \ begin {} bmatrix 3 & 1 \ end {} bmatrix + 3 \ begin {} bmatrix 2 & 1 \ end {} bmatrix + 1 \ begin {} bmatrix 1 & 0 \ end {bmatrix} \ end {} bmatrix = \ begin {bmatrix} \ begin {} bmatrix 3 & 1 \ end {} bmatrix + \ begin {} bmatrix 0 & 0 \ end {} bmatrix + \ begin {} bmatrix 2 & 0 \ end {} bmatrix \\ \ begin {} bmatrix -3 et -1 \ end {} bmatrix + \ begin {} bmatrix 6 et 3 \ end {} bmatrix + \ begin {} bmatrix 1 & 0 \ end {bmatrix} \ end {} bmatrix$

$= \ Begin {} bmatrix 5 & 1 \\ 4 & 2 \ end {} bmatrix$

Les lignes de la matrice sont ?? gauche de la liste des coefficients. La matrice sur la droite est la liste des vecteurs. Dans l'exemple, la premi??re ligne est [1 0 2], et donc nous prenons une fois le premier vecteur, 0 fois le second vecteur, et deux fois la troisi??me vecteur.

L'??quation peut ??tre simplifi??e en utilisant en outre produits ext??rieurs:

$\ Mathbf {A} = \ begin {} bmatrix A_1 & A_2 & \ dots \ end {bmatrix} \ implique \ mathbf {AB} = \ sum_i A_iB_i$

Les termes de cette somme sont des matrices de la m??me forme, chacune d??crivant l'effet d'une colonne de A et une rang??e de B sur le r??sultat. Les colonnes de A peuvent ??tre consid??r??s comme un syst??me de coordonn??es de la transformation, ce est ?? dire ??tant donn?? un vecteur x nous avons $\ mathbf {a} x = A_1x_1 + A_2x_2 + \ cdots$ o?? $x_i$ sont des coordonn??es le long de la $A_i$ "Axes". Les termes $A_iB_i$ sont comme $A_ix_i$ , Except?? $B_i$ contient la i i??me coordonn??e pour chaque vecteur de colonne de B, dont chacun est ind??pendamment transform?? en parall??le.

L'exemple revisit??:

$\ Begin {} bmatrix 1 & 0 & 2 -1 \\ & 3 & 1 \ end {bmatrix} \ cdot \ begin {} bmatrix 3 & 1 \\ 2 & 1 \\ 1 & 0 \ end {} bmatrix = \ begin {} bmatrix 1 \\ -1 \ end {bmatrix} \ begin {} bmatrix 3 & 1 \ end {} bmatrix + \ begin {} 0 bmatrix \\ 3 \ end {bmatrix} \ begin {} bmatrix 2 & 1 \ end {} bmatrix + \ begin {} bmatrix 2 \\ 1 \ end {bmatrix} \ begin {} bmatrix 1 & 0 \ end {} bmatrix$

$= \ Begin {} bmatrix 1 \ cdot 3 & 1 \ cdot 1 \\ -1 \ cdot 3 et -1 \ cdot 1 \ end {} bmatrix + \ begin {} 0 bmatrix \ cdot 2 & 0 \ cdot 1 \\ 3 \ cdot 2 & 3 \ cdot 1 \ end {} bmatrix + \ begin {} bmatrix 2 \ cdot 1 & 2 \ cdot 0 1 \\ \ cdot 1 & 1 \ cdot 0 \ end {} bmatrix = \ begin {bmatrix } 5 & 1 \\ 4 & 2 \ end {} bmatrix$

Les vecteurs $\ Begin {} bmatrix 3 & 2 & 1 \ end {bmatrix} ^ \ top$ et $\ Begin {} bmatrix 1 & 1 & 0 \ end {bmatrix} ^ \ top$ ont ??t?? transform??s ?? $\ Begin {} bmatrix 5 & 4 \ end {bmatrix} ^ \ top$ et $\ Begin {} bmatrix 1 & 2 \ end {bmatrix} ^ \ top$ en parall??le. On pourrait aussi les transformer un par un avec les m??mes ??tapes:

$\ Begin {} bmatrix 1 & 0 & 2 -1 \\ & 3 & 1 \ end {bmatrix} \ cdot \ begin {} bmatrix 3 \\ \\ 2 1 \ end {} bmatrix = \ begin {} bmatrix 1 \ \ -1 \ end {} bmatrix 3+ \ begin {} 0 bmatrix \\ 3 \ end {} bmatrix 2+ \ begin {} bmatrix 2 \\ 1 \ end {} bmatrix 1 = \ begin {} bmatrix 1 \ cdot 3 -1 \\ \ cdot 3 \ end {} bmatrix + \ begin {} 0 bmatrix \ cdot 2 \\ 3 \ cdot 2 \ end {} bmatrix + \ begin {} bmatrix 2 \ cdot 1 \\ 1 \ cdot 1 \ end {} bmatrix = \ begin {} bmatrix 5 4 \\ \ end {} bmatrix$

M??thode vectorielle listes

Le produit de la matrice ordinaire peut ??tre consid??r?? comme un dot produit d'une colonne liste des vecteurs et un rang??e liste des vecteurs. Si A et B sont des matrices donn??s par:

$\ Mathbf {A} = \ begin {} bmatrix a_ {1,1} et {1,2} a_ & a_ {1,3} \ & points \\ a_ {2,1} et {2,2} a_ & a_ {2,3} \ & points \\ a_ {3,1} et {3,2} a_ & a_ {3,3} \ & points \\ \ vdots & \ vdots & \ & vdots \ ddots \ end { bmatrix} = \ begin {} bmatrix A_1 \\ \\ A_2 A_3 \\ \ vdots \ end {} bmatrix$ et $\ Mathbf {B} = \ begin {} bmatrix b_ {1,1} & b_ {1,2} & b_ {1,3} \ & points \\ b_ {2,1} et {2,2} b_ & b_ {2,3} \ & points \\ b_ {3,1} et {3,2} b_ & b_ {3,3} et \ dots \\ \ vdots & \ vdots & \ & vdots \ ddots \ end { bmatrix} = \ begin {} bmatrix B_1 & B_2 & B_3 & \ dots \ end {} bmatrix$

o??

A ₁ est le vecteur ligne de tous les ??l??ments de la forme a _{une, x} A ₂ est le vecteur ligne de tous les ??l??ments de la forme a _{2, x} etc,

et B ₁ est le vecteur colonne de tous les ??l??ments de la forme b _{x, 1} B ₂ est le vecteur colonne de tous les ??l??ments de la forme b _{x, 2} etc,

puis

$\ Mathbf {AB} = \ begin {} bmatrix A_1 \\ \\ A_2 A_3 \\ \ vdots \ end {} bmatrix * \ begin {} bmatrix B_1 & B_2 & B_3 & \ dots \ end {} bmatrix = \ begin { bmatrix} (A_1 \ cdot b_1) et (A_1 \ cdot B_2) et (A_1 \ cdot B_3) & \ dots \\ (A_2 \ cdot B_1) & (A_2 \ cdot B_2) & (A_2 \ cdot B_3) & \ dots \\ (A_3 \ cdot B_1) & (A_3 \ cdot B_2) & (A_3 \ cdot B_3) & \ dots \\ \ vdots & \ vdots & \ & vdots \ ddots \ end {} bmatrix.$

Propri??t??s

La multiplication de matrices ne est pas commutative (ce est-?? AB de la BA), sauf dans des cas particuliers. Il est facile de voir pourquoi: vous ne pouvez pas vous attendre ?? passer les proportions avec les vecteurs et obtenir le m??me r??sultat. Il est ??galement facile de voir comment l'ordre des facteurs qui d??termine le r??sultat, quand on sait que le nombre de colonnes dans la matrice des proportions doit ??tre le m??me que le nombre de lignes de la matrice des vecteurs: ils doivent repr??senter le m??me nombre de vecteurs.

Bien que la multiplication de matrices ne est pas commutative, les d??terminants de AB et BA sont toujours ??gaux (si A et B sont des matrices carr??es de m??me taille). Voir l'article sur les d??terminants pour une explication. Cependant la multiplication de matrices est commutative lorsque les deux matrices sont diagonale et de la m??me dimension.

Cette notion de multiplication est important parce que si A et B sont interpr??t??es comme transformations lin??aires (qui est presque universellement fait), puis le produit matriciel AB correspond ?? la composition des deux transformations lin??aires, avec B ??tant appliqu??s en premier.

En outre, toutes les notions de la multiplication de matrices d??crites ici part un ensemble de propri??t??s communes d??crites ci-dessous.

Algorithmes

Le complexit?? de la multiplication de matrices, si elle est effectu??e na??vement, est O (n ??), mais des algorithmes plus efficaces existent. L'algorithme de Strassen, con??u par Volker Strassen en 1969 et souvent appel??e ??la multiplication de matrices rapide", est bas?? sur une fa??on intelligente de multiplier deux matrices 2 ?? 2 qui exige seulement 7 multiplications (au lieu de l'habituel 8). Appliquant cette astuce donne de mani??re r??cursive un algorithme avec un co??t de $O (n ^ {\ log_ {2}} 7) \ environ O (n ^ {2,807})$ . En pratique, cependant, il est rarement utilis?? car il est difficile ?? mettre en ??uvre et il manque stabilit?? num??rique. Le facteur constant implicite dans le Comparaison asymptotique est d'environ 4,695.

Le algorithme avec l'exposant le plus bas connu, qui a ??t?? pr??sent?? par Don Coppersmith et Shmuel Winograd en 1990 , a une complexit?? asymptotique de O (n ^2,376). Il est similaire ?? l'algorithme de Strassen: une fa??on intelligente est con??u pour multiplier deux matrices k ?? k avec moins de multiplications ?? k, et cette technique est appliqu??e de mani??re r??cursive. Il am??liore le facteur constant dans l'algorithme de Strassen, r??duisant ?? 4,537. Cependant, le terme constant impliqu?? dans le O (n ^2,376) r??sultat est si grande que l'algorithme Coppersmith-Winograd ne vaut que pour les matrices qui sont trop gros pour g??rer sur les ordinateurs actuels (Knuth, 1998).

Depuis ne importe quel algorithme pour multiplier deux matrices n ?? n doit traiter tous les 2 ?? n ?? entr??es, il ya une borne inf??rieure asymptotique des op??rations Ω (n) ??. Raz (2002) prouve une borne inf??rieure de $\ Omega (m ^ 2 \ log m)$ pour coefficient born??es circuits arithm??tiques sur les nombres r??els ou complexes.

Cohn et al. (2003, 2005) mis des m??thodes telles que les algorithmes Strassen et Coppersmith-Winograd dans un tout autre, th??orie des groupes contexte. Ils montrent que si les familles de produits de couronnes de ab??lien avec des groupes sym??triques satisfaisant certaines conditions existent, algorithmes matrice de multiplication avec une complexit?? quadratique essentielle existent. La plupart des chercheurs croient que ce est effectivement le cas (Robinson, 2005).

Multiplication scalaire

La multiplication scalaire d'une matrice A = (a _ij) et un scalaire r r donne un produit A de la m??me taille que A. Les entr??es de r A sont donn??s par

$(R \ mathbf {A}) _ {} ij = r \ cdot a_ {ij}. \,$

Par exemple, si

$\ Mathbf {A} = \ begin {} bmatrix 1 & 2 \\ 3 & 4 \ end {} bmatrix$

puis

$7 \ mathbf {A} = \ begin {} bmatrix 7 \ cdot 1 et 7 \ cdot 2 \\ 7 \ cdot 3 & 7 \ cdot 4 \ end {} bmatrix = \ begin {} bmatrix 7 & 14 21 \\ & 28 \ end {} bmatrix.$

Si nous sommes pr??occup??s par les matrices sur une anneau, puis la multiplication ci-dessus est parfois appel?? la multiplication gauche tandis que la droite multiplication est d??finie comme

$(\ Mathbf {A} r) _ {ij} = {a_ ij} \ cdot r. \,$

Lorsque l'anneau sous-jacent est commutatif , par exemple, le champ de nombre r??el ou complexe, les deux multiplications sont les m??mes. Toutefois, si l'anneau ne est pas commutative, telle que la quaternions, ils peuvent ??tre diff??rents. Par exemple

$i \ begin {} i bmatrix & 0 0 \\ & j \\ \ end {} bmatrix = \ begin {} bmatrix -1 et 0 0 \\ & k \\ \ end {} bmatrix \ ne \ begin {} bmatrix -1 et 0 0 \\ & -k \\ \ end {} bmatrix = \ begin {} i bmatrix & 0 0 \\ & j \\ \ end {} i bmatrix.$

Produit Hadamard

Pour les deux matrices de m??mes dimensions, on a le produit de Hadamard, ??galement connu sous le nom de produit et le produit entrywise Schur. Il peut ??tre g??n??ralis??e ?? tenir non seulement pour les matrices mais aussi pour les op??rateurs. Le Hadamard produit de deux m -by- n matrices A et B, not??e A ??? B est une matrice n m -by- donn??e par (A ??? B) a _{ij ij} = b _ij. Par exemple

$\ Begin {} bmatrix 1 & 2 & 3 1 \\ \\ \ end {} bmatrix \ bullet \ begin {} bmatrix 0 et 3 \\ 2 & 1 \\ \ end {} bmatrix = \ begin {} bmatrix 1 \ cdot 0 et 2 \ cdot 3 \\ 3 \ cdot 2 & 1 \ cdot 1 \\ \ end {} bmatrix = \ begin {} bmatrix 0 et 6 \\ 6 & 1 \\ \ end {} bmatrix$ .

Notez que le produit est un Hadamard sous-matrice du produit de Kronecker (voir ci-dessous).

Le produit Hadamard est commutative .

Le produit Hadamard est ??tudi?? par les th??oriciens de la matrice, et il appara??t dans algorithmes de compression avec perte tels que JPEG, mais il est pratiquement ??pargn??e par alg??bristes lin??aires. Il est discut?? dans (Horn & Johnson, 1994, Ch. 5).

Produit de Kronecker

Pour tout deux matrices arbitraires A et B, nous avons le produit direct ou Produit de Kronecker A ⊗ B d??fini comme

$\ Begin {} bmatrix a_ {11} B & a_ {12} B & \ & cdots a_ {} B 1n \\ \ vdots & \ vdots & \ & ddots \ vdots \\ a_ {m1} B & a_ {} m2 B & \ & cdots a_ {mn} B \ end {} bmatrix.$

Notez que si A est m -by- n et B est de p r alors A ⊗ B est un mp -by- nr matrice. Encore une fois cette multiplication ne est pas commutative.

Par exemple

$\ Begin {} bmatrix 1 & 2 & 3 1 \\ \\ \ end {bmatrix} \ otimes \ begin {} bmatrix 0 et 3 \\ 2 & 1 \\ \ end {} bmatrix = \ begin {} bmatrix 1 \ cdot 0 & 1 \ cdot 3 & 2 \ cdot 0 et 2 \ cdot 3 \\ 1 \ cdot 2 & 1 \ cdot 1 & 2 \ cdot 2 & 2 \ cdot 1 \\ 3 \ cdot 0 et 3 \ cdot 3 & 1 \ cdot 0 & 1 \ cdot 3 \\ 3 \ cdot 2 & 3 \ cdot 1 & 1 \ cdot 2 & 1 \ cdot 1 \\ \ end {} bmatrix = \ begin {} bmatrix 0 & 3 & 0 & 6 \\ 2 & 1 & 4 & 2 \\ 0 et 9 et 0 et 3 \\ 6 & 3 & 2 & 1 \ end {} bmatrix$ .

Si A et B repr??sentent des transformations lin??aires V ₁ → W ₁ et W ₂ → V _2, respectivement, alors A ⊗ B repr??sente le produit tenseur des deux cartes, _une V ⊗ V ₂ → W ₁ ⊗ W _2.

Propri??t??s communes

Le Wikibook Le Livre de preuves math??matiques a une page sur le th??me de: Les preuves de propri??t??s des matrices

Tous les trois notions de multiplication de matrices sont associative :

$\ \ Mathbf {A} (\ mathbf {BC}) = (\ mathbf {AB}) \ mathbf {C}$

et distributive:

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

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

et compatible avec multiplication scalaire:

$\ C (\ mathbf {AB}) = (c \ mathbf {A}) \ mathbf {B}$

$\ (\ Mathbf {A} c) \ mathbf {B} = \ mathbf {A} (c \ mathbf {B})$

$\ (\ Mathbf {AB}) c = \ mathbf {A} (\ mathbf {B} c)$

Notez que ces trois couples s??par??s d'expressions seront ??gaux entre eux que si la multiplication et l'addition sur le champ scalaire sont commutative, ce est ?? dire le champ scalaire est un anneau commutatif. Voir multiplication scalaire ci-dessus pour un contre-exemple comme le champ scalaire de quaternions.

Produit interne Frobenius

Le produit int??rieur Frobenius, parfois not??e A: B est le produit int??rieur composante par composante de deux matrices comme se ils sont des vecteurs. En d'autres termes, ce est la somme des entr??es du produit, ce est-Hadamard,

$\ Mathbf {A}: \ mathbf {B} = \ sum_i \ sum_j A_ {ij} {B_ ij} = \ operatorname {trace} (\ mathbf {A} ^ T \ mathbf {B}) = \ operatorname {trace} (\ mathbf {A} \ mathbf {B} ^ T).$

Ce produit int??rieure induit la Norme de Frobenius.

R??cup??r?? ?? partir de " http://en.wikipedia.org/w/index.php?title=Matrix_multiplication&oldid=203157436 "