Calcul Différentiel 2 et Optimisation Numérique (2025)
Feuille de TD n°5
Exercice 1 (Descente de gradient à pas optimal, le cas quadratique). On considère A ∈ Sd++ (R)
et la fonction
1
f : x 7→ ⟨Ax, x⟩.
2
On considère la descente de gradient à pas optimal. Une itération xk étant fixée, déterminer le
pas tk tel que
f (xk − tk ∇f (xk )) = inf f (xk − t∇f (xk )).
t≥0
Exercice 2 (Une variante de la descente de gradient). On rappelle que la norme ∥ · ∥∞ sur Rd
Pd
est définie de la manière suivante : si (e1 , . . . , ed ) est la base canonique de Rd et si x = i=1 xi ei
alors
∥x∥∞ = max |xi |.
i
On note ∥ · ∥ la norme euclidienne usuelle.
On travaille avec une fonction f de classe C 2 , coercive, convexe, et on suppose qu’il existe
ℓ, L > 0 tels que
∀x ∈ Rd , ∀h ∈ Rd , ℓ∥h∥2 ≤ ⟨∇2 f (x)h, h⟩ ≤ L∥h∥2 .
1. Montrer que le problème d’optimisation
inf f (x)
x∈Rd
a une unique solution x∗ .
2. Démontrer que, pour tout x ∈ Rd , on a
ℓ
∥x − x∗ ∥ − ∥∇f (x)∥ ≤ 0
2
et que pour tout x ∈ Rd
1
f (x) − f (x∗ ) ≤ ∥∇f (x)∥2 .
2ℓ
3. On étudie l’algorithme itératif suivant : une initialisation x0 étant donnée on choisit, à
chaque étape k la direction
∂f
dk := − (xk )ei(k)
∂xi(k)
où i(k) est le premier indice tel que
∂f
= ∥∇f (xk )∥∞ .
∂xi(k)
1
Le pas de descente est le réel tk ≥ 0 défini par
tk = argmint≥0 f (xk + tdk )
et on pose
xk+1 = xk + tk dk .
Montrer que le pas tk est bien défini et que dk est une direction de descente.
4. Montrer que pour tout t ≥ 0
Lt2
f (xk+1 ) ≤ f (xk + tdk ) ≤ f (xk ) − t∥∇f (xk )∥2∞ + ∥∇f (xk )∥2∞ .
2
5. En déduire que
1
f (xk+1 ) − f (xk ) ≤ − ∥∇f (xk )∥2∞ .
2L
6. En déduire que
∗ ℓ
f (xk+1 ) − f (x ) ≤ 1 − (f (xk ) − f (x∗ )).
dL
Qu’en déduit-on sur la convergence de la suite des valeurs renvoyées par l’algorithme ?
Exercice 3 (Changement de produit scalaire). On note ⟨·, ·⟩ le produit scalaire usuel de Rd . Soit
A ∈ Sd++ (R) de valeurs propres 0 < λ1 ≤ · · · ≤ λd . On définit la forme bilinéaire sur Rd
∀x, y ∈ Rd , ⟨x, y⟩A := ⟨xA, y⟩ = xT Ay.
1. Montrer que ⟨·, ·⟩A est un produit scalaire.
2. Montrer que la norme associée ∥ · ∥A est équivalente à la norme usuelle ∥ · ∥, et plus
précisément,
∀x ∈ Rd , λ1 ||x||2 ≤ ||x||2A ≤ λd ∥x∥2 .
3. Soit B ∈ Md (R). Montrer que
⟨x, By⟩A = ⟨A−1 B T Ax, y⟩A .
On dit que le dual de B est A−1 B T A pour le produit scalaire ⟨·, ·, ⟩A .
4. Pour les fonctions suivantes, calculer le gradient, pour le produit scalaire ⟨·, ·⟩A :
1 T
F1 (x) := ∥x∥2A , F2 (x) := ∥x∥2 , F3 (x) := x Ax − bT x.
2
On remarquera que le gradient dépend du produit scalaire.
Exercice 4 (Résolution de l’équation de Poisson). On veut dans cet exercice résoudre l’équation
différentielle (
−u′′ = f dans [0; 1],
(1)
u(0) = u(1) = 0.
Ici la fonction f est continue sur l’intervalle. Pour résoudre cette équation numériquement, on va
mettre en œuvre des algorithmes de type descente de gradient ou gradient conjugué pour l’analyse
d’un système discrétisé approché.
2
1. Soit g une fonction de classe C 4 sur R, avec ∥g (4) ∥L∞ < ∞. On se fixe un pas de
discrétisation δ > 0. Démontrer qu’il existe une constante C0 telle que
g(x + δ) − 2g(x) + g(x − δ)
g ′′ (x) − ≤ C0 δ 2 .
δ2
1
2. On se fixe un entier d > 1 et on pose δ := d+1 . On veut approcher la solution u de (1)
par un vecteur U := (ui )i=1,...,d en approchant le terme source f par F = (f (iδ))i=1,...,d .
Est-il raisonnable de choisir U comme la solution de
∆δ U = F
où ∆δ est la matrice définie par
−1
2 0 ... ... 0
.. ..
−1 2 −1 . .
..
.. ..
1 0 −1 2 . . .
∆δ = 2 ?
δ ... .. .. ..
. . . −1 0
. ..
..
. −1 2 −1
0 ... ... 0 −1 2
3. Démontrer que ∆δ est une matrice symétrique définie positive. En déduire que le système
∆δ U = F est bien posé (i.e. qu’il admet une unique solution).
4. Calculer les valeurs propres (et les vecteurs propres associés) de la matrice ∆δ . Que vaut
cond(∆δ ) ? En donner un équivalent quand δ → 0. Indication : on pourra commencer par
déterminer les réels λ et les fonctions ϕ ∈ C 2 (R; R) non identiquement nulles sur [0; 1]
telles que −ϕ′′ = λϕ.
5. Proposer une méthode de résolution numérique de (1).
