Stabilité numérique - Numerical stability

Dans le sous-domaine mathématique de l'analyse numérique , la stabilité numérique est une propriété généralement souhaitable des algorithmes numériques . La définition précise de la stabilité dépend du contexte. L'un est l'algèbre linéaire numérique et l'autre les algorithmes de résolution d'équations aux dérivées ordinaires et partielles par approximation discrète.

En algèbre linéaire numérique, la principale préoccupation concerne les instabilités causées par la proximité de singularités de divers types, telles que des valeurs propres très petites ou presque en collision . D'autre part, dans les algorithmes numériques pour les équations différentielles, le problème est la croissance des erreurs d'arrondi et/ou de petites fluctuations dans les données initiales qui pourraient entraîner un écart important de la réponse finale par rapport à la solution exacte.

Certains algorithmes numériques peuvent atténuer les petites fluctuations (erreurs) dans les données d'entrée ; d'autres pourraient amplifier de telles erreurs. Les calculs dont il est prouvé qu'ils n'amplifient pas les erreurs d'approximation sont appelés numériquement stables . L'une des tâches courantes de l'analyse numérique est d'essayer de sélectionner des algorithmes robustes  , c'est-à-dire qui ne produisent pas un résultat très différent pour un très petit changement dans les données d'entrée.

Un phénomène opposé est l' instabilité . Typiquement, un algorithme implique une méthode approximative, et dans certains cas, on pourrait prouver que l'algorithme approcherait la bonne solution dans une certaine limite (lors de l'utilisation de nombres réels réels, pas de nombres à virgule flottante). Même dans ce cas, il n'y a aucune garantie qu'il convergerait vers la solution correcte, car les erreurs d'arrondi ou de troncature à virgule flottante peuvent être amplifiées, au lieu d'être amorties, provoquant une croissance exponentielle de l'écart par rapport à la solution exacte.

Stabilité en algèbre linéaire numérique

Il existe différentes manières de formaliser le concept de stabilité. Les définitions suivantes de la stabilité avant, arrière et mixte sont souvent utilisées en algèbre linéaire numérique .

Diagramme montrant l' erreur vers l' avant Δ y et l' erreur vers l' arrière Δ x , et leur relation avec la carte de solution exacte  f et la solution numérique  f *.

Considérons le problème à résoudre par l'algorithme numérique comme une fonction  f faisant correspondre les données  x à la solution  y . Le résultat de l'algorithme, disons y *, s'écartera généralement de la "vraie" solution  y . Les principales causes d'erreur sont arrondi erreur et erreur troncature . L' erreur directe de l'algorithme est la différence entre le résultat et la solution ; dans ce cas, Δ y = y * - y . L' erreur vers l'arrière est le plus petit Δ x tel que f  ( x + Δ x ) = y * ; en d'autres termes, l'erreur arrière nous indique quel problème l'algorithme a réellement résolu. L'erreur avant et arrière est liée par le numéro de condition : l'erreur avant est au plus aussi grande en amplitude que le numéro de condition multiplié par l'amplitude de l'erreur arrière.

Dans de nombreux cas, il est plus naturel de considérer l' erreur relative

au lieu de l'erreur absolue Δ x .

L'algorithme est dit rétro-stable si l'erreur rétrograde est faible pour toutes les entrées  x . Bien entendu, « petit » est un terme relatif et sa définition dépendra du contexte. Souvent, nous voulons que l'erreur soit du même ordre que, ou peut-être seulement quelques ordres de grandeur plus grande que l' arrondi unitaire .

La stabilité mixte combine les concepts d'erreur avant et d'erreur arrière.

La définition habituelle de la stabilité numérique utilise un concept plus général, appelé stabilité mixte , qui combine l'erreur avant et l'erreur arrière. Un algorithme est stable en ce sens s'il résout approximativement un problème voisin, c'est-à-dire s'il existe un x tel que à la fois Δ x est petit et f  ( x + Δ x ) − y * est petit. Par conséquent, un algorithme stable en amont est toujours stable.

Un algorithme est stable en avant si son erreur en avant divisée par le nombre de conditions du problème est faible. Cela signifie qu'un algorithme est stable vers l'avant s'il a une erreur d'amplitude similaire à celle d'un algorithme stable vers l'arrière.

Stabilité dans les équations différentielles numériques

Les définitions ci-dessus sont particulièrement pertinentes dans les situations où les erreurs de troncature ne sont pas importantes. Dans d'autres contextes, par exemple lors de la résolution d' équations différentielles , une définition différente de la stabilité numérique est utilisée.

Dans les équations différentielles ordinaires numériques , divers concepts de stabilité numérique existent, par exemple la stabilité A . Ils sont liés à un certain concept de stabilité au sens des systèmes dynamiques , souvent la stabilité de Lyapunov . Il est important d'utiliser une méthode stable lors de la résolution d'une équation rigide .

Une autre définition encore est utilisée dans les équations aux dérivées partielles numériques . Un algorithme de résolution d'une équation aux dérivées partielles évolutive linéaire est stable si la variation totale de la solution numérique à un instant fixe reste bornée lorsque la taille du pas tend vers zéro. Le théorème d'équivalence de Lax stipule qu'un algorithme converge s'il est cohérent et stable (dans ce sens). La stabilité est parfois atteinte en incluant la diffusion numérique . La diffusion numérique est un terme mathématique qui garantit que les arrondis et autres erreurs de calcul sont étalés et ne s'additionnent pas pour faire "exploser" le calcul. L'analyse de stabilité de Von Neumann est une procédure couramment utilisée pour l'analyse de stabilité des schémas aux différences finies appliquée aux équations aux dérivées partielles linéaires. Ces résultats ne sont pas valables pour les EDP non linéaires, où une définition générale et cohérente de la stabilité est compliquée par de nombreuses propriétés absentes des équations linéaires.

Voir également

Les références