Admin CliCours
Algorithmes numériques
Les opérations
En entier
• Tous les calculs sont exacts tant que que le résultat peut s’exprimer en entier
– float x ; int a,b ; x = a*b ; /* ne change rien */
• En règle général, la division s’effectue dans le type « le plus général », conversion automatique (cast)
– float x ; int a; a= … ; x = 1/a ; /* …. */
– Une cause d’erreur « on ne peut plus classique »
– float x ; int a ; x = 1.0/a ; /* …. */
• En C : 1.0 est double,
• 1.0/a est double,
• le résultat est converti en float !
En virgule flottante
• Les opérations sont réalisées dans des registres plus longs
– N’augmente pas la précision des opérandes
• Additions
– Mise en correspondance des exposants
– Addition des mantisses
– Normalisation du résultat
– Pas de problème sur des variables du même ordre
– a+b=a même si b≠0
– Résultat arrondi
• Multiplication
– Le résultat dans le registre est bon : comme à la main !
• Bonne taille des registres
– Résultat est arrondi
• Les divisions ne sont pas exactes dans le registre
• Il faut mieux décaler les divisions quand c’est possible
• Résultat arrondi
• Les autres opérations
– Algorithmes approchés câblés :
• Développements limités, méthodes de Newton, …
– Algorithmes différents suivant les processeurs
– Résultat arrondi
• « Tous » les calculs en virgule flottante sont approchés
– Sur des nombres approchés
• L’ordre des opérations n’est pas anodin
– Quand il est gérable
• Arithmétique commutative, mais ni associative ni distributive
La norme définit 4 arrondis
• Vers -∞ : (x)plus petit nombre machine≤x
• Vers +∞ : (x) plus petit nombre machine ≥ x
• Vers 0 : = (x) si x ≥ 0 = (x) si x < 0
• Au plus près : on prend le nombre machine le plus proche de x
– Si x au milieu de deux flottants successifs, on prend la mantisse paire – C’est l’arrondi par défaut
• Le choix de l’arrondi n’est pas sans conséquence dans les cas critiques
Gestion des arrondis de l’arithmétique virgule flottante en « C »
#include <stdio.h>
#include <fenv.h> // entetes de la virgule flottante
// pour l’édition de liens :action sur la figure flottante #pragma STDC FENV_ACCESS ON
changement d’arrondi
FE_TONEAREST
FE_TOWARDZERO FE_UPWARD FE_DOWNWARD
sauvegarde de l’arrondi par défaut */
const int originalRounding = fegetround( ); // FE_TONEAREST
fesetround(FE_TOWARDZERO); …
printf(« avec l’arrondi vers 0\n ») ; …
fesetround(FE_UPWARD); …
printf(« avec l’arrondi vers + infini\n ») ; …
fesetround(FE_DOWNWARD); …
printf(« avec l’arrondi vers – infini\n ») ; …
fesetround(originalRounding); // on remet l’arrondi d’origine return 0; }
Soit f(a,b)=333,75b5+a2(11a2b2-b6-121b4-2)+5,5b8+a/2b a=77617 b=33096 extrait de [7]
• en format IBM (en base 16)
– f(a,b) = 1,172603 en SP
– f(a,b) = 1,1726039400531 en DP
• Sur une SUN Sparc
– f(a,b) = -9,875012 1029 en SP
– f(a,b) = -1.180592… 1021 en DP
• Sur la machine de votre serviteur (IEEE 754)
– -7.498167 1029 en SP
Il faut toujours avoir un – -1.180592… 1021 en DP
regard critique
• Résultat théorique : -0,827396……
Les erreurs
• Tous les nombres sont approchés – Tous les calculs sont approchés
– 2 variables ne peuvent être comparées qu’à une erreur près
• Comparer x et x*
– « x = x* » ?
– Erreurs de représentation + erreurs de calcul
• x = x* n’a pas de sens
• Choix d’une précision ε
– |x-x*| < ε : erreur absolue
– x x * : erreur relative
• Une première règle :
– Erreur absolue sur les nombres |x| <1, on parle de précision absolue
– Erreur relative pour les nombres |x|>1, on parle de précision relative
• Équivalent si |x|≈1
• L’important : le nombre de chiffres significatifs (stables)
– Quel que soit l’ordre de grandeur de la variable
• Comment relier la précision au nombre de chiffres significatifs ?
• Un retour arrière : précision absolue de l’ordre de 10-n
– x≈10-n
– x= 0.dddddddddd 10α 3 cas
– α=0 x= 0.dddddddddd nbchif =
– α<0 x= 0.0000dddd dddd nbchif =
– α>0 x= ddd.ddddddd nbchif =
• Le nombre de chiffres dépend de α …
• Un retour arrière : précision relative de l’ordre de 10-n
– | x|/|x|≈10-n
– x= 0.dddddddddd 10α, l’ordre de grandeur de x est 10α-1
Cela revient à étudier avec la précision absolue 10-n . 10α-1 = 10 -(n-α+1)
– α=0 nbchif =
– α<0 nbchif =
– α>0 nbchif =
• En conclusion
– |x| >1 précision relative de 10-n
– |x| <1 précision absolue de 10-m
– La cohérence impose m=n+1
• Test d’arrêt très général
– | x| < εrelative |x| + εabsolue
– Valable si x grand ou non
• Et ramené en nombre de chiffres significatifs stables
– n chiffres significatifs stables
– | x| < 10-n ( |x| + 0.1)
Arithmétique d’intervalle
• Norme IEEE1788 en 2012 ?
• Chaque variable appartient à un intervalle et est notée [v]
– [v]=[v*,v*] = {x/ v* ≤ x ≤ v*}
• Les opérations sont définies sur des intervalles
– [a]+[b] = [a*+b*,a*+b*]
– [a]-[b] = [a*-b*,a*-b*]
– [a]*[b] = [min(a*b*, a*b*, a*b*, a*b*), max(a*b*, a*b*, a*b*, a*b*)]
– [a]/[b] = [a*,a*] * [1/b*,1/b*] si 0∉[b]
• Généralisation aux fonctions continues : exp([v])=[exp(v*),exp(v*)]
– Dépend de la monotonie de la fonction
• La vraie valeur toujours à l’intérieur d’un intervalle : fiable
– Utilisation des arrondis vers –∞ (v*)et +∞ (v*)
• Les limites
– Le temps de calcul
– La taille des intervalles des variables qui croit très vite
– Problème quand 0 est dans l’intervalle
– Surestimation des intervalles
• Ex : P(x) = x-x2
• P([0,1])= [0,1]- [0,1]2 = [0,1]-[0,1] = [-1,1]
• Ou avec P(x) = x(1-x)
• P([0,1])= [0,1]*( 1-[0,1])= [0,1]*[0,1] = [0,1]
• Or le bon intervalle est [0,1/4]
– [a]2 = [min(a*2, a*2), max(a*2, a*2)] si 0∉ [a]
= [0, max(a*2, a*2)] autrement plus précis que [a]*[a] car les bornes sont corrélées
– Il faut éventuellement envisager de réduire les intervalles
Arithmétique stochastique
• Basée sur les travaux de Laporte et Vigne (années 70)
• On perturbe aléatoirement les données et les calculs
– En particulier en jouant sur les règles d’arrondi
• On obtient le nombre de chiffres significatifs stables obtenus en comparant les résultats
– Nombre de chiffres obtenu avec très peu de tirages en pratique ( ≈ 3)
– Permet de statuer sur :
• une variable sans chiffres significatifs
• 2 variables stochastiquement équivalentes (tous les chiffres stables sont identiques)
• Nombre de chiffres significatifs du résultat du code donné
– CADNA : http://www.lip6.fr/cadna
– Existe pour MPI et GPU
– Beaucoup plus long, plus de mémoire, mais fiable.
Première partie : Les bases de l’algorithmique numérique
• Généralités
• Les nombres sur l’ordinateur
• Les calculs sur ordinateur
• Les erreurs, les chiffres significatifs, les tests
• les arithmétiques alternatives
• Considérations algorithmiques
Deuxième partie : Equations non linéaires
• Racine d’une équation
• Evaluation d’un polynôme
• Dichotomie
• Méthode de Newton
• Localisation des racines
• Méthode de Bairstow
Troisième partie : Systèmes d’équations linéaires
• Généralités et définitions
• Méthodes directes
– Méthode de Gauss
– Méthode du LU
– Méthode de Cholesky
• Méthodes itératives
• Problèmes aux moindres carrés
• Résolution aux moindres carrés
Quatrième partie : Différentiation et Intégration numériques
• Approximation par un polynôme
• Différentiation numérique
• Intégration numérique
• Intégrales multiples
Cinquième partie : Interpolation – Approximation – Lissage :notions
• Problème
• Interpolation
• Meilleure approximation
• Lissage
Conclusion
Bibliographie succincte
Télécharger le cours complet
