Méthodes directes pour les systèmes linéaires

Les méthodes directes résolvent un système linéaire Ax = b en un nombre fini d'étapes arithmétiques, généralement en factorisant la matrice puis en résolvant les systèmes triangulaires par substitution.

Definition

Une méthode directe est un algorithme qui calcule la solution exacte d'un système linéaire — à l'erreur d'arrondi près — en un nombre fini et prédéterminé d'opérations, par opposition à une méthode itérative qui produit une séquence d'approximations.

Scope

Ce sujet aborde l'élimination de Gauss, son expression sous forme de factorisation LU, le rôle du pivotement dans la maîtrise de la croissance des erreurs, la substitution avant et arrière pour les systèmes triangulaires, ainsi que le nombre d'opérations qui rendent les solveurs directs pratiques pour les matrices denses et à bande.

Core questions

• Comment l'élimination de Gauss réduit-elle un système à une forme triangulaire, et pourquoi cela équivaut-il à une factorisation LU ?
• Pourquoi le pivotement est-il nécessaire, et comment le pivotement partiel et complet contrôle-t-il la croissance de l'erreur d'arrondi ?
• Quel est le coût de calcul d'une résolution directe, et comment l'exploitation de la structure (symétrie, structure de bande, parcimonie) le réduit-elle ?
• Dans quelles conditions l'élimination de Gauss avec pivotement partiel est-elle stable en arrière en pratique ?

Key theories

Factorisation LU avec pivotement partiel

L'élimination de Gauss avec échanges de lignes factorise une matrice sous la forme PA = LU, où L est une matrice triangulaire inférieure unitaire et U est une matrice triangulaire supérieure ; le pivotement partiel borne les multiplicateurs et rend la méthode fiable pour presque toutes les matrices rencontrées en pratique.

Facteur de croissance et stabilité arrière

L'erreur arrière de l'élimination de Gauss est régie par le facteur de croissance des éléments pendant l'élimination ; bien qu'une croissance exponentielle soit possible dans des cas artificiels, le pivotement partiel maintient la croissance suffisamment faible pour que la méthode soit stable en arrière pour pratiquement tous les problèmes réels.

Mechanisms

L'élimination de Gauss procède colonne par colonne : à chaque étape, un pivot est sélectionné (le pivotement partiel choisit le candidat de plus grande magnitude dans la colonne courante), des multiples de la ligne du pivot sont soustraits des lignes inférieures pour introduire des zéros, et les multiplicateurs sont stockés pour former L. La matrice U triangulaire supérieure résultante est résolue par substitution arrière et le second membre est traité par substitution avant. Pour une matrice dense de taille n par n, la factorisation coûte environ deux tiers de n au cube opérations, tandis que chaque résolution triangulaire coûte de l'ordre de n au carré.

Clinical relevance

Les solveurs directs sont l'outil de prédilection chaque fois qu'un système dense ou à bande de taille modérée doit être résolu avec une précision totale — dans l'assemblage par éléments finis, la simulation de circuits, le contrôle, et comme résolution interne au sein de schémas numériques plus vastes — et qu'une seule factorisation peut être réutilisée pour résoudre de nombreux seconds membres à faible coût.

History

Les méthodes d'élimination remontent à Gauss et même avant, mais leur comportement en arithmétique à précision finie a été clarifié par l'analyse d'erreur arrière de Wilkinson dans les années 1960, qui a montré que le pivotement partiel maîtrise la croissance des erreurs et a expliqué la fiabilité empirique de la méthode observée depuis longtemps sur les premiers ordinateurs.

Key figures

• Carl Friedrich Gauss
• James H. Wilkinson
• Nicholas J. Higham

Seminal works

• trefethen1997
• golub2013
• higham2002

Frequently asked questions

Quand une méthode directe doit-elle être préférée à une méthode itérative ?

Les méthodes directes sont préférées lorsque la matrice est dense ou de taille modérée, lorsque de nombreux seconds membres partagent une même matrice (permettant la réutilisation d'une seule factorisation), ou lorsqu'une solution garantie finie et de pleine précision est requise. Les systèmes très grands et creux privilégient généralement les méthodes itératives.

Le pivotement garantit-il toujours une petite erreur ?

Le pivotement partiel garantit la stabilité arrière en pratique pour presque toutes les matrices, mais il ne résout pas le problème du mauvais conditionnement : si la matrice elle-même est presque singulière, même une résolution stable en arrière peut renvoyer une solution avec une grande erreur avant.