Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur GraphSearch.
Concept
Méthode de surrelaxation successive
Résumé
En analyse numérique, la méthode de surrelaxation successive (en anglais : Successive Overrelaxation Method{', abrégée en SOR) est une variante de la méthode de Gauss-Seidel pour résoudre un système d'équations linéaires. La convergence de cet algorithme est généralement plus rapide. Une approche similaire peut être appliquée à bon nombre de méthodes itératives.
Cette méthode a été découverte simultanément par et Stan Frankel en 1950 dans le but de résoudre automatiquement des systèmes linéaires avec des ordinateurs. Les méthodes de surrelaxations ont été utilisées auparavant. On citera la méthode de Lewis Fry Richardson et la méthode de R. V. Southwell. Ces méthodes étaient conçues pour des êtres humains et elles requéraient une expertise certaine afin d'assurer la convergence. Ces méthodes ne pouvaient être retranscrites sur ordinateur. Ces limitations ont été discutées dans la thèse de David Young
On considère un système linéaire de n équations avec n inconnues notées x (qui est un vecteur) :
où :
A étant la somme d'une matrice diagonale notée D et de deux matrices triangulaires (respectivement inférieure et supérieure) notées L et U :
le système d'équations linéaires peut être reformulé par :
pour tout ω > 0.
La méthode de surrelaxation successive est une méthode itérative initialisée par le choix d'un arbitraire, et où chaque itération consiste à déterminer à l'aide de selon la formule suivante :
La matrice de gauche (D+ωL) étant triangulaire, il est aisé de calculer par :
Le choix du facteur de relaxation n'est pas trivial et dépend des coefficients de la matrice. Pour une matrice définie positive, on peut démontrer que l'algorithme est convergent pour tout . Toutefois, on veut une convergence aussi rapide que possible. Notons que pour un facteur de relaxation de 1, on tombe sur la méthode de Gauss-Seidel
Entrée: A, b, ω
Sortie:
On choisit une solution initiale arbitraire .
Répéter jusqu'à convergence
Boucler i de 1 à n
Boucler j de 1 à i − 1
Fin (boucle j)
Boucler j de i + 1 à n
Fin (boucle j)
Fin (boucle i)
Vérifier la convergence.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.