Voir la source de 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 {{nobr|''n'' &#xD7; ''n''}} {{math|''A'' {{=}}(''a''<sub>''i'',''j''</sub>)}}. 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''<sub>1</sub> et ''k''<sub>2</sub> :

: <math>a_{i,j}=0 \quad\mbox{si}\quad j<i-k_1 \quad\mbox{ ou }\quad j>i+k_2; \quad k_1, k_2 \ge 0.\,</math>

alors les quantités ''k'' <sub>1</sub> et ''k'' <sub>2</sub> sont appelées les''' largeurs de bande inférieure''' et '''largeur de bande supérieure''' respectivement{{Sfn|Golub|Van Loan|1996|loc=§1.2.1}}. La largeur de bande de la matrice est le maximum de ''k''<sub>1</sub> et ''k''<sub>2</sub> ; autrement dit, c'est le nombre ''k'' tel que <math> a_{i,j}=0 </math> si <math> |i-j| > k </math> {{Sfn|Atkinson|1989|p=527}}.

== Exemples ==

* Une matrice bande avec {{nobr|''k''<sub>1</sub> {{=}} ''k''<sub>2</sub> {{=}} 0}} est une [[matrice diagonale]]
* Une matrice bande avec {{nobr|''k''<sub>1</sub> {{=}} ''k''<sub>2</sub> {{=}} 1}} est une [[matrice tridiagonale]]
* Pour {{nobr|''k''<sub>1</sub> {{=}} ''k''<sub>2</sub> {{=}} 2}} on a une matrice pentadiagonale et ainsi de suite.
* les [[Matrice triangulaire|Matrices triangulaires]]
** Pour {{nobr|''k''<sub>1</sub> {{=}} 0, ''k''<sub>2</sub> {{=}} ''n'' &#x2212; 1}}, on obtient la définition d'une [[matrice triangulaire]] supérieure
** de même, pour  {{nobr|''k''<sub>1</sub> {{=}} ''n'' &#x2212; 1, ''k''<sub>2</sub> {{=}} 0}} on obtient une matrice triangulaire inférieure.
* les [[Matrice de Hessenberg|matrices de Hessenberg]] supérieure et inférieure
* les [[Matrice de Toeplitz|matrices de Toeplitz]] lorsque la bande passante est limitée.
* les [[Matrice par blocs|matrices diagonales par blocs]]
* les matrices de déplacement et de cisaillement
* les matrices sous [[Réduction de Jordan|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 [[Matrice de Lehmer|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'[[Méthode des éléments finis|éléments finis]] ou de [[Différence finie|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ées{{Spaced ndash}}par 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.{{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 [[Factorisation de Cholesky|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
: <math>
\begin{bmatrix}
 B_{11} & B_{12} & 0   & \cdots & \cdots & 0 \\
 B_{21} & B_{22} & B_{23} & \ddots & \ddots & \vdots \\
 0   & B_{32} & B_{33} & B_{34} & \ddots & \vdots \\
 \vdots & \ddots & B_{43} & B_{44} & B_{45} & 0 \\
 \vdots & \ddots & \ddots & B_{54} & B_{55} & B_{56} \\
 0   & \cdots & \cdots & 0   & B_{65} & B_{66}
\end{bmatrix}
</math>

est stockée dans un matrice 6 par 3
: <math>
\begin{bmatrix}
 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{bmatrix}.
</math>

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 :
: <math>
\begin{bmatrix}
 A_{11} & A_{12} & A_{13} &  0 & \cdots & 0 \\
   & A_{22} & A_{23} & A_{24} & \ddots & \vdots \\
   &    & A_{33} & A_{34} & A_{35} & 0 \\
   &    &    & A_{44} & A_{45} & A_{46} \\
   & \mathrm{sym}  &    &    & A_{55} & A_{56} \\
   &    &    &    &    & A_{66}
\end{bmatrix}.
</math>

Cette matrice est stockée en tant que matrice 6 par 3 :
: <math>
\begin{bmatrix}
 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{bmatrix}.
</math>

== 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 [[Matrice carrée|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 [[Théorie de la complexité (informatique théorique)|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é{{Sfn|Davis|2006|loc=§7.7}}.

L'{{Lien|trad=Cuthill–McKee algorithm|algorithme de Cuthill-McKee}} 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]] {{Sfn|Feige|2000}}.

== Notes ==
{{Traduction/Référence|en|Band matrix|1027621404}}
{{références}}

== Références ==
* {{ouvrage |lang=en | auteur1= Kendall E. Atkinson | titre = An Introduction to Numerical Analysis | année= 1989 | éditeur = John Wiley & Sons | isbn = 0-471-62489-6 }}.
* {{ouvrage |lang=en | auteur1= Timothy A. Davis | titre = Direct Methods for Sparse Linear Systems | année= 2006 | éditeur = Society for Industrial and Applied Mathematics | isbn = 978-0-898716-13-9 }}.
* {{ouvrage |lang=en | auteur1= Uriel Feige | contribution = Coping with the NP-Hardness of the Graph Bandwidth Problem | titre = Algorithm Theory - SWAT 2000 | series = Lecture Notes in Computer Science | volume = 1851 | année= 2000 | pp = 129–145 | doi = 10.1007/3-540-44985-X_2 }}.
* {{ouvrage |lang=en | auteur1=Gene H. Golub |auteur2=Charles F. Van Loan | année=1996 | titre=Matrix Computations | édition=3 | éditeur=Johns Hopkins | lieu=Baltimore | isbn=978-0-8018-5414-9 }}.
* {{ouvrage |lang=en |auteur1=WH Press |auteur2=SA Teukolsky |auteur3=WT Vetterling |auteur4=BP Flannery |année=2007 |titre=Numerical Recipes: The Art of Scientific Computing |édition=3 |éditeur=Cambridge University Press |lieu=New York |isbn=978-0-521-88068-8 |chapitre=Section 2.4 |lire en ligne=http://apps.nrbook.com/empanel/index.html?pg=56}}.

== Voir aussi ==
=== Articles connexes ===
* [[Matrice diagonale]]
* [[Matrice creuse]]
* Bande passante graphique

=== Liens externes ===
* [http://www.netlib.org/lapack/lug/node124.html Informations relatives à LAPACK et aux matrices de bandes]
* [http://www.netlib.org/linalg/html_templates/node89.html#SECTION00930000000000000000 Un tutoriel sur les matrices en bandes et autres formats de matrices creuses]

{{Portail|algèbre}}

[[Catégorie:Matrice remarquable]]
[[Catégorie:Pages avec des traductions non relues]]