Giansalvo EXIN Cirrincione unité #3 rappels grand O Définition : la fonction T(n) est dite « grand O » de f(n) que lon note T(n)= O (f(n)), sil existe

Giansalvo EXIN CirrincioneGiansalvo EXIN Cirrincione

unité #3unité #3

rappelsrappels

Définition : la fonction T(n) est dite « grand grand OO » de f(n) que l’on

note T(n)=O(f(n)), s’il existe deux constantes C et n0

telles que 0 ( ) ( )n n T n C f n

32 132493log14 xxxx O

Problème : fonction f : X Y de l’espace vectoriel normé

X des entrées à l’espace vectoriel normé Y des solutions.

Algorithme :f X Y

Axiom fondamental de l’arithmétique en virgule flottante

, , avec telle que 1machinex y F x y x y

rappelsrappels

Problème : fonction f : X Y de l’espace vectoriel normé

X des entrées à l’espace vectoriel normé Y des solutions.

Algorithme :f X Y

Stabilité d’un algorithmeStabilité d’un algorithme

est stable si , telle que

machine

machine

f x X x

f x f xO

f x

x xO

x

A stable algorithm gives nearly the right A stable algorithm gives nearly the right answer to nearly the right question.answer to nearly the right question.

rappelsrappels

Stabilité d’un algorithmeStabilité d’un algorithme

est stable si , telle que

machine

machine

f x X x

f x f xO

f x

x xO

x

A stable algorithm gives nearly the right A stable algorithm gives nearly the right answer to nearly the right question.answer to nearly the right question.

x

x f

f fx

rappelsrappels

Stabilité Stabilité backwardbackward d’un algorithme d’un algorithme

est stable backward si , telle que

machine

f x X

f x f x

xO

x

x

x

A backward stable algorithm gives exactly the right A backward stable algorithm gives exactly the right answer to nearly the right question.answer to nearly the right question.

x

x f

f fx fx

xx f

f

fxfx

Résolution de systèmes linéairesRésolution de systèmes linéaires

x

1 21

, ,

range span , , ,

rang rang

m n m n

n

j j nj

A b x

a x b b A a

A b

a a

Ax b

A Théorème de Théorème de Rouché-CapelliRouché-Capelli

La solution d’un système linéaire (A carrée inversible n x n) ne s’obtient pas en calculant l’inverse de A. Le calcul de A-1 est équivalent à la résolution des n systèmes linéaires :

1j jAu e j n

où uj est le j-ème vecteur de la base de Kn.

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

4 principes fondamentaux4 principes fondamentaux

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

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

triangulaire !triangulaire !


Algorithme

fait

àjusqu' 1pour

ii

ii a

bx

ni

Fonction x = diago(A,b)

11 11 0 0 0

0 0

0 0 0 0

0 0

0 0 0

i i

n n

ii

nn

a

a

bx

x b

x ba

problèmeproblème

nia

bx

ii

ii ,1 ,

solution

AA matrice diagonale matrice diagonale


A triangulaire inférieureproblèmeproblème

11

1

1

1

10 0 0

0

0 0

0

i ii

n ni nn

i

n

i

n

bx

x b

x b

a

a a

a a a

1

1

1

1

11

i

jjiji

iii xab

ax

ab

x

ommes

solution

Algorithme

Fonction x = trianginf(A,b)

fait

omme

fait ommeomme

1 àjusqu' 1pour

omme

àjusqu' 2pour

11

11

iii

jij

i

as

x

xassij

bs

ni

ab

x


A triangulaire inférieureproblèmeproblème

11

1

1

1

10 0 0

0

0 0

0

i ii

n ni nn

i

n

i

n

bx

x b

x b

a

a a

a a a

1

1

1

1

11

i

jjiji

iii xab

ax

ab

x

ommes

solution 2 flopsO n 2 flopsO n

1

det( )n

iii

A a


A triangulaire supérieureproblèmeproblème11 1 111

0

0 0

0

0 0 0

i

i n

ii i

n

n

n nn

i

bx

x b

x b

a a a

a a

a

solution

1

1

n

ijjiji

iii

n

nn

xaba

x

a

bx

ommes

Algorithme

Fonction x = triang(A,b)

fait

omme

fait ommeomme

àjusqu' 1pour

omme

1 àjusqu' 1pour

iii

jij

i

nn

nn

as

x

xassnij

bs

ni

a

bx

2 flopsO n 2 flopsO n


A triangulaire supérieureproblèmeproblème11 1 111

0

0 0

0

0 0 0

i

i n

ii i

n

n

n nn

i

bx

x b

x b

a a a

a a

a

solution

1

1

n

ijjiji

iii

n

nn

xaba

x

a

bx

ommes

Chaque composante xi apparaissant comme une fonction linéaire de bi , bi+1 , … , bn , ceci montre que l’inverse d’une matrice triangulaire est une matrice triangulaire du même type.

Méthode de remontée

x et triangulaire supérieure telle

BACKWARD S

s que

TABLE

n n

machine

n

A A x b

AO

A

x A

La méthode de GaussLa méthode de Gauss

AuAu = = bb , , AA : matrice inversible : matrice inversible

I.I. Une procédure d’Une procédure d’éliminationélimination qui équivaut à déterminer une qui équivaut à déterminer une matrice inversible matrice inversible MM telle que telle que M AM A soit triangulaire supérieure. soit triangulaire supérieure.

II.II. On calcule simultanément le vecteur On calcule simultanément le vecteur M bM b..III.III. On résout le système linéaire On résout le système linéaire M A uM A u = = M b M b

par lapar la méthode de la méthode de la remontéeremontée..

En pratique, on ne calcule pas explicitement la matrice En pratique, on ne calcule pas explicitement la matrice MM, mais seulement la matrice , mais seulement la matrice M AM A et le vecteur et le vecteur M bM b. .

6 2

8 2 3

0 3

6242

432

4321

421

321

xxx

xxxx

xxx

xxx


exempleexemple

pivot (1)

6 2

8 2 3

0 3

6242

432

4321

421

321

xxx

xxxx

xxx

xxx

(2) = (2) - (a(2) = (2) - (a2121/pivot(1)) (1)/pivot(1)) (1)


exempleexemple

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


exempleexemple

(2) = (2) - (a(2) = (2) - (a2121/pivot(1)) (1)/pivot(1)) (1)

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

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


exempleexemple

(3) = (3) - (a(3) = (3) - (a3131/pivot(1)) (1)/pivot(1)) (1)


exempleexemple

pivot (2)

6 2

71 2 4 7 0

3 0

6242

432

432

432

321

xxx

xxx

xxx

xxx

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 Fonction A,bA,b = descent ( = descent (A,bA,b))

TriangularisationTriangularisation



U, c = descent (A,b)

x = triang (U,c)

Fonction Fonction xx = Gauss( = Gauss( A,b A,b ) )

La méthode de GaussLa méthode de GaussPremière étape de l’éliminationPremière étape de l’éliminationL’un au moins des éléments de la première colonne est différent de zéro, sans quoi la matrice serait singulière. On choisit alors l’un des coefficients non nuls (premier pivotpremier pivot) de la première colonne de A. Ensuite, on échange la ligne du pivot avec la première ligne, ce qui revient à multiplier A à gauche par une matrice de permutation matrice de permutation PP. Pour l’échange des i-ème et j-ème lignes, on multiplie à gauche par la matrice P suivante.

1

1

1

1

0 1

1

1

1

1

1 0

i jP P

11

det 1

si est le pivot

P

P I a

ii

jj

ii jj

1ij ijP P

La méthode de GaussLa méthode de GaussPremière étape de l’éliminationPremière étape de l’éliminationL’un au moins des éléments de la première colonne est différent de zéro, sans quoi la matrice serait singulière. On choisit alors l’un des coefficients non nuls (premier pivotpremier pivot) de la première colonne de A. Ensuite, on échange la ligne du pivot avec la première ligne, ce qui revient à multiplier A à gauche par une matrice de permutation matrice de permutation PP. Pour l’échange des i-ème et j-ème lignes, on multiplie à gauche par la matrice P suivante.

1ij ijP P

La méthode de GaussLa méthode de GaussPremière étape de l’éliminationPremière étape de l’élimination

11 avec 0ijPA

Par des combinaisons linéaires appropriées de la première ligne et des autres lignes de la matrice PA, on annule tous les éléments de la première colonne de PA situés sous la diagonale, la première ligne restant inchangée.

B EPA

det 1

det det det det det

est inversible

E

B E P A A

B

La méthode de GaussLa méthode de GaussSeconde étape de l’éliminationSeconde étape de l’éliminationElle consiste à effectuer les mêmes opérations que précédemment, mais seulement sur la sous-matrice ( bij ) , 2 i, j n , en laissant inchangée la première ligne, et ainsi de suite …

( ( kk--1 1 )-ème étape de l’élimination ()-ème étape de l’élimination (22 kk nn )

1 1 2 2 1 1 1k k kA E P E P E P A

La méthode de GaussLa méthode de Gausskk-ème étape de l’élimination (-ème étape de l’élimination (22 k k nn )

det det est inversible 0 , pivotkk k i kA A A a k i n

avec 0k kk k i j k kP A

1k k k kA E P A


( ( nn--1 1 )-ème étape de l’élimination)-ème étape de l’élimination

1 1 2 2 1 1 triangulaire supérieuren n nA E P E P E P A

1 1 2 2 1 1 inversible n nM E P E P E P

-ème pivotnnn n n n

A n


La méthode de GaussLa méthode de Gaussexempleexemple

4 110 1

21 1x

Trouver Trouver xx en ne gardant en ne gardant que que 33 chiffres significatifs chiffres significatifs après la virguleaprès la virgule

représentation: 0. 10eddd

1.00010... 1

0.99990... 1exactex

pivotpivot

44

4

2 101 1

110

0 0

1x

4

44 1

110 01

0 1 100x x

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

La méthode de GaussLa méthode de Gaussexempleexemple

4 110 1

21 1x

Trouver Trouver xx en ne gardant en ne gardant que que 33 chiffres significatifs chiffres significatifs après la virguleaprès la virgule

représentation: 0. 10eddd

1.00010... 1

0.99990... 1exactex

4

1 1 2

10 1 1x

pivotpivot

4 41 10

1 1

00 1 2 1

2x

1 2

0 1

1 1

11xx

effet de la division par un pivot trop petiteffet de la division par un pivot trop petit

Gaussian elimination Gaussian elimination without pivotingwithout pivoting is is neither backward stable neither backward stable nor stablenor stable. Additionally, the triangular matrices it generates have . Additionally, the triangular matrices it generates have condition numbers that may be arbitrarily greater than those of A condition numbers that may be arbitrarily greater than those of A itself, leading to additional sources of instability in the forward itself, leading to additional sources of instability in the forward and back substitution phases of the solution of and back substitution phases of the solution of A xA x = = bb . .

si un pivot est nul, on permute deux lignessi un pivot est nul, on permute deux lignes si tous les pivots restant sont nuls, la matrice est singulièresi tous les pivots restant sont nuls, la matrice est singulière (i.e. le système d’équations n’admet pas de solution unique) stratégie pour minimiser les erreurs d’arrondis.stratégie 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)

Choix du pivotChoix du pivot


kk-ème étape de l’élimination (-ème étape de l’élimination (22 k k nn )

Stratégie du pivot partielStratégie du pivot partiel

Le pivot est l'un des éléments , , vérifiant

maxk krk ik

k

k

kr

i n

a k r

a

n

a

O( n2 ) flops


kk-ème étape de l’élimination (-ème étape de l’élimination (22 k k nn )

Stratégie du pivot totalStratégie du pivot total

,

Le pivot est l'un des éléments , , , vérifiant

maxk krs ik

k i j n

krka k r s n

a a

O( n3 ) flops

Il faut aussi effectuer Il faut aussi effectuer un un échange de échange de colonnescolonnes qui equivaut qui equivaut a multiplier la a multiplier la matrice matrice AAkk à droiteà droite

par une matrice de par une matrice de permutation.permutation.

FLOPSFLOPS

32 flops

3O n

FLOPSFLOPS

32 flops

3O n

Formules de CramerFormules de CramerFormules de CramerFormules de Cramer

111 1, 1 1, 1 1

21 2, 1 2, 1 2

, 1 ,

2

1 1

det

det ,

i i n

i i ni

n n i n i

ii

n nn

a a a a

a a a aB

a a a

Bx

A

b

b

ab

1 ! additions

2 ! multiplications

divisions

n

n

n

Pour n = 10 par exemple, on obtient environ :Pour n = 10 par exemple, on obtient environ :• 700 opérations pour Gauss700 opérations pour Gauss• 400 000 000 opérations pour Cramer !400 000 000 opérations pour Cramer !

Pour n = 10 par exemple, on obtient environ :Pour n = 10 par exemple, on obtient environ :• 700 opérations pour Gauss700 opérations pour Gauss• 400 000 000 opérations pour Cramer !400 000 000 opérations pour Cramer !

Gauss-JordanGauss-Jordan

Gauss-JordanGauss-Jordan

La méthode de Gauss-Jordan est utilisée pour le calcul de l’inverse d’une matrice donnée : on résout simultanément les n systèmes linéaires :

La méthode de Gauss-Jordan est utilisée pour le calcul de l’inverse d’une matrice donnée : on résout simultanément les n systèmes linéaires :

, 1j jAu e j n

, 1n j jA u Me j n

diagonalediagonale

La factorisation LU d’une matriceLa factorisation LU d’une matrice

1 1 2 2 1 1 triangulaire supérieuren n nA E P E P E P A 1 1 111 12 1

2 222 2

n

n

n

n

nn

a a a

a a

a

U A

1

,

,

,

1

1 , 1

1

1

1kik

k k

n k

k kk

k

ik

E k

a

n

k i na

1,

,

0

0k

k k

n k

*

*

*

* * *

1 *

0k k

k k k k

k k k

k

k k k k

k k

e

I e I e I e e I

E I e

E I e

1,

,

1

1

1

1

1

k k

n k

kE



1,

,

1

1

1

1

1

k k

n k

kE

11 2 1 2 1n nE E E PU AP P

1 11 1 1 1knk k k nEP P P PE

permutations seulement sur k

1

1,

,

1

1

1

1

k k

n k

kE



11 2 1 2 1n nE E E PU AP P

1,

,

0

0k

k k

n k

1 1 *

*

*1 1

*

1 *

1

* *1 11

0

k k k k

k k

k k k

k k

k

k

k k k

kk

e

E I e

E I e

E E I e eI e I e

1

1,

,

1

1

1

1

k k

n k

kE

21

31 3

1 1 1 11 2 1 2

1 2

2

1

1

,

1

1

1

1

1n n n n

n nL E E E E E E

1 2 1nP P P P PA LU


PA LU

, : , :

,1: 1 ,1: 1

,: ,:

, ,

for 1 to 1

select to maximize (* stratégie du pivot partiel

p

*)

(* *)

ermutationik

k k n i k n

k k i k

k i

U A L I P I

k n

i k u

u u

p p

, : , : , :

for 1 to

jkj k

kk

j k n j k n j k k k n

j k n

u

u

u u u

Fonction P,L,U = décompose (A)


1 1 2 2 1 1 triangulaire supérieuren n nA E P E P E P A 1 1 111 12 1

2 222 2

n

n

n

n

nn

a a a

a a

a

U A

1

,

,

,

1

1 , 1

1

1

1kik

k k

n k

k kk

k

ik

E k

a

n

k i na

1,

,

0

0k

k k

n k

*

*

*

* * *

1 *

0k k

k k k k

k k k

k

k k k k

k k

e

I e I e I e e I

E I e

E I e

1,

,

1

1

1

1

1

k k

n k

kE



1,

,

1

1

1

1

1

k k

n k

kE

11 2 1 2 1n nE E E PU AP P

1 11 1 1 1knk k k nEP P P PE

permutations seulement sur k

1

1,

,

1

1

1

1

k k

n k

kE



11 2 1 2 1n nE E E PU AP P

1,

,

0

0k

k k

n k

1 1 *

*

*1 1

*

1 *

1

* *1 11

0

k k k k

k k

k k k

k k

k

k

k k k

kk

e

E I e

E I e

E E I e eI e I e

1

1,

,

1

1

1

1

k k

n k

kE

21

31 3

1 1 1 11 2 1 2

1 2

2

1

1

,

1

1

1

1

1n n n n

n nL E E E E E E

1 2 1nP P P P PA LU


PA LU

, : , :

,1: 1 ,1: 1

,: ,:

, ,

for 1 to 1

select to maximize (* stratégie du pivot partiel

p

*)

(* *)

ermutationik

k k n i k n

k k i k

k i

U A L I P I

k n

i k u

u u

p p

, : , : , :

for 1 to

jkj k

kk

j k n j k n j k k k n

j k n

u

u

u u u

Fonction P,L,U = décompose (A)


PA LU

Ax b PA x Pb LU x PLy Pb

Ux yb

LL

00

00

UUAAPP ==

P,L,UP,L,U = décompose ( = décompose (AA))

yy = triang ( = triang (L, P*bL, P*b) )

xx = triang ( = triang (U, yU, y) )

Fonction Fonction xx = LU( = LU(A,bA,b) )

P = 1P = 1A LU

11 1

1

, 1k

k

k kk

a a

k n

a a

Soit Soit AA = ( = ( aaij ij ) une matrice ) une matrice

carrée d’ordre carrée d’ordre nn telle que les telle que les n n sous-matrices diagonalessous-matrices diagonales

soient soient inversiblesinversibles. Alors il . Alors il existeexiste une matrice triangulaire inférieure une matrice triangulaire inférieure LL et une matrice triangulaire et une matrice triangulaire supérieure supérieure U U telles que telles que AA = = LL UU . . De plus, une telle factorisation est De plus, une telle factorisation est uniqueunique..

P = 1P = 1A LU

Matrices spécialesMatrices spéciales((pas de stratégie de pivoting dans la factorisation LUpas de stratégie de pivoting dans la factorisation LU) )

1

1, ,n

ii ijjj i

a a i n

AA est diagonalement est diagonalement dominantedominante

1

0 , 1, , ,

0 , 1, ,

i j

i j

a i j n i j

A i j n

AA est une est une

MM-matrice-matrice

AA est une matrice symétrique définie positive est une matrice symétrique définie positive

Stabilité de la factorisation Stabilité de la factorisation LULU

Let the factorization P A = L U of a matrix A be computed by Gaussian elimination with partial pivoting. Then the computed matrices P, L and U satisfy :

~ ~ ~

, machine

ALU PA A O

L U

backward stable

backward unst

Gaussian elimination is

Gaussian elimination ei abls

L U O A

L U O A

For Gaussian elimination without pivoting, both L and U can be unboundedly large.

Pivoting, ensures that L and U are not too large.

1L O

backward

stable

U O A


For Gaussian elimination without pivoting, both L and U can be unboundedly large.

Pivoting, ensures that L and U are not too large.

1L O

backward

stable

U O A

, machine

ALU PA A O

L U

,

,

max

max

growth factor

iji j

iji j

u

a

U O A

,

if there are no ties in the pivot selection

machine

ALU PA A O

P

A

P


,

,

max

max

growth factor

iji j

iji j

u

a

,


machine

ALU PA A O

P

A

P

3 23

1machine

x An n

AxA

A

1

0.25ln

définie positive

stratégie du pivot partiel

stratégie du pivot tot

1

2

1.8 al

n

nn

A


,

,

max

max

growth factor

iji j

iji j

u

a

,


machine

ALU PA A O

P

A

P

3 23

1machine

x An n

AxA

A

1

0.25ln

définie positive

stratégie du pivot partiel

stratégie du pivot tot

1

2

1.8 al

n

nn

A

Gauss elimination is backward stablebackward stable if = = OO((11)) uniformly for all matrices of a given dimension n


,

,

max

max

growth factor

iji j

iji j

u

a

exempleexemple 1 0 0 0 1 1 0 0 0

1 1 0 0 1 0 1 0 0

1 1 1 0 1 0 0 1 0

1 1 1 1 1 0 0 0 1

1 1 1 1 1 0 0

1

2

4

8

10 60

A U

1 1

1 1 1

1 1 1 1

1 1 1 1 1

1 1 1 1

1 1

1 1 1

1 1 1 1

1 1 1

1

2

4

1

1 1 8

161 1 1 1 1

12 16n

A growth factor of order 2n corresponds to a loss of the order of n bits of precision.


Despite this example, Gaussian elimination with partial pivoting is utterly stable in practice. Large factors U never seem to appear in real applications.

Random matrix : each entry is an independent sample from the real normal distribution of mean 0 and standard deviation n -1/2 .

A = randn(n,n)/sqrt(n)A = randn(n,n)/sqrt(n)


Despite this example, Gaussian elimination with partial pivoting is utterly stable in practice. Large factors U never seem to appear in real applications.

Random matrix : each entry is an independent sample from the real normal distribution of mean 0 and standard deviation n -1/2 .

A = randn(n,n)/sqrt(n)A = randn(n,n)/sqrt(n)

La factorisation LU d’une matrice La factorisation LU d’une matrice tridiagonaletridiagonale

La factorisation LU d’une matrice La factorisation LU d’une matrice tridiagonaletridiagonale

, tridiagonaleAv d A

1

diag i

i

1

11

22

21

1

1

1

1n

nn

n

c

zz

ca

zz

ca

z

A L U

111

1

, , 2kk k

k

cz z c k n

b

11

1

111 1

1 1

1

1

2,3, ,

2,3, ,

1, 2, ,1

k k k kk k k k

k

n n k

k k

kk

k k

k

k k k

k

ccz z

b b a z

z d a wdw w d a w

b c

v

b a

w v w z v

k n

k n

k n

z

n

suite

L w d 1Uv w

3 1 additions

3 1 multiplications

2 divisions

n

n

n

328 vs.

3 O n O n

La factorisation LU d’une matrice-bandeLa factorisation LU d’une matrice-bande

no no pivotingpivoting

pivotingpivoting

FINEFINE

Documents

Giansalvo EXIN Cirrincione unité #3 rappels grand O Définition : la fonction T(n) est dite « grand O » de f(n) que lon note T(n)= O (f(n)), sil existe