Ce document propose le corrigé de l'examen final d'Analyse Numérique du 1er février 2016, destiné aux étudiants universitaires. Il a pour objectif de consolider les connaissances sur les principales méthodes de résolution numérique.
Il aborde notamment les sujets suivants :
- La recherche de racines d'équations non linéaires et les critères de convergence des méthodes de point fixe.
- L'analyse des matrices (définie positivité, décomposition de Cholesky) pour la résolution de systèmes linéaires.
- Les méthodes itératives comme Gauss-Seidel, avec un examen de leurs conditions de convergence.
Université Annaba - Correction d'Examen : Analyse Numérique (01 février 2016)
Ce document présente la correction détaillée de l'examen final d'Analyse Numérique du 1er février 2016, destiné aux étudiants du Département MI2 de l'EP ST Annaba pour l'année universitaire 2015-2016. Il couvre des concepts fondamentaux des méthodes numériques, incluant les méthodes de point fixe, la décomposition de Cholesky pour la résolution de systèmes linéaires, et la méthode itérative de Gauss-Seidel.
Exercice 1 : Méthodes de Point Fixe
Puisque la fonction f est continue sur l’intervalle [0,1] et que f(0) < 0 tandis que f(1) > 0, alors, d’après le Théorème des valeurs intermédiaires, il existe un α dans ]0,1[ tel que f(α) = 0. L’unicité de α résulte du fait que la fonction f est strictement monotone, car sa dérivée f'(x) = ex + 3 / (2√x) est strictement positive pour tout x dans ]0,1].
Analyse de la fonction g1
Considérons la fonction g1. On observe qu'elle est définie seulement sur le sous-intervalle [0, 4/9[, qui contient la racine α de la fonction f. Calculons la dérivée de g1 : g'1(x) = -3 / (2√x * (2 - 3√x)). Posons h(x) = |g'1(x)| = 3 / (2√x * |2 - 3√x|), pour x dans ]0, 4/9[.
On constate que limx→0 h(x) = +∞ et limx→4/9 h(x) = +∞. La dérivée h'(x) = (3 / (2√x)) * ((2√x - 3x) / (3√x - 1)2) s'annule pour x = 1/9. En ce point, h(1/9) = |g'1(1/9)| = 9/2, ce qui est strictement supérieur à 1.
Par conséquent, on peut conclure que |g'1(x)| ≥ 1 (plus précisément > 1 sur une partie de l'intervalle) pour tout x dans ]0, 4/9[. En particulier, |g'1(α)| > 1, et donc la méthode de point fixe correspondante ne convergera pas vers le point fixe α, même pas localement.
Analyse de la fonction g2
Pour la fonction g2, on observe que sa dérivée est g'2(x) = d/dx ( (2 - ex)2 / 9 ) = (2/9) * ex * (ex - 2). Sa dérivée seconde est g''2(x) = (4/9) * ex * (ex - 1), qui est supérieure ou égale à 0 pour tout x dans [0,1].
Le supremum de la valeur absolue de la dérivée est sup0≤x≤1 |g'2(x)| = |(2/9) * ex * (ex - 2)| ≤ (2/9) * e * (e - 2) = k. En calculant cette valeur, on trouve que k < 1. Cela signifie que g2 est strictement contractante sur l'intervalle [0,1].
Le tableau de variation de la fonction g2 montre qu'elle est stable sur l’intervalle [0,1]. En effet, g2 décroît de g2(0) = 1/9 à un minimum en x = ln(2) où g2(ln(2)) = 0, puis croît jusqu'à g2(1) = (2/9)e(e-2). Puisque g2([0,1]) ⊆ [0, 1/9] et que [0, 1/9] ⊆ [0,1], la fonction est stable.
En conséquence, la méthode basée sur g2 est convergente ; elle est donc la méthode à choisir.
Itérations de la méthode de point fixe avec g2
Notons g(x) = g2(x) = (2 - ex)2 / 9. La suite d'approximations (xn) est générée par le schéma itératif : x0 = 0, et xn+1 = g(xn) pour n = 0, 1, 2, ....
Puisque g est stable et strictement contractante sur l’intervalle [0,1], la suite (xn) converge vers l’unique point fixe α qui vérifie l’équation f(α) = 0, et ceci pour tout choix de x0 dans [0,1].
Le test d'arrêt est défini par |xn - α| ≤ ε = 10-6. Le nombre d'itérations n nécessaire est estimé par la formule n ≥ (ln(ε) - ln(b-a)) / ln(k) ≈ 16.546. Ainsi, il faut n = 17 itérations pour atteindre la précision souhaitée.
Les quatre premières itérations sont :
x1 = 0.111111111111111x2 = 0.086530288226025x3 = 0.091933394716623x4 = 0.090743167695529
La solution approchée du point fixe est donc α ≈ 0.09.
Exercice 2 : Décomposition de Cholesky
Il est évident que la matrice A est symétrique (A = AT). Pour vérifier qu'elle est définie positive, nous appliquons le Théorème de Sylvester en calculant les mineurs principaux :
- Le premier mineur principal :
Δ1 = 2 > 0. - Le deuxième mineur principal :
Δ2 = det([[2, 0], [0, 4]]) = 8 > 0. - Le troisième mineur principal :
Δ3 = det([[2, 0, -3], [0, 4, 2], [-3, 2, 6]]) = 4 > 0.
Puisque tous les mineurs principaux sont strictement positifs, la matrice A est symétrique définie positive (SDP).
Remarque : On peut également vérifier que A est SDP en utilisant la caractérisation spectrale : une matrice est SDP si et seulement si toutes ses valeurs propres sont strictement positives. En effet, les valeurs propres de A sont calculées comme étant 0.1361, 3.5230, et 8.3408, qui sont toutes positives.
Décomposition de Cholesky
Puisque A est SDP, elle admet une unique décomposition de Cholesky sous la forme A = L LT, où L est une matrice triangulaire inférieure avec des éléments diagonaux strictement positifs (l11 > 0, l22 > 0, l33 > 0).
En calculant les éléments de L, nous obtenons les matrices L et LT :
A = [[2, 0, -3], [0, 4, 2], [-3, 2, 6]]
L = [[√2, 0, 0], [0, 2, 0], [-3/(2√2), 1/(2√2), 1/(2√2)]]
LT = [[√2, 0, -3/(2√2)], [0, 2, 1], [0, 0, 1/(2√2)]]
Résolution du système linéaire Ax = b
Le système linéaire Ax = b est résolu en deux étapes distinctes en utilisant la décomposition de Cholesky : Ax = (L LT)x = b, ce qui peut être décomposé en Ly = b, suivi de LTx = y.
1. Résolution de L y = b avec b = [[-1], [2], [3]] :
[[√2, 0, 0], [0, 2, 0], [-3/(2√2), 1/(2√2), 1/(2√2)]] * [[y1], [y2], [y3]] = [[-1], [2], [3]]
Cette première étape donne le vecteur y = [[-1/√2], [1], [1/(2√2)]].
2. Résolution de LT x = y :
[[√2, 0, -3/(2√2)], [0, 2, 1], [0, 0, 1/(2√2)]] * [[x1], [x2], [x3]] = [[-1/√2], [1], [1/(2√2)]]
Cette seconde étape conduit à la solution x = [[1], [0], [1]].
Vérification de la solution
Pour confirmer l'exactitude de la solution, nous calculons le produit Ax avec la solution trouvée :
[[2, 0, -3], [0, 4, 2], [-3, 2, 6]] * [[1], [0], [1]] = [[(2*1 + 0*0 + -3*1)], [(0*1 + 4*0 + 2*1)], [(-3*1 + 2*0 + 6*1)]] = [[-1], [2], [3]]
Le vecteur résultant [[-1], [2], [3]] correspond bien au vecteur b initial, ce qui valide la solution x.
Exercice 3 : Méthode de Gauss-Seidel
Pour vérifier que la matrice A est définie positive, on peut utiliser le Théorème de Sylvester (car A est symétrique). Une matrice A est SDP si et seulement si tous ses mineurs principaux Δk sont strictement positifs pour k = 1, 2, 3.
Nous avons pour la matrice A = [[1, α, α], [α, 1, α], [α, α, 1]] :
Δ1 = 1 > 0.Δ2 = det([[1, α], [α, 1]]) = 1 - α2.Δ3 = det([[1, α, α], [α, 1, α], [α, α, 1]]) = 2α3 - 3α2 + 1. Cette expression peut être factorisée en(α - 1)2 (2α + 1).
Pour que A soit SDP, les conditions suivantes doivent être satisfaites :
Δ2 > 0 ⇒ 1 - α2 > 0 ⇒ α ∈ ]-1, 1[.Δ3 > 0 ⇒ (α - 1)2 (2α + 1) > 0. Puisque(α - 1)2 ≥ 0(et nous excluonsα = 1pour l'inversibilité), il faut que2α + 1 > 0 ⇒ α > -1/2.
En combinant ces conditions, la matrice A est SDP si et seulement si α ∈ ]-1/2, 1[.
Remarque : Si α ∈ ]-1/2, 1[, la matrice A est également inversible.
Matrice d'itération de Gauss-Seidel
Supposons que A est inversible (c'est-à-dire α ≠ 1 et α ≠ -1/2). La matrice d’itération G de la méthode de Gauss-Seidel est définie par A = D - L - U et G = (D - L)-1 U. Pour la matrice A donnée, nous avons :
D = [[1, 0, 0], [0, 1, 0], [0, 0, 1]]
L = [[0, 0, 0], [-α, 0, 0], [-α, -α, 0]]
U = [[0, -α, -α], [0, 0, -α], [0, 0, 0]]
Alors :
D - L = [[1, 0, 0], [α, 1, 0], [α, α, 1]]
L'inverse de (D - L) est :
(D - L)-1 = [[1, 0, 0], [-α, 1, 0], [α2 - α, -α, 1]]
La matrice d'itération G est obtenue par le produit (D - L)-1 U :
G = [[0, -α, -α], [0, α2, α2 - α], [0, α(α - α2), α2 + α(α - α2)]]
Convergence de la méthode de Gauss-Seidel
Les valeurs propres de la matrice G sont λ1 = 0, et deux autres valeurs λ2 et λ3 données par les formules :
λ2 = (α/2) * ((α2 - 3α) + |α - 1|√(α(α - 4)))
λ3 = (α/2) * ((α2 - 3α) - |α - 1|√(α(α - 4)))
La méthode de Gauss-Seidel converge si et seulement si le rayon spectral de G, noté Ω(G) = max{|λ1|, |λ2|, |λ3|}, est strictement inférieur à 1.
Si la méthode de Gauss-Seidel converge, cela implique que α ∈ ]-1, -1/2[ ∪ ]-1/2, 1[. Il est important de souligner que pour α ∈ ]-1/2, 1[, la matrice A est symétrique définie positive, ce qui garantit la convergence de la méthode de Gauss-Seidel.
À l'inverse, si α ∈ ]-1, -1/2[, alors Ω(G) ≥ 1, ce qui entraîne la non-convergence de la méthode de Gauss-Seidel.
Explication : La fonction α → λmax(α) (où λmax est la valeur propre de G de plus grand module) est décroissante. Pour tout α ∈ ]-1, -1/2[, on observe que 1 ≤ λmax(-0.5) ≤ λmax(α) ≤ λmax(-1) ≈ 2 + √5.
Exemple d'itérations avec Gauss-Seidel
Considérons le cas où α = 1/2, avec le vecteur b = (1,1,0)T et le vecteur initial x(0) = (0,0,0)T. Le schéma itératif de Gauss-Seidel s’écrit :
(D - L)-1 = [[1, 0, 0], [-1/2, 1, 0], [-1/4, -1/2, 1]]
G = [[0, -1/2, -1/2], [0, 1/4, -1/4], [0, 1/8, 3/8]]
La formule d'itération est x(k+1) = G x(k) + (D - L)-1 b.
Après 4 itérations, nous obtenons les approximations successives suivantes :
x(1) = [[1], [1/2], [-3/4]]
x(2) = [[9/8], [13/16], [-31/32]]
x(3) = [[69/64], [121/128], [-259/256]]
Ce qui donne approximativement : x(3) ≈ [[1.0781], [0.94531], [-1.0117]]
Remarque : La solution exacte du système Ax = b pour α = 1/2 et b = [[1], [1], [0]] est x = [[1], [1], [-1]]. La matrice inverse A-1 pour α = 1/2 est [[3/2, -1/2, -1/2], [-1/2, 3/2, -1/2], [-1/2, -1/2, 3/2]].
Foire Aux Questions (FAQ)
Qu'est-ce que le Théorème des Valeurs Intermédiaires ?
Le Théorème des Valeurs Intermédiaires (TVI) est un concept fondamental en analyse mathématique. Il stipule que pour une fonction continue f définie sur un intervalle fermé [a,b], si f(a) et f(b) ont des signes opposés, alors il existe au moins un point c dans l'intervalle ouvert ]a,b[ tel que f(c) = 0. Il est couramment utilisé pour prouver l'existence de racines pour une équation donnée.
Pourquoi la condition |g'(x)| < 1 est-elle importante pour la convergence d'une méthode de point fixe ?
La condition |g'(x)| < 1 dans un voisinage du point fixe est essentielle pour garantir la convergence d'une méthode de point fixe. Elle signifie que la fonction g est une contraction locale, c'est-à-dire qu'elle "rapproche" les points à chaque itération. Si la fonction n'est pas contractante (c'est-à-dire si |g'(x)| ≥ 1), les itérations peuvent s'éloigner du point fixe, entraînant une divergence de la méthode ou l'absence de convergence locale.
Qu'est-ce qu'une matrice symétrique définie positive (SDP) et pourquoi est-elle utile en analyse numérique ?
Une matrice est dite symétrique définie positive (SDP) si elle est symétrique (c'est-à-dire égale à sa transposée, A = AT) et si le produit scalaire xTAx est strictement positif pour tout vecteur non nul x. En analyse numérique, les matrices SDP sont très importantes car elles possèdent des propriétés qui garantissent la stabilité et la convergence de nombreux algorithmes. Par exemple, une matrice SDP admet toujours une unique décomposition de Cholesky et les méthodes itératives comme Jacobi ou Gauss-Seidel convergent pour les systèmes linéaires associés à de telles matrices sous des conditions moins restrictives.