1

ASI 3

Méthodes numériquespour l’ingénieur

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

Jacobi, Gauss Seidel, relaxation

Résoudre un système linéaire

=++−=++−=++

−=−+

⇔=

6 2

8 2 3

0 3

6242

432

4321

421

321

xxx

xxxxxxx

xxx

bAx

( )

( )

ii

n

ijjjiji

ia

xabx

xxx

xxxx

xxx

xxx

AAdistbxA

xxxx

∑≠=

−

=

−+=

−+−=

−−=

+−−=

<=

,1

324

4213

412

321

4321

~

soit

1

~2~61

~2~~38

3

~~0

2

~2~46

:essayait on si

~, exemplepar avec ~~~ que imaginons

solution presque"" une ~,~,~,~soit

ε

2

Résoudre un système linéaire en itérant

ii

n

ijjjiji

i a

xabx

xxx

xxxx

xxx

xxx

∑≠=

−

=

−+=

−+−=

−−=

+−−=

,1

324

4213

412

321

~

soit

1

~2~61

~2~~38

3

~~0

2

~2~46

Si Ax n’est pas encore égale à b, on recommence !

fin

)10 ( ),( quetant

,1

old

new

12-

ii

n

ijjjiji

i

new

a

xabx

i.e.bAxdist

∑≠=

−

=

> ε

Osons itérer ! méthode de Jacobi

fin

)10 ( ),( quetant

,1

old

new

12-

ii

n

ijjjiji

i

new

a

xabx

i.e.bAxdist

∑≠=

−

=

> ε

Soit D la diagonale de la matrice A, et G le reste :A = D+G

( )old1newoldnew

1,1

,11,

,,11,1

,121

111211

0

0

0

0

0

0000

0000

0000

0000

0000

GxbDxGxbDx

aaa

aaaaaa

aa

aaa

G

a

a

a

D

nnnin

nnii

niiiiii

ii

ni

nn

ii

−=⇔−=

=

=

−

−

−+

−−

−

L

OM

MO

L

O

O

3

=++−

=++−

=++

−=−+

⇔=

6 2

8 2 3

0 3

6242

432

4321

421

321

xxx

xxxxxxx

xxx

bAx

ii

n

ijjij

i

jjiji

i a

xaxabx

xxx

xxxx

xxx

xxx

∑∑+=

−

=−−

=

−+=

−+−=

−−=

+−−=

1

1

1

324

4213

412

321

~

soit

1

261

~238

3

~0

2

~2~46

Gauss Seidel

méthode de Gauss-Seidel

fin

)10 ( ),( quetant

1

old1

1

new

new

12-

ii

n

ijjij

i

jjiji

i

new

a

xaxabx

i.e.bAxdist

∑∑+=

−

=

−−

=

> ε

Soit E la triangulaire inférieure et F la supérieure de la matrice A :A = D+E+F

( ) ( ) ( )old1newoldnew

,1

,,1

,1

1112

1,1

1,

1,1

21

0000

00

000

00

0

0

00

000

00

0000

FxbEDxFxbxED

a

aaa

aaa

F

aaaa

aaa

Enn

niii

ii

ni

nnnin

ii

iii

−+=⇔−=+

=

=

−

−

−

−

−

+

−

L

OM

MO

L

L

OM

MO

L

4

La relaxation( )

relaxation de paramètre:0

)1(

>

−+=

=

ω

ωω

ϕoldnewnew

r

oldnew

xxx

xx

] [

] [

∈

=

∈

tionextrapolla :2,1

quo status :1

tioninterpolla :1,0

ω

ω

ω

( ) ( ) ( )

( )( )

( ) ( ) ( )

( ) ( )( ) old

oldold1

old

oldold1

1

1

1

par t multiplianen

1

xFDbxED

xFxbEDx

xGDbDx

D

xGxbDx

newr

newr

newr

newr

ωωωω

ωω

ωωω

ωω

−−+=+

−+−+=

−−+=

−+−=

−

−( ) ( )

( ) ( )old1new

old1new

: SeidelGauss

)( :Jacobi

FxbEDx

xFEbDx

−+=−

+−=

−

−

Résumé « algorithmique »

( )

( ) ( )

( ) ( )

=

+=+=+

−=

+=−=+

−

−−=

=+−=

+=

−−

−−

FDN

EDMxFDbxED

R

FN

EDMFxbxED

FEN

DMxFEbDx

bNxMx

ω

ωω

ω

ω

ω 1

1old1new1

oldnew

oldnew

oldnew

:

:elaxation

:

: SeidelGauss

:)(

:Jacobi

5

ConvergencePrincipes généraux

( ) dxCI

xx

C

dCxx

xkk

=−

−<

+=+

*

*

0

1

0

: desolution la vers pour tout converge dessusci algorithmel' Alors

1 que telleesubordonné ematriciell norme une existe ilS':

donné,

Théorème

Éléments de démonstration- x* est un point fixe de l’algorithme-

( )0 ,1 si

* C *

*

00

1

011

→<≤≤−=

==⇔−−+=−=

∞→

−

−−

kkkkk

k

kkkk

kk

CCeCeCexxC

eCeedCxdCxxxe

ini

n

ii

n

i

pi

pp

n

ii

n

xxxxpxxxx

REynxnyxn

xnxn

xxn

xn

xnx

REn

,111

11

222 sup ; ; )1( ;

; exemples

)()()(

)()(

00)(

positivité 0)(

iant vérif)(

::norme

=∞

===

+

==≥==

=

+≤+

=

=⇔=

≥

→

∑∑∑

λλa

Normes matricielles

DéfinitionSoit A une matrice nxm, étant donnée une norme vectorielle,on appelle norme matricielle subordonnée, la norme matricielledéfinie par :

xAx

AxRx

n0,

max≠∈

=

xAxAx ~ ~:max ceest ~ =Conséquence :

6

-2 .5 -2 -1 .5 -1 -0 .5 0 0 . 5 1 1 . 5 2 2 . 5

-2

-1 .5

-1

-0 .5

0

0 . 5

1

1 . 5

2

x

Ax

Exemples

( )

∞

=≤≤∞=≤≤

==

=

==

==

∑∑

∑∑

'

; max ; max

; tr :Frobénius de norme

1

11111

1

2

1

2

AA

aAaA

A'AaA

m

jijni

n

iijmj

n

iij

m

jF

AxAxRx n 1,

max=∈

=Illustration 2d

12 =x

x1

x2 x2Ax

x1

2A

à utiliser pour le calcul !

Calculez les valeurs propres de

−

−

111

110

201

Et ses vecteurs propres ?,31,31,1 321 ii −=+== λλλ

1

,

1

,

0

1

1

33

332

333

332

21

=

=

= −

−

i

i

i

i

vvv

7

Rayon spectrale d’une matriceDéfinition : on appelle rayon spectrale d’une matrice carrée A,

le nombre réel ρ(A) tel que :

( ) )(max,1

AA ini

λρ=

=

Théorème : soit A une matrice nxm, alors :

( )AAA F '2ρ=

Corollaire : si A est une matrice carrée symétrique nxn, alors :

( )AA F ρ=

Remarque : en général, le rayon spectrale n’est pas une norme :

( ) 0,01 , 00

10=≠=

= AAA F ρ

Convergence : le retourPrincipes généraux

( ) dxCI

xx

C

dCxx

xkk

=−

−<

+=+

*

*

0

1

0

: desolution la vers pour tout converge dessusci algorithmel' Alors

1 que telleesubordonné ematriciell norme une existe ilS':

donné,

Théorème

Théorème : les points suivants sont équivalents : • C est une matrice convergente, (i.e. Ck tend vers 0)• ρ(C)<1•

1<C

8

Résumé « algorithmique »

( )

( ) ( )

( ) ( )

=

+=+=+

−=

+=−=+

−

−−=

=+−=

+=

−−

−−

FDN

EDMxFDbxED

R

FN

EDMFxbxED

FEN

DMxFEbDx

bNxMx

ω

ωω

ω

ω

ω 1

1old1new1

oldnew

oldnew

oldnew

:

:elaxation

:

: SeidelGauss

:)(

:Jacobi

Convergence

Théorème : Si A est une matrice à diagonale strictement dominante,alors la méthode de Jacobi converge.

Démonstration

( ) ( )

11

max)(

, )( avec

)( :Jacobi

1,1

1

11k1k

k11k

<

=+=

=+=+=

+−=

∑==∞

−

∞

−−+

−+

n

jij

iini aa

FEDC

bDdFEDCdCxx

xFEbDx

Remarque : il en est de même pour la méthode de Gauss-Seidel

9

ConvergenceThéorème : soit une méthode itérative :

Si A est une matrice symétrique définie positive telle que si A = M-N alors M+N’ est définie positiveAlors la méthode itérative est convergente

Démonstration( )

( ) ( )

( )

1max : donc aon

''''''

'''''

posons

' positive définie symétrique

1

1,

1221

22

2221

1

212121

2

<=⇒<−

+−=+−−=

+−−=−−=−=−

=⇔≡

−=−=

=⇔

−

=

−−

−

−

−−−

AxxAAA

AA

AAA

AAA

A

NxMNMxAxMx

yNMyxAyyMyyyMyx

AyyAxyAyxxAyxAyxyxAxMx

AxMyAxMy

AxMxxAMMNxM

AxxxA

A

Théorème : Si A est une matrice symétrique définie positive, la méthode de la relaxation converge pour :

k1k bNxMx +=+

20 << ω

0 2

1

rayo

n sp

ectr

al

rayon spectral de la matrice M-1

N

ω

Influence de w

10

Remarques

pratique :

• pas de preuve de convergence généralisée,

• on préfère la relaxation avec différents tests pour ω,

• on préfère les méthodes directes,

• voir les méthodes semi directes pour les problèmes degrande taille (cf les méthodes « multigrilles »),

Conditionnement d’un système linéaire

[ ][ ]

2et 0002.0

0002.0 0

00

0

3

1

1

solutionsdeux examinons

3

3

20001.1

21

2

1

2

1

2

1

=−=−

=−=

=−=

=

=

=

=

=

⇔=

yxrr

bAyr

bAxr

y

yy

x

xx

x

xbAx

yx

Ty

Tx

Deux vecteurs très différents donnent des solutions très proches

x2

x11

1

3

11

Conditionnement : influence du second membre

7363)(:007.0,1.24

6.22 10 7.3 :

0.26

6.5

0.11

5.34

,

9.22

1.28

9.12

1.38

1

1

1

1

solution commeadmet ,

23

28

13

38

,

7187

74107

1651

1010108

41

3

=−==

==

−

−

=+

=+

=

=

=

−

Acond

xx

bb

xxbb

xbA

λλ

δδδδ

( )( )

( ) ( )

~ singulièrenon ~ ~

)(~ avec ~

1

1

rAxx

ArAxxxxA

xxxxAAx

bbbr

−

−

≤−⇒

=−⇔−=

+=−=

+−=

δ

δ

ConditionnementDéfinition : on appelle conditionnement d’une matrice carrée A, relatif

à une norme subordonnée, le nombre réel χ(A) :

( ) 1 −= AAAχ

Remarque :( ) 1

11≥⇒≤=

−−AAAAAI χ

Théorème : Si A est une matrice carrée, non singulière (régulière)

( )

( )bb

Axx

bbxxAbAxδ

χδ

δδ

≤

+=+=

, ( )( )

( )AA

Axx

x

bxxAAbAxδ

χδ

δ

δδ

≤+

=++=

,

Perturbation du second membre Perturbation de la matrice

Un problème est dit « bien conditionné » si χ(A) est proche de 1,

il est dit « mal conditionné » si χ(A) est grand (et mal posé si χ(A) est infini)

12

Conditionnement

( )

bb

AAxx

bAxxAbbbxxA

bA

xxAbbAx

δδ

δδδδδδ

1

1

)2 )1

)2

11 )1

−

−

≤⇒+

≤⇒≤⇒+=+

≤⇒≤⇒=

( ) 1 −= AAAχ

Remarque : si A est symétrique, si on note ses valeurs propres λi

( )1

2

22

1

121

doncet

1

,,...,,...,,

λ

λχ

λλ

λλλλ

n

nni

A

AA

=

== −

Dans l ’exemple, ( )

( ) 22.5) trouvéa(on 2.27 de ordrel' deest erreur l' de borne la

0037.0,7363

2

2

=

==

bA

bA

δχ

δχ

Comment améliorer le conditionnement ?

Ajouter un « chouia » sur la diagonale

( )µλ

µλµχ

+

+=+

12

nIA

13

Itérations !A = randn(n);b= ones(n,1);x = A\b;err = A*x-b;norm(err)

ans = 2.8246e-013

dx = A\err;

err2 = A*(x-dx)-b;norm(err2)

ans = 6.4789e-014

( )

xAbbxA

bxxA

bxAerr

bAgaussx

bAx

~~~

~),(~

−==

=+

−=

=

=

δ

δ

TP - la relaxationLe but du TP est d’écrire un programme matlab résolvant un système linéaire par la méthode de la relaxation

x = relax(A,b,w,nite,err)

Pour ce faire, il faut étudier l’évolution du rayon spectal

- mettez vous par binôme- rédigez une page :

recto : ce que vous avez faitverso ce que vous en pensez

- a rendre pour le 8 décembre à 17h30 (publication du corrigé)

Indices : créer un problème test,

les fonction cputime et flopstril et triu pourraient vous simplifier la vie

et diag(diag()) et eig aussi

( ) defonction en 1

ωρ NM−

14

PropriétésDéfinition : on appelle quotient de Rayleigh la fonction qA(x)

xxAxx

xqA ''

)( =

Théorème : si A est symétrique,

)(maxmax xqAx

ii

=λ

λi est une valeur propre de A, vi est un vecteur propre de A.

iii vvA rrλ=

Soit A une matrice carrée, on appelle polynôme caractéristique de A le polynôme défini par :

( )IAp λλ −= det)(

Les n racines λi de ce polynôme sont les valeurs propres de A, vi est un vecteur propre de A. Il existe n vecteurs vi tels que :