Universite Joseph Fourier L3 Methodes Numeriques 2eme semestre
4
pages
Français
Documents
Le téléchargement nécessite un accès à la bibliothèque YouScribe Tout savoir sur nos offres
4
pages
Français
Documents
Le téléchargement nécessite un accès à la bibliothèque YouScribe Tout savoir sur nos offres
Niveau: Supérieur, Licence, Bac+3
Universite Joseph Fourier L3 Methodes Numeriques 2eme semestre 2008/2009 Feuille d'exercices no 3 Resolution de systemes lineaires. Methodes directes Exercice 1 : Donner l'ordre de grandeur du nombre d'operations necessaires pour calculer le determinant et l'inverse d'une matrice A de taille n? n grace aux formules det(A) = ∑ ???n ?(?)a1?(1)a2?(2)...an?(n) et A?1 = 1 det(A) tcom(A) . Meme question mais en utilisant la decomposition A = LU (methode de Gauss). Un ordinateur standard effectue de l'ordre de 1010 operations par secondes (10 gigaflops). Comparer les temps necessaires dans le cas d'une matrice 100? 100. Exercice 2 : Soit Eij(?) la matrice egale a l'identite sauf pour le coefficient (i, j) qui vaut ?. Soit A une matrice quelconque. Comment la multiplication a droite et a gauche par Eij(?) agit-elle sur A ? Exercice 3 : Donner une decomposition LU des matrices suivantes A = ( 1 4 ?1 2 ) B = ? ? ?2 3 0 1 0 ?4 2 0 5 ? ? . Exercice 4 : Decomposition QR. On munit Cn du produit hermitien canonique < x|y >= ∑ xiyi.
Voir
Universite Joseph Fourier L3 Methodes Numeriques 2eme semestre 2008/2009 Feuille d'exercices no 3 Resolution de systemes lineaires. Methodes directes Exercice 1 : Donner l'ordre de grandeur du nombre d'operations necessaires pour calculer le determinant et l'inverse d'une matrice A de taille n? n grace aux formules det(A) = ∑ ???n ?(?)a1?(1)a2?(2)...an?(n) et A?1 = 1 det(A) tcom(A) . Meme question mais en utilisant la decomposition A = LU (methode de Gauss). Un ordinateur standard effectue de l'ordre de 1010 operations par secondes (10 gigaflops). Comparer les temps necessaires dans le cas d'une matrice 100? 100. Exercice 2 : Soit Eij(?) la matrice egale a l'identite sauf pour le coefficient (i, j) qui vaut ?. Soit A une matrice quelconque. Comment la multiplication a droite et a gauche par Eij(?) agit-elle sur A ? Exercice 3 : Donner une decomposition LU des matrices suivantes A = ( 1 4 ?1 2 ) B = ? ? ?2 3 0 1 0 ?4 2 0 5 ? ? . Exercice 4 : Decomposition QR. On munit Cn du produit hermitien canonique < x|y >= ∑ xiyi.
- methodes directes
- resolution des systemes lineaires
- cn de la norme ?x?∞
- precision des instruments et de l'ordinateur
- unique matrice triangulaire
- base de cn
- decomposition
- norme matricielle
Universite Methodes
Joseph Fourier Numeriques
o Feuille d’exercices n3
L3 eme 2semestre2008/2009
Resolution de systemes lineaires.
Methodes directes
Exercice 1 :nnerl’orDouednnudrderdargeerpioatbrom’oedseopasricesesnnerlculurca ledeterminantetl’inversed’unematriceAdetaillennxuaemrofselugacrˆ X 1 1t det(A) =ε()a1(1)a2(2)...an(n)etA= com(A). det(A) ∈n MˆemequestionmaisenutilisantladecompositionA=LU(methode de Gauss). 10 Unordinateurstandarde ectuedel’ordrede10operationsparsecondes(10gigaops). Comparerlestempsnecessairesdanslecasd’unematrice100100.
Exercice 2 :SoitEij() la matrice egale a l’identite sauf pour le coecient (i, j) qui vaut . SoitAune matrice quelconque.Comment la multiplication a droite et a gauche par Eij() agit-elle surA?
Exercice 3 :noopmoitisrunedecDonneLUdes matrices suivantes 02 3 1 4 A=B= 104. 1 2 2 0 5
Exercice4:DecompositionQR. P n . On munitCdu produit hermitien canonique< x|y >=xiyi n 1) Soienta1, ..., andes vecteurs formant une base deC. Montrerqu’il existe une base orthonormeeq1, ..., qnet des nombres complexesrij(ij) tels queriiest un reel positif pour toutiet a1=r11q1 a2=r12q1+r22q2 . an=r1nq1+. . .+rnnqn
1
2)EndeduirequetoutematriceinversibleApeut s’ecrireA=QRuoQest unitaire etR esttriangulairesuperieureaelementsdiagonauxreelsetpositifsetquecettedecomposition est unique. 3)CommentutilisercettedecompositionpourresoudrefacilementlesystemeAx=b? t 4) SoitA∈GLn(C), montrer queAAnestlelievi.euQleinpesotiitimrehtedennees entreladecompositiondeCholeskietladecompositionQR?
Exercice5:DecompositiondeCholeski. SoitAmierentidneniesopevitinO.epparellequ’ilexisteuennuqieuamrtcieehictrmaneu t triangulaireinferieureLeuqesfitlletqesedaiuentslemonaudiagcietsxrtopisemtnA=L L (decompositiondeCholeski). 1) Donner l’algorithme qui permet de calculerLa la matrice. L’appliquer 1 21 A13= 21. 11 3
Cet algorithme est-il appliquable a des matrices non hermitiennes ? 2)ExpliquercommentutiliserladecompositiondeCholeskipourresoudrelesystemeAx= berad’opmbrelenonnreteod.snoit 3) Une matriceA= (aij) est appeleepbande siaije=0desqu|ij| p. a) Donner des exemples de matricespbandes. b) Montrer que siAermiicehnedtienpesoeinetivisertamenutpbande, alorsLest aussipbande.
Methodes indirectes n Exercice 6 :On munitCup| de la normekxk∞= sixi|. OnmunitMn(C) de la norme triple associee.Montrer que n X kAxk |||A|||∞sup =sup|aij|. x∈C\{0}kxki=1,...,n n j=1 n k DonneruneconditionsusantesurApour que pour toutx∈C,A x →0 quand k →?easriceseelnt-elonesditiecon.0tteC
2
Exercice7:Matricesadiagonaledominante. On appelle matrice a diagonale dominante une matriceA= (aij)∈GLn(C) telle que, pour i= 1, ..., n, X |aii|>|aij|. j6=i 1) Donner un exemple de matrice a diagonale dominante. 2) Montrer que toute matrice a diagonale dominante est inversible. 3)OnsouhaiteappliquerlamethodedeJacobipourresoudrelesystemeAx=buoAest a diagonale dominante.On pose a1,10. . .0 0a1,2a. . .1,n . . . . 0a2,2..a2,10 .. M= etN= . . .. . . . . . .0. ... .an1,n 0. . .0an,nan,1. . .an,n10 LamethodedeJacobiconsistearechercherlepointxedequellefonction?Montrerque lamethodedeJacobiconvergetoujourssiAest a diagonale dominante.
Conditionnement PourresoudrelesystemeAx=b, il faut connaˆtrebnnuestpascolui-cin’areec,lnE.neg avecuneprecisioninniecarilpeutyavoirdeserreursdemesuresetcarlaprecisiondes instrumentsetdel’ordinateurn’estpasinnie.Ons’interessedoncal’erreurquipeutˆetre commise surxesuaisedrpmsicensiorsuacb. Lavaleur pertinente est l’erreur relative k xk/kxk.
Exercice 8 :stemeliudrelesynaerieoseretiahuosnOAx=bavec 1001 1000 A=. 1000 1001
1) Donner les valeurs propres et vecteurs propres deA. 2)Expliciterlaresolutiondel’equationAx=btincdeonelsmeetnpsorrpse.ofne 3)ResoudrelesystemeAx=bavecb= (1,1). Ona en fait une petite erreur surbqui est donnepar baveck bk/kbkde l’ordre de 0,a donc une erreur01. On xsurxrdnoneeap A(x+ x) =b+ brelative. L’erreurk xk/kxkest-elle grande ?
3
Exercice 9 :emteelerysesnocndisOAx=bavecA∈GLn(Rs.)eLsdonneeAetbsont imprecises.Onadoncenrealitelesystemelineaire (A+ A)(x+ x) =b+ b. Etantdonneeunenormematricielle,ondenitleconditionnementdelamatriceApar 1 (A) =|||A|||.|||A|||. A1 1) Montrer que si, on a |||A|||(A) k xk(A)k bk ||| A||| + ||| A||| kxk kbk |||A||| 1(A) |||A||| 2) Montrer que le conditionnement deAest minore par le rapport|n/1|u,onet1 sont respectivement la plus grande et la plus petite valeur propre en module.Expliquer l’exerciceprecedentdupointdevueduconditionnement.
TP Scilab Exercice 10 :rpgoernudenoarmmladnantposiecomontiriEcQRd’une matrice.Le transformer en un programme calculant l’inverse d’une matrice. Exercice 11 :eJacodedethrlamemmargorPbo.i
4
