Systèmes linéaires
Progression
#title: "Systèmes linéaires" description: "Résolution par le pivot de Gauss"
#Systèmes linéaires
La résolution de systèmes d'équations linéaires est l'un des problèmes les plus fondamentaux en mathématiques appliquées et en informatique. Des applications aussi diverses que la simulation physique, l'apprentissage automatique, l'optimisation économique ou le rendu 3D font appel quotidiennement à des solveurs de systèmes linéaires. L'algorithme du pivot de Gauss fournit une méthode systématique, élégante et efficace pour résoudre ces systèmes.
#Définitions et écriture matricielle
#Système linéaire
Un système linéaire de équations à inconnues s'écrit sous la forme :
Les coefficients sont les coefficients du système et les constituent le second membre.
#Écriture matricielle
Ce système se réécrit de manière compacte sous forme matricielle , où :
- est la matrice des coefficients (de taille )
- est le vecteur des inconnues
- est le vecteur second membre
#Structure des solutions
L'ensemble des solutions d'un système linéaire possède une structure géométrique remarquable.
#Système homogène ()
Lorsque le second membre est nul, l'ensemble des solutions forme un sous-espace vectoriel de . Ce sous-espace est précisément le noyau de la matrice :
Ce sous-espace contient toujours au moins le vecteur nul .
#Système avec second membre
S'il existe une solution particulière (c'est-à-dire un vecteur tel que ), alors l'ensemble complet des solutions est un espace affine :
Cette formule exprime une idée fondamentale :
Solution générale = Solution particulière + Solution homogène
Si le système n'a pas de solution particulière, on dit qu'il est incompatible (ensemble des solutions vide).
#Algorithme du pivot de Gauss
L'algorithme de Gauss transforme le système en un système échelonné (triangulaire) équivalent, beaucoup plus simple à résoudre. L'idée est d'éliminer progressivement les inconnues dans les équations successives.
#Opérations élémentaires
Les trois opérations suivantes transforment un système en un système équivalent (même ensemble de solutions) :
- Échange de lignes :
- Dilatation : avec
- Transvection : avec
Ces opérations correspondent à des multiplications matricielles par des matrices inversibles.
#Méthode détaillée
Phase de descente (élimination)
L'objectif est de mettre la matrice sous forme échelonnée :
┌ * * * * ┐ ┌ * * * * ┐ │ * * * * │ → │ 0 * * * │ │ * * * * │ │ 0 0 * * │ └ * * * * ┘ └ 0 0 0 * ┘
Les zéros sous la diagonale permettent une résolution directe.
#Exemple complet
Résolvons le système suivant :
Matrice augmentée initiale
Le pivot est non nul. On peut l'utiliser.
#Rang et interprétation
Le nombre de pivots non nuls obtenus à la fin de l'algorithme est appelé le rang du système, noté .
#Critères de résolution
| Condition | Nombre de solutions |
|---|---|
| Solution unique | |
| Infinité de solutions (dimension ) | |
| Aucune solution (système incompatible) |
où désigne la matrice augmentée.
#Variables libres
Lorsque , les inconnues correspondant aux colonnes sans pivot sont appelées variables libres. Elles peuvent prendre n'importe quelle valeur et servent de paramètres pour exprimer l'ensemble des solutions.
#Complexité algorithmique
L'algorithme de Gauss a une complexité de opérations pour une matrice carrée . C'est remarquablement efficace : résoudre un système de 1000 équations nécessite environ opérations, soit moins d'une seconde sur un ordinateur moderne.
Des variantes optimisées existent pour des matrices particulières (creuses, bande, symétriques...) qui réduisent encore cette complexité.