1

Résolution des systèmes d’équations linéaires Algorithme de la méthode de Gauss : Données : n ordre de A , les jia éléments de la matrice A et les ib éléments de la

colonne des termes constants. Faire pour 1=i à 1−n Si 0=iia , alors

Si pour 1+= im à n tous les 0=ima , Fin de l’algorithme (pas de solution unique)

Sinon permuter les lignes i et m Fin de si Fin de si Faire pour 1+= ij à n Poser iiij aaT =

Poser ijj bTbb −=

Poser kikjkj aTaa −= pour ik = à n

Fin de la boucle de j Fin de la boucle de i Si 0=nna Fin (pas de solution)

Poser ii

n

ijjiji

i a

axb

x

∑+=

−

= 1 pour ni = à 1,-1 (solution du système linéaire)

Algorithme de la méthode du pivot : Données : n ordre de A , les jia éléments de la matrice A et les ib éléments de la

colonne des termes constants. Faire pour 1=i à 1−n Chercher pour im = à n et pour il = à n l’élément qpa tel que

lmqp aa max=

Permuter les lignes i et p Permuter les colonnes i et q Faire pour 1+= ij à n Poser iiij aaT =

2

Poser ijj bTbb −=

Poser kikjkj aTaa −= pour ik = à n

Fin de la boucle de j Fin de la boucle de i Si 0=nna Fin (pas de solution)

Poser ii

n

ijjiji

i a

axb

x

∑+=

−

= 1 pour ni = à 1,-1 (solution du système linéaire)

Algorithme de la méthode de Gauss-Jordan : Données : n ordre de A , les jia éléments de la matrice A et les ib éléments de la

colonne des termes constants. ( c est la matrice inverse de A ). Faire pour 1=i à n Faire pour 1=j à n Si ji = poser 1=jic

Sinon poser 0=jic

Fin de si Fin de la boucle de j Fin de la boucle de i Faire pour 1=i à n Si 0=iia alors

Si pour 1+= im à n tous les 0=ima Fin (Pas de solution unique)

Sinon Permuter entre kma et kia pour ik = à n

Permuter entre kmc et kic pour 1=k à n

Fin de si Fin de si Faire pour 1=j à n Si ji ≠ , alors Poser iiij aaT =

Poser ijj bTbb −=

Faire pour 1=k à n Poser kikjkj aTaa −=

Poser kikjkj cTcc −=

3

Fin de la boucle de k Fin de la boucle de j Fin de la boucle de i Poser iiii abx = pour 1=i à n (la solution du système linéaire)

Poser iijiji acc = pour 1=i à n et 1=j à n (éléments de la matrice inverse)

Algorithme de la méthode de Crout : Données : n ordre de A , les jia éléments de la matrice A , et les ib éléments de

la colonne des termes constants. Si 011 =a Fin ( A ne peut pas être décomposée)

Poser 11 ii aL = pour 1=i à n

Poser 1111 aaU jj = pour 2=j à n

Faire pour 2=j à n Faire pour 2=i à n Si ji ≥ alors

Poser ∑−

=−=

1

1

j

kjkkijiji ULaL

Si 0=iiL , Fin ( A ne peut pas être décomposée)

Sinon

Poser

−= ∑

−

=

1

1

1i

kjkkiji

iiji ULa

LU

Fin de si Fin de la boucle de i Fin de la boucle de j

Poser ii

i

jjiji

i L

Lyb

y

∑−

=

−

=

1

1 pour 1=i à n

Poser ∑+=

−=n

ijjijii Uxyx

1

pour ni = à 1 avec un pas de -1

4

Algorithme de la méthode de Doolittle : Données : n ordre de A , les jia éléments de la matrice A , et les ib éléments de

la colonne des termes constants. Si 011 =a Fin ( A ne peut pas être décomposée)

Poser jj aU 11 = pour 1=j à n

Poser 1111 UaL ii = pour 2=i à n

Faire pour 2=i à n Faire pour 2=j à n Si ij ≥ alors

Poser ∑−

=−=

1

1

i

kjkkijiji ULaU

Si 0=jjU Fin ( A ne peut pas être décomposée)

Sinon

Poser

−= ∑

−

=

1

1

1j

kjkkiji

jjji ULa

UL

Fin de si Fin de la boucle de j Fin de la boucle de i

Poser ∑−

=

−=1

1

i

jjijii Lyby pour 1=i à n

Poser ii

n

ijjijii UUxyx

−= ∑

+= 1 pour ni = à 1 avec un pas de -1

Algorithme de la méthode de Choleski : Données : n ordre de A , les jia éléments de la matrice A , et les ib éléments de

la colonne des termes constants. Si 011 ≤a Fin ( A n’est pas définie positive)

Poser 1111 aL =

Poser 1111 LaL ii = pour 2=i à n

Faire pour 2=j à n

5

Faire pour 1=i à n Si ji p poser 0=jiL

Si ji = alors

Poser ∑−

=−=

1

1

2i

kkiii LaS

Si 0≤S Fin ( A n’est pas définie positive) Poser SL ii =

Si ji f poser

−= ∑

−

=

1

1

1j

kkjkiji

jjji LLa

LL

Fin de la boucle de i Fin de la boucle de j

Poser ii

i

jjjiii LyLby

−= ∑

−

=

1

1 pour 1=i à n

Poser ii

n

ijjijii LxLyx

−= ∑

+= 1 pour ni = à 1 avec un pas de -1

Algorithme de la méthode de Jacobi : Données : Les jia éléments de la matrice A , n ordre de A , les ib éléments de la

colonne des termes constants, l’approximation initiale ( )0X et la précision ε . 1) Poser 1=k

2) Poser ( ) ( ) ( )∑∑+=

−−

=

− −−=n

ij

kj

ii

jii

j

kj

ii

ji

ii

iki x

a

ax

a

a

a

bx

1

11

1

1 pour 1=i à n

3) Calculer ( ) ( )1

1max −

≤≤− k

ik

inixx

4) Si ( ) ( ) ε≤− −

≤≤

1

1max k

ik

inixx (la solution est ( )kX ) aller à l’étape 5

Sinon ajouter 1 à k et aller à l’étape 2 5) Fin

6

Algorithme de la méthode de Gauss-Seidel : Données : n ordre de A , les jia éléments de la matrice A , les ib éléments de la

colonne des termes constants, l’approximation initiale ( )0X et la précision ε . 1) Poser 1=k

2) Poser ( ) ( ) ( )∑∑+=

−−

=

−−=n

ij

kj

ii

jii

j

kj

ii

ji

ii

iki x

a

ax

a

a

a

bx

1

11

1

pour 1=i à n

3) Calculer ( ) ( )1

1max −

≤≤− k

ik

inixx

4) Si ( ) ( ) ε≤− −

≤≤

1

1max k

ik

inixx (la solution est ( )kX ) aller à l’étape 5

Sinon ajouter 1 à k et aller à l’étape 2 5) Fin Algorithme de la méthode de relaxation (Southwell): Données : n ordre de A , les jia éléments de la matrice A , les ib éléments de la

colonne des termes constants, l’approximation initiale ( )0X et la précision ε . 1) Poser 0=k

2) Poser ( ) ( ) ( )∑≠=

−+−=

n

ijj

kj

ii

jiki

ii

iki x

a

ax

a

bR

1

3) Choisir m tel que la valeur ( ) ( )kini

km RR

≤≤=

1max soit maximale

4) Si ( ) ε≤kmR (la solution approchée est ( )kX ) aller à l’étape 7

sinon aller à l’étape 5

5) Si mi ≠ poser ( ) ( )ki

ki xx =+1 pour 1=i à n

Sinon poser ( ) ( ) ( )km

ki

ki Rxx +=+1

6) Ajouter 1 à k et aller à l’étape 2 7) Fin

7

Algorithme de la méthode SOR : Données : n ordre de A , les jia éléments de la matrice A , les ib éléments de la

colonne des termes constants , l’approximation initiale ( )0X , la précision ε et ω . 1) Poser 1=k

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

1

11

11 −

+=

−−

=−+

−−= ∑∑ k

i

n

ij

kjji

i

j

kjjii

ii

ki xxaxab

ax ωω pour 1=i

à n

3) Calculer ( ) ( )1

1max −

≤≤− k

ik

inixx

4) Si ( ) ( ) ε≤− −

≤≤

1

1max k

ik

inixx (la solution est ( )kX ) aller à l’étape 5

Sinon ajouter 1 à k et aller à l’étape 2 5) Fin