Ce document présente la correction détaillée de l'examen d'Analyse Numérique (SMA4-SMI4, session de rattrapage Juin 2015), destiné aux étudiants universitaires. Il vise à consolider leur compréhension des méthodes numériques fondamentales et des concepts clés.
Il couvre les notions suivantes:
- Les définitions et l'utilisation du conditionnement d'une matrice et des normes matricielles.
- La décomposition LU de matrices pour la résolution de systèmes linéaires, incluant les conditions d'existence.
- L'application de la méthode de Steffensen pour les problèmes non linéaires, son ordre de convergence et ses avantages.
Questions de cours
1. Définition et utilité du conditionnement d'une matrice
Le conditionnement d'une matrice A, pour une norme matricielle donnée notée ||.||, est défini comme le produit de la norme de A par la norme de son inverse : Cond(A) = ||A|| * ||A⁻¹||.
Il mesure la sensibilité des solutions d'un système linéaire Ax = b aux petites perturbations des données A et b. Un conditionnement élevé indique que le système est mal conditionné, rendant les solutions très sensibles aux erreurs de calcul ou aux imprécisions des données.
2. Définition des normes matricielles subordonnées
Pour une matrice A = (aij) de taille n x n :
- La norme 1 (norme colonne maximale) : ||A||₁ = max1 ≤ j ≤ n (∑1 ≤ i ≤ n |aij|). Elle correspond à la somme maximale des valeurs absolues des éléments de chaque colonne.
- La norme infinie (norme ligne maximale) : ||A||∞ = max1 ≤ i ≤ n (∑1 ≤ j ≤ n |aij|). Elle correspond à la somme maximale des valeurs absolues des éléments de chaque ligne.
- La norme 2 (norme spectrale) : ||A||₂ = √(ρ(A*A)), où ρ(M) est le rayon spectral de la matrice M (la plus grande valeur propre en module), et A* est la transconjugée de A.
Problème 1 : Système linéaire
1. Pourquoi la matrice A n'admet-elle pas de décomposition LU ?
Une matrice A admet une décomposition LU sans permutation si et seulement si tous ses mineurs principaux de tête (déterminants des sous-matrices carrées supérieures gauches) sont non nuls. Dans ce cas, il est indiqué que deux des déterminants principaux de la matrice A sont nuls, à savoir Δ₂ = 0 et Δ₃ = 0. Cette condition empêche la décomposition LU directe.
2. Proposition d'une permutation pour une décomposition LU
En permutant la deuxième et la quatrième ligne de la matrice A, on obtient la matrice B :
B = [[1, 1, 1, 1], [1, 2, 4, 4], [1, 1, 3, 3], [1, 2, 2, 4]]
Les déterminants principaux de la matrice B sont calculés comme suit :
- Δ₁ = 1
- Δ₂ = det([[1, 1], [1, 2]]) = 1
- Δ₃ = det([[1, 1, 1], [1, 2, 4], [1, 1, 3]]) = 2
- Δ₄ = det(B) = 2
Puisque tous les mineurs principaux de B sont non nuls, la matrice B admet une décomposition LU.
3. Calcul de la décomposition LU de B
La décomposition LU de la matrice B est donnée par les matrices L et U suivantes :
L = [[1, 0, 0, 0], [1, 1, 0, 0], [1, 0, 1, 0], [1, 2, 1/2, 1]]
U = [[1, 1, 1, 1], [0, 1, 3, 3], [0, 0, 2, 2], [0, 0, 0, 2]]
4. Résolution du système Bx = b'
La permutation de la 2e et 4e ligne, appliquée au vecteur b = [1, 2, 3, 4]T, donne le vecteur b' = [1, 4, 3, 2]T.
Nous résolvons le système Ly = b' puis Ux = y.
Pour Ly = b', avec L = [[1, 0, 0, 0], [1, 1, 0, 0], [1, 0, 1, 0], [1, 2, 1/2, 1]] et b' = [1, 4, 3, 2]T, le calcul fournit la solution y = [1, 4, 7, 6]T.
Pour Ux = y, avec U = [[1, 1, 1, 1], [0, 1, 3, 3], [0, 0, 2, 2], [0, 0, 0, 2]] et y = [1, 4, 7, 6]T, le calcul fournit la solution x = [1, 4, 5, 2]T.
Problème 2 : Problème non linéaire
1. Calcul d'une limite pour la méthode de Steffensen
Nous devons calculer limx→α (f(x + f(x)) - f(x)) / f(x).
Puisque f est continument dérivable (f ∈ C¹(I)) et f(α) = 0, lorsque x tend vers α, f(x) tend vers 0.
Posons h = f(x). Lorsque x → α, h → 0.
L'expression devient : limh→0 (f(α + h) - f(α)) / h.
Par définition de la dérivée, cette limite est égale à f'(α).
2. Déduction que g est une méthode de point fixe
Une méthode est de point fixe si le point recherché (la racine α) est un point fixe de la fonction d'itération g, c'est-à-dire si g(α) = α.
La méthode de Steffensen est définie par g(x) = x - (f(x))² / (f(x + f(x)) - f(x)).
Lorsque x = α, nous avons f(α) = 0. En substituant dans l'expression de g(α) :
g(α) = α - (f(α))² / (f(α + f(α)) - f(α)) = α - 0² / (f(α) - f(α)) = α - 0/0.
Cette forme est indéterminée. En utilisant le résultat de la question précédente :
limx→α g(x) = α - limx→α f(x) / [(f(x + f(x)) - f(x)) / f(x)]
= α - 0 / f'(α) = α (car f'(α) ≠ 0).
Donc, g(α) = α. La racine α de f est bien un point fixe de g.
3. Calcul de g'(α) et ordre de convergence
La méthode de Steffensen est connue pour avoir un ordre de convergence quadratique.
Pour démontrer cela, il faut calculer g'(α). La formule de g(x) est g(x) = x - f(x)² / (f(x + f(x)) - f(x)).
Un calcul détaillé de la dérivée g'(x) et son évaluation en α montre que g'(α) = 0. La condition f'(α) ≠ 0 est cruciale ici.
Puisque g'(α) = 0 et g''(α) ≠ 0 (ce qui est généralement le cas pour f''(α) ≠ 0), l'ordre de convergence de la méthode de Steffensen est de 2 (convergence quadratique).
4. Avantage de la méthode de Steffensen sur celle de Newton
L'avantage principal de la méthode de Steffensen par rapport à la méthode de Newton est qu'elle n'exige pas le calcul de la dérivée de la fonction f, f'(x).
Elle maintient un ordre de convergence quadratique (comme Newton), en approximant la dérivée par une différence finie (f(x + f(x)) - f(x)) / f(x), ce qui est particulièrement utile lorsque la dérivée est difficile ou coûteuse à calculer analytiquement.
FAQ - Questions Fréquentes
1. Quand peut-on utiliser la décomposition LU d'une matrice ?
La décomposition LU d'une matrice A est principalement utilisée pour résoudre des systèmes linéaires, calculer l'inverse d'une matrice ou son déterminant. Elle peut être appliquée à toute matrice carrée dont tous les mineurs principaux sont non nuls. Si certains mineurs sont nuls, une permutation des lignes (ou colonnes) est nécessaire, menant alors à une décomposition PLU.
2. Quel est l'intérêt du conditionnement d'une matrice ?
Le conditionnement d'une matrice est crucial pour évaluer la fiabilité des solutions obtenues par des méthodes numériques. Un nombre de conditionnement élevé indique que le système linéaire est "mal conditionné", signifiant que de petites erreurs dans les données d'entrée (matrice A ou vecteur b) peuvent entraîner de très grandes erreurs dans la solution x. Il permet donc de prédire la stabilité numérique des algorithmes de résolution.
3. La méthode de Steffensen converge-t-elle toujours ?
Comme la plupart des méthodes de point fixe, la convergence de la méthode de Steffensen n'est pas garantie pour toute fonction et toute condition initiale. Elle nécessite que la fonction g(x) soit contractante dans un voisinage de la racine. Cependant, elle est souvent plus rapide que la méthode de Newton si le point initial est proche de la racine et que le calcul de la dérivée est évité.