Mathematiques assistees par ordinateur Chapitre Calcul matriciel et algebre lineaire

De
Publié par

Mathematiques assistees par ordinateur Chapitre 9 : Calcul matriciel et algebre lineaire Michael Eisermann Mat249, DLST L2S4, Annee 2008-2009 www-fourier.ujf-grenoble.fr/˜eiserm/cours _ mao Document mis a jour le 6 juillet 2009 1/56

  • reduction des endomorphismes espaces vectoriels

  • methode des iterations inverses

  • calcul de la solution

  • mathematiques assistees par ordinateur chapitre

  • systeme d'equations lineaires

  • algorithme de gauss calcul matriciel


Publié le : lundi 18 juin 2012
Lecture(s) : 55
Source : www-fourier.ujf-grenoble.fr
Nombre de pages : 56
Voir plus Voir moins
Math´ematiquesassist´eesparordinateur Chapitre9:Calculmatricieletalg`ebrelin´eaire
Michael Eisermann
Mat249, DLST L2S4, Anne´ e 2008-2009 www-fourier.ujf-grenoble.fr/˜eiserm/cours # mao Document mis a` jour le 6 juillet 2009
1/56
Sommaire
1
2
3
4
R´esolutiondesyste`mesd´equationslin´eaires Syste` mes d’e´ quations line´ aires, l’algorithme de Gauss Calcul matriciel : addition, multiplication, inversion, de´ terminant Stabilite´num´erique,conditionnementdunematrice
Re´ duction des endomorphismes Espacesvectorielsetapplicationslin´eaires Vecteurs propres, polynome caracte´ ristique ˆ Polynomeminimal,m´ethodesdecalcul ˆ
Me´thodesapproche´esit´eratives La methode de la puissance ´ Lam´ethodedesite´rationsinverses Matrices hermitiennes et syme´ triques
Comment fonctionne Google ? Comment mesurer l’importance d’une page web ? Le mode` le PageRank : marche ale´ atoire sur le web Existence, unicite´ , et calcul de la solution
2/56
§1.
Syst`emesd´equationslin´eaires Dans la suite nous fixons un corpsK(par exempleQ,R, ouC). Nous souhaitons re´ soudre un line´ airessyste` me quations d’e´: a11x1+a12x2+∙ ∙ ∙+a1nxn=y1 a21x1+a22x2+∙ ∙ ∙+a2nxn=y2
1
. am1x1+am2x2+∙ ∙ ∙+amnxn=ym
Ici les coefficientsaijKetyiKnndontsos.´e L’objectif est de trouver toutes les solutionsxiK.
On´ecritcesyste`meplussuccinctementcommeA` x=you aa2111aa2122aa......12nn xx12 yy12 .. .A=am1am2. . . amn, x=x.n, y=y.m.
Cette structuration est bien plus qu’une notation commode : Programmes = structure de don ´ s + algorithmes ! s nee  . .Calcul matriciel : addition, multiplication, inverse, de´ terminant, .
3/56
Matricestriangulaireset´echelonn´ees Oncherche`are´soudreunsyst`emed´equationsline´airesAx=y. SiAesttriangulairefsuertdonemr.teile:atdi´emmtiesnoitulosal, 101 1 0 0 0 1000001voireA=100000010010. A= us ge: Pl´ene´ralementlasolutionestfacilesiAest´cenne´ehol 1001 001010000A 0 0 1= 0∗ ∗ ∗voireA 0 0 1= 0∗ ∗0. 0000000001000000000000100000Danscetexemplel´equationAx=yn’a pas de solution siy56= 0. Siy5= 0, les solutionsxtelles queAx=yforment un sous-espace affine deK7de dimension3: on peut choisirx2, x5, x6arbitrairement, les valeursx7, x4, x3, x1s’en de´ duisent en remontant. «Solution ge´ ne´ rale = solution particulie` re + solutions homoge` nes.» §1.1 4/56
§.1
Ope´ rations elementaires ´ ´ Objectif :formsousheloe´ectteremeen´onenuee´nndecirtam a11. . A=.aa1nnm=LL.1m. am.1. . ..
1
Pour ceci on effectue desaintme´eels´ontiserpoe´arsur les lignes : LiLjerlahang´eceilngiet la lignej, LiλLimultiplier la ligneipar un facteur inversibleλ, LiLi+λLjajouter un multiple de la lignejal`neigali.
` Anoterquechacunedecesop´erationsestinversible! Ainsi on les appelle aussitransformations d’e´ quivalence.
Pourr´esoudreAx=ynsiorsup´soatereftceuecnofe(A|y): c’est la matriceAagrandie en accolant le vecteur colonney. Lefaitquenosop´erationstransformant(A|y)en(A0|y0)soient inversiblesgarantitquelessyst`emeslin´eairesAx=yetA0x=y0 ontexactementlesmˆemessolutions.
/556
§1.
L’algorithme de Gauss : ide´ e D’abord on choisit un pivotaj16= 0 : teet on le place en teˆ a11a21. . . a1n a21a22 a. . .2nL1Ljaa1112aa2212.a.....a12nn−−−→ . . .am.1a.m2. . . a.mnam1am2 a. . .mn
1
Ensuite on annule la premie` re colonne : L1a111L1a211aa2122.a..a...12nn−−−−−−−→ a116=0am.1am.2. . . am.n1a21 a. . .1n LjLjaj1L0a22 a. . .2n1 −−−−−−−−−→ j=2,...,m.0a.m2. . . a.mn
ce{2, . . . , m} × {2, . .
Onit`erecettem´ethodesurlasous-matrice{2, . . . , m} × {2, . . . , n}.
/656
§1.
LalgorithmedeGauss:formulationde´taille´e
1
L’algorithme de Gauss transforme une matriceAen une matrice e´chelonn´eea`laidedesope´rations´ele´mentairessurleslignes: 1On initialisec1et`1. Icic roest le nume´ de la colonne, et` estlenum´erodelalignea`partirdelaquelleonchercheunpivot. 2Sic > nou` > m, alors on arreˆ te. 3Si la colonnec de la ligne partirn’a que des coefficients nuls a``, on i cr ´ ntecet on passe `a l’e´ tape 2. n eme 4On choisit un pivotakconnun,l`ouk∈ {`, . . . , m}. En calcul exact on cherche un pivotakcle plus simple possible. En calcul approch ´e on chercheakcde plus grande valeur absolue. Sik > `on effectueL`Lke´ changeant les lignes`etk. = On divise,L`a`c1L`, afin d’obtenir un pivota`c1. On effectue pour toutes les lignesk=`+ 1, . . . , ml’operation ´ LkLkakcL`annulant les coefficients en dessous du pivot. Optionnellement on annule les coefficients au dessus du pivot. On incre´ mentecet``´lapate.2eetpaon sse
5 6 7 8 9
7/56
L’algorithme de Gauss : complexite´ du calcul Proposition Afin de mettre une matriceAKm×nsous forme e´ chelonne´ e, l’algorithme de Gauss effectue au plusmn2ope´ rations dansK. D´emonstration.`seaffceutreanopdrembontira´epmoConelsnot de traiter lac-i`emloceennoruopc= 1, . . . , n. (On supposeranm.) D’abord, pour mettre le pivot en place : nce´ changes puisncdivisions dansK. Ensuite, pour e´ liminer les coefficients dans la colonne du pivot : (m1)(nc)multiplications et soustractions dansK. Au total cela fait2m(nc) dansope´ rationsKpour lacmecelonoen.i`-Il faut ensuite sommer surc= 1, . . . , n sultat., ce qui donne le re´ On a applique´ ici quelques optimisations : les coefficients des colonnespr´ec´edentessontd´eja`annul´esetnejouentplusaucunrˆole. Ceci´economiseunfacteur21. (Sinon on effectue2mn2ope´ rations.) Onconsid`ereicilesope´rationsdansKstontcˆuco`aant,cequi n’est justifie´ que siKest fini, ou si les coefficients restent petits. Sur un corps commeQouQ(X), meˆ me pour une matrice modeste, §1.1les calculs provoquent souvent une«explosion des coefficients».8/56
§.1
Avertissementnum´erique:lebonpivot Soit`ar´esoudrelesystemeline´airesuivantavecunparame`treε0: ` xxε2+1+..00yy3=1=..00
1
La solution exacte estx=121ε1ety=11−−23εε1 !). (Exercice
On obtient
Supposons d’abord que l’on utilise le pivot1, comme il se doit : xxε+1+2..00yy==31..00 x+(1.20.02y.0ε)y=1=(.30.03.0ε)
puis
Sur ordinateur on effectue souvent des calculs arrondis ! Par exemple, pour une pre´ cision de52bits et|ε| ≤254, le calcul arrondi´evalue1.02.0εa`1.0emtdemeˆe1.03.0εa`1.0.
Enmodeapproch´e,oncalculey= 1.0puis en remontantx= 1.0. Ce n’est plus exact, mais reste assez proche de la vraie solution.
/965
§1.
Avertissementnume´rique:lemauvaispivot Onconsid`eretoujourslemeˆmesyste`meline´aireo`uε0. εx+ 1.0y= 1.0 x+ 2.0y= 3.0
1
On obtient
Supposons que l’on utilise (maladroitement) comme pivotε: x+1.ε0y=1.ε0 x+ 2.0y= 3.0 (x+1.0y1.0 = ε ε 2.01ε.0y=3.01.ε0
puis
Icilecalcularrondime`nein´evitablementa`lacatastrophe! Pour une pre´ cision de52bits et0< ε254, le calcul arrondi ´evalue(2.01.ε0)`a(1.ε0)tedemˆeme(3.01.ε0)a`(1ε.0). On calcule ainsiy= 1.0et en remontantx= 0.0 ! faux s. C’est tre` Pire encore, l’utilisateur non averti ne s’en rendra pas compte.
Contrairement`auncalculr´ee´chi,deslogicielsnum´eriquesignorent souventdesanomalies.Desv´ericationssontindispensables!
10/56
Calcul matriciel : notation FixonsI={1, . . . , m}etJ={1, . . . , n}avecm, nN. Unematricede taillem×n dansa` coefficientKest une famille A= (aij)eml´´edstneaijKindexes par(i, j)I×J. ´ ´ Ce n’est rien autre qu’une applicationa:I×JKnotee(i, j)7→aij. L’ensemble de ces matrices sera note´Km×n. Dans la pratiqueAec´sarectangulaire,irctmoemnucs´hme aveciIindexant les lignes etjJindexant les colonnes. Les matricesm×1sont lesvecteurs colonnes, alors que les matrices1×nsont lesvecteurs lignes. ` A chaque matriceA= (aij)ijde taillem×non peut associer la matrice transpose´ eAt= (aij)jide taillen×m. Sur ordinateur, on stocke une matricem×ncomme untableau. Cela marche assez bien pour les matrices de taille modeste. (Pour lesgrandesmatricescreusesilfaudra´economiserdelam´emoire...) Jusqu’iciKm×ncuuterpssenassrt.´eciquenuuqtselbmesnen Lath´eoriedevientinte´ressantequandKest un corps (ou anneau) : dans ce cas on peut de´ finir une addition et une multiplication. . . §1.2 11/56
Soyez le premier à déposer un commentaire !

17/1000 caractères maximum.