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