Remerciez-le!

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

Factorisation LU et de Cholesky Références : Algèbre linéaire numérique, Grégoi

Factorisation LU et de Cholesky Références : Algèbre linéaire numérique, Grégoire Allaire Théo. Soit une matrice A = (aij)1≤i,j≤n d’ordre n dont toutes les sous- matrices diagonales ∆k =         a11 . . . a1k . . . . . . . . . . . . . . . ak1 . . . akk         sont inversibles. Il existe un unique couple (L, U) avec U triangulaire supé- rieure et L triangulaire inférieure à diagonale unité tel que A = LU. Démonstration. Supposons qu’au cours de l’élimination de Gauss, il n’y ait pas besoin de faire de permutations pour changer de pivot, ie que tous les pivots naturels sont non nuls. Alors on a A(n) = En−1...E1A avec Ek =                1 0 . . . . . 0 0 . . . . . . . . . 1 . . . . . . . −lk+1,k 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 0 . −ln,k . . . . 1                et pour i ∈Jk + 1, nK, lik = a(k) ik a(k) kk . On pose U = A(n) et L = (E1)−1...(En−1)−1. Alors on a A = LU et il reste simplement à vériﬁer que L est bien triangulaire supérieure. On trouve facilement que (Ek)−1 =                1 0 . . . . . 0 0 . . . . . . . . . 1 . . . . . . . lk+1,k 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 0 . ln,k . . . . 1                De la même manière, on a que L           1 0 . . . 0 l21 . . . . . . . . . . . . . . . . . . . . . . 0 ln1 . . . lnn−1 1           Montrons maintenant que les pivots ne s’annulent pas sous l’hypothèse faite sur les matrices ∆k. On le fait par récurrence. Le premier pivot a11 est non nul car égal à ∆1 qui est inversible. On suppose que tous les pivots jusqu’à l’ordre k −1 sont non nuls. Montrons que le nou- veau pivot ak kk est aussi non nul. Comme les k −1 premiers pivots sont non nuls, on a pu calculer A(k). On écrit alors l’égalité (E1)−1...(Ek−1)−1A(k) = A sous la forme d’une égalité entre matrices par blocs : L(k) 11 0 L(k) 21 I ! U (k) 11 A(k) 12 A(k) 21 A(k) 22 ! = Ç∆k A12 A21 A22 å avec U (k) 11 , L(k) 11 et ∆k des blocs carrés de taille k, et A(k) 22 , I et A22 des blocs carrés de taille n −k. En appliquant la règle de multiplication des matrices 1 Factorisation LU et de Cholesky par blocs, on obtient L(k) 11 U (k) 11 = ∆k, où U (k) 11 est une matrice triangulaire supérieure et L(k) 11 une matrice trian- gulaire inférieure avec des 1 sur la diagonale. On en déduit que la matrice U (k) 11 = (L(k) 11 )−1∆k est inversible comme produit de matrices inversibles. Son déterminant est donc non nul. Or det(U (k) 11 ) = k Y i=1 a(k) ii ̸= 0, donc le pivot a(k) kk à l’étape k est non nul. Il ne reste plus qu’à vériﬁer l’unicité. Soient deux décompositions LU de la matrice A A = L1U1 = L2U2. On en déduit que L−1 2 L1 = U2U −1 1 où la matrice L−1 2 L1 est triangulaire inférieure et U2U −1 1 est triangulaire supérieure. Elles sont donc toutes les deux diagonales, et comme la diagonale de L2L−1 1 est composée de 1, on a L−1 2 L1 = U2U −1 1 = In d’où l’unicité. Théo. Soit A une matrice symétrique réelle déﬁnie positive. Il existe une unique matrice réelle B triangulaire inférieure, telle que tous ses éléments diagonaux sont strictement positifs et qui vériﬁe : A = BtB. Démonstration. On vériﬁe l’hypothèse sur les mineurs. Comme A est sy- métrique déﬁnie positive, on peut lui associer un produit scalaire φ. On a donc que A =         φ(e1, e1) . . . φ(e1, en) . . . . . . . . . . . . . . . φ(en, e1) . . . φ(en, en)         Si on écrit le mineur d’ordre k, on a ∆k =         φ(e1, e1) . . . φ(e1, ek) . . . . . . . . . . . . . . . φ(ek, e1) . . . φ(ek, ek)         On a donc que ∆k est la matrice de φ sur V ect(e1, ..., ek). Elle est donc déﬁ- nie positive et inversible. Par application du théorème sur la décomposition LU, il existe un unique couple de matrices (L, U) tel que A = LU avec L =           1 0 . . . 0 × . . . . . . . . . . . . . . . . . . . . . . . × . . . × 1           et U =           u11 × . . . × 0 . . . . . . . . . . . . . . . . . . . . . . . 0 . . . 0 unn           On note D la matrice diagonale déﬁnie par D = diag(√uii). On a bien que les uii sont strictement positifs car Qk i=1 uii = det(∆k) > 0. On pose alors B = LD et C = D−1U qui vériﬁe A = BC. Comme A =t A, on en déduit C(tB)−1 = (B−1)tC. La matrice C(tB)−1 est triangulaire supérieure tandis que (B−1)tC est tri- angulaire inférieure. Elles sont donc toutes les deux diagonales. De plus, tous les éléments diagonaux de B et C sont les mêmes, donc la diagonale de (B−1)tC n’est constituée que de 1. On en déduit C(tB)−1 = (B−1)tC = In ⇒C =t B. Pour montrer l’unicité de la décomposition de Cholesky, on suppose qu’il existe deux factorisations A = Bt 1B1 = Bt 2B2, 2 Factorisation LU et de Cholesky d’où B−1 2 B1 =t B2(tB1)−1. Il existe donc une matrice diagonale D = diag(d1, ..., dn) telle que B−1 2 B1 = D ⇒B1 = B2D. On en déduit que A = Bt 2B2 = B2(DtD)tB2. Comme B2 est inversible, il vient D2 = In donc di = ±1. Or tous les coeﬃcients diagonaux d’une décomposition de Cholesky sont positifs par hypothèse. Donc di = 1 ce qui implique B1 = B2. Leçons possibles : 162 3 uploads/Litterature/ factorisation-lu-et-de-cholesky.pdf