Erreur d'arrondis et choix du pivot.

[invite13cd37f1]

Salut tout le monde,
J'étais entrain de lire un cours d'analyse numérique, et plus précisément la partie qui traite l'erreur d'arrondis et sa relation avec le choix du pivot dans la résolution d'un système linéaire A.x=b.

Ce que j'ai pu comprendre c'est qu'au cours de l'élimination de Gauss et lorsqu'on a un pivot qui est très proche de 0, on doit le remplacer par
un autre nombre, à l'aide d'une ou plusieurs permutations de lignes ou de colonnes,parce que si non le calcul va être perturbé et on nous a
donner un exemple où on montre l'importance de cette permutation .

Mes questions:

1-pourquoi le calcul se perturbe,puisque les valeurs sont celles de la matrice A, pourquoi le système ne peut pas être résolus sans faire les
échanges ?

2-Lorsqu'on parle de valeur qui tourne autour 0, on n'a pas par hasard un problème avec celle qui est très grande ?

3-Et si on parle de perturbation de solution, est-ce que seulement pour les pivots ou bien pour toute valeur de la matrice ?

Merci d'avance.
-----

[invite13cd37f1]

______________________________ ___

[Dlzlogic]

Bonjour,
Le principe de la méthode du pivot de Gauss est de multiplier tous les termes d'une équation par une valeur, puis de soustraire terme à terme de façon à annuler celui correspondant à une variable. Donc l'une des équation aura un terme en moins, de proche en proche, la dernière n'aura plus qu'un terme, d'où la valeur de l'inconnue est immédiate, et de proche en proche dans l'autre sens, on peut calculer toutes les inconnues.
Donc, à chaque instant, on réalise une opération du type k.A - kB
Si kA et kB sont des valeurs grandes, du même ordre, le résultat de la soustraction sera un nombre petit.
Supposons que les calculs soient faits avec 10 chiffres significatifs, et que ce résultats n'ait que 4 chiffres significatifs, on en a perdu 6. Il est donc très important, dans l'organisation du calcul, d'éviter ce genre de situation.
Ais-je répondu à votre question ?

[leon1789]

Reprenons les questions les unes après les autres.

1-pourquoi le calcul se perturbe,puisque les valeurs sont celles de la matrice A, pourquoi le système ne peut pas être résolus sans faire les échanges ?

De manière générale, il y a deux types de calculs : le calcul formel et le calcul numérique.

Le calcul formel, c'est en particulier un calcul exact (avec des fractions par exemple), c'est celui que l'on pratique à la main si on peut dire.
Dans ce cas, on n'a pas besoin de se préoccuper du fait que le pivot est proche de 0 ou pas, car toutes les opérations sont calculées de manière exacte.

Le calcul numérique, c'est en particulier un calcul approché (avec un certain nombre de chiffres après la virgule), c'est celui pratiqué par la plupart des machines à calculer.

Qui dit calcul approché, dit erreur de calcul : chaque opération apporte une erreur, parfois les erreurs se compensent globalement (ça c'est cool), parfois elles s'ajoutent (ça c'est pas cool, mais ça peut encore aller), parfois elles explosent (ça c'est pas cool du tout !).
L'explosion, c'est justement le cas quand on pratique une division par un nombre proche de 0.
Du coup, tous les coefficients matriciels qui vont suivre dans la résolution du système linéaire seront calculés avec une précision très mauvaise.

2-Lorsqu'on parle de valeur qui tourne autour 0, on n'a pas par hasard un problème avec celle qui est très grande ?

C'est justement le cas quand on pratique une division par un nombre proche de 0, et ce n'est pas le cas quand on divise par un grand nombre.

exemple simple : on veut diviser 1 par le pivot p...

avec un petit nombre :
soit (l'incertitude absolue sur p est petite 0.0001)
alors
donc (l'incertitude absolue sur 1/p est énorme !)
Ainsi une erreur d'arrondi de 0.0001 sur p provoque une erreur de plusieurs milliers sur l'inverse et rend alors le calcul non pertinent.

avec un grand nombre :
soit (l'incertitude absolue sur p est petite 0.0001)
alors
donc (l'incertitude absolue sur 1/p est infime)
Ainsi une erreur d'arrondi de 0.0001 sur p provoque une erreur infime sur l'inverse, plus faible que la précision de la machine à calculer, donc tout va bien.

3-Et si on parle de perturbation de solution, est-ce que seulement pour les pivots ou bien pour toute valeur de la matrice ?

Lorsqu'on il y a des perturbations, c'est sur tous les coefficients qui vont être calculés.

[A voir en vidéo sur Futura]

[Dlzlogic]

Cette réponse est intéressant, mais elle ne s'applique pas dans les calculs informatique.
En effet, la "taille" des nombres est sans grande importance en cas de multiplication et division de nombres. La caractéristique a une latitude de -38 à +38 ou -308 à +308.
La seule chose qui compte, c'est le nombre de chiffres significatifs qu'il faut éviter de perdre en cas de soustraction de deux nombre de "taille" équivalente.
Par contre, il est vrai que lorsque ce nombre aura perdu une partie de ses chiffres significatifs, qu'il serve dans une multiplication ou une division, le nombre de chiffres significatifs exacts du résultat, sera celui des deux facteurs qui en a le moins.

[leon1789]

Le nombre de chiffres significatifs est une incertitude relative. Effectivement, cette incertitude se comporte bien par multiplications/divisions, et peut augmenter avec les additions ou les soustractions.

Mais dans ma réponse, je parle d'incertitude absolue (j'aurais dû le dire dès le début, et pas seulement au milieu de mon message) : c'est cette incertitude qui explose avec des divisions par des nombres proches de 0 (c'est le sujet de la question posée, non ?), ou par des multiplications avec de grands nombres.

[leon1789]

A toutes fins utiles, un document http://www.unige.ch/ses/dsec/static/.../MNE-Cours.pdf

Il est donc absolument nécessaire d’introduire dans l’algorithme un mécanisme de permutation des lignes et/ou des colonnes afin d’éviter des petits pivots.

(fin de la section 6.1 "Formalisation de l’élimination de Gauss")

[leon1789]

Cette réponse est intéressant, mais elle ne s'applique pas dans les calculs informatique.

Ah bon, elle ne s'applique pas dans les calculs informatiques ?! Affirmation assez étonnante...
Par exemple ici http://www.polytech-lille.fr/cours-a...e/Exgauss.html (cours de calcul scientifique à l'école polytechnique de Lille),

Le programme utilise la fonction sl_gauss_aff. En pratique, il est préférable d'utiliser la fonction sl_gauss_pivmax qui :
- n'effectue pas certains calculs inutiles (calcul de zéros) ;
- n'affiche pas à chaque étape les matrices intermédiaires ;
- effectue à chaque étape une recherche de pivot maximum dans la colonne pivot.

[Dlzlogic]

Je n'ai pas compris la contradiction.
Par contre il y a une faute qui pour moi est une faute grave : la variable pivot est un double et le programme le teste égale à 0.
Il ne me parait pas normal de citer en référence sur un forum, une fonction qui contient une telle faute. Idem pour den, un peu plus loin.

[leon1789]

Je n'ai pas compris la contradiction.

tant pis

Par contre il y a une faute qui pour moi est une faute grave : la variable pivot est un double et le programme le teste égale à 0.

Ca doit être cela qui explique tout, en effet. Comme quoi, rien n'est pas parfait.

Il ne me parait pas normal de citer en référence sur un forum, une fonction qui contient une telle faute. Idem pour den, un peu plus loin.

Tu as raison : ne jamais donner de référence, c'est bien mieux.

Revenons aux maths...

[Dlzlogic]

Tu essaye de t'en tirer par une pirouette.
Cette question n'a pas eu de réponse pendant 2 jour.
J'ai apporté une tentative de réponse, tac, 2 heures plus tard tu réagis.
Bon, ce que je dis, c'est que l'opération multiplication, resp, division, n'a rien à voir dans cette problématique, mais seulement l'opération soustraction.
Bien-sûr on est dans un contexte de calcul informatique.

[jiherve]

Bonsoir,
avec des calculs fait en flottant sur des alu réelles (rien à voir avec les réels) on perd la commutativité entre les opérations usuelles, et attention aux additions soustraction celles ci ne peuvent se faire que dans un format commun donc ipso facto on peut perdre des bits.
Inoxydable :http://docs.oracle.com/cd/E19957-01/..._goldberg.html.
Pas grand chose de plus que ce qu'a écrit Dizlogic mais un petit lien fondamental.
JR

[leon1789]

Bon, ce que je dis, c'est que l'opération multiplication, resp, division, n'a rien à voir dans cette problématique, mais seulement l'opération soustraction.

Pour toi (et jiherve, peut-être), prendre un pivot proche de 0 n'est pas un souci ?

[leon1789]

Ok, au lieu de prendre des exemples, reprenons formellement l'opération réalisée avec le pivot lors de l'algorithme. Normalement, on effectue une opération du type

où est le pivot. Pour simplifier les indices, je vais noter sombrement

Supposons que les quantités soient connues respectivement à près. Qu'en est-il pour ? Un petit calcul montre que vaut à près, où

Le fait d'avoir p en dénominateur(s) prouve qu'il ne faut pas qu'il soit proche de 0, sinon l'erreur absolue aura tendance à exploser. Et pour cela, peu importe comment sont codés les nombres... (Certes, il se peut que leur codage informatique accentue davantage encore les erreurs lors de telle ou telle opération, mais le problème posé n'est aussi compliqué.)

[jiherve]

Re

Pour toi (et jiherve, peut-être), prendre un pivot proche de 0 n'est pas un souci ?

Je ne me suis pas prononcé sur ce point juste sur les pièges des calculs fait en flottant IEE754!
JR

[leon1789]

Re
Je ne me suis pas prononcé sur ce point juste sur les pièges des calculs fait en flottant IEE754!
JR

Ok, je comprends mieux ton intervention. Mais ces pièges ne sont pas l'explication de l'instabilité de l'algorithme du pivot de Gauss, on est d'accord ?

[leon1789]

Tu essaye de t'en tirer par une pirouette.

ah bon

J'imagine que tu essayeras de t'en tirer en MP.

[Dlzlogic]

J'ai dit précédemment qu'il fallait distinguer le cas où on applique la méthode en calcul manuel, du cas où on applique la méthode en calcul informatique.
Dans le second cas, le piège est dû à la soustraction de deux nombres approximativement de même valeur, et comme je l'ai expliqué, la division par un nombre petit ou grand n'a pas vraiment d'importance.

D'autre part, j'attire l'attention de la modération sur la tournure que prend cette discussion, d'autant que l'on n'a pas de nouvelle du demandeur.

[leon1789]

le piège est dû à la soustraction de deux nombres approximativement de même valeur

Dans le cas où on soustrait deux nombres approximativement de même valeur, c'est l'incertitude relative qui augmente (puisque le dénominateur est proche de 0).
Pour améliorer l'algorithme, il faudrait alors éviter de faire de telles soustractions dans l'algorithme de Gauss, je veux bien, mais comment ?

la division par un nombre petit ou grand n'a pas vraiment d'importance.

C'est à se demander pourquoi tant de gens cherchent un pivot grand en évitant un pivot proche de 0... (et ce n'est pas un problème de calcul à la main, mais bien en machine).

Encore un exemple très simple :
on veut calculer où et
on obtient
L'incertitude absolue de a été transmise en une incertitude absolue de (1000 fois plus grande) sur le quotient a/b.

Et c'est bien sûr exactement la même chose quand on multiplie par des nombres grands.

En revanche multiplier par des nombres proches de 0 ou diviser par des nombres grands ne conduit pas à ce genre d'explosion de l'incertitude absolue.
De même, additionner et soustraire ne conduit pas à l'explosion de l'incertitude absolue (à moins de faire des milliers ou millions d'additions).

j'attire l'attention de la modération sur la tournure que prend cette discussion

Où est le problème ? chakib.lem.1 a demandé pourquoi éviter les pivots proches de 0, et la réponse est claire.