Chapitre 1

Optimisation sans contraintes

On rappelle que tout minimum ou maximum x d’une fonction réelle dérivable f : R → R

satisfait f ′ (x) = 0. Ce résultat s’applique aussi pour les fonctions J : Rn → R dérivables.

Ce chapitre vise dans sa première partie à rappeler quelques notions élémentaires concernant
les problèmes d’optimisation non contraints sur Rn . Ensuite, et dans la dernière partie de ce
chapitre, des méthodes de descente de type gradient seront développées pour calculer numéri-
quement un minimum x̄ d’une fonction J sur Rn .

Comme application, on considère le problème de minimisation d’une fonction quadratique dont

la résolution est équivalente à la résolution d’un système linéaire Ax = b, où A est une matrice
symétrique définie positive.

1.1 Optimisation sur Rn

Dans de nombreux domaines d’applications d’analyse numérique, on est amené à minimiser une
fonction J et chercher x̄ vérifiant

J(x̄) ≤ J(x), ∀x ∈ Rn , (1.1)

où la fonction J, dite objectif, est une fonction numérique à variable un vecteur x de Rn . C’est
un problème de minimisation qu’on peut noter aussi

min J(x). (P)

x∈Rn

Pour maximiser une fonction J, il suffit de minimiser (−J), un problème d’optimisation sur Rn
peut donc s’écrire toujours sous la forme de (P).

Tout vecteur x̄ solution de (3.1) est appelé solution optimale de (P). On dit aussi que x̄ présente
(ou tout simplement) un minimum de J sur Rn .

Du théorique au numérique, pour la résolution du problème (P) ou de (3.1), on s’intéresse aux

questions suivantes :
1. Existe-t-il une solution et est-elle unique ?
2. Comment caractériser cette solution ?
3. Comment approcher d’une manière efficace cette solution ?
Commençons par développer la première étape concernant l’existence puis l’unicité d’une solu-
tion d’un problème d’optimisation sans contraintes.

2
Optimisation sur Rn 3

1.1.1 Existence et unicité d’un minimum

On rappelle tout d’abord qu’une suite de vecteurs (x(k) ) est dite bornée de Rn s’il existe R > 0
tel que
∥x(k) ∥ ≤ R, pour tout entier k,
c’est-à-dire que la suite (x(k) ) est contenue dans une boule de centre 0 et de rayon R > 0.
On rappelle aussi que de toute suite bornée de Rn , on peut en extraire une sous-suite conver-
gente.

Proposition 1.1.1. On suppose que J est continue et qu’elle vérifie

lim J(x) = +∞. (1.2)
∥x∥→+∞

Alors le problème de minimisation (P) admet au moins une solution.

Preuve. Soit
α = infn J(x).
x∈R

Montrons que α est atteint, i.e., il existe x̄ ∈ Rn tel que J(x̄) = α. D’après la propriété de la
borne inférieure, il existe une suite (x(k) )k de Rn telle que
lim J(x(k) ) = α.
k→∞

Alors la suite (x(k) ) est bornée. En effet, si la suite (x(k) ) est non bornée, elle vérifie, pour une
sous-suite, notée aussi (x(k) ), que limk→+∞ ∥x(k) ∥ = +∞ et comme lim∥x∥→+∞ J(x(k) ) = +∞,
donc α = +∞, ce qui est une contradiction. Comme (x(k) ) est bornée, on peut en extraire une
sous-suite (x(k) ) convergente vers x̄. Comme J est continue, alors
J(x̄) = lim J(x(k) ) = lim J(x(k) ) = infn J(x).
k→+∞ k→+∞ x∈R

D’où l’existence d’au moins une solution pour le problème (P).

Remarques 1.1.1.

1. Si J vérifie (3.2), on dit qu’elle est infinie à l’infini ou qu’elle est coercive.
2. Une fonction J continue et minorée sur Rn admet une borne inférieure, mais pas forcé-
ment de minimum si elle n’est pas infinie à l’infini. Voici un contre-exemple : La fonction
x 7→ ex est positive, mais elle n’a pas de minimum sur R.
Remarque 1.1.1. Ce résultat donne l’existence d’un minimum mais il ne donne pas l’unicité.
La fonction x 7→ x4 − 2x2 admet deux minima atteints en x = −1 et x = 1.

Figure 1.1 – f (x) = x4 − 2x2

On peut avoir des résultats d’unicité si on utilise la convexité.

Page 3
Optimisation sur Rn 4

Définition 1.1.1. Soit J une fonction définie sur Rn à valeurs dans R.

1. On dit que J est convexe sur Rn si :
∀(x, y) ∈ Rn × Rn , ∀t ∈ [0, 1], J((1 − t)x + ty) ≤ (1 − t)J(x) + tJ(y).

2. On dit que J est strictement convexe sur Rn si :

∀(x, y) ∈ Rn × Rn , tel que x ̸= y, ∀t ∈]0, 1[, J((1 − t)x + ty) < (1 − t)J(x) + tJ(y).
Remarques 1.1.2.
1. Graphiquement, une fonction est convexe si sa courbe se trouve en dessous de ses cordes.

2. Une fonction J est dite concave si (−J) est convexe.

Exemples 1.1.1.
1. L’application x 7→ ∥x∥2 est strictement convexe sur Rn .
2. Toute forme linéaire J(x) = (b, x) = bT x où b ∈ Rn est convexe mais non strictement
convexe.
Proposition 1.1.2. Si la fonction J : Rn → R est convexe, alors l’ensemble des solutions du
problème (P) est convexe. Si de plus J est strictement convexe et elle admet un minimum sur
Rn , il est unique.

Preuve. Soit S l’ensemble des solutions optimales. Montrons que S est convexe. Soit (x1 , x2 ) ∈
S × S, si t ∈ [0, 1], et comme J est convexe, on a donc :
J((1 − t)x1 + tx2 ) ≤ (1 − t)J(x1 ) + tJ(x2 ) ≤ (1 − t)J(x) + tJ(x) = J(x), ∀x ∈ Rn .

On en déduit que (1 − t)x1 + tx2 ∈ S, pour tout t ∈ [0, 1]. D’où la convexité de S.

Si de plus J est strictement convexe, on suppose qu’il existe deux solutions x1 et x2 de (P )

telles que x1 ̸= x2 . Alors, x1 +x
2
2
∈ S et en vertu de la stricte convexité de J, il vient que :
x1 + x2 1 1
 
J < J(x1 ) + J(x2 ) = J(x1 ).
2 2 2

Contradiction, ainsi x1 = x2 .

1.1.2 Conditions d’optimalité

On se limite dans ce cours à donner les conditions d’optimalité du premier ordre qui font
intervenir seulement les dérivées d’ordre 1 de la fonction à minimiser.

Page 4
Optimisation sur Rn 5

Fonction différentiable

Définition 1.1.2. On dit que J : Rn → R est différentiable au point x ∈ Rn , s’il existe p ∈ Rn

et une fonction φ : Rn → R tels que

J(x + h) = J(x) + (p, h) + ∥h∥ · ε(h) avec lim ε(h) = 0.

h→0

S’il existe, le vecteur p est appelé la différentielle (ou la dérivée) de J en x et il est noté J ′ (x).
On dit que J est différentiable sur Rn si elle est différentiable en tout point de Rn .
Remarque 1.1.2. Si on note (e1 , . . . , en ) la base canonique de Rn , on peut vérifier que J :
Rn → R est différentiable en x. De plus, le gradient de J en x est
 
∂J
(x)
 ∂x1
.. 
J ′ (x) = ∇J(x) =  . , (1.3)
 
 
∂J
∂xn
(x)

où
∂J J(x + tei ) − J(x)
(x) = lim , i = 1, . . . , n,
∂xi t→0 t
sont les dérivées partielles de J.
Exercice 1.1.1. On pourra montrer en exercice que :
1. Toute forme linéaire J(x) = (b, x) = b⊤ x où b ∈ Rn , est différentiable et on a :

J ′ (x) · h = (b, h) = b⊤ h,

donc
J ′ (x) = ∇J(x) = b.
2. La fonctionnelle J : x 7→ J(x) = 12 a(x, x), où a est une forme bilinéaire symétrique
continue sur Rn , est différentiable. On a alors :

J ′ (x) · h = a(x, h).

Donc,
J ′ (x) = a(x, ·).
En particulier, si A est une matrice symétrique, alors J : x 7→ 12 (Ax, x) est différentiable
et on a :
J ′ (x) = ∇J(x) = Ax. (1.4)

Fonction différentiable convexe

On peut caractériser la convexité et la convexité stricte des fonctions différentiables. C’est

l’objet de deux propositions suivantes :
Proposition 1.1.3. Soit J : Rn → R une fonction différentiable. Alors les propriétés suivantes
sont équivalentes :
i) J est convexe sur Rn ;
ii) pour tout (x, y) ∈ Rn × Rn on a :

J(y) ≥ J(x) + (∇J(x), y − x);

Page 5
Optimisation sur Rn 6

iii) ∇J est un opérateur monotone, c’est-à-dire, ∀(x, y) ∈ Rn × Rn , on a :

(⟨)∇J(x) − ∇J(y), x − y) ≥ 0.
Preuve.
- i) ⇒ ii) Supposons que J est convexe. Alors, pour tout t ∈]0, 1] et pour tout (x, y) ∈
Rn × Rn , on a :
J((1 − t)x + ty) ≤ (1 − t)J(x) + tJ(y).
En réarrangeant, on obtient :
J(x + t(y − x)) − J(x)
J(y) ≥ J(x) + .
t
En faisant tendre t vers 0, on obtient :
J(y) ≥ J(x) + (∇J(x), y − x).
- ii) ⇒ iii) Si x, y ∈ Rn , alors :
J(y) ≥ J(x) + (∇J(x), y − x) et J(x) ≥ J(y) + (∇J(y), x − y).
En additionnant ces deux inégalités, on obtient :
(∇J(x) − ∇J(y), y − x) ≥ 0.
- iii) ⇒ i) Pour montrer que J est convexe, il suffit de montrer que, pour tout x, y ∈ Rn ,
la fonction g définie sur [0, 1] par :
g(t) = (1 − t)J(x) + tJ(y) − J((1 − t)x + ty)
est positive. Il est clair que g est dérivable sur [0, 1] et que :
g ′ (t) = −J(x) + J(y) − (∇J(x + t(y − x)), y − x).
Pour t1 ̸= t2 , on a :
(g ′ (t1 ) − g ′ (t2 ))(t1 − t2 ) = (∇J(x + t2 (y − x)) − ∇J(x + t1 (y − x)), y − x)(t2 − t1 ) ≤ 0.
Donc, g ′ est décroissante. Comme g est continue sur [0, 1] et dérivable sur ]0, 1[, vérifiant
g(0) = g(1) = 0, d’après le théorème de Rolle, il existe c ∈]0, 1[ tel que g ′ (c) = 0, ce qui
entraîne que g est positive pour tout t ∈ [0, 1].
On peut montrer de manière analogue que :
Proposition 1.1.4. Soit J : Rn → R une fonction différentiable. Alors les propriétés suivantes
sont équivalentes :
- i) J est strictement convexe sur Rn ;
- ii) pour tout (x, y) ∈ Rn × Rn tels que x ̸= y, on a :
J(y) > J(x) + (∇J(x), y − x); (1.5)
- iii) ∇J est un opérateur strictement monotone, c’est-à-dire, ∀(x, y) ∈ Rn × Rn tels que
x ̸= y, on a :
(∇J(x) − ∇J(y), x − y) > 0.
Remarque 1.1.3. D’après (iii) de la Proposition 3.1.3, une fonction dérivable J : R → R est
convexe sur R si et seulement si sa fonction dérivée J ′ est croissante. Si de plus J est deux fois
dérivable, alors J est convexe sur R si et seulement si J ′′ est positive.
Exemple 1.1.1.
Si A est une matrice symétrique, la fonction J : Rn → R; x 7→ 21 (Ax, x) − (b, x) est strictement
convexe sur Rn si et seulement si
(∇J(x) − ∇J(y), x − y) = (A(x − y), x − y) > 0 pour tout x, y ∈ Rn , x ̸= y.
On rappelle que cette dernière propriété sur A est vérifiée si et seulement si A est définie
positive.

Page 6
Optimisation sur Rn 7

Condition nécessaire et suffisante d’optimalité

En général, pour déterminer un minimum d’une fonction J, on cherche parmi les points critiques
qui vérifient la condition nécessaire d’optimalité (qui devient aussi suffisante lorsque J est
convexe) suivante :
Proposition 1.1.5. Soit J : Rn → R une fonction différentiable en x̄.
1. Si x̄ réalise un minimum de J sur Rn , alors

∇J(x̄) = 0. (1.6)

2. Si la fonction J est convexe et si ∇J(x̄) = 0, alors x̄ réalise un minimum de J sur Rn .

Remarque 1.1.4.
La condition (3.6) est connue sous le nom de l’équation d’Euler qui est, sans la convexité de J,
en général une condition nécessaire mais non suffisante d’optimalité. La fonction x 7→ x4 − 2x2
tracée dans la remarque (3.1.1) est un contre-exemple puisque sa dérivée s’annule en x = 0 et
x = ±1, mais x = 0 ne réalise pas un minimum pour cette fonction. La fonction J : x 7→ x3
vérifie J ′ (0) = 0 mais 0 n’est ni un minimum ni un maximum de J sur R.

1.1.3 Problème d’optimisation quadratique

Si la fonction objectif est de type quadratique, c’est-à-dire si elle est de la forme

1
J(x) = (Ax, x) − (b, x)
2
pour A ∈ Mn (R) symétrique et b ∈ Rn , alors le problème de minimisation (P ) est dit quadra-
tique et on a :
Proposition 1.1.6. Si A est symétrique définie positive, alors le problème quadratique (P )
admet une solution unique x̄ vérifiant :

Ax̄ = b.

Preuve. Si on note par λ1 la plus petite valeur propre de A, on a (voir (1.6) dans chapitre 1) :

λ1 ∥x∥22 ≤ (Ax, x) ∀x ∈ Rn . (1.7)

D’après la remarque précédente et l’inégalité de Cauchy-Schwarz, on déduit que J vérifie

λ1 λ1
J(x) ≥ ∥x∥22 − (b, x) ≥ ∥x∥22 − ∥b∥2 ∥x∥2 −→ 0
2 2 k→+∞

De plus, J est strictement convexe, donc J admet un minimum unique x̄ sur Rn vérifiant

∇J(x̄) = Ax̄ − b = 0.

1.1.4 Problème aux moindres carrés

Pour A ∈ Mpn (R) et b ∈ Rp , avec n < p, le système Ax = b ne possède pas, en général, de

solution. On peut se contenter alors à chercher x qui minimise le carré de la norme de Ax − b,
et donc ainsi formuler le problème de moindres carrés suivant :
1
min ∥Ax − b∥22 . (1.8)
x∈Rn2

Page 7
Algorithmes de descente et méthodes du gradient 8

Remarque 1.1.5. Pour chercher la solution de (3.8) et afin de pouvoir appliquer l’équation
d’Euler, on minimise la norme au carré de Ax − b au lieu de ∥Ax − b∥2 puisque l’application
norme n’est jamais différentiable en 0. Clairement, les deux problèmes sont équivalents.
Proposition 1.1.7. Le problème (3.8) admet au moins une solution. De plus, toute solution x̄
de (3.8) est aussi solution du système

AT Ax̄ = AT b.

Le problème (3.8) admet une solution unique si et seulement si la matrice A est injective.

Avant de montrer cette proposition, rappelons le résultat classique d’algèbre linéaire :

Lemme 1.1.1. Pour toute matrice A ∈ Mpn (R), on a Im(AT A) = Im(AT ).

Preuve. Il est clair que Im(AT A) ⊂ Im(AT ). De plus, d’après le théorème de rang, on sait que

dim Im(A) + dim ker(A) = dim(Rn ) = n = dim Im(AT ) + dim ker(A).

Or on ker(A) = ker(AT A), puisque ker(A) ⊂ ker(AT A) et si x ∈ ker(AT A), (AT Ax, x) =
(Ax, Ax) = ∥Ax∥22 = 0, donc Ax = 0 et par suite x ∈ ker(A). on obtient

dim Im(AT A) + dim ker(AT A) = dim(Rn ) = n.

Par conséquent, dim Im(AT A) = dim Im(AT ) et les deux espaces sont donc égaux.

Preuve. de la propositio (3.1.7) Ici, la fonction objectif est

1 1
J(x) = (AT Ax, x) − (AT b, x) + ∥b∥22
2 2

La matrice AT A est toujours symétrique et semi-définie positive puisque (AT Ax, x) = ∥Ax∥22 ≥
0 pour tout vecteur x ∈ Rn . La fonction quadratique J est donc convexe. Par conséquent, x̄ est
solution de (3.8) si et seulement si

∇J(x̄) = AT Ax̄ − AT b = 0.

Comme Im(AT ) = Im(AT A), on déduit que le système AT Ax = AT b admet au moins une
solution, d’où l’existence d’au moins un minimum de J sur Rn . L’unicité du minimum est
assurée si et seulement si le système AT Ax = AT b admet une solution unique pour tout vecteur
b, donc si et seulement si la matrice AT A est bijective. Ceci étant vérifié si et seulement si A
est injective.

1.2 Algorithmes de descente et méthodes du gradient

1.2.1 Méthodes de descente

Les méthodes numériques de descente en général sont des méthodes itératives dont le
but est de déterminer x̄ réalisant le minimum d’une fonction J sur Rn , en utilisant des direc-
tions de déplacement permettant de se rapprocher le plus possible de x̄. Dans ce chapitre, on
va utiliser des méthodes numériques de descente du gradient pour un problème de minimisa-
tion sans contrainte quelconque dont la convergence sera étudiée seulement pour le problème
quadratique :
1
J(x) := minn (Ax, x) − (b, x), (1.9)
x∈R 2

Page 8
Algorithmes de descente et méthodes du gradient 9

où A est une matrice symétrique définie positive et b un vecteur de Rn .

Ces méthodes s’appliquent alors aussi pour résoudre numériquement un système linéaire
Ax = b, pour A une matrice symétrique définie positive.

Définition 1.2.1. Soit J une fonction de Rn à valeurs dans R. Soit x ∈ Rn . On dit que d ∈ Rn ,
avec d ̸= 0, est une direction de descente de J en x s’il existe α0 > 0 tel que
J(x + αd) ≤ J(x), ∀α ∈ [0, α0 ].

Ainsi, une méthode de descente pour la recherche de x̄ solution de

min J(x),
x∈Rn

consiste à construire une suite (x(k) )k∈N de la manière suivante :

- Initialisation : x(0) ∈ Rn ,
- Pour k ≥ 0 : on cherche la direction de descente d(k) au point x(k) et on détermine le pas
αk .
- Ensuite, on calcule x(k+1) = x(k) + αk d(k) .
Proposition 1.2.1. Soient J : Rn → R une fonction différentiable, x, d ∈ Rn avec d ̸= 0. Si d
est une direction de descente en x, alors :
(∇J(x), d) ≤ 0.

Preuve. Soit la fonction ϕ : R → R définie par : ϕ(α) = J(x + αd). Alors ϕ est dérivable et
ϕ′ () = (∇J(x + αd), d).
On considère d ∈ Rn une direction de descente au point x. Alors par définition, il existe α0 > 0
tel que :
J(x + αd) ≤ J(x), ∀α ∈ [0, α0 ].

Comme d est une direction de descente, on peut écrire, pour tout α ∈ [0, α0 ],
ϕ(α) ≤ ϕ(0),
et donc pour tout α ∈]0, α0 ],
ϕ(α) − ϕ(0)
≤ 0.
α−0
En passant à la limite lorsque α tend vers 0, on déduit que ϕ′ (0) ≤ 0, ce qui signifie que
(∇J(x), d) ≤ 0.

1.2.2 Méthodes du gradient

Dans ces méthodes, les directions de descente s’expriment en fonction du gradient de la fonction
à minimiser.

Remarque 1.2.1. Ces méthodes itératives de descente ne sont pas toujours finies. Il faut donc
un critère d’arrêt qui permet d’arrêter les itérations dès que l’itérée x(k) s’approche de la solution
x̄ du problème à minimiser. Comme test d’arrêt classique pour ce type d’algorithmes, on peut
s’arrêter à l’itération k si ∥∇J(x(k) )∥ ≤ ϵ ou si ∥x(k+1) −x(k) ∥ ≤ ϵ, pour ϵ une précision donnée.

Page 9
Algorithmes de descente et méthodes du gradient 10

1.2.3 Méthode du gradient à pas fixe

La méthode du gradient à pas fixe α > 0 consiste à choisir comme direction de descente d(k+1)
à l’étape k + 1, définie par :
d(k+1) = −∇J(x(k) ).

Pour un problème quadratique, l’algorithme s’écrit comme suit :

1. On choisit x(0) ∈ Rn et un pas α > 0.

2. Pour k ≥ 0, on calcule :

d(k) = −∇J(x(k) ) = b − Ax(k) ,

x(k+1) = x(k) + αd(k) .

Proposition 1.2.2. Méthode du gradient à pas fixe pour un problème quadratique

Si J(x) = 12 (Ax, x) − (b, x), où A est une matrice symétrique définie positive, alors la méthode
2
du gradient à pas fixe converge si et seulement si α ∈]0, ρ(A) [.

Démonstration. On a, pour k ≥ 0 :
x(k+1) = x(k) − α(Ax(k) − b) = (I − αA)x(k) + αb.

La matrice d’itération est Bα = I − αA, dont le spectre est

Sp(Bα ) = {1 − αλ; λ ∈ Sp(A)}.

Si on note par λ1 et λn respectivement la plus petite et la plus grande valeur propre de A,

alors :
1 − αλn ≤ 1 − αλ ≤ 1 − αλ1 , ∀λ ∈ Sp(A).

Ainsi,
ρ(Bα ) = max(|1 − αλ1 |, |1 − αλn |).

Par conséquent, la méthode du gradient à pas fixe converge si et seulement si ρ(Bα ) < 1. Donc
si et seulement si 0 < α < λ21 et 0 < α < λ2n . Cette dernière condition est bien équivalente à :
2
0<α< .
ρ(A)

1.2.4 Méthodes du gradient à pas optimal

Méthodes de descente à pas optimal

Une méthode de descente générale est du type

x(k+1) = x(k) + αk d(k)

Page 10
Algorithmes de descente et méthodes du gradient 11

pour x(0) donnée et pour une direction d(k) connue, est dite à pas optimal si l’on choisit le pas
αk de manière à minimiser la fonction
α 7→ J(x(k) + αd(k) ).

Calculons le pas αk pour un problème quadratique. Ceci revient à chercher α ∈ R vérifiant,

pour x, d ∈ Rn tel que d ̸= 0 :
∀r ∈ R, J(x + αd) ≤ J(x + rd). (Q)
Lemme 1.2.1. Si la matrice A est symétrique définie positive, alors (Q) admet une unique
solution donnée par
(Ax − b, d)
α=− .
(Ad, d)

Preuve. On considère la fonction f : R → R définie par :

f (r) = J(x + rd).

On a
1 1
f (r) = J(x+rd) = (A(x+rd), x̄+rd)−(b, x+rd) = ((Ax, x)+2r(Ax, d)+r2 (Ad, d))−(b, x)−r(b, x).
2 2

Ceci nous donne :

1 1
f (r) = r2 (Ad, d) + r(Ax − b, d) + (Ax, x) − (b, x).
2 2

Puisque (Ad, d) > 0 (car A est définie positive et d ̸= 0), on en déduit que la fonction f
(polynôme de degré 2) admet un minimum global au point r = α donné par :
(Ax − b, d)
α=− .
(Ad, d)
Remarque 1.2.2. Pour un problème quadratique du type (3.9), une méthode de descente à pas
optimal
(Ax(k) − b, d(k) )
αk = −
(Ad(k) , d(k) )
donne une relation d’orthogonalité entre la direction de descente d(k) et le gradient g (k+1) pour
g (k) = ∇J(x(k) ) = Ax(k) − b = −d(k) .

En effet, on a :
(g (k+1) , d(k) ) = (Ax(k+1) − b, d(k) ) = (Ax(k) − b, d(k) ) + αk (Ad(k) , d(k) ) = 0. (1.10)

Algorithme du gradient à pas optimal

La méthode du gradient à pas optimal est une méthode de descente dont la direction de descente
est donnée par le gradient.

Le principe de cette méthode s’écrit :

Initialisation : x(0) ∈ Rn donné.

Pour k ≥ 0, on procède comme suit :

Page 11
Algorithmes de descente et méthodes du gradient 12

1. Calculer d(k) = −∇J(x(k) ).

2. Choisir αk ≥ 0 tel que :

J(x(k) + αk d(k) ) ≤ J(x(k) + αd(k) ) pour tout α ≥ 0.

3. Poser x(k+1) = x(k) + αk d(k) .

Ainsi, l’algorithme du gradient à pas optimal pour un problème quadratique s’écrit :

1. Initialisation : x(0) ∈ Rn donnée,

2. Pour k ≥ 0, on calcule :

d(k) = b − Ax(k) ,
∥d(k) ∥22
αk = ,
(Ad(k) , d(k) )
x(k+1) = x(k) + αk d(k) .

Proposition 1.2.3. Si A est une matrice symétrique définie positive, alors la méthode du
gradient à pas optimal converge.

Preuve. Par construction, la suite (J(x(k) )) est décroissante et on sait qu’elle est minorée par
J(x̄), donc elle est convergente. Par conséquent,

lim (J(x(k+1 )) − J(x(k) )) = 0.

k→+∞

Or, on a
αk2
J(x(k+1 )) − J(x(k) ) = (Ad(k) , d(k) ) + αk (Ax(k) − b, d(k) ).
2
Sachant que
∥d(k) ∥22
αk = −
(Ad(k) , d(k) )
et
d(k) = −g (k) = −(Ax(k) − b),

donc
1 ∥g (k) ∥42
J(x(k+1 )) − J(x(k) ) = − .
2 (Ag (k) , g (k) )

D’après la relation (1.6), on déduit que

1
∥g (k) ∥22 ≤ J(x(k) ) − J(x(k+1 ) ,
2λn
où λn est la plus grande valeur propre de A. Donc,

∥g (k) ∥22 → 0 quand k → +∞.

Par conséquent, on en déduit que

∥x(k) − x̄∥2 = ∥A−1 (Ax(k) − b)∥2 ≤ ∥A−1 ∥2 ∥g (k) ∥2 → 0 quand k → +∞.

Page 12
Algorithmes de descente et méthodes du gradient 13

1.2.5 Méthodes du gradient conjugué

Cette méthode s’applique directement pour chercher la solution unique x̄ du problème

min J(x),
x∈Rn

pour

1
J(x) = (Ax, x) − (b, x), (P )
2

où A est une matrice symétrique définie positive.

Dans les algorithmes des deux méthodes de descente précédentes, les termes de la suite (x(k) )
s’approchent de plus en plus vers la solution cherchée x̄ sans généralement jamais l’atteindre.
D’où l’idée de la méthode du gradient conjugué où, comme on le verra, la suite (x(k) ) générée
par l’algorithme de cette méthode devient stationnaire à partir d’un certain nombre d’itérations
(au plus n), et elle vaut x̄.
Définition 1.2.2. Soit A une matrice symétrique définie positive de Mn (R).
- 1. Deux vecteurs non nuls d(1) , d(2) de Rn sont dits A-conjugués si (Ad(1) , d(2 )) = 0.
- 2. Une famille (d(1) , d(2) , . . . , d(p) ) de p vecteurs non nuls de Rn est dite A-conjuguée si
(Ad(i) , d(j) ) = 0 ∀i, j ∈ {1, . . . , p}, i ̸= j.
Remarque 1.2.3. On peut facilement vérifier que
1. Toute famille A-conjuguée de p vecteurs non nuls de Rn est libre.
2. Une famille A-conjuguée de n vecteurs non nuls de Rn est une base de Rn .
L’idée de la méthode du gradient conjugué, qui est aussi une méthode de descente à pas optimal,
est de construire la direction de descente en fonction du gradient et de la direction précédente
de descente.
On part de x(0) donnée et d(0) = −∇J(x(0) ) = −(Ax(0) − b) = −g (0) . Connaissant x(k) , d(k−1)
et g (k) , et si g (k) ̸= 0, on choisit la direction de descente

d(k) = −g (k) + βk−1 d(k−1) , (1.11)

et

x(k+1) = x(k) + αk d(k) , (1.12)

de manière à minimiser la fonction à deux variables

f : (α, β) 7→ J(x(k) + α(g (k) + βd(k−1) )) = J(x(k) + αd(k) ).

Donc ici le pas αk est optimal et on a la relation d’orthogonalité (voir lemme (3.2.1)) suivante

(d(k−1) , g (k) ) = 0. (1.13)

Si g (k) ̸= 0, d’après (3.11), on aura aussi d(k) ̸= 0 et par conséquent

Page 13
Algorithmes de descente et méthodes du gradient 14

(Ax(k) − b, d(k) ) (g (k) , −g (k) + βk−1 d(k−1) ) ∥g (k) ∥22

αk = − =− = .
(Ad(k) , d(k) ) (Ad(k) , d(k) ) (Ad(k) , d(k) )

Il suffit donc de déterminer la direction de descente d(k) . Ceci revient à chercher βk−1 . Sachant
que cette dernière doit vérifier

∂f
(αk , βk−1 ) = αk (∇J(x(k) + αk d(k) ), d(k−1) ) = 0,
∂β

et que ∇J(x) = Ax − b. On déduit d’abord

(Ad(k−1) , g (k) )
βk−1 = ,
(Ad(k−1) , d(k−1) )

puis que les directions d(k) et d(k−1) sont A-conjuguées,

(Ad(k) , d(k−1) ) = 0.

g (k) −g (k−1)
En remplaçant Ad(k−1) par αk−1
, on déduit que

∥g (k) ∥22
(Ad(k−1) , g (k) ) =
αk−1
et que
∥g (k−1) ∥22
(Ad(k−1) , d(k−1) ) = .
αk−1
On tire alors que

∥g (k) ∥22
βk−1 = .
∥g (k−1) ∥22

D’où l’algorithme du gradient conjugué :

1. On choisit x(0) ∈ Rn . On prend g (0) = Ax(0) − b = −d(0) .

2. Pour k ≥ 0, on calcule

∥g (k) ∥22
αk = , x(k+1) = x(k) + αk d(k) ,
(Ad(k) , d(k) )

g (k+1) = Ax(k+1) − b = g (k) + αk Ad(k) ,

∥g (k+1) ∥22
βk = , d(k+1) = −g (k+1) + βk d(k) .
∥g (k) ∥22
On montre alors :

Proposition 1.2.4. Si A est symétrique définie positive, alors l’algorithme du gradient conjugué
converge en au plus n itérations vers le minimum de J(x) := 21 (Ax, x) − (b, x) sur Rn .

Page 14
Algorithmes de descente et méthodes du gradient 15

Preuve. Pour k = 0, si g (0) = 0, alors Ax(0) = b et x̄ = x(0) . Sinon, on a :

d(0) = −g (0) = −Ax(0) + b = −∇J(x(0) ),

et

(g (0) , d(0) )
α0 = − , x(1) = x(0) + α0 d(0) , g (1) = Ax(1) − b
(Ad(0) , d(0) )

vérifiant

(g (1) , g (0) ) = (g (1) , d(0) ) = (d(1) , Ad(0) ) = 0.

Supposons maintenant, pour 1 ≤ k < n, l’hypothèse de récurrence

 
g (k) , g (j) = 0 pour 0 ≤ j < k,
 
g (k) , d(j) = 0 pour 0 ≤ j < k, (1.14)
 
d(k) , Ad(j) = 0 pour 0 ≤ j < k.

Si g (k) = 0, alors x̄ = x(k) et l’algorithme converge à l’itération k. Si g (k) ̸= 0, on construit

x(k+1) , g (k+1) et d(k+1) par l’algorithme du gradient conjugué.

Vérifions l’hypothèse de récurrence à l’ordre (k + 1)

 
g (k+1) , g (j) = 0 pour 0 ≤ j < k + 1,
 
g (k+1) , d(j) = 0 pour 0 ≤ j < k + 1,
 
d(k+1) , Ad(j) = 0 pour 0 ≤ j < k + 1.

D’après (3.13), et par construction, on a (g (k+1) , d(k) ) = 0,

et pour j < k, on a
         
g (k+1) , d(j) = g (k+1) , d(j) − g (k) , d(j) = g (k+1) − g (k) , d(j) = αk Ad(k) , d(j) = 0.
| {z }
=0

On a

g (k) = −d(k) + βk−1 d(k−1) .

Donc, pour j ≤ k,

(g (k+1) , g (j) ) = (g (k+1) , d(j) ) − βj (g (k+1) , d(j−1) ) = 0.

Or, pour j ≤ k, on a g (j+1) = g (j) + αj Ad(j) et donc

αj (g (k+1) , Ad(j) ) = (g (k+1) , g (j+1) ) − (g (k+1) , g (j) ) = 0.

Page 15
Algorithmes de descente et méthodes du gradient 16

Sachant que g (j) ̸= 0, donc αj ̸= 0 et par conséquent (g (k+1) , Ad(j) ) = 0.

Comme

d(k+1) = −g (k+1) + βk d(k) ,

alors, pour j ≤ k, on a

(d(k+1) , Ad(j) ) = (g (k+1) , Ad(j) ) + βk (d(k) , Ad(j) ) = 0,

et la récurrence est vérifiée.

Si g (k) ̸= 0, pour k = 0, . . . , n − 1, alors (d(0) , d(1) , . . . , d(n−1) ) est une famille A-conjuguée de n
vecteurs, donc une base de Rn et le vecteur g (n) sera orthogonal à d(0) , d(1) , . . . , d(n−1) . Nécessai-
rement g (n) = 0 et par suite x(n) = x̄. L’algorithme ainsi converge à l’itération exactement
n.
Remarque 1.2.4. Les directions de descente sont telles que la base (d(0) , d(1) , . . . , d(n−1) ) est
obtenue par le procédé d’orthogonalité de Gram-Schmidt, adapté au produit scalaire (Ax, y), à
partir de la base (−g (0) , . . . , −g (n−1) ).

1.2.6 Vitesse de convergence

En général, une suite (x(k) ) qui converge vers x̄, vérifiant x(k) ̸= x̄ pour tout entier k, est dite
d’ordre de convergence au moins p ∈ R∗+ si

∥x(k+1) − x̄∥ = O(∥x(k) − x̄∥p ).

En particulier, s’il existe γ ∈]0, 1[ tel que

∥x(k+1) − x̄∥
lim = γ,
k→+∞ ∥x(k) − x̄∥p

alors la convergence est dite exactement d’ordre p. La convergence est dite linéaire si p = 1 et
quadratique si p = 2.

Les méthodes de descente du gradient à pas fixe et à pas optimal sont à convergence au moins
linéaire et on pourra montrer que

Cond2 (A) − 1 (k)

∥x(k+1) − x̄∥ ≤ ∥x − x̄∥, (1.15)
Cond2 (A) + 1

où ∥ · ∥ désigne la norme euclidienne pour la méthode du gradient à pas fixe et la norme définie
par ∥x∥ = ∥x∥A = (Ax, x)1/2 pour la méthode du gradient à pas optimal.

Pour la méthode du gradient conjugué, et tant que g (k) = Ax(k) − b ̸= 0, on peut montrer la
majoration suivante :
q
Cond2 (A) − 1 (0)
∥x(k+1) − x̄∥A ≤ 2 q ∥x − x̄∥A . (1.16)
Cond2 (A) + 1

Page 16
Algorithmes de descente et méthodes du gradient 17

1.2.7 Méthodes du gradient et préconditionnement

Des majorations (3.15) et (3.16), on constate que l’erreur x(k) −x̄, obtenue au cours des itérations
des méthodes du gradient, diminue d’autant plus rapidement que Cond2 (A) est petit.
On rappelle aussi que les méthodes du gradient sont également des méthodes numériques pour
résoudre un système linéaire Ax = b, pour A ∈ Mn (R) symétrique définie positive. Ainsi, la
matrice du système préconditionné doit aussi être symétrique définie positive.

Le préconditionnement de ce système consiste alors à appliquer les méthodes du gradient pour

le problème de minimisation

1
minn (Ay, ỹ) − (b̃, y), (Pc )
y∈R 2

avec à = P AP T et b̃ = P b, où P est une matrice inversible bien choisie de sorte que à soit
bien conditionnée. La nouvelle matrice à est aussi symétrique définie positive et la solution x̄
du système Ax = b est donnée par x̄ = P T ȳ, pour ȳ solution optimale de (Pc ).

Page 17