Ce document, premier d'une série de Travaux Dirigés (TD n°1), propose une introduction générale à l'Analyse Numérique. Il est destiné aux étudiants universitaires souhaitant aborder les concepts fondamentaux.
Il couvre les notions suivantes :
- Les algorithmes fondamentaux tels que l'évaluation de polynômes (Horner) et les méthodes de tri, incluant leur complexité.
- La représentation des nombres entiers et fractionnaires en diverses bases.
- Les principes de la représentation en virgule flottante.
- L'analyse de la sensibilité des systèmes linéaires aux perturbations (conditionnement).
TD n°1 (Introduction générale à l'Analyse Numérique)
Exercice 1 : Algorithmes fondamentaux
1. Algorithme de Horner pour l'évaluation de polynômes
L'algorithme de Horner est une méthode efficace pour évaluer un polynôme de la forme P(x) = anxn + an-1xn-1 + ... + a1x + a0.
- Le nombre de multiplications avec l'évaluation naïve est n(n+1)/2, soit O(n²).
- Avec l'algorithme de Horner, le nombre de multiplications est réduit à n, soit O(n).
- Algorithme :
Initialiser une variable P à P = an.
Pour k variant de n-1 à 0, répéter : P = P * x + ak.
2. Exemples d'algorithmes de tri
Les algorithmes de tri permettent d'organiser les éléments d'une liste dans un ordre spécifique.
a. Tri à bulles
Le tri à bulles consiste à faire remonter progressivement les plus grands éléments d'une liste, de la même manière que les bulles d'air remontent à la surface d'un liquide. Le nombre d’opérations de comparaison-échange dans cet algorithme est n(n+1)/2, ce qui correspond à une complexité en O(n²).
b. Tri rapide (Quicksort)
Le tri rapide est une méthode qui consiste à placer un élément d'un tableau à trier (appelé pivot) à sa position finale. Pour ce faire, tous les éléments inférieurs au pivot sont déplacés à sa gauche, et tous les éléments supérieurs à sa droite. Cette opération est appelée partitionnement. Ce processus est ensuite répété récursivement sur les sous-tableaux ainsi créés, jusqu'à ce que l'ensemble des éléments soit trié. Le nombre d’opérations de comparaison-échange, lorsqu'on a une liste désordonnée complète de 1 à n, est en moyenne n log₂(n), soit O(n log(n)).
Systèmes de numération
Exercice 2 : Conversion de bases
1. Nombres entiers
Pour convertir un nombre entier de la base 10 à la base 2, on peut décomposer le nombre en somme de puissances de 2, ou utiliser la méthode des divisions euclidiennes successives par 2.
- Exemples par décomposition :
127 = 64 + 32 + 16 + 8 + 4 + 2 + 1 = (1111111)2
2354 = 2048 + 256 + 32 + 16 + 2 = (100100110010)2
27 = 16 + 8 + 2 + 1 = (11011)2 - Autre méthode : Division euclidienne successive par 2
Pour convertir 27 en base 2 :
| Nombre initial | Quotient de la division euclidienne par 2 | Reste de la division euclidienne par 2 |
|---|---|---|
| 27 | 13 | 1 |
| 13 | 6 | 1 |
| 6 | 3 | 0 |
| 3 | 1 | 1 |
| 1 | 0 | 1 |
La lecture des restes de bas en haut donne (11011)2.
2. Nombres fractionnaires
La partie entière d'un nombre fractionnaire est traitée comme pour les nombres entiers. Pour la partie fractionnaire, on utilise des multiplications successives par 2. On obtient alors soit une suite binaire finie, soit une suite binaire infinie mais périodique.
Exemple pour 0,245 :
| Partie fractionnaire avant multiplication par 2 | Partie entière après multiplication par 2 |
|---|---|
| 0,245 | 0 |
| 0,49 | 0 |
| 0,98 | 1 |
| 0,96 | 1 |
| 0,92 | 1 |
| 0,84 | 1 |
| 0,68 | 1 |
| … | … |
Ainsi, 0,245 = (0,0011111...)2.
3. Passage de la base 2 à la base 10
Pour le passage de la base 2 à la base 10, on développe directement les puissances de 2 (positives pour la partie entière, négatives pour la partie fractionnaire).
Exemple : (101,00110)2 = 1*2² + 0*2¹ + 1*2⁰ + 0*2⁻¹ + 0*2⁻² + 1*2⁻³ + 1*2⁻⁴ + 0*2⁻⁵ = 4 + 0 + 1 + 0 + 0 + 1/8 + 1/16 + 0 = 5 + 0,125 + 0,0625 = 5,1875.
Représentation des nombres en machine
Exercice 3 : Représentation en virgule flottante
La représentation en virgule flottante permet de stocker des nombres réels avec une précision et une étendue dynamiques.
- La forme générale d'un nombre x en virgule flottante est : x = ± 2e * 0,C1C2...Cp, avec -64 ≤ e ≤ 63 et p=8. La condition C1 ≠ 0 est requise si x ≠ 0 pour une forme normalisée.
- Le plus petit nombre positif représentable est x = 2-64 * 0,1. Le plus grand nombre positif est x = 263 * 0,11111111.
- Le nombre de cas possibles pour cette représentation (x ≠ 0) est :
2 possibilités pour le signe (positif ou négatif)
128 possibilités pour l'exposant e (de -64 à 63)
27 possibilités pour la mantisse (C1 étant fixe à 1 si normalisé, les 7 autres bits C2...C8 varient).
Le total des cas possibles est donc 2 * 128 * 27 = 2 * 27 * 27 = 215.
En ajoutant le cas x=0, le nombre total de cas est 215 + 1. - Exemple : x = (2,8)10 = (10,11001100...)2.
Pour le représenter en virgule flottante normalisée (0,1...), on décale la virgule :
(10,11001100...)2 = (0,1011001100...)2 * 22.
Donc, x ≈ 22 * 0,101100110. Ici, l'exposant e est 2.
Rappels et compléments d'Algèbre Linéaire
Exercice 4 : Analyse de la sensibilité des systèmes linéaires
Cet exercice explore la sensibilité des solutions de systèmes linéaires aux perturbations des données d'entrée, un concept clé en analyse numérique.
1. Exercice 2 : Calcul de normes (implicite)
Ce type d'exercice implique généralement des calculs directs liés aux normes vectorielles ou matricielles.
2. Exercice 3 : Analyse de conditionnement
Ce calcul est similaire aux concepts abordés dans la partie précédente.
3. Étude d'un système linéaire ill-conditionné
Considérons le système linéaire suivant :
((5,0001 1)
(1 1)) * ((x1)
(x2)) = ((6)
(6))
La solution de ce système est :
((x1)
(x2)) = ((0)
(6))
a. Perturbation du second membre
Pour une petite perturbation sur le second membre b, nous observons :
||Δb||∞ / ||b||∞ = 0,0005 / 6,0005 ≈ 8,3326 × 10-5.
Et pour la solution x, nous avons :
||Δx||∞ / ||x||∞ = 5 / 15 = 1/3 ≈ 0,3333.
On constate que la variation relative de x est beaucoup plus grande que celle de b. Autrement dit, une petite variation sur le second membre peut produire une grande variation sur la solution.
b. Nombre de conditionnement
En posant la matrice A = ((5,0001 1)
(1 1)) et son inverse A-1 ≈ ((1 -1)
(-1 5,0001)) / 4,0001.
Le nombre de conditionnement en norme infinie est Cond∞(A) = ||A||∞ * ||A-1||∞.
Ici, Cond∞(A) = 120002.
Nous vérifions la relation de majoration des perturbations :
||Δx||∞ / ||x||∞ ≤ Cond∞(A) * (||Δb||∞ / ||b||∞)
0,3333 ≤ 120002 * (8,3326 × 10-5) ≈ 9,9993.
L'inégalité est bien respectée, illustrant l'amplification des erreurs par un mauvais conditionnement.
c. Interprétation géométrique
La solution d'un système linéaire représente le point d'intersection des droites définies par les équations du système. Dans ce cas, les deux droites sont presque parallèles. Une petite perturbation de b (qui se traduit géométriquement par une petite translation d'une droite par rapport à l'autre) engendre une grande translation du point d'intersection, et donc une grande variation de la solution. Le cas idéal se produit lorsque les deux droites sont perpendiculaires (correspondant à une matrice orthogonale), où le conditionnement est égal à 1 et les perturbations de b et de x restent du même ordre de grandeur.
FAQ sur l'Analyse Numérique
Qu'est-ce que l'algorithme de Horner et à quoi sert-il ?
L'algorithme de Horner est une méthode optimisée pour évaluer la valeur d'un polynôme pour une valeur donnée de x. Il réduit le nombre de multiplications nécessaires de O(n²) à O(n), ce qui le rend beaucoup plus efficace pour les polynômes de haut degré.
Quelle est la principale différence de performance entre le tri à bulles et le tri rapide ?
La principale différence réside dans leur complexité algorithmique. Le tri à bulles a une complexité en O(n²), ce qui signifie que son temps d'exécution augmente quadratiquement avec la taille de la liste. Le tri rapide a une complexité moyenne en O(n log(n)), ce qui le rend beaucoup plus rapide pour les grandes listes.
Comment les nombres fractionnaires sont-ils convertis en binaire ?
Pour convertir la partie fractionnaire d'un nombre décimal en binaire, on utilise des multiplications successives par 2. À chaque multiplication, la partie entière du résultat (qui sera 0 ou 1) devient le bit binaire suivant après la virgule. Ce processus se poursuit jusqu'à ce que la partie fractionnaire devienne zéro ou jusqu'à atteindre la précision souhaitée, pouvant donner une suite binaire finie ou infinie et périodique.