[PDF] [PDF] Exercice 2 Soit A ∈ M n(R) une matrice inversible admettant une

[PDF] Matrices inversibles

La notion de matrice inversible n'a de sens que pour des matrices carrées Méthode 1 : Montrer qu'une matrice est inversible et calculer son inverse

[PDF] Matrices - Exo7 - Cours de mathématiques

Montrer que si A+ B = A, alors B est la matrice nulle 3 Que vaut 0 · A? et 1 C' est une matrice inversible, et son inverse est elle-même par l'égalité InIn = In

[PDF] Exercices Corrigés Matrices Exercice 1 – Considérons les matrices

Exercice 12 – Soit A et B deux matrices carrées de même ordre, on suppose que la matrice AB est inversible d'inverse la matrice C Montrer alors que B est 

[PDF] Calcul matriciel

8 nov 2011 · gauche ou à droite par une matrice inversible Deux matrices équivalentes ont même rang Nous allons démontrer la réciproque Théorème 4

[PDF] Exercice 2 Soit A ∈ M n(R) une matrice inversible admettant une

Montrer que si factorisation LU existe alors elle est unique 2 Décrire une méthode permettant de calculer explicitement les coefficients des matrices L et U 3 ( 

[PDF] Alg`ebre linéaire Chapitre 2 Introduction aux matrices

En d'autres termes, si une matrice est inversible, l'inverse `a gauche et l'inverse ` a droite de cette matrice sont égaux Démonstration Il suffit de montrer que si 

[PDF] Cours 3: Inversion des matrices dans la pratique - Institut de

Inverse d'une matrice Critère d'inversibilité : le déterminant Quelques exemples det( ( 4 3 -1 2 ) ) = 11, donc la matrice est inversible det( ( 4 -1 -1 1/4 )

[PDF] calculer le déterminant d'une matrice

[PDF] inverse matrice 2x2

[PDF] matrice non inversible

[PDF] matrice des cofacteurs

[PDF] inverse d'une matrice pdf

[PDF] calcul matriciel cours et exercices corrigés pdf

[PDF] calcul matriciel determinant

[PDF] cour matrice

[PDF] comment calculer le cout d'un algorithme

[PDF] taux de rendement production trp

[PDF] trp production definition

[PDF] taux de rendement de production

[PDF] calcul trp production

[PDF] trp calcul

[PDF] faire des statistiques sur excel 2010

Exercice 2

SoitA2 Mn(R)une matrice inversible admettant une factorisationLUoùLest une matrice triangulaire inférieure à

diagonale unité etUest une matrice triangulaire supérieure. 1. Montrer que si facto risationLUexiste alors elle est unique. 2. Décrire une métho dep ermettantde c alculerexplicitement les co efficientsdes matrices LetU. 3. ( algo) Ecrire une fonctionFactLUpermettant de calculer les matricesLetU. 4. Quel est le coût de cette métho de(évaluer le nomb red"op érationsélémentaires) ? 5.

Soit A2 Mn(R)une matrice inversible. Est-il toujours possible de décomposerAsous la formeA=LUoùLest

une matrice triangulaire inférieure à diagonale unité etUest une matrice triangulaire supérieure?1. Supposons que la matriceA2 Mn(R)vérifie

A=L1U1=L2U2;(1)

où -U12 Mn(R)etU22 Mn(R)sont des matrices triangulaires supérieures,

-L12 Mn(R)etL22 Mn(R)sont des matrices triangulaires inférieures à diagonale unité (leurs coefficients diagonaux

sont tous égaux à1). Nous allons montrer queL1=L2etU1=U2. CommeAest inversible, alors det(A) =det(L1U1) =det(L1)det(U1)6= 0:

Cela signifie donc que det(L1)6= 0et det(U1)6= 0, autrement dit que les matricesL1etU1sont inversibles (on savait déjà

en fait queL1était inversible puisqueL1est triangulaire inférieure à diagonale unité). De manière similaire, on montre que

L

2etU2sont inversibles.

Ainsi, la seconde égalité de(1)est équivalente à (L2)1L1=U2(U1)1:(2)

La matriceL2est triangulaire inférieure à diagonale unité. Par conséquent, la matriceL12est triangulaire inférieure à diago-

nale unité. Donc commeL12L1est le produit de deux matrices triangulaires inférieures à diagonale unité, le terme de gauche

de l"égalité(2)est une matrice triangulaire inférieure à diagonale unité.

De manière similaire, comme la matriceU1est triangulaire supérieure, son inverse(U1)1est triangulaire supérieure. Donc,

le terme de droite de l"égalité(2)est une matrice trinagulaire supérieure.

Ainsi, l"égalité(2)implique que(L2)1L1(L2)1etU2(U1)1sont des matrices diagonales à diagonale unité. Puisque

la seule matrice diagonale à diagonale unité est la matrice identité, on a L

2=L1etU2=U1:

Autrement dit, siAadmet une factorisationLU(avecLtriangulaire inférieure à diagonale unité etUtriangulaire inférieure),

cette factorisation est unique.

Remarque.Ce résultat respose de manière essentiel sur le fait queLest à diagonale unité. Sans cette hypothèse, il n"y a pas

unicité de la décomposition.

2. On suppose queAadmet une décompositionLU. L"objectif de cette question de calculerLetU. On poseA=

(aij)(i;j)2[1:n]2((i;j)2N2,1in,1jn),L= (`ij)(i;j)2[1:n]2,U= (uij)(i;j)2[1:n]2. A=0 B

BBBBB@a

11a12 a1n

a

21a22 a2n...............

a n1an2 ann1 C

CCCCCAL=0

B

BBBBB@1 0 0

211 00

............0 n1`n2 `nn1 C

CCCCCA

et U=0 B

BBBBB@u

11u12 u1n

0u22u23u2n...............

......0......

0 0unn1

C

CCCCCA

1 CommeLest triangulaire inférieure à diagonale unité, on sait que, pour touti2[1 :n] ii= 1et`ik= 08k > i:(3) De manière similaire, commeUest triangulaire supérieure, pour toutj2[1 :n], b kj= 08k > j:(4)

Ainsi les inconnues du problèmes sont :

les nomb res`ik, pour touti2[1 :n]et pour toutk < i. les nomb resukj, pour toutj2[1 :n]et pour toutk < j.

CommeA=LU, et en utilisant(3)et(4),

8(i;j)2[1 :n]2;aij=nX

k=1` ikukj=min(i;j)X k=1` ikukj:(5)

La question est donc la suivante :comment utiliser la formule(5)pour touver un algorithme de calcul des inconnues`ik

(i2[1 :n],k < i) etukj(j2[1 :n],k < j)? Nous proposons deux méthodes qui permettent de déterminer ces coefficients :

1. identification des co efficientsde Alignes par lignes: calcul deUetLlignes par lignes. 2.

identification des co efficientsde Amixte: calcul de laUcolonnes par colonnes et deLlignes par lignes.

Remarque.La méthode que nous allons mettre en oeuvre pour calculerLetUs"appelle la méthode de Crout.

Méthode 1 : identification lignes par lignes

Étape 1 : identification de la première ligne deA

Nous allons voir que cette étape va nous permettre de calculer la première ligne deU(i.e les coefficientu1jpour tout

j2[1 :n]) et la première ligne deL(il n"y a en fait rien à calculer puisque`11= 1et`1k= 0sinon).

L"equation(5)pouri= 1donne

a 1j=1X k=1`

1kukj=`11u1j=u1j

carmin(1;j) = 1et`11= 1. Ainsi, u

1j=a1j(6)

ce qui nous permet de calculer la première ligne deU. A l"issue de cette première étape, la première ligne deLet la première

ligne deUsont intégralement déterminée. Étape 2 : identification de la deuxième ligne deA

Nous allons voir que cette étape va nous permettre de calculer la deuxième ligne deL(i.e, le coefficient`21)puisla deuxième

ligne deU(i.e les coefficientu2jpour toutj2).

L"equation(5)pouri= 2donne

a

2j=min(j;2)X

k=1`

2kukj(7)

Nous discutons deux cas, suivant la valeur demin(j;2): a-j <2(min(j;2) =j) : dans ce cas,j= 1, et on a a

21=`21u11:

Commeu11a été calculé à la première étape, on en déduit que

21=a21u

11(8)

si bien que la deuxième ligne deLest maintenant déterminée (On note, que puisque par hypothèse,Aest inversible

etA=LU,u116= 0). 2 b-j2(min(j;2) = 2) : la formule(7)devient a

2j=`21u1j+`22u2j

ou encore, puisque`22= 1, u

2j=a2j`21u1j(8j2):(9)

Le terme de droite de l"equation précédente est connu intégralement :`21a été calculée lors de l"étape 2-a ((8)) et les

termesu1jest connu depuis l"étape 1. La seconde ligne deUest maintenant complètement déterminée.

Remarque.Dans le processus d"identification ci dessus, il n"est pas possible d"intervertir les étapes 2-a et 2-b.

Étape i : identification de la ligneideA

Dans cette étape, nous allons calculer la ligneideL(i.e, le coefficient`ij,j < i) (Étape i-a)puisla ligneideU(i.e les

coefficientuijpour toutji) (Étape i-b)).

Nous faisons l"hypothèse que les étapes précédentes (étapeskpourk < i) ont permis de calculer lesi1premières lignes

deLet lesi1premières lignes deU. On rappelle que l"equation(5)donne a ij=min(j;i)X k=1` ikukj:(10) Nous discutons deux cas, suivant la valeur demin(j;i): a-j < i(min(j;i) =j) : L"équation(10)devient a ij=jX k=1` ikukj:(11) On remarque que, commekj < i, les nombresukjsont connus. Pourj= 1, nous obtenons alorsai1=`i1u11ce qui nous permet de déterminer`i1par la formule i1=ai1u 11

i1étant déterminé, nous allons pouvoir déterminer`i2. En effet, l"équation(11)pourj= 2donne

a i2=`i1u12+`i2u22

Puisque les termesu12etu22(puisqueAest inversible etA=LU,u226= 0) ont été calculés lors d"étapes précédentes

et que`i1vient d"être calculé, la seule inconnue de l"équation précédente est`i2. On obtient alors

i2=ai2`i1u12u 22:

On peut ainsi continuer à déterminer`ijde proche en proche pour toutj < i. En effet, supposons`ikconnu pour

toutkj1. On peut réécrire l"équation(11)comme ij=a ijj1X k=1` ikukju jj(8ji1):(12)

Le terme de droite de l"équation précédente est connu : en effetukjest connu pour toutk < i(donc en particulier pour

kj). De même, les termes`iksont connus. De plus, on sait que puisqueAest inversible, l"hypothèse d"existence

de la factorisationA=LUgarantit queujj6= 0. Donc`ijest déterminé. A l"issue de cette étape i-a, les coefficients`ijpourj < isont déterminés. b-ji(min(j;i) =i) : l"équation L"équation(10)devient a ij=iX k=1` ikukj=i1X k=1` ikukj+`iiuij(13) 3 qui, comme`ii= 1donne u ij=aiji1X k=1` ikukj(8ji):(14)

Puisque les coefficientsukjpourki1ont été déterminés lors des étapes précédentes que les coefficients`ik

(ki) sont connus depuis l"étape i-a, le terme de droite de(14)est connu et l"équation(14)permet de construireuij

pour toutji.

Remarque.

1.

Dans le pr ocessusd"identification de l"étape i -a,il n"est pas possible d"intervertir les sous étapes : dans l"égalité (12), il

faut connaitre`ikpourkj1pour pouvoir calculer`ij. Il faut donc commencer par calculer`i1, puis`i2et ainsi de

suite jusqu à`i;i1. Par contre, la définition(14)deuijne fait pas appel àuikpourkj1. Les calculs(14)peuvent

donc être effectués en parallèle. 2. On aur aitaussi pu identifier les équations (5)colonnes par colonnes.

Méthode 2 : identification mixte

Cette seconde méthode est une méthode récurrente qui va permettre de calculer les coefficients deLetUennétapes : à

l"étapep, nous calculons a-

La lign enuméro pdeU, c"est à dire les coefficientsupjpourj2Jp;nK. Pour cela, nous utilisons la formule(10)avec

i=p. b-

La colonne numéro pdeL, c"est à dire les coefficients`ippouri2Jp;nK. Pour cela, nous utilisons la formule(10)

avecj=p.

Étape 1 :

a- On calcu lela ligne numéro 1deU, c"est à dire les coefficientsu1jpour toutj22J1;nK. Pour cela nous utilisons la formule(10)aveci= 1:8j2J1;nK a

1j=min(1;j)X

k=1`

1kukj=`11u1j=u1j

On a donc

u

1j=a1j8j2J1;nK:

b- On calc ulela colonne numéro 1deL, c"est à dire les coefficients`i1pour touti22J1;nK.

Tout d"abord, on pose

11= 1;

puis, nous utilisons la formule(10)aveci= 1:8i2J2;nK a i1=min(i;1)X k=1` ikuk1=`i1uk1

On en déduit que

i1=ai1u k18i2J2;nK:

Étape p :

À cette étape, on suppose que l"on connait lesp1premières colonnes deLet lesp1premières lignes deU. Plus

précisément, on suppose que les coefficients suivants sont connus : les co efficients`ijpour toutj2J1;p1Ket pour touti2J1;nK(ouJj;nK). les co efficientsuijpour touti2J1;p1Ket pour toutj2J1;nK(ouJi;nK).

On procède alors en deux étapes :

a- On calcu lela ligne numéro pdeU, c"est à dire les coefficientsupjpour toutj2Jp;nK. Pour cela nous utilisons la formule(10)aveci=p:8j2Jp;nK a pj=min(p;j)X k=1` pkukj=pX k=1` pkukj=p1X k=1` pkukj |{z} connu+upj: 4 Or, quel que soitk2J1;p1K,`pk(coefficient de la colonnekp1deL) etukj(coefficient de la lignekp1 deU) sont connus. On en déduit donc u pj=apjp1X k=1` pkukj(15) b- On calcul ela colonne numéro pdeL, c"est à dire les coefficients`ippour touti22Jp;nK.

Tout d"abord, on pose

pp= 1; puis, nous utilisons la formule(10)aveci=p:8i2Jp+ 1;nK a ip=min(i;p)X k=1` ikukp=pX k=1` ikukp=p1X k=1` ikukp+`ipupp Quel que soitk2J1;p1K,`ik(coefficient de la colonnekp1deL) etukp(coefficients de la lignekp1

deU) sont connus. Par ailleurs,uppest aussi désormais connu par la formule(15). On en déduit donc que

ip=a ipp1X k=1` ikukpu pp8i2Jp+ 1;nK:(16)

Remarque.Lors de l"étapep, il est possible de calculer les champsupjet`ipen parallèle. En revanche, il faut attendre queupp

soit calculé avant de pouvoir calculer les nombres`ip.

3. Algorithmes : nous proposons deux algorithmes. L"algorithme est basé sur une identification par lignes, alors que l"algo-

rithme est basé sur une identification mixte. 5 FonctionFACTLU(A) :L,U[Aest une matrice carrée (inversible), , Uest un matrice carrée triangulaire supérieure Lest une matrice trianguaire inferieure à diagonale unité

Ce programme calcule la décompositionLUdeA

par identification par lignes][Quelques initialisations]U zeros(size(A));L zeros(size(A));[On initialise les matricesUetLpar la matrice nulle]

Pouride1ànfaire[1- On calcule la ligneideL(`ij,j < i)(formule(12)) ] Pourjde1ài1faireL(i;j) A(i;j)Pourkde1àj1faireL(i;j) L(i;j)L(i;k)U(k;j);

Fin PourL(i;j) L(i;j)=U(j;j);Fin Pour

[2- On pose`ii= 1] L(i;i) 1[3- On calcule la ligneideU(uij,ji)(formule(14))] PourjdeiànfaireU(i;j) A(i;j);Pourkde1ài1faireU(i;j) U(i;j)L(i;k)U(k;j)

Fin Pour

Fin Pour

Fin Pour

RetournerL,U;

FinAlgorithme 1:Algorithme pour la factorisationLU Remarque.On pourrait ne stocker qu"un tableauAet remplacer les valeurs deApar celles deLetU. 6 FonctionFACTLUM(A) :L,U[Aest une matrice carrée (inversible) , Uest un matrice carrée triangulaire supérieure Lest une matrice triangulaire inférieure à diagonale unité

Ce programme calcule la décompositionLUdeA

par identification mixte][Quelques initialisations]U zeros(size(A));L zeros(size(A));[On initialise les matricesUetLpar la matrice nulle]

Pourpde1ànfaire[1- On calcule la lignepdeU:(upj,j2Jp;nK) (formule(15))] PourjdepànfaireU(p;j) A(p;j)Pourkde1àp1faireU(p;j) U(p;j)L(p;k)U(k;j)

Fin Pour

Fin Pour

[2- On calcule la colonnepdeL:(`ip,i2Jp;nK) (formule(16))] L(p;p) 1Pouridep+ 1ànfaireL(i;p) A(i;p)Pourkde1àp1faireL(i;p) L(i;p)L(i;k)U(k;p)

Fin Pour

L(i;p) L(i;p)=U(p;p)

Fin Pour

Fin Pour

RetournerL,U;

FinAlgorithme 2:Algorithme pour la factorisationLUpar identification mixte

4. Coût de la factorisationLU.

Identification par lignes

On évalue d"abord le coût pour l"identification chaque ligne. On pose -N+ i: nombre d"additions ou de soustractions intervenant dans le caclul de la ligneideLetU. -Ni: nombre de multiplications ou de divisions intervenant dans le caclul de la ligneideLetU. En étudiant l"algorithme de la question 3, on voit quecolonneN i;jN i;jj < ij1j jii1i1Donc N i=n1X j=1N i;j=i1X j=1j |{z} somme de suite arithmétique+ nX j=i(i1)|{z} independant dej (i1)=iz}|{ (1 + (i1))2 + (ni+ 1)(i1) =i22 +i2 + (n+ 1)(i1): 7

De même,

N i=i1X j=1(j1) +nX j=1(i1) (i1)(i2)2 + (ni+ 1)(i1) =Ni(i1):

On calcule ensuite le nombre total d"additionsN+et de multilplicationsNen effectuant la somme sur les lignes pouri

allant de1àn. On anX j=1i

2=n(n+ 1)(2n+ 1)6

Donc nX j=1(i22 +i2 ) =n(n+ 1)(2n+ 1)12 +n(n+ 1)4 =n(n+ 1)(n1)6

De plus,

nX i=1(n+ 1)(i1) = (n+ 1)n1X i=0i=n(n+ 1)(n1)2

Finalement

N =n(n+ 1)(n1)2 n(n+ 1)(n1)6 =n(n+ 1)(n1)3

De même,

N +=nX i=1N i=nX i=1N inX i=1(i1) |{z} =n(n1)=2; n(n+ 1)(n1)3 n(n1)2 n(n1)6 (2(n+ 1)3); n(n1)(2n1)6 Le nombre total d"opérationsNtotal=N++Nest donc donné par N total=n(n1)(2n1)6 +n(n+ 1)(n1)3 n(n1)(4n1)6 Quandnest grand le coût total de la factorisationLUest donc de l"ordre de2n33 . Pour résoudre le systèmeAx=LUx=b (cf exercice 1) est donc de 2n33 +O(n2)2n33

Identification mixte

On pose

1.N+p: nombre d"additions et de soustractions intervenant lors du calcul de la lignepdeUet de la colonnepdeL.

2.Np: nombre de multilplications et de divisions intervenant lors du calcul de la lignepdeUet de la colonnepdeL.

On a N +p=N+ p;U+N+ p;L oùN+ p;U(resp.N+ p;L) désigne le nombre d"additions et de soustractions intervenant lors du calcul de la lignepdeU (resp. colonnepdeL). Or, N p;U=nX j=pN p;U;j 8 oùN+ p;U;jdésigne le nombre d"additions et de soustractions intervenant lors du calcul de deupj. On a N p;U;j=p Donc N p;U=p(np+ 1)

De manière similaire, on trouve

N p;L=p(np+ 1) ce qui donne N +p= 2p(np+ 1)

En sommant surp, on trouve donc

N +=nX p=12p(np+ 1) =n(n+ 1)(n+ 2)3

De manière similaire,

N n33 et on retrouve le meme nombre d"opérations que dans le cas de l"identification par lignes.

Remarque.Même si les deux algorithmes conduisent à un nombre similaire de calculs, l"algorithme par indentification

mixte se révèle avantageux dans le cas d"une implémentation parallèle.

5. Non, même quand la matriceAest inversible, on ne peut pas toujours la décomposer sous la formeA=LUn"est pas

toujours possible. En effet, siujj= 0, on ne peut pas appliquer l"algorithme (puisqu"il faudrait diviser par0).

Une condition suffisante pour cette factorisation existe est que les mineurs principaux deAsoient tous non nuls. On rappelle

que le mineur principal deAd"ordreiest le déterminant de la matrice formée par laipremières colonnes etipremières lignes

deA. Par contre, on peut toujours permuter des lignes pour obtenir une décomposition de typePA=LU.

Remarque.En général, si on souhaite résoudre simplementAx=b, on ne calculer pas explicitementLetUmais on effectue

directement le procédé d"élimination de Gauss. Par contre, si on a besoin de résoudre une famille de systèmesAx=bi(pour

différents second membresbi), alors il devient utile de calculer les matricesLetU. 9quotesdbs_dbs15.pdfusesText_21