Produto Matrix
O produto da matriz refere-se à multiplicação de matrizes , inicialmente chamada de “composição de matrizes”.
Produto de matriz comum
Esta é a maneira mais comum de multiplicar matrizes entre eles.
Em álgebra linear , uma matriz A de dimensões m linhas en colunas (matriz m × n ) representa um mapa linear ƒ de um espaço de dimensão n a um espaço de dimensão m . Uma matriz de coluna V de n linhas é uma matriz n × 1 e representa um vetor v de um espaço vetorial de dimensão n . O produto A × V representa ƒ ( v ).
Se A e B representam os mapas lineares ƒ eg respectivamente , então A × B representa a composição dos mapas ƒo g .
Esta operação é usada em particular em mecânica durante cálculos de torção estáticos , ou em processamento de dados para a matriz de adjacência de um grafo.
O produto de duas matrizes só pode ser definido se o número de colunas da primeira matriz for igual ao número de linhas da segunda matriz, ou seja, quando forem de tipo compatível.
Se é uma matriz de tipo e é uma matriz de tipo , então seu produto , notado é uma matriz de tipo dada por:
NO=(noeuj){\ displaystyle A = (a_ {ij})}
(m,não){\ displaystyle (m, n)}
B=(beuj){\ displaystyle B = (b_ {ij})}
(não,p){\ displaystyle (n, p)}
NOB=(vseuj){\ displaystyle AB = (c_ {ij})}
(m,p){\ displaystyle (m, p)}![(m, p)](https://wikimedia.org/api/rest_v1/media/math/render/svg/ac9c06c928c28ebca304079c6ded976858428af1)
∀eu,j:vseuj=∑k=1nãonoeukbkj=noeu1b1j+noeu2b2j+⋯+noeunãobnãoj{\ displaystyle \ forall i, j: c_ {ij} = \ sum _ {k = 1} ^ {n} a_ {ik} b_ {kj} = a_ {i1} b_ {1j} + a_ {i2} b_ { 2j} + \ cdots + a_ {in} b_ {nj}}![\ forall i, j: c _ {{ij}} = \ sum _ {{k = 1}} ^ {n} a _ {{ik}} b _ {{kj}} = a _ {{i1}} b _ {{1j}} + a _ {{i2}} b _ {{2j}} + \ cdots + a _ {{in}} b _ {{nj}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/840716c2745c63bd10c38a0b5ecac966faf0b1ff)
A figura a seguir mostra como calcular os coeficientes e a matriz produzida se for uma matriz de tipo e for uma matriz de tipo .
vs12{\ displaystyle c_ {12}}
vs33{\ displaystyle c_ {33}}
NOB{\ displaystyle AB}
NO{\ displaystyle A}
(4,2){\ displaystyle (4.2)}
B{\ displaystyle B}
(2,3){\ displaystyle (2,3)}![(2,3)](https://wikimedia.org/api/rest_v1/media/math/render/svg/b31c93ba409b1d9834540d2a9fa66e8ab5a3d8dc)
vs12=∑r=12no1rbr2=no11b12+no12b22{\ displaystyle {\ color {BrickRed} c_ {12}} = \ sum _ {r = 1} ^ {2} a_ {1r} b_ {r2} = a_ {11} b_ {12} + a_ {12} b_ {22}}
vs33=∑r=12no3rbr3=no31b13+no32b23{\ displaystyle {\ color {NavyBlue} c_ {33}} = \ sum _ {r = 1} ^ {2} a_ {3r} b_ {r3} = a_ {31} b_ {13} + a_ {32} b_ {23}}
Exemplos
(102-1)×(34-2-3){\ displaystyle {\ begin {pmatrix} 1 e 0 \\ 2 & -1 \ end {pmatrix}} \ times {\ begin {pmatrix} 3 e 4 \\ - 2 e -3 \\\ end {pmatrix}} }
=((1×3+0×-2)(1×4+0×-3)(2×3+-1×-2)(2×4+-1×-3))=(34811){\ displaystyle = {\ begin {pmatrix} (1 \ vezes 3 + 0 \ vezes -2) & (1 \ vezes 4 + 0 \ vezes -3) \\ (2 \ vezes 3 + -1 \ vezes -2) & (2 \ vezes 4 + -1 \ vezes -3) \ end {pmatriz}} = {\ begin {pmatriz} 3 e 4 \\ 8 & 11 \ end {pmatriz}}}
Em geral, a multiplicação da matriz não é comutativa , ou seja, não é igual a , como mostra o exemplo a seguir.
NOB{\ displaystyle AB}
BNO{\ displaystyle BA}![BA](https://wikimedia.org/api/rest_v1/media/math/render/svg/5b8efb97e621ab9b49f8498a49704690bdeb2698)
(12043-1)(512334)=(97239){\ displaystyle {\ begin {pmatrix} 1 & 2 & 0 \\ 4 & 3 & -1 \\\ end {pmatrix}} {\ begin {pmatrix} 5 & 1 \\ 2 & 3 \\ 3 & 4 \ \\ end {pmatrix}} = {\ begin {pmatrix}}} 9 e 7 \\ 23 e 9 \\\ end {pmatrix}}}![{\ begin {pmatrix} 1 & 2 & 0 \\ 4 & 3 & -1 \\\ end {pmatrix}} {\ begin {pmatrix} 5 & 1 \\ 2 & 3 \\ 3 & 4 \\\ end {pmatriz}} = {\ begin {pmatrix} 9 e 7 \ \ 23 e 9 \\\ end {pmatrix}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/65629483342105d447b68ac133981a8f98a59f83)
enquanto
(512334)(12043-1)=(913-11413-31918-4){\ displaystyle {\ begin {pmatrix} 5 & 1 \\ 2 & 3 \\ 3 & 4 \\\ end {pmatrix}} {\ begin {pmatrix} 1 & 2 & 0 \\ 4 & 3 & -1 \ \\ end {pmatrix}} = {\ begin {pmatrix}} = {\ begin {pmatrix}} 9 e 13 & -1 \\ 14 & 13 & -3 \\ 19 & 18 & -4 \\\ end { pmatrix}}}
Multiplicação de matrizes por bloco
Se considerarmos as matrizes e , onde e são matrizes que satisfazem:
M=(NOBVSD){\ displaystyle M = \ left ({\ begin {smallmatrix} A&B \\ C&D \ end {smallmatrix}} \ right)}
NÃO=(NO′B′VS′D′){\ displaystyle N = \ left ({\ begin {smallmatrix} A '& B' \\ C '& D' \ end {smallmatrix}} \ right)}
NO,NO′,B,B′,VS,VS′{\ displaystyle A, A ', B, B', C, C '}
D,D′{\ displaystyle D, D '}![D, D '](https://wikimedia.org/api/rest_v1/media/math/render/svg/2e2b887c754013186ad0fb182a15f9f1f5084d56)
- O número de colunas de e é igual ao número de linhas de eNO{\ displaystyle A}
VS{\ displaystyle C}
NO′{\ displaystyle A '}
B′{\ displaystyle B '}
- O número de colunas de e é igual ao número de linhas de eB{\ displaystyle B}
D{\ displaystyle D}
VS′{\ displaystyle C '}
D′{\ displaystyle D '}
então temos igualdade
MNÃO=(NONO′+BVS′NOB′+BD′VSNO′+DVS′VSB′+DD′){\ displaystyle MN = {\ begin {pmatrix} AA '+ BC' & AB '+ BD' \\ CA '+ DC' & CB '+ DD' \ end {pmatrix}}}![MN = {\ begin {pmatrix} AA '+ BC' & AB '+ BD' \\ CA '+ DC' & CB '+ DD' \ end {pmatrix}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/53710a3affb017d7f918508559f02fdcec6211c9)
Observe a analogia entre o produto da matriz de bloco e o produto de duas matrizes quadradas de ordem 2.
NB: não se define assim uma nova forma de multiplicação de matrizes. Este é simplesmente um método de cálculo do produto matricial comum que pode simplificar os cálculos.
Produto Hadamard
Para duas matrizes do mesmo tipo, temos o produto Hadamard ou produto componente por componente. O produto de Hadamard de duas matrizes e do tipo , denotado A · B = ( c ij ) , é uma matriz de tipo dada por
NO=(noeuj){\ displaystyle A = (a_ {ij})}
B=(beuj){\ displaystyle B = (b_ {ij})}
(m,não){\ displaystyle (m, n)}
(m,não){\ displaystyle (m, n)}![(m, n)](https://wikimedia.org/api/rest_v1/media/math/render/svg/274d4857135a7d28a94ba9ee8135779615084d43)
vseuj=noeuj×beuj.{\ displaystyle c_ {ij} = a_ {ij} \ times b_ {ij}.}![{\ displaystyle c_ {ij} = a_ {ij} \ times b_ {ij}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/dd8ac7a3b16e6e8a6d6d4ca8673fe87b7805190c)
Por exemplo :
(132100122)⋅(002750211)=(1×03×02×21×70×50×01×22×12×1)=(004700222).{\ displaystyle {\ begin {pmatrix} 1 & 3 & 2 \\ 1 & 0 & 0 \\ 1 & 2 & 2 \ end {pmatrix}} \ cdot {\ begin {pmatrix} 0 & 0 & 2 \\ 7 & 5 & 0 \ 2 & 1 & 1 \ end {pmatrix}} = {\ begin {pmatrix} 1 \ times 0 & 3 \ times 0 & 2 \ times 2 \\ 1 \ times 7 & 0 \ times 5 & 0 \ times 0 \\ 1 \ times 2 & 2 \ times 1 e 2 \ times 1 \ end {pmatrix}} = {\ begin {pmatrix} 0 & 0 & 4 \\ 7 & 0 & 0 \\ 2 & 2 & 2 \ end {pmatrix}}.}![{\ displaystyle {\ begin {pmatrix} 1 & 3 & 2 \\ 1 & 0 & 0 \\ 1 & 2 & 2 \ end {pmatrix}} \ cdot {\ begin {pmatrix} 0 & 0 & 2 \\ 7 & 5 & 0 \ 2 & 1 & 1 \ end {pmatrix}} = {\ begin {pmatrix} 1 \ times 0 & 3 \ times 0 & 2 \ times 2 \\ 1 \ times 7 & 0 \ times 5 & 0 \ times 0 \\ 1 \ times 2 & 2 \ times 1 e 2 \ times 1 \ end {pmatrix}} = {\ begin {pmatrix} 0 & 0 & 4 \\ 7 & 0 & 0 \\ 2 & 2 & 2 \ end {pmatrix}}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/bd6bc1b6f505189f3fd8eb66de3069f2f2a20362)
Este produto é uma submatriz do produto Kronecker (veja abaixo).
Produto Kronecker
Para duas matrizes arbitrárias e , temos o produto tensorial ou produto de Kronecker A ⊗ B que é definido por
NO=(noeuj){\ displaystyle A = (a_ {ij})}
B{\ displaystyle B}
(no11Bno12B⋯no1nãoB⋮⋮⋱⋮nom1Bnom2B⋯nomnãoB){\ displaystyle {\ begin {pmatrix} a_ {11} B & a_ {12} B & \ cdots & a_ {1n} B \\\ vdots & \ vdots & \ ddots & \ vdots \\ a_ {m1} B & a_ {m2} B & \ cdots & a_ {mn} B \ end {pmatriz}}}![{\ begin {pmatrix} a _ {{11}} B & a _ {{12}} B & \ cdots & a _ {{1n}} B \\\ vdots & \ vdots & \ ddots & \ vdots \\ a _ {{m1}} B & a_ {{m2}} B & \ cdots e a _ {{mn}} B \ end {pmatrix}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ce82af0d71300caa5d6b3eb22a03829433852311)
Se for uma matriz de tipo e for uma matriz de tipo , A ⊗ B é uma matriz de tipo . Novamente, essa multiplicação não é comutativa.
NO{\ displaystyle A}
(m,não){\ displaystyle (m, n)}
B{\ displaystyle B}
(p,r){\ displaystyle (p, r)}
(mp,nãor){\ displaystyle (mp, nr)}![(mp, nr)](https://wikimedia.org/api/rest_v1/media/math/render/svg/310c556aea073ccc663b4bfe785f51096c638544)
por exemplo
(1231)⊗(0321)=(1×01×32×02×31×21×12×22×13×03×31×01×33×23×11×21×1)=(0306214209036321){\ displaystyle {\ begin {pmatrix} 1 & 2 \\ 3 & 1 \\\ end {pmatrix}} \ otimes {\ begin {pmatrix} 0 & 3 \\ 2 & 1 \\\ end {pmatrix}} = {\ begin {pmatrix} 1 \ times 0 & 1 \ times 3 & 2 \ times 0 & 2 \ times 3 \\ 1 \ times 2 & 1 \ times 1 & 2 \ times 2 & 2 \ times 1 \\ 3 \ vezes 0 e 3 \ vezes 3 e 1 \ vezes 0 e 1 \ vezes 3 \\ 3 \ vezes 2 e 3 \ vezes 1 & 1 \ vezes 2 & 1 \ vezes 1 \\\ end {pmatrix}} = {\ begin {pmatrix} 0 & 3 & 0 & 6 \\ 2 & 1 & 4 & 2 \\ 0 & 9 & 0 & 3 \\ 6 & 3 & 2 & 1 \ end {pmatrix}}}![{\ begin {pmatrix} 1 & 2 \\ 3 & 1 \\\ end {pmatrix}} \ otimes {\ begin {pmatrix} 0 & 3 \\ 2 & 1 \\\ end {pmatrix}} = {\ begin {pmatriz} 1 \ vezes 0 e 1 \ vezes 3 e 2 \ vezes 0 e 2 \ vezes 3 \\ 1 \ vezes 2 e 1 \ vezes 1 e 2 \ vezes 2 e 2 \ vezes 1 \\ 3 \ vezes 0 & 3 \ vezes 3 & 1 \ vezes 0 & 1 \ vezes 3 \\ 3 \ vezes 2 & 3 \ vezes 1 & 1 \ vezes 2 & 1 \ vezes 1 \\\ end {pmatrix}} = {\ begin {pmatrix} 0 & 3 & 0 & 6 \\ 2 & 1 & 4 & 2 \\ 0 & 9 & 0 & 3 \\ 6 & 3 & 2 & 1 \ end {pmatrix}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4154a0b949d4b4b1f74eceab3c62941fd54ea717)
.
Se e são as matrizes dos mapas lineares V 1 → W 1 e V 2 → W 2 , respectivamente, então A ⊗ B representa o produto tensorial dos dois mapas , V 1 ⊗ V 2 → W 1 ⊗ W 2 .
NO{\ displaystyle A}
B{\ displaystyle B}![B](https://wikimedia.org/api/rest_v1/media/math/render/svg/47136aad860d145f75f3eed3022df827cee94d7a)
Propriedades comuns
As três multiplicações de matrizes anteriores são associativas
NO×(B×VS)=(NO×B)×VS{\ displaystyle A \ times (B \ times C) = (A \ times B) \ times C}![A \ vezes (B \ vezes C) = (A \ vezes B) \ vezes C](https://wikimedia.org/api/rest_v1/media/math/render/svg/5d99e08fa401b6f5835113dc2f3313a38f8088bb)
,
distributiva em relação à adição:
NO×(B+VS)=NO×B+NO×VS{\ displaystyle A \ times (B + C) = A \ times B + A \ times C}
(NO+B)×VS=NO×VS+B×VS{\ displaystyle (A + B) \ times C = A \ times C + B \ times C}
e compatível com a multiplicação por um escalar:
vs(NO×B)=(vsNO)×B=NO×(vsB){\ displaystyle c (A \ times B) = (cA) \ times B = A \ times (cB)}![c (A \ vezes B) = (cA) \ vezes B = A \ vezes (cB)](https://wikimedia.org/api/rest_v1/media/math/render/svg/82418ab20b35810ecaae0d66f437b06b505ce8c2)
Multiplicação por um escalar
A multiplicação escalar de uma matriz dá ao produto
r{\ displaystyle r}
NO=(noeuj){\ displaystyle A = (a_ {ij})}![A = (a _ {{ij}})](https://wikimedia.org/api/rest_v1/media/math/render/svg/296ad42d9541f8285979ce822ccb661da56111ca)
rNO=(rnoeuj){\ displaystyle rA = (ra_ {ij})}![rA = (ra _ {{ij}})](https://wikimedia.org/api/rest_v1/media/math/render/svg/7d3b2dda4f79509b215ad74b50f0dc2d69c2401a)
.
Se estivermos trabalhando com matrizes em um anel , a multiplicação por um escalar é às vezes chamada de multiplicação à esquerda, enquanto a multiplicação à direita é definida por:
NOr=(noeujr){\ displaystyle Ar = (a_ {ij} r)}![Ar = (a _ {{ij}} r)](https://wikimedia.org/api/rest_v1/media/math/render/svg/f2cea9cc38cb0ac15301efc965b9211f7d4a01ea)
.
Quando o anel fundamental é um anel comutativo , por exemplo, o campo de reais ou complexos, as duas multiplicações são idênticas.
No entanto, se o anel não for comutativo, como o dos quatérnios , eles podem ser diferentes. por exemplo
eu(eu00j)=(-100k)≠(-100-k)=(eu00j)eu{\ displaystyle i {\ begin {pmatrix} i & 0 \\ 0 & j \\\ end {pmatrix}} = {\ begin {pmatrix} -1 & 0 \\ 0 & k \\\ end {pmatrix}} \ neq {\ begin {pmatrix} -1 & 0 \\ 0 & -k \\\ end {pmatrix}} = {\ begin {pmatrix} i & 0 \\ 0 & j \\\ end {pmatrix}} i }![i {\ begin {pmatrix} i & 0 \\ 0 & j \\\ end {pmatrix}} = {\ begin {pmatrix} -1 & 0 \\ 0 & k \\\ end {pmatrix}} \ neq { \ begin {pmatrix} -1 & 0 \ \ 0 & -k \\\ end {pmatrix}} = {\ begin {pmatrix} i & 0 \\ 0 & j \\\ end {pmatrix}} i](https://wikimedia.org/api/rest_v1/media/math/render/svg/1615f011be4c6bf032f30ac50a9de707b47f75a5)
Aspectos algorítmicos
Multiplicação eficiente de duas matrizes
O problema que consiste, dadas duas matrizes quadradas, em multiplicá-las rapidamente, é um problema importante em algoritmos . O algoritmo que segue da definição tem uma complexidade de tempo em , onde é o número de linhas das matrizes. Um limite inferior é (porque cada um dos coeficientes da matriz deve ser escrito). O expoente ótimo para a complexidade está, portanto, entre 2 e 3, mas seu valor exato é um problema em aberto. Muitos algoritmos foram inventados para este problema, por exemplo, o algoritmo Strassen em , o primeiro a ser descoberto, e o algoritmo Coppersmith-Winograd em . Em 1993, Bahar et al. forneceu um algoritmo de multiplicação de matrizes para matrizes representadas simbolicamente usando uma estrutura de dados chamada Diagramas de Decisão Algébrica (ADD), que é uma generalização de diagramas de decisão binários .
O(não3){\ displaystyle O (n ^ {3})}
não{\ displaystyle n}
O(não2){\ displaystyle O (n ^ {2})}
não2{\ displaystyle n ^ {2}}
O(não2,807){\ displaystyle O (n ^ {2.807})}
O(não2,376) {\ displaystyle O (n ^ {2.376}) \! \}![{\ displaystyle O (n ^ {2.376}) \! \}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9d90936216dac22435d530ffe341ddd19b31a70f)
Multiplicações de matrizes encadeadas
Damos-nos uma série de matrizes retangulares e queremos calcular o produto (supomos que todas as matrizes têm um tamanho compatível, ou seja, o produto está bem definido). Sendo o produto da matriz associativo , qualquer parêntese do produto dará o mesmo resultado. No entanto, o número de multiplicações escalares a serem realizadas depende dos parênteses retidos se as matrizes forem de tamanhos diferentes.
⟨NO1...,NOk⟩{\ displaystyle \ langle A_ {1} \ dots, A_ {k} \ rangle}
NO1,não=NO1...NOk{\ displaystyle A_ {1, n} = A_ {1} \ dots A_ {k}}![{\ displaystyle A_ {1, n} = A_ {1} \ dots A_ {k}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/14bc943da62eb060b7b724652d41e3dd1bf49e55)
Portanto, se pegarmos , e
tivermos =, mas o cálculo de requer 6 multiplicações escalares, enquanto o de requer 18.
NO=(no1no2no3){\ displaystyle A = {\ begin {pmatrix} a_ {1} & a_ {2} & a_ {3} \\\ end {pmatrix}}}
B=(b1b2b3){\ displaystyle B = {\ begin {pmatrix} b_ {1} \\ b_ {2} \\ b_ {3} \\\ end {pmatrix}}}
VS=(vs1vs2vs3){\ displaystyle C = {\ begin {pmatrix} c_ {1} & c_ {2} & c_ {3} \\\ end {pmatrix}}}
(NOB)VS{\ displaystyle (AB) C}
NO(BVS){\ displaystyle A (BC)}
(NOB)VS{\ displaystyle (AB) C}
NO(BVS){\ displaystyle A (BC)}![{\ displaystyle A (BC)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1dcc92bb29718d480f29434fcee02fc38d19a176)
Portanto, pode ser útil executar um algoritmo de otimização de produto de matriz concatenada para identificar o parênteses mais eficiente antes de executar os produtos reais.
Verificação de um produto de matriz
Para verificar um produto de matriz, existem algoritmos mais eficientes do que apenas recalculá-lo.
Por exemplo, o algoritmo de Freivalds é um algoritmo probabilístico que permite verificar o resultado de um produto matricial com a menor probabilidade de erro desejada.
O(não2){\ displaystyle O (n ^ {2})}![O (n ^ 2)](https://wikimedia.org/api/rest_v1/media/math/render/svg/6cd9594a16cb898b8f2a2dff9227a385ec183392)
Notas e referências
-
Alain Connes , Triângulo de pensamentos , Odile Jacob Edition, p. 72 .
-
(en) Thomas H. Cormen , Charles E. Leiserson e Ronald L. Rivest , Introdução à Algoritmia , Paris, Dunod ,2002, xxix + 1146 pág. ( ISBN 978-2-10-003922-7 , SUDOC 068254024 ) , cap. 28 ("Cálculo da matriz").
-
Markus Bläser , “ Fast Matrix Multiplication ”, Theory of Computing, Graduate Surveys , vol. 5,2013, p. 1-60 ( ler online ).
-
R. Iris Bahar , Erica A. Frohm , Charles M. Gaona e Gary D. Hachtel , “ Diagramas de decisão algébrica e suas aplicações ”, ICCAD '93 Proceedings of the 1993 IEEE / ACM International Conference on Computer-aided design , IEEE Computer Society Press,7 de novembro de 1993, p. 188–191 ( ISBN 0818644907 , lido online , acessado em 9 de fevereiro de 2018 )
Veja também
Artigo relacionado
Adição de matriz
links externos
<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">