En Python, la méthode de résolution des systèmes linéaires doit varier en fonction de la taille du système (et donc de sa complexité de résolution). En effet, les méthodes classiques de résolution de système vues en prépa ECG peuvent prendre un temps immense dans le cas d’un système linéaire complexe et c’est pourquoi il existe une autre manière de résoudre les systèmes par une approximation des résultats : la méthode itérative. Étudions quelques-unes de ces méthodes itératives ! Attention, il s’agit d’une notion assez avancée dans le hors programme, maîtrise bien les bases Python des matrices pour aborder cet article.
Introduction
Pour de nombreux problèmes d’analyse quantitative en économie et en science des données, les systèmes d’équations linéaires peuvent être d’une taille colossale, contenant des milliers, voire des millions de variables. Dans ce contexte, les méthodes de résolution directes deviennent souvent impraticables en raison de leurs exigences massives en mémoire et donc d’un temps de résolution trop conséquent.
C’est là que les méthodes itératives prennent tout leur sens. Plutôt que de trouver la solution exacte en un nombre fini d’étapes, elles procèdent par approximations successives, en affinant une estimation initiale jusqu’à ce qu’elle soit suffisamment proche de la solution réelle. Le résultat est une solution approchée, dont la précision est contrôlée par un critère de tolérance, ce qui est souvent largement suffisant pour les applications pratiques.
Un système d’équations linéaires est un ensemble de deux ou plusieurs équations linéaires impliquant les mêmes variables. La solution du système est un ensemble de valeurs pour les variables qui satisfait toutes les équations simultanément.
\(
\begin{cases}
a_{11}x_1 + a_{12}x_2 + \dots + a_{1n}x_n = b_1 \\
a_{21}x_1 + a_{22}x_2 + \dots + a_{2n}x_n = b_2 \\
\vdots \\
a_{m1}x_1 + a_{m2}x_2 + \dots + a_{mn}x_n = b_m
\end{cases}\)
En regroupant ce système sous forme d’équation matricielle \(Ax = b\), on cherche à déterminer la matrice \(x\) contenant les inconnues. Cela tombe bien, voyons les trois méthodes principales lorsque l’on ne peut pas résoudre le système directement et que l’on doit recourir à des valeurs approchées.
La méthode de Jacobi
La méthode de Jacobi est l’une des approches itératives les plus intuitives. Son principe repose sur une mise à jour simultanée des valeurs du vecteur solution à chaque itération.
Principe et limites
Pour résoudre le système \(Ax=b\), on réorganise chaque équation pour isoler une variable, en utilisant les valeurs de l’itération précédente. Le nouveau vecteur solution, \(x^{(k+1)}\), est calculé en utilisant le vecteur solution de l’itération précédente, \(x^{(k)}\) :
\(x_{i}^{(k+1)} = \frac{1}{a_{ii}} \left( b_i – \sum_{j \neq i} a_{ij}x_j^{(k)} \right)\)
L’avantage majeur de la méthode de Jacobi réside dans sa simplicité de mise en œuvre. Chaque nouvelle composante \(x_i^{(k+1)}\) est calculée indépendamment des autres dans la même itération. Cela la rend idéale pour le calcul haute performance, où le travail peut être réparti sur plusieurs processeurs.
Le principal inconvénient est sa faible vitesse de convergence. Pour de nombreuses matrices, la méthode de Jacobi converge beaucoup plus lentement que la méthode de Gauss-Seidel (que nous allons voir par la suite). De plus, la convergence n’est pas toujours garantie ; elle est assurée si la matrice est à diagonale dominante.
Script Python
Explorons un petit peu ce script pour développer les fonctions moins connues qui sont hors programme pour certaines.
Avec ‘n=len(b)’, on obtient la dimension du système, qui est la longueur du vecteur
x_prev = x.copy() crée une nouvelle liste ou un tableau en mémoire avec les mêmes éléments précédents pris par x_prev. Dans un algorithme qui met à jour une variable de manière répétée, il est souvent nécessaire de conserver la valeur de la variable avant sa mise à jour et cette fonction sauvegarde les précédentes valeurs prises par x_prev.
Après chaque itération, on vérifie si la solution a convergé en calculant la norme de la différence entre la solution actuelle () et la solution précédente () à l’aide de la ligne np.linalg.norm(x – x_prev) < tol. En effet, par définition de la méthode, si cette différence est inférieure à la tolérance spécifiée, la solution est considérée comme stable et donc on la retiendra. Comme tu l’auras compris, tout tient à l’appréciation de la valeur de tolérance fixée au préalable.
La méthode de Gauss-Seidel
La méthode de Gauss-Seidel est une amélioration de Jacobi. Son principe repose sur une mise à jour séquentielle des variables, qui permet d’accélérer le processus de convergence.
Principe et limites
Lors du calcul d’une nouvelle valeur \(x_i^{(k+1)}\), la méthode de Gauss-Seidel utilise immédiatement les nouvelles valeurs \(x_j^{(k+1)}\) (déjà calculées dans la même itération) pour \(j < i\) :
\(x_{i}^{(k+1)} = \frac{1}{a_{ii}} \left( b_i – \sum_{j < i} a_{ij}x_j^{(k+1)} – \sum_{j > i} a_{ij}x_j^{(k)} \right)\)
L’avantage principal est sa vitesse de convergence : en utilisant les valeurs les plus à jour, elle converge généralement en moins d’itérations que Jacobi. De plus, elle est plus efficace en mémoire, car elle n’a pas besoin de stocker un vecteur temporaire.
Son principal inconvénient est son caractère séquentiel. Le calcul d’une variable dépend du calcul des variables précédentes dans la même itération. Cela rend la méthode difficile à paralléliser.
Script Python
Les fonctions ont déjà été expliquées précédemment lors du premier script. En effet, la différence essentielle avec le premier script se situe entre la 10 et la 12e ligne qui concerne la partie « mathématique » qui différencie les deux méthodes d’itération.
La méthode SOR (Successive Over-Relaxation)
La méthode de surrelaxation successive est une généralisation de Gauss-Seidel, conçue pour accélérer sa convergence en introduisant un paramètre de relaxation \(\omega\).
Principe et limites
La méthode SOR procède en deux étapes à chaque itération.
On calcule d’abord une estimation intermédiaire \(\tilde{x}_i^{(k+1)}\) en utilisant la méthode de Gauss-Seidel :
\[\tilde{x}_{i}^{(k+1)} = \frac{1}{a_{ii}} \left( b_i – \sum_{j < i} a_{ij}x_j^{(k+1)} – \sum_{j > i} a_{ij}x_j^{(k)} \right)\]
On applique ensuite le facteur de relaxation \(\omega\) pour obtenir la valeur finale :
\[x_i^{(k+1)} = (1 – \omega)x_i^{(k)} + \omega \tilde{x}_i^{(k+1)}\]
Si \(1 < \omega < 2\), on parle de « sursaut » (ou over-relaxation).
La méthode SOR peut drastiquement réduire le nombre d’itérations nécessaires à la convergence. Pour les bonnes valeurs de \(\omega\), elle est significativement plus rapide que Gauss-Seidel. Elle est largement utilisée dans la résolution numérique des équations aux dérivées partielles.
Limites : le principal défi est le choix du paramètre optimal \(\omega\). Une mauvaise valeur peut non seulement ralentir la convergence, mais aussi la faire diverger complètement. Pour les matrices générales, déterminer ce paramètre est un problème en soi que nous ne développerons pas ici par crainte de trop complexifier le sujet de l’article !
Script Python
Les fonctions présentes dans ce script sont toutes au programme ou expliquées précédemment, je ne peux que t’inciter à relire les scripts plus haut si tu n’arrives pas à intuiter ce script-là, sache que c’est totalement normal et que ces scripts sont relativement complexes !
Conclusion
Ces méthodes ne sont pas un remplacement des méthodes directes que tu as vues dans le cours, mais bien un ensemble d’outils complémentaires, indispensables pour aborder des problèmes d’une complexité sans cesse croissante. Soyons réalistes, ces méthodes sont extrêmement complexes et ne pourront vraisemblablement pas être abordées dans un sujet Ecricome, EMLyon ou EDHEC. Même pour un sujet de type Maths I, il serait assez complexe de traiter cette notion, bien qu’il ne soit pas impossible qu’elle vienne à tomber aux concours.
Tu peux retrouver le méga-répertoire qui contient toutes les annales de concours et les corrigés. Tu peux également accéder à toutes nos autres ressources mathématiques !
