Matriu per blocs

De Viquipèdia
Dreceres ràpides: navegació, cerca

En matemàtiques, una matriu per blocs és una matriu que pot interpretar-se com a formada per seccions anomenades blocs o submatrius. [1] De forma intuïtiva, hom pot visualitzar una matriu per blocs com la matriu original amb una col·lecció de línies verticals i horitzontals que la divideixen, obtenint així una col·lecció de matrius més petites. [2] Tota matriu pot interpretar-se com a matriu per blocs d'una o més formes, on cada interpretació depèn de com es divideixen les files i les columnes. Aquesta noció es pot formular de manera més precisa per una matriu M de dimensió n per m tot particionant n en una col·lecció \text{grup de files}, i particionant m en una col·lecció \text{grup de columnes}. La matriu original llavors es considera com el "total" d'aquests grups, en el sentit que l'entrada (i,j) de la matriu original es correspon de forma biunívoca amb alguna entrada offset (s,t) d'alguns (x,y), on x \in \text{grup de files} i y \in \text{grup de columnes}.

Exemple[modifica | modifica el codi]

Una matriu quadrada per blocs 168x168, on els elements no-nuls estan simbolitzats per color blau, i els elements nuls pel color gris

La matriu

\mathbf{P} = \begin{bmatrix}
1 & 1 & 2 & 2\\
1 & 1 & 2 & 2\\
3 & 3 & 4 & 4\\
3 & 3 & 4 & 4\end{bmatrix}

es pot dividir en quatre blocs 2×2

\mathbf{P}_{11} = \begin{bmatrix}
1 & 1 \\
1 & 1 \end{bmatrix},   \mathbf{P}_{12} = \begin{bmatrix}
2 & 2\\
2 & 2\end{bmatrix},  \mathbf{P}_{21} = \begin{bmatrix}
3 & 3 \\
3 & 3 \end{bmatrix},   \mathbf{P}_{22} = \begin{bmatrix}
4 & 4\\
4 & 4\end{bmatrix}.

Llavors la matriu particionada es pot escriure com

\mathbf{P} = \begin{bmatrix}
\mathbf{P}_{11} & \mathbf{P}_{12}\\
\mathbf{P}_{21} & \mathbf{P}_{22}\end{bmatrix}.

Multiplicació de matrius per blocs[modifica | modifica el codi]

El producte d'una matriu per blocs pot ser descrit només en termes algebraics dels factors. Tot i això, la partició dels factors no és arbitrària, i requereix particions "compatibles" entre dues matrius A i B tals que tots els productes de les submatrius que s'utilitzin estiguin ben definits. [3] Aquestes particions compatibles són conegudes amb el nom de "particions conformes". [4] Donades una matriu \mathbf{A} de dimensió (m \times p) amb particions de files q i particions de columnes s


\mathbf{A} = \begin{bmatrix}
\mathbf{A}_{11} & \mathbf{A}_{12} & \cdots &\mathbf{A}_{1s}\\
\mathbf{A}_{21} & \mathbf{A}_{22} & \cdots &\mathbf{A}_{2s}\\
\vdots          & \vdots          & \ddots &\vdots \\
\mathbf{A}_{q1} & \mathbf{A}_{q2} & \cdots &\mathbf{A}_{qs}\end{bmatrix}

i una matriu \mathbf{B} de dimensió (p\times n) amb particions de files s i particions de columnes r


\mathbf{B} = \begin{bmatrix}
\mathbf{B}_{11} & \mathbf{B}_{12} & \cdots &\mathbf{B}_{1r}\\
\mathbf{B}_{21} & \mathbf{B}_{22} & \cdots &\mathbf{B}_{2r}\\
\vdots          & \vdots          & \ddots &\vdots \\
\mathbf{B}_{s1} & \mathbf{B}_{s2} & \cdots &\mathbf{B}_{sr}\end{bmatrix},

compatibles amb les particions d'A, llavors el producte matricial


\mathbf{C}=\mathbf{A}\mathbf{B}

es pot computar per blocs, obtenint \mathbf{C} com una matriu de dimensió (m\times n) amb particions de files q i particions de columnes r. Les (sub)matrius de la matriu \mathbf{C} es calculen multiplicant:


\mathbf{C}_{\alpha \beta} = \sum^s_{\gamma=1}\mathbf{A}_{\alpha \gamma}\mathbf{B}_{\gamma \beta}.

O bé, usant el conveni de sumació d'Einstein que suma de forma implícita sobre els índexs repetits:


\mathbf{C}_{\alpha \beta} = \mathbf{A}_{\alpha \gamma}\mathbf{B}_{\gamma \beta}.

Matrius diagonals per blocs [modifica | modifica el codi]

Una matriu diagonal per blocs és una matriu per blocs que és també una matriu quadrada, i que a la diagonal principal té matrius per blocs quadrades, de manera que els blocs de fora de la diagonal són matrius nul·les. Tota matriu diagonal per blocs A té la forma

 
\mathbf{A} = \begin{bmatrix} 
\mathbf{A}_{1} & 0 & \cdots & 0 \\ 0 & \mathbf{A}_{2} & \cdots &  0 \\
\vdots & \vdots & \ddots & \vdots \\
0 & 0 & \cdots & \mathbf{A}_{n} 
\end{bmatrix}

on Ak és una matriu quadrada; en altres paraules, és la suma directa de A1, …, An. També es pot escriure com A1 \oplus A2 \oplus\,\ldots\,\oplus  An  o també  diag(A1, A2,\ldots, An)  (aquesta última notació és similar a l'emprada per una matriu diagonal). Qualsevol matriu quadrada pot considerar-se com una matriu diagonal per blocs trivial, amb només un bloc.

Hom observa les següents propietats pel determinant i per la traça

 \operatorname{det} \mathbf{A} = \operatorname{det} \mathbf{A}_1 \times \ldots \times \operatorname{det} \mathbf{A}_n,
 \operatorname{tr} \mathbf{A} = \operatorname{tr} \mathbf{A}_1 +\cdots +\operatorname{tr} \mathbf{A}_n.

La inversa d'una matriu diagonal per blocs és una altra matriu diagonal per blocs, composta per l'invers de cada bloc, de la següent forma:

\begin{pmatrix}
\mathbf{A}_{1} & 0 & \cdots & 0 \\
0 & \mathbf{A}_{2} & \cdots &  0 \\
\vdots & \vdots & \ddots & \vdots \\
0 & 0 & \cdots & \mathbf{A}_{n} 
\end{pmatrix}^{-1} = \begin{pmatrix} \mathbf{A}_{1}^{-1} & 0 & \cdots & 0 \\
 0 & \mathbf{A}_{2}^{-1} & \cdots &  0 \\
\vdots & \vdots & \ddots & \vdots \\
0 & 0 & \cdots & \mathbf{A}_{n}^{-1} 
\end{pmatrix}.

Els valors propis i vectors propis d'A són simplement els d'A_{1} i A_{2} i ... i A_{n} (combinats).

Matrius tridiagonals per blocs[modifica | modifica el codi]

Una matriu tridiagonal per blocs és un tipus especial de matriu per blocs, que, de la mateixa manera que una matriu diagonal per blocs, és una matriu quadrada, i que té (sub)matrius quadrades (blocs) a la subdiagonal, a la diagonal principal i a la superdiagonal, i on tots els altres blocs són la matriu nul·la. És essencialment una matriu tridiagonal, però que té submatrius en comptes d'escalars. Una matriu tridiagonal A té la forma

 
\mathbf{A} = \begin{bmatrix}
\mathbf{B}_{1}  & \mathbf{C}_{1}  &         &         & \cdots  &         & 0 \\
\mathbf{A}_{2}  & \mathbf{B}_{2}  & \mathbf{C}_{2}   &         &         &         & \\
       & \ddots & \ddots  & \ddots  &         &         & \vdots \\
       &        & \mathbf{A}_{k}   & \mathbf{B}_{k}   & \mathbf{C}_{k}   &         & \\
\vdots &        &         & \ddots  & \ddots  & \ddots  & \\
       &        &         &         & \mathbf{A}_{n-1} & \mathbf{B}_{n-1} & \mathbf{C}_{n-1}   \\
0      &        & \cdots  &         &         & \mathbf{A}_{n}   & \mathbf{B}_{n}
\end{bmatrix}

on Ak, Bk i Ck són submatrius quadrades de la subdiagonal, la diagonal principal i la superdiagonal, respectivament.

Hom troba sovint la utilitat de les matrius tridiagonals per blocs a l'hora de trobar solucions numèriques en problemes d'enginyeria (per exemple, en la mecànica de fluids computacional). En aquest àmbit, existeixen métodes numèrics optimitzats per la descomposició LU, i per tant existeixen algorismes eficients per poder trobar les solucions de sistemes d'equacions on la matriu de coeficients és una matriu tridiagonal per blocs. L'algorisme de Thomas, que s'usa per resoldre sistemes d'equacions amb una matriu de coeficients tridiagonal, també és aplicable a matrius tridiagonals per blocs (vegeu també Descomposició LU per blocs).

Matrius per blocs de Toeplitz[modifica | modifica el codi]

Una matriu per blocs de Toeplitz és un altre tipus especial de matriu per blocs, on els blocs es repeteixen al llarg de les diagonals de la matriu, de la mateixa forma que succeeix amb una matriu de Toeplitz per elements escalars.

Una matriu per blocs de Toeplitz A té la forma

 
\mathbf{A} = \begin{bmatrix}
\mathbf{A}_{(1,1)}  & \mathbf{A}_{(1,2)}  &         &         & \cdots  &     \mathbf{A}_{(1,n-1)}    & \mathbf{A}_{(1,n)} \\
\mathbf{A}_{(2,1)}  & \mathbf{A}_{(1,1)}  & \mathbf{A}_{(1,2)}   &         &         &         & \mathbf{A}_{(1,n-1)} \\
       & \ddots & \ddots  & \ddots  &         &         & \vdots \\
       &        & \mathbf{A}_{(2,1)}   & \mathbf{A}_{(1,1)}   & \mathbf{A}_{(1,2)}   &         & \\
\vdots &        &         & \ddots  & \ddots  & \ddots  & \\
\mathbf{A}_{(n-1,1)}       &        &         &         & \mathbf{A}_{(2,1)} & \mathbf{A}_{(1,1)} & \mathbf{A}_{(1,2)}   \\
\mathbf{A}_{(n,1)}      & \mathbf{A}_{(n-1,1)}       & \cdots  &         &         & \mathbf{A}_{(2,1)}   & \mathbf{A}_{(1,1)}
\end{bmatrix}.

Suma directa[modifica | modifica el codi]

Per matrius qualssevol A (de dimensió m × n) i B (de dimensió p × q), tenim la suma directa d' A i B, denotada per A \oplus B, i definida com


  \mathbf{A} \oplus \mathbf{B} =
  \begin{bmatrix}
     a_{11} & \cdots & a_{1n} &      0 & \cdots &      0 \\
     \vdots & \cdots & \vdots & \vdots & \cdots & \vdots \\
    a_{m 1} & \cdots & a_{mn} &      0 & \cdots &      0 \\
          0 & \cdots &      0 & b_{11} & \cdots &  b_{1q} \\
     \vdots & \cdots & \vdots & \vdots & \cdots & \vdots \\
          0 & \cdots &      0 & b_{p1} & \cdots &  b_{pq} 
  \end{bmatrix}.

Per exemple,


  \begin{bmatrix}
    1 & 3 & 2 \\
    2 & 3 & 1
  \end{bmatrix}
\oplus
  \begin{bmatrix}
    1 & 6 \\
    0 & 1
  \end{bmatrix}
=
  \begin{bmatrix}
    1 & 3 & 2 & 0 & 0 \\
    2 & 3 & 1 & 0 & 0 \\
    0 & 0 & 0 & 1 & 6 \\
    0 & 0 & 0 & 0 & 1
  \end{bmatrix}.

Aquesta operació es generalitza de forma natural a matrius de dimensions arbitràries (en el supòsit que A i B tinguin el mateix nombre de dimensions).

Notem que qualsevol element d'una suma directa d'espais vectorials de matrius pot ser representat com una suma directa de dues matrius.

Producte directe[modifica | modifica el codi]

Article principal: Producte Kronecker

Aplicacions[modifica | modifica el codi]

En termes d'àlgebra lineal, l'ús d'una matriu per blocs correspon a la idea de tenir una aplicació lineal entre "grups" de vectors base. També es pot interpretar com tenir una descomposició en suma directa del domini i el recorregut. És particularment significatiu si un bloc és la matriu nul·la; això vol dir que un sumand es correspon (per l'aplicació lineal) en una "sub-suma".

Tenint en compte la interpretació via aplicacions lineals i sumes directes, hi ha un tipus especial de matrius per blocs: les que apareixen en matrius quadrades (és a dir, on m = n). En aquests casos, podem interpretar que tenim un endomorfisme d'un espai vectorial V de dimensió n; l'estructura en blocs on els "grups" de files i columnes són els mateixos és important, en el sentit que ens permet obtenir una descomposició en suma directa de V. En aquest cas, per exemple, els blocs diagonals són tots quadrats. Hom utilitza aquesta estructura per descriure la forma canònica de Jordan.

Es pot utilizar aquesta tècnica per optimitzar els càlculs sobre matrius, expansions fila-columna, i moltes aplicacions en computació, inclòs el disseny de xips VLSI. Un exemple n'és l'algorisme d'Strassen per la multiplicació ràpida de matrius, així com el Codi de Hamming (7,4) per la detecció i correcció d'errors en transmissions de dades.

Referències[modifica | modifica el codi]

  1. Eves, Howard. Elementary Matrix Theory. Reimpressió. New York: Dover, 1980, p. 37. ISBN 0-486-63946-0 [Consulta: 24 abril 2013]. «We shall find that it is sometimes convenient to subdivide a matrix into rectangular blocks of elements. This leads us to consider so-called partitioned, or block, matrices 
  2. Anton, Howard. Elementary Linear Algebra. 7a. edició. New York: John Wiley, 1994, p. 30. ISBN 0-471-58742-7. «A matrix can be subdivided or partitioned into smaller matrices by inserting horizontal and vertical rules between selected rows and columns.» 
  3. Anton, Howard. Elementary Linear Algebra. 7a. edició. New York: John Wiley, 1994, p. 36. ISBN 0-471-58742-7. «...provided the sizes of the submatrices of A and B are such that the indicated operations can be performed.» 
  4. Eves, Howard. Elementary Matrix Theory. reimpressió. New York: Dover, 1980, p. 37. ISBN 0-486-63946-0 [Consulta: 24 abril 2013]. «A partitioning as in Theorem 1.9.4 is called a conformable partition of A and B