Ainsi, dans la leçon précédente, nous avons examiné les règles d'addition et de soustraction de matrices. Ce sont des opérations si simples que la plupart des étudiants les comprennent littéralement dès le départ.
Cependant, vous vous réjouissez tôt. Le cadeau est terminé - passons à la multiplication. Je vous préviens tout de suite : multiplier deux matrices, ce n'est pas du tout multiplier des nombres dans des cellules de mêmes coordonnées, comme on pourrait le penser. Tout est beaucoup plus amusant ici. Et nous devrons commencer par des définitions préliminaires.
Matrices appariées
Un des les caractéristiques les plus importantes la matrice est sa taille. Nous en avons déjà parlé une centaine de fois : la notation $A=\left[ m\times n \right]$ signifie que la matrice a exactement $m$ lignes et $n$ colonnes. Nous avons également déjà expliqué comment ne pas confondre les lignes avec les colonnes. Quelque chose d’autre est important maintenant.
Définition. Matrices de la forme $A=\left[ m\times n \right]$ et $B=\left[ n\times k \right]$, dans lesquelles le nombre de colonnes de la première matrice coïncide avec le nombre de lignes dans le second, sont appelés cohérents.
Encore une fois : le nombre de colonnes dans la première matrice est égal au nombre de lignes dans la seconde ! De là, nous obtenons deux conclusions à la fois :
- L'ordre des matrices est important pour nous. Par exemple, les matrices $A=\left[ 3\times 2 \right]$ et $B=\left[ 2\times 5 \right]$ sont cohérentes (2 colonnes dans la première matrice et 2 lignes dans la seconde) , mais vice versa — les matrices $B=\left[ 2\times 5 \right]$ et $A=\left[ 3\times 2 \right]$ ne sont plus cohérentes (5 colonnes de la première matrice ne sont pas 3 lignes dans la seconde ).
- La cohérence peut être facilement vérifiée en notant toutes les dimensions les unes après les autres. En reprenant l'exemple du paragraphe précédent : « 3 2 2 5 » - il y a des nombres identiques au milieu, donc les matrices sont cohérentes. Mais « 2 5 3 2 » ne sont pas cohérents, car il y a des nombres différents au milieu.
De plus, Captain Obviousness semble laisser entendre que les matrices carrées de même taille $\left[ n\times n \right]$ sont toujours cohérentes.
En mathématiques, lorsque l’ordre de listage des objets est important (par exemple, dans la définition évoquée ci-dessus, l’ordre des matrices est important), on parle souvent de paires ordonnées. Nous les avons rencontrés à l'école : je pense qu'il va de soi que les coordonnées $\left(1;0 \right)$ et $\left(0;1 \right)$ définissent différents points sur l'avion.
Donc : les coordonnées sont également des paires ordonnées composées de nombres. Mais rien ne vous empêche de constituer une telle paire à partir de matrices. On peut alors dire : « Une paire ordonnée de matrices $\left(A;B \right)$ est cohérente si le nombre de colonnes de la première matrice est le même que le nombre de lignes de la seconde. »
Eh bien, et alors ?
Définition de la multiplication
Considérons deux matrices cohérentes : $A=\left[ m\times n \right]$ et $B=\left[ n\times k \right]$. Et nous définissons pour eux l’opération de multiplication.
Définition. Le produit de deux matrices appariées $A=\left[ m\times n \right]$ et $B=\left[ n\times k \right]$ est la nouvelle matrice $C=\left[ m\times k \ right] $, dont les éléments sont calculés selon la formule :
\[\begin(align) & ((c)_(i;j))=((a)_(i;1))\cdot ((b)_(1;j))+((a)_ (i;2))\cdot ((b)_(2;j))+\ldots +((a)_(i;n))\cdot ((b)_(n;j))= \\ & =\sum\limits_(t=1)^(n)(((a)_(i;t))\cdot ((b)_(t;j))) \end(align)\]
Un tel produit est noté de la manière standard : $C=A\cdot B$.
Ceux qui voient cette définition pour la première fois se posent immédiatement deux questions :
- De quel genre de jeu féroce s'agit-il ?
- Pourquoi est-ce si difficile?
Eh bien, commençons par le commencement. Commençons par la première question. Que signifient tous ces indices ? Et comment ne pas se tromper lorsqu’on travaille avec de vraies matrices ?
Tout d'abord, on note que la longue ligne de calcul de $((c)_(i;j))$ (j'ai spécialement mis un point-virgule entre les indices pour ne pas se tromper, mais il n'est pas nécessaire de les mettre général - j'en ai moi-même eu marre de taper la formule dans la définition) se résume en fait à une règle simple :
- Prenez la $i$ième ligne de la première matrice ;
- Prenez la $j$ème colonne de la deuxième matrice ;
- Nous obtenons deux séquences de nombres. Nous multiplions les éléments de ces séquences par les mêmes nombres, puis additionnons les produits résultants.
Ce processus est facile à comprendre à partir de l'image :
Schéma de multiplication de deux matrices Encore une fois : nous fixons la ligne $i$ dans la première matrice, la colonne $j$ dans la deuxième matrice, multiplions les éléments avec les mêmes nombres, puis ajoutons les produits résultants - nous obtenons $((c)_(ij))$ . Et ainsi de suite pour tous les $1\le i\le m$ et $1\le j\le k$. Ceux. Il y aura $m\times k$ de telles « perversions » au total.
En fait, nous avons déjà rencontré la multiplication matricielle dans les programmes scolaires, mais sous une forme très réduite. Soit les vecteurs :
\[\begin(align) & \vec(a)=\left(((x)_(a));((y)_(a));((z)_(a)) \right); \\ & \overrightarrow(b)=\left(((x)_(b));((y)_(b));((z)_(b)) \right). \\ \fin(aligner)\]
Alors leur produit scalaire sera exactement la somme des produits par paires :
\[\overrightarrow(a)\times \overrightarrow(b)=((x)_(a))\cdot ((x)_(b))+((y)_(a))\cdot ((y )_(b))+((z)_(a))\cdot ((z)_(b))\]
Fondamentalement, à l'époque où les arbres étaient plus verts et le ciel plus lumineux, nous multipliions simplement le vecteur ligne $\overrightarrow(a)$ par le vecteur colonne $\overrightarrow(b)$.
Rien n'a changé aujourd'hui. C’est juste que maintenant il y a plus de ces vecteurs de lignes et de colonnes.
Mais assez de théorie ! Regardons des exemples réels. Et commençons par le cas le plus simple : les matrices carrées.
Multiplication matricielle carrée
Tâche 1. Faites la multiplication :
\[\left[ \begin(array)(*(35)(r)) 1 & 2 \\ -3 & 4 \\\end(array) \right]\cdot \left[ \begin(array)(* (35)(r)) -2 & 4 \\ 3 & 1 \\\end(array) \right]\]
Solution. Nous avons donc deux matrices : $A=\left[ 2\times 2 \right]$ et $B=\left[ 2\times 2 \right]$. Il est clair qu’elles sont cohérentes (les matrices carrées de même taille sont toujours cohérentes). On effectue donc la multiplication :
\[\begin(align) & \left[ \begin(array)(*(35)(r)) 1 & 2 \\ -3 & 4 \\\end(array) \right]\cdot \left[ \ début(array)(*(35)(r)) -2 & 4 \\ 3 & 1 \\\end(array) \right]=\left[ \begin(array)(*(35)(r)) 1\cdot \left(-2 \right)+2\cdot 3 & 1\cdot 4+2\cdot 1 \\ -3\cdot \left(-2 \right)+4\cdot 3 & -3\cdot 4+4\cdot 1 \\\end(array) \right]= \\ & =\left[ \begin(array)(*(35)(r)) 4 & 6 \\ 18 & -8 \\\ fin (tableau) \ droite]. \fin(aligner)\]
C'est tout!
Réponse : $\left[ \begin(array)(*(35)(r))4 & 6 \\ 18 & -8 \\\end(array) \right]$.
Tâche 2. Faites la multiplication :
\[\left[ \begin(matrix) 1 & 3 \\ 2 & 6 \\\end(matrix) \right]\cdot \left[ \begin(array)(*(35)(r))9 & 6 \\ -3 & -2 \\\end(tableau) \right]\]
Solution. Encore une fois, des matrices cohérentes, nous effectuons donc les actions suivantes :\[\]
\[\begin(align) & \left[ \begin(matrix) 1 & 3 \\ 2 & 6 \\\end(matrice) \right]\cdot \left[ \begin(array)(*(35)( ) r)) 9 & 6 \\ -3 & -2 \\\end(array) \right]=\left[ \begin(array)(*(35)(r)) 1\cdot 9+3\cdot \gauche(-3\right) & 1\cdot 6+3\cdot \left(-2 \right) \\ 2\cdot 9+6\cdot \left(-3 \right) & 2\cdot 6+6 \ cdot \left(-2 \right) \\\end(array) \right]= \\ & =\left[ \begin(matrix) 0 & 0 \\ 0 & 0 \\\end(matrice) \right ] . \fin(aligner)\]
Comme vous pouvez le voir, le résultat est une matrice remplie de zéros
Réponse : $\left[ \begin(matrix) 0 & 0 \\ 0 & 0 \\\end(matrix) \right]$.
D’après les exemples ci-dessus, il est évident que la multiplication matricielle n’est pas une opération si compliquée. Au moins pour les matrices carrées 2 par 2.
Au cours du processus de calcul, nous avons compilé une matrice intermédiaire, dans laquelle nous avons directement décrit quels nombres sont inclus dans une cellule particulière. C’est exactement ce qu’il faut faire pour résoudre de vrais problèmes.
Propriétés de base du produit matriciel
En un mot. Multiplication matricielle :
- Non commutatif : $A\cdot B\ne B\cdot A$ dans le cas général. Il existe bien sûr des matrices particulières pour lesquelles l'égalité $A\cdot B=B\cdot A$ (par exemple, si $B=E$ est la matrice identité), mais dans la grande majorité des cas cela ne fonctionne pas ;
- Associativement : $\left(A\cdot B \right)\cdot C=A\cdot \left(B\cdot C \right)$. Il n'y a aucune option ici : debout à proximité les matrices peuvent être multipliées sans se soucier de ce qui se trouve à gauche et à droite de ces deux matrices.
- De manière distributive : $A\cdot \left(B+C \right)=A\cdot B+A\cdot C$ et $\left(A+B \right)\cdot C=A\cdot C+B\cdot C $ (en raison de la non-commutativité du produit, il est nécessaire de spécifier séparément la distributivité droite et gauche.
Et maintenant, tout est pareil, mais plus en détail.
La multiplication matricielle est à bien des égards similaire à la multiplication classique des nombres. Mais il existe des différences, dont la plus importante est que La multiplication matricielle est, d’une manière générale, non commutative.
Regardons à nouveau les matrices du problème 1. Nous connaissons déjà leur produit direct :
\[\left[ \begin(array)(*(35)(r)) 1 & 2 \\ -3 & 4 \\\end(array) \right]\cdot \left[ \begin(array)(* (35)(r)) -2 & 4 \\ 3 & 1 \\\end(array) \right]=\left[ \begin(array)(*(35)(r))4 & 6 \\ 18 & -8 \\\end(tableau) \right]\]
Mais si on échange les matrices, on obtient un résultat complètement différent :
\[\left[ \begin(array)(*(35)(r)) -2 & 4 \\ 3 & 1 \\\end(array) \right]\cdot \left[ \begin(array)(* (35)(r)) 1 & 2 \\ -3 & 4 \\\end(array) \right]=\left[ \begin(matrice) -14 & 4 \\ 0 & 10 \\\end(matrice )\droite]\]
Il s'avère que $A\cdot B\ne B\cdot A$. De plus, l'opération de multiplication n'est définie que pour les matrices cohérentes $A=\left[ m\times n \right]$ et $B=\left[ n\times k \right]$, mais personne n'a garanti qu'elles resteront cohérents s’ils sont échangés. Par exemple, les matrices $\left[ 2\times 3 \right]$ et $\left[ 3\times 5 \right]$ sont assez cohérentes dans l'ordre spécifié, mais les mêmes matrices $\left[ 3\times 5 \right] $ et $\left[ 2\times 3 \right]$ écrits en ordre inverse, ne sont plus convenus. Triste.:(
Parmi les matrices carrées d'une taille donnée $n$, il y aura toujours celles qui donneront le même résultat à la fois lorsqu'elles sont multipliées dans l'ordre direct et dans l'ordre inverse. Comment décrire toutes ces matrices (et combien il y en a en général) est le sujet d'une leçon distincte. Nous n'en parlerons pas aujourd'hui. :)
Cependant, la multiplication matricielle est associative :
\[\left(A\cdot B \right)\cdot C=A\cdot \left(B\cdot C \right)\]
Ainsi, lorsqu'il faut multiplier plusieurs matrices d'affilée à la fois, il n'est pas du tout nécessaire de le faire tout de suite : il est fort possible que certaines matrices adjacentes, une fois multipliées, donnent un résultat intéressant. Par exemple, une matrice nulle, comme dans le problème 2 discuté ci-dessus.
Dans les problèmes réels, nous devons le plus souvent multiplier des matrices carrées de taille $\left[ n\times n \right]$. L'ensemble de toutes ces matrices est noté $((M)^(n))$ (c'est-à-dire que les entrées $A=\left[ n\times n \right]$ et \ signifient la même chose), et cela signifiera la même chose. contiennent nécessairement la matrice $E$, qui est appelée matrice identité.
Définition. Une matrice identité de taille $n$ est une matrice $E$ telle que pour toute matrice carrée $A=\left[ n\times n \right]$ l'égalité est vraie :
Une telle matrice a toujours la même apparence : il y a des un sur sa diagonale principale et des zéros dans toutes les autres cellules.
\[\begin(align) & A\cdot \left(B+C \right)=A\cdot B+A\cdot C; \\ & \left(A+B \right)\cdot C=A\cdot C+B\cdot C. \\ \end(align)\]
En d’autres termes, si vous devez multiplier une matrice par la somme de deux autres, vous pouvez la multiplier par chacun de ces « deux autres » puis additionner les résultats. En pratique, nous devons généralement effectuer l'opération inverse : nous remarquons la même matrice, la sortons des parenthèses, effectuons une addition et ainsi nous simplifions la vie. :)
Remarque : pour décrire la distributivité, nous avons dû écrire deux formules : où la somme est dans le deuxième facteur et où la somme est dans le premier. Cela se produit précisément parce que la multiplication matricielle est non commutative (et en général, en algèbre non commutative, il y a beaucoup de choses amusantes qui ne viennent même pas à l'esprit lorsque l'on travaille avec des nombres ordinaires). Et si, par exemple, vous devez écrire cette propriété lors d'un examen, assurez-vous d'écrire les deux formules, sinon l'enseignant pourrait se mettre un peu en colère.
D'accord, c'étaient tous des contes de fées sur les matrices carrées. Et les rectangulaires ?
Le cas des matrices rectangulaires
Mais rien - tout est comme avec les carrés.
Tâche 3. Faites la multiplication :
\[\left[ \begin(matrice) \begin(matrice) 5 \\ 2 \\ 3 \\\end(matrice) & \begin(matrice) 4 \\ 5 \\ 1 \\\end(matrice) \ \\end(matrice) \right]\cdot \left[ \begin(array)(*(35)(r)) -2 & 5 \\ 3 & 4 \\\end(array) \right]\]
Solution. Nous avons deux matrices : $A=\left[ 3\times 2 \right]$ et $B=\left[ 2\times 2 \right]$. Notons les nombres indiquant les tailles d'affilée :
Comme vous pouvez le constater, les deux nombres centraux coïncident. Cela signifie que les matrices sont cohérentes et peuvent être multipliées. De plus, en sortie on obtient la matrice $C=\left[ 3\times 2 \right]$ :
\[\begin(align) & \left[ \begin(matrice) \begin(matrice) 5 \\ 2 \\ 3 \\\end(matrice) & \begin(matrice) 4 \\ 5 \\ 1 \\ \end(matrice) \\\end(matrice) \right]\cdot \left[ \begin(array)(*(35)(r)) -2 & 5 \\ 3 & 4 \\\end(array) \right]=\left[ \begin(array)(*(35)(r)) 5\cdot \left(-2 \right)+4\cdot 3 & 5\cdot 5+4\cdot 4 \\ 2 \cdot \left(-2 \right)+5\cdot 3 & 2\cdot 5+5\cdot 4 \\ 3\cdot \left(-2 \right)+1\cdot 3 & 3\cdot 5+1 \cdot 4 \\\end(array) \right]= \\ & =\left[ \begin(array)(*(35)(r)) 2 & 41 \\ 11 & 30 \\ -3 & 19 \ \\fin (tableau) \right]. \fin(aligner)\]
Tout est clair : la matrice finale comporte 3 lignes et 2 colonnes. Tout à fait $=\left[ 3\times 2 \right]$.
Réponse : $\left[ \begin(array)(*(35)(r)) \begin(array)(*(35)(r)) 2 \\ 11 \\ -3 \\\end(array) & \begin(matrice) 41 \\ 30 \\ 19 \\\end(matrice) \\\end(array) \right]$.
Examinons maintenant l'une des meilleures tâches de formation pour ceux qui commencent tout juste à travailler avec des matrices. Dans ce document, vous ne devez pas seulement multiplier deux comprimés, mais d'abord déterminer : une telle multiplication est-elle autorisée ?
Problème 4. Trouver tous les produits de matrices par paires possibles :
\\]; $B=\left[ \begin(matrice) \begin(matrice) 0 \\ 2 \\ 0 \\ 4 \\\end(matrice) & \begin(matrice) 1 \\ 0 \\ 3 \\ 0 \ \\end(matrice) \\\end(matrice) \right]$; $C=\left[ \begin(matrix)0 & 1 \\ 1 & 0 \\\end(matrix) \right]$.
Solution. Tout d'abord, notons les tailles des matrices :
\;\ B=\left[ 4\times 2 \right];\ C=\left[ 2\times 2 \right]\]
On constate que la matrice $A$ ne peut être réconciliée qu'avec la matrice $B$, puisque le nombre de colonnes de $A$ est 4, et seul $B$ a ce nombre de lignes. On peut donc retrouver le produit :
\\cdot \left[ \begin(array)(*(35)(r)) 0 & 1 \\ 2 & 0 \\ 0 & 3 \\ 4 & 0 \\\end(array) \right]=\ gauche[ \begin(array)(*(35)(r))-10 & 7 \\ 10 & 7 \\\end(array) \right]\]
Je suggère au lecteur de suivre les étapes intermédiaires de manière indépendante. Je noterai seulement qu'il vaut mieux déterminer la taille de la matrice résultante à l'avance, avant même tout calcul :
\\cdot \left[ 4\times 2 \right]=\left[ 2\times 2 \right]\]
Autrement dit, on supprime simplement les coefficients de « transit » qui assuraient la cohérence des matrices.
Quelles autres options sont possibles ? Bien sûr, on peut trouver $B\cdot A$, puisque $B=\left[ 4\times 2 \right]$, $A=\left[ 2\times 4 \right]$, donc la paire ordonnée $\ left(B ;A \right)$ est cohérent, et la dimension du produit sera :
\\cdot \left[ 2\times 4 \right]=\left[ 4\times 4 \right]\]
En bref, le résultat sera une matrice $\left[ 4\times 4 \right]$, dont les coefficients peuvent être facilement calculés :
\\cdot \left[ \begin(array)(*(35)(r)) 1 & -1 & 2 & -2 \\ 1 & 1 & 2 & 2 \\\end(array) \right]=\ gauche[ \begin(array)(*(35)(r))1 & 1 & 2 & 2 \\ 2 & -2 & 4 & -4 \\ 3 & 3 & 6 & 6 \\ 4 & -4 & 8 & -8 \\\end(tableau) \right]\]
Évidemment, vous pouvez également vous mettre d'accord sur $C\cdot A$ et $B\cdot C$ - et c'est tout. Par conséquent, nous écrivons simplement les produits résultants :
C'était facile.:)
Réponse : $AB=\left[ \begin(array)(*(35)(r)) -10 & 7 \\ 10 & 7 \\\end(array) \right]$; $BA=\left[ \begin(array)(*(35)(r)) 1 & 1 & 2 & 2 \\ 2 & -2 & 4 & -4 \\ 3 & 3 & 6 & 6 \\ 4 & -4 & 8 & -8 \\\end(tableau) \right]$; $CA=\left[ \begin(array)(*(35)(r)) 1 & 1 & 2 & 2 \\ 1 & -1 & 2 & -2 \\\end(array) \right]$; $BC=\left[ \begin(array)(*(35)(r))1 & 0 \\ 0 & 2 \\ 3 & 0 \\ 0 & 4 \\\end(array) \right]$.
En général, je recommande fortement de réaliser cette tâche vous-même. Et une autre tâche similaire qui fait partie des devoirs. Ces pensées apparemment simples vous aideront à pratiquer toutes les étapes clés de la multiplication matricielle.
Mais l'histoire ne s'arrête pas là. Passons aux cas particuliers de multiplication. :)
Vecteurs de lignes et vecteurs de colonnes
L’une des opérations matricielles les plus courantes est la multiplication par une matrice comportant une ligne ou une colonne.
Définition. Un vecteur colonne est une matrice de taille $\left[ m\times 1 \right]$, c'est-à-dire composé de plusieurs lignes et d'une seule colonne.
Un vecteur ligne est une matrice de taille $\left[ 1\times n \right]$, c'est-à-dire composé d'une ligne et de plusieurs colonnes.
En fait, nous avons déjà rencontré ces objets. Par exemple, un vecteur tridimensionnel ordinaire issu de la stéréométrie $\overrightarrow(a)=\left(x;y;z \right)$ n'est rien de plus qu'un vecteur ligne. D'un point de vue théorique, il n'y a quasiment aucune différence entre les lignes et les colonnes. Il vous suffit d'être prudent lors de la coordination avec les matrices multiplicatrices environnantes.
Tâche 5. Faites la multiplication :
\[\left[ \begin(array)(*(35)(r)) 2 & -1 & 3 \\ 4 & 2 & 0 \\ -1 & 1 & 1 \\\end(array) \right] \cdot \left[ \begin(array)(*(35)(r)) 1 \\ 2 \\ -1 \\\end(array) \right]\]
Solution. Nous avons ici le produit de matrices appariées : $\left[ 3\times 3 \right]\cdot \left[ 3\times 1 \right]=\left[ 3\times 1 \right]$. Retrouvons cette pièce :
\[\left[ \begin(array)(*(35)(r)) 2 & -1 & 3 \\ 4 & 2 & 0 \\ -1 & 1 & 1 \\\end(array) \right] \cdot \left[ \begin(array)(*(35)(r)) 1 \\ 2 \\ -1 \\\end(array) \right]=\left[ \begin(array)(*(35 )(r)) 2\cdot 1+\left(-1 \right)\cdot 2+3\cdot \left(-1 \right) \\ 4\cdot 1+2\cdot 2+0\cdot 2 \ \ -1\cdot 1+1\cdot 2+1\cdot \left(-1 \right) \\\end(array) \right]=\left[ \begin(array)(*(35)(r) ) -3 \\ 8 \\ 0 \\\end(tableau) \right]\]
Réponse : $\left[ \begin(array)(*(35)(r))-3 \\ 8 \\ 0 \\\end(array) \right]$.
Tâche 6. Faites la multiplication :
\[\left[ \begin(array)(*(35)(r)) 1 & 2 & -3 \\\end(array) \right]\cdot \left[ \begin(array)(*(35) (r)) 3 & 1 & -1 \\ 4 & -1 & 3 \\ 2 & 6 & 0 \\\end(array) \right]\]
Solution. Encore une fois, tout est d'accord : $\left[ 1\times 3 \right]\cdot \left[ 3\times 3 \right]=\left[ 1\times 3 \right]$. On compte le produit :
\[\left[ \begin(array)(*(35)(r)) 1 & 2 & -3 \\\end(array) \right]\cdot \left[ \begin(array)(*(35) (r)) 3 & 1 & -1 \\ 4 & -1 & 3 \\ 2 & 6 & 0 \\\end(array) \right]=\left[ \begin(array)(*(35)( ) r))5 & -19 & 5 \\\end(array) \right]\]
Réponse : $\left[ \begin(matrix) 5 & -19 & 5 \\\end(matrix) \right]$.
Comme vous pouvez le voir, en multipliant un vecteur ligne et un vecteur colonne par Matrice Carrée nous obtenons toujours une ligne ou une colonne de la même taille que la sortie. Ce fait a de nombreuses applications - de la résolution d'équations linéaires à toutes sortes de transformations de coordonnées (qui en fin de compte se résument également à des systèmes d'équations, mais ne parlons pas de choses tristes).
Je pense que tout était évident ici. Passons à la dernière partie de la leçon d'aujourd'hui.
Exponentiation matricielle
Parmi toutes les opérations de multiplication, l'exponentiation mérite une attention particulière : c'est lorsque l'on multiplie plusieurs fois le même objet par lui-même. Les matrices ne font pas exception ; elles peuvent également être élevées à diverses puissances.
De tels travaux sont toujours convenus :
\\cdot \left[ n\times n \right]=\left[ n\times n \right]\]
Et ils sont désignés exactement de la même manière que les diplômes ordinaires :
\[\begin(align) & A\cdot A=((A)^(2)); \\ & A\cdot A\cdot A=((A)^(3)); \\ & \underbrace(A\cdot A\cdot \ldots \cdot A)_(n)=((A)^(n)). \\ \fin(aligner)\]
À première vue, tout est simple. Voyons à quoi cela ressemble en pratique :
Tâche 7. Élever la matrice à la puissance indiquée :
$((\left[ \begin(matrix) 1 & 1 \\ 0 & 1 \\\end(matrix) \right])^(3))$
Solution. Bon, d'accord, construisons. Tout d'abord, mettons les choses au carré :
\[\begin(align) & ((\left[ \begin(matrix) 1 & 1 \\ 0 & 1 \\\end(matrix) \right])^(2))=\left[ \begin(matrix ) 1 & 1 \\ 0 & 1 \\\end(matrice) \right]\cdot \left[ \begin(matrice) 1 & 1 \\ 0 & 1 \\\end(matrice) \right]= \\ & =\left[ \begin(array)(*(35)(r)) 1\cdot 1+1\cdot 0 & 1\cdot 1+1\cdot 1 \\ 0\cdot 1+1\cdot 0 & 0\cdot 1+1\cdot 1 \\\end(array) \right]= \\ & =\left[ \begin(array)(*(35)(r)) 1 & 2 \\ 0 & 1 \ \\end(tableau) \right] \end(align)\]
\[\begin(align) & ((\left[ \begin(matrix) 1 & 1 \\ 0 & 1 \\\end(matrix) \right])^(3))=((\left[ \begin (matrice) 1 & 1 \\ 0 & 1 \\\end(matrice) \right])^(3))\cdot \left[ \begin(matrice) 1 & 1 \\ 0 & 1 \\\end( matrice) \right]= \\ & =\left[ \begin(array)(*(35)(r)) 1 & 2 \\ 0 & 1 \\\end(array) \right]\cdot \left[ \begin(matrix) 1 & 1 \\ 0 & 1 \\\end(matrix) \right]= \\ & =\left[ \begin(array)(*(35)(r)) 1 & 3 \\ 0 & 1 \\\end(tableau) \right] \end(align)\]
C'est tout.:)
Réponse : $\left[ \begin(matrix)1 & 3 \\ 0 & 1 \\\end(matrix) \right]$.
Problème 8. Élevez la matrice à la puissance indiquée :
\[((\left[ \begin(matrix) 1 & 1 \\ 0 & 1 \\\end(matrix) \right])^(10))\]
Solution. Ne pleurez pas maintenant sur le fait que « le diplôme est trop grand », « le monde n’est pas juste » et « les enseignants ont complètement perdu leurs rivages ». C'est en fait simple :
\[\begin(align) & ((\left[ \begin(matrix) 1 & 1 \\ 0 & 1 \\\end(matrix) \right])^(10))=((\left[ \begin (matrice) 1 & 1 \\ 0 & 1 \\\end(matrice) \right])^(3))\cdot ((\left[ \begin(matrice) 1 & 1 \\ 0 & 1 \\\ end(matrice) \right])^(3))\cdot ((\left[ \begin(matrix) 1 & 1 \\ 0 & 1 \\\end(matrix) \right])^(3))\ cdot \left[ \begin(matrix) 1 & 1 \\ 0 & 1 \\\end(matrix) \right]= \\ & =\left(\left[ \begin(matrix) 1 & 3 \\ 0 & 1 \\\end(matrice) \right]\cdot \left[ \begin(matrice) 1 & 3 \\ 0 & 1 \\\end(matrice) \right] \right)\cdot \left(\left[ \begin(matrice) 1 & 3 \\ 0 & 1 \\\end(matrice) \right]\cdot \left[ \begin(matrice) 1 & 1 \\ 0 & 1 \\\end(matrice) \right ] \right)= \\ & =\left[ \begin(matrice) 1 & 6 \\ 0 & 1 \\\end(matrice) \right]\cdot \left[ \begin(matrice) 1 & 4 \\ 0 & 1 \\\end(matrice) \right]= \\ & =\left[ \begin(matrice) 1 & 10 \\ 0 & 1 \\\end(matrice) \right] \end(align)\ ]
Notez que dans la deuxième ligne, nous avons utilisé l’associativité de multiplication. En fait, nous l'avons utilisé dans la tâche précédente, mais il y était implicite.
Réponse : $\left[ \begin(matrix) 1 & 10 \\ 0 & 1 \\\end(matrix) \right]$.
Comme vous pouvez le constater, il n’y a rien de compliqué à élever une matrice à une puissance. Dernier exemple peut être résumé :
\[((\left[ \begin(matrix) 1 & 1 \\ 0 & 1 \\\end(matrix) \right])^(n))=\left[ \begin(array)(*(35) (r)) 1 & n \\ 0 & 1 \\\end(array) \right]\]
Ce fait est facile à prouver par induction mathématique ou multiplication directe. Cependant, il n'est pas toujours possible de détecter de tels schémas lors de l'élévation à une puissance. Soyez donc prudent : souvent, multiplier plusieurs matrices « au hasard » s'avère plus facile et plus rapide que de rechercher une sorte de modèle.
En général, ne cherchez pas de sens supérieur là où il n’y en a pas. En conclusion, considérons l'exponentiation d'une matrice plus grande - jusqu'à $\left[ 3\times 3 \right]$.
Problème 9. Élevez la matrice à la puissance indiquée :
\[((\left[ \begin(matrix) 0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \\\end(matrix) \right])^(3))\]
Solution. Ne cherchons pas de modèles. Nous travaillons à l'avance :
\[((\left[ \begin(matrix) 0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \\\end(matrix) \right])^(3))=(( \left[ \begin(matrice) 0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \\\end(matrice) \right])^(2))\cdot \left[ \begin (matrice)0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \\\end(matrice) \right]\]
Commençons par mettre au carré cette matrice :
\[\begin(align) & ((\left[ \begin(matrix) 0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \\\end(matrix) \right])^( 2))=\left[ \begin(matrice) 0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \\\end(matrice) \right]\cdot \left[ \begin(matrice ) 0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \\\end(matrice) \right]= \\ & =\left[ \begin(array)(*(35)(r )) 2 & 1 & 1 \\ 1 & 2 & 1 \\ 1 & 1 & 2 \\\end(array) \right] \end(align)\]
Maintenant, découpons-le :
\[\begin(align) & ((\left[ \begin(matrix) 0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \\\end(matrix) \right])^( 3))=\left[ \begin(array)(*(35)(r)) 2 & 1 & 1 \\ 1 & 2 & 1 \\ 1 & 1 & 2 \\\end(array) \right] \cdot \left[ \begin(matrice) 0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \\\end(matrice) \right]= \\ & =\left[ \begin( tableau)(*(35)(r)) 2 & 3 & 3 \\ 3 & 2 & 3 \\ 3 & 3 & 2 \\\end(array) \right] \end(align)\]
C'est tout. Le problème est résolu.
Réponse : $\left[ \begin(matrix) 2 & 3 & 3 \\ 3 & 2 & 3 \\ 3 & 3 & 2 \\\end(matrix) \right]$.
Comme vous pouvez le constater, le volume de calculs est devenu plus important, mais le sens n'a pas changé du tout. :)
Ceci conclut la leçon. La prochaine fois, nous considérerons l'opération inverse : en utilisant le produit existant, nous rechercherons les facteurs d'origine.
Comme vous l'avez probablement déjà deviné, nous parlerons de la matrice inverse et des méthodes pour la trouver.
Cours 6. Algorithmes numériques parallèles pour résoudre des problèmes typiques de mathématiques computationnelles : multiplication matricielle.
Multiplier une matrice par un vecteur. Atteindre les performances les plus élevées possibles. Exploiter le parallélisme de niveau intermédiaire. Organisation du calcul parallèle à p = n. Utilisation d'un ensemble limité de processeurs. Multiplication matricielle. Analyse macro-opérationnelle d'algorithmes de résolution de problèmes. Organisation du parallélisme basé sur le partage de données.
Multiplier une matrice par un vecteur
Le problème de la multiplication d'une matrice par un vecteur est défini par les relations
Ainsi, l'obtention du vecteur résultant implique de répéter des opérations similaires de multiplication des lignes de la matrice et du vecteur. L'obtention de chacune de ces opérations implique la multiplication élément par élément des éléments d'une ligne d'une matrice et d'un vecteur et la sommation ultérieure des produits résultants. Le nombre total d'opérations scalaires requises est estimé par la quantité
Comme il ressort des actions effectuées lors de la multiplication d'une matrice et d'un vecteur, méthodes parallèles des solutions au problème peuvent être obtenues sur la base d’algorithmes de sommation parallèles (voir paragraphe 4.1). Dans cette section, l'analyse des méthodes de parallélisation sera complétée par la prise en compte des problématiques d'organisation du calcul parallèle en fonction du nombre de processeurs disponibles à l'usage. De plus, à l'aide de l'exemple du problème de multiplication d'une matrice par un vecteur, l'attention sera attirée sur la nécessité de sélectionner la topologie du système informatique la plus adaptée (canaux de communication existants entre processeurs) pour réduire les coûts d'organisation de l'interaction interprocesseur.
Atteindre les performances les plus élevées possibles ()
Analysons les dépendances d'information dans l'algorithme de multiplication matrice-vecteur pour la sélection moyens possibles parallélisation. Comme vous pouvez le constater, les opérations de multiplication de lignes individuelles d'une matrice par un vecteur effectuées lors des calculs sont indépendantes et peuvent être effectuées en parallèle ;
La multiplication de chaque ligne par un vecteur implique des opérations de multiplication indépendantes par éléments et peut également être effectuée en parallèle ;
La sommation des produits résultants dans chaque opération de multiplication d'une ligne matricielle par un vecteur peut être effectuée en utilisant l'une des variantes précédemment envisagées de l'algorithme de sommation (algorithme séquentiel, schémas en cascade conventionnels et modifiés).
Ainsi, le nombre maximum requis de processeurs est déterminé par la valeur
L'utilisation d'un tel nombre de processeurs peut être représentée comme suit. De nombreux processeurs sont divisés en groupes
,
dont chacun représente un ensemble de processeurs pour effectuer l'opération de multiplication d'une ligne individuelle d'une matrice par un vecteur. Au début des calculs, un élément de ligne matricielle et un élément vectoriel correspondant sont envoyés à chaque processeur du groupe. Ensuite, chaque processeur effectue une opération de multiplication. Les calculs ultérieurs sont ensuite effectués à l'aide d'un schéma de sommation en cascade. Pour illustration sur la Fig. 6.1 montre le schéma de calcul pour les processeurs d'un groupe avec une dimension matricielle de .
Riz. 6.1. Schéma informatique pour multiplier une ligne matricielle par un vecteur
Le temps d'exécution d'un algorithme parallèle lors de l'utilisation de processeurs est déterminé par le temps d'exécution de l'opération de multiplication parallèle et le temps d'exécution du circuit en cascade
En conséquence, les indicateurs d'efficacité de l'algorithme sont déterminés par les relations suivantes :
, 
,
Pour le problème de multiplication matrice-vecteur considéré, les topologies les plus adaptées sont les structures qui fournissent transfert rapide données (chemins de longueur unitaire) dans un circuit de sommation en cascade (voir Fig. 4.5). De telles topologies sont une structure avec système complet Connexions ( graphique complet) Et hypercube. D'autres topologies entraînent une augmentation du temps de communication en raison de routes de transfert de données plus longues. Ainsi, avec un ordre linéaire des processeurs avec un système de connexions uniquement avec les voisins les plus proches à gauche et à droite ( règle ou anneau) pour un schéma en cascade, la longueur du chemin de transmission de chaque somme partielle reçue à l'itération , , est égale à . Si nous supposons que la transmission de données le long d'un chemin dans des topologies à structure linéaire nécessite des opérations de transmission de données, le nombre total d'opérations parallèles (durée totale des chemins) de transmission de données est déterminé par la valeur
(hors transferts de données pour le chargement initial des processeurs).
Application d'un système informatique à topologie rectangulaire réseau bidimensionnel la taille conduit à une interprétation simple et claire des calculs effectués (la structure du réseau correspond à la structure des données traitées). Pour une telle topologie, il est préférable de placer les lignes de la matrice le long des grilles horizontales ; dans ce cas, les éléments du vecteur doivent être répartis le long des verticales du système informatique. Les calculs avec cette disposition des données peuvent être effectués en parallèle le long des lignes de la grille ; par conséquent, le nombre total de transferts de données correspond aux résultats de Ruler().
Les actions de communication effectuées lors de la résolution d'une tâche donnée consistent à transférer des données entre des paires de processeurs MCS. Une analyse détaillée de la durée de mise en œuvre de ces opérations est réalisée au paragraphe 3.3.
4. Recommandations pour la mise en œuvre d'un algorithme parallèle. Lors de la mise en œuvre d'un algorithme parallèle, il est conseillé de souligner l'étape initiale de chargement des processeurs utilisés avec les données initiales. Plus simplement, une telle initialisation est fournie avec une topologie d'un système informatique avec une topologie sous la forme graphique complet(le téléchargement est fourni à l'aide d'une opération de transfert de données parallèle). Lors de l'organisation de plusieurs processeurs sous la forme hypercube Il peut être utile d'avoir un contrôle à deux niveaux du processus d'amorçage, dans lequel le processeur de contrôle central garantit que les lignes matricielles et vectorielles sont envoyées aux processeurs de contrôle des groupes de processeurs, qui, à leur tour, envoient les éléments de la matrice. et des lignes vectorielles vers les processeurs exécutifs. Pour les topologies sous la forme dirigeants ou anneaux nécessite des opérations de transfert de données séquentielles avec une quantité successivement décroissante de données transférées des éléments vers les éléments.
Utiliser le parallélisme de niveau intermédiaire()
1. Choisir une méthode de calcul parallèle. Lorsque le nombre disponible de processeurs utilisés () diminue, le schéma de sommation en cascade habituel lors de l'exécution d'opérations de multiplication de lignes matricielles par vecteur devient inapplicable. Pour simplifier la présentation du matériel, supposons et utilisons un schéma en cascade modifié. Dans ce cas, la charge initiale de chaque processeur augmente et le processeur est chargé () par parties des lignes de la matrice et du vecteur. Le temps d'exécution de l'opération de multiplication d'une matrice par un vecteur peut être estimé comme
Lors de l'utilisation du nombre de processeurs requis pour mettre en œuvre le schéma en cascade modifié, c'est-à-dire à , cette expression donne une estimation du temps d'exécution 
(à ).
Lorsque le nombre de processeurs est , lorsque le temps d'exécution de l'algorithme est estimé à , un nouveau schéma d'exécution parallèle des calculs peut être proposé, dans lequel pour chaque itération de sommation en cascade, ensembles de processeurs qui ne se chevauchent pas. Avec cette approche, le nombre de processeurs disponibles s'avère suffisant pour mettre en œuvre une seule opération de multiplication d'une ligne matricielle et d'un vecteur. De plus, lors de l'exécution de la prochaine itération de sommation en cascade, les processeurs chargés d'exécuter toutes les itérations précédentes sont libres. Cependant, cet inconvénient de l’approche proposée peut être transformé en avantage en utilisant des processeurs inactifs pour traiter les lignes suivantes de la matrice. En conséquence, le schéma suivant peut être formé convoyeur effectuer une multiplication matricielle et vectorielle :
Un ensemble de processeurs est divisé en groupes de processeurs disjoints
,
dans ce cas, le groupe , , est constitué de processeurs et est utilisé pour effectuer des itérations de l'algorithme en cascade (le groupe est utilisé pour implémenter la multiplication élément par élément) ; nombre total de processeurs ;
L'initialisation des calculs consiste à charger élément par élément les processeurs du groupe avec les valeurs de 1 ligne de la matrice et du vecteur ; après le chargement initial, une opération parallèle de multiplication par éléments et de mise en œuvre ultérieure du circuit de sommation en cascade habituel est effectuée ;
Lors de l'exécution de calculs, chaque fois après l'achèvement d'une opération de multiplication élément par élément, les processeurs du groupe sont chargés avec les éléments de la ligne suivante de la matrice et le processus de calcul est lancé pour les données nouvellement chargées.
Suite à l'application de l'algorithme décrit, de nombreux processeurs implémentent un pipeline pour effectuer l'opération de multiplication d'une ligne matricielle par un vecteur. Sur un tel convoyeur, il peut y avoir simultanément plusieurs rangées distinctes de matrice à différentes étapes de traitement. Ainsi, par exemple, après multiplication élément par élément des éléments de la première ligne et du vecteur, les processeurs du groupe effectueront la première itération de l'algorithme en cascade pour la première ligne de la matrice, et les processeurs du groupe effectueront effectuer une multiplication élément par élément des valeurs de la deuxième ligne de la matrice, etc. Pour illustration sur la Fig. 6.2 montre la situation du processus de calcul après 2 itérations du pipeline à .
Riz. 6.2. État du pipeline pour l'opération de multiplication d'une ligne matricielle par un vecteur après avoir effectué 2 itérations
2. Évaluation des indicateurs de performance des algorithmes. La multiplication de la première ligne par vecteur selon le schéma en cascade sera complétée comme d'habitude après l'exécution des () opérations parallèles. Pour les autres lignes - conformément au schéma de pipeline d'organisation des calculs - l'apparition des résultats de multiplication de chaque ligne suivante se produira après l'achèvement de chaque itération suivante du pipeline. En conséquence, le temps total d’exécution de l’opération de multiplication matrice-vecteur peut être exprimé comme
Cette évaluation est légèrement plus long que le temps d'exécution de l'algorithme parallèle décrit dans le paragraphe précédent (), cependant, la méthode nouvellement proposée nécessite moins de données transmises (le vecteur n'est envoyé qu'une seule fois). De plus, l’utilisation d’un schéma pipeline conduit à l’apparition plus précoce de certains résultats de calcul (ce qui peut être utile dans un certain nombre de situations de traitement de données).
De ce fait, les indicateurs d'efficacité de l'algorithme sont déterminés par les relations suivantes :
3. Sélection de la topologie du système informatique. La topologie appropriée d'un système informatique est entièrement déterminée par le circuit informatique - il s'agit d'une arbre binaire hauteur Le nombre de transferts de données avec une telle topologie de réseau est déterminé par le nombre total d'itérations effectuées par le pipeline, c'est-à-dire
.
L'initialisation des calculs commence par les feuilles de l'arbre, les résultats de la sommation sont accumulés dans le processeur racine.
L'analyse de la complexité des actions de communication effectuées pour les systèmes informatiques avec d'autres topologies de communication interprocesseurs est censée être effectuée comme une tâche indépendante (voir également la clause 3.4).
Organisation du calcul parallèle dans
1. Choisir une méthode de calcul parallèle. Lors de l'utilisation de processeurs pour multiplier une matrice par un vecteur, l'algorithme de multiplication parallèle ligne par ligne évoqué précédemment dans le manuel peut être utilisé, dans lequel les lignes de la matrice sont réparties entre les processeurs ligne par ligne et chaque processeur implémente l'opération de multiplication de n'importe quelle ligne individuelle de la matrice par un vecteur. Une autre façon possible d'organiser le calcul parallèle pourrait être de construire circuit pipeline pour l'opération de multiplication d'une ligne matricielle par un vecteur(produit scalaire de vecteurs) en disposant tous les processeurs disponibles dans une séquence linéaire ( dirigeants).
Un tel schéma de calcul peut être défini comme suit. Imaginons l'ensemble des processeurs comme une séquence linéaire (voir Fig. 4.7) :
Chaque processeur, , permet de multiplier les éléments d'une colonne matricielle et un élément vectoriel. Les calculs effectués sur chaque processeur , , sont les suivants :
L'élément suivant de la colonne matricielle est demandé ;
Les éléments et se multiplient ;
Le résultat des calculs du processeur précédent est demandé ;
Les valeurs sont ajoutées ;
Le résultat obtenu est envoyé au processeur suivant.
Riz. 6.3. État du pipeline linéaire pour l'opération de multiplication d'une ligne matricielle par un vecteur après avoir effectué deux itérations
Lors de l'initialisation du schéma décrit, vous devez effectuer un certain nombre d'actions supplémentaires :
Lors de la première itération, chaque processeur demande en plus un élément du vecteur ;
Pour synchroniser les calculs (lors de l'exécution de l'itération suivante du circuit, le résultat du calcul du processeur précédent est demandé) au stade d'initialisation, le processeur, , effectue () une boucle d'attente.
De plus, pour l'homogénéité du circuit décrit pour le premier processeur, qui ne dispose pas de processeur précédent, il convient d'introduire une opération d'addition à vide ( 
).
Pour illustration sur la Fig. La figure 6.3 montre l'état du processus de calcul après la deuxième itération du pipeline à .
2. Évaluation des indicateurs de performance des algorithmes. La multiplication de la première ligne par le vecteur selon le schéma pipeline décrit sera terminée après l'exécution des opérations parallèles (). Le résultat de la multiplication des lignes suivantes se produira après la fin de chaque itération suivante du pipeline (rappelons que l'itération de chaque processeur comprend l'exécution d'opérations de multiplication et d'addition). De ce fait, le temps total d’exécution d’une opération de multiplication matrice-vecteur peut être exprimé comme suit :
Cette estimation est également supérieure au temps d'exécution minimum possible de l'algorithme parallèle à . L'utilité de l'utilisation d'un schéma informatique pipeline réside, comme indiqué dans le paragraphe précédent, dans la réduction de la quantité de données transmises et dans l'apparition plus précoce de certains résultats de calcul.
Les indicateurs d'efficacité de ce schéma informatique sont déterminés par les relations :
, 
,
3. Sélection de la topologie du système informatique. La topologie nécessaire du système informatique pour exécuter l'algorithme décrit est uniquement déterminée par le schéma informatique proposé - il s'agit d'un ensemble de processeurs ordonnés linéairement ( règle).
Utilisation d'un ensemble limité de processeurs ()
1. Choisir une méthode de calcul parallèle. En réduisant le nombre de processeurs à une valeur, un schéma de calcul parallèle pour la multiplication matrice-vecteur peut être obtenu en adaptant l'algorithme de multiplication ligne par ligne. Dans ce cas, le circuit en cascade de sommation des résultats de la multiplication élément par élément dégénère et l'opération de multiplication d'une ligne matricielle par un vecteur est entièrement réalisée sur un seul processeur. Le schéma de calcul obtenu avec cette approche peut être spécifié comme suit :
Un vecteur et des lignes matricielles sont envoyés à chacun des processeurs disponibles ;
L'exécution d'une opération de multiplication de lignes matrice-vecteur est effectuée à l'aide d'un algorithme séquentiel conventionnel.
Il convient de noter que la taille de la matrice ne peut pas être un multiple du nombre de processeurs et que les lignes de la matrice ne peuvent alors pas être divisées de manière égale entre les processeurs. Dans ces situations, vous pouvez vous écarter de l'exigence de chargement uniforme des processeurs et, afin d'obtenir un schéma de calcul plus simple, accepter la règle selon laquelle les données sont placées sur les processeurs uniquement ligne par ligne (c'est-à-dire que les éléments d'une ligne de la matrice ne peuvent pas être réparti entre plusieurs processeurs). Un nombre inégal de lignes entraîne une charge de calcul différente sur les processeurs ; Ainsi, l'achèvement des calculs (la durée totale de résolution du problème) sera déterminé par le temps de fonctionnement du processeur le plus chargé (dans ce cas, une partie de ce temps total, les processeurs individuels peuvent être inactifs en raison de l'épuisement de leur part de calculs). La charge inégale des processeurs réduit l'efficacité de l'utilisation de MCS et, en considérant cet exemple, nous pouvons conclure que problème d'équilibrage
3. Sélection de la topologie du système informatique. Conformément à la nature des interactions interprocesseurs réalisées dans le schéma informatique proposé, l'organisation des processeurs sous forme de étoiles(voir Fig. 1.1). Un processeur de contrôle d'une telle topologie peut être utilisé pour charger des processeurs informatiques avec des données initiales et pour recevoir les résultats des calculs effectués.
Multiplication matricielle
Le problème de la multiplication matrice-matrice est défini par les relations
.
(pour simplifier la présentation, nous supposerons que les matrices multipliées et sont carrées et d'ordre ).
Une analyse des méthodes possibles d'exécution parallèle de cette tâche peut être réalisée par analogie avec la considération du problème de la multiplication d'une matrice par un vecteur. Laissant une telle analyse pour une étude indépendante, nous utiliserons l'exemple du problème de multiplication matricielle pour montrer l'utilisation de plusieurs approches générales qui nous permettent de former des méthodes parallèles pour résoudre des problèmes complexes.
Dans le système MatLab, il est assez simple d'effectuer des opérations mathématiques sur des matrices et des vecteurs. Considérons d'abord des opérations simples d'addition et de multiplication de matrices et de vecteurs. Soit deux vecteurs
une = ; % vecteur de ligne
b = ; %vecteur colonne
alors la multiplication de ces deux vecteurs peut s'écrire comme suit
c = a*b; %c=1+2+3+4+5=16
d = b*a; % d – matrice de 5x5 éléments
Selon les opérations sur les vecteurs, multiplier un vecteur ligne par un vecteur colonne donne un nombre, et multiplier un vecteur colonne par un vecteur ligne donne une matrice bidimensionnelle, qui est le résultat des calculs de l'exemple ci-dessus, c'est-à-dire
L'addition et la soustraction de deux vecteurs s'écrivent comme suit :
a1 = ;
a2 = ;
c = a1+a2; % c = ;
c = a2-a1 ; % c = ;
Notez que les opérations d'addition et de soustraction peuvent être effectuées entre deux vecteurs colonnes ou deux vecteurs lignes. Sinon, MatLab affichera un message d'erreur, car Des vecteurs de types différents ne peuvent pas être ajoutés. C'est le cas de toutes les opérations arithmétiques illégales : si elles ne peuvent pas être calculées, MatLab signalera une erreur et le programme se terminera sur la ligne correspondante.
Les opérations de multiplication et d'addition entre matrices s'effectuent de la même manière :
UNE = ;
B = un(3);
C = A+B ; % ajout de deux matrices de même taille
D = A+5 ; % d'ajout de matrice et de nombre
E = A*B ; % multiplication de la matrice A par B
F = B*A ; % multiplication de la matrice B par A
G = 5*A ; % en multipliant une matrice par un nombre
Les opérations de calcul de la matrice inverse, ainsi que de transposition des matrices et des vecteurs, s'écrivent comme suit :
une = ; % vecteur de ligne
b = a'; % vecteur colonne formé par
% en transposant le vecteur ligne a.
UNE = ; % Matrice d'éléments 3x3
B = une*UNE ; %B = – vecteur ligne
C = A*b ; %C = – vecteur colonne
D = a*A*a' ; % D = 45 – nombre, somme des éléments de la matrice A
E = A' ; % E – matrice transposée A
F = inv(A); % F – matrice inverse A
G = A^-1 ; % G – matrice inverse A
D’après l’exemple ci-dessus, il ressort clairement que l’opération de transposition de matrices et de vecteurs est indiquée par le symbole ‘ (apostrophe), qui est placé après le nom du vecteur ou de la matrice. Le calcul de l'inverse d'une matrice peut être effectué en appelant la fonction inv() ou en élevant la matrice à la puissance -1. Le résultat dans les deux cas sera le même et deux méthodes de calcul sont conçues pour faciliter l'utilisation lors de la mise en œuvre d'algorithmes différents.
Si, au cours du processus de calcul, il est nécessaire de multiplier, diviser ou élever des éléments d'un vecteur ou d'une matrice élément par élément, alors les opérateurs suivants sont utilisés pour cela :
.* - multiplication par élément ;
./ et.\ - divisions élément par élément ;
.^ - exponentiation par élément.
Regardons comment fonctionnent ces opérateurs à l'aide de l'exemple suivant.
une = ; % vecteur de ligne
b = ; % vecteur de ligne
c = a.*b; %c=
A = un(3); % Matrice 3x3 composée de uns
B = ; % matrice 3x3
C = A.*B; % matrice 3x3 composée de 
D = A./B; % matrice 3x3 composée de 
E = A.\B; % matrice 3x3 composée de 
F = A.^2 ; % mettant au carré les éléments de la matrice A
Pour conclure cette section, nous considérerons plusieurs fonctions utiles lorsque l'on travaille avec des vecteurs et des matrices.
Pour trouver la valeur maximale d'un élément vectoriel, utilisez la fonction standard max(), qui renvoie la valeur maximale trouvée de l'élément et sa position (index) :
une = ;
= maximum(une); % v = 6, je = 2 ;
v = max(une); % v = 6 ;
L'exemple ci-dessus montre deux différentes façons appeler la fonction max(). Dans le premier cas, la valeur maximale de l'élément et son indice dans le vecteur sont déterminés, et dans le second, uniquement la valeur maximale de l'élément.
Dans le cas des matrices, cette fonction détermine les valeurs maximales figurant dans les colonnes, comme le montre l'exemple ci-dessous :
UNE = ;
= maximum(A); %V=,Je=
V = maximum(UNE); %V=
La syntaxe complète de la fonction max() peut être trouvée en tapant la commande dans la fenêtre de commande MatLab
aide<название функции>
La fonction min() fonctionne de la même manière, qui détermine valeur minimumélément d'un vecteur ou d'une matrice et son indice.
Un autre fonction utile travailler avec des matrices et des vecteurs est la fonction sum(), qui calcule la somme des valeurs des éléments vectoriels ou des colonnes de la matrice :
une = ;
s = somme(a); % s = 3+5+4+2+1=15
UNE = ;
S1 = somme(A); %S1=
S2 = somme(somme(A)); %S2=39
Lors du calcul de la somme S2, la somme des valeurs des éléments de la matrice A est d'abord calculée en colonnes, puis en lignes. De ce fait, la variable S2 contient la somme des valeurs de tous les éléments de la matrice A.
Pour trier les valeurs des éléments d'un vecteur ou d'une matrice par ordre croissant ou décroissant, utilisez la fonction sort() comme suit :
une = ;
b1 = trier(a); %b1=
b2 = trier(a, 'descendre'); %b2=
b3 = trier(a, 'monter'); %b3=
pour matrices
UNE = ;
B1 = trier(A); %B1=
B2 = trier(A, 'descendre'); %B2=
Dans de nombreux problèmes pratiques, vous devez souvent trouver un élément spécifique dans un vecteur ou une matrice. Cela peut être fait en utilisant fonction standard find(), qui prend comme argument une condition selon laquelle les éléments recherchés sont trouvés, par exemple :
une = ;
b1 = trouver(a == 2); % b1 = 4 – indice de l'élément 2
b2 = trouver(a ~= 2); % b2 = – index sans 2
b3 = trouver (a > 3); % b3 =
Dans l'exemple donné, le symbole '==' signifie vérifier l'égalité, et le symbole '~=' vérifie l'inégalité des valeurs des éléments du vecteur a. Ces opérateurs seront décrits plus en détail dans la section Opérateurs conditionnels.
Une autre fonction utile pour travailler avec des vecteurs et des matrices est la fonction Mean() pour calculer la moyenne arithmétique, qui fonctionne comme suit :
une = ;
m = moyenne(a); % m = 3
UNE = ;
M1 = moyenne (A) ; % M1 =
M2 = moyenne (moyenne (A)); % M2 = 4,333
Chaque vecteur peut être considéré comme une matrice à une seule colonne ou à une seule ligne. Nous appellerons une matrice à une seule colonne un vecteur colonne et une matrice à une seule ligne un vecteur ligne.
Si A est une matrice de taille m*n, alors le vecteur colonne b a une taille n et le vecteur ligne b a une taille m.
Ainsi, pour multiplier une matrice par un vecteur, il faut considérer le vecteur comme un vecteur colonne. Lors de la multiplication d'un vecteur par une matrice, il doit être traité comme un vecteur ligne.
Matrice de multiplication
à un vecteur complexe
On obtient le résultat
Comme vous pouvez le voir, avec la dimension vectorielle inchangée, nous pouvons avoir deux solutions.
Je voudrais attirer votre attention sur le fait que les matrices des première et deuxième versions, malgré les mêmes valeurs, sont complètement différentes (ont des dimensions différentes)
Dans le premier cas, le vecteur est considéré comme une colonne et il faut alors multiplier la matrice par le vecteur, et dans le deuxième cas nous avons un vecteur ligne et alors nous avons produit d'un vecteur et d'une matrice.
Ce bot multiplie également les vecteurs et les matrices ayant des valeurs complexes. Basé sur une calculatrice plus complète : Multiplication matricielle à valeurs complexes en ligne
Propriétés de la multiplication matrice-vecteur
Matrice
Colonne de vecteur
Vecteur de ligne
Numéro arbitraire
1. Le produit d'une matrice par la somme des vecteurs colonnes est égal à la somme des produits de la matrice par chacun des vecteurs
2. Le produit de la somme des vecteurs lignes et de la matrice est égal à la somme des produits des vecteurs et de la matrice
3. Le facteur commun d'un vecteur peut être pris en dehors du produit d'une matrice par un vecteur/vecteur par une matrice
4. Le produit d'un vecteur ligne et le produit d'une matrice et d'un vecteur colonne est équivalent au produit du produit d'un vecteur ligne et d'une matrice et d'un vecteur colonne.
Définition 1Le produit matriciel (C = AB) est une opération uniquement pour les matrices appariées A et B, dans laquelle le nombre de colonnes de la matrice A est égal au nombre de lignes de la matrice B :
C ⏟ m × n = A ⏟ m × p × B ⏟ p × n
Exemple 1
Matrices données :
- A = a (i j) de dimensions m × n ;
- B = b (i j) de dimensions p × n
Matrice C dont les éléments c i j sont calculés selon la formule suivante :
c je j = une je 1 × b 1 j + une je 2 × b 2 j + . . . + une je p × b p j , je = 1 , . . . m, j = 1, . . . m
Exemple 2
Calculons les produits AB=BA :
UNE = 1 2 1 0 1 2 , B = 1 0 0 1 1 1
Solution utilisant la règle de multiplication matricielle :
A ⏟ 2 × 3 × B ⏟ 3 × 2 = 1 2 1 0 1 2 × 1 0 0 1 1 1 = 1 × 1 + 2 × 0 + 1 × 1 1 × 0 + 2 × 1 + 1 × 1 0 × 1 + 1 × 0 + 2 × 1 0 × 0 + 1 × 1 + 2 × 1 = = 2 3 2 3 ⏟ 2 × 2
B ⏟ 3 × 2 × A ⏟ 2 × 3 = 1 0 0 1 1 1 × 1 2 1 0 1 2 = 1 × 1 + 0 × 0 1 × 2 + 0 × 1 1 × 1 + 0 × 2 0 × 1 + 1 × 0 0 × 2 + 1 × 1 0 × 1 + 1 × 2 1 × 1 + 1 × 0 1 × 2 + 1 × 1 1 × 1 + 1 × 2 = 1 2 1 0 1 2 1 3 3 ⏟ 3×3
Les produits A B et B A sont trouvés, mais sont des matrices des tailles différentes: A B n'est pas égal à B A.
Propriétés de la multiplication matricielle
Propriétés de la multiplication matricielle :
- (A B) C = A (B C) - associativité de la multiplication matricielle ;
- A (B + C) = A B + A C - distributivité de la multiplication ;
- (A + B) C = A C + B C - distributivité de la multiplication ;
- λ (UNE B) = (λ UNE) B
Vérifions la propriété n°1 : (A B) C = A (B C) :
(A × B) × A = 1 2 3 4 × 5 6 7 8 × 1 0 0 2 = 19 22 43 50 × 1 0 0 2 = 19 44 43 100,
A (B × C) = 1 2 3 4 × 5 6 7 8 1 0 0 2 = 1 2 3 4 × 5 12 7 16 = 19 44 43 100.
Exemple 2
Vérifions la propriété n°2 : A (B + C) = A B + A C :
A × (B + C) = 1 2 3 4 × 5 6 7 8 + 1 0 0 2 = 1 2 3 4 × 6 6 7 10 = 20 26 46 58,
A B + A C = 1 2 3 4 × 5 6 7 8 + 1 2 3 4 × 1 0 0 2 = 19 22 43 50 + 1 4 3 8 = 20 26 46 58.
Produit de trois matrices
Le produit de trois matrices A B C se calcule de 2 manières :
- trouvez A B et multipliez par C : (A B) C ;
- ou trouvez d'abord B C, puis multipliez A (B C).
Multipliez les matrices de 2 manières :
4 3 7 5 × - 28 93 38 - 126 × 7 3 2 1
Algorithme d'actions :
- trouver le produit de 2 matrices ;
- puis trouvez à nouveau le produit de 2 matrices.
1). A B = 4 3 7 5 × - 28 93 38 - 126 = 4 (- 28) + 3 × 38 4 × 93 + 3 (- 126) 7 (- 28) + 5 × 38 7 × 93 + 5 (- 126 ) = 2 - 6 - 6 21
2). A B C = (A B) C = 2 - 6 - 6 21 7 3 2 1 = 2 × 7 - 6 × 2 2 × 3 - 6 × 1 - 6 × 7 + 21 × 2 - 6 × 3 + 21 × 1 = 2 0 0 3 .
On utilise la formule A B C = (A B) C :
1). B C = - 28 93 38 - 126 7 3 2 1 = - 28 × 7 + 93 × 2 - 28 × 3 + 93 × 1 38 × 7 - 126 × 2 38 × 3 - 126 × 1 = - 10 9 14 - 12
2). A B C = (A B) C = 7 3 2 1 - 10 9 14 - 12 = 4 (- 10) + 3 × 14 4 × 9 + 3 (- 12) 7 (- 10) + 5 × 14 7 × 9 + 5 (- 12) = 2 0 0 3
Réponse : 4 3 7 5 - 28 93 38 - 126 7 3 2 1 = 2 0 0 3
Multiplier une matrice par un nombre
Définition 2Le produit de la matrice A par le nombre k est la matrice B = A k de même taille, qui s'obtient à partir de celle d'origine en multipliant tous ses éléments par un nombre donné :
b je, j = k × a je, j
Propriétés de la multiplication d'une matrice par un nombre :
- 1 × UNE = UNE
- 0 × A = matrice nulle
- k (A + B) = k A + k B
- (k + n) A = k A + n A
- (k × n) × A = k (n × A)
Trouvons le produit de la matrice A = 4 2 9 0 par 5.
5 A = 5 4 2 9 0 5 × 4 5 × 2 5 × 9 5 × 0 = 20 10 45 0
Multiplier une matrice par un vecteur
Définition 3Pour trouver le produit d'une matrice et d'un vecteur, vous devez multiplier en utilisant la règle « ligne par colonne » :
- si vous multipliez une matrice par un vecteur colonne, le nombre de colonnes de la matrice doit correspondre au nombre de lignes du vecteur colonne ;
- Le résultat de la multiplication d’un vecteur colonne est simplement un vecteur colonne :
A B = a 11 a 12 ⋯ a 1 n a 21 a 22 ⋯ a 2 n ⋯ ⋯ ⋯ ⋯ a m 1 a m 2 ⋯ a m n b 1 b 2 ⋯ b 1 n = a 11 × b 1 + a 12 × b 2 + ⋯ + a 1 n × b n une 21 × b 1 + une 22 × b 2 + ⋯ + une 2 n × b n ⋯ ⋯ ⋯ ⋯ une m 1 × b 1 + une m 2 × b 2 + ⋯ + une m n × b n = c 1 s 2 ⋯ s 1 m
- si vous multipliez une matrice par un vecteur ligne, alors la matrice multipliée doit être exclusivement un vecteur colonne et le nombre de colonnes doit correspondre au nombre de colonnes dans le vecteur ligne :
A B = a a ⋯ a b b ⋯ b = a 1 × b 1 a 1 × b 2 ⋯ a 1 × b n a 2 × b 1 a 2 × b 2 ⋯ a 2 × b n ⋯ ⋯ ⋯ ⋯ a n × b 1 a n × b 2 ⋯ une n × b n = c 11 c 12 ⋯ c 1 n c 21 c 22 ⋯ c 2 n ⋯ ⋯ ⋯ ⋯ c n 1 c n 2 ⋯ c n n
Exemple 5
Trouvons le produit de la matrice A et du vecteur colonne B :
A B = 2 4 0 - 2 1 3 - 1 0 1 1 2 - 1 = 2 × 1 + 4 × 2 + 0 × (- 1) - 2 × 1 + 1 × 2 + 3 × (- 1) - 1 × 1 + 0 × 2 + 1 × (- 1) = 2 + 8 + 0 - 2 + 2 - 3 - 1 + 0 - 1 = 10 - 3 - 2
Exemple 6
Trouvons le produit de la matrice A et du vecteur ligne B :
A = 3 2 0 - 1 , B = - 1 1 0 2
A B = 3 2 0 1 × - 1 1 0 2 = 3 × (- 1) 3 × 1 3 × 0 3 × 2 2 × (- 1) 2 × 1 2 × 0 2 × 2 0 × (- 1) 0 × 1 0 × 0 0 × 2 1 × (- 1) 1 × 1 1 × 0 1 × 2 = - 3 3 0 6 - 2 2 0 4 0 0 0 0 - 1 1 0 2
Réponse : A B = - 3 3 0 6 - 2 2 0 4 0 0 0 0 - 1 1 0 2
Si vous remarquez une erreur dans le texte, veuillez la surligner et appuyer sur Ctrl+Entrée
