28/12/13 Rsolution des systmes linaires

jmblanc.developpez.com/algorithmique/systemes-lineaires/?page=page_4 1/5

Forums Tutoriels Magazine FAQs Blogs Projets Chat Newsletter tudes Emploi Club Contacts

Ada Algorithmique Basic Cobol Fortran LaTeX MATLAB Prolog Purebasic R Ruby XMLRAD

ACCUEIL ALGO COURS ALGO FAQ ALGO FORUM ALGO LIVRES ALGO SOURCES ALGO

Rsolution des systmes linaires

Table des matires

IV. Mthodes itrativesIV-A. Mthode de Jacobi

AlgorithmeErreurConvergenceRsidu

IV-B. Mthode de Gauss-SeidelAlgorithmeVarianteErreurConvergenceRsidu

IV-C. Mthode de surrelaxation (SOR)VarianteErreurConvergenceRsiduMthode de surrelaxation symtrique (SSOR)

IV. Mthodes itratives

IV-A. Mthode de Jacobi

La mthode de Jacobi est une mthode itrative de rsolution de systme linaire dela forme A x = B o :

Pour cela, on va construire une suite de vecteurs :

qui converge vers x , solution du systme d'quations linaires.

Remarque : chacun des vecteurs successifs est identifi par un numro plac enexposant et entre parenthses.

Algorithme

Un vecteur initial x(0) tant donn, l'algorithme suivant permet de dterminer leslments successifs de la suite.

On dcompose la matrice A en trois matrices L , D et U . La matrice L estconstitue des termes qui se trouvent au-dessous de la diagonale principale de A(j< i) ; la matrice D contient les termes diagonaux de A(j = i) ; la matrice U estconstitue des termes qui se trouvent au-dessus de la diagonale principale de A(j >i) .

Accueil ALM Java .NET Dv. Web EDI Langages SGBD Office Solutions d'entreprise Applications Mobiles Systmes

http://ada.developpez.com/http://algo.developpez.com/http://bodman.developpez.com/basichttp://cobol.developpez.com/http://fortran.developpez.com/http://latex.developpez.com/http://matlab.developpez.com/http://prolog.developpez.com/http://purebasic.developpez.com/http://r.developpez.com/http://ruby.developpez.com/http://xmlrad.developpez.com/http://algo.developpez.com/http://algo.developpez.com/cours/http://algo.developpez.com/faq/http://www.developpez.net/forums/f60/autres-langages/algorithmes/http://algo.developpez.com/livres/http://algo.developpez.com/sources/http://www.developpez.net/forums/http://general.developpez.com/cours/http://magazine.developpez.com/http://general.developpez.com/faq/http://blog.developpez.com/http://projets.developpez.com/http://chat.developpez.com/http://www.developpez.com/newsletter/http://etudes.developpez.com/http://emploi.developpez.com/http://club.developpez.com/http://club.developpez.com/contacts/http://www.developpez.com/http://ams1.ib.adnxs.com/click?AAAAAAAAAAAAAAAAAAAAAFg5tMh2vr8_AAAAAAAAAAAAAAAAAAAAAH-G9pEQkrYrIO-1fH9PvhvL9b5SAAAAAAUiDQB0AwAAdAMAAAIAAAAJ02QASV4CAAAAAQBVU0QARVVSANQBPABMdgAA-HgBAgQCAQIAAIIAvRdCQAAAAAA./cnd=%21mgWCMgiw6lgQiaaTAxjJvAkgBA../referrer=http%3A%2F%2Fwww.developpez.com/clickenc=http%3A%2F%2Fwww.rechercheruncredit.fr%2Findex%2Fhome%2Ftr_code%2F1296http://algo.developpez.com/index/rsshttp://www.developpez.com/http://alm.developpez.com/http://java.developpez.com/http://dotnet.developpez.com/http://web.developpez.com/http://edi.developpez.com/http://general.developpez.com/langages/http://sgbd.developpez.com/http://office.developpez.com/http://solutions-entreprise.developpez.com/http://applications.developpez.com/http://mobiles.developpez.com/http://systeme.developpez.com/

28/12/13 Rsolution des systmes linaires

jmblanc.developpez.com/algorithmique/systemes-lineaires/?page=page_4 2/5

Le systme rsoudre peut alors s'crire :

d'o l'on tire la formule de rcurrence :

qui permet de calculer x(k+1) lorsque x(k) est connu :

On remarquera que toutes les composantes de x(k) sont utilises pour le calcul de

chaque composante de x(k+1) . Ces deux vecteurs doivent donc tre stocks dansdeux tableaux distincts.

Erreur

A chaque itration, le vecteur trouv x(k+1) comporte une certaine erreur :

On pose P = D -1 (L+U) . Il vient alors :

Convergence

L'algorithme converge si ou, ce qui revient au mme,

.

Thorme : une condition ncessaire et suffisante pour que estque les modules de toutes les valeurs propres de P soient strictement infrieures 1.

Thorme : la formule de rcurrence converge, quel que soit x(0) , si la matrice Aest diagonale dominante, c'est--dire si la valeur absolue de chaque termediagonal est suprieure la somme des valeurs absolues des termes rectanglesplacs sur la mme ligne.

Rsidu

On appelle rsidu le vecteur R (k) = B - A x (k) . La prcision exige tant donne,on arrte les itrations lorsque :

IV-B. Mthode de Gauss-Seidel

La mthode de Gauss-Seidel est une mthode itrative de rsolution de systmelinaire de la forme A x = B o :

http://jmblanc.developpez.com/algorithmique/systemes-lineaires/images/methiter01003.gif

28/12/13 Rsolution des systmes linaires

jmblanc.developpez.com/algorithmique/systemes-lineaires/?page=page_4 3/5

Pour cela, on va construire une suite de vecteurs :

qui converge vers x , solution du systme d'quations linaires.

Remarque : chacun des vecteurs successifs est identifi par un numro plac enexposant et entre parenthses.

Algorithme

Un vecteur initial x(0) tant donn, l'algorithme suivant permet de dterminer leslments successifs de la suite.

On dcompose la matrice A en trois matrices L , D et U . La matrice L estconstitue des termes qui se trouvent au-dessous de la diagonale principale de A(j< i) ; la matrice D contient les termes diagonaux de A(j = i) ; la matrice U estconstitue des termes qui se trouvent au-dessus de la diagonale principale de A(j >i) .

Le systme rsoudre peut alors s'crire :

d'o l'on tire la formule de rcurrence :

qui permet de calculer les composantes de x(k+1) lorsque celles de x sont connues :

On remarquera que chaque composante de x(k) n'est utilise que jusqu'au calcul de

la composante correspondante de x(k+1) . Ces deux vecteurs peuvent donc trestocks dans le mme tableau.

Variante

Il est aussi possible de calculer les xi(k+1) partir du dernier. Cela revient

permuter le rle des matrices L et U . La formule de rcurrence devient :

qui permet de calculer les composantes de x(k+1) lorsque celles de x sont connues :

Erreur

A chaque itration, le vecteur trouv x(k+1) comporte une certaine erreur :

On pose P = D +L -1U . Il vient alors :

Convergence

http://jmblanc.developpez.com/algorithmique/systemes-lineaires/images/methiter01003.gif

28/12/13 Rsolution des systmes linaires

jmblanc.developpez.com/algorithmique/systemes-lineaires/?page=page_4 4/5

L'algorithme converge si ou, ce qui revient au mme,

.

Thorme : une condition ncessaire et suffisante pour que estque les modules de toutes les valeurs propres de P soient strictement infrieures 1.

Thorme : la formule de rcurrence converge, quel que soit x(0), si la matrice Aest diagonale dominante, c'est--dire si la valeur absolue de chaque termediagonal est suprieure la somme des valeurs absolues des termes rectanglesplacs sur la mme ligne.

Rsidu

On appelle rsidu le vecteur R (k) = B - A x (k) . La prcision exige tant donne,on arrte les itrations lorsque :

IV-C. Mthode de surrelaxation (SOR)

En utilisant la mthode de Gauss-Seidel, on observe qu' chaque itration lacorrection apporte au vecteur solution a tendance tre sous-estime. End'autres termes, le vecteur converge trop lentement vers la solution. D'o l'ided'augmenter la correction, l'aide d'un facteur multiplicatif , appel paramtre derelaxation .

Comme dans la mthode de Gauss-Seidel, on dcompose la matrice A en troismatrices L , D et U :

Le systme rsoudre peut alors s'crire :

d'o l'on tire la formule de rcurrence :

qui permet de calculer les composantes de x(k+1) lorsque celles de x sont connues :

Remarque : si on pose = 1, on retrouve la mthode de Gauss-Seidel

Variante

Il est aussi possible de calculer les xi(k+1) partir du dernier. Cela revient

permuter le rle des matrices L et U . La formule de rcurrence devient :

Ce qui permet de calculer les composantes de x(k+1) lorsque celles de x sontconnues :

http://jmblanc.developpez.com/algorithmique/systemes-lineaires/images/methiter01003.gif

28/12/13 Rsolution des systmes linaires

jmblanc.developpez.com/algorithmique/systemes-lineaires/?page=page_4 5/5

Developpez.com

Nous contacterParticipezInformations lgales

ServicesForum AlgorithmiqueBlogsHbergement

Erreur

A chaque itration, le vecteur trouv x(k+1) comporte une certaine erreur :

On pose P = D +L -1U . Il vient alors :

Convergence

L'algorithme converge si ou, ce qui revient au mme,

.

Thorme : une condition ncessaire et suffisante pour que estque les modules de toutes les valeurs propres de P soient strictement infrieures 1.

Thorme : la formule de rcurrence converge, quel que soit x(0), si la matrice Aest diagonale dominante, c'est--dire si la valeur absolue de chaque termediagonal est suprieure la somme des valeurs absolues des termes rectanglesplacs sur la mme ligne.

Rsidu

On appelle rsidu le vecteur R (k) = B - A x (k) . La prcision exige tant donne,on arrte les itrations lorsque :

Mthode de surrelaxation symtrique (SSOR)

La surrelaxation successive symtrique (SSOR) est une variante qui consiste fairejouer le mme rle aux matrices L et U , en alternant une itration dans laquelle oncommence par la premire composante du vecteur x et une dans laquelle oncommence par la dernire. On a donc une paire de formules de rcurrence :

qui permettent de calculer les composantes de x(k+1) et x(k+2) lorsque celles de xsont connues :

C opyright 2008-2013 Jean-Marc Blanc . A ucune reproduc tion, mme partielle, ne peut tre faite de ce s ite et de l'ensemble de son contenu : textes , documents , images , etc .

sans l'autorisation expresse de l'auteur. Sinon vous encourez selon la loi jusqu' trois ans de prison et jusqu' 300 000 de dommages et intrts .

Responsable bnvole de la rubrique Algorithmique : Romuald Perrot (PRomu@ld) - Contacter par email

Copyright 2000-2013 - www.developpez.com

http://club.developpez.com/contacts/http://www.developpez.com/participez/http://www.developpez.com/legal/http://www.developpez.net/forums/f60/autres-langages/algorithmes/http://blog.developpez.com/http://www.developpez.com/hebergement/http://www.developpez.net/forums/u60280/promu-ld/mailto:algo@redaction-developpez.com