Worldlex Wiki Le raffinement itératif est une méthode itérative proposée par James H. Wilkinson pour améliorer la précision des solutions numériques aux systèmes d'équations linéaires .
Lors de la résolution d'un système linéaire en raison de l'accumulation composée d' erreurs d'arrondi , la solution calculée peut parfois s'écarter de la solution exacte. En commençant par un raffinement itératif, on calcule une séquence qui converge lorsque certaines hypothèses sont remplies.
Description
Pour la m -ième itération, le raffinement itératif se compose de trois étapes :
- Calculer l'erreur résiduelle r m
- Résolvez le système pour la correction, c m , qui supprime l'erreur résiduelle
- Ajoutez la correction pour obtenir la solution suivante révisée x m +1
Le raisonnement crucial pour l'algorithme de raffinement est que, bien que la solution pour c m à l'étape (ii) puisse en effet être troublée par des erreurs similaires à la première solution, , le calcul du résidu r m à l'étape (i), en comparaison, est numériquement presque exact : vous ne connaissez peut-être pas très bien la bonne réponse, mais vous savez assez précisément à quel point la solution que vous avez en main est loin de produire le résultat correct ( b ). Si le résidu est petit dans un certain sens, alors la correction doit également être petite et devrait au moins orienter l'estimation actuelle de la réponse, x m , plus près de celle souhaitée,
Les itérations s'arrêteront d'elles-mêmes lorsque le résidu r m sera nul, ou suffisamment proche de zéro pour que la correction correspondante c m soit trop petite pour changer la solution x m qui l'a produite ; alternativement, l'algorithme s'arrête lorsque r m est trop petit pour convaincre l'algébriste linéaire qui surveille la progression qu'il vaut la peine de continuer avec d'autres améliorations.
Notez que l'équation matricielle résolue à l'étape (ii) utilise la même matrice pour chaque itération. Si l'équation matricielle est résolue à l'aide d'une méthode directe, telle que la décomposition de Cholesky ou LU , la factorisation numériquement coûteuse de est effectuée une fois et est réutilisée pour la substitution avant et arrière relativement peu coûteuse pour résoudre c m à chaque itération.
Analyse des erreurs
En règle générale, le raffinement itératif pour l'élimination gaussienne produit une solution correcte à la précision de travail si le double de la précision de travail est utilisé dans le calcul de r , par exemple en utilisant une virgule flottante IEEE 754 à précision étendue quadruple ou double , et si A n'est pas trop mal conditionné (et l'itération et le taux de convergence sont déterminés par le numéro de condition de A ).
Plus formellement, en supposant que chaque étape (ii) peut être résolue de manière raisonnablement précise, c'est-à-dire, en termes mathématiques, pour chaque m , nous avons
où ‖F m ‖ ∞ < 1 , l' erreur relative dans la m -ième itération du raffinement itératif satisfait
où
- ‖·‖ ∞ désigne la norme ∞ d'un vecteur,
- κ (A) est le nombre de condition ∞ de A ,
- n est l'ordre de A ,
- ε 1 et ε 2 sont des arrondis unitaires d' opérations arithmétiques à virgule flottante ,
- σ , μ 1 et μ 2 sont des constantes qui dépendent de A , ε 1 et ε 2
si A n'est « pas trop mal conditionné », ce qui signifie dans ce contexte
et implique que μ 1 et μ 2 sont de l’ordre de l’unité.
La distinction entre ε 1 et ε 2 est destinée à permettre une évaluation de précision mixte de r m où les résultats intermédiaires sont calculés avec un arrondi unitaire ε 2 avant que le résultat final ne soit arrondi (ou tronqué) avec un arrondi unitaire ε 1 . Tous les autres calculs sont supposés être effectués avec un arrondi unitaire ε 1 .
