Analyse Matr

Universit Aix Marseille

Licence de mathmatiques

Cours dAnalyse numrique

Raphale Herbin

8 octobre 2014

Table des matires

1 Systmes linaires 5

1.1 Objectifs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51.2 Pourquoi et comment ? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

1.2.1 Quelques rappels dalgbre linaire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51.2.2 Discrtisation de lquation de la chaleur . . . . . . . . . . . . . . . . . . . . . . . . . . 111.2.3 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 151.2.4 Suggestions pour les exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 191.2.5 Corrigs des exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

1.3 Les mthodes directes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 221.3.1 Dfinition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 221.3.2 Mthode de Gauss, mthode LU . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 221.3.3 Mthode de Choleski . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 301.3.4 Quelques proprits . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 361.3.5 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 381.3.6 Suggestions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 421.3.7 Corrigs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42

1.4 Normes et conditionnement dune matrice . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 501.4.1 Normes, rayon spectral . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 511.4.2 Le problme des erreurs darrondis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 561.4.3 Conditionnement et majoration de lerreur darrondi . . . . . . . . . . . . . . . . . . . . 561.4.4 Discrtisation dquations diffrentielles, conditionnement efficace" . . . . . . . . . . . 601.4.5 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 611.4.6 Suggestions pour les exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 661.4.7 Corrigs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67

1.5 Mthodes itratives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 761.5.1 Dfinition et proprits . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 761.5.2 Quelques exemples de mthodes itratives . . . . . . . . . . . . . . . . . . . . . . . . . . 781.5.3 Les mthodes par blocs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 841.5.4 Exercices, noncs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 871.5.5 Exercices, suggestions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 941.5.6 Exercices, corrigs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96

1.6 Valeurs propres et vecteurs propres . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1091.6.1 Mthode de la puissance et de la puissance inverse . . . . . . . . . . . . . . . . . . . . . 1101.6.2 Mthode QR . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1121.6.3 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1131.6.4 Suggestions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1171.6.5 Corrigs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117

1

TABLE DES MATIRES TABLE DES MATIRES

2 Systmes non linaires 122

2.1 Les mthodes de point fixe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1222.1.1 Point fixe de contraction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1222.1.2 Point fixe de monotonie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1262.1.3 Vitesse de convergence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1282.1.4 Mthode de Newton dans IR . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1302.1.5 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131

Analyse numrique I, tl-enseignement, L3 2 Universit dAix-Marseille, R. Herbin, 8 octobre 2014

Introduction

Lobjet de lanalyse numrique est de concevoir et dtudier des mthodes de rsolution de certains problmesmathmatiques, en gnral issus de la modlisation de problmes rels", et dont on cherche calculer la solution laide dun ordinateur.Le cours est structur en quatre grands chapitres :

Systmes linaires Systmes non linaires Optimisation Equations diffrentielles.

On pourra consulter les ouvrages suivants pour ces diffrentes parties (ceci est une liste non exhaustive !) : A. Quarteroni, R. Sacco et F. Saleri, Mthodes Numriques : Algorithmes, Analyse et Applications, Sprin-

ger 2006. P.G. Ciarlet, Introduction lanalyse numrique et loptimisation, Masson, 1982, (pour les chapitre 1 3

de ce polycopi). M. Crouzeix, A.L. Mignot, Analyse numrique des quations diffrentielles, Collection mathmatiques

appliques pour la maitrise, Masson, (pour le chapitre 4 de ce polycopi). J.P. Demailly, Analyse numrique et quations diffrentielles Collection Grenoble sciences Presses Univer-

sitaires de Grenoble L. Dumas, Modlisation loral de lagrgation, calcul scientifique, Collection CAPES/Agrgation, El-

lipses, 1999. E. Hairer, polycopi du cours "Analyse Numrique", http ://www.unige.ch/ hairer/polycop.html J. Hubbard, B. West, Equations diffrentielles et systmes dynamiques, Cassini. J. Hubbard et F. Hubert, Calcul Scientifique, Vuibert. P. Lascaux et R. Thodor, Analyse numrique matricielle applique lart de lingnieur, tomes 1 et 2,

Masson, 1987 L. Sainsaulieu, Calcul scientifique cours et exercices corrigs pour le 2me cycle et les coles dingnieurs,

Enseignement des mathmatiques, Masson, 1996. M. Schatzman, Analyse numrique, cours et exercices, (chapitres 1,2 et 4). D. Serre, Les matrices, Masson, (2000). (chapitres 1,2 et 4). P. Lascaux et R. Theodor, Analyse numrique sapplique aux sciences de lingnieur, Paris, (1994) R. Temam, Analyse numrique, Collection SUP le mathmaticien, Presses Universitaires de France, 1970.

Et pour les anglophiles... M. Braun, Differential Equations and their applications, Springer, New York, 1984 (chapitre 4). G. Dahlquist and A. Bjrck, Numerical Methods, Prentice Hall, Series in Automatic Computation, 1974,

Englewood Cliffs, NJ. R. Fletcher, Practical methods of optimization, J. Wiley, New York, 1980 (chapitre 3). G. Golub and C. Van Loan, Matrix computations, The John Hopkins University Press, Baltimore (chapitre

1). R.S. Varga, Matrix iterative analysis, Prentice Hall, Englewood Cliffs, NJ 1962.

Pour des rappels dalggre linaire : Poly dalgbre linaire de premire anne, P. Bousquet, R. Herbin et F. Hubert, http ://www.cmi.univ-

mrs.fr/ herbin/PUBLI/L1alg.pdf

3

TABLE DES MATIRES TABLE DES MATIRES

Introduction to linear algebra, Gilbert Strang, Wellesley Cambridge Press, 2008

Ce cours a t rdig pour la licence de mathmatiques distance (tlenseignement) du CTES de luniversitdAix-Marseille. Chaque chapitre est suivi dun certain nombre dexercices. On donne ensuite des suggestionspour effectuer les exercices, puis des corrigs dtaills. Il est fortement conseill dessayer de faire les exercicesdabord sans ces indications, et de ne regarder les corrigs dtaills quune fois lexercice achev (mme si certainesquestions nont pas pu tre effectues), ceci pour se prparer aux conditions dexamen.


Chapitre 1

Systmes linaires

1.1 Objectifs

On noteMn(IR) lensemble des matrices carres dordre n. Soit A Mn(IR) une matrice inversible, et b IRn,on a comme objectif de rsoudre le systme linaire Ax = b, cest dire de trouver x solution de :{

x IRnAx = b

(1.1)

Comme A est inversible, il existe un unique vecteur x IRn solution de (1.1). Nous allons tudier dans les deuxchapitres suivants des mthodes de calcul de ce vecteur x : la premire partie de ce chapitre sera consacre auxmthodes directes" et la deuxime aux mthodes itratives". Nous aborderons ensuite en troisime partie lesmthodes de rsolution de problmes aux valeurs propres.Un des points essentiels dans lefficacit des mthodes envisages concerne la taille des systmes rsoudre. Lataille de la mmoire des ordinateurs a augment de faon drastique de 1980 nos jours.Le dveloppement des mthodes de rsolution de systmes linaires est lie lvolution des machines infor-matiques. Cest un domaine de recherche trs actif que de concevoir des mthodes qui permettent de profiter aumieux de larchitecture des machines (mthodes de dcomposition en sous domaines pour profiter des architecturesparallles, par exemple).Dans la suite de ce chapitre, nous verrons deux types de mthodes pour rsoudre les systmes linaires : lesmthodes directes et les mthodes itratives. Pour faciliter la comprhension de leur tude, nous commenons parquelques rappels dalgbre linaire.

1.2 Pourquoi et comment ?

Nous donnons dans ce paragraphe un exemple de problme dont la rsolution numrique recquiert la rsolutiondun systme linaire, et qui nous permet dintroduire des matrices que nous allons beaucoup tudier par la suite.Nous commenons par donner ci-aprs aprs quelques rappels succincts dalgbre linaire, outil fondamental pourla rsolution de ces systmes linaires.

1.2.1 Quelques rappels dalgbre linaire

Quelques notions de base

Ce paragraphe rappelle des notions fondamentales que vous devriez connatre lissue du cours dalgbre linairede premire anne. On va commencer par revisiter le produit matriciel, dont la vision combinaison linaire delignes est fondamentale pour bien comprendre la forme matricielle de la procdure dlimination de Gauss.

5

1.2. POURQUOI ET COMMENT? CHAPITRE 1. SYSTMES LINAIRES

Soient A et B deux matrices carres dordre n, etM = AB. Prenons comme exemple dillustration

A =

[1 20 1

], B =

[1 03 2

]etM =

[5 43 2

]On note ai,j bi,j etmi,j , i, j = 1, . . . n les coefficients respectifs de A, B etM . Vous savez bien sr que

mi,j =

nk=1

ai,kbk,j . (1.2)

Si on crit les matrices A et B sous forme de lignes (notes i) et colonnes (notes cj) :

A =

1(A). . .n(A)

et B = [c1(B) . . . n(B)]Dans nos exemples, on a donc

1(A) =[1 2

], 2(A) =

[0 1

], c1(B) =

[13

]c2(B) =

[02

].

Lexpression (1.2) scrit encoremi,j = i(A)cj(B),

qui est le produit dune matrice 1 n par une matrice n 1, quon peut aussi crire sous forme dun produitscalaire :

mi,j = (i(A))t cj(B)

o (i(A))t dsigne la matrice transpose, qui est donc maintenant une matrice n 1 quon peut identifier unvecteur de IRn. Cest la technique habituelle de calcul du produit de deux matrices. On a dans notre exemple :

m1,2 = 1(A) c2(B) =[1 2

] [02

].

= (i(A))t cj(B) =

[12

][02

]= 4.

Mais de lexpression (1.2), on peut aussi avoir lexpression des lignes et des colonnes de M = AB en fonctiondes lignes de B ou des colonnes de A :

i(AB) =n

k=1

ai,kk(B) (1.3)

cj(AB) =

nk=1

bk,jck(A) (1.4)

Dans notre exemple, on a donc :

1(AB) =[1 0]+ 2 [3 2] = [5 4]

ce qui montre que la ligne 1 de AB est combinaison linaire des lignes de B. Le colonnes de AB, par contre, sontdes combinaisons linaires de colonnes de A. Par exemple :

c2(AB) = 0

[10

]+ 2

[21

]=

[42

]Il faut donc retenir que dans un produit matriciel AB,



les colonnes de AB sont des combinaisons linaires des colonnes de Ales lignes de AB sont des combinaisons linaires des lignes de B.

Cette remarque est trs importante pour la reprsentation matricielle de llimination de Gauss : lorquon calculedes systmes quivalents, on effectue des combinaisons linaires de lignes, et donc on multiplie gauche par unematrice dlimination.

Le tableau ci-dessous est la traduction littrale de Linear algebra in a nutshell, par Gilbert Strang 1 Pour unematrice carre A, on donne les caractrisations du fait quelle est inversible ou non.

A inversible A non inversible

Les vecteurs colonne sont indpendants Les vecteurs colonne sont lisLes vecteurs ligne sont indpendants Les vecteurs ligne sont lis

Le dterminant est non nul Le dterminant est nulAx = 0 a une unique solution x = 0 Ax = 0 a une infinit de solutions.

Le noyau de A est rduit {0} Le noyau de A contient au moins un vecteur non nul.Ax = b a une solution unique x = A1b Ax = b a soit aucune solution, soit une infinit.

A a n (nonzero) pivots A a r < n pivotsA est de rang maximal : rg(A) = n. rg(A) = r < n

La forme totatement chelonne R de A est la matrice identit R a au moins une ligne de zros.Limage de A est tout IRn. Limage de A est strictement incluse dans IRn.

Lespace L(A) engendr par les lignes de A est tout IRn. L(A) est de dimension r < nToutes les valeurs propres de A sont non nulles Zero est valeur propre de A.

AtA is symtrique dfinie positive 2 AtA nest que semi- dfinie .

TABLE 1.1: Extrait de Linear algebra in a nutshell, G. Strang

On rappelle pour une bonne lecture de ce tableau les quelques dfinitions suivantes :

Dfinition 1.1 (Pivot). Soit A Mn(IR) une matrice carre dordre n. On appelle pivot de A le premier lmentnon nul de chaque ligne dans la forme chelonne de A obtenue par limination de Gauss. Si la matrice estinversible, elle a donc n pivots (non nuls).

Dfinition 1.2 (Valeurs propres). Soit A Mn(IR) une matrice carre dordre n. On appelle valeur propre de Atout Cl tel quil existe x Cl n, x 6= 0 tel que Ax = x. Llment x est appel vecteur propre de A associ .

Dfinition 1.3 (Dterminant). Il existe une unique application, note det de Mn(IR) dans IR qui vrifie lesproprits suivantes

(D1) Le dterminant de la matrice identit est gal 1.

(D2) Si la matrice A est obtenue partir de A par change de deux lignes, alors detA = detA.

1. Voir la page web de Strang www.mit.edu/~gs pour une foule dinformations et de cours sur lalgbre linaire.



(D3) Le dterminant est une fonction linaire de chacune des lignes de la matrice A.

(D3a) (multiplication par un scalaire) si A est obtenue partir de A en multipliant tous les coefficients duneligne par IR, alors det(A) = det(A).

(D3b) (addition) si A =

1(A)...

k(A)...

n(A)

, A =

1(A)...

k(A)...

n(A)

et B =

1(A)...

k(A) + k(A)...

n(A)

, alors

det(B) = det(A) + det(A).

On peut dduire de ces trois proprits fondamentales un grand nombre de proprits importantes, en particulierle fait que det(AB) = detA detB et que le dterminant dune matrice inversible est le produit des pivots : cestde cette manire quon le calcule sur les ordinateurs. En particulier on nutilise jamais la formule de Cramer,beaucoup trop coteuse en termes de nombre doprations.

On rappelle que si A Mn(IR) une matrice carre dordre n, les valeurs propres sont les racines du polynmecaractristique PA de degr n, qui scrit :

PA()) = det(A I).

Matrices diagonalisables

Un point important de lalgbre linaire, appel rduction des endomorphismes dans les programmes franais,consiste se demander sil existe une base de lespace dans laquelle la matrice de lapplication linaire est diago-nale ou tout au moins triangulaire (on dit aussi trigonale).

Dfinition 1.4 (Matrice diagonalisable dans IR). Soit A une matrice relle carre dordre n. On dit que A estdiagonalisable dans IR sil existe une base (u1, . . . ,un) de IR

n et des rels 1, . . . , n (pas forcment distincts)tels que Aui = iui pour i = 1, . . . , n. Les rels 1, . . . , n sont les valeurs propres de A, et les vecteursu1, . . . ,un sont les vecteurs propres associs.

Vous connaissez srement aussi la diagonalisation dans Cl : une matrice relle carre dordre n admet toujours nvaleurs propres dansCl , qui ne sont pas forcment identiques. Une matrice est diagonalisable dansCl sil existe unebase (u1, . . . ,un) de Cl

n et des nombres complexes 1, . . . , n (pas forcment distincts) tels que Aui = iuipour i = 1, . . . , n. Ceci est vrifi si la dimension de chaque sous espace propre Ei = Ker(A Id) (appelemultiplicit gomtrique) est gale a la multiplicit algbrique de i, c..d. son ordre de multiplicit en tant queracine du polynme caractristique.

Par exemple la matrice A =

(0 01 0

)nest pas diagonalisable dans Cl (ni videmment, dans IR). Le polynme

caractristique de A est PA() = 2, lunique valeur propre est donc 0, qui est de multiplicit algbrique 2, et demultiplicit gomtrique 1, car le sous espace propre associ la valeur propre nulle est F = {x IR2 ;Ax =0} = {x = (0, t), t IR}, qui est de dimension 1.Ici et dans toute la suite, comme on rsout des systmes linaires rels, on prfre travailler avec la diagonalisationdans IR ; cependant il y a des cas o la diagonalisation dans Cl est utile et mme ncessaire (tude de stabilit des



systmes difrentiels, par exemple). Par souci de clart, nous prciserons toujours si la diagonalisation considreest dans IR ou dans Cl .

Lemme 1.5. Soit A une matrice relle carre dordre n, diagonalisable dans IR. Alors

A = Pdiag(1, . . . , n)P1,

o P est la matrice dont les vecteurs colonnes sont gaux aux vecteurs propres u1, . . . ,un associes au valeurspropres 1, . . . , n

DMONSTRATION Par dfinition dun vecteur propre, on a Aui = iui pour i = 1, . . . N , et donc, en notant P lamatrice dont les colonnes sont les vecteurs propres ui,[

Au1 . . . Aun]= A

[u1 . . . un

]= AP

et donc

AP =[1u1 . . . nun

]=[u1 . . . un

]1 0 . . . 0

0 2. . .

......

. . .. . .

...0 . . . 0 n

= Pdiag(1, . . . , n).Notons que dans ce calcul, on a fortement utilis la multiplication des matrices par colonnes, c..d.

ci(AB) =j=1,n

ai,jcj(B).

Remarquons que P lest aussi la matrice dfinie (de manire unique) par Pei = ui, o (ei)i=1,...,n est la base canoniquede IRn, cest--dire que (ei)j = i,j . La matrice P est appele matrice de passage de la base (ei)i=1,...,n la base(ui)i=1,...,n ; (il est bien clair que la i-me colonne de P est constitue des composantes de ui dans la base canonique(e1, . . . ,en).La matrice P est inversible car les vecteurs propres forment une base, et on peut donc aussi crire :

P1AP = diag(1, . . . , n) ou A = Pdiag(1, . . . , n)P

1.

La diagonalisation des matrices relles symtriques est un outil quon utilisera souvent dans la suite, en particulierdans les exercices. Il sagit dun rsultat extrmement important.

Lemme 1.6 (Une matrice symtrique est diagonalisable dans IR). Soit E un espace vectoriel sur IR de dimensionfinie : dimE = n, n IN, muni dun produit scalaire i.e. dune application

E E IR,(x, y) (x | y)E ,

qui vrifie :x E, (x | x)E 0 et (x | x)E = 0 x = 0,(x, y) E2, (x | y)E = (y | x)E ,y E, lapplication de E dans IR, dfinie par x (x | y)E est linaire.

Ce produit scalaire induit une norme sur E, x =(x | x)E .Soit T une application linaire de E dans E. On suppose que T est symtrique, c..d. que (T (x) | y)E = (x |T (y))E , (x, y) E2 . Alors il existe une base orthonorme (f1, . . . ,fn) deE (c..d. telle que (f i,f j)E = i,j)et (1 . . . n) IRn tels que T (fi) = if i pour tout i {1 . . . n}.



Consquence immdiate : Dans le cas o E = IRn, le produit scalaire canonique de x = (x1, . . . , xn)t ety = (y1, . . . , yn)

t est dfini par (x | y)E = x y =n

i=1 xiyi. Si A Mn(IR) est une matrice symtrique, alorslapplication T dfinie de E dans E par : T (x) = Ax est linaire, et : (Tx|y) = Ax y = x Aty = x Ay = (x |Ty). Donc T est linaire symtrique. Par le lemme prcdent, il existe (f1, . . . ,fn) et (1 . . . n) IR tels queTf i = Af i = if i i {1, . . . , n} et fi f j = i,j , (i, j) {1, . . . , n}2.

Interprtation algbrique : Il existe une matrice de passage P de (e1, . . . , en) base canonique dans (f1, . . . ,fn)dont la premire colonne de P est constitue des coordonnes de fi dans (e1 . . . en). On a : Pei = fi. On a alorsP1APei = P1Af i = P

1(ifi) = iei = diag(1, . . . , n)ei, o diag(1, . . . , n) dsigne la matricediagonale de coefficients diagonaux 1, . . . , n. On a donc :

P1AP =

i 0. . .0 n

= D.De plus P est orthogonale, i.e. P1 = P t. En effet,

P tPei ej = Pei Pej = (fi|fj) = i,j i, j {1 . . . n},et donc (P tPei ei) ej = 0 j {1 . . . n} i {1, . . . n}. On en dduit P tPei = ei pour tout i = 1, . . . n,i.e. P tP = PP t = Id.

DMONSTRATION du lemme 1.6 Cette dmonstration se fait par rcurrence sur la dimension de E.

1re tape.

On suppose dimE = 1. Soit e E, e 6= 0, alors E = IRe = f1 avec f1 =e

e . Soit T : E E linaire symtrique,on a : Tf1 IRf1 donc il existe 1 IR tel que Tf1 = 1f1.

2me tape.

On suppose le lemme vrai si dimE < n. On montre alors le lemme si dimE = n. Soit E un espace vectoriel norm surIR tel que dimE = n et T : E E linaire symtrique. Soit lapplication dfinie par :

: E IRx (Tx|x).

Lapplication est continue sur la sphre unit S1 = {x E| x = 1} qui est compacte car dimE < + ; il existedonc e S1 tel que (x) (e) = (Te | e) = pour tout x E. Soit y E \{0}, et soit t ]0, 1y [ alors e+ ty 6= 0.On en dduit que :

e+ ty

e+ ty S1 et donc (e) = (T(e+ ty)

e+ ty|e+ ty

e + ty)E

donc (e+ ty | e+ ty)E (T (e+ ty) | e+ ty). En dveloppant on obtient :[2t(e | y) + t2(y | y)E] 2t(T (e) | y) + t2(T (y) | y)E.

Comme t > 0, ceci donne :[2(e | y) + t(y | y)E] 2(T (e) | y) + t(T (y) | y)E .

En faisant tendre t vers 0+, on obtient 2(e | y)E 2(T (e) | y), Soit 0 (T (e) e | y) pour tout y E \ {0}. Demme pour z = y on a 0 (T (e) e|z) donc (T (e) e | y) 0. Do (T (e) e | y) = 0 pour tout y E. Onen dduit que T (e) = e. On pose fn = e et n = .

Soit F = {x E; (x | e) = 0}, on a donc F 6= E, et E = F IRe : on peut dcomposer x E comme (x =x (x | e)e+ (x | e)e). Lapplication S = T |F est linaire symtrique et on a dimF = n 1. et S(F ) F . On peutdonc utiliser lhypothse de rcurrence : (1 . . . n1) IRn et (f1 . . .fn1) En tels que i {1 . . . n 1},Sf i = Tf i = if i, et i, j {1 . . . n 1}, f i f j = i,j . Et donc (1 . . . n) et (f1, . . . ,fn) conviennent.



x

x

x

x

x

x0 = 0 x1 xi = ih

u(x)

ui

xN+1 = 1

x

x

x

x x

FIGURE 1.1: Solution exacte et approche de u = f

1.2.2 Discrtisation de lquation de la chaleur

Dans ce paragraphe, nous prenons un exemple trs simple pour obtenir un systme linaire partir de la discrti-sation dun problme continu.

Lquation de la chaleur unidimensionnelle

Discrtisation par diffrences finies de u = f Soit f C([0, 1], IR). On cherche u tel que

u(x) = f(x) (1.5a)u(0) = u(1) = 0. (1.5b)

Remarque 1.7 (Problmes aux limites, problmes conditions initiales). Lquation diffrentielleu = f admetune infinit de solutions. Pour avoir existence et unicit, il est ncessaire davoir des conditions supplmentaires.Si lon considre deux conditions en 0 (ou en 1, lorigine importe peu) on a ce quon appelle un problme deCauchy, ou problme conditions initiales. Le problme (1.5) est lui un problme aux limites : il y a une conditionpour chaque bord du domaine. En dimension suprieure, le problme u = f ncessite une condition sur aumoins un bout de frontire pour tre bien pos : voir le cours dquations aux drives partielles de master pourplus de dtails ce propos.

On peut montrer (on ladmettra ici) quil existe une unique solution u C2([0, 1], IR). On cherche calculeru de manire approche. On va pour cela introduire la mthode de discrtisation dite par diffrences finies. Soitn IN, on dfinit h = 1/(n + 1) le pas de discrtisation, c..d. la distance entre deux points de discrtisation,et pour i = 0, . . . , n + 1 on dfinit les points de discrtisation xi = ih (voir Figure 1.1), qui sont les points olon va crire lquation u = f en vue de se ramener un systme discret, c..d. un systme avec un nombrefini dinconnues u1, . . . , un. Remarquons que x0 = 0 et xn+1 = 1, et quen ces points, u est spcifie par lesconditions limites (1.5b). Soit u(xi) la valeur exacte de u en xi. On crit la premire quation de (1.5a) en chaquepoint xi, pour i = 1 . . . n.

u(xi) = f(xi) = bi i {1 . . . n}. (1.6)Supposons que u C4([0, 1], IR) (ce qui est vrai si f C2). Par dveloppement de Taylor, on a :

u(xi+1) = u(xi) + hu(xi) +

h2

2u(xi) +

h3

6u(xi) +

h4

24u(4)(i),

u(xi1) = u(xi) hu(xi) + h2

2u(xi) h

3

6u(xi) +

h4

24u(4)(i),



avec i (xi, xi+1) et i (xi, xi+1). En sommant ces deux galits, on en dduit que :

u(xi+1) + u(xi1) = 2u(xi) + h2u(xi) +h4

24u(4)(i) +

h4

24u(4)(i).

On dfinit lerreur de consistance, qui mesure la manire dont on a approchu(xi) ; lerreur de consistance Riau point xi est dfinie par

Ri = u(xi) u(xi+1) + u(xi1) 2u(xi)h2

. (1.7)

On a donc :

|Ri| =u(xi+1) + u(xi1) 2u(xi)h2 + u(xi)

h424u(4)(i) + h424u(4)(i)

h

2

12u(4). (1.8)

o u(4) = supx]0,1[ |u(4)(x)|. Cette majoration nous montre que lerreur de consistance tend vers 0 commeh2, et on en dit que le schma est consistant dordre 2.On introduit alors les inconnues (ui)i=1,...,n quon espre tre des valeurs approches de u aux points xi et quisont les composantes de la solution (si elle existe) du systme suivant{

ui+1 + ui1 2uih2

= bi, i; 1 i n,u0 = un+1 = 0.

(1.9)

On cherche donc u =

u1...un

IRn solution de (1.9). Ce systme peut scrire sous forme matricielle :Knu = bo b =

b1...bn

etKn est la matrice carre dordre n de coefficients (ki,j)i,j=1,n dfinis par :

ki,i =2

h2, i = 1, . . . , n,

ki,j = 1h2, i = 1, . . . , n, j = i 1,

ki,j = 0, i = 1, . . . , n, |i j| > 1.(1.10)

On remarque immdiatement queKn est tridiagonale.On peut montrer que Kn est symtrique dfinie positive (voir exercice 8 page 19), et elle est donc inversible LesystmeKnu = b admet donc une unique solution. Cest bien, mais encore faut il que cette solution soit ce quonesprait, c..d. que chaque valeur ui soit une approximation pas trop mauvaise de u(xi). On appelle erreur dediscrtisation en xi la diffrence de ces deux valeurs :

ei = u(xi) ui, i = 1, . . . , n. (1.11)

mSi on appelle e le vecteur de composantes ei, on dduit de la dfinition 1.11 de lerreur de consistance et desquations (exactes) 1.6 que

Kne = R et donc e = K1n R. (1.12)

Le fait que le schma soit consistant est une bonne chose, mais cela ne suffit pas montrer que le schma estconvergent, c..d. que lerreur entre maxi=1,...,n ei tend vers 0 lorsque h tend vers 0, parce que A dpend de



h ! Pour cela, il faut de plus que le schma soit stable, au sens o lon puisse montrer que K1n est bornindpendamment de h, ce qui revient trouver une estimation sur les valeurs approches ui indpendante de h. Lastabilit et la convergence font lobjet de lexercice 43, o lon montre que le schma est convergent, et quon alestimation derreur suivante :

maxi=1...n

{|ui u(xi)|} h2

96u(4).

Cette ingalit donne la prcision de la mthode (cest une mthode dite dordre 2). On remarque en particulierque si on raffine la discrtisation, cestdire si on augmente le nombre de points n ou, ce qui revient au mme,si on diminue le pas de discrtisation h, on augmente la prcision avec laquelle on calcule la solution approche.

Lquation de la chaleur bidimensionnelle

Prenonsmaintenant le cas dune discrtisation du Laplacien sur un carr par diffrences finies. Si u est une fonctionde deux variables x et y valeurs dans IR, et si u admet des drives partielles dordre 2 en x et y, loprateurlaplacien est dfini par u = xxu + yyu. Lquation de la chaleur bidimensionnelle scrit avec cet oprateur.On cherche rsoudre le problme :

u = f sur =]0, 1[]0, 1[,u = 0 sur ,

(1.13)

On rappelle que loprateur Laplacien est dfini pour u C2(), o est un ouvert de IR2, par

u =2u

x2+2u

y2.

Dfinissons une discrtisation uniforme du carr par les points (xi, yj), pour i = 1, . . . ,M et j = 1, . . . ,Mavec xi = ih, yj = jh et h = 1/(M + 1), represente en figure 1.2 pour M = 6. On peut alors approcher lesdrives secondes par des quotients diffrentiels comme dans le cas unidimensionnel (voir page 11), pour obtenirun systme linaire : Au = b o A Mn(IR) et b IRn avec n = M2. Utilisons lordrelexicographique"pour numroter les inconnues, c..d. de bas en haut et de gauche droite : les inconnues sont alors numrotes de1 n = M2 et le second membre scrit b = (b1, . . . , bn)t. Les composantes b1, . . . , bn sont dfinies par :pouri, j = 1, . . . ,M , on pose k = j + (i 1)M et bk = f(xi, yj).Les coefficients de A = (ak,)k,l=1,n peuvent tre calculs de la manire suivante :

Pour i, j = 1, . . . ,M, on pose k = j + (i 1)M,ak,k =

4

h2,

ak,k+1 =

{ 1h2

si j 6= M,0 sinon,

ak,k1 =

{ 1h2

si j 6= 1,0 sinon,

ak,k+M =

{ 1h2

si i < M,

0 sinon,

ak,kM =

{ 1h2

si i > 1,

0 sinon,

Pour k = 1, . . . , n, et = 1, . . . , n;ak, = 0, k = 1, . . . , n, 1 < |k | < n ou |k | > n.



2 3 4 5 6

7 8 9

31

10 11 12

13 14 15 16 17 18

19 20 21 22 23 24

302928272625

32 33 34 35 36

1i = 1

j = 1

x

y

FIGURE 1.2: Ordre lexicographique des inconnues, exemple dans le casM = 6

La matrice est donc tridiagonale par blocs, plus prcisment si on note

D =

4 1 0 . . . . . . 01 4 1 0 . . . 00

. . .. . .

. . .. . .

......

0. . .

. . .. . . 1

0 . . . 0 1 4

,

les blocs diagonaux (qui sont des matrices de dimensionM M ), on a :

A =

D Id 0 . . . . . . 0Id D Id 0 . . . 00 Id D Id 0...

. . .. . .

. . .. . .

...

0. . . Id D Id

0 . . . 0 Id D

, (1.14)

o Id dsigne la matrice identit dordreM .

Matrices monotones, ou inverse positive Une proprit qui revient souvent dans ltude des matrices issuesde la discrtisation dquations diffrentielles est le fait que si leur action sur un vecteur u donne un vecteur positifv (composante par composante) alors le vecteur u de dpart doit tre positif (composante par composante) ; on ditsouvent que la matrice est monotone, ce qui nest pas un terme trs evocateuri. . . Dans ce cours, on lui prfererale terme inverse positive ; en effet, on montre la proposition quune matrice A est monotone si et seulementsi elle inversible et inverse positive.



Dfinition 1.8 (IP-matrice ou matrice monotone). Si x IRn, on dit que x 0 [resp. x > 0] si toutes lescomposantes de x sont positives [resp. strictement positives].Soit A Mn(IR), on dit que A est une matrice monotone si elle vrifie la proprit suivante :

Si x IRn est tel que Ax 0, alors x 0,

ce qui peut encore scrire : {x IRn t.q. Ax 0} {x IRn t.q. x 0}.

Proposition 1.9 (Caractrisation des matrices monotones). Une matrice A est monotone si et seulement si elleinversible et inverse positive (c..d. dont tous les coefficients sont positifs).

La dmonstration de ce rsultat est lobjet de lexercice 6. Retenez que toute matrice monotone est inversible etdinverse positive que cette proprit de monotonie est utilise pour tablir une borne de A1 pour la matricede discrtisation du Laplacien, dont on a besoin pour montrer la convergence du schma. Cest donc une propritqui est importante au niveau de lanalyse numrique.

1.2.3 Exercices

Exercice 1 (Vrai ou faux ? Motiver les rponses. . . ).

On suppose dans toutes les questions suivantes que n 2.1. Soit Z IRn un vecteur non nul. La matrice ZZt est inversible.2. La matrice inverse dune matrice triangulaire infrieure est triangulaire suprieure.

3. Les valeurs propres sont les racines du polynme caractristique.

4. Toute matrice inversible est diagonalisable dans IR.

5. Toute matrice inversible est diagonalisable dans Cl .

6. Le dterminant dune matrice A est gal au produit de ses valeurs propres.

7. Soit A une matrice carre telle que Ax = 0 = x = 0, alors A est inversible.8. Soit A une matrice carre telle que Ax 0 = x 0, alors A est inversible.9. Une matrice symtrique est inversible.

10. Une matrice symtrique dfinie positive est inversible.

Exercice 2 (Sur quelques notions connues).

1. Soit A une matrice carre dordre n et b IR3. Peut il exister exactement deux solutions distinctes ausystme Ax = b ?

2. Soient A, B et C de dimensions telles que AB et BC existent. Montrer que si AB = Id et BC = Id,alors A = C.

3. Combien y a -til de matrices carres dordre 2 ne comportant que des 1 ou des 0 comme coefficients ?Combien dentre elles sont inversibles ?

4. Soit B =

[3 25 3

].Montrer que B1024 = Id.

Exercice 3 (La matriceK3). Soit f C([0, 1], IR). On cherche u tel que u(x) = f(x), x (0, 1), (1.15a)u(0) = u(1) = 0. (1.15b)



1. Calculer la solution exacte u(x) du problme lorsque f est la fonction identiquement gale 1 (on admettraque cette solution est unique), et vrifier que u(x) 0 pour tout x [0, 1].

On discrtise le problme suivant par diffrences finies, avec un pas h = 14 avec la technique vue en cours.

2. A laide de dvloppements de Taylor, crire lapproximation de u(xi) au deuxime ordre en fonction deu(xi), u(xi1) et u(xi+1). En dduire le schma aux diffrences finies pour lapproximation de (1.15),quon crira sous la forme :

K3u = b, (1.16)

oK3 est la matrice de discrtisation quon explicitera, u =

u1u2u3

et b =b1b2b3

=f(x1)f(x2)f(x3)

.3. Rsoudre le systme linaire (1.16) par la mthode de Gauss. Comparer ui et u(xi) pour i = 1, 2, 3, et

expliquer pourquoi lerreur de discrtisation u(xi) ui est nulle.4. Reprendre les questions prcdentes en remplaant les conditions limites (1.15b) par :

u(0) = 0, u(1) = 0. (1.17)

5. Soit c IR. On considre maintenant le problme suivant : u(x) = c, x (0, 1), (1.18a)u(0) = u(1) = 0, (1.18b)

(a) Montrer que le problme (1.18) admet soit une infinit de solution, soit pas de solution.

(b) Ecrire la discrtisation du problme (1.18), toujours avec h = 14 , sous la forme K3u = b en explicitant

K3 et b.

(c) Montrer que la matrice K3 nest pas inversible : on part dun problme continu mal pos, et on obtientpar discrtisation un problme discret mal pos. . .

Exercice 4 (Matrices symtriques dfinies positives). Suggestions en page 19, corrig en page 19. On rappelle quetoute matrice A Mn(IR) symtrique est diagonalisable dans IR (cf. lemme 1.6 page 9). Plus prcisment, on amontr en cours que, si A Mn(IR) est une matrice symtrique, il existe une base de IRn, note {f1, . . . ,fn},et il existe 1, . . . , n IR t.q.Af i = if i, pour tout i {1, . . . , n}, et f i f j = i,j pour tout i, j {1, . . . , n}(x y dsigne le produit scalaire de x avec y dans IRn).

1. Soit A Mn(IR). On suppose que A est symtrique dfinie positive, montrer que les lments diagonauxde A sont strictements positifs.

2. Soit A Mn(IR) une matrice symtrique. Montrer queA est symtrique dfinie positive si et seulement sitoutes les valeurs propres de A sont strictement positives.

3. Soit A Mn(IR). On suppose que A est symtrique dfinie positive. Montrer quon peut dfinir uneunique matrice B Mn(IR), symtrique dfinie positive t.q. B2 = A (on note B = A 12 ).

Exercice 5 (Diagonalisation dans IR ).

Soit E un espace vectoriel rel de dimension n IN muni dun produit scalaire, not (, ). Soient T et S deuxapplications linaires symtriques deE dans E (T symtrique signifie (Tx, y) = (x, T y) pour tous x, y E). Onsuppose que T est dfinie positive (cest--dire (Tx, x) > 0 pour tout x E \ {0}).

1. Montrer que T est inversible. Pour x, y E, on pose (x, y)T = (Tx, y). Montrer que lapplication(x, y) 7 (x, y)T dfinit un nouveau produit scalaire sur E.

2. Montrer que T1S est symtrique pour le produit scalaire dfini la question prcdente. En dduire, avecle lemme 1.6 page 9, quil existe une base de E, note {f1, . . . ,fn} et une famille {1, . . . , n} IRtelles que T1Sf i = if i pour tout i {1, . . . , n} et t.q. (Tf i,f j) = i,j pour tout i, j {1, . . . , n}.



Exercice 6 (IP-matrice). Corrig en page 21

Soit n IN, on noteMn(IR) lensemble des matrices de n lignes et n colonnes et coefficients rels. Si x IRn,on dit que x 0 [resp. x > 0] si toutes les composantes de x sont positives [resp. strictement positives].Soit A Mn(IR), on dit que A est une IP-matrice si elle vrifie la proprit suivante :

Si x IRn est tel que Ax 0, alors x 0,

ce qui peut encore scrire : {x IRn t.q. Ax 0} {x IRn t.q. x 0}.1. Soit A = (ai,j)i,j=1,...,n Mn(IR). Montrer que A est une IP-matrice si et seulement si A est inversible etA1 0 (cest--dire que tous les coefficients de A1 sont positifs).

2. Soit A =

(a bc d

)une matrice relle dordre 2. Montrer que A est une IP-matrice si et seulement si :

ad < bc,a < 0, d < 0b 0, c 0

ou

ad > bc,a > 0, d > 0,b 0, c 0.

(1.19)

3. Montrer que si A Mn(IR) est une IP-matrice alors At (la transpose de A) est une IP-matrice.4. Montrer que si A est telle que

ai,j 0, pour tout i, j = 1, . . . , n, i 6= j,ai,i >

nj=1j 6=i

|ai,j |, pour tout i = 1, . . . , n, (1.20)

alors A est une IP-matrice.

5. En dduire que si A est telle que

ai,j 0, pour tout i, j = 1, . . . , n, i 6= j,ai,i >

nj=1j 6=k

|aj,i|, pour tout i = 1, . . . , n, (1.21)

alors A est une IP-matrice.

6. Montrer que si A Mn(IR) est une IP-matrice et si x IRn alors :

Ax > 0 x > 0.

cest--dire que {x IRn t.q. Ax > 0} {x IRn t.q. x > 0}7. Montrer, en donnant un exemple, quunematriceA deMn(IR) peut vrifier {x IRn t.q.Ax > 0} {x IRnt.q. x > 0} et ne pas tre une IP-matrice.8. On suppose dans cette question que A Mn(IR) est inversible et que {x IRn t.q. Ax > 0} {x IRn t.q.x > 0}. Montrer que A est une IP-matrice.9. (Question plus difficile) Soit E lespace des fonctions continues sur IR et admettant la mme limite finie en+ et . Soit L(E) lensemble des applications linaires continues de E dans E. Pour f E, on dit quef > 0 (resp. f 0) si f(x) > 0 (resp. f(x) 0) pour tout x IR. Montrer quil existe T L(E) tel queTf 0 = f 0, et g E tel que Tg > 0 et g 6> 0 (ceci dmontre que le raisonnement utilis en 2 (b) nemarche pas en dimension infinie).

Exercice 7 (M-matrice).



Dans ce qui suit, toutes les ingalits crites sur des vecteurs ou des matrices sont entendre au sens composantepar composante.Soit A = (ai,j)i,j=1,...,n une matrice carre dordre n. On dit que A est uneM -matrice si A est une IP-matrice (Aest inversible et A1 0, voir exercice 6) qui vrifie de plus

(a) ai,i > 0 pour i = 1, . . . , n ;

(b) ai,j 0 pour i, j = 1, . . . , n, i 6= j ;1. Soit A une IP-matrice ; montrer que A est uneM -matrice si et seulement si la proprit (b) est vrifie.

2. Soit A =

(a bc d

)une matrice relle dordre 2. Montrer que A est une M-matrice si et seulement si :

ad > bc,a > 0, d > 0,b 0, c 0.

(1.22)

3. Les matrices A =

( 1 22 1

)et B =

(2 1

1 2)sont-elles des IP-matrices ? des M-matrices ?

4. Soit A la matrice carre dordre 3 dfinie par :

A =

2 1 120 1 11 0 1

Montrer que A1 0 mais que A nest pas uneMmatrice.5. Soit A une matrice carre dordre n = m+ p, avecm, p IN tels quem 1 et p 1, vrifiant :

ai,i 0,ai,j 0, pour j = 1, . . . , n, j 6= i,ai,i +

nj=1j 6=i

ai,j = 0

pour i = 1, . . . ,m, (1.23)

ai,i = 1,ai,j = 0, pour j = 1, . . . , n, j 6= i,

}pour i = m+ 1, . . . , n. (1.24)

i m, (k)=1,...,Li ; k1 = i, kLi > m, et ak,k+1 < 0, = 1, . . . , Li. (1.25)Soit b IRn tel que bi = 0 pour i = 1, . . . ,m. On considre le systme linaire

Au = b (1.26)

5.1 Montrer que le systme (1.26) admet une et une seule solution.

5.2 Montrer que u est tel que mink=m+1,n bk ui maxk=m+1,n bk. (On pourra pour simplifier supposer queles quations sont numrotes de telle sorte quemink=m+1,n bk = bm+2 b2 . . . bn = maxk=m+1,n bk.)6. On considre le problme de Dirichlet suivant :

u = 0 sur [0, 1] (1.27a)u(0) = 1 (1.27b)u(1) = 1. (1.27c)

6.1 Calculer la solution exacte u de ce problme et vrifier quelle reste comprise entre -1 et 1.

6.2 Soitm > 1 et soientA et b et la matrice et le second membre du systme linaire dordre n = m+2 obtenu pardiscrtisation par diffrences finies avec un pas uniforme h = 1m du problme (1.27) (en crivant les conditionsaux limites dans le systme). Montrer que la solution u = (u1, . . . , un)t IRn du systme Au = b vrifie1 ui 1.



Exercice 8 (Matrice du Laplacien discret 1D). Corrig dtaill en page 20.Soit f C([0, 1]). Soit n IN, n impair. On pose h = 1/(n+ 1). SoitKn la matrice dfinie par (1.10) page 12,issue dune discrtisation par diffrences finies avec pas constant du problme (1.5a) page 11.Montrer queKn est symtrique dfinie positive.

Exercice 9 (Pas non constant). Reprendre la discrtisation vue en cours avec un pas hi = xi+1xi non constant,et montrer que dans ce cas,le schma est consistant dordre 1 seulement.

Exercice 10 (Raction diffusion 1d.). Corrig dtaill en page 20. On sintresse la discrtisation par Diffren-ces Finies du problme aux limites suivant :

u(x) + u(x) = f(x), x ]0, 1[,u(0) = u(1) = 0.

(1.28)

Soit n IN. On note U = (uj)j=1,...,n une valeur approche de la solution u du problme (1.28) aux points(j

n+1

)j=1,...,n

. Donner la discrtisation par diffrences finies de ce problme sous la forme AU = b.

Exercice 11 (Discrtisation).

On considre la discrtisation pas constant par le schma aux diffrences finies symtrique trois points duproblme (1.5a) page 11, avec f C([0, 1]). Soit n IN, n impair. On pose h = 1/(n + 1). On note u estla solution exacte, xi = ih, pour i = 1, . . . , n les points de discrtisation, et (ui)i=1,...,n la solution du systmediscrtis (1.9).

1. Montrer que si u C4([0, 1], alors la proprit (1.7) est vrifie, c..d. :

u(xi+1) + u(xi1) 2u(xi)h2

= u(xi) +Ri avec |Ri| h2

12u(4).

2. Montrer que si f est constante, alors

max1in

|ui u(xi)| = 0.

.

3. Soit n fix, et max1in

|uiu(xi)| = 0. A-t-on forcment que f est constante sur [0, 1] ? (justifier la rponse.)

1.2.4 Suggestions pour les exercices

Exercice 4 page 16 (Matrices symtriques dfinies positives)

3. Utiliser la diagonalisation sur les oprateurs linaires associs.

1.2.5 Corrigs des exercices

Exercice 4 page 16 (Matrices symtriques dfinies positives)

1. Supposons quil existe un lment diagonal ai,i ngatif. Alors Aei ei 0 ce qui contredit le fait que A estdfinie positive.

2. Soit x IRn, dcomposons x sur la base orthonorme (f i)i=1,n : x =n

i=1 xif i. On a donc :

Ax x =ni=1

ix2i . (1.29)

Montrons dabord que si les valeurs propres sont strictement positives alors A est dfinie positive :



Supposons que i 0, i = 1, . . . , n. Alors pour x IRn, daprs (1.29), Ax x 0 et la matrice Aest positive. Supposons maintenant que i > 0, i = 1, . . . , n. Alors pour x IRn, toujours daprs (1.29),(Ax x = 0) (x = 0), et la matrice A est donc bien dfinie.

Montrons maintenant la rciproque : si A est dfinie positive, alors Af i f i > 0, i = 1, . . . , n et donc i > 0,i = 1, . . . , n.

3. Comme A est s.d.p., toutes ses valeurs propres sont strictement positives, et on peut donc dfinir lapplicationlinaire S dans la base orthonorme (fi)i=1,n par : S(f i) =

if i, i = 1, . . . , n. On a videmment S S = T ,

et donc si on dsigne parB la matrice reprsentative de lapplication S dans la base canonique, on a bienB2 = A.

Exercice 8 page 19 (Matrice du laplacien discret 1D.)

Il est clair que la matrice A est symtrique.Pour montrer que A est dfinie positive (carA est videmment symtrique), on peut procder de plusieurs faons :

1. Par chelonnement :

2. Par les valeurs propres :Les valeurs propres sont calcules lexercice 41 ; elles sont de la forme :

k =2

h2(1 cos kh) = 2

h2(1 cos k

n+ 1), k = 1, . . . , n,

et elles sont donc toutes strictement positives ; de ce fait, la matrice est symtrique dfinie positive (voirexercice 4).

3. Par la forme quadratique associe : on montre que Ax x > 0 si x 6= 0 et Ax x = 0 ssi x = 0. En effet,on a

Ax x = 1h2

[x1(2x1 x2) +

n1i=2

xi(xi1 + 2xi xi+1) + 2x2n xn1xn]

On a donc

h2Ax x = 2x21 x1x2 n1i=2

(xixi1 + 2x2i

) ni=3

xixi1 + 2x2n xn1xn

=

ni=1

x2i +

ni=2

x21i + x2n 2

ni=1

xixi1

=

ni=2

(xi xi1)2 + x21 + x2n 0.

De plus, Ax x = 0 x21 = xn = 0 et xi = xi1 pour i = 2 n, donc x = 0.

Exercice 10 page 19 (Raction diffusion 1D.)

La discrtisation du probllme consiste chercher U comme solution du systme linaire

AU =

(f(

j

N + 1)

)j=1,...,n

o la matrice A Mn(IR) est dfinie par A = (N + 1)2Kn + Id, Id dsigne la matrice identit et

Kn =

2 1 0 . . . 01 2 1 . . . ...0

. . .. . .

. . . 0...

. . . 1 2 10 . . . 0 1 2



Exercice 6 page 17 (IP-matrice)

1. Supposons dabord que A est inversible et que A1 0 ; soit x IRn tel que b = Ax 0. On a doncx = A1b, et comme tous les coefficients de A1 et de b sont positifs ou nuls, on a bien x 0.Rciproquement, si A est une IP-matrice, alors Ax = 0 entraine x = 0 ce qui montre que A est inversible.Soit ei le i-me vecteur de la base canonique de IR

n, on a : AA1ei = ei 0, et donc par la proprit deIP-matrice, A1ei 0, ce qui montre que tous les coefficients de A1 sont positifs.

2. La matrice inverse deA est A1 = 1

(d bc a

)avec = ad bc. Les coefficients deA1 sont donc

positifs ou nuls si et seulement siad < bc,a 0, d 0b 0, c 0

ou

ad > bc,a 0, d 0,b 0, c 0.

Or on a forcment ad 6= 0 : en effet sinon on aurait dans le premier cas) bc < 0, or b 0 et c 0, cequi aboutit une contradiction. De mme dans le deuxime cas, on aurait bc > 0, or b 0 et c 0. Lesconditions prcdentes sont donc quivalentes aux conditions (1.19).

3. La matrice At est une IP-matrice si et seulement At est inversible et (At)1 0. Or (At)1 = (A1)t.Do lquivalence.

4. Supposons queA vrifie (1.20), et soit x IRn tel queAx 0. Soit k 1, . . . , n tel que xk = min{xi, i =1, . . . , n}. Alors

(Ax)k = ak,kxk +

nj=1j 6=k

ak,jxj 0.

Par hypothse, ak,j 0 pour k 6= j, et donc ak,j = |ak,j |. On peut donc crire :

ak,kxk nj=1j 6=k

|ak,j |xj 0,

et donc :

(ak,k nj=1j 6=k

|ak,j |)xk nj=1j 6=k

|ak,j |(xj xk).

Comme xk = min{xi, i = 1, . . . , n}, on en dduit que le second membre de cette ingalit est positif ounul, et donc que xk 0. On a donc x 0.

5. Si la matrice A vrifie (1.21), alors la matrice At vrifie (1.20). On en dduit par les questions prcdentesque At et A sont des IP-matrices.

6. Soit 1 le vecteur de IRn dont toutes les composantes sont gales 1. Si Ax > 0, comme lespace IRn estde dimension finie, il existe > 0 tel queAx 1. Soit z = A11 0 ; on a alors A(x z) 0 et doncx z, car A est une IP-matrice.Montrons maintenant que z > 0 : tous les coefficients de A1 sont positifs ou nuls et au moins lun dentreeux est non nul par ligne (puisque la matriceA1 est inversible). On en dduit que zi =

ni=1(A

1)i,j >0 pour tout i = 1, . . . , n. On a donc bien x z > 0.

7. Soit A la matrice nulle, on a alors {x IRn t.q.Ax > 0} = , et donc {x IRn t.q.Ax > 0} {x IRnt.q. x > 0}. Pourtant A nest pas inversible, et nest donc pas une IP-matrice.

8. Soit x tel que Ax 0, alors il existe 0 tel que Ax + 1 0. Soit maintenant b = A11 ; on aA(x + b) > 0 et donc x+ b > 0. En faisant tendre vers 0, on en dduit que x 0.


1.3. LES MTHODES DIRECTES CHAPITRE 1. SYSTMES LINAIRES

9. Soit T L(E) dfini par f E 7 Tf , avec Tf(x) = f( 1x ) si x 6= 0 et f(0) = , avec = lim f . Onvrifie facilement que Tf E. Si Tf 0, alors f( 1x ) 0 pour tout x IR ; donc f(x) 0 pour toutx IR \ {0} ; on en dduit que f(0) 0 par continuit. On a donc bien f 0.Soit maintenant g dfinie de IR dans IR par g(x) = | arctanx|. On a g(0) = 0, donc g 6> 0. Or Tg(0) = 2et Tg(x) = | arctan 1x | > 0 si x > 0, donc Tg > 0.

1.3 Les mthodes directes

1.3.1 Dfinition

Dfinition 1.10 (Mthode directe). On appelle mthode directe de rsolution de (1.1) une mthode qui donneexactement x (A et b tant connus) solution de (1.1) aprs un nombre fini doprations lmentaires (+,,, /).

Parmi les mthodes de rsolution du systme (1.1), la plus connue est la mthode de Gauss (avec pivot), encoreappele mthode dchelonnement ou mthode LU dans sa forme matricielle.Nous rappelons la mthode de Gauss et sa rcriture matricielle qui donne la mthode LU et nous tudierons plusen dtails la mthode de Choleski, qui est adapte aux matrices symtriques.

1.3.2 Mthode de Gauss, mthode LU

Soit A Mn(IR) une matrice inversible, et b IRn. On cherche calculer x IRn tel que Ax = b. Le principede la mthode de Gauss est de se ramener, par des oprations simples (combinaisons linaires), un systmetriangulaire quivalent, qui sera donc facile inverser.Commenons par un exemple pour une matrice 3 3. Nous donnerons ensuite la mthode pour une matrice nn.

Un exemple 3 3On considre le systme Ax = b, avec

A =

1 0 10 2 11 1 2

b = 212

.On crit la matrice augmente, constitue de la matrice A et du second membre b.

A =[A b

]=

1 0 1 20 2 1 11 1 2 2

.Gauss et oprations matricielles Allons y pour Gauss :La premire ligne a un 1 en premire position (en gras dans la matrice), ce coefficient est non nul, et cest un pivot.On va pouvoir diviser toute la premire ligne par ce nombre pour en soustraire un multiple toutes les lignesdaprs, dans le but de faire apparatre des 0 dans tout le bas de la colonne.La deuxime quation a dj un 0 dessous, donc on na rien besoin de faire. On veut ensuite annuler le premiercoefficient de la troisime ligne. On retranche donc (-1) fois la premire ligne la troisime 3 : 1 0 1 20 2 1 1

1 1 2 2

3to3+11 0 1 20 2 1 10 1 1 0

3. Bien sr, ceci revient ajouter la premire ligne ! Il est cependant prfrable de parler systmatiquement de retrancher quitte utiliser

un coefficient ngatif, car cest ce quon fait conceptuellement : pour llimination on enlve un multiple de la ligne du pivot la ligne courante.



Ceci revient multiplier A gauche par la matrice E1 =

1 0 00 1 01 0 1

.La deuxime ligne a un terme non nul en deuxime position (2) : cest un pivot. On va maintenant annuler ledeuxime terme de la troisime ligne ; pour cela, on retranche 1/2 fois la ligne 2 la ligne 3 :1 1 1 20 2 1 1

0 1 1 0

331/221 0 1 20 2 1 10 0 1

2 12

.Ceci revient multiplier la matrice prcdente gauche par la matrice E2 =

1 0 00 1 00 12 1

. On a ici obtenu unematrice sous forme triangulaire suprieure trois pivots : on peut donc faire la remonte pour obtenir la solutiondu systme, et on obtient (en notant xi les composantes de x) : x3 = 1 puis x2 = 1 et enfin x1 = 1.On a ainsi rsolu le systme linaire.On rappelle que le fait de travailler sur la matrice augmente est extrmement pratique car il permet de travaillersimultanment sur les coefficients du systme linaire et sur le second membre.Finalement, au moyen des oprations dcrites ci-dessus, on a transform le systme linaire

Ax = b en Ux = E2E1b, o U = E2E1A

est une matrice triangulaire suprieure.

Factorisation LU Tout va donc trs bien pour ce systme, mais supposons maintenant quon ait rsoudre3089 systmes, avec la mme matrice A mais 3089 seconds membres b diffrents 4. Il serait un peu dommagede recommencer les oprations ci-dessus 3089 fois, alors quon peut en viter une bonne partie. Comment faire ?Lide est de factoriser la matriceA, c..d de lcrire comme un produitA = LU , o L est triangulaire infrieure(lower triangular) et U triangulaire suprieure (upper triangular). On reformule alors le systme Ax = b sous laforme LUx = b et on rsout maintenant deux systmes faciles rsoudre car triangulaires : Ly = b et Ux = y.La factorisationLU de la matrice dcoule immdiatement de lalgorithme de Gauss. Voyons comment sur lexempleprcdent.

1/ On remarque que U = E2E1A peut aussi scrire A = LU , avec L = (E2E1)1.

2/ On sait que (E2E1)1 = (E1)1(E2)1.

3/ Les matrices inversesE11 et E12 sont faciles dterminer : commeE2 consiste retrancher 1/2 fois la ligne 2

la ligne 3, lopration inverse consiste ajouter 1/2 fois la ligne 2 la ligne 3, et donc

E12 =

1 0 00 1 00 12 1

.

Il est facile de voir que E11 =

1 0 00 1 01 0 1

et donc L = E11 E12 = 1 0 00 1 01 12 1

.La matrice L est une matrice triangulaire infrieure (et cest dailleurs pour cela quon lappelle L, pour lowerin English...) dont les coefficients sont particulirement simples trouver : les termes diagonaux sont tous gaux un, et chaque terme non nul sous-diagonal i,j est gal au coefficient par lequel on a multipli la ligne pivoti avant de la retrancher la ligne j.

4/ On a bien donc A = LU avec L triangulaire infrieure (lower triangular) et U triangulaire suprieure (uppertriangular).

4. Ceci est courant dans les applications. Par exemple on peut vouloir calculer la rponse dune structure de gnie civil 3089 chargementsdiffrents.



a(1)1,1

a(i+1)i+1,i+1

a(i+1)i+2,i+1

a(i+1)N,N

a(1)1,N

a(i+1)N,i+10

0

0

0

A(i+1) =

FIGURE 1.3: Allure de la matrice de Gauss ltape i+ 1

La procdure quon vient dexpliquer sappelle mthode LU pour la rsolution des systmes linaires, et elleest dune importance considrable dans les sciences de lingnieur, puisquelle est utilise dans les programmesinformatiques pour la rsolution des systmes linaires.Dans lexemple que nous avons tudi, tout se passait trs bien car nous navons pas eu de zro en position pivotale.Si on a un zro en position pivotale, la factorisation peut quand mme se faire, mais au prix dune permutation.Le rsultat gnral que lon peut dmontrer est que si la matrice A est inversible, alors il existe une matrice depermutationP , une matrice triangulaire infrieureL et unematrice triangulaire suprieureU telles quePA = LU :voir le thorme 1.19.

Le cas gnral dune matrice n nDe manire plus gnrale, pour une matrice A carre dordre n, la mthode de Gauss scrit :On pose A(1) = A et b(1) = b. Pour i = 1, . . . , n 1, on cherche calculer A(i+1) et b(i+1) tels que lessystmes A(i)x = b(i) et A(i+1)x = b(i+1) soient quivalents, o A(i+1) est une matrice dont les coefficientssous-diagonaux des colonnes 1 i sont tous nuls, voir figure 1.3 :Une fois la matrice A(n) (triangulaire suprieure) et le vecteur b(n) calculs, il sera facile de rsoudre le systmeA(n)x = b(n). Le calcul de A(n) est ltape de factorisation", le calcul de b(n) ltape de descente", et le calculde x ltape de remonte". Donnons les dtails de ces trois tapes.

Etape de factorisation et descente Pour passer de la matrice A(i) la matrice A(i+1), on va effectuer descombinaisons linaires entre lignes qui permettront dannuler les coefficients de la i-me colonne situs en dessousde la ligne i (dans le but de se rapprocher dune matrice triangulaire suprieure). Evidemment, lorsquon fait ceci,il faut galement modifier le second membre b en consquence. Ltape de factorisation et descente scrit donc :

1. Pour k i et pour j = 1, . . . , n, on pose a(i+1)k,j = a(i)k,j et b(i+1)k = b(i)k .2. Pour k > i, si a(i)i,i 6= 0, on pose :

a(i+1)k,j = a

(i)k,j

a(i)k,i

a(i)i,i

a(i)i,j , pour k = j, . . . , n, (1.30)

b(i+1)k = b

(i)k

a(i)k,i

a(i)i,i

b(i)i . (1.31)

La matrice A(i+1) est de la forme donne sur la figure 1.3. Remarquons que le systme A(i+1)x = b(i+1) est bienquivalent au systme A(i)x = b(i).Si la condition a(i)i,i 6= 0 est vrifie pour i = 1 n, on obtient par le procd de calcul ci-dessus un systme linaireA(n)x = b(n) quivalent au systme Ax = b, avec une matrice A(n) triangulaire suprieure facile inverser. On



verra un peu plus loin les techniques de pivot qui permettent de rgler le cas o la condition a(i)i,i 6= 0 nest pasvrifie.

Etape de remonte Il reste rsoudre le systme A(n)x = b(n). Ceci est une tape facile. Comme A(n) est unematrice inversible, on a a(i)i,i 6= 0 pour tout i = 1, . . . , n, et commeA(n) est une matrice triangulaire suprieure, onpeut donc calculer les composantes de x en remontant", cestdire de la composante xn la composante x1 :

xn =b(n)n

a(n)n,n

,

xi =1

a(n)i,i

b(i) j=i+1,n

a(n)i,j xj

, i = n 1, . . . , 1.Il est important de savoir mettre sous forme algorithmique les oprations que nous venons de dcrire : cest ltapeclef avant lcriture dun programme informatique qui nous permettra de faire faire le boulot par lordinateur !

Algorithme 1.11 (Gauss sans permutation).

1. (Factorisation et descente)Pour i allant de 1 n, on effectue les calculs suivants :

(a) On ne change pas la i-me ligne (qui est la ligne du pivot)ui,j = ai,j pour j = i, . . . , n,yi = bi

(b) On calcule les lignes i+ 1 n de U et le second membre y en utilisant la ligne i.Pour k allant de i+ 1 n :

k,i =ak,iai,i

(si ai,i = 0, prendre la mthode avec pivot partiel)

pour j allant de i+ 1 n,uk,j = ak,j k,iui,j (noter que ak,i = 0)

Fin pouryk = bk k,iyi

Fin pour

2. (Remonte) On calcule x :

xn =ynun,n

Pour i allant de n 1 1,xi = yi

Pour j allant de i+ 1 n,xi = xi ui,jxj

Fin pour

xi =1

ui,ixi

Fin pour

Cot de la mthode de Gauss (nombre doprations) On peut montrer (on fera le calcul de manire dtaillepour la mthode de Choleski dans la section suivante, le calcul pour Gauss est similaire) que le nombre doprationsncessaires nG pour effectuer les tapes de factorisation, descente et remonte est 23n

3 + O(n2) ; on rappellequune fonction f de IN dans IN est O(n2) veut dire qui existe un rel constant C tel que f(n) Cn2. On a donclimn+ nGn3 =

23 : lorsque n est grand, le nombre doprations se comporte comme n

3.En ce qui concerne la place mmoire, on peut trs bien stocker les itrsA(i) dans la matriceA de dpart, ce quonna pas voulu faire dans le calcul prcdent, par souci de clart.



Dcomposition LU Si le systme Ax = b doit tre rsolu pour plusieurs second membres b, on a dj dit quona intrt ne faire ltape de factorisation (i.e. le calcul deA(n)), quune seule fois, alors que les tapes de descenteet remonte (i.e. le calcul de b(n) et x) seront faits pour chaque vecteur b. Ltape de factorisation peut se faire endcomposant la matriceA sous la forme LU . Supposons toujours pour linstant que lors de lalgorithme de Gauss,

la condition a(i)i,i 6= 0 est vrifie pour tout i = 1, . . . , n. La matrice L a comme coefficients k,i =a(i)k,i

a(i)i,i

pour k > i,

i,i = 1 pour tout i = 1, . . . , n, et i,j = 0 pour j > i, et la matrice U est gale la matrice A(n). On peut vrifierque A = LU grce au fait que le systme A(n)x = b(n) est quivalent au systme Ax = b. En effet, commeA(n)x = b(n) et b(n) = L1b, on en dduit que LUx = b, et comme A et LU sont inversibles, on en dduit queA1b = (LU)1b pour tout b IRn. Ceci dmontre que A = LU. La mthode LU se dduit donc de la mthodede Gauss en remarquant simplement que, ayant conserv la matrice L, on peut effectuer les calculs sur b aprs lescalculs sur A, ce qui donne :

Algorithme 1.12 (LU simple (sans permutation)).

1. (Factorisation) Pour i allant de 1 n, on effectue les calculs suivants :

(a) On ne change pas la i-me ligne

ui,j = ai,j pour j = i, . . . , n,

(b) On calcule les lignes i+ 1 n de U en utilisant la ligne i (mais pas le second membre).

Pour k allant de i+ 1 n :

k,i =ak,iai,i

(si ai,i = 0, prendre la mthode avec pivot partiel)

pour j allant de i+ 1 n,

uk,j = ak,j k,iui,j (noter que ak,i = 0)Fin pour

2. (Descente) On calcule y (avec Ly = b)

Pour i allant de 1 n,

yi = bi i1

k=1 i,kyk (on a ainsi implicitement i,i = 1)

3. (Remonte) On calcule x (avec Ux = y)

Pour i allant de n 1,

xi =1ui,i

(yi n

j=i+1 ui,jxj)

Remarque 1.13 (Optimisation mmoire). Lintroduction des matrices L et U et des vecteurs y et x nest pasncessaire (tout peut scrire avec la matrice A et le vecteur b, que lon modifie au cours de lalgorithme). Lin-troduction de L, U , x et y peut toutefois aider comprendre la mthode. Le principe retenu est que, dans lesalgorithmes (Gauss ou LU), on modifie la matrice A et le second membre b (en remplaant le systme rsoudrepar un systme quivalent) mais on ne modifie jamais L, U , y et x (qui sont dfinis au cours de lalgorithme).

Nous allons maintenant donner une condition ncessaire et suffisante (CNS) pour quune matrice A admette unedcomposition LU avec U inversible et sans permutation. Commenons par un petit lemme technique qui va nouspermettre de prouver cette CNS.

Lemme 1.14 (Dcomposition LU de la matrice principale dordre k). Soit n IN, A Mn(IR) et k {1, . . . , N}. On appelle matrice principale dordre k de A la matrice Ak Mk(IR) dfinie par (Ak)i,j = ai,jpour i = 1, . . . , k et j = 1, . . . , k. On suppose quil existe une matrice Lk Mk(IR) triangulaire infrieure decoefficients diagonaux tous gaux 1 et une matrice triangulaire suprieure Uk Mk(IR) inversible, telles queAk = LkUk. Alors A scrit sous la forme par blocs suivante :

A =

Lk 0k(nk)Ck Idnk

Uk Bk0(nk)k Dk

, (1.32)



o 0p,q dsigne la matrince nulle de dimension p q, Bk Mk,nk(IR) et Ck Mnk,k(IR) et Dk Mnk,nk(IR) ; de plus, la matrice principale dordre k + 1 scrit sous la forme

Ak+1 =

Lk 01kck 1

Uk bk0k1 dk

(1.33)o b Mk,1(IR) est la premire colonne de la matrice Bk, ck M1,k est la premire ligne de la matrice Ck, etdk est le coefficient de la ligne 1 et colonne 1 deDk.

DMONSTRATION On crit la dcomposition par blocs de A :

A =

Ak EkFk Gk

,avecAk Mk(IR),Ek Mk,nk(IR), Fk Mnk,k(IR) etGk Mnk,nk(IR). Par hypothse, on aAk = LkUk.De plus Lk et Uk sont inversibles, et il existe donc une unique matrice Bk Mk(IR) (resp. Ck Mk(IR)) telleque LkBk = Ek (resp CkUk = Gk). En posant Dk = Gk BkCk, on obtient (1.32). Lgalit (1.33) en dcouleimmdiatement.

Proposition 1.15 (CNS pour LU sans permutation). Soit n IN, A Mn(IR). Les deux proprits suivantessont quivalentes.

(P1) Il existe un unique couple (L,U), avec L matrice triangulaire infrieure de coefficients gaux 1 et U unematrice inversible triangulaire suprieure, tel que A = LU .

(P2) Les mineurs principaux 5 de A sont tous non nuls.

DMONSTRATION Si A = LU avec L triangulaire infrieure de coefficients gaux 1 et U inversible triangulairesuprieure, alors Ak = LkUk o les matrices Lk et Uk les matrices principales dordre k de L et U , qui sont encorerespectivement triangulaire infrieure de coefficients gaux 1 et inversible triangulaire suprieure. On a donc

det(Ak) = det(Lk)det(Uk) 6= 0 pour tout k = 1, . . . , n,et donc (P1) (P2).Montrons maintenant la rciproque. On suppose que les mineurs sont non nuls, et on va montrer que A = LU . On vaen fait montrer que pour tout k = 1, . . . n, on a Ak = LkUk o Lk triangulaire infrieure de coefficients gaux 1et Uk inversible triangulaire suprieure. Le premier mineur est non nul, donc a11 = 1 a11, et la rcurrence est bieninitialise. On la suppose vraie ltape k. Par le lemme 1.14, on a donc Ak+1 qui est de la forme (1.33), et donc uneAk+1 = Lk+1Uk+1 Comme det(Ak+1) 6= 0, la matrice Uk+1 est inversible, et lhypothse de rcurrence est vrifie lordre k + 1. On a donc bien (P2) (P1).

Que faire en cas de pivot nul : la technique de permutation La caractrisation que nous venons de donner pourquune matrice admette une dcomposition LU sans permutation est intressante mathmatiquement, mais de peudintrt en pratique. On ne va en effet jamais calculer n dterminants pour savoir si non peut ou non permuter. Enpratique, on effectue la dcompositionLU sans savoir si on a le droit ou non de le faire, avec ou sans permutation.Au cours de llimination, si a(i)i,i = 0, on va permuter la ligne i avec une des lignes suivantes telle que a

(i)k,i 6= 0.

Notons que si le pivot" a(i)i,i est trs petit, son utilisation peut entraner des erreurs darrondi importantes dans lescalculs et on va l encore permuter. En fait, mme dans le cas o la CNS donne par la proposition 1.15 est verifie,la plupart des fonctions de libraries scientifiques vont permuter.Plaons-nous litration i de la mthode de Gauss. Comme la matrice A(i) est forcment non singulire, on a :

det(A(i)) = a(i)1,1a

(i)2,2 a(i)i1,i1det

a(i)i,i . . . a

(i)i,n

.... . .

...

a(i)n,i . . . a

(i)n,n

6= 0.5. On rappelle que le mineur principal dordre k est le dterminant de la matrice prinicipale dordre k.



On a donc en particulier

det

a(i)i,i . . . a

(i)i,n

.... . .

...

a(i)n,i . . . a

(i)n,n

6= 0.On dduit quil existe i0 {i, . . . , n} tel que a(i)i0,i 6= 0. On choisit alors i0 {i, . . . , n} tel que |a

(i)i0,i| =

max{|a(i)k,i|, k = i, . . . , n}. Le choix de ce max est motiv par le fait quon aura ainsi moins derreur darrondi. Onchange alors les lignes i et i0 (dans la matrice A et le second membre b) et on continue la procdure de Gaussdcrite plus haut.Lintrt de cette stratgie de pivot est quon aboutit toujours la rsolution du systme (ds que A est inversible).

Remarque 1.16 (Pivot total). La mthode que nous venons de dcrire est souvent nomme technique de pivotpartiel. On peut vouloir rendre la norme du pivot encore plus grande en considrant tous les coefficients restantset pas uniquement ceux de la colonne i. A letape i, on choisit maintenant i0 et j0 {i, . . . , n} tels que |a(i)i0,j0 | =max{|a(i)k,j|, k = i, . . . , n, j = i, . . . , n}, et on change alors les lignes i et i0 (dans la matrice A et le secondmembre b), les colonnes i et j0 deA et les inconnues xi et xj0 . La stratgie du pivot total permet une moins grandesensibilit aux erreurs darrondi. Linconvnient majeur est quon change la structure de A : si, par exemple lamatrice avait tous ses termes non nuls sur quelques diagonales seulement, ceci nest plus vrai pour la matriceA(n).

Ecrivons maintenant lalgorithme de la mthode LU avec pivot partiel ; pour ce faire, on va simplement remarquerque lordre dans lequel les quations sont prises na aucune importance pour lalgorithme. Au dpart de lalgo-rithme, on initialise la bijection t de {1, . . . , n} dans {1, . . . , n} par lidentit, c..d. t(i) = i ; cette bijection t vatre modifie au cours de lalgorithme pour tenir compte du choix du pivot.

Algorithme 1.17 (LU avec pivot partiel).

1. (Initialisation de t) Pour i allant de 1 n, t(i) = i. Fin pour

2. (Factorisation)

Pour i allant de 1 n, on effectue les calculs suivants :

(a) Choix du pivot (et de t(i)) : on cherche i {i, . . . , n} t.q. |at(i),i| = max{|at(k),i|, k {i, . . . , n}} (noter que ce max est forcment non nul car la matrice est inversible).

On modifie alors t en inversant les valeurs de t(i) et t(i).p = t(i) ; t(i) = t(i) ; t(i) = p.

On ne change pas la ligne t(i) :ut(i),j = at(i),j pour j = i, . . . , n,

(b) On modifie les lignes t(k), k > i (et le second membre), en utilisant la ligne t(i).Pour k = i+ 1, . . . , n} (noter quon a uniquement besoin de connatre lensemble , et pas lordre) :t(k),i =

at(k),iat(i),iPour j allant de i+ 1 n,

ut(k),j = at(k),j t(k),iut(i),j (noter que ut(k),i = 0)Fin pour

Fin pour

3. (Descente) On calcule y

Pour i allant de 1 n,

yt(i) = bt(i) i1

j=1 t(j),kykFin pour



4. (Remonte) On calcule xPour i allant de n 1,x(t(i) =

1ut(i),i

(yi n

j=i+1 ut(i),jxj)

Fin pour

NB : On a chang lordre dans lequel les quations sont considres (le tableau t donne cet ordre, et donc lamatrice P ). Donc, on a aussi chang lordre dans lequel interviennent les composantes du second membre : lesystme Ax = b est devenu PAx = Pb. Par contre, on na pas touch lordre dans lequel interviennent lescomposantes de x et y.

Il reste maintenant signaler la proprit magnifique de cet algorithme. . . Il est inutile de connaitre a priorila bijection pour cet algorithme. A ltape i de litem 1 (et dailleurs aussi ltape i de litem 2), il suffit deconnatre t(j) pour j allant de 1 i, les oprations de 1(b) se faisant alors sur toutes les autres lignes (dans unordre quelconque). Il suffit donc de partir dune bijection arbitraire de {1, . . . , n} dans {1, . . . , n} (par exemplelidentit) et de la modifier chaque tape. Pour que lalgorithme aboutisse, il suffit que at(i),i 6= 0 (ce qui toujourspossible car A est inversible).

Remarque 1.18 (Ordre des quations et des inconnues). Lalgorithme se ramne donc rsoudre LUx = b, enrsolvant dabord Ly = b puis Ux = y. Notons que lors de la rsolution du systme Ly = b, les quations sontdans lordre t(1), . . . , t(k) (les composantes de b sont donc aussi prises dans cet ordre), mais le vecteur y estbien le vecteur de composantes (y1, . . . , yn), dans lordre initial. Puis, on rsout Ux = y, et les quations sontencore dans lordre t(1), . . . , t(k) mais les vecteurs x et y ont comme composantes respectives (x1, . . . , xn) et(y1, . . . , yn).

Le thorme dexistence Lalgorithme LU avec pivot partiel nous permet de dmontrer le thorme dexistencede la dcomposition LU pour una matrice inversible.

Thorme 1.19 (Dcomposition LU dune matrice). Soit A Mn(IR) une matrice inversible, il existe unematrice de permutation P telle que, pour cette matrice de permutation, il existe un et un seul couple de matrices(L,U) o L est triangulaire infrieure de termes diagonaux gaux 1 et U est triangulaire suprieure, vrifiant

PA = LU.

DMONSTRATION 1. Lexistence de la matrice P et des matrices L U peut seffectuer en sinspirant de lalgorithme LU avec pivot partiel1.17). Posons A(0) = A. chaque tape i de lalgorithme 1.17 peut scrire comme A(i) = E(i)P (i)A(i1), o P (i) est la matrice de permutationqui permet le choix du pivot partiel, et E(i) est une matrice dlimination qui effectue les combinaisons linaires de lignespermettant de mettre zro tous les coefficients de la colonne i situs en dessous de la ligne i. Pour simplifier, raisonnonssur une matrice 4 4 (le raisonnement est le mme pour une matrice n n. On a donc en appliquant lalgorithme deGauss :

E(3)P

(3)E

(2)P

(2)E

(1)P

(1)A = U

Les matrices P (i+1) et E(i) ne permutent en gnal pas. Prenons par exemple E2, qui est de la forme

E(2) =

1 0 0 00 1 0 00 a 1 00 b 0 1

Si P (3) est la matrice qui change les lignes 3 et 4, alors

P(3) =

1 0 0 00 1 0 00 0 0 10 0 1 0

et P (3)E(2) =1 0 0 00 1 0 00 b 0 10 a 1 0

, alors que E(2)P (3) =1 0 0 00 1 0 00 a 0 10 b 1 0



Mais par contre, comme la multiplication gauche par P (i+1) permute les lignes i + 1 et i + k, pour un certain k 1,et que la multiplication droite permute les colonnes i+ 1 et i + k, la matrice E(i) = P (i+1)E(i)P (i+1) est encore unematrice triangulaire infrieure avec la mme structure que E(i) : on a juste chang les coefficients extradiagonaux deslignes i+ 1 et i+ k. On a donc

P(i+1)

E(i) = E(i)P (i+1). (1.34)

Dans lexemple prcdent, on effectue le calcul :

P(3)E

(2)P

(3) =

1 0 0 00 1 0 00 b 1 00 a 0 1

= E(2,qui est une matrice triangulaire infrieure de coefficients tous gaux 1, et comme P (3)P (3) = Id, on a donc :

P(3)E

(2) = E(2)P (3).

Pour revenir notre exemple n = 4, on peut donc crire :

E(3)E(2)P

(3)E(1)P

(2)P

(1)A = U

Mais par le mme raisonnement que prcdemment, on a P (3)E(1) =E(1)P (3) o

E(1) est encore une matrice triangulaire

infrieure avec des 1 sur la diagonale. On en dduit que

E(3)E(2)

E(1)P

(3)P

(2)P

(1)A = U, soit encore PA = LU

o P = P (3)P (2)P (1) bien une matrice de permutation, et L = (E(3)E(2)E(1))1 est une matrice triangulaire infrieure

avec des 1 sur la diagonale.

Le raisonnement que nous venons de faire pour n = 3 se gnralise facilement n quelconque. Dans ce cas, lchelonne-ment de la matrice scrit sous la forme

U = E(n1)P (n1) . . . E(2)P (2)E(1)P (1)A,

et se transforme grce (1.34) en

U = F (n1) . . . F (2)F (1)P (n1) . . . P (2)P (1)A,

o les matrices F (i) sont des matrices triangulaires infrieures de coefficients diagonaux tous gaux 1. Plus prcisment,

F (n1) = E(n1), F (n2) = E(n2), F (n3) =E(n3), etc. . . On a ainsi dmontr lexistence de la dcomposition

LU .

2. Pour montrer lunicit du couple (L,U) P donne, supposons quil existe une matrice P et des matrices L1, L2,triangulaires infrieures et U1, U2, triangulaires suprieures, telles que

PA = L1U1 = L2U2

Dans ce cas, on a donc L12 L1 = U2U11 .Or la matrice L

12 L1 est une matrice triangulaire infrieure dont les coefficients

diagonaux sont tout gaux 1, et la matrice U2U11 est une matrice triangulaire suprieure. On en dduit que L12 L1 =

U2U11 = Id, et donc que L1 = L2 et U1 = U2.

Remarque 1.20 (Dcomposition LU pour les matrices non inversibles). En fait nimporte quelle matrice carreadmet une dcomposition de la forme PA = LU . Mais si la matrice A nest pas inversible, son chelonnementva nous donner des lignes de zros pour les dernires lignes . La dcomposition LU nest dans ce cas pas unique.Cette remarque fait lobjet de lexercice 20.

1.3.3 Mthode de Choleski

On va maintenant tudier la mthode de Choleski, qui est une mthode directe adapte au cas o A est symtriquedfinie positive. On rappelle quune matrice A Mn(IR) de coefficients (ai,j)i=1,n,j=1,n est symtrique siA = At, o At dsigne la transpose de A, dfinie par les coefficients (aj,i)i=1,n,j=1,n, et que A est dfiniepositive si Ax x > 0 pour tout x IRn tel que x 6= 0. Dans toute la suite, x y dsigne le produit scalaire desdeux vecteurs x et y de IRn. On rappelle (exercice) que si A est symtrique dfinie positive elle est en particulierinversible.



Description de la mthode

Commenons par un exemple. On considre la matrice A =

2 1 01 2 10 1 2

, qui est symtrique. Calculons sadcomposition LU . Par chelonnement, on obtient

A = LU =

1 0 0 12 1 00 23 1

2 1 00 32 10 0 43

La structure LU ne conserve pas la symtrie de la matriceA. Pour des raisons de cot mmoire, il est important depouvoir la conserver. Une faon de faire est de dcomposer U en sa partie diagonale fois une matrice triangulaire.On obtient

U =

2 0 00 32 00 0 43

1 12 00 1 230 0 1

On a donc U = DLt, et comme tous les coefficients de D sont positifs, on peut crire D =

DD, o

D est

la matrice diagonale dont les lments diagonaux sont les racines carres des lments diagonaux de A. On a doncA = L

DDLt = LLt, avec L = L

D. Notons que la matrice L est toujours triangulaire infrieure, mais ses

coefficients diagonaux ne sont plus astreints tre gaux 1. Cest la dcomposition de Choleski de la matrice A.

De fait, la mthode de Choleski consiste donc trouver une dcomposition dune matrice A symtrique dfiniepositive de la forme A = LLt, o L est triangulaire infrieure de coefficients diagonaux strictement positifs. Onrsout alors le systme Ax = b en rsolvant dabord Ly = b puis le systme Ltx = y. Une fois la matriceA factorise", cestdire la dcomposition LLt obtenue (voir paragraphe suivant), on effectue les tapes dedescente" et remonte" :

1. Etape 1 : descente" Le systme Ly = b scrit :

Ly =

1,1 0... . . . ...n,1 . . . n,n

y1...

yn

= b1...

bn

.Ce systme scrit composante par composante en partant de i = 1.

1,1y1 = b1, donc y1 =b11,1

2,1y1 + 2,2y2 = b2, donc y2 =1

2,2(b2 2,1y1)

......

j=1,i

i,jyj = bi, donc yi =1

i,i(bi

j=1,i1

i,jyj)

......

j=1,n

n,jyj = bn, donc yn =1

n,n(bn

j=1,n1

n,jyj).

On calcule ainsi y1, y2, . . . , yn.



2. Etape 2 : remonte" On calcule maintenant x solution de Ltx = y.

Ltx =

1,1 2,1 . . . n,1

0. . .

......

0 . . . n,n

x1

...

xn

=

y1

...

yn

.

On a donc :n,n xn = yn donc xn =

ynn,n

n1,n1xn1 + n,n1xn = yn1 donc xn1 =yn1n,n1xn

n1,n1...j=1,n

j,1xj = y1 donc x1 =y1

j=2,n j,1xj

1,1.

On calcule ainsi xn, xn1, . . . , x1.

Existence et unicit de la dcomposition

Soit A une matrice symtrique dfinie positive. On sait dj par le thorme 1.19 page 29, quil existe une matricede permutation et L triangulaire infrieure et U triangulaire suprieure telles que PA = LU . Lavantage dans lecas o la matrice est symtrique dfinie positive, est que la dcomposition est toujours possible sans permutation.On prouve lexistence et unicit en construisant la dcomposition, c..d. en construisant la matrice L.Pour comprendre le principe de la preuve, commenons dabord par le cas n = 2. Dans ce cas on peut crire

A =

[a bb c

]. On sait que a > 0 car A est s.d.p. . Lchelonnement de A donne donc

A = LU =

[1 0ba 1

] [a b

0 c b2a

]En extrayant la diagonale de U , on obtient :

A = LU =

[1 0ba 1

] [a 0

0 c b2a

] [a ba0 1

].

Et donc

A = LLt avec L =

[ a 0

b

acb2a

].

Thorme 1.21 (Dcomposition de Choleski). SoitA Mn(IR) (n 1) une matrice symtrique dfinie positive.Alors il existe une unique matrice L Mn(IR), L = (i,j)ni,j=1, telle que :

1. L est triangulaire infrieure (cestdire i,j = 0 si j > i),

2. i,i > 0, pour tout i {1, . . . , n},3. A = LLt.

DMONSTRATION

I- Existence de L : dmonstration par rcurrence sur n



1. Dans le cas n = 1, on a A = (a1,1). Comme A est symtrique dfinie positive, on a a1,1 > 0. On peut donc dfinirL = (1,1) o 1,1 =

a1,1, et on a bien A = LLt.

2. On suppose que la dcomposition de Choleski sobtient pour A Mp(IR) symtrique dfinie positive, pour 1 p n et on va dmontrer que la proprit est encore vraie pour A Mn+1(IR) symtrique dfinie positive. Soit doncA Mn+1(IR) symtrique dfinie positive ; on peut crire A sous la forme :

A =

B a

at

(1.35)o B Mn(IR) est symtrique, a IRn et IR. Montrons que B est dfinie positive, c..d. que By y > 0, pourtout y IRn tel que y 6= 0. Soit donc y IRn \ {0}, et x =

[y

0

] IRn+1. Comme A est symtrique dfinie positive,

on a :

0 < Ax x =

B a

at

y

0

y

0

=By

aty

y

0

= By ydonc B est dfinie positive. Par hypothse de rcurrence, il existe une matriceM Mn(IR)M = (mi,j)ni,j=1 telleque :

(a) mi,j = 0 si j > i

(b) mi,i > 0

(c) B = MM t.

On va chercher L sous la forme :

L =

M 0

bt

(1.36)avec b IRn, IR+ tels que LLt = A. Pour dterminer b et , calculons LLt o L est de la forme (1.36) etidentifions avec A :

LLt =

M 0

bt

M t b

0

=MM t Mb

btM t btb+ 2

On cherche b IRn et IR+ tels que LLt = A, et on veut donc que les galits suivantes soient vrifies :

Mb = a et btb+ 2 = .

Comme M est inversible (en effet, le dterminant de M scrit det(M) =n

i=1mi,i > 0), la premire galit ci-dessus donne : b = M1a et en remplaant dans la deuxime galit, on obtient : (M1a)t(M1a) + 2 = , doncat(M t)1M1a+ 2 = soit encore at(MM t)1a+ 2 = , cestdire :

atB1a+ 2 = (1.37)

Pour que (1.37) soit vrifie, il faut que atB1a > 0 (1.38)

Montrons que la condition (1.38) est effectivement vrifie : Soit z =

(B1a

1) IRn+1. On a z 6= 0 et donc

Az z > 0 car A est symtrique dfinie positive. Calculons Az :

Az =

B aat

B1a

1

=

0

atB1a

.



On a donc Az z = atB1a > 0 ce qui montre que (1.38) est vrifie. On peut ainsi choisir = atB1a(> 0) de telle sorte que (1.37) est vrifie. Posons :

L =

M 0

(M1a)t

.La matrice L est bien triangulaire infrieure et vrifie i,i > 0 et A = LLt.

On a termin ainsi la partie existence.

II- Unicit et calcul de L. Soit A Mn(IR) symtrique dfinie positive ; on vient de montrer quil existe L Mn(IR)triangulaire infrieure telle que i,j = 0 si j > i, i,i > 0 et A = LLt. On a donc :

ai,j =n

k=1

i,kj,k, (i, j) {1 . . . n}2. (1.39)

1. Calculons la 1-re colonne de L ; pour j = 1, on a :

a1,1 = 1,11,1 donc 1,1 =a1,1 (a1,1 > 0 car 1,1 existe ),

a2,1 = 2,11,1 donc 2,1 =a2,1

1,1,

ai,1 = i,11,1 donc i,1 =ai,1

1,1i {2, . . . , n}.

2. On suppose avoir calcul les q premires colonnes de L. On calcule la colonne (q + 1) en prenant j = q + 1 dans(1.39)

Pour i = q + 1, aq+1,q+1 =q+1k=1

q+1,kq+1,k donc

q+1,q+1 = (aq+1,q+1 q

k=1

2q+1,k)

1/2> 0. (1.40)

Notons que aq+1,q+1q

k=1

2q+1,k > 0 car L existe : il est indispensable davoir dabord montr lexistence de L pour

pouvoir exhiber le coefficient q+1,q+1.

On procde de la mme manire pour i = q + 2, . . . , n ; on a :

ai,q+1 =

q+1k=1

i,kq+1,k =

qk=1

i,kq+1,k + i,q+1q+1,q+1

et donc

i,q+1 =

(ai,q+1

qk=1

i,kq+1,k

)1

q+1,q+1. (1.41)

On calcule ainsi toutes les colonnes de L. On a donc montr que L est unique par un moyen constructif de calcul de L.

Remarque 1.22 (Choleski et LU .). Considrons une matrice A symtrique dfinie positive. Alors une matrice Pde permutation dans le thorme 1.21 possible nest autre que lidentit. Il suffit pour sen convaincre de remarquerquune fois quon sest donn la bijection t = Id dans lalgorithme 1.17, celle-ci nest jamais modifie et donc ona P = Id. Les thormes dexistence et dunicit 1.19 et 1.21 nous permettent alors de remarquer que A = LU =LLt avec L = L

D, oD est la matrice diagonale extraite de U , et

D dsigne la matrice dont les coefficients

sont les racines carres des coefficients deD (qui sont tous positifs). Voir ce sujet lexercice 21 41.

La dcomposition LU permet de caractriser les matrices symtriques dfinies positives.



Proposition 1.23 (Caractrisation des matrices symtriques dfinies positives par la dcomposition LU ). Soit Aune matrice symtrique admettant une dcompositionLU sans permutation, cest--dire quon suppose quil existeL triangulaire infrieure de coefficients diagonaux tous gaux 1, et U triangulaire suprieure telle queA = LU .Alors A est symrique dfinie positive si et seulement si tous les pivots (cest--dire les coefficients diagonaux dela matrice U ) sont

Documents

Analyse Matr