Regras para multiplicar uma matriz por um vetor. Multiplicação da matriz

12.09.202227.05.2017

No sistema MatLab é bastante simples realizar operações matemáticas em matrizes e vetores. Consideremos primeiro operações simples de adição e multiplicação de matrizes e vetores. Sejam dados dois vetores

uma =; % vetor linha
b = ; % vetor de coluna

então a multiplicação desses dois vetores pode ser escrita da seguinte forma

c = a*b; %c=1+2+3+4+5=16
d = b*a; % d – matriz de elementos 5x5

De acordo com as operações sobre vetores, multiplicar um vetor linha por um vetor coluna resulta em um número, e multiplicar um vetor coluna por um vetor linha fornece uma matriz bidimensional, que é o resultado dos cálculos no exemplo acima, ou seja,

A adição e subtração de dois vetores são escritas da seguinte forma:

a1 = ;
a2 = ;
c = a1+a2; % c = ;
c = a2-a1; % c = ;

Observe que as operações de adição e subtração podem ser realizadas entre dois vetores coluna ou dois vetores linha. Caso contrário, o MatLab exibirá uma mensagem de erro, porque Vetores de tipos diferentes não podem ser adicionados. Este é o caso de todas as operações aritméticas ilegais: se não puderem ser calculadas, o MatLab reportará um erro e o programa terminará na linha correspondente.

As operações de multiplicação e adição entre matrizes são realizadas de maneira semelhante:

UMA = ;
B = uns(3);
C=A+B; % adição de duas matrizes do mesmo tamanho
D = A+5; % adição de matriz e número
E = A*B; % multiplicação da matriz A por B
F = B*A; % multiplicação da matriz B por A
G = 5*A; % multiplicando uma matriz por um número

As operações de cálculo da matriz inversa, bem como de transposição de matrizes e vetores, são escritas da seguinte forma:

uma =; % vetor linha
b = uma’; % vetor coluna formado por
% transpondo o vetor linha a.
UMA = ; % Matriz de elemento 3x3
B = a*A; %B = – vetor linha
C = A*b; %C = – vetor coluna
D = a*A*a’; % D = 45 – número, soma dos elementos da matriz A
E = A'; % E – matriz transposta A
F = inv(A); % F – matriz inversa A
G = A^-1; % G – matriz inversa A

Do exemplo acima fica claro que a operação de transposição de matrizes e vetores é indicada pelo símbolo ‘ (apóstrofo), que é colocado após o nome do vetor ou matriz. O cálculo do inverso de uma matriz pode ser feito chamando a função inv() ou elevando a matriz à potência -1. O resultado em ambos os casos será o mesmo, e dois métodos de cálculo são feitos para facilitar o uso na implementação de algoritmos diferentes.

Se no processo de cálculo for necessário multiplicar, dividir ou elevar elementos de um vetor ou matriz elemento por elemento, então os seguintes operadores são utilizados para isso:

.* - multiplicação elemento a elemento;
./ e.\ - divisões elemento por elemento;
.^ - exponenciação elemento a elemento.

Vejamos como esses operadores funcionam usando o exemplo a seguir.

uma =; % vetor linha
b = ; % vetor linha
c = a.*b; %c=
A = uns(3); % Matriz 3x3 composta por unidades
B = ; % matriz 3x3
C = A.*B; % Matriz 3x3 consistindo em
D = A./B; % Matriz 3x3 consistindo em
E = A.\B; % Matriz 3x3 consistindo em
F = A.^2; % ao quadrado dos elementos da matriz A

Para concluir esta seção, consideraremos diversas funções úteis ao trabalhar com vetores e matrizes.

Para encontrar o valor máximo de um elemento vetorial, use a função padrão max(), que retorna o valor máximo encontrado do elemento e sua posição (índice):

uma =;
= máx(uma); % v = 6, i = 2;

v = máx(uma); % v = 6;

O exemplo acima mostra duas maneiras diferentes de chamar a função max(). No primeiro caso, são determinados tanto o valor máximo do elemento quanto seu índice no vetor, e no segundo - apenas o valor máximo do elemento.

No caso de matrizes, esta função determina os valores máximos existentes nas colunas, conforme exemplo abaixo:

UMA = ;
= máx(A); %V=,eu=
V = máx(A); %V=

A sintaxe completa da função max() pode ser encontrada digitando o comando na janela de comando do MatLab

ajuda<название функции>

A função min() funciona de forma semelhante, que determina o valor mínimo de um elemento de um vetor ou matriz e seu índice.

Outra função útil para trabalhar com matrizes e vetores é a função sum(), que calcula a soma dos valores dos elementos de um vetor ou colunas de matrizes:

uma =;
s = soma(uma); %s = 3+5+4+2+1=15
UMA = ;
S1 = soma(A); %S1=
S2 = soma(soma(A)); %S2=39

Ao calcular a soma S2, a soma dos valores dos elementos da matriz A é calculada primeiro em colunas e depois em linhas. Como resultado, a variável S2 contém a soma dos valores de todos os elementos da matriz A.

Para classificar os valores dos elementos de um vetor ou matriz em ordem crescente ou decrescente, use a função sort() da seguinte forma:

uma =;

b1 = classificar(a); %b1=
b2 = ordenar(a, ‘descer’); %b2=
b3 = ordenar(a, ‘ascender’); %b3=

para matrizes

UMA = ;
B1 = ordenar(A); %B1=
B2 = ordenar(A, 'descer'); %B2=

Em muitos problemas práticos, muitas vezes é necessário encontrar um elemento específico em um vetor ou matriz. Isso pode ser feito usando a função find() padrão, que toma como argumento uma condição segundo a qual os elementos necessários são encontrados, por exemplo:

uma =;
b1 = encontrar(a == 2); % b1 = 4 – índice do elemento 2
b2 = encontrar(a ~= 2); % b2 = – índices sem 2
b3 = encontrar(uma > 3); % b3 =

No exemplo dado, o símbolo ‘==’ significa verificação de igualdade, e o símbolo ‘~=’ verifica a desigualdade dos valores dos elementos do vetor a. Esses operadores serão descritos com mais detalhes na seção Operadores Condicionais.

Outra função útil para trabalhar com vetores e matrizes é a função mean() para calcular a média aritmética, que funciona da seguinte forma:

uma =;
m = média(a); % m = 3
UMA = ;
M1 = média(A); % M1 =
M2 = média(média(A)); % M2 = 4,333

Definição 1

Produto matricial (C = AB) é uma operação apenas para matrizes casadas A e B, em que o número de colunas da matriz A é igual ao número de linhas da matriz B:

C ⏟ m × n = A ⏟ m × p × B ⏟ p × n

Exemplo 1

Matrizes dadas:

A = a (i j) de dimensões m × n;
B = b (i j) de dimensões p × n

Matriz C, cujos elementos ci j são calculados usando a seguinte fórmula:

c i j = a i 1 × b 1 j + a i 2 × b 2 j + . . . + a i p × b p j , i = 1 , . . . m, j = 1, . . . eu

Exemplo 2

Vamos calcular os produtos AB=BA:

UMA = 1 2 1 0 1 2 , B = 1 0 0 1 1 1

Solução usando a regra de multiplicação de matrizes:

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

O produto A B e BA A são encontrados, mas são matrizes de tamanhos diferentes: A B não é igual a BA A.

Propriedades da multiplicação de matrizes

Propriedades da multiplicação de matrizes:

(A B) C = A (B C) - associatividade da multiplicação de matrizes;
A (B + C) = A B + A C - distributividade da multiplicação;
(A + B) C = A C + B C - distributividade da multiplicação;
λ (AB) = (λ A) B

Exemplo 1

Vamos verificar a propriedade 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.

Exemplo 2

Vamos verificar a propriedade 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.

Produto de três matrizes

O produto de três matrizes A B C é calculado de 2 maneiras:

encontre A B e multiplique por C: (A B) C;
ou primeiro encontre B C e depois multiplique A (B C).

Exemplo 3

Multiplique matrizes de 2 maneiras:

4 3 7 5 × - 28 93 38 - 126 × 7 3 2 1

Algoritmo de ações:

encontre o produto de 2 matrizes;
então encontre novamente o produto de 2 matrizes.

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 .

Usamos a fórmula 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

Resposta: 4 3 7 5 - 28 93 38 - 126 7 3 2 1 = 2 0 0 3

Multiplicando uma matriz por um número

Definição 2

O produto da matriz A pelo número k é a matriz B = A k do mesmo tamanho, que é obtida da original multiplicando todos os seus elementos por um determinado número:

b eu, j = k × a eu, j

Propriedades de multiplicar uma matriz por um número:

1 × UMA = UMA
0 × A = matriz zero
k (A + B) = k A + k B
(k + n) UMA = k UMA + n UMA
(k × n) × A = k (n × A)

Exemplo 4

Vamos encontrar o produto da matriz A = 4 2 9 0 por 5.

5 A = 5 4 2 9 0 5 × 4 5 × 2 5 × 9 5 × 0 = 20 10 45 0

Multiplicando uma matriz por um vetor

Definição 3

Para encontrar o produto de uma matriz e um vetor, você precisa multiplicar usando a regra “linha por coluna”:

se você multiplicar uma matriz por um vetor coluna, o número de colunas na matriz deve corresponder ao número de linhas no vetor coluna;
O resultado da multiplicação de um vetor coluna é apenas um vetor coluna:

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 a 21 × b 1 + a 22 × b 2 + ⋯ + a 2 n × b n ⋯ ⋯ ⋯ ⋯ a m 1 × b 1 + a m 2 × b 2 + ⋯ + a m n × b n = c 1 s 2 ⋯ s 1 metro

se você multiplicar uma matriz por um vetor linha, então a matriz que está sendo multiplicada deve ser exclusivamente um vetor coluna, e o número de colunas deve corresponder ao número de colunas no vetor linha:

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 ⋯ a 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

Exemplo 5

Vamos encontrar o produto da matriz A e do vetor coluna 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

Exemplo 6

Vamos encontrar o produto da matriz A e do vetor linha B:

UMA = 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

Resposta: A B = - 3 3 0 6 - 2 2 0 4 0 0 0 0 - 1 1 0 2

Se você notar um erro no texto, destaque-o e pressione Ctrl+Enter

Portanto, na lição anterior vimos as regras para adicionar e subtrair matrizes. Essas são operações tão simples que a maioria dos alunos as entende literalmente de cara.

No entanto, você se alegra cedo. O brinde acabou - vamos passar para a multiplicação. Já vou avisar: multiplicar duas matrizes não é de forma alguma multiplicar números em células com as mesmas coordenadas, como você pode imaginar. Tudo é muito mais divertido aqui. E teremos que começar com definições preliminares.

Matrizes correspondentes

Uma das características mais importantes de uma matriz é o seu tamanho. Já falamos sobre isso centenas de vezes: escrever $A=\left[ m\times n \right]$ significa que a matriz tem exatamente $m$ linhas e $n$ colunas. Também já discutimos como não confundir linhas com colunas. Outra coisa é importante agora.

Definição. Matrizes da forma $A=\left[ m\times n \right]$ e $B=\left[ n\times k \right]$, nas quais o número de colunas na primeira matriz coincide com o número de linhas no segundo, são chamados de consistentes.

Mais uma vez: o número de colunas da primeira matriz é igual ao número de linhas da segunda! A partir daqui, tiramos duas conclusões ao mesmo tempo:

A ordem das matrizes é importante para nós. Por exemplo, as matrizes $A=\left[ 3\times 2 \right]$ e $B=\left[ 2\times 5 \right]$ são consistentes (2 colunas na primeira matriz e 2 linhas na segunda) , mas vice-versa - as matrizes $B=\left[ 2\times 5 \right]$ e $A=\left[ 3\times 2 \right]$ não são mais consistentes (5 colunas na primeira matriz não são 3 linhas no segundo ).
A consistência pode ser facilmente verificada anotando todas as dimensões, uma após a outra. Usando o exemplo do parágrafo anterior: “3 2 2 5” - existem números idênticos no meio, então as matrizes são consistentes. Mas “2 5 3 2” não são consistentes, pois existem números diferentes no meio.

Além disso, o Capitão Obviedade parece estar sugerindo que matrizes quadradas do mesmo tamanho $\left[ n\times n \right]$ são sempre consistentes.

Em matemática, quando a ordem da listagem dos objetos é importante (por exemplo, na definição discutida acima, a ordem das matrizes é importante), frequentemente falamos sobre pares ordenados. Nós os conhecemos na escola: acho que é óbvio que as coordenadas $\left(1;0 \right)$ e $\left(0;1 \right)$ definem pontos diferentes no plano.

Então: as coordenadas também são pares ordenados compostos de números. Mas nada impede que você faça esse par a partir de matrizes. Então podemos dizer: “Um par ordenado de matrizes $\left(A;B \right)$ é consistente se o número de colunas na primeira matriz for igual ao número de linhas na segunda.”

Bem, e daí?

Definição de multiplicação

Considere duas matrizes consistentes: $A=\left[ m\times n \right]$ e $B=\left[ n\times k \right]$. E definimos a operação de multiplicação para eles.

Definição. O produto de duas matrizes correspondentes $A=\left[ m\times n \right]$ e $B=\left[ n\times k \right]$ é a nova matriz $C=\left[ m\times k \ direita] $, cujos elementos são calculados usando a fórmula:

\[\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))= \\ & =\soma\limites_(t=1)^(n)(((a)_(i;t))\cdot ((b)_(t;j))) \end(align)\]

Tal produto é denotado da maneira padrão: $C=A\cdot B$.

Quem vê esta definição pela primeira vez tem imediatamente duas perguntas:

Que tipo de jogo feroz é esse?
Por que é tão difícil?

Bem, primeiro as primeiras coisas. Vamos começar com a primeira pergunta. O que todos esses índices significam? E como não cometer erros ao trabalhar com matrizes reais?

Em primeiro lugar, notamos que a longa fila para calcular $((c)_(i;j))$ (coloquei especialmente um ponto e vírgula entre os índices para não ficar confuso, mas não há necessidade de colocá-los geral - eu mesmo cansei de digitar a fórmula na definição) na verdade se resume a uma regra simples:

Pegue a $i$ésima linha da primeira matriz;
Pegue a $j$ésima coluna na segunda matriz;
Obtemos duas sequências de números. Multiplicamos os elementos dessas sequências pelos mesmos números e depois somamos os produtos resultantes.

Este processo é fácil de entender pela imagem:

Esquema para multiplicar duas matrizes

Mais uma vez: fixamos a linha $i$ na primeira matriz, a coluna $j$ na segunda matriz, multiplicamos os elementos pelos mesmos números e depois somamos os produtos resultantes - obtemos $((c)_(ij))$ . E assim por diante para todos $1\le i\le m$ e $1\le j\le k$. Aqueles. Haverá $m\times k$ de tais “perversões” no total.

Na verdade, já encontramos a multiplicação de matrizes no currículo escolar, apenas de forma bastante reduzida. Sejam dados os vetores:

\[\begin(align) & \vec(a)=\left(((x)_(a));((y)_(a));((z)_(a)) \right); \\ & \overrightarrow(b)=\esquerda(((x)_(b));((y)_(b));((z)_(b)) \direita). \\ \fim(alinhar)\]

Então seu produto escalar será exatamente a soma dos produtos aos pares:

\[\overrightarrow(a)\times \overrightarrow(b)=((x)_(a))\cdot ((x)_(b))+((y)_(a))\cdot ((y )_(b))+((z)_(a))\cdot ((z)_(b))\]

Basicamente, quando as árvores eram mais verdes e os céus mais claros, simplesmente multiplicamos o vetor linha $\overrightarrow(a)$ pelo vetor coluna $\overrightarrow(b)$.

Nada mudou hoje. Acontece que agora existem mais destes vetores de linha e coluna.

Mas chega de teoria! Vejamos exemplos reais. E vamos começar com o caso mais simples - matrizes quadradas.

Multiplicação de matriz quadrada

Tarefa 1. Faça a multiplicação:

\[\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]\]

Solução. Portanto, temos duas matrizes: $A=\left[ 2\times 2 \right]$ e $B=\left[ 2\times 2 \right]$. É claro que são consistentes (matrizes quadradas do mesmo tamanho são sempre consistentes). Portanto, realizamos a multiplicação:

\[\begin(align) & \left[ \begin(array)(*(35)(r)) 1 & 2 \\ -3 & 4 \\\end(array) \right]\cdot \left[ \ começar(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 \\\ fim(matriz)\direita]. \fim(alinhar)\]

Isso é tudo!

Resposta: $\left[ \begin(array)(*(35)(r))4 & 6 \\ 18 & -8 \\\end(array) \right]$.

Tarefa 2. Faça a multiplicação:

\[\left[ \begin(matriz) 1 & 3 \\ 2 & 6 \\\end(matriz) \right]\cdot \left[ \begin(array)(*(35)(r))9 & 6 \\ -3 e -2 \\\end(array) \right]\]

Solução. Novamente, matrizes consistentes, então realizamos as seguintes ações:\[\]

\[\begin(align) & \left[ \begin(matrix) 1 & 3 \\ 2 & 6 \\\end(matrix) \right]\cdot \left[ \begin(array)(*(35)( ) r)) 9 e 6 \\ -3 & -2 \\\end(array) \right]=\left[ \begin(array)(*(35)(r)) 1\cdot 9+3\cdot \ left(-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(matrix) \right ] . \fim(alinhar)\]

Como você pode ver, o resultado é uma matriz preenchida com zeros

Resposta: $\left[ \begin(matrix) 0 & 0 \\ 0 & 0 \\\end(matrix) \right]$.

A partir dos exemplos acima, é óbvio que a multiplicação de matrizes não é uma operação tão complicada. Pelo menos para matrizes quadradas 2 por 2.

No processo de cálculos, compilamos uma matriz intermediária, onde descrevemos diretamente quais números estão incluídos em uma determinada célula. Isso é exatamente o que deve ser feito na resolução de problemas reais.

Propriedades básicas do produto da matriz

Em poucas palavras. Multiplicação da matriz:

Não comutativo: $A\cdot B\ne B\cdot A$ no caso geral. Existem, é claro, matrizes especiais para as quais a igualdade $A\cdot B=B\cdot A$ (por exemplo, se $B=E$ é a matriz identidade), mas na grande maioria dos casos isso não funciona ;
Associativamente: $\left(A\cdot B \right)\cdot C=A\cdot \left(B\cdot C \right)$. Não há opções aqui: matrizes adjacentes podem ser multiplicadas sem se preocupar com o que está à esquerda e à direita dessas duas matrizes.
Distributivamente: $A\cdot \left(B+C \right)=A\cdot B+A\cdot C$ e $\left(A+B \right)\cdot C=A\cdot C+B\cdot C $ (devido à não comutatividade do produto, é necessário especificar separadamente a distributividade direita e esquerda.

E agora - tudo é igual, mas com mais detalhes.

A multiplicação de matrizes é em muitos aspectos semelhante à multiplicação clássica de números. Mas existem diferenças, a mais importante das quais é que A multiplicação de matrizes é, em geral, não comutativa.

Vejamos novamente as matrizes do Problema 1. Já conhecemos seu produto direto:

\[\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(array) \right]\]

Mas se trocarmos as matrizes, obteremos um resultado completamente diferente:

\[\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(matriz) -14 & 4 \\ 0 & 10 \\\end(matriz )\certo]\]

Acontece que $A\cdot B\ne B\cdot A$. Além disso, a operação de multiplicação só é definida para as matrizes consistentes $A=\left[ m\times n \right]$ e $B=\left[ n\times k \right]$, mas ninguém garantiu que elas permanecerão consistentes se forem trocados. Por exemplo, as matrizes $\left[ 2\times 3 \right]$ e $\left[ 3\times 5 \right]$ são bastante consistentes na ordem especificada, mas as mesmas matrizes $\left[ 3\times 5 \right] $ e $\left[ 2\times 3 \right]$ escritos em ordem inversa não são mais consistentes. Triste.:(

Entre matrizes quadradas de um determinado tamanho $n$ sempre haverá aquelas que dão o mesmo resultado tanto quando multiplicadas em ordem direta quanto em ordem inversa. Como descrever todas essas matrizes (e quantas existem em geral) é um tópico para uma lição separada. Não falaremos sobre isso hoje. :)

No entanto, a multiplicação de matrizes é associativa:

\[\left(A\cdot B \right)\cdot C=A\cdot \left(B\cdot C \right)\]

Portanto, quando você precisa multiplicar várias matrizes seguidas ao mesmo tempo, não é necessário fazê-lo imediatamente: é bem possível que algumas matrizes adjacentes, quando multiplicadas, dêem um resultado interessante. Por exemplo, uma matriz zero, como no Problema 2 discutido acima.

Em problemas reais, na maioria das vezes temos que multiplicar matrizes quadradas de tamanho $\left[ n\times n \right]$. O conjunto de todas essas matrizes é denotado por $((M)^(n))$ (ou seja, as entradas $A=\left[ n\times n \right]$ e \ significam a mesma coisa), e será necessariamente contém a matriz $E$, que é chamada de matriz identidade.

Definição. Uma matriz identidade de tamanho $n$ é uma matriz $E$ tal que para qualquer matriz quadrada $A=\left[ n\times n \right]$ a igualdade é válida:

Essa matriz sempre parece a mesma: há unidades em sua diagonal principal e zeros em todas as outras células.

\[\begin(align) & A\cdot \left(B+C \right)=A\cdot B+A\cdot C; \\ & \esquerda(A+B \direita)\cdot C=A\cdot C+B\cdot C. \\ \end(align)\]

Em outras palavras, se você precisar multiplicar uma matriz pela soma de outras duas, poderá multiplicá-la por cada uma dessas “outras duas” e depois somar os resultados. Na prática, normalmente temos que realizar a operação oposta: notamos a mesma matriz, tiramos-na dos colchetes, realizamos a adição e assim simplificamos nossa vida. :)

Nota: para descrever a distributividade, tivemos que escrever duas fórmulas: onde a soma está no segundo fator e onde a soma está no primeiro. Isso acontece justamente porque a multiplicação de matrizes é não comutativa (e, em geral, na álgebra não comutativa há muitas coisas divertidas que nem vêm à mente quando se trabalha com números comuns). E se, por exemplo, você precisar anotar essa propriedade em um exame, certifique-se de escrever as duas fórmulas, caso contrário o professor pode ficar um pouco irritado.

Ok, todos esses eram contos de fadas sobre matrizes quadradas. E os retangulares?

O caso de matrizes retangulares

Mas nada - tudo é igual aos quadrados.

Tarefa 3. Faça a multiplicação:

\[\left[ \begin(matriz) \begin(matriz) 5 \\ 2 \\ 3 \\\end(matriz) & \begin(matriz) 4 \\ 5 \\ 1 \\\end(matriz) \ \\end(matriz) \right]\cdot \left[ \begin(array)(*(35)(r)) -2 & 5 \\ 3 & 4 \\\end(array) \right]\]

Solução. Temos duas matrizes: $A=\left[ 3\times 2 \right]$ e $B=\left[ 2\times 2 \right]$. Vamos anotar os números que indicam os tamanhos consecutivos:

Como você pode ver, os dois números centrais coincidem. Isso significa que as matrizes são consistentes e podem ser multiplicadas. Além disso, na saída obtemos a matriz $C=\left[ 3\times 2 \right]$:

\[\begin(align) & \left[ \begin(matrix) \begin(matrix) 5 \\ 2 \\ 3 \\\end(matrix) & \begin(matrix) 4 \\ 5 \\ 1 \\ \end(matriz) \\\end(matriz) \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 \ \\fim(matriz) \direita]. \fim(alinhar)\]

Tudo está claro: a matriz final possui 3 linhas e 2 colunas. Bastante $=\left[ 3\times 2 \right]$.

Resposta: $\left[ \begin(array)(*(35)(r)) \begin(array)(*(35)(r)) 2 \\ 11 \\ -3 \\\end(array) & \begin(matriz) 41 \\ 30 \\ 19 \\\end(matriz) \\\end(array) \right]$.

Agora vejamos uma das melhores tarefas de treinamento para quem está começando a trabalhar com matrizes. Nele você não precisa apenas multiplicar duas tabuinhas, mas primeiro determinar: tal multiplicação é permitida?

Problema 4. Encontre todos os produtos pares possíveis de matrizes:

\\]; $B=\left[ \begin(matriz) \begin(matriz) 0 \\ 2 \\ 0 \\ 4 \\\end(matriz) & \begin(matriz) 1 \\ 0 \\ 3 \\ 0 \ \\end(matriz) \\\end(matriz) \right]$; $C=\left[ \begin(matriz)0 & 1 \\ 1 & 0 \\\end(matriz) \right]$.

Solução. Primeiro, vamos anotar os tamanhos das matrizes:

\;\ B=\esquerda[ 4\vezes 2 \direita];\ C=\esquerda[ 2\vezes 2 \direita]\]

Descobrimos que a matriz $A$ só pode ser reconciliada com a matriz $B$, pois o número de colunas de $A$ é 4, e apenas $B$ possui esse número de linhas. Portanto, podemos encontrar o produto:

\\cdot \left[ \begin(array)(*(35)(r)) 0 & 1 \\ 2 & 0 \\ 0 & 3 \\ 4 & 0 \\\end(array) \right]=\ esquerda[ \begin(array)(*(35)(r))-10 & 7 \\ 10 & 7 \\\end(array) \right]\]

Sugiro que o leitor complete as etapas intermediárias de forma independente. Observo apenas que é melhor determinar antecipadamente o tamanho da matriz resultante, antes mesmo de qualquer cálculo:

\\cdot \left[ 4\times 2 \right]=\left[ 2\times 2 \right]\]

Em outras palavras, simplesmente removemos os coeficientes de “trânsito” que garantiam a consistência das matrizes.

Que outras opções são possíveis? Claro, pode-se encontrar $B\cdot A$, já que $B=\left[ 4\times 2 \right]$, $A=\left[ 2\times 4 \right]$, então o par ordenado $\ left(B ;A \right)$ é consistente e a dimensão do produto será:

\\cdot \left[ 2\times 4 \right]=\left[ 4\times 4 \right]\]

Resumindo, a saída será uma matriz $\left[ 4\times 4 \right]$, cujos coeficientes podem ser facilmente calculados:

\\cdot \left[ \begin(array)(*(35)(r)) 1 & -1 & 2 & -2 \\ 1 & 1 & 2 & 2 \\\end(array) \right]=\ esquerda[\begin(array)(*(35)(r))1 & 1 & 2 & 2 \\ 2 & -2 & 4 & -4 \\ 3 & 3 & 6 & 6 \\ 4 & -4 & 8 e -8 \\\end(array) \right]\]

Obviamente, você também pode concordar com $C\cdot A$ e $B\cdot C$ - e é isso. Portanto, simplesmente anotamos os produtos resultantes:

Foi fácil.:)

Resposta: $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(array) \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]$.

Em geral, eu recomendo fortemente que você mesmo faça essa tarefa. E mais uma tarefa semelhante que está na lição de casa. Esses pensamentos aparentemente simples o ajudarão a praticar todos os estágios principais da multiplicação de matrizes.

Mas a história não termina aí. Vamos passar para casos especiais de multiplicação. :)

Vetores de linha e vetores de coluna

Uma das operações matriciais mais comuns é a multiplicação por uma matriz que possui uma linha ou uma coluna.

Definição. Um vetor coluna é uma matriz de tamanho $\left[ m\times 1 \right]$, ou seja, consistindo em várias linhas e apenas uma coluna.

Um vetor linha é uma matriz de tamanho $\left[ 1\times n \right]$, ou seja, consistindo em uma linha e várias colunas.

Na verdade, já encontramos esses objetos. Por exemplo, um vetor tridimensional comum da estereometria $\overrightarrow(a)=\left(x;y;z \right)$ nada mais é do que um vetor linha. Do ponto de vista teórico, quase não há diferença entre linhas e colunas. Você só precisa ter cuidado ao coordenar com as matrizes multiplicadoras vizinhas.

Tarefa 5. Faça a multiplicação:

\[\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]\]

Solução. Aqui temos o produto de matrizes correspondentes: $\left[ 3\times 3 \right]\cdot \left[ 3\times 1 \right]=\left[ 3\times 1 \right]$. Vamos encontrar esta peça:

\[\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(array) \right]\]

Resposta: $\left[ \begin(array)(*(35)(r))-3 \\ 8 \\ 0 \\\end(array) \right]$.

Tarefa 6. Faça a multiplicação:

\[\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]\]

Solução. Novamente está tudo combinado: $\left[ 1\times 3 \right]\cdot \left[ 3\times 3 \right]=\left[ 1\times 3 \right]$. Contamos o produto:

\[\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]\]

Resposta: $\left[ \begin(matrix) 5 & -19 & 5 \\\end(matrix) \right]$.

Como você pode ver, quando multiplicamos um vetor linha e um vetor coluna por uma matriz quadrada, a saída sempre resulta em uma linha ou coluna do mesmo tamanho. Esse fato tem muitas aplicações - desde a resolução de equações lineares até todos os tipos de transformações de coordenadas (que, em última análise, também se resumem a sistemas de equações, mas não vamos falar de coisas tristes).

Acho que tudo era óbvio aqui. Vamos passar para a parte final da lição de hoje.

Exponenciação matricial

Dentre todas as operações de multiplicação, a exponenciação merece atenção especial - é quando multiplicamos várias vezes o mesmo objeto por ele mesmo. As matrizes não são exceção; elas também podem ser elevadas a vários poderes.

Tais trabalhos são sempre acordados:

\\cdot \left[ n\times n \right]=\left[ n\times n \right]\]

E eles são designados exatamente da mesma forma que os graus comuns:

\[\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)). \\ \fim(alinhar)\]

À primeira vista, tudo é simples. Vamos ver como isso fica na prática:

Tarefa 7. Eleve a matriz à potência indicada:

$((\left[ \begin(matriz) 1 & 1 \\ 0 & 1 \\\end(matriz) \right])^(3))$

Solução. Bem, ok, vamos construir. Primeiro vamos enquadrar:

\[\begin(align) & ((\left[ \begin(matrix) 1 & 1 \\ 0 & 1 \\\end(matrix) \right])^(2))=\left[ \begin(matrix ) 1 & 1 \\ 0 & 1 \\\end(matriz) \right]\cdot \left[ \begin(matriz) 1 & 1 \\ 0 & 1 \\\end(matriz) \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(array) \right] \end(align)\]

\[\begin(align) & ((\left[ \begin(matrix) 1 & 1 \\ 0 & 1 \\\end(matrix) \right])^(3))=((\left[ \begin (matriz) 1 & 1 \\ 0 & 1 \\\end(matriz) \right])^(3))\cdot \left[ \begin(matriz) 1 & 1 \\ 0 & 1 \\\end( matriz) \right]= \\ & =\left[ \begin(array)(*(35)(r)) 1 & 2 \\ 0 & 1 \\\end(array) \right]\cdot \left[ \begin(matriz) 1 & 1 \\ 0 & 1 \\\end(matriz) \right]= \\ & =\left[ \begin(array)(*(35)(r)) 1 & 3 \\ 0 e 1 \\\end(array) \right] \end(align)\]

Isso é tudo.:)

Resposta: $\left[ \begin(matrix)1 & 3 \\ 0 & 1 \\\end(matrix) \right]$.

Problema 8. Eleve a matriz à potência indicada:

\[((\left[ \begin(matriz) 1 & 1 \\ 0 & 1 \\\end(matriz) \right])^(10))\]

Solução. Só não chore agora pelo fato de que “o diploma é muito grande”, “o mundo não é justo” e “os professores perderam completamente o controle”. Na verdade é fácil:

\[\begin(align) & ((\left[ \begin(matrix) 1 & 1 \\ 0 & 1 \\\end(matrix) \right])^(10))=((\left[ \begin (matriz) 1 & 1 \\ 0 & 1 \\\end(matriz) \right])^(3))\cdot ((\left[ \begin(matriz) 1 & 1 \\ 0 & 1 \\\ end(matriz) \right])^(3))\cdot ((\left[ \begin(matrix) 1 & 1 \\ 0 & 1 \\\end(matrix) \right])^(3))\ cdot \left[ \begin(matriz) 1 & 1 \\ 0 & 1 \\\end(matriz) \right]= \\ & =\left(\left[ \begin(matriz) 1 & 3 \\ 0 & 1 \\\end(matriz) \right]\cdot \left[ \begin(matrix) 1 & 3 \\ 0 & 1 \\\end(matrix) \right] \right)\cdot \left(\left[ \begin(matriz) 1 & 3 \\ 0 & 1 \\\end(matriz) \right]\cdot \left[ \begin(matriz) 1 & 1 \\ 0 & 1 \\\end(matriz) \right ] \right)= \\ & =\left[ \begin(matrix) 1 & 6 \\ 0 & 1 \\\end(matrix) \right]\cdot \left[ \begin(matrix) 1 & 4 \\ 0 & 1 \\\end(matriz) \right]= \\ & =\left[ \begin(matrix) 1 & 10 \\ 0 & 1 \\\end(matrix) \right] \end(align)\ ]

Observe que na segunda linha usamos associatividade de multiplicação. Na verdade, usamos isso na tarefa anterior, mas estava implícito ali.

Resposta: $\left[ \begin(matrix) 1 & 10 \\ 0 & 1 \\\end(matrix) \right]$.

Como você pode ver, não há nada complicado em elevar uma matriz a uma potência. O último exemplo pode ser resumido:

\[((\left[ \begin(matriz) 1 & 1 \\ 0 & 1 \\\end(matriz) \right])^(n))=\left[ \begin(array)(*(35) (r)) 1 & n \\ 0 & 1 \\\end(array) \right]\]

Este fato é fácil de provar através de indução matemática ou multiplicação direta. No entanto, nem sempre é possível detectar tais padrões ao elevar a uma potência. Portanto, tenha cuidado: muitas vezes multiplicar várias matrizes “ao acaso” acaba sendo mais fácil e rápido do que procurar algum tipo de padrão.

Em geral, não procure um significado superior onde não existe. Concluindo, vamos considerar a exponenciação de uma matriz maior - tanto quanto $\left[ 3\times 3 \right]$.

Problema 9. Eleve a matriz à potência indicada:

\[((\esquerda[ \begin(matriz) 0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \\\end(matriz) \direita])^(3))\]

Solução. Não vamos procurar padrões. Trabalhamos à frente:

\[((\esquerda[ \begin(matriz) 0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \\\end(matriz) \direita])^(3))=(( \left[ \begin(matriz) 0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \\\end(matriz) \right])^(2))\cdot \left[ \begin (matriz)0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \\\end(matriz) \right]\]

Primeiro, vamos elevar esta matriz ao quadrado:

\[\begin(align) & ((\left[ \begin(matrix) 0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \\\end(matrix) \right])^( 2))=\left[ \begin(matriz) 0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \\\end(matriz) \right]\cdot \left[ \begin(matriz) ) 0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \\\end(matriz) \right]= \\ & =\left[ \begin(array)(*(35)(r )) 2 & 1 & 1 \\ 1 & 2 & 1 \\ 1 & 1 & 2 \\\end(array) \right] \end(align)\]

Agora vamos cubá-lo:

\[\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(matriz) 0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \\\end(matriz) \right]= \\ & =\left[ \begin( matriz)(*(35)(r)) 2 e 3 e 3 \\ 3 e 2 e 3 \\ 3 e 3 e 2 \\\end(array) \right] \end(align)\]

Isso é tudo. O problema está resolvido.

Resposta: $\left[ \begin(matrix) 2 & 3 & 3 \\ 3 & 2 & 3 \\ 3 & 3 & 2 \\\end(matrix) \right]$.

Como você pode ver, o volume de cálculos aumentou, mas o significado não mudou em nada. :)

Isso conclui a lição. Da próxima vez consideraremos a operação inversa: utilizando o produto existente procuraremos os fatores originais.

Como você provavelmente já adivinhou, falaremos sobre a matriz inversa e os métodos para encontrá-la.

Cada vetor pode ser considerado uma matriz de coluna única ou de linha única. Chamaremos uma matriz de coluna única de vetor coluna e uma matriz de linha única de vetor linha.

Se A é uma matriz de tamanho m*n, então o vetor coluna b tem tamanho n e o vetor linha b tem tamanho m.

Assim, para multiplicar uma matriz por um vetor, devemos considerar o vetor como um vetor coluna. Ao multiplicar um vetor por uma matriz, ele deve ser tratado como um vetor linha.

Multiplicar matriz

para um vetor complexo

Obtemos o resultado

Como você pode ver, com a dimensão vetorial inalterada, podemos ter duas soluções.

Gostaria de chamar a atenção para o fato de que a matriz da primeira e da segunda versões, apesar dos mesmos valores, são completamente diferentes (possuem dimensões diferentes)

No primeiro caso o vetor é considerado uma coluna e então é necessário multiplicar matriz por vetor, e no segundo caso temos um vetor linha e então temos produto de um vetor e uma matriz.

Este bot também multiplica vetores e matrizes que possuem valores complexos. Baseado em uma calculadora mais completa: Multiplicação de matrizes com valores complexos online

Propriedades da multiplicação de matrizes e vetores

Matriz

Coluna vetorial

Vetor de linha

Número arbitrário

1. O produto de uma matriz pela soma dos vetores coluna é igual à soma dos produtos da matriz por cada um dos vetores

2. O produto da soma dos vetores linha e da matriz é igual à soma dos produtos dos vetores e da matriz

3. O fator comum de um vetor pode ser retirado do produto de uma matriz por um vetor/vetor por uma matriz

4. O produto de um vetor linha e o produto de uma matriz e um vetor coluna é equivalente ao produto do produto de um vetor linha e uma matriz e um vetor coluna.

Aula 6. Algoritmos numéricos paralelos para resolução de problemas típicos de matemática computacional: multiplicação de matrizes.

Multiplicando uma matriz por um vetor. Alcançando o melhor desempenho possível. Explorando o paralelismo de nível médio. Organização da computação paralela em p = n. Uso de um conjunto limitado de processadores. Multiplicação da matriz. Análise macro-operacional de algoritmos de resolução de problemas. Organização do paralelismo baseada no compartilhamento de dados.

Multiplicando uma matriz por um vetor

O problema de multiplicar uma matriz por um vetor é definido pelas relações

Assim, a obtenção do vetor resultante envolve a repetição de operações semelhantes de multiplicação das linhas da matriz e do vetor. A obtenção de cada uma dessas operações envolve a multiplicação elemento a elemento dos elementos de uma linha de uma matriz e de um vetor e a subsequente soma dos produtos resultantes. O número total de operações escalares necessárias é estimado pela quantidade

Como decorre das ações realizadas ao multiplicar uma matriz e um vetor, métodos paralelos para resolver o problema podem ser obtidos com base em algoritmos de soma paralela (ver parágrafo 4.1). Nesta seção, a análise dos métodos de paralelização será complementada pela consideração de questões de organização da computação paralela dependendo do número de processadores disponíveis para uso. Além disso, usando o exemplo do problema de multiplicação de uma matriz por um vetor, chamar-se-á a atenção para a necessidade de selecionar a topologia mais adequada do sistema computacional (canais de comunicação existentes entre processadores) para reduzir custos de organização da interação interprocessador.

Alcançando o melhor desempenho possível ()

Vamos analisar as dependências de informações no algoritmo de multiplicação de matrizes e vetores para selecionar possíveis métodos de paralelização. Como você pode ver, as operações de multiplicação de linhas individuais de uma matriz por um vetor realizadas durante os cálculos são independentes e podem ser realizadas em paralelo;

Multiplicar cada linha por um vetor envolve operações independentes de multiplicação elemento a elemento e também pode ser realizada em paralelo;

A soma dos produtos resultantes em cada operação de multiplicação de uma linha da matriz por um vetor pode ser realizada usando uma das variantes do algoritmo de soma anteriormente consideradas (algoritmo sequencial, esquemas em cascata convencionais e modificados).

Assim, o número máximo necessário de processadores é determinado pelo valor

O uso de tal número de processadores pode ser representado da seguinte forma. Muitos processadores são divididos em grupos

cada um dos quais representa um conjunto de processadores para realizar a operação de multiplicação de uma linha individual de uma matriz por um vetor. No início dos cálculos, um elemento de linha da matriz e um elemento de vetor correspondente são enviados para cada processador do grupo. A seguir, cada processador realiza uma operação de multiplicação. Os cálculos subsequentes são então realizados usando um esquema de soma em cascata. Para ilustração na Fig. 6.1 mostra o esquema computacional para os processadores de um grupo com dimensão matricial de .

Arroz. 6.1. Esquema computacional para a operação de multiplicação de uma linha de matriz por um vetor

O tempo de execução de um algoritmo paralelo ao usar processadores é determinado pelo tempo de execução da operação de multiplicação paralela e pelo tempo de execução do circuito em cascata

Como resultado, os indicadores de eficiência do algoritmo são determinados pelas seguintes relações:

Para o problema de multiplicação de vetores de matrizes em consideração, as topologias mais adequadas são estruturas que fornecem transmissão rápida de dados (caminhos de comprimento unitário) em um circuito somatório em cascata (ver Fig. 4.5). Tais topologias são uma estrutura com um sistema completo de conexões ( gráfico completo) E hipercubo. Outras topologias levam ao aumento do tempo de comunicação devido a rotas de transferência de dados mais longas. Assim, com uma ordenação linear de processadores com um sistema de conexões apenas com os vizinhos mais próximos à esquerda e à direita ( governante ou anel) para um esquema em cascata, o comprimento do caminho de transmissão de cada soma parcial recebida na iteração, é igual a. Se assumirmos que a transmissão de dados ao longo de um caminho em topologias com estrutura linear requer operações de transmissão de dados, o número total de operações paralelas (duração total dos caminhos) de transmissão de dados é determinado pelo valor

(excluindo transferências de dados para carregamento inicial de processadores).

Aplicação de um sistema computacional com topologia retangular rede bidimensional o tamanho leva a uma interpretação simples e clara dos cálculos realizados (a estrutura da rede corresponde à estrutura dos dados processados). Para tal topologia, é mais aconselhável colocar as linhas da matriz ao longo das grades horizontais; neste caso, os elementos do vetor devem ser distribuídos ao longo das verticais do sistema computacional. Os cálculos com esta disposição de dados podem ser realizados em paralelo ao longo das linhas da grade; como resultado, o número total de transferências de dados corresponde aos resultados da régua().

As ações de comunicação realizadas na resolução de uma determinada tarefa consistem na transferência de dados entre pares de processadores MCS. Uma análise detalhada da duração da implementação de tais operações é realizada no parágrafo 3.3.

4. Recomendações para implementação de um algoritmo paralelo. Ao implementar um algoritmo paralelo, é aconselhável destacar a etapa inicial de carregamento dos processadores utilizados com os dados iniciais. Mais simplesmente, tal inicialização é fornecida com uma topologia de um sistema de computador com uma topologia na forma gráfico completo(o download é fornecido usando uma operação paralela de transferência de dados). Ao organizar vários processadores no formato hipercubo Pode ser útil ter controle de dois níveis do processo de bootstrap, no qual o processador de controle central garante que as linhas da matriz e do vetor sejam enviadas aos processadores de controle dos grupos de processadores, que, por sua vez, enviam os elementos da matriz e linhas vetoriais para os processadores executivos. Para topologias na forma governantes ou argolas requer operações sequenciais de transferência de dados com uma quantidade sucessivamente decrescente de dados transferidos de para elementos.

Usando paralelismo de nível médio()

1. Escolhendo um método de computação paralela. Quando o número disponível de processadores usados () diminui, o esquema usual de soma em cascata ao realizar operações de multiplicação de linhas de matriz por vetor torna-se inaplicável. Para simplificar a apresentação do material, vamos assumir e utilizar um esquema em cascata modificado. A carga inicial de cada processador neste caso aumenta e o processador é carregado () por partes das linhas da matriz e do vetor. O tempo de execução da operação de multiplicação de uma matriz por um vetor pode ser estimado como

Ao usar o número de processadores necessários para implementar o esquema em cascata modificado, ou seja, no , esta expressão fornece uma estimativa do tempo de execução (no ).

Quando o número de processadores é , quando o tempo de execução do algoritmo é estimado como , um novo esquema para execução paralela de cálculos pode ser proposto, no qual para cada iteração de somatório em cascata, conjuntos de processadores não sobrepostos. Com esta abordagem, o número disponível de processadores acaba sendo suficiente para implementar apenas uma operação de multiplicação de uma linha de matriz e de um vetor. Além disso, ao realizar a próxima iteração do somatório em cascata, os processadores responsáveis pela execução de todas as iterações anteriores ficam livres. No entanto, esta desvantagem da abordagem proposta pode ser transformada em uma vantagem ao utilizar processadores ociosos para processar as próximas linhas da matriz. Como resultado, o seguinte esquema pode ser formado transportador realizando multiplicação de matrizes e vetores:

Um conjunto de processadores é dividido em grupos de processadores disjuntos

neste caso, o grupo , , consiste em processadores e é usado para realizar iterações do algoritmo em cascata (o grupo é usado para implementar a multiplicação elemento a elemento); número total de processadores;

A inicialização dos cálculos consiste no carregamento elemento a elemento dos processadores do grupo com os valores de 1 linha da matriz e do vetor; após o carregamento inicial, é realizada uma operação paralela de multiplicação elemento a elemento e subsequente implementação do circuito de soma em cascata usual;

Ao realizar cálculos, cada vez após a conclusão de uma operação de multiplicação elemento a elemento, os processadores do grupo são carregados com elementos da próxima linha da matriz e o processo de cálculo é iniciado para os dados recém-carregados.

Como resultado da aplicação do algoritmo descrito, muitos processadores implementam um pipeline para realizar a operação de multiplicação de uma linha de matriz por um vetor. Nesse transportador pode haver simultaneamente várias linhas separadas da matriz em diferentes estágios de processamento. Assim, por exemplo, após a multiplicação elemento a elemento dos elementos da primeira linha e do vetor, os processadores do grupo realizarão a primeira iteração do algoritmo em cascata para a primeira linha da matriz, e os processadores do grupo irão realizar a multiplicação elemento a elemento dos valores da segunda linha da matriz, etc. Para ilustração na Fig. 6.2 mostra a situação do processo de cálculo após 2 iterações do pipeline em.

Arroz. 6.2. Estado do pipeline para a operação de multiplicação de uma linha da matriz por um vetor após completar 2 iterações

2. Avaliação de indicadores de desempenho de algoritmos. A multiplicação da primeira linha por um vetor de acordo com o esquema em cascata será concluída normalmente após a execução de () operações paralelas. Para outras linhas - de acordo com o esquema de organização de cálculos do pipeline - o aparecimento dos resultados da multiplicação de cada linha seguinte ocorrerá após a conclusão de cada iteração subsequente do pipeline. Como resultado, o tempo total de execução da operação de multiplicação de vetores de matrizes pode ser expresso como

Esta estimativa é um pouco maior que o tempo de execução do algoritmo paralelo descrito no parágrafo anterior (), porém, o método recém-proposto requer menos dados transmitidos (o vetor é enviado apenas uma vez). Além disso, o uso de um esquema de pipeline resulta no aparecimento mais precoce de alguns dos resultados computacionais (o que pode ser útil em diversas situações de processamento de dados).

Como resultado, os indicadores de eficiência do algoritmo são determinados pelas seguintes relações:

3. Selecionando a topologia do sistema computacional. A topologia apropriada de um sistema de computação é completamente determinada pelo circuito de computação - esta é uma árvore binária altura O número de transferências de dados com tal topologia de rede é determinado pelo número total de iterações realizadas pelo pipeline, ou seja,

A inicialização dos cálculos começa nas folhas da árvore, os resultados da soma são acumulados no processador raiz.

A análise da complexidade das ações de comunicação realizadas para sistemas computacionais com outras topologias de comunicação interprocessadores deve ser realizada como uma tarefa independente (ver também cláusula 3.4).

Organização da computação paralela em

1. Escolhendo um método de computação paralela. Ao usar processadores para multiplicar uma matriz por um vetor, pode-se usar o algoritmo de multiplicação paralela linha por linha discutido anteriormente no manual, no qual as linhas da matriz são distribuídas entre os processadores linha por linha e cada processador implementa a operação de multiplicar qualquer linha individual da matriz por um vetor. Outra maneira possível de organizar a computação paralela poderia ser construir circuito de pipeline para a operação de multiplicação de uma linha de matriz por um vetor(produto escalar de vetores) organizando todos os processadores disponíveis em uma sequência linear ( governantes).

Tal esquema de cálculo pode ser definido da seguinte forma. Vamos imaginar o conjunto de processadores como uma sequência linear (ver Fig. 4.7):

Cada processador, , é usado para multiplicar os elementos de uma coluna de matriz e um elemento de vetor. Os cálculos realizados em cada processador, são os seguintes:

O próximo elemento da coluna da matriz é solicitado;

Os elementos e são multiplicados;

É solicitado o resultado dos cálculos do processador anterior;

Os valores são somados;

O resultado resultante é enviado para o próximo processador.

Arroz. 6.3. Estado do pipeline linear para a operação de multiplicação de uma linha da matriz por um vetor após realizar duas iterações

Ao inicializar o esquema descrito, você deve realizar uma série de ações adicionais:

Ao realizar a primeira iteração, cada processador solicita adicionalmente um elemento do vetor;

Para sincronizar os cálculos (ao realizar a próxima iteração do circuito, é solicitado o resultado do cálculo do processador anterior) no estágio de inicialização, o processador, , executa () um loop de espera.

Além disso, para a homogeneidade do circuito descrito para o primeiro processador, que não possui processador anterior, é aconselhável introduzir uma operação de adição vazia ( ).

Para ilustração na Fig. A Figura 6.3 mostra o estado do processo de computação após a segunda iteração do pipeline em.

2. Avaliação de indicadores de desempenho de algoritmos. A multiplicação da primeira linha pelo vetor de acordo com o esquema de pipeline descrito será concluída após a execução de () operações paralelas. O resultado da multiplicação das linhas a seguir ocorrerá após a conclusão de cada próxima iteração do pipeline (lembre-se de que a iteração de cada processador inclui a execução de operações de multiplicação e adição). Como resultado, o tempo total de execução de uma operação de multiplicação de vetores de matrizes pode ser expresso como:

Esta estimativa também é maior que o tempo mínimo de execução possível do algoritmo paralelo em. A utilidade da utilização de um esquema de computação em pipeline está, conforme observado no parágrafo anterior, na redução da quantidade de dados transmitidos e no aparecimento mais precoce de alguns dos resultados do cálculo.

Os indicadores de eficiência deste esquema computacional são determinados pelas relações:

, ,

3. Selecionando a topologia do sistema computacional. A topologia necessária do sistema de computação para executar o algoritmo descrito é determinada exclusivamente pelo esquema de computação proposto - este é um conjunto de processadores ordenados linearmente ( governante).

Usando um conjunto limitado de processadores ()

1. Escolhendo um método de computação paralela. Ao reduzir o número de processadores a um valor, um esquema de computação paralela para multiplicação de vetores de matrizes pode ser obtido adaptando o algoritmo de multiplicação linha por linha. Nesse caso, o circuito em cascata para somar os resultados da multiplicação elemento a elemento degenera e a operação de multiplicação de uma linha da matriz por um vetor é totalmente realizada em um único processador. O esquema computacional obtido com esta abordagem pode ser especificado da seguinte forma:

Um vetor e linhas de matriz são enviados para cada um dos processadores disponíveis;

A execução de uma operação de multiplicação de linhas de vetores de matrizes é realizada usando um algoritmo sequencial convencional.

Deve-se notar que o tamanho da matriz não pode ser um múltiplo do número de processadores e então as linhas da matriz não podem ser divididas igualmente entre os processadores. Nessas situações, você pode desviar-se do requisito de carregamento uniforme dos processadores e, para obter um esquema computacional mais simples, aceitar a regra de que os dados são colocados nos processadores apenas linha por linha (ou seja, os elementos de uma linha da matriz não podem ser dividido entre vários processadores). Um número desigual de linhas leva a diferentes cargas computacionais nos processadores; Assim, a conclusão dos cálculos (a duração total da resolução do problema) será determinada pelo tempo de operação do processador mais carregado (neste caso, parte desse tempo total, os processadores individuais podem ficar ociosos devido ao esgotamento de sua participação de cálculos). A carga desigual dos processadores reduz a eficiência do uso do MCS e, ao considerar este exemplo, podemos concluir que problema de equilíbrio

3. Selecionando a topologia do sistema computacional. De acordo com a natureza das interações interprocessadores realizadas no esquema de computação proposto, a organização dos processadores na forma de estrelas(ver Fig. 1.1). Um processador de controle de tal topologia pode ser usado para carregar processadores de computação com dados iniciais e receber os resultados dos cálculos realizados.

Multiplicação da matriz

O problema da multiplicação matriz-matriz é definido pelas relações

(para simplificar a apresentação, assumiremos que as matrizes multiplicadas e são quadradas e possuem ordem).

Uma análise dos possíveis métodos de execução paralela desta tarefa pode ser realizada por analogia com a consideração do problema de multiplicação de uma matriz por um vetor. Deixando tal análise para estudo independente, usaremos o exemplo do problema de multiplicação de matrizes para mostrar o uso de diversas abordagens gerais que nos permitem formar métodos paralelos para resolver problemas complexos.