Discussion :

[membreComplexe12]

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]

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]

merci je vais regarder

[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

||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]

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]

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.