O produto de uma matriz e um vetor c. Multiplicação de uma matriz por um vetor

12.09.202227.05.2017

O sistema MatLab simplesmente executa operações matemáticas em matrizes e vetores. Considere primeiro as operações simples de adição e multiplicação de matrizes e vetores. Sejam dados dois vetores

um = ; vetor linha %
b = ; % vetor coluna

então a multiplicação desses dois vetores pode ser escrita como

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

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

Adição e subtração de dois vetores é escrita como

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 de coluna ou dois vetores de linha. Caso contrário, o MatLab emitirá 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 sistema MatLab informará um erro e o programa terminará na linha correspondente.

Da mesma forma, as operações de multiplicação e adição entre matrizes são realizadas:

A = ;
B = uns(3);
C=A+B; % adição de duas matrizes do mesmo tamanho
D=A+5; % adição de uma matriz e um 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; % multiplicação de uma matriz por um número

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

um = ; vetor linha %
b = a'; % vetor coluna formado por
% de transposição do vetor linha a.
A = ; % matriz 3x3 elementos
B = a*A; %b= - vetor linha
C=A*b; % C = - vetor coluna
D = a*A*a'; % D = 45 – número, soma da matriz A
E = A'; % E é a matriz transposta A
F = inv(A); % F - matriz inversa A
G = A^-1; % G - matriz inversa A

Do exemplo acima, pode-se ver que a operação de transposição de matrizes e vetores é denotada pelo símbolo ‘ (apóstrofe), que é colocado após o nome do vetor ou matriz. O cálculo da matriz inversa 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 ao implementar vários algoritmos.

Se durante os cálculos for necessário multiplicar, dividir ou elevar elementos de um vetor ou elemento de matriz por elemento, os seguintes operadores serão usados para isso:

.* - multiplicação elementar;
./ e .\ - divisões elementares;
.^ - exponenciação elementar.

Considere a operação desses operadores no exemplo a seguir.

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

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

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

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

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

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

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

A = ;
= máx(A); % V=, I=
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 maneira semelhante, que determina o valor mínimo de um vetor ou elemento de 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 uma matriz:

um = ;
s = soma(a); %s = 3+5+4+2+1=15
A = ;
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 por colunas e depois por linhas. Como resultado, a variável S2 contém a soma dos valores de todos os elementos da matriz A.

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

um = ;

b1 = ordenar(a); %b1=
b2 = sort(a, 'desce'); %b2=
b3 = sort(a, 'ascender'); %b3=

para matrizes

A = ;
B1 = classificar(A); %B1=
B2 = sort(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 de acordo com a qual os elementos necessários são encontrados, por exemplo:

um = ;
b1 = encontrar(a == 2); %b1 = 4 - índice de elemento 2
b2 = encontrar(a ~= 2); % b2 = - índices sem 2
b3 = encontrar(a > 3); %b3=

No exemplo acima, o símbolo ‘==’ significa verificação de igualdade, e o símbolo ‘~=’ realiza uma verificação de desigualdade dos valores dos elementos do vetor a. Mais detalhes sobre esses operadores serão descritos na seção sobre 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 assim:

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

Assim, na lição anterior, analisamos as regras de adição e subtração de 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á aviso: multiplicar duas matrizes não é de forma alguma multiplicar os números em células com as mesmas coordenadas, como você pode pensar. Aqui tudo é muito mais divertido. E você tem que começar com definições preliminares.

matrizes consistentes

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

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

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

Nós nos preocupamos com a ordem das matrizes. 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 são, como fosse, não 3 linhas no segundo).
A consistência é fácil de verificar se você escrever todas as dimensões uma após a outra. Usando o exemplo do parágrafo anterior: "3 2 2 5" - os mesmos números estão no meio, então as matrizes são consistentes. Mas “2 5 3 2” não está de acordo, porque há números diferentes no meio.

Além disso, o capitão parece sugerir que matrizes quadradas de mesmo tamanho $\left[ n\times n \right]$ são sempre consistentes.

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

Então: as coordenadas também são pares ordenados, que são compostos de números. Mas nada o impede de fazer esse par de matrizes. Então será possível dizer: "Um par ordenado de matrizes $\left(A;B \right)$ é consistente se o número de colunas da primeira matriz for igual ao número de linhas da 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 para eles a operação de multiplicação.

Definição. O produto de duas matrizes consistentes $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 de acordo com 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\limits_(t=1)^(n)(((a)_(i;t))\cdot ((b)_(t;j))) \end(align)\]

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

Para quem vê esta definição pela primeira vez, duas perguntas surgem imediatamente:

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

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

Em primeiro lugar, notamos que a linha longa para calcular $((c)_(i;j))$ (especialmente coloque um ponto e vírgula entre os índices para não confundir, mas você não precisa colocá-los em geral - eu mesmo cansei de digitar a fórmula na definição) realmente se resume a uma regra simples:

Pegue a $i$-ésima linha na primeira matriz;
Pegue a $j$-ésima coluna na segunda matriz;
Obtemos duas sequências de números. Multiplicamos os elementos dessas sequências com os mesmos números e, em seguida, adicionamos os produtos resultantes.

Este processo é fácil de entender a partir da 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 adicionamos os produtos resultantes - obtemos $((c)_(ij ))$. E assim para todo $1\le i\le m$ e $1\le j\le k$. Aqueles. haverá $m\vezes k$ tais "perversões" no total.

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

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

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

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

Na verdade, naqueles anos distantes, quando as árvores eram mais verdes e o céu mais claro, simplesmente multiplicávamos o vetor linha $\overrightarrow(a)$ pelo vetor coluna $\overrightarrow(b)$.

Nada mudou hoje. Só que agora existem mais desses vetores linha e coluna.

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

Multiplicação de matrizes quadradas

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. Assim, temos duas matrizes: $A=\esquerda[ 2\vezes 2 \direita]$ e $B=\esquerda[ 2\vezes 2 \direita]$. É claro que eles são consistentes (matrizes quadradas do mesmo tamanho são sempre consistentes). Então fazemos a multiplicação:

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

No processo de cálculos, compilamos uma matriz intermediária, onde pintamos diretamente quais números estão incluídos em uma determinada célula. Isso é exatamente o que deve ser feito ao resolver 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$ em 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 ;
Associativo: $\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 $

E agora - tudo igual, mas com mais detalhes.

A multiplicação de matrizes é muito parecida com a multiplicação clássica de números. Mas há diferenças, a mais importante das quais é que a multiplicação de matrizes é, de um modo geral, não comutativa.

Considere 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, obtemos 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(matrix) -14 & 4 \\ 0 & 10 \\\end(matrix )\certo]\]

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

Entre as matrizes quadradas de um dado tamanho $n$, sempre haverá aquelas que dão o mesmo resultado tanto na multiplicação direta quanto na ordem inversa. Como descrever todas essas matrizes (e quantas delas em geral) é um tópico para uma lição separada. Hoje não vamos falar sobre isso. :)

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 de uma só vez, não é necessário fazê-lo com antecedência: é 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 é preciso 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á definitivamente contém a matriz $E$, que é chamada de matriz identidade.

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

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; \\ & \left(A+B \right)\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, geralmente é necessário realizar a operação inversa: notamos a mesma matriz, tiramos do colchete, realizamos a adição e, assim, simplificamos nossa vida. :)

Observe que 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 se deve justamente ao fato de que a multiplicação de matrizes não é comutativa (e, em geral, na álgebra não comutativa, existem muitos tipos de piadas que nem vêm à mente ao trabalhar com números comuns). E se, por exemplo, você precisar anotar essa propriedade durante o exame, certifique-se de escrever as duas fórmulas, caso contrário o professor pode ficar um pouco zangado.

Ok, tudo isso eram contos de fadas sobre matrizes quadradas. E os retângulos?

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=\esquerda[ 3\vezes 2 \direita]$ e $B=\esquerda[ 2\vezes 2 \direita]$. Vamos escrever os números que indicam os tamanhos em uma linha:

Como você pode ver, os dois números centrais são os mesmos. Isso significa que as matrizes são consistentes e podem ser multiplicadas. E 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(array)\direita]. \fim(alinhar)\]

Tudo está claro: a matriz final tem 3 linhas e 2 colunas. Bastante $=\esquerda[ 3\vezes 2 \direita]$.

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 considere uma das melhores tarefas de treinamento para quem está começando a trabalhar com matrizes. Nele, você não precisa apenas multiplicar cerca de dois comprimidos, mas primeiro determinar: tal multiplicação é permitida?

Problema 4. Encontre todos os possíveis produtos pareados 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=\esquerda[ \begin(matriz)0 & 1 \\ 1 & 0 \\\end(matriz) \direita]$.

Solução. Primeiro, vamos anotar as dimensões das matrizes:

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

Obtemos que a matriz $A$ só pode ser combinada com a matriz $B$, pois o número de colunas em $A$ é 4 e apenas $B$ tem 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 execute as etapas intermediárias por conta própria. Apenas observarei que é melhor determinar o tamanho da matriz resultante com antecedência, mesmo antes de qualquer cálculo:

\\cdot \esquerda[ 4\vezes 2 \direita]=\esquerda[ 2\vezes 2 \direita]\]

Em outras palavras, simplesmente removemos os coeficientes "transitórios" que asseguravam a consistência das matrizes.

Que outras opções são possíveis? Certamente é possível 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 \esquerda[ 2\vezes 4 \direita]=\esquerda[ 4\vezes 4 \direita]\]

Resumindo, a saída será uma matriz $\left[ 4\times 4 \right]$, cujos coeficientes são fáceis de calcular:

\\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 & -8 \\\end(array) \right]\]

Obviamente, você também pode combinar $C\cdot A$ e $B\cdot C$, e é isso. Portanto, simplesmente escrevemos 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 fazer essa tarefa sozinho. E outra tarefa semelhante que está na lição de casa. Esses pensamentos aparentemente simples o ajudarão a descobrir todas as etapas principais da multiplicação de matrizes.

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

Vetores linha e vetores 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 $\left[ m\times 1 \right]$, ou seja, consistindo de várias linhas e apenas uma coluna.

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

Na verdade, já encontramos esses objetos. Por exemplo, um vetor tridimensional comum de 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ê precisa ter cuidado apenas ao coordenar com as matrizes multiplicadoras circundantes.

Tarefa 5. Multiplique:

\[\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. Temos um produto de matrizes consistentes: $\left[ 3\times 3 \right]\cdot \left[ 3\times 1 \right]=\left[ 3\times 1 \right]$. Encontre 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 tudo é consistente: $\left[ 1\times 3 \right]\cdot \left[ 3\times 3 \right]=\left[ 1\times 3 \right]$. Consideramos o trabalho:

\[\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, ao multiplicar um vetor linha e um vetor coluna por uma matriz quadrada, a saída é sempre uma linha ou coluna do mesmo tamanho. Este fato tem muitas aplicações - desde a resolução de equações lineares até todos os tipos de transformações de coordenadas (que no final 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árias potências.

Tais trabalhos são sempre coordenados:

\\cdot \left[ n\vezes n \direita]=\esquerda[ n\vezes n \direita]\]

E são designados da mesma forma que os graus ordinários:

\[\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)). \\ \end(align)\]

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

Tarefa 7. Aumente a matriz para a potência especificada:

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

Solução. OK, vamos construir. Vamos ao quadrado primeiro:

\[\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(matrix) 1 & 1 \\ 0 & 1 \\\end(matrix) \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 & 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 especificada:

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

Solução. Só não chore agora pelo fato de que “o diploma é muito alto”, “o mundo não é justo” e “os professores perderam completamente os bancos”. Na verdade, tudo é 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(matrix) 1 & 1 \\ 0 & 1 \\\ end(matrix) \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(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(matrix) 1 & 1 \\ 0 & 1 \\\end(matrix) \right ] \right)= \\ & =\left[ \begin(matrix) 1 & 6 \\ 0 & 1 \\\end(matrix) \right]\cdot \left[ \begin(matrix) 1 & 4 \\ 0 & 1 \\\end(matrix) \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 na tarefa anterior, mas estava implícito.

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(matrix) 1 & 1 \\ 0 & 1 \\\end(matrix) \right])^(n))=\left[ \begin(array)(*(35) (r)) 1 & n \\ 0 & 1 \\\end(array) \right]\]

Este fato é fácil de provar por indução matemática ou multiplicação direta. No entanto, nem sempre é possível capturar esses padrões ao elevar a uma potência. Portanto, tenha cuidado: muitas vezes é mais fácil e rápido multiplicar várias matrizes "em branco" do que procurar alguns padrões ali.

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

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

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

Solução. Não vamos procurar padrões. Trabalhamos "através":

\[((\left[ \begin(matrix) 0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \\\end(matrix) \right])^(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]\]

Vamos começar elevando ao quadrado esta matriz:

\[\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( array)(*(35)(r)) 2 & 3 & 3 \\ 3 & 2 & 3 \\ 3 & 3 & 2 \\\end(array) \right] \end(align)\]

Isso é tudo. Problema resolvido.

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

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

Esta lição pode terminar. Da próxima vez, consideraremos a operação inversa: procuraremos os multiplicadores originais usando o produto existente.

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

Definição 1

O produto de matrizes (C=AB) é uma operação apenas para matrizes consistentes 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

Dados da matriz:

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

Matriz C , cujos elementos c i j são calculados pela 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 , . . . m

Exemplo 2

Vamos calcular os produtos AB=BA:

A = 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 B A são encontrados, mas são matrizes de tamanhos diferentes: A B não é igual a B A.

Propriedades da multiplicação de matrizes

Propriedades de multiplicação de matrizes:

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

Exemplo 1

Verifique a propriedade #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

Verificamos a propriedade nº 2: A (B + C) \u003d 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 \u003d 1 2 3 4 × 5 6 7 8 + 1 2 3 4 × 1 0 0 2 \u003d 19 22 43 50 + 1 4 3 8 \u003d 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 encontre primeiro 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ção:

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

1). A B \u003d 4 3 7 5 × - 28 93 38 - 126 \u003d 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 \u003d (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 \u003d (A B) C \u003d 7 3 2 1 - 10 9 14 - 12 \u003d 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 \u003d A k do mesmo tamanho, que se obtém do original multiplicando por um determinado número de todos os seus elementos:

bi , j = k × ai , j

Propriedades de multiplicar uma matriz por um número:

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

Exemplo 4

Encontre o produto da matriz A \u003d 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

Multiplicação de uma matriz por um vetor

Definição 3

Para encontrar o produto de uma matriz e um vetor, você precisa multiplicar de acordo com 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 c 2 ⋯ c 1m

se você multiplicar uma matriz por um vetor linha, a matriz a ser 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

Encontre o produto da matriz A e do vetor coluna B:

A B \u003d 2 4 0 - 2 1 3 - 1 0 1 1 2 - 1 \u003d 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

Encontre o produto da matriz A e do vetor linha B:

A \u003d 3 2 0 - 1, B \u003d - 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 \u003d - 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

Cada vetor pode ser visto como uma matriz de uma coluna ou uma linha. Uma matriz de uma coluna será chamada de vetor coluna e uma matriz de uma linha será chamada 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, deve-se tratar o vetor como um vetor coluna. Ao multiplicar um vetor por uma matriz, ele deve ser tratado como um vetor linha.

matriz multiplicadora

para o vetor complexo

Nós obtemos o resultado

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

Gostaria de chamar a atenção para o fato de que a matriz na primeira e na segunda versão, apesar dos mesmos valores, é completamente diferente (elas têm dimensões diferentes)

No primeiro caso, o vetor é considerado como uma coluna e então é necessário multiplique matriz por vetor, e no segundo caso temos um vetor linha e então temos o 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 matriz-vetor

Matriz

coluna de vetores

vetor 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 pela matriz é igual à soma dos produtos dos vetores pela matriz

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

4. O produto de um vetor linha pelo produto de uma matriz e um vetor coluna é equivalente ao produto do produto de um vetor linha por 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.

Multiplicação de uma matriz por um vetor. Alcance a maior velocidade possível. Uso de paralelismo de nível médio. Organização da computação paralela para p = n. Uso de um conjunto limitado de processadores. Multiplicação da matriz. Análise macrooperacional de algoritmos de resolução de problemas. Organização do paralelismo baseada no compartilhamento de dados.

Multiplicação de uma matriz por um vetor

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

Assim, obter o vetor resultante envolve repetir o mesmo tipo de operações para multiplicar as linhas da matriz e do vetor . A obtenção de cada uma dessas operações inclui a multiplicação elemento por elemento dos elementos da linha da matriz e do vetor e a subseqüente soma dos produtos resultantes. O número total de operações escalares necessárias é estimado pelo valor

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

Alcançar o desempenho mais rápido possível ()

Vamos fazer uma análise das dependências de informação no algoritmo de multiplicação matriz-vetor para selecionar possíveis formas 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;

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

A soma dos produtos obtidos em cada operação de multiplicação de uma linha de uma matriz por um vetor pode ser realizada usando uma das variantes do algoritmo de somação anteriormente consideradas (algoritmo serial, esquemas convencionais e em cascata 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. O conjunto de processadores é dividido em grupos

cada um dos quais representa um conjunto de processadores para executar a operação de multiplicar uma única linha de uma matriz por um vetor. No início dos cálculos, cada processador do grupo recebe um elemento da linha da matriz e o correspondente elemento do vetor. Em seguida, cada processador executa a operação de multiplicação. Os cálculos subsequentes são realizados de acordo com o esquema de soma em cascata. Para ilustração na fig. 6.1 mostra o esquema computacional para os processadores do grupo com a dimensão da matriz .

Arroz. 6.1. Esquema computacional para multiplicar 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 esquema em cascata

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

, ,

Para o problema considerado de multiplicação de uma matriz por um vetor, as topologias mais adequadas são estruturas que fornecem transferência rápida de dados (caminhos de comprimento unitário) em um esquema de soma 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 resultam em maior tempo de comunicação devido a caminhos de dados mais longos. 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 o esquema em cascata, o comprimento do caminho de transmissão de cada soma parcial recebida na iteração , , é igual a . Se aceitarmos que a transmissão de dados ao longo de um caminho de comprimento em topologias com estrutura linear requer a execução de operações de transmissão de dados, o número total de operações paralelas (comprimento total dos caminhos) de transmissão de dados é determinado pelo valor

(excluindo transferências de dados para processadores de inicialização).

Aplicação de um sistema computacional com topologia retangular rede bidimensional tamanho leva a uma interpretação simples e visual dos cálculos realizados (a estrutura da rede corresponde à estrutura dos dados processados). Para tal topologia, é mais conveniente colocar as linhas da matriz ao longo das linhas horizontais da rede; neste caso, os elementos do vetor devem ser enviados ao longo das verticais do sistema computacional. A execução de cálculos com esse arranjo de dados pode ser realizada em paralelo ao longo das linhas da rede; como resultado, o número total de transferências de dados é o mesmo que os resultados de rule().

As ações de comunicação realizadas na resolução do problema são para transferir 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 a implementação do algoritmo paralelo. Ao implementar um algoritmo paralelo, é aconselhável destacar o estágio inicial de carregamento dos processadores usados com dados iniciais. Essa inicialização é simplesmente fornecida para a topologia de um sistema de computação com uma topologia na forma gráfico completo(o carregamento é fornecido com uma única operação paralela de transferência de dados). Ao organizar um conjunto de processadores na forma hipercubo Pode ser útil ter um controle de dois níveis do processo de bootstrap, no qual o processador de controle central distribui as linhas da matriz e do vetor para os processadores de controle dos grupos de processadores , , que, por sua vez, distribuem os elementos da matriz e do vetor linhas para os processadores executivos. Para topologias na forma governantes ou argolas operações de transferência de dados sequenciais são necessárias com uma quantidade decrescente sequencial de dados transferidos de para elementos.

Usando paralelismo de nível médio ()

1. Escolha do método de computação paralela. Com uma diminuição no número disponível de processadores usados (), o esquema usual de soma em cascata ao realizar operações de multiplicação de linhas de matriz por um vetor torna-se inaplicável. Para simplificar a apresentação do material, assumimos e usamos um esquema de 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 o valor

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

Com o número de processadores , quando o tempo de execução do algoritmo é estimado como , pode ser proposto um novo esquema para execução paralela de cálculos, no qual para cada iteração de somatórios em cascata são utilizados conjuntos de processadores não sobrepostos. Com essa abordagem, o número disponível de processadores é suficiente para implementar apenas uma operação de multiplicação de uma linha de uma matriz e 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 usando processadores ociosos para processar as próximas linhas da matriz. Como resultado, o seguinte esquema pode ser formado transportador realizar a multiplicação de matrizes e vetores:

O conjunto de processadores é dividido em grupos de processadores não sobrepostos

o grupo , , consiste em processadores e é usado para iterar o algoritmo em cascata (o grupo é usado para implementar a multiplicação elementar); número total de processadores;

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

Ao realizar cálculos, cada vez após a conclusão da 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, uma pluralidade de processadores implementa um pipeline para realizar a operação de multiplicar uma linha de matriz por um vetor. Nesse pipeline, várias linhas individuais da matriz podem estar simultaneamente 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 de grupo executarão a primeira iteração do algoritmo em cascata para a primeira linha da matriz e os processadores de grupo executarão o elemento multiplicação por sentido dos valores da segunda linha da matriz e assim por diante. Para ilustração na fig. 6.2 mostra a situação do processo de computação após 2 iterações do pipeline em .

Arroz. 6.2. O estado do pipeline para a operação de multiplicar uma linha de uma matriz por um vetor após realizar 2 iterações

2. Avaliação de indicadores de desempenho do algoritmo. A multiplicação da primeira linha pelo vetor de acordo com o esquema em cascata será concluída, como de costume, após a execução de () operações paralelas. Para outras linhas, de acordo com o esquema de pipeline de organização dos cálculos, os resultados da multiplicação de cada linha sucessiva aparecerão 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 matriz-vetor pode ser expresso como

Essa estimativa é um pouco maior que o tempo de execução do algoritmo paralelo descrito no parágrafo anterior (), porém, o novo método proposto requer menos dados a serem transmitidos (o vetor é enviado apenas uma vez). Além disso, o uso de um esquema de pipeline leva a uma aparência anterior de alguns dos resultados do cálculo (o que pode ser útil em várias situações de processamento de dados).

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

3. Escolha da topologia do sistema de computador. A topologia conveniente de um sistema de computação é completamente determinada pelo esquema de computação - esta é uma árvore binária altura . O número de transferências de dados com essa 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 entre processadores é considerada uma tarefa independente (ver também Seção 3.4).

Organização da computação paralela com

1. Escolha do método de computação paralela. Ao utilizar processadores para multiplicar uma matriz por um vetor, pode-se utilizar o algoritmo de multiplicação paralela linha por linha já discutido no manual, no qual as linhas da matriz são distribuídas linha por linha entre os processadores e cada processador implementa a operação de multiplicar qualquer linha individual da matriz pelo vetor . Outra maneira possível de organizar a computação paralela pode ser construir esquema de pipeline para a operação de multiplicar uma linha de uma 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 como segue. Vamos representar o conjunto de processadores como uma sequência linear (ver Fig. 4.7):

cada processador, , é usado para multiplicar os elementos da coluna da matriz e o elemento do vetor. A execução dos cálculos em cada processador , , consiste no seguinte:

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 adicionados;

O resultado é enviado para o próximo processador.

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

Ao inicializar o esquema descrito, é necessário executar várias ações adicionais:

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

Para sincronizar os cálculos (durante a execução da próxima iteração do circuito, é solicitado o resultado do cálculo do processador anterior) na fase de inicialização, o processador , , executa () um loop de espera.

Além disso, para uniformidade do esquema 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. 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 do algoritmo. 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, 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 da operação de multiplicação matriz-vetor pode ser expresso como:

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

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

, ,

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

Usando um conjunto limitado de processadores ()

1. Escolha do método de computação paralela. Quando o número de processadores é reduzido a um valor, um esquema computacional paralelo para multiplicação matriz-vetor pode ser obtido como resultado da adaptação do algoritmo de multiplicação linha por linha. Nesse caso, o esquema em cascata para somar os resultados da multiplicação elementar degenera e a operação de multiplicar 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 operação de multiplicar linhas de uma matriz por um vetor é realizada usando o algoritmo sequencial usual.

Deve-se notar que o tamanho da matriz pode não ser um múltiplo do número de processadores e, portanto, as linhas da matriz não podem ser divididas igualmente entre os processadores. Nessas situações, é possível desviar-se do requisito de uniformidade de carga do processador 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, elementos de uma linha de uma matriz não pode ser compartilhado entre vários processadores). Um número diferente de linhas resulta em uma carga computacional diferente nos processadores; assim, a conclusão dos cálculos (a duração total da solução da tarefa) será determinada pelo tempo de operação do processador mais carregado (ao mesmo tempo, alguns processadores podem ficar ociosos parte desse tempo total devido ao esgotamento de sua parcela de cálculos). O carregamento desigual dos processadores reduz a eficiência do uso do MCS e, considerando este exemplo, podemos concluir que problema de balanceamento

3. Escolha da topologia do sistema de computador. De acordo com a natureza das interações entre processadores realizadas no esquema computacional proposto, a organização dos processadores na forma 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 de multiplicar uma matriz por uma matriz é definido pelas relações

(para simplificar, assumiremos que as matrizes multiplicadas e são quadradas e têm ordem).

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