1.5. MÉTHODES ITÉRATIVES CHAPITRE 1. SYSTÈMES LINÉAIRES 1.5.4 Exercices (méthod

1.5. MÉTHODES ITÉRATIVES CHAPITRE 1. SYSTÈMES LINÉAIRES 1.5.4 Exercices (méthodes itératives) Exercice 52 (Convergence de suites). Corrigé en page 118 Etudier la convergence de la suite (x(k))k∈I N ⊂I Rn définie par x(0) donné, x(k) = Bx(k) + c dans les cas suivants : (a) B =  2 3 1 0 2 3  , c = 0 1  , (b) B =  2 3 1 0 2  , c = 0 0  . Exercice 53 (Méthode de Richardson). Suggestions en page 117, corrigé en page 118 Soit A ∈Mn(I R) une matrice symétrique définie positive, b ∈I Rn et α ∈I R. Pour trouver la solution de Ax = b, on considère la méthode itérative suivante : — Initialisation : x(0) ∈I Rn, — Iterations : x(k+1) = x(k) + α(b −Ax(k)). 1. Pour quelles valeurs de α (en fonction des valeurs propres de A) la méthode est-elle convergente? 2. Calculer α0 (en fonction des valeurs propres de A) t.q. ρ(Id −α0A) = min{ρ(Id −αA), α ∈I R}. Commentaire sur la méthode de Richardson : On peut la voir comme une méthode de gradient à pas fixe pour la minimisation de la fonction f définie de I RN dans I R par : x 7→f(x) = 1 2Ax · x −b · x, qui sera étudiée au chapitre Optimisation. On verra en effet que grâce qu caractère symétrique définie positif de A, la fonction f admet un unique minimum, caractérisé par l’annulation du gradient de f en ce point. Or ∇f(x) = Ax −b, et annuler le gradient consiste à résoudre le système linéaire Ax = b. Exercice 54 (Non convergence de la méthode de Jacobi). Suggestions en page 117. Corrigé en page 119. Soit a ∈I R et A =   1 a a a 1 a a a 1   Montrer que A est symétrique définie positive si et seulement si −1/2 < a < 1 et que la méthode de Jacobi converge si et seulement si −1/2 < a < 1/2. Exercice 55 (Jacobi et Gauss–Seidel : cas des matrices tridiagonales). Corrigé en page 120. Soit A ∈Mn(I R) une matrice carrée d’ordre n inversible et tridiagonale; on note ai,j le coefficient de la ligne i et la ligne j de la matrice A. On décompose en A = D −E −F, où D représente la diagonale de la matrice A, (−E) la partie triangulaire inférieure stricte et (−F) la partie triangulaire supérieure stricte. On note BJ et BGS les matrices d’itération des méthodes de Jacobi et Gauss-Seidel pour la résolution d’un système linéaire de matrice A. 1. Calculer les matrices BJ et BGS pour la matrice particulère A =  2 −1 −1 2  et calculer leurs rayons spectraux.Montrer que les méthodes convergent. Citer les résultats du cours qui s’appliquent pour cette matrice. 2. Montrer que λ est valeur propre de BJ si et seulement s’il existe un vecteur complexe x = (x1, . . . xn) ∈ Cn, x ̸= 0, tel que −ap,p−1xp−1 −ap,p+1xp+1 = λap,pxp, p = 1, . . . , n. avec x0 = xn+1 = 0. 3. Soit y = (y1, . . . yn) ∈Cn défini par yp = λpxp, où λ est une valeur propre non nulle de BJ et x = (x1, . . . , xn) un vecteur propre associé. On pose y0 = yn+1 = 0. Montrer que −ap,p−1yp−1 −λ2ap,p+1yp+1 = λ2ap,pyp, p = 1, . . . , n. Analyse numérique I, télé-enseignement, L3 109 Université d’Aix-Marseille, R. Herbin, 8 septembre 2016 1.5. MÉTHODES ITÉRATIVES CHAPITRE 1. SYSTÈMES LINÉAIRES 4. Montrer que µ est valeur propre de BGS associée à un vecteur propre z ̸= 0 si et seulement si (F −µ(D −E)) z = 0. 5. Montrer que λ est valeur propre non nulle de BJ si et seulement si λ2 est valeur propre de BGS, et en déduire que ρ(BGS) = ρ(BJ)2. 6. On considère la matrice : A =   1 3 4 3 4 3 4 1 3 4 3 4 3 4 1   Montrer que cette matrice est symétrique définie positive. Montrer que ρ(BGS) ̸= ρ(BJ)2. Quelle est l’hy- pothèse mise en défaut ici ? Exercice 56 (Méthode de Jacobi et relaxation). Suggestions en page 118, corrigé en page 126 Soit n ≥1. Soit A = (ai,j)i,j=1,...,n ∈Mn(I R) une matrice symétrique. On note D la partie diagonale de A, −E la partie triangulaire inférieure de A et −F la partie triangulaire supérieure de A, c’est-à-dire : D = (di,j)i,j=1,...,n, di,j = 0 si i ̸= j, di,i = ai,i, E = (ei,j)i,j=1,...,n, ei,j = 0 si i ≤j, ei,j = −ai,j si i > j, F = (fi,j)i,j=1,...,n, fi,j = 0 si i ≥j, fi,j = −ai,j si i < j. Noter que A = D −E −F. Soit b ∈I Rn. On cherche à calculer x ∈I Rn t.q. Ax = b. On suppose que D est définie positive (noter que A n’est pas forcément inversible). On s’intéresse ici à la méthode de Jacobi (par points), c’est–à–dire à la méthode itérative suivante : Initialisation. x(0) ∈I Rn Itérations. Pour n ∈I N, Dx(k+1) = (E + F)x(k) + b. On pose J = D−1(E + F). 1. Montrer, en donnant un exemple avec n = 2, que J peut ne pas être symétrique. 2. Montrer que J est diagonalisable dans I R et, plus précisement, qu’il existe une base de I Rn, notée {f1, . . . , fn}, et il existe {µ1, . . . , µn} ⊂I R t.q. Jf i = µif i pour tout i ∈{1, . . . , n} et t.q. Df i · f j = δi,j pour tout i, j ∈{1, . . . , n}. En ordonnant les valeurs propres de J, on a donc µ1 ≤. . . ≤µn, on conserve cette notation dans la suite. 3. Montrer que la trace de J est nulle et en déduire que µ1 ≤0 et µn ≥0. On suppose maintenant que A et 2D −A sont symétriques définies positives et on pose x = A−1b. 4. Montrer que la méthode de Jacobi (par points) converge (c’est-à-dire x(k) →x quand n →∞). [Utiliser un théorème du cours.] On se propose maintenant d’améliorer la convergence de la méthode par une technique de relaxation. Soit ω > 0, on considère la méthode suivante : Initialisation. x(0) ∈I Rn Itérations. Pour n ∈I N, D˜ x(k+1) = (E + F)x(k) + b, x(k+1) = ω˜ x(k+1) + (1 −ω)x(k). 5. Calculer les matrices Mω (inversible) et Nω telles que Mωx(k+1) = Nωx(k)+b pour tout n ∈I N, en fonction de ω, D et A. On note, dans la suite Jω = (Mω)−1Nω. 6. On suppose dans cette question que (2/ω)D −A est symétrique définie positive. Montrer que la méthode converge (c’est-à-dire que x(k) →x quand n →∞.) 7. Montrer que (2/ω)D −A est symétrique définie positive si et seulement si ω < 2/(1 −µ1). 8. Calculer les valeurs propres de Jω en fonction de celles de J. En déduire, en fonction des µi, la valeur “optimale” de ω, c’est-à-dire la valeur de ω minimisant le rayon spectral de Jω. Analyse numérique I, télé-enseignement, L3 110 Université d’Aix-Marseille, R. Herbin, 8 septembre 2016 uploads/Litterature/ anum-td4-pdf.pdf

Tags
littérature méthode montrer définie matrice fonction
Documents similaires
  • 37
  • 0
  • 0
Afficher les détails des licences
Licence et utilisation
Gratuit pour un usage personnel Attribution requise
Partager