Aller au contenu
ELECTRONICS ENGINEERINGelectronics-engineering.com
Analyse numérique

Systèmes linéaires sur ordinateur : LU, pivotage, Cholesky et méthodes itératives

Factorisation LU et son coût, pivotage partiel avec un exemple, Cholesky, matrices creuses, méthodes de Jacobi et de Gauss-Seidel, rayon spectral et résidu.

https://www.electronics-engineering.com/fr/systemes-lineaires-numeriques-lu-cholesky-iteratives/

Pas encore de vote : soyez le premier à noter cette page.

En Géométrie et Algèbre les systèmes linéaires se résolvaient par élimination de Gauss sur des matrices 3×3. Dans les problèmes réels les matrices ont des milliers ou des millions de lignes : simuler un circuit intégré, l’analyse de structures par éléments finis, reconstruire une image dans un scanner. Ce qui compte ici, c’est le coût du calcul, la stabilité vis-à-vis des arrondis et la structure de la matrice. Nous voyons les méthodes directes (factorisations LU et de Cholesky) et itératives (Jacobi et Gauss-Seidel).

La factorisation LU

L’élimination de Gauss, en enregistrant les multiplicateurs utilisés, décompose la matrice en produit

    \[ A = L\,U \]

avec L triangulaire inférieure (des 1 sur la diagonale et les multiplicateurs en dessous) et U triangulaire supérieure (la forme échelonnée). Le système A\mathbf x = \mathbf b devient deux systèmes triangulaires, résolus par substitution :

    \[ L\mathbf y = \mathbf b \;\;(\text{forward}),\qquad U\mathbf x = \mathbf y \;\;(\text{backward}) \]

L’avantage. La factorisation coûte environ \tfrac23 n^3 opérations, mais les deux substitutions seulement 2n^2. S’il faut résoudre de nombreux systèmes avec la même matrice et des seconds membres différents (comme dans un simulateur où seules les sources changent à chaque pas), on factorise une seule fois. Avec n = 1000 : 6.7\times 10^8 opérations pour la factorisation, 2\times 10^6 pour chaque nouveau second membre.

Exemple.

    \[ A = \begin{pmatrix} 2 & 1 & 1\\ 4 & 3 & 3\\ 8 & 7 & 9\end{pmatrix} = \begin{pmatrix} 1 & 0 & 0\\ 2 & 1 & 0\\ 4 & 3 & 1\end{pmatrix}\begin{pmatrix} 2 & 1 & 1\\ 0 & 1 & 1\\ 0 & 0 & 2\end{pmatrix} \]

Les multiplicateurs 2 et 4 éliminent la première colonne, le 3 la seconde.

Le pivotage

Si un zéro apparaît sur la diagonale pendant l’élimination la méthode s’arrête ; si un très petit nombre apparaît, on divise par lui et les erreurs d’arrondi explosent.

Exemple. Avec A = \begin{pmatrix}10^{-20} & 1\\ 1 & 1\end{pmatrix} et \mathbf b = (1, 2), la vraie solution est environ x_1 = x_2 = 1. Sans échanges le multiplicateur est 10^{20}, et en double précision la deuxième ligne devient (0, -10^{20}) parce que 1 - 10^{20} s’arrondit à -10^{20} : on obtient x_2 = 1 puis x_1 = 0, complètement faux. Échanger les lignes avant d’éliminer donne le bon résultat.

Le pivotage partiel choisit à chaque pas, comme pivot, l’élément de plus grand module de la colonne, et échange les lignes. Les multiplicateurs ont alors un module d’au plus 1 et la méthode est stable en pratique. La factorisation devient PA = LU, avec P une matrice de permutation. C’est la méthode standard de toute bibliothèque numérique (LAPACK, NumPy, MATLAB).

Matrices symétriques définies positives : Cholesky

Si A est symétrique et définie positive (comme les matrices de rigidité des structures, les matrices de covariance, les matrices nodales des circuits de seules résistances), alors

    \[ A = L\,L^T \]

avec L triangulaire inférieure. La factorisation de Cholesky coûte moitié moins que LU (\tfrac13 n^3), n’a pas besoin de pivotage et est toujours stable. Si la racine carrée d’un nombre négatif apparaît pendant le calcul, la matrice n’était pas définie positive : c’est aussi la façon la plus rapide de le vérifier.

Les matrices creuses

Dans les applications, les grandes matrices sont presque entièrement nulles : dans la matrice nodale d’un circuit, chaque ligne n’a des éléments non nuls que pour les nœuds directement connectés. Une matrice pleine 10^6\times 10^6 occuperait 8 téraoctets en double précision ; creuse, avec 10 éléments par ligne, 80 mégaoctets. Les méthodes directes creuses réordonnent lignes et colonnes pour limiter le remplissage (fill-in), les zéros qui deviennent non nuls pendant l’élimination. C’est ce que font SPICE et les programmes d’éléments finis.

Les méthodes itératives

Pour de très grandes matrices creuses il vaut souvent mieux partir d’une estimation \mathbf x^{(0)} et l’améliorer, sans jamais factoriser.

Jacobi. À partir de l’équation i, on résout en x_i en utilisant pour les autres inconnues les valeurs de l’itération précédente :

    \[ x_i^{(k+1)} = \frac{1}{a_{ii}}\Big(b_i - \sum_{j \ne i}a_{ij}\,x_j^{(k)}\Big) \]

Gauss-Seidel. Comme Jacobi, mais il utilise tout de suite les valeurs déjà mises à jour dans la même itération. Il converge en général environ deux fois plus vite et utilise moins de mémoire.

Exemple. 4x + y = 9, x + 3y = 7 (solution x = 20/11 \approx 1.818, y = 19/11 \approx 1.727). Gauss-Seidel à partir de (0, 0) : x = 9/4 = 2.25, y = (7 - 2.25)/3 = 1.583 ; puis x = 1.854, y = 1.715 ; puis x = 1.821, y = 1.726. Trois pas, trois chiffres corrects.

Quand elles convergent

En écrivant l’itération sous la forme \mathbf x^{(k+1)} = B\,\mathbf x^{(k)} + \mathbf c, l’erreur est multipliée par B à chaque pas, donc la méthode converge si et seulement si le rayon spectral de B (le plus grand module de ses valeurs propres, leçon de Géométrie et Algèbre) est inférieur à 1. Une condition suffisante facile à vérifier : la matrice est à diagonale dominante, |a_{ii}| \gt \sum_{j \ne i}|a_{ij}| pour chaque ligne. Les matrices nodales des circuits résistifs le sont presque toujours.

Pour les plus gros problèmes on utilise des méthodes itératives plus sophistiquées, comme la méthode du gradient conjugué pour les matrices symétriques définies positives, qui en arithmétique exacte atteint la solution en au plus n pas et en pratique en demande bien moins, surtout avec un bon préconditionneur.

Gauss-Seidel sur l'exemple
Les deux droites sont les équations du système et se coupent à la solution, en rouge. En partant de l’origine, en vert, chaque pas de Gauss-Seidel résout une équation à la fois : il se déplace horizontalement jusqu’à la première droite et verticalement jusqu’à la seconde. L’escalier, en bleu, converge vers la solution en quelques pas.

Le résidu ne suffit pas

Après avoir calculé \hat{\mathbf x}, le résidu \mathbf r = \mathbf b - A\hat{\mathbf x} est facile à calculer, mais un petit résidu ne garantit pas une solution précise. L’erreur relative est majorée par

    \[ \frac{\|\mathbf x - \hat{\mathbf x}\|}{\|\mathbf x\|} \le K(A)\,\frac{\|\mathbf r\|}{\|\mathbf b\|} \]

avec K(A) le nombre de conditionnement de la leçon sur les erreurs. Si K(A) est grand, même un résidu minuscule peut cacher une grosse erreur.

S’abonner
Notifier de
guest
1 commentaire
Le plus ancien
Plus récent Les plus votés
1
0
Vous avez apprécié cet article ? Merci de laisser un commentaire.x