Pourquoi le gradient conjugué exige-t-il une matrice symétrique définie positive ?

SDP rend la fonction quadratique strictement convexe et définit le produit scalaire associé à A, qui sert aux directions conjuguées. Sans ces propriétés, les garanties classiques du procédé ne tiennent plus.

Pourquoi le système bidimensionnel se résout-il en deux pas ?

En arithmétique exacte, le procédé minimise sur un sous-espace de Krylov qui s’agrandit et s’arrête en au plus n itérations pour un système SDP de dimension n. Dans la démonstration bidimensionnelle, la solution est atteinte en au plus deux directions indépendantes.

En quoi le gradient conjugué est-il meilleur que la plus grande pente ?

La plus grande pente suit −∇f et zigzague sur des ellipses allongées. Les directions conjuguées ne répètent pas les directions A déjà choisies, donc sur une cuvette mal conditionnée la convergence est nettement plus rapide.

Méthode du gradient conjugué

Système SDP Ax=b comme minimisation d’une forme quadratique : lignes de niveau, gradient conjugué contre plus grande pente, norme du résidu et conditionnement.

En arithmétique exacte, le gradient conjugué atteint la solution 2D en au plus deux itérations. Les itérations supplémentaires montrent surtout le résidu à l’échelle de l’arrondi et l’écart de trajectoire avec la plus grande pente.

Graphiques

À propos du modèle

La méthode du gradient conjugué traite le système Ax = b à matrice symétrique définie positive comme la minimisation de f(x) = ½ xᵀ A x − bᵀ x. Dans l’exemple bidimensionnel, les lignes de niveau sont des ellipses, la solution exacte est leur centre, le résidu vaut b − Ax. Le procédé choisit des directions de recherche A-conjuguées. Pour comparaison, depuis le même point, on montre la plus grande pente : sur des ellipses allongées, elle zigzague. Le conditionnement κ = λ_max/λ_min fixe l’allongement de la cuvette. En arithmétique exacte, le gradient conjugué termine en au plus n pas pour un système SDP de dimension n.

Public : Algèbre linéaire numérique, calcul scientifique, optimisation et résolution d’équations aux dérivées partielles.

Notions clés

gradient conjugué
matrice SDP
norme du résidu
minimisation quadratique
conditionnement
plus grande pente

Comment ça marche

Pour une matrice symétrique définie positive, le système Ax=b équivaut à minimiser f(x)=1/2 x^T A x − b^T x. Les lignes de niveau de cette fonction sont des ellipses, et la solution x\* est en leur centre. La méthode du gradient conjugué construit des directions p_k, conjuguées pour le produit scalaire (·,·)_A, et choisit le pas α_k=(r_k^T r_k)/(p_k^T A p_k). En dimension deux, en arithmétique exacte, deux itérations suffisent ; un grand κ allonge les ellipses et ralentit les méthodes voisines, par exemple la plus grande pente.

Formules

Le gradient conjugué résout Ax=b en minimisant f(x)=1/2 x^T A x − b^T x pour A SDP

α_k=(r_k^T r_k)/(p_k^T A p_k), β_k=(r_{k+1}^T r_{k+1})/(r_k^T r_k)

Questions fréquentes

Pourquoi le gradient conjugué exige-t-il une matrice symétrique définie positive ?: SDP rend la fonction quadratique strictement convexe et définit le produit scalaire associé à A, qui sert aux directions conjuguées. Sans ces propriétés, les garanties classiques du procédé ne tiennent plus.
Pourquoi le système bidimensionnel se résout-il en deux pas ?: En arithmétique exacte, le procédé minimise sur un sous-espace de Krylov qui s’agrandit et s’arrête en au plus n itérations pour un système SDP de dimension n. Dans la démonstration bidimensionnelle, la solution est atteinte en au plus deux directions indépendantes.
En quoi le gradient conjugué est-il meilleur que la plus grande pente ?: La plus grande pente suit −∇f et zigzague sur des ellipses allongées. Les directions conjuguées ne répètent pas les directions A déjà choisies, donc sur une cuvette mal conditionnée la convergence est nettement plus rapide.

Poursuivez avec des thèmes proches de cette catégorie — ou les 85 de «Visualisation mathématique».

Toute la catégorie →

NouveauCollège–lycée

Descente de gradient (2D)

Lancer la simulation

Lignes de niveau de f(x, y) et trajectoire (x, y) ← (x, y) − η∇f ; cuvette ou puits elliptique.

NouveauUniversité

MEF : équation de Poisson (2D)

Lancer la simulation

Éléments P1 triangulaires pour −Δu = f sur le carré : assemblage des matrices de rigidité, nœuds de Dirichlet imposés ou flux naturel de Neumann, résolution par le gradient conjugué, potentiel comme membrane colorée.

NouveauUniversité

Géométrie ACP / SVD

Lancer la simulation

Ellipse de covariance et réduction de dimension via la décomposition en valeurs singulières : composantes principales, variance expliquée et erreur de reconstruction de rang 1.

NouveauUniversité

Optimiseurs de descente de gradient

Lancer la simulation

Comparaison de SGD, du moment et d’Adam sur un relief bidimensionnel de la fonction de perte : pas d’apprentissage, courbure, stabilité et trajectoires des itérations.

NouveauUniversité

Particules dans un champ d’écoulement

Lancer la simulation

Champ synthétique v(x, y, t) ; transport à bords périodiques ; grille de flèches en option.

NouveauUniversité

Équation de la chaleur : différences finies

Lancer la simulation

Équation 1D u_t = αu_xx : FTCS explicite et Euler implicite ; faites varier r = αΔt/Δx², observez l’explosion du schéma explicite pour r > 1/2 et comparez la diffusion numérique.

Méthode du gradient conjugué

Graphiques

À propos du modèle

Comment ça marche

Formules

Questions fréquentes

Simulations voisines

Descente de gradient (2D)

MEF : équation de Poisson (2D)

Géométrie ACP / SVD

Optimiseurs de descente de gradient

Particules dans un champ d’écoulement

Équation de la chaleur : différences finies

Méthode du gradient conjugué

Graphiques

À propos du modèle

Comment ça marche

Formules

Questions fréquentes