Algorithmes numériques

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*)

Arithmétiques alternatives 

•  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
•  La valeur d'une variable est de la forme a/b –  a et b entiers –  Premiers entre eux (forme irréductible)
•  Les calculs sont effectués sur des fractions rationnelles –
•  Les fonctions mathématiques sont codées en rationnel
•  Les limites –  Ne représente pas tous les rationnels –  L'ensemble Q n'est pas l'ensemble R –  Calculs très lents