1.6 L’erreur n’est pas seulement humaine
29
0
10
20
30
40
50
10
−15
10
−10
10
−5
10
0
0
10
20
30
40
50
0
0.05
0.1
0.15
0.2
0.25
0.3
0.35
0.4
0.45
Figure 1.8. Erreurs e
x
n (traits pleins), e
y
n (traits discontinus) et e
z
n (traits
mixtes) en échelle semi-logarithmique (à gauche) et linéaire-linéaire (à droite)
log(e
x
n ) C 1 + log(ρ x )n,
log(e
y
n ) C 2 + log(ρ y )n
2 ,
log(e
z
n ) C 3 + log(ρ z )n
3 ,
c’est-à-dire une ligne droite, une parabole et une cubique, comme on
peut le voir sur la Figure 1.8, à gauche.
La commande MATLAB pour utiliser l’échelle semi-logharitmique
est semilogy(x,y), où x et y sont des tableaux de même taille.
semilogy
Sur la Figure 1.8, à droite, on a représenté à l’aide de la commande
plot les erreurs e
x
n , e
y
n et e
z
n en fonction des itérations en échelle linéairelinéaire. Il est clair que l’usage d’une échelle semi-logarithmique est plus
appropriée dans ce cas.
1.6.1 Parlons de coûts
En général, un problème est résolu sur un ordinateur à l’aide d’un algorithme, qui est une procédure se présentant sous la forme d’un texte qui
spécifie l’exécution d’une séquence finie d’opérations élémentaires.
Le coût de calcul d’un algorithme est le nombre d’opérations en virgule flottante requises pour son exécution. On mesure souvent la vitesse
d’un ordinateur par le nombre maximum d’opérations en virgule flottante qu’il peut effectuer en une seconde (en abrégé flops). Les abréviations suivantes sont couramment utilisées : Mega-flops pour 10
6 flops,
Giga-flops pour 10
9 flops, Tera-flops pour 10
12 flops, Peta-flops pour
10
15 flops. Les ordinateurs les plus rapides atteignent actuellement 1.7
Peta-flops.
En général, il n’est pas essentiel de connaître le nombre exact d’opérations effectuées par un algorithme. Il est suffisant de se contenter de
l’ordre de grandeur en fonction d’un paramètre d relié à la dimension
du problème. On dit qu’un algorithme a une complexité constante s’il
requiert un nombre d’opérations indépendant de d, i.e. O(1) opérations.
On dit qu’il a une complexité linéaire s’il requiert O(d) opérations, ou,
29
0
10
20
30
40
50
10
−15
10
−10
10
−5
10
0
0
10
20
30
40
50
0
0.05
0.1
0.15
0.2
0.25
0.3
0.35
0.4
0.45
Figure 1.8. Erreurs e
x
n (traits pleins), e
y
n (traits discontinus) et e
z
n (traits
mixtes) en échelle semi-logarithmique (à gauche) et linéaire-linéaire (à droite)
log(e
x
n ) C 1 + log(ρ x )n,
log(e
y
n ) C 2 + log(ρ y )n
2 ,
log(e
z
n ) C 3 + log(ρ z )n
3 ,
c’est-à-dire une ligne droite, une parabole et une cubique, comme on
peut le voir sur la Figure 1.8, à gauche.
La commande MATLAB pour utiliser l’échelle semi-logharitmique
est semilogy(x,y), où x et y sont des tableaux de même taille.
semilogy
Sur la Figure 1.8, à droite, on a représenté à l’aide de la commande
plot les erreurs e
x
n , e
y
n et e
z
n en fonction des itérations en échelle linéairelinéaire. Il est clair que l’usage d’une échelle semi-logarithmique est plus
appropriée dans ce cas.
1.6.1 Parlons de coûts
En général, un problème est résolu sur un ordinateur à l’aide d’un algorithme, qui est une procédure se présentant sous la forme d’un texte qui
spécifie l’exécution d’une séquence finie d’opérations élémentaires.
Le coût de calcul d’un algorithme est le nombre d’opérations en virgule flottante requises pour son exécution. On mesure souvent la vitesse
d’un ordinateur par le nombre maximum d’opérations en virgule flottante qu’il peut effectuer en une seconde (en abrégé flops). Les abréviations suivantes sont couramment utilisées : Mega-flops pour 10
6 flops,
Giga-flops pour 10
9 flops, Tera-flops pour 10
12 flops, Peta-flops pour
10
15 flops. Les ordinateurs les plus rapides atteignent actuellement 1.7
Peta-flops.
En général, il n’est pas essentiel de connaître le nombre exact d’opérations effectuées par un algorithme. Il est suffisant de se contenter de
l’ordre de grandeur en fonction d’un paramètre d relié à la dimension
du problème. On dit qu’un algorithme a une complexité constante s’il
requiert un nombre d’opérations indépendant de d, i.e. O(1) opérations.
On dit qu’il a une complexité linéaire s’il requiert O(d) opérations, ou,