Matrice bande

En mathématiques, une matrice bande ou une matrice à bande est une matrice creuse dont les coefficients non nuls sont restreints à une bande diagonale, comprenant la diagonale principale et éventuellement une ou plusieurs diagonales de chaque côté.

Matrice bande

Largeur de bande

Formellement, on considère une matrice carrée Modèle:Nobr Modèle:Math. Si tous les éléments de la matrice sont nuls en dehors d'une bande diagonale dont la plage est déterminée par les constantes k₁ et k₂ :

$a_{i,j}=0\text{si}j<i-k_1\text{ ou }j>i+k_2;k_1,k_2\ge 0.$

alors les quantités k ₁ et k ₂ sont appelées les largeurs de bande inférieure et largeur de bande supérieure respectivementModèle:Sfn. La largeur de bande de la matrice est le maximum de k₁ et k₂ ; autrement dit, c'est le nombre k tel que $a_{i,j}=0$ si $|i-j|>k$ Modèle:Sfn.

Exemples

• Une matrice bande avec Modèle:Nobr est une matrice diagonale
• Une matrice bande avec Modèle:Nobr est une matrice tridiagonale
• Pour Modèle:Nobr on a une matrice pentadiagonale et ainsi de suite.
• les Matrices triangulaires
  • Pour Modèle:Nobr, on obtient la définition d'une matrice triangulaire supérieure
  • de même, pour Modèle:Nobr on obtient une matrice triangulaire inférieure.
• les matrices de Hessenberg supérieure et inférieure
• les matrices de Toeplitz lorsque la bande passante est limitée.
• les matrices diagonales par blocs
• les matrices de déplacement et de cisaillement
• les matrices sous forme normale de Jordan
• Une matrice d'horizon, également appelée "matrice de bande variable" — une généralisation de la matrice bande
• Les inverses des matrices de Lehmer sont des matrices tridiagonales constantes, et sont donc des matrices bandes.

Applications

En analyse numérique, les matrices des problèmes d'éléments finis ou de différences finies sont souvent à bande. Ces matrices peuvent être considérées comme des descriptions du couplage entre les variables du problème ; le fait que la matrice soit une matrice bande correspond au fait que les variables ne sont pas couplées sur des distances arbitrairement grandes. De telles matrices peuvent être encore diviséesModèle:Spaced ndashpar exemple, il existe des matrices en bandes où chaque élément de la bande est différent de zéro. Ceux-ci surviennent souvent lors de la discrétisation de problèmes unidimensionnels.Modèle:Référence nécessaire

Les problèmes dans les dimensions supérieures conduisent également à des matrices bandes, auquel cas la bande elle-même a également tendance à être creuse. Par exemple, une équation aux dérivées partielles sur un domaine carré (utilisant des différences centrales) donnera une matrice avec une largeur de bande égale à la racine carrée de la dimension de la matrice, mais à l'intérieur de la bande, seules 5 diagonales sont non nulles. Malheureusement, l'application du pivot de Gauss (ou de manière équivalente une décomposition LU ou de Cholesky) à une telle matrice entraîne le remplissage de la bande par de nombreux éléments non nuls.

Stockage de bande

Les matrices bandes sont généralement stockées en stockant les diagonales dans la bande ; le reste est implicitement nul.

Par exemple, une matrice tridiagonale a une largeur de bande de 1. La matrice 6 par 6

$\left[\begin{array}{cccccc}{B}_{11}& B_{12}& 0& \cdots & \cdots & 0\\ B_{21}& B_{22}& B_{23}& \ddots & \ddots & ⋮\\ 0& B_{32}& B_{33}& B_{34}& \ddots & ⋮\\ ⋮& \ddots & B_{43}& B_{44}& B_{45}& 0\\ ⋮& \ddots & \ddots & B_{54}& B_{55}& B_{56}\\ 0& \cdots & \cdots & 0& B_{65}& B_{66}\end{array}\right]$

est stockée dans un matrice 6 par 3

$\left[\begin{array}{ccc}0& B_{11}& B_{12}\\ B_{21}& B_{22}& B_{23}\\ B_{32}& B_{33}& B_{34}\\ B_{43}& B_{44}& B_{45}\\ B_{54}& B_{55}& B_{56}\\ B_{65}& B_{66}& 0\end{array}\right].$

Une économie supplémentaire est possible lorsque la matrice est symétrique. Par exemple, on considère une matrice symétrique 6 par 6 avec une bande passante supérieure de 2 :

$\left[\begin{array}{cccccc}{A}_{11}& A_{12}& A_{13}& 0& \cdots & 0\\ & A_{22}& A_{23}& A_{24}& \ddots & ⋮\\ & & A_{33}& A_{34}& A_{35}& 0\\ & & & A_{44}& A_{45}& A_{46}\\ & \mathrm{s}\mathrm{y}\mathrm{m}& & & A_{55}& A_{56}\\ & & & & & A_{66}\end{array}\right].$

Cette matrice est stockée en tant que matrice 6 par 3 :

$\left[\begin{array}{ccc}{A}_{11}& A_{12}& A_{13}\\ A_{22}& A_{23}& A_{24}\\ A_{33}& A_{34}& A_{35}\\ A_{44}& A_{45}& A_{46}\\ A_{55}& A_{56}& 0\\ A_{66}& 0& 0\end{array}\right].$

Forme bandée des matrices creuses

D'un point de vue informatique, travailler avec des matrices bandes est toujours préférable à travailler avec des matrices carrées de même dimension. Une matrice bande peut être assimilée en complexité à une matrice rectangulaire dont le nombre de lignes est égale à la largeur de bande de la matrice bande. Ainsi, le travail nécessaire pour effectuer des opérations telles que la multiplication diminue considérablement, ce qui entraîne souvent d'énormes économies en termes de temps de calcul et de complexité.

Comme les matrices creuses se prêtent à un calcul plus efficace que les matrices denses, ainsi qu'à une utilisation plus efficace du stockage informatique, de nombreuses recherches se sont concentrées sur la recherche de moyens de minimiser la largeur de la bande (ou de minimiser directement le remplissage) en appliquant des permutations à la matrice, ou à d'autres transformations d'équivalence ou de similaritéModèle:Sfn.

L'Modèle:Lien peut être utilisé pour réduire la largeur de bande d'une matrice symétrique creuse. Il existe cependant des matrices pour lesquelles l'algorithme inverse de Cuthill-McKee fonctionne mieux. De nombreuses autres méthodes sont utilisées.

Le problème de trouver une représentation d'une matrice avec une bande minimale au moyen de permutations de lignes et de colonnes est NP-difficile Modèle:Sfn.

Références

• Modèle:Ouvrage.
• Modèle:Ouvrage.
• Modèle:Ouvrage.
• Modèle:Ouvrage.
• Modèle:Ouvrage.

Voir aussi

Articles connexes

• Matrice diagonale
• Matrice creuse
• Bande passante graphique

Liens externes

• Informations relatives à LAPACK et aux matrices de bandes
• Un tutoriel sur les matrices en bandes et autres formats de matrices creuses