Ê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 Graph Search.
Concept
Méthode du gradient conjugué
Résumé
vignette|Illustration de la méthode du gradient conjugué.
En analyse numérique, la méthode du gradient conjugué est un algorithme pour résoudre des systèmes d'équations linéaires dont la matrice est symétrique définie positive. Cette méthode, imaginée en 1950 simultanément par Cornelius Lanczos, Eduard Stiefel et Magnus Hestenes, est une méthode itérative qui converge en un nombre fini d'itérations (au plus égal à la dimension du système linéaire). Toutefois, son grand intérêt pratique du point de vue du temps de calcul vient de ce qu’une initialisation astucieuse (dite « préconditionnement ») permet d'aboutir en seulement quelques passages à une estimation très proche de la solution exacte : c'est pourquoi, en pratique, on se borne à un nombre d'itérations bien inférieur au nombre d'inconnues.
La méthode du gradient biconjugué fournit une généralisation pour les matrices non symétriques.
L'objectif est de minimiser la fonction où A est une matrice carrée symétrique définie positive de taille n.
Le calcul montre qu'une solution du problème est la solution du système : en effet, on a .
Intuitivement, la fonction f peut donc être vue comme une primitive (littéralement un potentiel scalaire) du résidu . En annulant le gradient de f, on obtient le vecteur x qui minimise l'erreur.
On rappelle que deux vecteurs non nuls u et v sont conjugués par rapport à A si
Sachant que A est symétrique définie positive, on en déduit un produit scalaire
Ainsi, deux vecteurs sont conjugués s'ils sont orthogonaux pour ce produit scalaire.
La conjugaison est une relation symétrique : si u est conjugué à v pour A, alors v est conjugué à u.
Supposons que est une suite de n directions conjuguées deux à deux. Alors les forment une base de Rn, ainsi la solution x* de dans cette base :
Les coefficients sont donnés par
(car sont conjugués deux à deux)
On a ainsi l'idée directrice de la méthode pour résoudre le système : trouver une suite de n directions conjuguées, et calculer les coefficients αk.
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.