Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Sup’Galilée Année 2020/2021 MACS1 Analyse numérique - TD6 & TD 7 - Corrigé Méth

Sup’Galilée Année 2020/2021 MACS1 Analyse numérique - TD6 & TD 7 - Corrigé Méthodes directes pour la résolution des systèmes linéaires 1 Méthode de Gauss et factorisation LU Exercice 1 : un exemple Soient α, β, γ P R. On considère le système linéaire suivant d’inconnues x1, x2, x3 : $ & % x1 ` 2x2 ´ 3x3 “ α 2x1 ` 6x2 ´ 5x3 “ β x1 ´ 2x2 ` 7x3 “ γ (1) 1. Écrire le système (1) sous la forme Ax x x “ b b b, avec A P M3pRq, x x x P R3, et b b b P R3, que l’on explicitera. 2. Est-ce que le système (1) admet une unique solution pour tout α, β, γ P R ? 3. Montrer que A admet une unique factorisation LU. Dans la suite on choisit α “ 1, β “ ´1 et γ “ 2 et on va résoudre le système Ax x x “ b b b de plusieurs façons : (a) Résoudre le système (1) par l’algorithme de Gauss sans pivot. (b) Calculer la factorisation LU de A puis résoudre le système (1) en utilisant cette factorisation LU. (c) Résoudre le système (1) par l’algorithme de Gauss avec pivot partiel. (d) Calculer la factorisation ¯ L¯ U de PA (où P est la matrice produit des matrices de permutations eﬀectuées dans l’algorithme de Gauss avec pivot partiel), puis résoudre le système (1) en utilisant cette factorisation. Correction 1. On a A “ ¨ ˝ 1 2 ´3 2 6 ´5 1 ´2 7 ˛ ‚, x x x “ ¨ ˝ x1 x2 x3 ˛ ‚, b b b “ ¨ ˝ α β γ ˛ ‚, A et b b b étant les données, et x x x P R3 le vecteur inconnu. 2. On calcule detpAq “ 24 ‰ 0 donc A est inversible. Le système admet donc une unique solution : x x x “ A´1b b b, Pour tout b b b P R3, c’est-à-dire pour tout α, β, γ P R. 3. On choisit α “ 1, β “ ´1 et γ “ 2. Vériﬁons que A admet une unique factorisation LU. D’après le cours (ou l’exercice 3 ci-dessous), une condition suﬃsante est que les sous matrices principales de A sont inversibles. Ceci est bien le cas car : detp∆1q “ detp1q “ 1 ‰ 0, detp∆2q “ det ˆ 1 2 2 6 ˙ “ 2 ‰ 0, et detp∆3q “ detpAq ‰ 0. 3. (a) Le fait que A admet une (unique) factorisation LU revient à dire que l’on peut eﬀectuer l’algorithme de Gauss sans pivot. On regroupe A et b b b (en ajoutant b b b à droite de A) : ¨ ˝ 1 2 ´3 1 2 6 ´5 ´1 1 ´2 7 2 ˛ ‚ Ý Ñ L2ÐL2´2L1 L3ÐL3´L1 ¨ ˝ 1 2 ´3 1 0 2 1 ´3 0 ´4 10 1 ˛ ‚ Ý Ñ L3ÐL3`2L2 ¨ ˝ 1 2 ´3 1 0 2 1 ´3 0 0 12 ´5 ˛ ‚ Ap0q “ A b b bp0q “ b b b Ap1q b b bp1q Ap2q b b bp2q En posant U “ Ap2q et c c c “ b b bp2q on est ramené à résoudre le système triangulaire supérieur Ux x x “ c c c, que l’on résout par remontée : $ & % 12x3 “ ´5 ñ permet de calculer x3 : x3 “ ´ 5 12 2x2 ` x3 “ ´3 ñ permet de calculer x2 connaissant x3 : x2 “ ´ 31 24 x1 ` 2x2 ´ 3x3 “ 1 ñ permet de calculer x1 connaissant x2, x3 : x1 “ 7 3 1 (b) Pour trouver la factorisation LU de A on reprend les étapes de l’algorithme de Gauss : ¨ ˝ 1 2 ´3 2 6 ´5 1 ´2 7 ˛ ‚ loooooooooomoooooooooon A“Ap0q Ý Ñ L2ÐL2´2 2 2˚L1 L3ÐL3´1 1 1˚L1 ¨ ˝ 1 2 ´3 0 2 1 0 ´4 10 ˛ ‚ loooooooooomoooooooooon Ap1q “ ¨ ˝ 1 0 0 ´2 1 0 ´1 0 1 ˛ ‚ loooooooomoooooooon Ep1q ¨ ˝ 1 2 ´3 2 6 ´5 1 ´2 7 ˛ ‚ loooooooooomoooooooooon Ap0q Ý Ñ L3ÐL3´p´2 ´2 ´2q˚L2 ¨ ˝ 1 2 ´3 0 2 1 0 0 12 ˛ ‚ loooooooomoooooooon Ap2q “ ¨ ˝ 1 0 0 0 1 0 0 2 1 ˛ ‚ looooooomooooooon Ep2q ¨ ˝ 1 2 ´3 0 2 1 0 ´4 10 ˛ ‚ loooooooooomoooooooooon Ap1q Notons que Ep1q est inversible, et pEp1qq´1 “ ¨ ˝ 1 0 0 2 1 0 1 0 1 ˛ ‚ . De même, Ep2q est inversible, et pEp2qq´1 “ ¨ ˝ 1 0 0 0 1 0 0 ´2 1 ˛ ‚. Ainsi, à la ﬁn de la 1ère étape de la méthode de Gauss on a : Ap1q “ Ep1qA, et à la ﬁn de la 2ème étape on obtient : U “ def Ap2q “ Ep2qAp1q “ Ep2qEp1qA. De l’égalité ci-dessus, on a Ep2qEp1qA “ U ð ñ A “ pEp2qEp1qq´1U ð ñ A “ ´ pEp1qq´1pEp2qq´1¯ U ð ñ A “ LU avec L “ def “ pEp1qq´1pEp2qq´1 “ ¨ ˝ 1 0 0 2 1 0 1 0 1 ˛ ‚ ¨ ˝ 1 0 0 0 1 0 0 ´2 1 ˛ ‚“ ¨ ˝ 1 0 0 2 1 0 1 ´2 1 ˛ ‚. Notons que pour obtenir L il suﬃt de partir de la matrice identité I puis de recopier dans cette matrice, en les changeant de signe, les coeﬃcients utilisés à chaque opération élémentaire ¨ ˝ 1 0 0 0 1 0 0 0 1 ˛ ‚Ý Ñ ¨ ˝ 1 0 0 2 2 2 1 0 1 1 1 ´2 ´2 ´2 1 ˛ ‚. I L “ pEp1qq´1pEp2qq´1 Si l’on souhaite directement trouver la factorisation LU de A sans passer par les étapes de l’algorithme de Gauss, alors on cherche L “ ¨ ˝ 1 0 0 ℓ21 1 0 ℓ31 ℓ32 1 ˛ ‚et U “ ¨ ˝ u11 u12 u13 0 u22 u23 0 0 u33 ˛ ‚telles que LU “ A. Identiﬁons les coeﬃcients ligne par ligne : Étape 1 : identiﬁcation de la première ligne de LU “ A : u11 “ a11 “ 1, u12 “ a12 “ 2, u13 “ a13 “ ´3. Étape 2 : identiﬁcation de la deuxième ligne de LU “ A : ℓ21u11 “ a21 “ 2 ñ ℓ21 “ 2, ℓ21u12 ` u22 “ a22 “ 6 ñ u22 “ 2, ℓ21u13 ` u23 “ a23 “ ´5 ñ u23 “ 1. Étape 2 : identiﬁcation de la troisième ligne de LU “ A : ℓ31u11 “ a31 “ 1 ñ ℓ31 “ 1, ℓ31u12 ` ℓ32u22 “ a32 “ ´2 ñ ℓ32 “ ´2, ℓ31u13 ` ℓ32u23 ` u33 “ a33 “ 7 ñ u33 “ 12. 2 C’est cette méthode que l’on généralisera ci-dessous, dans l’exercice 2, pour écrire l’algorithme de calcul de la factorisation LU d’une matrice A de dimension quelconque. Utilisons maintenant cette factorisation LU pour résoudre le système Ax x x “ b b b. On a Ax x x “ b b b ð ñ LUx x x “ b b b ð ñ Ly y y “ b b b puis Ux x x “ y y y On résout par descente Ly y y “ b b b et on trouve y y y “ p1, ´3, ´5qt (notons que y y y “ c c c de la question (a)). Puis on résout Ux x x “ y y y par remontée, et on trouve x x x “ p 7 3, ´ 31 24, ´ 5 12qt. (c) Eﬀectuons maintenant l’algorithme de Gauss avec pivot partiel. On commence par chercher dans la colonne 1 le plus grand nombre en valeur absolue : ici 2 (à la 2ème ligne) et on permute la 2ème ligne avec la 1ère : ¨ ˝ 1 2 ´3 1 2 6 ´5 ´1 1 ´2 7 2 ˛ ‚ Ý Ñ L2ØL1 ¨ ˝ 2 6 ´5 ´1 1 2 ´3 1 1 ´2 7 2 ˛ ‚ Ensuite on eﬀectue la 1ère étape de la méthode de Gauss : ¨ ˝ 2 6 ´5 ´1 1 2 ´3 1 1 ´2 7 2 ˛ ‚ Ý Ñ L2ÐL2´ 1 2 1 2 1 2 L1 L3ÐL3´ 1 2 1 2 1 2 L1 ¨ ˝ 2 6 ´5 ´1 0 ´1 ´ 1 2 3 2 0 ´5 19 2 5 2 ˛ ‚ On cherche maintenant dans la colonne 2 à partir de la ligne 2 le plus grand nombre en valeur absolue : ici -5 (à la 3ème ligne) et on permute la 3ème ligne avec la 2ème : ¨ ˝ 2 6 ´5 ´1 0 ´1 ´ 1 2 3 2 0 ´5 19 2 5 2 ˛ ‚ uploads/Litterature/ td6-corrige 2 .pdf