Remerciez-le!

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

M1 Math´ ematiques Fondamentales et Appliqu´ ees (MFA) Universit´ e Paris–Sud D

M1 Math´ ematiques Fondamentales et Appliqu´ ees (MFA) Universit´ e Paris–Sud D4MA10 : MAO Option calcul scientiﬁque Centre d’Orsay Ann´ ee 2008 −2009 TP8 : Quelques m´ ethodes de r´ esolution de syst` emes lin´ eaires Ce TP porte sur les m´ ethodes de r´ esolution des syst` emes lin´ eaires. Les matrices utilis´ ees seront celles obtenues par discr´ etisation par diff´ erences ﬁnis du Laplacien (les matrices obtenues par une discr´ etisation par ´ el´ ements ﬁnis sont aussi valables) ou des matrices g´ en´ er´ ees al´ eatoirement, satisfaisant certaines propri´ et´ es particuli` eres (sym´ etrie, d´ eﬁnie positive,etc.). On joint ` a cet effet des scripts MATLAB , pour la discr´ etisation par diff´ erences ﬁnies du Laplacien en 1D et 2D, et pour la g´ en´ eration al´ eatoire des matrices de propri´ et´ es particuli` eres. Cette ﬁche est constitu´ ee de 5 parties dont la partie 5 est un ´ el´ ement de r´ eponse ` a la partie 4. PARTIE - 1 M´ ethodes directes Exercice - 1 M´ ethode de r´ esolution par la factorisation LU Algorithme de r´ esolution de syst` emes triangulaires inf´ erieures (` a gauche) et sup´ erieures (` a droite) --------------------------------------------------------------------------------------- ALGORITHME DE DESCENTE | ALGORITHME DE REMONTEE --------------------------------------------------------------------------------------- Donn´ ees: A,b. R´ esultat:x solution de A x= b| Donn´ ees: A,b. R´ esultat:x solution de A x=b -------------------------------------------|------------------------------------------- pour i= 1 ` a n | pour i= n ` a 1 s= 0 | s = 0 pour j = 1 ` a i-1 | pour j = i+1 ` a n s = s + A(i,j) * x(j) | s = s + A(i,j) * x(j) fin j | fin x(i) = (b(i) - s) /A(i,i) | x(i) = (b(i) - s)/A(i,i) fin |fin Q-1 : ´ Ecrire une une fonction MATLAB de prototype function [x] = Descente (A, b), qui r´ esout un syst` eme lin´ eaire triangulaire inf´ erieure Ax = b. Tester la fonction en g´ en´ erant al´ eatoirement des matrices triangulaires inf´ erieures inversibles (voir ci-dessus), de tailles n et en effectuant : b = rand(n,1), norm(b - Descente(A,A*b)). Q-2 : Mˆ eme question pour les matrices triangulaires sup´ erieures inversibles. La fonction aura pour prototype, function [x] = Remontee (A, b). Q-3 : ´ Ecrire une fonction MATLAB de prototype function [L,U] = decompLU (A) qui effectue la d´ ecomposition LU d’une matrice carr´ ee. Algorithme de d´ ecomposition A = LU 1 Donn´ ee: A. | 2 R´ esultat: U triangulaire sup´ erieure | Explications des notations et indications 3 L triangulaire inf´ erieure (diagonale unit´ e)| 4 -------------------------------------------| ----------------------------------------------- 5 pour k = 1 ` a n |% : introduit un commentaire 6 pour i = k+1 ` a n | 7 A(i,k)= A(i,k)/ A(k,k) | 8 pour j = k+1 ` a n | 9 A(i,j)=A(i,j)-A(i,k)*A(k,j) | 10 fin | 11 fin | 12 fin | Commande MATLAB pour r´ ecup´ erer L et U 13 R´ ecup´ erer L et U ` a partir de A | U=triu(A); L = A - U + diag(ones(n,1)); Q-3-1 : ´ Evaluer cette fonction sur la matrice A =     2 4 −4 1 3 6 1 −2 −1 1 2 3 1 1 4 1    . Conclure en calculant tous les mineurs principaux d’ordre k, k = 1 . . . 3 de A. Q-3-2 : On consid` ere la matrice de permutation P =     0 1 0 0 0 0 1 0 1 0 0 0 0 0 0 1    . . V´ eriﬁer que le produit PA admet une factorisation LU, en ´ evaluant [L,U] = decompLU(PA). Expliquer alors comment r´ esoudre un syst` eme lin´ eaire dont la matrice est la matrice A ci-dessus. Q-4 : La question pr´ ec´ edente met en ´ evidence la n´ ecessit´ e de pivot dans la factorisation LU de certaines matrices. Q-4-1 : Montrer que pour toute matrice inversible A ∈Mm(R), il existe une matrice de permutation P telle que la matrice PA admette une factorisation LU. Compar´ ee ` a la factorisation LU, on a all´ eg´ e les hypoth` eses sur la matrice A pour que la factorisation PA = LU soit possible. Lesquelles ? Q-4-2 : ´ Ecrire une fonction MATLAB de prototype [L,U,P] = decompLUP(A), qui effectue une factorisa- tion LU d’une matrice r´ eguli` ere A selon une m´ ethode de Gauss avec pivot partiel, c’est ` a dire avec une permutation de lignes. (L’algorithme est donn´ e ci-dessous). Algorithme de d´ ecomposition PA =LU Donn´ ee: A. R´ esultats: A contenant L,et U | Explications des notations et indications et P vecteur de permutation des lignes | -------------------------------------------| ----------------------------------------------- pour i =1 ` a n P(i) = i fin |% : introduit un commentaire pour k = 1 ` a n |ipivot est telle que |A(ipivot,k)|=max|A(i,k)| k<= i <= n recherche la ligne ipivot du pivot: | commande MATLAB de recherche du pivot : permuter les lignes P(ipivot) et P(k) |[vpivot,ipivot]=max(abs(A(k:n,k))); ipivot = k - 1 + ipivot; pour i = k+1 ` a n | commande MATLAB pour permuter les lignes P(ipivot) et P(k) : A(i,k)= A(i,k)/AA(k,k) |ip=P(ipivot); P(ipivot)=P(k);P(k)= ip; pour j = k+1 ` a n |v=A(k,:); A(k,:) = A(ipivot,:); A(ipivot,:)= v; A(i,j) = A(i,j)-A(i,k) * A(k,j) | fin | fin | Exercice - 2 Complexit´ e de la m´ ethode de d´ ecomposition LU Q-1 : Complexit´ e de la factorisation. Q-1-1 : Modiﬁer la fonction [L,U] = decompLU(A) de l’exercice pr´ ec´ edent, en une fonction [L,U,nop] = decompLU nop(A) qui retourne en plus le nombre de multiplications et de divisions effectu´ ees pen- dant la factorisation LU. (On Pourra initialiser nop ` a 0 en d´ ebut de fonction et l’incr´ ementer, dans les boucles de la factorisation LU, ` a chaque fois qu’on rencontre une multiplication ou une division (algo-lignes 7 et 9)). Q-1-2 : Justiﬁer l’existence de la factorisation LU d’une matrice sym´ etrique d´ eﬁnie positive. G´ en´ erer des matrices sym´ etriques d´ eﬁnies positives de tailles n = 1, · · · 30. Relever Nop(n) fourni par la factorisation decompLU nop(A) et repr´ esenter sur un mˆ eme graphique la courbe n 7− →Nop(n) et la courbe n 7− →n3/3. Qu’observe-t-on ? (On pourra utiliser le script MATLAB ci-dessous qui r´ ealise cette exp´ erience). fichier nopLU.m de test de la complexit´ e de la factorisation LU x=[]; ni=[]; Nop=[];ind=0; for i =5:20 ind=ind+1; x(ind)= i; A=MatSdp(i); % voir TP1 [L,U,Nop(ind)] = decompLU_nop(A); ni(ind) = (iˆ3)/3. ; end plot(x,Nop,’*’,x,ni,’-’); legend(’Nop LU’,’nˆ3 / 3’); Q-1-3 : Reprendre la mˆ eme exp´ erience en ne repr´ esentant que la courbe n 7− →Nop(n) en ´ echelle logarithmique. D´ eterminer la pente de la droite la plus proche de cette courbe et conclure. (On utilisera la commande MATLAB loglog pour la repr´ esentation en ´ echelle logarithmique). Exercice - 3 Ph´ enom` ene de remplissage Q-1 : Modiﬁer la factorisation LU de sorte qu’elle retourne les facteurs L, U dans une matrice de la taille de A ; U ´ etant stock´ ee dans la partie sup´ erieure et L (sauf sa diagonale) dans la partie inf´ erieure. Le prototype de la fonction sera function [A]=decompLU eco(A). Q-2 : On consid` ere la matrice de taille n d´ eﬁnie sous MATLAB , pour n donn´ ee, par : A = eye(n) ; A( :,1)=1 ; A(1, :)=1 ; A(1,1)=n ; Q-2-1 : Pour diverses valeurs de n, afﬁcher la matrice A (commande spy). Afﬁcher aussi la matrice B=decompLU eco(A). Qu’observe-t-on ? Q-2-2 : Que retourne la commande MATLAB length(find(A)) ? Comparer length(find(A)) et length(find(decompLU eco(A))). Conclure. PARTIE - 2 M´ ethodes directes : pratiques Exercice - 1 M´ ethode de r´ esolution par la factorisation Cholesky Q-1 : D´ ecomposition Cholesky et complexit´ e. Q-1-1 : ´ Ecrire une fonction MATLAB de prototype function [L,Nop] = decompCholesky(A) qui effectue la d´ ecomposition Cholesky d’une matrice carr´ ee sym´ etrique d´ eﬁnie positive et retourne le nombre Nop de multiplications et de divisions effectu´ ees. Q-1-2 : G´ en´ erer al´ eatoirement des matrices sym´ etriques d´ eﬁnies positives (voir scripts joints) de taille n = 5, . . . 30 et repr´ esenter en ´ echelle logarithmique, la courbe n 7− →Nop(n), o` u Nop(n) est le nombre d’op´ erations fournies par la d´ ecomposition Cholesky pr´ ec´ edente. En d´ eduire la complexit´ e de la factorisation Cholesky ; c’est-` a-dire les constantes C et α, telles que Nop(n) ≈Cnα. Comparer cette complexit´ e ` a celle obtenue par la factorisation LU (voir Parties pr´ ec´ edentes). Q-2 : Inversion du syst` eme lin´ eaire par la factorisation Cholesky. Q-2-1 : Ecrire une fonction MATLAB de prototype function [x] = inverseCholesky(L,b) qui r´ esout le syst` eme LLT x = b. Tester cette fonction sur quelques exemples. Exercice uploads/s3/ fiche-8.pdf