Méthode de Gauss optimisée

**membreComplexe12** · 22/01/2012, 18h02

Salut tous,

j'ai vu sur un document que pour optimiser la methode de Gauss (minimiser les erreur d'arrondis) il faut choisir le plus grand pivot possible (et donc permurter les lignes).

je n'ai pas compris pourquoi, pourriez vous m'expliquer svp ?

=> ce que je comprends pas c'est que si on raisonne comme cela on peut se dire: je dois ajouter à chaque ligne un nombre enorme pour avoir le pivot maximal ! je comprends que ce raisonnement est faux mais j'aimerai comprendre c'est quoi cet histoire de pivot max...

merci d'avance pour votre aide

**FR119492** · 22/01/2012, 21h19

Salut!
Sur ce site, il y a des cours, en particulier un que j'ai écrit: "Résolution des systèmes linéaires", où tu trouveras la réponse à ta question.
Jean-Marc Blanc

**membreComplexe12** · 23/01/2012, 00h08

merci je vais regarder

**Aleph69** · 23/01/2012, 14h08

Bonjour,

tu liras dans beaucoup de documents qu'il faut pivoter pour améliorer la précision de tes calculs mais en fait on sait théoriquement que ça ne sert pas à grand chose. Quand on résout un système linéaire Ax=b à l'aide de la méthode de Gauss, on sait que l'erreur sur la solution vérifie

||x-y|| <= C(n)*k(A)*rho(A)*||x||,

où ||.|| est une norme vectorielle, y désigne la solution approchée calculée, C(n)>1 est une constante ne dépendant que de la taille n du problème, k(A)>=1 est le conditionnement de la matrice A pour la norme matricielle subordonnée à ||.||, et rho(A)>=1 un terme de croissance. Il s'avère que ce dernier terme n'est pas borné en général, c'est-à-dire que l'erreur ||x-y|| peut être arbitrairement grande. Concrètement, cela veut dire qu'en utilisant la méthode de Gauss tu peut calculer n'importe quoi si ton système linéaire possède des propriétés particulièrement défavorables. Les techniques de pivotage permettent de borner le terme de croissance. Par exemple, en permutant les lignes pour maximiser chaque pivot en valeur absolue, on obtient

rho(A) <= 2^n.

Certes, on sait que l'erreur est bornée, mais par un terme qui est très élevé si la taille n de ton système est grande.

La vraie raison pour laquelle on pivote est que l'on s'assure de ne pas avoir de pivot nul lorsque la matrice est inversible, c'est-à-dire qu'on s'assure de ne jamais diviser par un terme nul. Dit autrement, la factorisation LU d'une matrice inversible existe toujours à une permutation par ligne ou par colonne près . Sans permutation, une matrice inversible n'admet pas nécessairement de factorisation LU.

Pour approfondir le sujet, tu peux lire le livre de Higham intitulé "Accuracy and stability of numerical algorithms".

**membreComplexe12** · 23/01/2012, 14h29

Envoyé par Aleph69

Bonjour,

tu liras dans beaucoup de documents qu'il faut pivoter pour améliorer la précision de tes calculs mais en fait on sait théoriquement que ça ne sert pas à grand chose. Quand on résout un système linéaire Ax=b à l'aide de la méthode de Gauss, on sait que l'erreur sur la solution vérifie

où ||.|| est une norme vectorielle, y désigne la solution approchée calculée, C(n)>1 est une constante ne dépendant que de la taille n du problème, k(A)>=1 est le conditionnement de la matrice A pour la norme matricielle subordonnée à ||.||, et rho(A)>=1 un terme de croissance. Il s'avère que ce dernier terme n'est pas borné en général, c'est-à-dire que l'erreur ||x-y|| peut être arbitrairement grande. Concrètement, cela veut dire qu'en utilisant la méthode de Gauss tu peut calculer n'importe quoi si ton système linéaire possède des propriétés particulièrement défavorables. Les techniques de pivotage permettent de borner le terme de croissance. Par exemple, en permutant les lignes pour maximiser chaque pivot en valeur absolue, on obtient

Certes, on sait que l'erreur est bornée, mais par un terme qui est très élevé si la taille n de ton système est grande.

La vraie raison pour laquelle on pivote est que l'on s'assure de ne pas avoir de pivot nul lorsque la matrice est inversible, c'est-à-dire qu'on s'assure de ne jamais diviser par un terme nul. Dit autrement, la factorisation LU d'une matrice inversible existe toujours à une permutation par ligne ou par colonne près . Sans permutation, une matrice inversible n'admet pas nécessairement de factorisation LU.

Pour approfondir le sujet, tu peux lire le livre de Higham intitulé "Accuracy and stability of numerical algorithms".

merci alex pour cette reponse !

en gros ce que tu veux me dire c'est que si la matrice est mal conditionnée je peux prendre n'importe quel pivot la solution sera pourrie ?

si j'ai une matrice très bien conditionnée la solution de changer de pivot ameliore grandement les resultats où c'est negligeable ? (c'est solution porte de nom de pivot partiel, c'est bien ça ?)

**Aleph69** · 23/01/2012, 14h49

Le pivotage est dit partiel si on ne permute que des lignes (pivotage partiel par ligne) ou que des colonnes (pivotage partiel par colonne). Il est dit total lorsqu'on permute à la fois des lignes et des colonnes.

Il faut bien comprendre que la norme de l'erreur est bornée par un terme de conditionnement ET un terme de croissance, c'est-à-dire que :
1. il s'agit bien d'une borne supérieure qui ne donne qu'une estimation du pire cas possible. Un problème mal conditionné ne conduit pas nécessairement à de grandes erreurs de calcul.
2. les influences du préconditionnement et du pivotage ne sont pas liées (on n'agit pas sur le même terme).

Ceci permet de répondre à tes questions.

si la matrice est mal conditionnée je peux prendre n'importe quel pivot la solution sera pourrie ?

Non, pas forcément à cause de 1.

si j'ai une matrice très bien conditionnée la solution de changer de pivot ameliore grandement les resultats où c'est negligeable ?

A cause de 2., il n'y a pas de rapport direct entre le pivotage et le conditionnement (sauf cas particulier).

EDIT : je vais te donner une réponse plus frappante pour que tu comprennes bien. Je résous des systèmes linéaires inversibles de conditionnement en 10^8 et de terme de croissance en 10^9 et j'obtiens quand même une solution à 10^{-9} près. Seulement, je ne peux vérifier cela qu'après calcul de la solution. Par conséquent, pour éviter les problèmes, on préfère préconditionner et faire du pivotage pour éviter d'avoir des problèmes d'imprécisions et/ou d'inexistence de la factorisation LU.

**membreComplexe12** · 23/01/2012, 15h28

merci beaucoup pour ta reponse !!!

=> peux tu m'en dire un peu plus sur ce terme de croisance stp ?
c'est la capacité en amplifier les erreurs ou un truc dans ce genre ?

=> es ce terme de croissance est lié au rayon spectral de la matrice ? et si oui comment ? pourquoi ... ?

merci de ton aide

**Aleph69** · 23/01/2012, 15h48

=> peux tu m'en dire un peu plus sur ce terme de croisance stp ?
c'est la capacité en amplifier les erreurs ou un truc dans ce genre ?

C'est une mesure de la croissance des termes de ta matrice pendant l'élimination. Disons qu'on applique la méthode de Gauss à une matrice inversible A. On pose A^(0)=A. Je note A^(1) la matrice obtenue après élimination des termes sous-diagonaux de la 1e colonne (étape 1). Je note A^(2) la matrice obtenue après élimination des termes sous-diagonaux de la 2e colonne (étape 2). Plus généralement, je note A^(k) la matrice obtenue après élimination des termes sous-diagonaux de la ke colonne (étape k), pour 1<=k<n, n désignant la taille de A. En particulier, A^(n-1)=U est la matrice triangulaire supérieure obtenue à la fin de la méthode de Gauss. Pour 1<=i,j<=n, je note a_ij le coefficient de A situé en ligne i et colonne j, et je désigne par a_ij^(k) le coefficient de A^(k) situé en ligne i et colonne j. Alors, le terme de croissance est défini par

rho(A) = max_ijk |a_ij^(k)| / max_ij |a_ij|.

Ce terme grandit quand l'élimination augmente la valeur des coefficients matriciels.

=> es ce terme de croissance est lié au rayon spectral de la matrice ? et si oui comment ? pourquoi ... ?

Tout ce qui fait intervenir les coefficients d'une matrice peut être lié d'une manière ou d'une autre au rayon spectral via des minorations/majorations. En particulier, on peut majorer la norme d'une matrice par son rayon spectral et on peut utiliser aussi les encadrements de Gershgorin pour travailler plus localement. Bref, tu peux sûrement encadrer rho(A) par des termes dépendant du spectre de ta matrice et des matrices intermédiaires A^(k). Cependant, je ne pense pas qu'un tel encadrement soit très utile en pratique car beaucoup trop large.

**membreComplexe12** · 23/01/2012, 16h20

merci pour ton aide.

Si j'ai bien compris une matrice avec un conditionnement parfais, si on l'a résous par Gauss peut donner un résultat pourri... ?

j'aurais pas pensé...

**Aleph69** · 23/01/2012, 16h22

Tout à fait! C'est le cas de tous les algorithmes qui ne sont pas rétrogradement stables (backward stable).

**membreComplexe12** · 23/01/2012, 16h40

Envoyé par Aleph69

Tout à fait! C'est le cas de tous les algorithmes qui ne sont pas rétrogradement stables (backward stable).

merci alex pour ta reponse!

du coup c'est nul comme algo

lol
on est jamais certain que la solution est la bonne ....

**Aleph69** · 23/01/2012, 16h59

Il s'avère qu'en pratique l'algorithme fournit généralement des solutions très précises mais on ne sait pas expliquer pourquoi :
http://www.cse.illinois.edu/courses/..._Mysteries.pdf

**membreComplexe12** · 23/01/2012, 17h13

merci pour le lien

et en pratique c'est beaucoup utilisé comme algo ? par exemple dans matlab c'est ceci qui est utilisé ou un autre ?

on prefere utiliser des methodes iteratives en pratiques ou direct ? et pourquoi .. ?

**Aleph69** · 23/01/2012, 17h23

et en pratique c'est beaucoup utilisé comme algo ?

C'est la méthode directe la plus utilisée pour résoudre les systèmes linéaires inversibles qui ne sont pas hermitiens définis positifs.

par exemple dans matlab c'est ceci qui est utilisé ou un autre ?

Oui, c'est la commande backslash de matlab.

on prefere utiliser des methodes iteratives en pratiques ou direct ? et pourquoi .. ?

Cela dépend des applications. Les méthodes directes donnent en général des solutions plus précises que les méthodes itératives mais nécessitent beaucoup plus de mémoire vive. Au niveau des temps de calcul, c'est très variable. Pour faire simple, la complexité d'une méthode directe est en O(n^3) alors qu'une méthode itérative (krylov) est en O(mn^2) où m désigne le nombre d'itérations.

**membreComplexe12** · 23/01/2012, 17h28

merci beaucoup pour ces supers explication, une dernière:

=> tu dis que les méthodes directes utilisent + de memoires vivent, à quoi cela est lié ? il y a moijns d'operation que les methodes iteratives mais les operations sont plus grosses ?

c'est un truc dans ce genre ? pourrais tu m'expliquer stp ?

merci d'avance (c la dernière question

)

**Aleph69** · 24/01/2012, 18h44

On suppose que tu dois résoudre un système linéaire inversible de taille n. Avec une méthode itérative, tu devras stocker quelques vecteurs intermédiaires de taille n. Avec une méthode directe, tu devras stocker la factorisation LU de ta matrice c'est-à-dire des matrices de taille nxn. Tu gagnes un peu parce que ces matrices sont triangulaires mais ça reste beaucoup plus important que le stockage de quelques vecteurs.