Méthodes itératives pour la résolution des systèmes linéaires PDF 2024-2025

Outlines Chapitre 3 : Méthodes itératives pour la résolution des systèmes linéaires Cours d’Analyse Numérique (1 CSC)-2024/2025....

Outlines Chapitre 3 : Méthodes itératives pour la résolution des systèmes linéaires Cours d’Analyse Numérique (1 CSC)-2024/2025. Pr Hamid HADDADOU Cours d’Analyse Numérique (1 CSC)-2024/2025. Pr Hamid HADDADOU Méthodes itératives pour la résolution des systèmes linéaires  Outlines Plan 1 Introduction 2 Méthodes itératives pour la résolution des système linéaire 3 Méthodes de décomposition 4 Méthodes particulières de décomposition Méthode de Jacobi Méthode de Gauss-Seidel Les méthodes de relaxation SOR (Successive Over Relaxation) 5 Comparaison entre les méthodes de Jacobi, de Gauss-Seidel et SOR : Cas des matrices tridiagonales 6 Exemple motivant : Equation de la chaleur Cours d’Analyse Numérique (1 CSC)-2024/2025. Pr Hamid HADDADOU Méthodes itératives pour la résolution des systèmes linéaires  Introduction Introduction Cours d’Analyse Numérique (1 CSC)-2024/2025. Pr Hamid HADDADOU Méthodes itératives pour la résolution des systèmes linéaires  Introduction Introduction Les méthodes directes de résolution d’un système linéaure AX = b sont sensées donner la solution exacte en un nobre fini d’opérations. Mais, si la taille du système considéré est grande, le nombre d’opérations devient très important. Les erreurs de calcul dans ce cas seront très difficiles à contrôler, et la solution obtenue sera ainsi entachée d’erreurs et probablement loin de la solution exacte. Rajontons à cette faiblesse des méthodes directes, la non exploitaion du caractère creux de certaines matrices. Comme alternatives plus efficace il ya une autre calsse de méthodes de resoltion dites ”Méthodes itératives”. Cours d’Analyse Numérique (1 CSC)-2024/2025. Pr Hamid HADDADOU Méthodes itératives pour la résolution des systèmes linéaires  Méthodes itératives pour la résolution des système linéaire Méthodes itératives pour la résolution des systèmes linéaires Cours d’Analyse Numérique (1 CSC)-2024/2025. Pr Hamid HADDADOU Méthodes itératives pour la résolution des systèmes linéaires  Méthodes itératives pour la résolution des système linéaire Les méthodes itératives pour la résolution des systèmes linéaires Soit A une matrice inversible de Mn (R) et b ∈ Rn. Définition On appelle méthode itérative de résolution du système AX = b toute méthode qui construit une suite récurrente de vecteurs (X (k) )k∈N telle que (X (k) )k∈N est destinée à converger vers X pour tout X (0). Une idée simple pour construire un certain type de méthodes itératives pour résoudre un système AX = b est Tranformation AX = b ⇔ g (X ) = X , ensuite construire l’algorithme du point fixe (des approximations successives)  (k+1) X = g (X (k) ), X (0) un vecteur initial donné dans Rn. Cours d’Analyse Numérique (1 CSC)-2024/2025. Pr Hamid HADDADOU Méthodes itératives pour la résolution des systèmes linéaires  Méthodes itératives pour la résolution des système linéaire Les méthodes itératives linéaires du premier ordre Les méthodes itératives classiques (linéaires du premier ordre) s’intéresse à avoir (AX = b) ⇔ (BX + c = X ) , où B ∈ Mnn (R) et c ∈ Rn. Ainsi, ces méthodes sont de la forme  (k+1) X = BX (k) + c, (1) X un vecteur initial donnée dans Rn , (0) la matrice B dite matrice d’itération de la méthode. Proposition (Consistance : condition nécessaire de convergence) Si la suite (X (k) )k∈N définie par (1) converge vers X solution de AX = b, alors B et c vérifient BA−1 b + c = A−1 b. Cours d’Analyse Numérique (1 CSC)-2024/2025. Pr Hamid HADDADOU Méthodes itératives pour la résolution des systèmes linéaires  Méthodes itératives pour la résolution des système linéaire Exemple Exemple On considère le système AX = b avec     2 −1 1 A= et b = −1 2 1     2 0 0 1 On remarque que A = − 0 1 1 −1 | {z } | {z } M N Ainsi (puisque M est inversible), (AX = b) ⇔ (M − N)X = b) ⇔ (MX = NX + b) ⇔ (X = M −1 NX + M −1 b) On propose la méthode itérative  (k+1) X = BX (k) + c, X un vecteur initial donnée dans Rn (0) 1    1 . 0. avec B = M −1 N = 2 et c = M −1 N = 2. 1 −1 1 Cours d’Analyse Numérique (1 CSC)-2024/2025. Pr Hamid HADDADOU Méthodes itératives pour la résolution des systèmes linéaires  Méthodes itératives pour la résolution des système linéaire Convergence des méthodes itératives classiques Définition (Rappel) Le rayon spectral de A ∈ Mn (R) est défini par ρ(A) = max{|λi |; λi ∈ Sp(A)}. Théorème (Condition nécessaire et suffisante de convergence) Soit A ∈ Mn (R) inversible et b ∈ Rn. Considérons la suite (X (k) )k∈N définie par  (k+1) X = BX (k) + c, X un vecteur initial donnée dans Rn (0) qu’on suppose vérifiant la condition de consistance. Alors, la suite (X (k) )k∈N converge vers la solution du système AX = b pour tout X (0) si et seulement si ρ(B) < 1. Remarque (Vitesse de covergence) La vitesse d’une méthode linéaire du premier ordre convergente peut être. 1 quantifier par V = ρ(B). Cours d’Analyse Numérique (1 CSC)-2024/2025. Pr Hamid HADDADOU Méthodes itératives pour la résolution des systèmes linéaires  Méthodes itératives pour la résolution des système linéaire Convergence des méthodes itératives classiques Définition (Rappel) Le rayon spectral de A ∈ Mn (R) est défini par ρ(A) = max{|λi |; λi ∈ Sp(A)}. Théorème (Condition nécessaire et suffisante de convergence) Soit A ∈ Mn (R) inversible et b ∈ Rn. Considérons la suite (X (k) )k∈N définie par  (k+1) X = BX (k) + c, X un vecteur initial donnée dans Rn (0) qu’on suppose vérifiant la condition de consistance. Alors, la suite (X (k) )k∈N converge vers la solution du système AX = b pour tout X (0) si et seulement si ρ(B) < 1. Remarque (Vitesse de covergence) La vitesse d’une méthode linéaire du premier ordre convergente peut être. 1 quantifier par V = ρ(B). Cours d’Analyse Numérique (1 CSC)-2024/2025. Pr Hamid HADDADOU Méthodes itératives pour la résolution des systèmes linéaires  Méthodes itératives pour la résolution des système linéaire Exemple Exemple On considère le système AX = b avec   2 −1 A= et b ∈ Rn −1 8 On propose la méthode itérative  (k+1) X = BX (k) + c, X un vecteur initial donnée dans Rn (0) avec 1   0 B= 1 2 et c ∈ Rn 8 0 Supposons que la condition de consistance est satisfaite. On a PB (X ) = det(B − XI2 ) = X 2 − 16 1 , ce qui entraine 1 1 Sp(B) = {− , }. 4 4 Ainsi, ρ(B) = 14 < 1, d’où la convergence. De plus, la vitesse de convergence. 1 est estimée par V = ρ(B) = 4. Cours d’Analyse Numérique (1 CSC)-2024/2025. Pr Hamid HADDADOU Méthodes itératives pour la résolution des systèmes linéaires  Méthodes itératives pour la résolution des système linéaire Exemple Exemple On considère le système AX = b avec   2 −1 A= et b ∈ Rn −1 8 On propose la méthode itérative  (k+1) X = BX (k) + c, X un vecteur initial donnée dans Rn (0) avec 1   0 B= 1 2 et c ∈ Rn 8 0 Supposons que la condition de consistance est satisfaite. On a PB (X ) = det(B − XI2 ) = X 2 − 16 1 , ce qui entraine 1 1 Sp(B) = {− , }. 4 4 Ainsi, ρ(B) = 14 < 1, d’où la convergence. De plus, la vitesse de convergence. 1 est estimée par V = ρ(B) = 4. Cours d’Analyse Numérique (1 CSC)-2024/2025. Pr Hamid HADDADOU Méthodes itératives pour la résolution des systèmes linéaires  Méthodes itératives pour la résolution des système linéaire Condition suffisante de convergence Remarque Pour montrer qu’une méthode linéaire du premier ordre converge il suffit de trouver une norme matricielle induite k.k telle que la matrice d’itération B de la méthode satisfait kBk < 1, car ρ(B) ≤ kBk. En général, on essaye avec les normes k.k1 et k.k∞. Rappels n n déf P P 1) kAk1 = max kAX k1 = max{ |ai1 | ,..., |ain |} kX k1 =1 i=1 i=1 n n déf P P 2) kAk∞ = max kAX k∞ = max{ |a1j | ,..., |anj |} kX k∞ =1 j=1 j=1 Cours d’Analyse Numérique (1 CSC)-2024/2025. Pr Hamid HADDADOU Méthodes itératives pour la résolution des systèmes linéaires  Méthodes itératives pour la résolution des système linéaire Exemple Exemple Etant donnée un système AX = b et une méthode linéaire du premier ordre X (k+1) = BX (k) + c vérifiant la condition de consistance où la matrice d’itération 1 2   0   8 8    1 2 3  B= 8 8 8       2 5   0  8 8 On a kBk1 = 1, donc on peut rien déduire. Par contre kBk∞ = 78 < 1, donc le méthode itérative proposée converge. Cours d’Analyse Numérique (1 CSC)-2024/2025. Pr Hamid HADDADOU Méthodes itératives pour la résolution des systèmes linéaires  Méthodes itératives pour la résolution des système linéaire Exemple Exemple Etant donnée un système AX = b et une méthode linéaire du premier ordre X (k+1) = BX (k) + c vérifiant la condition de consistance où la matrice d’itération 1 2   0   8 8    1 2 3  B= 8 8 8       2 5   0  8 8 On a kBk1 = 1, donc on peut rien déduire. Par contre kBk∞ = 78 < 1, donc le méthode itérative proposée converge. Cours d’Analyse Numérique (1 CSC)-2024/2025. Pr Hamid HADDADOU Méthodes itératives pour la résolution des systèmes linéaires  Méthodes itératives pour la résolution des système linéaire Exemple Exemple Etant donnée un système AX = b et une méthode linéaire du premier ordre X (k+1) = BX (k) + c vérifiant la condition de consistance où la matrice d’itération 1 2   0   8 8    1 2 3  B= 8 8 8       2 5   0  8 8 On a kBk1 = 1, donc on peut rien déduire. Par contre kBk∞ = 78 < 1, donc le méthode itérative proposée converge. Cours d’Analyse Numérique (1 CSC)-2024/2025. Pr Hamid HADDADOU Méthodes itératives pour la résolution des systèmes linéaires  Méthodes itératives pour la résolution des système linéaire Estimations de l’erreur et test d’arrêt Soient un système AX = b et une méthode associée consistante X (k+1) = BX (k) + c. Proposition (Première estimation de l’erreur) Si pour une certaine norme matricielle subordonnée k.k∗ d’une norme vectorielle kk∗ on a kBk∗ < 1 alors la méthode itérative converge vers la solution de AX = b et kBk∗ X (k) − X ≤ X (k) − X (k−1) , ∀k ≥ 1 ∗ (1 − kBk∗ ) ∗ Cette estimation justifie, pour une précision donnée ε , l’utilisation du test d’arrêt suivant (dit des incréments) : kX (n) − X (n−1) k∗ ≤ ε. Proposition (Deuxième estimation de l’erreur) Pour toute norme matricielle subordonnée k.k d’une norme vectorielle kk, on a R (k) X (k) − X ≤ cond(A) , ∀k ≥ 0 (où R (k) = AX (k) − b) kAk Si cond(A) =. kAk A−1 est proche de 1 et la méthode converge, alors cette estimation justifie, pour une précision donnée ε, l’utilisation du test d’arrêt suivant (dit du résidu) : kR (n) k ≤ ε. Cours d’Analyse Numérique (1 CSC)-2024/2025. Pr Hamid HADDADOU Méthodes itératives pour la résolution des systèmes linéaires  Méthodes itératives pour la résolution des système linéaire Estimations de l’erreur et test d’arrêt Soient un système AX = b et une méthode associée consistante X (k+1) = BX (k) + c. Proposition (Première estimation de l’erreur) Si pour une certaine norme matricielle subordonnée k.k∗ d’une norme vectorielle kk∗ on a kBk∗ < 1 alors la méthode itérative converge vers la solution de AX = b et kBk∗ X (k) − X ≤ X (k) − X (k−1) , ∀k ≥ 1 ∗ (1 − kBk∗ ) ∗ Cette estimation justifie, pour une précision donnée ε , l’utilisation du test d’arrêt suivant (dit des incréments) : kX (n) − X (n−1) k∗ ≤ ε. Proposition (Deuxième estimation de l’erreur) Pour toute norme matricielle subordonnée k.k d’une norme vectorielle kk, on a R (k) X (k) − X ≤ cond(A) , ∀k ≥ 0 (où R (k) = AX (k) − b) kAk Si cond(A) =. kAk A−1 est proche de 1 et la méthode converge, alors cette estimation justifie, pour une précision donnée ε, l’utilisation du test d’arrêt suivant (dit du résidu) : kR (n) k ≤ ε. Cours d’Analyse Numérique (1 CSC)-2024/2025. Pr Hamid HADDADOU Méthodes itératives pour la résolution des systèmes linéaires  Méthodes itératives pour la résolution des système linéaire Exemple Exemple Etant donnée un système AX = b et une méthode linéaire du premier ordre X (k+1) = BX (k) + c vérifiant la condition de consistance où la matrice d’itération 0 18 18   B =  18 0 81  1 1 8 8 0 On a ρ(B) ≤ kBk∞ = 14 < 1, donc la méthode proposée converge vers la solution de AX = b. De plus, si par exemple, on part de X (0) = t (0, 0, 0) et on souhaite approcher la solution à moins de 10−2 par cette méthode, il suffit de faire n itérations telle que 1 X (n) − X ≤ 4 X (n) − X (n−1) ≤ 10−2 ∞ (1 − 14 ) ∞ c’est à dire, X (n) − X (n−1) ≤ 3 × 10−2 ∞ Cours d’Analyse Numérique (1 CSC)-2024/2025. Pr Hamid HADDADOU Méthodes itératives pour la résolution des systèmes linéaires  Méthodes itératives pour la résolution des système linéaire Exemple Exemple Etant donnée un système AX = b et une méthode linéaire du premier ordre X (k+1) = BX (k) + c vérifiant la condition de consistance où la matrice d’itération 0 18 18   B =  18 0 81  1 1 8 8 0 On a ρ(B) ≤ kBk∞ = 14 < 1, donc la méthode proposée converge vers la solution de AX = b. De plus, si par exemple, on part de X (0) = t (0, 0, 0) et on souhaite approcher la solution à moins de 10−2 par cette méthode, il suffit de faire n itérations telle que 1 X (n) − X ≤ 4 X (n) − X (n−1) ≤ 10−2 ∞ (1 − 14 ) ∞ c’est à dire, X (n) − X (n−1) ≤ 3 × 10−2 ∞ Cours d’Analyse Numérique (1 CSC)-2024/2025. Pr Hamid HADDADOU Méthodes itératives pour la résolution des systèmes linéaires  Méthodes itératives pour la résolution des système linéaire Exemple Exemple Etant donnée un système AX = b et une méthode linéaire du premier ordre X (k+1) = BX (k) + c vérifiant la condition de consistance où la matrice d’itération 0 18 18   B =  18 0 81  1 1 8 8 0 On a ρ(B) ≤ kBk∞ = 14 < 1, donc la méthode proposée converge vers la solution de AX = b. De plus, si par exemple, on part de X (0) = t (0, 0, 0) et on souhaite approcher la solution à moins de 10−2 par cette méthode, il suffit de faire n itérations telle que 1 X (n) − X ≤ 4 X (n) − X (n−1) ≤ 10−2 ∞ (1 − 14 ) ∞ c’est à dire, X (n) − X (n−1) ≤ 3 × 10−2 ∞ Cours d’Analyse Numérique (1 CSC)-2024/2025. Pr Hamid HADDADOU Méthodes itératives pour la résolution des systèmes linéaires  Méthodes itératives pour la résolution des système linéaire Exemple Exemple Etant donnée un système AX = b et une méthode linéaire du premier ordre X (k+1) = BX (k) + c vérifiant la condition de consistance où la matrice d’itération 0 18 18   B =  18 0 81  1 1 8 8 0 On a ρ(B) ≤ kBk∞ = 14 < 1, donc la méthode proposée converge vers la solution de AX = b. De plus, si par exemple, on part de X (0) = t (0, 0, 0) et on souhaite approcher la solution à moins de 10−2 par cette méthode, il suffit de faire n itérations telle que 1 X (n) − X ≤ 4 X (n) − X (n−1) ≤ 10−2 ∞ (1 − 14 ) ∞ c’est à dire, X (n) − X (n−1) ≤ 3 × 10−2 ∞ Cours d’Analyse Numérique (1 CSC)-2024/2025. Pr Hamid HADDADOU Méthodes itératives pour la résolution des systèmes linéaires  Méthodes de décomposition Méthodes de décomposition Cours d’Analyse Numérique (1 CSC)-2024/2025. Pr Hamid HADDADOU Méthodes itératives pour la résolution des systèmes linéaires  Méthodes de décomposition Méthodes de décomposition L’idée des méthodes de décompositions est d’écrire la matrice A sous la forme A = M − N avec M est une matrice de Mn (R) inversible, tout système linéaire MY = d peut être résolu simplement et avec un coût de calcul faible. Ainsi, le système (1) est équivalent à X = M −1 NX + M −1 b. D’où vient l’idée qu’à partir d’un X (0) (arbitraire) qu’on choisit dans Rn , on approche la solution X de (1) par la suite définie par X (k+1) = M −1 NX (k) + M −1 b, ∀k ∈ N. (5) Remarque Les méthodes de décomposition sont consistantes. Si une méthode de décomposition converge, on inverse pas M pour calculer l’itéré X (k+1) mais on résout le système MX (k+1) = NX (k) + b. Cours d’Analyse Numérique (1 CSC)-2024/2025. Pr Hamid HADDADOU Méthodes itératives pour la résolution des systèmes linéaires  Méthodes de décomposition Condition de convergence La proposition suivante traduit la condition nécessaire et suffisante pour avoir la convergence dans le cas des méthodes de décomposition Proposition Une méthode de décomposition converge si et seulement si ρ(M −1 N) < 1 Le résultat suivant donne une condition suffisante pour avoir la convergence des méthodes de décomposition : Théorème Soit A une matrice symétrique définie positive telle que A = M − N et M inversible. Alors, si la matrice symétrique t M + N est définie positive, ρ(M −1 N) < 1. Cours d’Analyse Numérique (1 CSC)-2024/2025. Pr Hamid HADDADOU Méthodes itératives pour la résolution des systèmes linéaires  Méthodes particulières de décomposition Méthode de Jacobi Méthode de Gauss-Seidel Les méthodes de relaxatio Méthodes particulières de décomposition Cours d’Analyse Numérique (1 CSC)-2024/2025. Pr Hamid HADDADOU Méthodes itératives pour la résolution des systèmes linéaires  Méthodes particulières de décomposition Méthode de Jacobi Méthode de Gauss-Seidel Les méthodes de relaxatio Méthodes particulières de décomposition Toute matrice A peut s’écrire sous la forme A = D − E − F telles que..   −aij    . 0  0 0 0  D= aii i>j  , E = .. i1 1 + 1 − (ρ(LJ ))2 et on a ρ(Lω0 ) = ω0 − 1. Cours d’Analyse Numérique (1 CSC)-2024/2025. Pr Hamid HADDADOU Méthodes itératives pour la résolution des systèmes linéaires  Exemple motivant : Equation de la chaleur Exemple motivant : Equation de la chaleur Cours d’Analyse Numérique (1 CSC)-2024/2025. Pr Hamid HADDADOU Méthodes itératives pour la résolution des systèmes linéaires  Exemple motivant : Equation de la chaleur Exemple motivant : Equation de la chaleur On s’intéresse à la diffusion de la chaleur dans une barre [0, 1] chauffée aux deux bouts. Supposons que la conductivité thermique du matériau constituant la bare est égale à 1. Pour une source de chaleur f donnée, la température u(x) au point x satisfait   ∂2u (x) = f (x) dans ]0, 1[, ∂x 2  u(0) = a et u(1) = 1. La solution analytique de ce problème aux limites est Z x Z y  u(x) = f (s)ds dy + c1 x + c0 , 0 0 où c0 et c1 deux constantes qu’on peut déterminer à l’aide des conditions aux limites u(0) = a etR x u(1) R y = 1 En
général, on ne sait pas calculer d’une manière exacte l’intégrale 0 0 f (s)ds dy. Cours d’Analyse Numérique (1 CSC)-2024/2025. Pr Hamid HADDADOU Méthodes itératives pour la résolution des systèmes linéaires  Exemple motivant : Equation de la chaleur Il y a plusieurs approches pour résoudre numériquement l’équation aux dérivées partielles précédente. Par exemple, on subdivise l’intervalle [0, 1] à l’aide de (n + 1) noeuds xk = kh (k ∈ {0,..., n}) avec h = n1. Alors, le développement de Taylor à l’ordre 3 donne  2  ∂ u u(xk−1 ) − 2u(xk ) + u(xk+1 ) (xk ) = + o(h3 ), ∂x 2 h2 ainsi, pour h assez petit, on fait l’approximation suivante :  2  ∂ u u(xk−1 ) − 2u(xk ) + u(xk+1 ) (xk ) ≈. ∂x 2 h2 On peut alors approcher u(xk ), pour k ∈ {1,..., n − 1}, par la valeur approximative uk donnée par a − 2u1 + u2 = h2 f (x1 ),    u1 − 2u2 + u3 = h2 f (x2 ),  ..   . un−2 − 2un−1 + b = h2 f (xn−1 ).  Cours d’Analyse Numérique (1 CSC)-2024/2025. Pr Hamid HADDADOU Méthodes itératives pour la résolution des systèmes linéaires  Exemple motivant : Equation de la chaleur Donc, le calcul des valeurs approximatives des u(xk ) revient à résoudre le système linéaire AX = b où   −2 1 0 ··· 0  u1  .....    u2   1 −2 1. .     ......  , X = ..    A=  0... 0    .  .. ..   ......  .... 1  0 ··· 0 1 −2 un−1 h2 f (x1 ) − a    h2 f (x2 ) ..     b= .   ..  .  h2 f (xn−1 ) − b Cours d’Analyse Numérique (1 CSC)-2024/2025. Pr Hamid HADDADOU Méthodes itératives pour la résolution des systèmes linéaires  Exemple motivant : Equation de la chaleur Dans l’exemple précédent si on veut avoir une approximation de très bonne qualité, il faut considérer une subdivision très fine, c’est à dire prendre n très grand. Dans ce cas là, les méthodes directes sont trop coûteuses en place mémoire et en temps, et de plus elle n’exploitent pas vraiment le caractère creux de la matrice. Les méthodes itératives représentent dans des situations une alternative plus efficace. Cours d’Analyse Numérique (1 CSC)-2024/2025. Pr Hamid HADDADOU Méthodes itératives pour la résolution des systèmes linéaires