ASI 3

Méthodes numériquespour l’ingénieur

Résolution de systèmes linéaires par des méthodes directes :

Gauss, LU,

Ax=b : un cas simpleA est une matrice diagonale

nia

bx

ii

ii ,1 ,

n

i

n

i

nn

ii

b

b

b

x

x

x

a

a

a

1111

000

00

0000

00

000

fait

àjusqu' 1pour

ii

ii a

bx

ni

Fonction x = diago(A,b)

problème

solution

Algorithme

A est de forme triangulaire

1

1

1

1

11

i

jjiji

iii xab

ax

ab

x

n

i

n

i

nnnin

iii

b

b

b

x

x

x

aaa

aa

a

11

1

1

11

0

00

0

000

fait

omme

fait ommeomme

1 àjusqu' 1pour

omme

àjusqu' 2pour

11

11

iii

jij

i

as

x

xassij

bs

ni

ab

x

ommes

Fonction x = triang(A,b)

Commentaires sur le programme « diago »

• Complexité ?

• Déterminant :

• que se passe t’il si A est triangulaire supérieure ?

• Exercice :

n

iiiaA

1)det(

Quels sont les âges d’Alice, de Louis, Sacha et Gaspar ?Sachant que trois fois la somme des âges des garçons est égale à la somme des âges des filles, que  l’âge d’Alice moins trois fois la somme des âges de Louis et de Sacha est égal à moins neuf, que trois fois l’âge de Louis est égal à vingt sept, et que l’âge de Louis moins deux fois  l’âge de Sacha est égal à 3.

Pivot de Gauss4 principes fondamentaux

On ne change pas la solution lorsque l’on :

1. permute 2 lignes

2. permute 2 colonnes

3. divise par un même terme non nul les éléments d’une ligne

4. ajoute ou retranche à une ligne un certain nombre de fois une autre ligne

Stratégie : Transformer le système linéaire en un système équivalent … facile à résoudre

Triangulaire !

Pivot de Gauss : un exemple

6 2

8 2 3

0 3

6242

432

4321

421

321

xxx

xxxx

xxx

xxx

pivot (1)

Pivot de Gauss : un exemple

6 2

8 2 3

0 3

6242

432

4321

421

321

xxx

xxxx

xxx

xxx

(2) = (2)-a21/pivot (1)

Pivot de Gauss : un exemple

6 2

8 2 3

0 3

6242

432

4321

421

321

xxx

xxxx

xxx

xxx

6 2

8 2 3

3 0

6242

432

4321

432

321

xxx

xxxx

xxx

xxx

(2) = (2)-a21/pivot (1)

Pivot de Gauss : un exemple

6 2

8 2 3

0 3

6242

432

4321

421

321

xxx

xxxx

xxx

xxx

6 2

71 2 4 7 0

3 0

6242

432

432

432

321

xxx

xxx

xxx

xxx

(3) = (3)-a31/pivot (1)

Le première variable à été éliminée de toutes les équations sauf une

1. Triangularisation

2. Résolution du système triangulaire

L’algorithme du pivot de Gauss

A x = b

fait problème""sinon fait

fait

àjusqu' 1pour

àjusqu' 1pour

alors 0 si

*)pivot de stratégie (*

1 àjusqu' 1pour

kjik

ijij

kik

ii

kk

apivot

aaa

nkj

bpivot

abb

nki

pivot

apivot

nk

Fonction A,b = descent(A,b)

Gauss : résolution d’un système triangulaire

1

1

n

ijjiji

iii

n

nn

xaba

x

a

bx

n

i

n

i

nn

inii

ni

b

b

b

x

x

x

a

aa

aaa

111111

000

0

00

0

fait

omme

fait ommeomme

àjusqu' 1pour

omme

1 àjusqu' 1pour

iii

jij

i

nn

nn

as

x

xassnij

bs

ni

a

bx

ommes

Fonction x = triang(A,b)

Gauss

U,c = descent(A,b)

x = triang(U,c)

Fonction x = Gauss(A,b)

RemarquesChoix du pivot : minimiser les erreurs d’arrondis si un pivot est nul, on permute deux lignes si tous les pivots restant sont nuls la matrice est singulière (i.e. le système d’équations n’admet pas de solution unique)

pour minimiser les erreurs d’arrondis : on choisi le plus grand pivot possible (en valeur absolue) et donc on permute les lignes (voir les colonnes associées) c’est la stratégie du pivot maximal (partiel (lignes) ou total)

Comment inverser une matrice ? Avec l’algorithme de gauss on peu résoudre directement

déterminant d’une matrice = produit des pivots

IAAcbAzcAybAx

1 : doncet ; et

Exemple

2

1

11

110 4

x

Trouver x en ne gardant que 4 chiffres significatifs après la virgule

44

44

102

1

1010

110 ,10: xpivot

edddd 10 .0 :tionreprésenta

1

0

10

1

100

11044

4

xx

Que se passe t’il si on prend le système à l’envers...

Exemple

2

1

11

110 4

x

Trouver x en ne gardant que 4 chiffres significatifs après la virgule

44

44

102

1

1010

110 ,10: xpivot

edddd 10 .0 :tionreprésenta

1

0

10

1

100

11044

4

xx

Que se passe t’il si on prend le système à l’envers...

; ; :ement matriciell

,...,1pour

,...,1pour

)()()1()()()1(

)()(

)()()1(

)()(

)()()1(

kkkkkk

kkk

kk

kikk

ik

i

kkjk

kk

kikk

ijk

ij

bMbAMA

ba

abb

nkjaa

aaa

nki

Représentation matricielle de l’élimination de Gauss

LcbLUA

LcUxbAx

et

: que telle matrice la rechercheon

A chaque étape de l’algorithme...

Les cas du second membre b

; :ement matriciell )()()1(

)()(

)()()1(

)()(

)()()1(

)()(

)(,1)(

1)1(

1

)()1(

)(1

)1(1

kkk

kkk

kk

knkk

nk

n

kkk

kk

kikk

ik

i

kkk

kk

kkkk

kk

k

kk

kk

kk

bMb

ba

abb

ba

abb

ba

abb

bb

bb

1000

0

100

0010

0001

;

,

,1

)(

kn

kk

k

kk

ikik

m

m

M

a

am

M (k) ?

Les cas du second membre b

; :ement matriciell )()()1(

)()(

)()()1(

)()(

)()()1(

)()(

)(,1)(

1)1(

1

)()1(

)(1

)1(1

kkk

kkk

kk

knkk

nk

n

kkk

kk

kikk

ik

i

kkk

kk

kkkk

kk

k

kk

kk

kk

bMb

ba

abb

ba

abb

ba

abb

bb

bb

1000

0

100

0010

0001

;

,

,1

)(

kn

kk

k

kk

ikik

m

m

M

a

am

Factorisation

1000

0

100

0010

0001

;

; ; :ement matriciell

,

,1

)(

)()()1()()()1(

kn

kk

k

kk

ikik

kkkkkk

m

m

Ma

am

bMbAMA

LUAML

UMAAM

AMMMMAMM

AMAU

M

nn

nnn

nnn

aon posant en

...

1

1

)1()2()2()1(

)2()2()1(

)1()1()(

LU : motivation

On connaît la matrice A

on ne connaît pas encore b

comment « préparer A » ?

LU : principeIl est si facile le résoudre un système « triangulaire » !

)2(

)1(

yUx

bLybAx

LUA

L

U

A0

0Comment construire Let U ?

idée : reprendre l’étape de triangularisation de la méthode de Gauss

De Gauss à LU

UAAAAMA nkkk )()1()()()1( et

Représentons une étape de la triangularisation par la multiplication de A par une matrice M(k)

kjkk

ikijij

kkk

ikii

aa

aaa

ba

abb

100

0100

0

001

,

,1

)(

,,

kn

kk

k

kikk

ikki

M

ma

a

1

1

)1()()1(

donc

......

ML

LUUMA

MAAMMMU kn

gauss

LU : la décompositionLes matrices élémentaires M(k) sont inversibles et leurs inverses sont les matrices L(k) triangulaires inférieurestelles que :

,n kil

nil

l

L

ikik

ii

ijk

1 sauf

,1 1 sauf

0 )(

IMIL kk )()(

100

0100

0

001

,

,1

)(

kn

kk

kM

100

0100

0

001

,

,1

)(

kn

kk

kL

)1()()1( ...... LLLL kn C’est la matrice lik

L’algorithme de décomposition

fait problème""sinon fait

fait

àjusqu' 1pour

àjusqu' 1pour 1

alors 0 si

*)pivot de stratégie (*

1 àjusqu' 1pour

kjikijij

ikik

kk

kk

aaankj

pivot

anki

pivot

apivot

nk

Fonction L,U = décompose(A)

Exemple

2

1

2

1

12

121

11

12

1

111

122

121

Montrez que :

LU : l’algorithme

L,U = decompose(A)

y = triang(L,b)

x = triang(U,y)

Fonction x = LU(A,b)

A=LU

n

ii

n

iiiuUULLUA

11pivot)det()det()det()det()det(

Théorème : Si au cours de l’élimination de Gauss sur la matrice A, les pivots sont non nuls,

alors il existe une matrice triangulaire inférieure L et une matrice triangulaire supérieure U, telle que :

A = LUsi de plus on impose à L d’avoir les éléments diagonaux égaux à un alors la factorisation est unique

LUUMA

MAAMMMU kn

1

)1()()1(

......Démonstration : (éléments)

unicité : par l’absurde

Remarque : (déterminent)

A=LUThéorème : Si au cours de l’élimination de Gauss sur la matrice A, les pivots sont non nuls,

alors il existe une matrice triangulaire inférieure L et une matrice triangulaire supérieure U, telle que :

A = LUsi de plus on impose à L d’avoir les éléments diagonaux égaux à un alors la factorisation est unique

11

20A

Contre exemple trivial :

Réorganisation du système linéaire : permutation des lignes et des colonnes

RECHERCHE DU MEILLEUR PIVOT

La factorisation PA=LU

Définition : Si la matrice A, est non singulière alors il existe une matrice de permutation P telle que les pivots de PA sont non nuls. (TL chapitre 4)

)2(

)1(

yUx

PbLybAx

LUPAL,U,P = decompose(A)

y = triang(L,P*b)

x = triang(U,y)

Fonction x = LU(A,b)

Si est égal à zéro,on échange (permute) deux lignes

kka

Matlab !

PA=LU : étape k

UAAAAPMA

Ankkkk

k

)()1()()()()1(

)(

et avec

matrice la permuteon étape chaqueAvant

Théorème : Si la matrice P (k), est la matrice de permutation des colonnes p et q

alors

10000

0

1

00

1

10

00

0001

~

1000

0

1

10

0

001avec ~ encoreou

~~ ;

)()(

)()()()(

)()()()(

a

bL

b

aL

LPPLPLPLki

ii

ikki

kiki

q

p

k

PA=LU

ULPA

ULPA

PPLPPL

ULLLPPPULPLPLPA

APMPMPMAU

APMA

A

kkk

nknk

nnkk

kknnn

kkkk

k

~et

~ :oud'

~posant en

~~~

: algorithmel'pour tout soit

matrice la permuteon étape chaqueAvant

)1()()()()1(

)1()()1()1()()1(

)1()1()()()1()1(

)1()1()()()1()1()(

)()()()1(

)(

A expliquer !

• Si on a pas besoin de permutation : – on peut faire plus « efficace »

• sinon– pivot partiel :

permutation de colonnes

– pivot total : permutation de ligne et de colonnes (plus cher)

• préconditionnement ou Equilibrage d’un système linéaire– Modifier le système d’équations pour diminuer les risques

d’erreurs

• Amélioration itérative

Choix du pivot

~ alors ~~

~ ; \ ; \

rrxAbr

exxrAeAxbrbAx