Conditionnement et Stabilité Numérique

Le conditionnement mesure la sensibilité de la solution d'un problème aux perturbations de ses données, tandis que la stabilité mesure l'erreur qu'un algorithme particulier ajoute lors de calculs en arithmétique à précision finie ; ensemble, ils déterminent la précision d'un résultat calculé.

Definition

Le conditionnement est une propriété intrinsèque d'un problème décrivant comment sa solution exacte réagit aux perturbations de l'entrée, tandis que la stabilité numérique est une propriété d'un algorithme décrivant avec quelle fidélité il résout le problème malgré les erreurs d'arrondi.

Scope

Ce sujet couvre l'arithmétique à virgule flottante et l'erreur d'arrondi unitaire (unit roundoff), le nombre de conditionnement de problèmes tels que la résolution de systèmes linéaires et l'évaluation de fonctions, l'erreur avant (forward error) et l'erreur arrière (backward error), la règle empirique selon laquelle l'erreur avant est bornée par le nombre de conditionnement multiplié par l'erreur arrière, et les définitions de la stabilité arrière et de la stabilité avant.

Core questions

• Comment l'arithmétique à virgule flottante est-elle modélisée, et quel est le rôle de l'erreur d'arrondi unitaire ?
• Que quantifie le nombre de conditionnement d'un problème, et comment est-il défini pour les systèmes linéaires et pour l'évaluation de fonctions ?
• Comment l'erreur avant, l'erreur arrière et le conditionnement sont-ils liés ?
• Qu'est-ce qui distingue un algorithme stable en arrière d'un algorithme stable en avant, et pourquoi la stabilité arrière est-elle généralement l'objectif ?

Key theories

Nombre de conditionnement

Le nombre de conditionnement est le facteur par lequel les perturbations relatives dans les données peuvent être amplifiées dans la solution ; pour un système linéaire, il est égal à la norme de la matrice multipliée par la norme de son inverse, et il fixe une limite à la précision atteignable, indépendamment de l'algorithme.

Analyse d'erreur arrière

Plutôt que de borner directement l'erreur dans la réponse, on montre que le résultat calculé est la réponse exacte à un problème voisin ; un algorithme est stable en arrière lorsque ce problème voisin diffère de l'original d'une quantité de l'ordre de l'erreur d'arrondi unitaire.

L'erreur avant est égale au nombre de conditionnement multiplié par l'erreur arrière

La règle empirique centrale de l'analyse numérique stipule que l'erreur avant (de la solution) est approximativement bornée par le nombre de conditionnement du problème multiplié par l'erreur arrière, séparant clairement les contributions du problème et de l'algorithme.

Mechanisms

Les nombres à virgule flottante représentent les nombres réels avec une précision finie ; ainsi, chaque opération élémentaire entraîne une erreur relative bornée par l'erreur d'arrondi unitaire. L'analyse d'erreur arrière (backward error analysis) suit ces erreurs en les attribuant à des perturbations des données plutôt qu'au résultat, produisant des bornes de la forme : la réponse calculée est égale à la réponse exacte d'une entrée perturbée. La combinaison d'une borne d'erreur arrière avec le nombre de conditionnement du problème donne une estimation de l'erreur avant, ce qui explique pourquoi un algorithme stable peut néanmoins perdre en précision sur un problème mal conditionné.

Clinical relevance

La compréhension du conditionnement et de la stabilité est essentielle chaque fois que les résultats calculés doivent être fiables : elle explique pourquoi certaines formulations des moindres carrés perdent en précision, guide le choix d'algorithmes stables et de formulations bien posées dans les domaines de la simulation et de l'analyse de données, et avertit lorsqu'un modèle mal conditionné ne peut pas fournir une réponse fiable, quelle que soit la méthode utilisée.

History

Le cadre conceptuel a été établi par Wilkinson, dont l'analyse d'erreur arrière dans les années 1960 a expliqué la fiabilité pratique de l'élimination de Gauss, et a ensuite été systématisé et étendu à l'ensemble du domaine par Higham ; la norme IEEE 754 pour l'arithmétique à virgule flottante a par la suite établi un fondement solide et portable pour le comportement d'arrondi.

Key figures

• James H. Wilkinson
• Nicholas J. Higham
• Lloyd N. Trefethen
• William Kahan

Seminal works

• trefethen1997
• higham2002

Frequently asked questions

Si un algorithme est stable, donnera-t-il toujours une réponse précise ?

Non. Un algorithme stable en arrière garantit seulement que sa réponse est exacte pour un problème voisin ; si le problème lui-même est mal conditionné, ce problème voisin peut avoir une solution très différente, de sorte que l'erreur avant peut toujours être importante.

Qu'est-ce que l'erreur d'arrondi unitaire ?

L'erreur d'arrondi unitaire est l'erreur relative maximale encourue lorsqu'un nombre réel est arrondi au nombre à virgule flottante le plus proche ; elle définit la granularité de l'arithmétique à virgule flottante et apparaît dans pratiquement toutes les bornes de stabilité.