Algèbre linéaire numérique
L'algèbre linéaire numérique développe des algorithmes pour la résolution de systèmes linéaires, de problèmes de moindres carrés et de problèmes de valeurs propres sur ordinateur, en accordant une attention explicite à la précision, à la stabilité et au coût en arithmétique à précision finie.
Definition
L'algèbre linéaire numérique est l'étude des algorithmes permettant d'effectuer des calculs d'algèbre linéaire — principalement la résolution de systèmes linéaires et de problèmes de valeurs propres/valeurs singulières — ainsi que l'analyse de leur précision, de leur stabilité et de leur efficacité en arithmétique à précision finie.
Scope
Ce domaine couvre le cœur computationnel qui sous-tend la plupart du calcul scientifique : la résolution de Ax = b, le calcul de factorisations matricielles (LU, QR, Cholesky, SVD), la recherche de valeurs propres et de valeurs singulières, et l'analyse de la manière dont l'erreur d'arrondi et le conditionnement du problème affectent le résultat calculé. Il englobe à la fois les matrices denses et structurées et traite le comportement en virgule flottante des algorithmes comme une préoccupation de premier ordre.
Sub-topics
Core questions
- Comment un système linéaire Ax = b peut-il être résolu avec précision et efficacité, et quand la réponse est-elle fiable ?
- Quelles factorisations matricielles révèlent la structure nécessaire à la résolution de problèmes, de moindres carrés et de valeurs propres ?
- Comment le conditionnement du problème et la stabilité de l'algorithme déterminent-ils conjointement l'erreur en arithmétique à précision finie ?
- Comment les valeurs propres et les valeurs singulières peuvent-elles être calculées sans former de quantités intermédiaires mal conditionnées ?
Key theories
- Analyse d'erreur rétrograde (backward error analysis)
- Une solution calculée est interprétée comme la solution exacte d'un problème légèrement perturbé ; un algorithme est stable au sens rétrograde (backward stable) si cette perturbation est de l'ordre de l'erreur d'arrondi unitaire, ce qui sépare la stabilité de l'algorithme du conditionnement du problème.
- Conditionnement et nombre de conditionnement
- La sensibilité d'un problème d'algèbre linéaire aux perturbations est quantifiée par un nombre de conditionnement ; pour les systèmes linéaires, l'erreur relative est bornée par le nombre de conditionnement de la matrice multiplié par la perturbation relative, indépendamment de l'algorithme utilisé.
- Paradigme de la factorisation matricielle
- La plupart des algorithmes réduisent un problème à un produit de facteurs plus simples (triangulaires, orthogonaux, diagonaux) ; LU, QR, Cholesky et la SVD (décomposition en valeurs singulières) fournissent des factorisations canoniques à partir desquelles les solutions, les ajustements par moindres carrés et les spectres sont déduits.
Clinical relevance
L'algèbre linéaire numérique constitue le substrat computationnel de pratiquement toutes les disciplines quantitatives : les équations différentielles discrétisées, l'optimisation, les statistiques et la régression, l'apprentissage automatique (machine learning), le traitement du signal et de l'image, ainsi que l'analyse de réseaux se réduisent tous à de grands systèmes linéaires, des problèmes de moindres carrés ou des calculs de valeurs propres dont la fiabilité dépend d'algorithmes matriciels stables.
History
Le domaine a été façonné au milieu du XXe siècle par l'avènement des ordinateurs numériques et par l'analyse d'erreur rétrograde (backward error analysis) de James H. Wilkinson, qui a expliqué pourquoi l'élimination de Gauss avec pivotement est fiable. Les décennies suivantes ont vu l'émergence de l'algorithme QR pour les valeurs propres, l'étude systématique de la décomposition en valeurs singulières, et le développement de bibliothèques de haute qualité (LINPACK, LAPACK) qui ont codifié des algorithmes stables pour un usage général.
Key figures
- James H. Wilkinson
- Gene H. Golub
- Lloyd N. Trefethen
- Nicholas J. Higham
Related topics
Seminal works
- trefethen1997
- golub2013
- higham2002
Frequently asked questions
- Quelle est la différence entre le conditionnement et la stabilité ?
- Le conditionnement est une propriété du problème — dans quelle mesure la solution exacte change sous l'effet de perturbations des données — tandis que la stabilité est une propriété de l'algorithme — quelle quantité d'erreur supplémentaire il introduit en arithmétique à précision finie. Un algorithme stable appliqué à un problème mal conditionné peut néanmoins produire une erreur importante.
- Pourquoi les transformations orthogonales sont-elles préférées en algèbre linéaire numérique ?
- Les transformations orthogonales (et unitaires) préservent la norme 2 et n'amplifient pas les erreurs d'arrondi ; par conséquent, les factorisations construites à partir de celles-ci — telles que la décomposition QR via les réflexions de Householder — tendent à être stables au sens rétrograde (backward stable).