Calculs par blocs

Plan du chapitre "Calcul matriciel"

Décompositions en blocs

{\vartriangleright} Commençons par quelques exemples

La matrice {A=\begin{pmatrix}2&5&3&1&6&7\\4&1&5&6&8&9\\ 1&0&4&5&1&3\\ 7&9&6&2&1&5 \\ 1&5&8&2&7&4\end{pmatrix}} est “décomposable en blocs” de plusieurs manières.

Par exemple : {\begin{array}{l}A=\left(\begin{array}{ccc|ccc}2&5&3&1&6&7\\4&1&5&6&8&9\\\text{---}&\text{---}&\text{---}&\text{---}&\text{---}&\text{---}\\1&0&4&5&1&3\\ 7&9&6&2&1&5 \\ 1&5&8&2&7&4\end{array}\right)=\begin{pmatrix}M&N\\ P&Q \end{pmatrix}\\\\\text{où\ }M=\begin{pmatrix}2&5&3\\4&1&5 \end{pmatrix},\;N=\begin{pmatrix}1&6&7\\6&8&9 \end{pmatrix},\;P=\begin{pmatrix}1&0&4\\7&9&6\\1&5&8 \end{pmatrix},\;Q=\begin{pmatrix}5&1&3\\2&1&5\\2&7&4 \end{pmatrix}\end{array}}
On pourrait aussi décomposer en {A=\left(\begin{array}{cccc|cc}2&5&3&1&6&7\\4&1&5&6&8&9\\ 1&0&4&5&1&3\\\text{---}&\text{---}&\text{---}&\text{---}&\text{---}&\text{---}\\ 7&9&6&2&1&5 \\ 1&5&8&2&7&4\end{array}\right)}

Autre possibilité : {A=\left(\begin{array}{cc|ccc|c}2&5&3&1&6&7\\4&1&5&6&8&9\\\text{---}&\text{---}&\text{---}&\text{---}&\text{---}&\text{---}\\ 1&0&4&5&1&3\\ 7&9&6&2&1&5\\\text{---}&\text{---}&\text{---}&\text{---}&\text{---}&\text{---} \\ 1&5&8&2&7&4\end{array}\right)}

{\vartriangleright} Décompositions en blocs avec Python

On reprend la matrice initiale {A}, et on forme les matrices {M,P,N,Q} comme indiqué ci-dessus.

Rappelons le principe du “slicing” qui dit que l’expression A[a:b;c:d] renvoie le bloc formé des lignes dont l’indice est dans {[a,b[} et des colonnes dont l’indice est dans {[c,d[}.

Dans cette syntaxe, le premier indice vaut {0} par défaut, et le deuxième vaut {+\infty} par défaut.

>>> A
array([[2, 5, 3, 1, 6, 7],
[4, 1, 5, 6, 8, 9],
[1, 0, 4, 5, 1, 3],
[7, 9, 6, 2, 1, 5],
[1, 5, 8, 2, 7, 4]])
>>> M = A[:2,:3]; M
array([[2, 5, 3],
[4, 1, 5]])
>>> P = A[2:,:3]; P
array([[1, 0, 4],
[7, 9, 6],
[1, 5, 8]])
>>> N = A[:2,3:]; N
array([[1, 6, 7],
[6, 8, 9]])
>>> Q = A[2:,3:]; Q
array([[5, 1, 3],
[2, 1, 5],
[2, 7, 4]])

Voici ensuite deux façons de reconstituer {A} à partir des blocs {M,N,P,Q} :

>>> np.bmat([[M,N],[P,Q]])
matrix([[2, 5, 3, 1, 6, 7],
[4, 1, 5, 6, 8, 9],
[1, 0, 4, 5, 1, 3],
[7, 9, 6, 2, 1, 5],
[1, 5, 8, 2, 7, 4]])
>>> np.bmat(‘M N; P Q’)
matrix([[2, 5, 3, 1, 6, 7],
[4, 1, 5, 6, 8, 9],
[1, 0, 4, 5, 1, 3],
[7, 9, 6, 2, 1, 5],
[1, 5, 8, 2, 7, 4]])

Attention : les résultats sont au format “matrix”, une sous-classe de “array”. Il y a quelques différences de syntaxe (notamment pour le produit matriciel), et il est préférable de s’en tenir au format array.
On pouvait par exemple écrire : np.asarray(np.bmat('M N; P Q'))

{\vartriangleright} Forme générale d’une décomposition en blocs

Plus généralement, soit {A} une matrice quelconque de {\mathcal{M}_{n,p}(\mathbb{K})}. On peut écrire :{A=\left(\begin{array}{c|c|c|c|c|c}\;A_{11}&A_{12}&\ldots&A_{1k}&\ldots&A_{1q}\cr \vdots&\vdots& &\vdots& &\vdots\cr \;A_{i1}&A_{i2}&\ldots&A_{ik}&\ldots&A_{iq}\cr\vdots&\vdots& &\vdots& &\vdots\cr \;A_{m{}1}&A_{m{}2}&\ldots&A_{mk}&\ldots&A_{mq}\end{array}\right)} où les {A_{i,j}} sont elles-mêmes des matrices.

On a ainsi décomposé {A} en {mq} blocs.

La contrainte est que chaque bloc {A_{i,j}} soit de taille {(n_{i},p_{j})}, avec {\displaystyle\sum_{i=1}^{m}n_{j}=n}, et {\displaystyle\sum_{j=1}^{q}p_{j}=p}.
Certaines décompositions par blocs reviennent plus souvent que d’autres.
Une matrice {A} peut par exemple être décomposée en quatre blocs : {A=\begin{pmatrix}M&N\\ P&Q \end{pmatrix}}

{\vartriangleright} Décompositions en lignes ou en colonnes

Soit {A} dans {\mathcal{M}_{n,p}(\mathbb{K})}. Notons {\text{C}_{1},\text{C}_{2},\ldots,\text{C}_{p}} ses colonnes, et {\text{L}_{1},\text{L}_{2},\ldots,\text{L}_{n}} ses lignes.
Les écritures {A=\left(\begin{array}{c}\text{L}_1\\\text{L}_2\\\vdots\\\text{L}_{n}\end{array}\right)=\left(\begin{array}{c|c|c|c}\text{C}_{1}&\text{C}_{2}&\cdots&\text{C}_{p}\end{array}\right)} sont des décompositions particulières de {A}.

{\vartriangleright} Matrices diagonales ou triangulaires (supérieure) par blocs

Désignons par {D_{1},D_{2},\ldots,D_{m}} une succession de {m} matrices carrées (pas nécessairement de même taille, certaines d’entre elles pouvant même être réduites à un seul scalaire).

On note également {\ast} des blocs matriciels quelconques.

Notons {A=\begin{pmatrix}D_{1}&0&\cdots&0\\ 0&D_{2}&\ddots&\vdots\\\vdots&\ddots&\ddots&0\\0&\cdots&0&D_{m}\end{pmatrix}} et {B=\begin{pmatrix}D_{1}&\ast&\cdots&\ast\\ 0&D_{2}&\ddots&\vdots\\\vdots&\ddots&\ddots&\ast\\0&\cdots&0&D_{m}\end{pmatrix}}.

On dit que {A} est “diagonale par blocs” et {B} est “triangulaire par blocs”.

Opérations sur les décompositions en blocs

{\vartriangleright} Addition par blocs

Soit {A,B} dans {\mathcal{M}_{n,p}(\mathbb{K})}, décomposées en blocs : {A=\begin{pmatrix}M&N\\ P&Q\end{pmatrix}} et {B=\begin{pmatrix}M'&N'\\ P'&Q' \end{pmatrix}}

On demande ici que ces deux décompositions soient “compatibles pour la somme”, c’est-à-dire que {M} et {M'} aient le même format (il en est alors de même pour {N} et {N'}, pour {P} et {P'}, pour {Q} et {Q'}).

Si ces conditions sont réunies, alors {\lambda A+\mu B=\begin{pmatrix}\lambda M+\mu M'&\lambda N+\mu N'\\ \lambda P+\mu P'&\lambda Q+\mu Q' \end{pmatrix}}.

Cette propriété se généralise à des décompositions en blocs quelconques, sous réserve bien sûr que les blocs qui se correspondent aient exactement la même taille.

{\vartriangleright} Produit par blocs

Soit {A\in\mathcal{M}_{n,p}(\mathbb{K})}, {B\in\mathcal{M}_{p,q}(\mathbb{K})}, décomposées en blocs : {A=\begin{pmatrix}M&N\\ P&Q\end{pmatrix}} et {B=\begin{pmatrix}M'&N'\\ P'&Q' \end{pmatrix}}

On souhaite effectuer le produit {AB} en exploitant cette décomposition.

On voudrait en fait pouvoir écrire : {AB=\begin{pmatrix}M&N\\ P&Q\end{pmatrix}\begin{pmatrix}M'&N'\\ P'&Q' \end{pmatrix}=\begin{pmatrix}MM'+NP'&MN'+NQ'\\ PM'+QP'&PN'+QQ' \end{pmatrix}}

Pour cela, il faut déjà pouvoir effectuer le produit {MM'} des blocs {M} et {M'}.

Supposons par exemple que {M} soit de type {(m,r)}, avec {\begin{cases}1\le m\le n\\ 1\le r\le p\end{cases}}

Supposons également que {M'} soit de type {(r,s)}, avec {\begin{cases}1\le r\le p\\ 1\le s\le q\end{cases}}

Avec ces hypothèses (qui permettent effectivement de calculer {MM'}) :

  • on a {\begin{cases}M\in\mathcal{M}_{m,r}(\mathbb{K})\\M'\in\mathcal{M}_{r,s}(\mathbb{K})\end{cases}\;\text{et}\;\begin{cases}N\in\mathcal{M}_{m,p-r}(\mathbb{K})\\P'\in\mathcal{M}_{p-r,s}(\mathbb{K})\end{cases}} donc {MM'+NP'\in\mathcal{M}_{m,s}(\mathbb{K})}.
  • on a {\begin{cases}M\in\mathcal{M}_{m,r}(\mathbb{K})\\N'\in\mathcal{M}_{r,q-s}(\mathbb{K})\end{cases}\begin{cases}N\in\mathcal{M}_{m,p-r}(\mathbb{K})\\Q'\in\mathcal{M}_{p-r,q-s}(\mathbb{K})\end{cases}} donc {MN'+NQ'\in\mathcal{M}_{m,q-s}(\mathbb{K})}.
  • on a {\begin{cases}P\in\mathcal{M}_{n-m,r}(\mathbb{K})\\M'\in\mathcal{M}_{r,s}(\mathbb{K})\end{cases}\begin{cases}Q\in\mathcal{M}_{n-m,p-r}(\mathbb{K})\\P'\in\mathcal{M}_{p-r,s}(\mathbb{K})\end{cases}} donc {PM'+QP'\in\mathcal{M}_{n-m,s}(\mathbb{K})}.
  • on a {\begin{cases}P\in\mathcal{M}_{n-m,r}(\mathbb{K})\\N'\in\mathcal{M}_{r,q-s}(\mathbb{K})\end{cases}\begin{cases}Q\in\mathcal{M}_{n-m,p-r}(\mathbb{K})\\Q'\in\mathcal{M}_{p-r,q-s}(\mathbb{K})\end{cases}} donc {PN'+QQ'\in\mathcal{M}_{n-m,q-s}(\mathbb{K})}.

On vérifie alors qu’effectivement : {AB=\begin{pmatrix}M&N\\ P&Q\end{pmatrix}\begin{pmatrix}M'&N'\\ P'&Q' \end{pmatrix}=\begin{pmatrix}MM'+NP'&MN'+NQ'\\ PM'+QP'&PN'+QQ' \end{pmatrix}}

Cette propriété se généralise à des décompositions en un nombre quelconque de blocs, sous réserve que tous les produits de blocs qui sont nécessaires à la construction du résultat soient possibles :

Proposition (théorème du produit par blocs)
Soit {A} dans {{\mathcal M}_{n,p}(\mathbb{K})}, et {B} dans {{\mathcal M}_{p,q}(\mathbb{K})}.
On suppose que {A} et {B} sont décomposées en blocs : {A=(A_{i,k})_{1\le i\le r\atop 1\le k\le s}} et {B=(B_{k,j})_{1\le k\le s\atop 1\le j\le t}}.
Alors {M=AB} se décompose en blocs {M=(M_{i,j})_{1\le i\le r\atop 1\le j\le t}}, avec : {\forall\, i\in\{1,\ldots,r\},\;\forall\, j\in\{1,\ldots,t\},\;M_{ij}=\displaystyle\sum_{k=1}^sA_{ik}\,B_{kj}}

{\vartriangleright} Cas des matrices triangulaires par blocs

Soit {A} et {B} deux matrices carrées, triangulaires par blocs.

On les écrit {A=\begin{pmatrix}D_{1}&\ast&\cdots&\ast\\ 0&D_{2}&\ddots&\vdots\\\vdots&\ddots&\ddots&\ast\\0&\cdots&0&D_{m}\end{pmatrix}} et {B=\begin{pmatrix}\Delta_{1}&\ast&\cdots&\ast\\ 0&\Delta_{2}&\ddots&\vdots\\\vdots&\ddots&\ddots&\ast\\0&\cdots&0&\Delta_{m}\end{pmatrix}}

On suppose ici que {D_{i}} et {\Delta_{i}} ont la même taille. Les blocs marqués {\ast} sont sans importance.

Avec ces notations, on montre que : {AB=\begin{pmatrix}D_{1}\Delta_{1}&\ast&\cdots&\ast\\ 0&D_{2}\Delta_{2}&\ddots&\vdots\\\vdots&\ddots&\ddots&\ast\\0&\cdots&0&D_{m}\Delta_{m}\end{pmatrix}}.

De même : {A^{p}=\begin{pmatrix}D_{1}^{p}&\ast&\cdots&\ast\\ 0&D_{2}^{p}&\ddots&\vdots\\\vdots&\ddots&\ddots&\ast\\0&\cdots&0&D_{m}^{p}\end{pmatrix}} et {A^{-1}=\begin{pmatrix}D_{1}^{-1}&\ast&\cdots&\ast\\ 0&D_{2}^{-1}&\ddots&\vdots\\\vdots&\ddots&\ddots&\ast\\0&\cdots&0&D_{m}^{-1}\end{pmatrix}}

La dernière égalité doit être précisée : elle exprime que {A} est inversible si et seulement si chacun des blocs diagonaux {D_{i}} est inversible. L’inverse de {A} est alors triangulaire par blocs, les blocs diagonaux de {A^{-1}} étant, respectivement, les inverses des blocs diagonaux de {A}.

Page précédente : transposition
Retour au début : espaces de matrices