Ce document de Travaux Dirigés (TD) est destiné aux étudiants universitaires des filières scientifiques. Il propose une série d'exercices visant à renforcer les compétences fondamentales en Analyse Numérique et en Algèbre Linéaire.
Il couvre les notions suivantes:
- Les concepts algorithmiques et la représentation des nombres (binaire, virgule flottante).
- Les limites inhérentes au calcul numérique (non-associativité, instabilité).
- Les normes matricielles, le rayon spectral et le conditionnement des matrices.
Introduction générale à l'Analyse Numérique : Travaux Dirigés
Ce document présente une série d'exercices d'introduction à l'analyse numérique, préparés par H. DOUZI de la Faculté des Sciences d'Agadir, dans le cadre du TD n°1 pour les filières SMA4, SM14 et SMP4 (édition 2017). Les exercices couvrent des concepts fondamentaux tels que les algorithmes, la représentation des nombres et les limites du calcul numérique.
Exercice 1 : Notion d'Algorithme
Question 1 : Évaluation de polynômes
On cherche à calculer la valeur d'un polynôme P(x) = anxn + an-1xn-1 + ... + a1x1 + a0 en un point donné x0 à partir de ses coefficients ai.
- Combien de multiplications sont nécessaires pour calculer P(x0) en utilisant la méthode directe (calcul terme par terme) ?
- La méthode de Horner est proposée pour évaluer P(x0). Calculer à nouveau le nombre de multiplications nécessaires avec cette méthode. La méthode de Horner factorise le polynôme sous la forme P(x) = a0 + x(a1 + x(a2 + ... + x(an-1 + x an)...)).
- Décrire un algorithme récursif pour la méthode de Horner. Un algorithme peut être décrit par des étapes séquentielles ou un pseudocode.
Question 2 : Algorithmes de Tri
Proposer deux algorithmes pour ordonner la suite des nombres entiers suivante : 6, 7, 9, 2, 1, 4, 3, 5, 0, 8.
- Le premier algorithme nécessite un nombre d'opérations élémentaires de l'ordre de 210.
- Le deuxième algorithme nécessite un nombre d'opérations élémentaires de l'ordre de 10 log(10) (où le logarithme est en base 2 ou naturelle, selon le contexte habituel de complexité algorithmique).
Note : Ces valeurs de complexité (210 et 10 log(10)) sont spécifiques pour une liste de 10 éléments, faisant référence à des algorithmes de tri de complexité O(n2) et O(n log n) pour n=10.
Exercice 2 : Système Binaire et Système Décimal
Question 1 : Représentation binaire de nombres décimaux
Représenter les nombres décimaux suivants en base 2 (binaire) :
- (255)10
- (2354)10
- (9,90625)10
- (0,0234)10
Question 2 : Équivalent décimal de nombres binaires
Donner l'équivalent décimal des nombres binaires suivants :
- (1010)2
- (11000001)2
- (0010110)2
- (101,00110)2
- (1111,1111)2
Exercice 3 : Représentation en Virgule Flottante
Question 1 : Calcul des bornes et du nombre de représentations
On considère la représentation en virgule flottante dans la base b avec une mantisse de longueur p et un exposant e vérifiant : M1 ≤ e ≤ M2. On suppose que : b = 2, p = 8, M1 = -64, M2 = 63.
- Calculer le plus petit et le plus grand nombre pouvant s'exprimer dans cette représentation (en excluant les cas dénormalisés ou l'infini, si non spécifié).
- Calculer le nombre de rationnels pouvant être représentés avec ces paramètres.
Question 2 : Expression binaire et flottante d'un nombre
Soit x = (2,8)10.
- Donner l'expression binaire de x.
- Donner son expression avec une représentation à virgule flottante : mantisse de longueur 9 et exposant compris entre -10 et 10.
Exercice 4 : Limites du Calcul Numérique
Question 1 : Phénomène de non-associativité
Calculer x + (y + z) et (x + y) + z en utilisant l'arithmétique flottante à 3 chiffres (troncature ou arrondi, à préciser si nécessaire) avec les nombres suivants : x = 0,854 × 103, y = 0,251, et z = 0,852 × 103.
Quelles sont vos remarques et conclusions concernant le résultat ?
Question 2 : Phénomène de compensation
On considère l'expression E = √(1+x) - √x avec x > 0. Calculer, sous Matlab (ou avec une calculatrice), la valeur de E pour x = 109, puis pour x = 1016.
On remarque que l'expression peut être réécrite de manière équivalente pour éviter la perte de précision : E = 1 / (√(1+x) + √x). En utilisant cette nouvelle formule, refaire les calculs.
Quelle conclusion tirez-vous de la comparaison des résultats ?
Question 3 : Phénomènes d'instabilité numérique
Calcul de l'exponentielle ex en utilisant la série de Taylor : ex = ∑n=0∞ (xn / n!).
Le tableau suivant montre les valeurs exactes de ex et les approximations obtenues en sommant la série de Taylor jusqu'à n=14 pour différentes valeurs de x négatives :
| x | Exp(x) exact | Somme, n=14 |
|---|---|---|
| -10 | 4,54 × 10-5 | 4,54 × 10-5 |
| -15 | 3,06 × 10-7 | 3,05 × 10-7 |
| -20 | 2,06 × 10-9 | -1,55 × 10-7 |
| -25 | 1,39 × 10-11 | 1,87 × 10-5 |
| -30 | 9,36 × 10-14 | 6,25 × 10-4 |
Que remarquez-vous sur ce tableau ? Comment expliquez-vous ces observations ? (Indice : Considérez les erreurs d'arrondi et la soustraction de nombres très grands).
Rappels et Compléments sur l'Algèbre Linéaire
Cette section aborde des concepts fondamentaux d'algèbre linéaire, notamment les normes matricielles, le rayon spectral et le conditionnement des matrices.
Exercice 1 : Normes Matricielles
- Soit Id la matrice identité de ℚn × n. Montrer que pour toute norme matricielle on a ‖Id‖ ≥ 1, et que pour toute norme matricielle induite on a ‖Id‖ = 1.
- Soit A = (aij) ∈ ℚn × n, avec 1 ≤ i, j ≤ n. On définit la norme de Schur par : ‖A‖S = ( ∑i=1n ∑j=1n |aij|2 )1/2. Montrer que ‖.‖S est une norme matricielle non induite pour n > 1.
Exercice 2 : Rayon Spectral
Soient les matrices A et B suivantes :
A = [[1, 1], [1, 1]] et B = [[1, 0], [1, 1]]
Calculer le rayon spectral de A et B.
Note : Le rayon spectral d'une matrice est le maximum des modules de ses valeurs propres.
Exercice 3 : Conditionnement des Matrices
Question 1 : Calcul du conditionnement
On considère le système linéaire Ax = b avec la matrice A et le vecteur b suivants :
A = [[100, 6], [0, 1]] et b = [[10], [6]]
- Calculer le conditionnement de la matrice A pour les normes 1, 2 et ∞ (cond1(A), cond2(A) et cond∞(A)).
- On perturbe le système. Considérons deux cas pour Δb :
Δb1 = [[1], [0]] et Δb2 = [[6], [2]].
Calculer les nouvelles solutions x + Δx pour chaque perturbation et vérifier les majorations des variations relatives : ‖Δx‖ / ‖x‖.
Question 2 : Analyse d'un système perturbé
Soit le système linéaire : [[1.0001, 65000], [0.0005, 6]] × [[x1], [x2]] = [[5], [5]]
La solution exacte est x = [[5], [5]].
- Trouver la nouvelle solution du système (x + Δx) lorsque l'on remplace le membre de droite du système (b) par b + Δb = [[6], [6]]. (On utilisera b = [[5], [5]] de la question précédente pour calculer Δb).
- Calculer les valeurs de ‖Δb‖∞ / ‖b‖∞ et ‖Δx‖∞ / ‖x‖∞. Que peut-on conclure sur la sensibilité de la solution à la perturbation ?
- Calculer le conditionnement de ce système pour la norme ∞ (cond∞(A)) et vérifier la relation des majorations des perturbations.
- Donner une interprétation géométrique du conditionnement du système.
Foire Aux Questions (FAQ) sur l'Analyse Numérique
Qu'est-ce que l'analyse numérique ?
- L'analyse numérique est une branche des mathématiques qui conçoit, analyse et met en œuvre des algorithmes pour résoudre des problèmes de mathématiques continues (fonctions, équations différentielles, intégrales, etc.) souvent rencontrés en science et ingénierie, en utilisant des approximations numériques.
Pourquoi la méthode de Horner est-elle souvent préférée pour l'évaluation de polynômes ?
- La méthode de Horner est préférée car elle réduit considérablement le nombre de multiplications nécessaires pour évaluer un polynôme par rapport à la méthode directe (terme par terme). Cela améliore non seulement l'efficacité computationnelle (rapidité) mais aussi la précision des calculs en minimisant l'accumulation des erreurs d'arrondi.
Quels sont les principaux phénomènes limitant la précision du calcul numérique ?
- Les principaux phénomènes incluent :
- La non-associativité de l'arithmétique flottante, où l'ordre des opérations peut changer le résultat.
- La compensation ou l'annulation catastrophique, qui se produit lors de la soustraction de nombres très proches, entraînant une perte significative de chiffres significatifs.
- L'instabilité numérique, où de petites erreurs initiales (par exemple, erreurs d'arrondi) peuvent s'amplifier de manière incontrôlable au cours des calculs, rendant le résultat final inexact.