View
34
Download
3
Category
Preview:
Citation preview
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.gif28/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.gif28/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.gif28/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.comRecommended