Matrice par blocs

Cet article ne cite pas suffisamment ses sources (juin 2014).

Si vous disposez d'ouvrages ou d'articles de référence ou si vous connaissez des sites web de qualité traitant du thème abordé ici, merci de compléter l'article en donnant les références utiles à sa vérifiabilité et en les liant à la section « Notes et références ».

En pratique : Quelles sources sont attendues ? Comment ajouter mes sources ?

On appelle matrice par blocs une matrice divisée en blocs à partir d'un groupement quelconque de termes contigus de sa diagonale. Chaque bloc étant indexé comme on indicerait les éléments d'une matrice, la somme et le produit de deux matrices partitionnées suivant les mêmes tailles de bloc, s'obtiennent avec les mêmes règles formelles que celles des composantes et en veillant à l'ordre des facteurs dans les produits matriciels. L'intérêt du partitionnement des matrices en bloc vient de ce que le produit d'un bloc par un bloc dont toutes les composantes sont nulles (sous-matrice nulle) est une matrice nulle. Le partitionnement des matrices permet de distribuer les calculs matriciels entre plusieurs processeurs travaillant concurremment : c'est l'un des principes de base du calcul parallèle.

En théorie des matrices, une matrice par blocs ou matrice partitionnée est une matrice divisée en sous-matrices rectangulaires à partir d'une division de sa diagonale : ces sous-matrices sont appelées blocs^[1]. On peut dire également que la matrice est écrite en termes de sous-matrices mises côte à côte. Une matrice par blocs doit se conformer à une manière cohérente de division des lignes et des colonnes :

• on groupe les lignes en « groupes » adjacents, et les colonnes de la même manière ;
• on convient que les blocs diagonaux sont des sous-matrices carrées.

La partition se fait dans les rectangles décrits par un groupe de lignes adjacentes croisant un groupe de colonnes adjacentes. En d'autres termes, la matrice est divisée par certaines des lignes horizontales et verticales la traversant.

La matrice

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

peut être partitionnée en quatre blocs

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

On peut alors écrire la matrice par bloc comme :

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

Sous certaines conditions d'homogénéité du partitionnement en blocs, un produit de matrices peut être effectué par blocs, c'est-à-dire en considérant seulement des opérations sur les sous-matrices^[1]. Étant donné une matrice A (m × p) avec q partitions de lignes et s de colonnes :

${\displaystyle \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}}}$

et une matrice B (p × n) avec s partitions de lignes et r partitions de colonnes :

${\displaystyle \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}}}$,

et à la condition que le nombre de colonnes de chaque bloc ${\displaystyle A_{ij}}$ soit égal au nombre de lignes du bloc ${\displaystyle B_{jk}}$, le produit matriciel :

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

peut être effectué par blocs, donnant C, matrice (m × n) avec q partitions de lignes et r partitions de colonnes. Les blocs sous-matrices de C sont calculés de la manière suivante^[2] :

${\displaystyle \mathbf {C} _{\alpha \beta }=\sum _{\gamma =1}^{s}\mathbf {A} _{\alpha \gamma }\mathbf {B} _{\gamma \beta },\quad \alpha =1,\ldots ,q,\quad \beta =1,\ldots ,r.}$

le produit de matrices n'est pas commutatif, donc l'ordre de facteurs ne changera pas.

Une matrice bloc-diagonale (ou diagonale par blocs) est une matrice carrée qui possède des blocs matrices carrées sur la diagonale principale, tels que les blocs non diagonaux soient des matrices nulles. Une matrice bloc-diagonale A est de forme :

${\displaystyle \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}}}$

où A_k est une matrice carrée ; en d'autres termes, c'est la somme directe de A₁, …, A_n. On peut aussi noter ceci : ${\displaystyle \mathbf {A} _{1}\oplus \mathbf {A} _{2}\oplus \,\ldots \,\oplus \mathbf {A} _{n}}$ ou diag(A₁, A₂,..., A_n), ce dernier étant une expression dans le même formalisme que celui d'une matrice diagonale. Toute matrice carrée peut être de manière triviale considérée comme une matrice bloc-diagonale avec un seul bloc.

Pour le déterminant et la trace, les expressions sont alors :

${\displaystyle \operatorname {det} (\mathbf {A} )=\operatorname {det} (\mathbf {A} _{1})\cdots \operatorname {det} (\mathbf {A} _{n})}$,

${\displaystyle \operatorname {trace} (\mathbf {A} )=\operatorname {trace} (\mathbf {A} _{1})+\cdots +\operatorname {trace} (\mathbf {A} _{n})}$.

La transposée sera donnée par:

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

Pour tout entier n, on a :

${\displaystyle {\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}}^{n}={\begin{pmatrix}\mathbf {A} _{1}^{n}&0&\cdots &0\\0&\mathbf {A} _{2}^{n}&\cdots &0\\\vdots &\vdots &\ddots &\vdots \\0&0&\cdots &\mathbf {A} _{n}^{n}\end{pmatrix}}}$

L'inverse d'une matrice diagonale par blocs est donc la matrice, diagonale par blocs, des inverses des blocs :

${\displaystyle {\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}}}$

Une matrice tridiagonale par bloc est une autre matrice par bloc spéciale, qui est comparable à la matrice diagonale par blocs, c'est-à-dire une matrice carrée ayant des matrices blocs carrées sur les diagonales principales, inférieure et supérieure, les autres blocs étant des matrices nulles. C'est une matrice tridiagonale essentiellement, mais qui possède des sous-matrices à la place des coefficients scalaires. Une matrice tridiagonale par bloc A a la forme :

${\displaystyle \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}}}$

où A_k, B_k et C_k sont des sous-matrices carrées sur les diagonales inférieure, principale et supérieure respectivement.

Les matrices tridiagonales par blocs sont parfois rencontrées dans les solutions numériques des problèmes d'ingénierie (ex. : en calcul de structures et en mécanique des fluides numérique). Les méthodes numériques optimisées pour une factorisation LU sont disponibles ainsi que des algorithmes de résolution de systèmes d'équations avec une matrice tridiagonale par bloc pour matrice de coefficients. L'algorithme de Thomas, utilisé pour obtenir une solution efficace des systèmes d'équations impliquant une matrice tridiagonale peut être aussi appliqué en utilisant des opérations matricielles aux matrices tridiagonales par blocs.^{[réf. nécessaire]}

Une matrice de Toeplitz par bloc est une autre matrice par bloc spéciale, contenant des blocs répétés le long des diagonales de la matrice, comme pour les coefficients d'une matrice de Toeplitz. Une matrice de Toeplitz par bloc A est de la forme :

${\displaystyle \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}}}$

Pour toutes matrices arbitraires A (de taille m × n) et B (de taille p × q), il existe une somme directe de A et B, notée ${\displaystyle \mathbf {A} \oplus \mathbf {B} }$ définie par :

${\displaystyle \mathbf {A} \oplus \mathbf {B} ={\begin{bmatrix}a_{11}&\cdots &a_{1n}&0&\cdots &0\\\vdots &\cdots &\vdots &\vdots &\cdots &\vdots \\a_{m1}&\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}}.}$

Par exemple,

${\displaystyle {\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}}.}$

Cette opération est généralisable naturellement à tous tableaux de dimensions arbitraires (pourvu que A et B aient le même nombre de dimensions).

Notons que tout élément dans la somme directe de deux espaces vectoriels matriciels peut être représentée comme une somme directe de matrices.

De manière similaire à la somme directe, il existe une opération appelée produit direct portant sur les matrices par blocs.

En algèbre linéaire, l'utilisation d'une matrice par bloc correspond à avoir une application linéaire pensée en termes de groupes correspondant à des vecteurs de base. Cela rejoint l'idée d'avoir des décompositions en sommes directes distinctes des ensembles de définitions de départ et d'arrivée. Cela est particulièrement significatif si un bloc est une matrice nulle ; ceci indique qu'un sous-ensemble est linéaire à une sous-somme. Étant donné cette interprétation par des applications linéaires et des sommes directes, il existe un genre spécial de matrice par bloc pour les matrices carrées (où m=n). Dans ce cas, on peut postuler une interprétation de ce type de matrice comme un endomorphisme d'un espace de dimension n V ; la structure par bloc dans lesquels les blocs sont disposés en lignes et colonnes est importante car elle correspond à obtenir une décomposition en somme directe simple (au lieu de deux) sur V. Dans ce cas, par exemple, les blocs diagonaux les plus évidents sont tous carrés. Ce type de structure est nécessaire pour la description de la réduction de Jordan.

Cette technique est utilisée pour alléger les calculs sur les matrices, les développements en colonnes et lignes, et autres applications en informatique, y compris la conception de puce d'intégration à très grande échelle. L'algorithme de Strassen pour des produits matriciels rapides, comme le code de Hamming (7,4) pour la détection d'erreur et la récupération de données dans les transmissions de données.

Elle est utilisée en sciences sociales en analyse des réseaux sociaux et en analyse de similitudes pour la détection des interactions corrélatives^[3].

Déterminant par blocs

Philippe Ciarlet, Introduction à l'analyse numérique matricielle et à l'optimisation, Masson, coll. « Mathématiques appliquées pour la maîtrise », 2001 (1^re éd. 1985) (ISBN 2-225-68893-1)

• Portail de l’algèbre