IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)

Résolution des systèmes linéaires


précédentsommairesuivant

III. Problèmes pathologiques

Cette section montre comment faire face à des situations dues à trois formulations d'une même loi fondamentale :

Loi de Murphy S'il y a plus d'une façon de faire quelque chose, et que l'une d'elles conduit à un désastre, alors il y aura quelqu'un pour le faire de cette façon ;

Loi de Finagle Si quelque chose de mal peut se produire, cela arrivera ;

Loi de la tartine beurrée Une tartine beurrée tombe toujours sur le côté beurré.

Dans cette perspective, nous étudierons divers cas :

  • la matrice est carrée et singulière : système indéterminé ;
  • la matrice est carrée et singulière : système impossible ;
  • la matrice est carrée et mal conditionnée ;
  • la matrice est rectangulaire : plus d'inconnues que d'équations ;
  • la matrice est rectangulaire : plus d'équations que d'inconnues.

III-A. Matrice singulière ; système indéterminé

On considère le système linéaire A x = B dont la matrice A est singulière.

La factorisation LU ne fonctionne pas car on tombe inévitablement sur un pivot nul. La factorisation QR peut être réalisée, mais conduit à une matrice R dont au moins un terme diagonal est nul ; c'est alors la substitution arrière qui tombe sur une division par zéro.

Méthode SVD

La factorisation peut toujours être réalisée. Si la matrice A est singulière, alors une ou plusieurs des valeurs singulières, stockées sur la diagonale principale de la matrice S sont nulles.

Image non disponible

On définit les vecteurs auxiliaires y et z en posant :

Image non disponible

La matrice U étant orthogonale, le calcul du vecteur z ne pose aucun problème :

Image non disponible

Pour déterminer chaque composante y k du vecteur y , on doit diviser la composante zk du vecteur z par la valeur singulière correspondante Sk , ce qui est évidemment impossible si celle-ci est nulle. On alors recours à l'astuce suivante : on met à zéro la composante yk qui sans cela serait infinie, résultant d'une division par zéro.

 
Sélectionnez
Pour k de 1 à n
    Si S(k) plus grand que zéro
        y(k) = z(k)/S(k)
    Sinon
        y(k) = 0
    Fin Si
Fin Pour

La matrice V étant orthogonale, le calcul du vecteur x ne pose aucun problème :

Image non disponible

Il peut sembler choquant de remplacer l'inverse de zéro par zéro lui-même. En fait, parmi l'infinité de solutions qui satisfont le système à résoudre, x est celle dont la norme euclidienne est la plus petite.

III-B. Matrice singulière ; système impossible

On considère le système linéaire Ax = B dont la matrice A est singulière.

La factorisation LU ne fonctionne pas car on tombe inévitablement sur un pivot nul. La factorisation QR peut être réalisée, mais conduit à une matrice R dont au moins un terme diagonal est nul; c'est alors la substitution arrière qui tombe sur une division par zéro.

Méthode SVD

La factorisation peut toujours être réalisée. Si la matrice A est singulière, alors une ou plusieurs des valeurs singulières, stockées sur la diagonale principale de la matrice S sont nulles.

Image non disponible

On définit les vecteurs auxiliaires y et y en posant :

Image non disponible

La matrice U étant orthogonale, le calcul du vecteur z ne pose aucun problème :

Image non disponible

Pour déterminer chaque composante y k du vecteur y , on doit diviser la composante zk du vecteur z par la valeur singulière correspondante Sk , ce qui est évidemment impossible si celle-ci est nulle. On alors recours à l'astuce suivante: on met à zéro la composante yk qui sans cela serait infinie, résultant d'une division par zéro.

 
Sélectionnez
Pour k de 1 à n
    Si S(k) plus grand que zéro
        y(k) = z(k)/S(k)
    Sinon
        y(k) = 0
    Fin Si
Fin Pour

La matrice V étant orthogonale, le calcul du vecteur x ne pose aucun problème :

Image non disponible

Il peut sembler choquant de remplacer l'inverse de zéro par zéro lui-même. En fait, aucune solution ne satisfait exactement le système à résoudre, mais le vecteur trouvé x est celui qui la satisfait le moins mal, c'est-à-dire celui pour lequel la norme euclidienne de Ax - B est la plus petite.

III-C. Matrice carrée mal conditionnée

On considère le système linéaire Ax = B dont la matrice A est mal conditionnée.

Méthode SVD

La factorisation peut toujours être réalisée :

Image non disponible

On définit les vecteurs auxiliaires y et z en posant :

Image non disponible

Si la matrice A est mal conditionnée, alors les dernières valeurs singulières, stockées au bas de la diagonale principale de la matrice S sont très petites par rapport à la plus grande. La matrice U étant orthogonale, le calcul du vecteur z ne pose aucun problème :

Image non disponible

Pour déterminer chaque composante yk du vecteur y , on doit diviser la composante z k du vecteur z par la valeur singulière correspondante Sk , ce qui donnerait un résultat démesuré si celle-ci est très petite. On alors recours à l'astuce suivante : on met à zéro la composante yk qui sans cela serait démesurée, résultant d'une division par une valeur singulière très petite.

 
Sélectionnez
Pour k de 1 à n
    Si S(k) plus grand que epsilon*S(1)
        y(k) = z(k)/S(k)
    Sinon
        y(k) = 0
    Fin Si
Fin Pour

La matrice V étant orthogonale, le calcul du vecteur x ne pose aucun problème :

Image non disponible

Il peut sembler choquant de remplacer l'inverse d'un nombre très petit par zéro. En fait, c'est cette manière de faire qui donne les résultats les plus raisonnables.

III-D. Matrices rectangulaires : systèmes sous-déterminés

On considère le système linéaire A x = B dont la matrice A comporte m lignes et n colonnes, avec m<n :

Image non disponible

Certaines des méthodes vue jusqu'ici ne s'appliquent, du fait de leur principe même, qu'à des matrices carrées (substitution, élimination de Gauss, factorisation LU, méthode de Cholesky). D'autres, en revanche, peuvent aussi être utilisées pour des matrices rectangulaires.

Méthode QR

La factorisation QR donne une matrice orthogonale carrée Q à m lignes et m colonnes, et une matrice « trapézoïdale » R à m lignes et n colonnes :

Image non disponible

On définit le vecteur auxiliaire y en posant :

Image non disponible

La matrice Q étant orthogonale, le calcul du vecteur y ne pose aucun problème :

Image non disponible

En revanche, la matrice R ayant moins de lignes que de colonnes, la solution du système Rx = y est indéterminée. On contourne la difficulté en attribuant une valeur arbitraire (souvent zéro) à une (ou éventuellement plusieurs) inconnue(s), en général la(les) dernière(s), puis on calcule les autres par la méthode de substitution.

Méthode SVD

La factorisation SVD donne :

Image non disponible

On définit les vecteurs auxiliaires y et z en posant :

Image non disponible

III-E. Matrices rectangulaires : systèmes surdéterminés

Dans les systèmes surdéterminés, on a plus d'équations que d'inconnues. La matrice A a donc un nombre de lignes m supérieur au nombre de colonnes :

Image non disponible

Méthode QR

La factorisation QR donne :

Image non disponible

La matrice Q est carrée; elle a m lignes et m colonnes. La matrice R est rectangulaire; elle a m lignes et n colonnes; tous les termes de la dernière ligne sont nuls.

Méthode SVD

La factorisation SVD donne :

Image non disponible

La matrice U est rectangulaire; elle a m lignes et n colonnes. La matrice S est diagonale; elle comporte n termes La matrice V est carrée; elle a n lignes et n colonnes.


précédentsommairesuivant

Copyright © 2008-2013 Jean-Marc Blanc. Aucune reproduction, même partielle, ne peut être faite de ce site ni de l'ensemble de son contenu : textes, documents, images, etc. sans l'autorisation expresse de l'auteur. Sinon vous encourez selon la loi jusqu'à trois ans de prison et jusqu'à 300 000 € de dommages et intérêts.