Mon espace Me contacter

Calcul I MTH1101 • Polytechnique Montréal

Fiche de révision : la méthode du gradient (MTH1101, Polytechnique)

Cette fiche de révision porte sur la méthode du gradient telle que MTH1101 l'enseigne à Polytechnique, d'après la section 5.2 de Stewart, *Calcul à plusieurs variables* (« Optimisation sans contraintes, recherche linéaire et méthode du gradient »), appuyée sur les notes du professeur : itération x⃗k+1=x⃗k−tk∇f(x⃗k)\vec x_{k+1}=\vec x_{k}-t_{k}\nabla f(\vec x_{k}), recherche linéaire exacte, pas fixe, orthogonalité des gradients successifs, critère d'arrêt.

Elle ne refait pas le cours, elle dit ce qui coûte des points. À l'examen final, sans calculatrice ; seul document permis, votre aide-mémoire d'une feuille recto verso, et cette fiche dit quoi y mettre, le bloc « à savoir par cœur » en étant le noyau. L'examen fait faire une à trois itérations à la main sur une quadratique choisie pour donner des fractions, et on JUSTIFIE : pourquoi ce pas, pourquoi cet angle droit, pourquoi ce zigzag.

Marque ici la fiche comme lue ou mets-la en favori : un compte gratuit, sans mot de passe, retient tes fiches lues et tes favoris d'une visite à l'autre, te dit quel chapitre attaquer ensuite et te permet de demander la méthode ou l'exercice qui te manque. Crée ton espace, un courriel suffit.

Le fil du chapitre

−∇f-\nabla f dit où la pente est la plus raide ICI, pas où se trouve le minimum. La méthode du gradient est donc un ALGORITHME qui corrige sa direction à chaque pas, et le pas tt se CHOISIT : trop grand, il fait remonter ou diverger ; exact, il impose un virage à angle droit.

Ce chapitre fait partie de Calcul I MTH1101, Polytechnique Montréal : exercices corrigés et fiches, chapitre par chapitre
Pour s'entraîner Les exercices corrigés de ce chapitre, 10 exercices

Avant ce chapitre

Cette fiche suppose ces notions acquises. Si une méthode ci-dessous reste opaque, c'est presque toujours l'une d'elles qui manque, pas la fiche.

Remonter plus loin : la chaîne complète (8 chapitres) ↓

Le chemin de remédiation, du plus ancien au plus proche. Un élève qui reprend ce chapitre de zéro le reprend dans cet ordre.

  1. 1Les séries de Taylor et de Maclaurin
  2. 2L'erreur d'approximation de Taylor
  3. 3Les dérivées partielles
  4. 4Plan tangent et différentielle
  5. 5La dérivation en chaîne
  6. 6Gradient et dérivée directionnelle
  7. 7Approximation quadratique et Taylor à deux variables
  8. 8Extrema et optimisation sans contrainte

L'essentiel

La direction de plus forte descente est locale

  • • En un point x⃗k\vec x_{k} où ∇f≠0⃗\nabla f\neq\vec 0, la direction −∇f(x⃗k)-\nabla f(\vec x_{k}) est celle où ff décroît le plus vite, au taux −∥∇f(x⃗k)∥-\|\nabla f(\vec x_{k})\|. Elle est perpendiculaire à la courbe de niveau qui passe par x⃗k\vec x_{k}.
  • • Elle ne vise le minimum que si les courbes de niveau sont des cercles, ou si le point est sur un axe de l'ellipse. Sinon il faut plusieurs pas, et la méthode CORRIGE sa direction à chaque itération : x⃗k+1=x⃗k−tk∇f(x⃗k)\vec x_{k+1}=\vec x_{k}-t_{k}\nabla f(\vec x_{k}), avec tk>0t_{k}>0.
  • • φ(t)=f(x⃗k−t∇f(x⃗k))\varphi(t)=f\left(\vec x_{k}-t\nabla f(\vec x_{k})\right) est la coupe de ff le long de la droite de recherche. Elle vérifie φ(0)=f(x⃗k)\varphi(0)=f(\vec x_{k}) et φ′(0)=−∥∇f(x⃗k)∥2<0\varphi'(0)=-\|\nabla f(\vec x_{k})\|^{2}<0 : on descend au départ, rien de plus.
x² + 2y² = 6x² + y² = 5PQ
En P(2 ;1)P(2\,;1), la flèche −∇f-\nabla f part perpendiculairement à l'ellipse et manque le centre, que vise le pointillé ; en QQ, sur le cercle, elle vise le centre.

Une direction de descente garantit qu'un pas ASSEZ PETIT fait baisser ff. Elle ne dit ni jusqu'où aller, ni où est le minimum.

Les deux façons de choisir le pas

  • • RECHERCHE LINÉAIRE EXACTE : tkt_{k} minimise φ\varphi sur [0 ;+∞[[0\,;+\infty[. Pour une quadratique f(x⃗)=12x⃗⋅Hx⃗−b⃗⋅x⃗+cf(\vec x)=\frac{1}{2}\vec x\cdot H\vec x-\vec b\cdot\vec x+c, avec g⃗=∇f(x⃗k)\vec g=\nabla f(\vec x_{k}) : tk=g⃗⋅g⃗g⃗⋅Hg⃗t_{k}=\dfrac{\vec g\cdot\vec g}{\vec g\cdot H\vec g}, où HH est la HESSIENNE.
  • • Conséquence : ∇f(x⃗k+1)⋅∇f(x⃗k)=0\nabla f(\vec x_{k+1})\cdot\nabla f(\vec x_{k})=0. Deux pas successifs sont perpendiculaires, d'où le zigzag.
  • • PAS FIXE : le même tt à chaque itération. Sur x2+κy2x^{2}+\kappa y^{2}, les coordonnées sont multipliées par 1−2t1-2t et 1−2κt1-2\kappa t ; il faut ∣1−2t∣<1|1-2t|<1 ET ∣1−2κt∣<1|1-2\kappa t|<1, la plus forte courbure impose la borne.
  • • ARRÊT : ∥∇f(x⃗k)∥<ε\|\nabla f(\vec x_{k})\|<\varepsilon, la seule quantité calculable sans connaître le minimum.

Les pièges qui coûtent des points

Les erreurs ci-dessous sont celles que je corrige le plus souvent en séance. Chacune coûte des points sur une copie, même quand le raisonnement est juste.

1. Oublier le signe moins de l'itération

toute la méthode, même si le point final est juste

Ce qu'il ne faut pas écrire

« x⃗1=x⃗0+t∇f(x⃗0)\vec x_{1}=\vec x_{0}+t\nabla f(\vec x_{0}), et φ\varphi est minimale en t=−14t=-\frac{1}{4}. »

Ce qu'il faut écrire

« x⃗1=x⃗0−t∇f(x⃗0)\vec x_{1}=\vec x_{0}-t\nabla f(\vec x_{0}) avec t>0t>0 ; contrôle : φ′(0)=−∥∇f(x⃗0)∥2<0\varphi'(0)=-\|\nabla f(\vec x_{0})\|^{2}<0. »

Pourquoi : Un pas optimal NÉGATIF est le symptôme : on est parti dans la direction de plus forte montée. Deux erreurs de signe qui se compensent donnent le bon point, et le correcteur retire quand même les points de la méthode.

2. Prendre la matrice des coefficients pour la hessienne

2 points, et aucune itération juste ensuite

Ce qu'il ne faut pas écrire

« f=2x2−3xy+3y2=x⃗⋅Ax⃗f=2x^{2}-3xy+3y^{2}=\vec x\cdot A\vec x avec A=(2−32−323)A=\begin{pmatrix}2&-\frac{3}{2}\\-\frac{3}{2}&3\end{pmatrix}, donc t0=g⃗⋅g⃗g⃗⋅Ag⃗=12t_{0}=\frac{\vec g\cdot\vec g}{\vec g\cdot A\vec g}=\frac{1}{2}. »

Ce qu'il faut écrire

« H=(4−3−36)=2AH=\begin{pmatrix}4&-3\\-3&6\end{pmatrix}=2A (dérivées secondes), donc t0=40160=14t_{0}=\frac{40}{160}=\frac{1}{4}. »

Pourquoi : Depuis (2 ;2)(2\,;2), le pas doublé mène en (1 ;−1)(1\,;-1) où f=8=f(x⃗0)f=8=f(\vec x_{0}) : φ\varphi est une parabole symétrique autour de t0t_{0}, donc φ(2t0)=φ(0)\varphi(2t_{0})=\varphi(0). Aucun progrès, et la copie ne s'en aperçoit pas sans calculer ff.

3. Prendre une baisse au premier pas pour une preuve de convergence

toute la question de convergence

Ce qu'il ne faut pas écrire

« Avec t=0,3t=0{,}3 sur f=x2+4y2f=x^{2}+4y^{2}, ff passe de 1010 à 3,43{,}4 : le pas convient. »

Ce qu'il faut écrire

« Les facteurs sont 1−2t=0,41-2t=0{,}4 et 1−8t=−1,41-8t=-1{,}4 ; ∣−1,4∣>1|-1{,}4|>1, donc yky_{k} diverge. Il faut 0<t<140<t<\frac{1}{4}. »

-11234-2-1,5-1-0,50,511,52x₀x₁x₂x₃
Le trajet traverse la vallée en s'élargissant : xkx_{k} fond, mais ∣yk∣|y_{k}| est multiplié par 1,41{,}4 à chaque pas, et ff remonte dès x⃗2\vec x_{2}.

Pourquoi : Le premier pas gagne sur xx, qui pesait lourd, et perd sur yy. Ensuite ff vaut 4,0724{,}072 puis environ 7,577{,}57 : les itérés sautent d'un bord à l'autre de la vallée, toujours plus haut.

4. Croire que le meilleur pas mène au minimum

1 à 2 points d'interprétation

Ce qu'il ne faut pas écrire

« Avec la recherche exacte, on atteint le minimum de x2+2y2x^{2}+2y^{2} en un pas depuis (2 ;1)(2\,;1). »

Ce qu'il faut écrire

« Le pas exact t0=13t_{0}=\frac{1}{3} donne (23 ;−13)\left(\frac{2}{3}\,;-\frac{1}{3}\right), où f=23f=\frac{2}{3} : c'est le minimum SUR LA DROITE de recherche, pas dans le plan. »

Pourquoi : La droite de recherche ne passe par le minimum que si −∇f-\nabla f le vise. Ici ff est divisée par 99 à chaque pas, sans jamais atteindre 00.

5. Normaliser la direction et garder le même pas

1 point par itération

Ce qu'il ne faut pas écrire

« Sur x2+y2x^{2}+y^{2} depuis (−6 ;8)(-6\,;8), le pas optimal vaut 12\frac{1}{2}, donc j'avance de 12\frac{1}{2} selon 120(6 ;−8)\frac{1}{20}(6\,;-8). »

Ce qu'il faut écrire

« Avec −∇f=(12 ;−16)-\nabla f=(12\,;-16), t=12t=\frac{1}{2} ; avec le vecteur unitaire, le pas devient s=∥∇f∥ t=10s=\|\nabla f\|\,t=10. Le point d'arrivée, l'origine, est le même. »

Pourquoi : Le nombre tt dépend de la longueur du vecteur direction, le point x⃗k+1\vec x_{k+1} non. Respectez la convention de l'énoncé, x⃗k−t∇f(x⃗k)\vec x_{k}-t\nabla f(\vec x_{k}) sans normaliser.

6. Prendre un petit gradient pour la proximité du minimum

1 point d'interprétation

Ce qu'il ne faut pas écrire

« ∥∇f(x⃗k)∥<10−2\|\nabla f(\vec x_{k})\|<10^{-2}, donc x⃗k\vec x_{k} est à moins de 10−210^{-2} du minimum. »

Ce qu'il faut écrire

« Le critère dit que la pente est faible ; sur x21000+y2\frac{x^{2}}{1000}+y^{2}, le point (1 ;0)(1\,;0) a un gradient de norme 0,0020{,}002 et se trouve à distance 11 du minimum. »

Pourquoi : Une fonction très plate dans une direction a un petit gradient loin de son minimum. Le critère est un critère d'ARRÊT pratique, pas une garantie de précision sur x⃗\vec x.

7. Prendre le point d'arrêt pour un minimum

2 points de classification

Ce qu'il ne faut pas écrire

« Sur f(x,y)=xyf(x,y)=xy depuis (1 ;1)(1\,;1), la méthode arrive en (0 ;0)(0\,;0) où ∇f=0⃗\nabla f=\vec 0 : c'est le minimum. »

Ce qu'il faut écrire

« φ(t)=(1−t)2\varphi(t)=(1-t)^{2} donne t=1t=1 et (0 ;0)(0\,;0), point CRITIQUE ; D=0×0−12=−1<0D=0\times 0-1^{2}=-1<0 : c'est un point de selle. »

Pourquoi : La méthode s'arrête où le gradient s'annule, c'est-à-dire en un point critique ; elle ne le classe pas. Le test des dérivées secondes reste à faire, et f(1 ;−1)=−1<0f(1\,;-1)=-1<0 le confirme.

8. Annoncer le minimum après deux itérations

1 point de conclusion

Ce qu'il ne faut pas écrire

« Après deux pas, x⃗2=(34 ;34)\vec x_{2}=\left(\frac{3}{4}\,;\frac{3}{4}\right) : c'est le minimum de 2x2−3xy+3y22x^{2}-3xy+3y^{2}. »

Ce qu'il faut écrire

« ∇f(x⃗2)=(34 ;94)≠0⃗\nabla f(\vec x_{2})=\left(\frac{3}{4}\,;\frac{9}{4}\right)\neq\vec 0 : on n'y est pas. Le minimum exact, par ∇f=0⃗\nabla f=\vec 0, est (0 ;0)(0\,;0), et f(x⃗2)=98f(\vec x_{2})=\frac{9}{8}. »

Pourquoi : Sur une quadratique non circulaire, la méthode du gradient n'atteint pas le minimum en un nombre fini de pas : elle s'en approche à vitesse constante. Calculer le gradient au dernier itéré est la vérification qui coûte cinq secondes.

Quelle méthode choisir

Comment trouver le pas selon l'énoncé

Regardez la forme de f et ce que l'énoncé impose.

  • Si ff quadratique, « recherche linéaire exacte » → tk=g⃗⋅g⃗g⃗⋅Hg⃗t_{k}=\frac{\vec g\cdot\vec g}{\vec g\cdot H\vec g} avec la hessienne, ou φ′(t)=0\varphi'(t)=0 sur la parabole φ\varphi

    Exemple : 2x2−3xy+3y22x^{2}-3xy+3y^{2} en (2 ;2)(2\,;2) : g⃗=(2 ;6)\vec g=(2\,;6), t0=40160=14t_{0}=\frac{40}{160}=\frac{1}{4}

  • Si ff non quadratique, « recherche linéaire exacte » → écrire φ(t)\varphi(t), chercher une racine évidente de φ′\varphi', puis prouver qu'elle est unique (monotonie de φ′\varphi')

    Exemple : φ′(t)=128t3+8t−4\varphi'(t)=128t^{3}+8t-4, croissante, racine 14\frac{1}{4}

  • Si « pas fixe tt », ff de la forme ax2+by2ax^{2}+by^{2} → écrire les facteurs 1−2at1-2at et 1−2bt1-2bt et comparer leurs valeurs absolues à 11

    Exemple : x2+4y2x^{2}+4y^{2}, t=0,3t=0{,}3 : facteurs 0,40{,}4 et −1,4-1{,}4, divergence

  • Si « choisir le meilleur pas fixe » → égaler les valeurs absolues des deux facteurs extrêmes

    Exemple : x2+4y2x^{2}+4y^{2} : 1−2t=8t−11-2t=8t-1, t=15t=\frac{1}{5}, facteur 35\frac{3}{5}

La méthode de Newton à plusieurs variables est hors du cours : on ne remplace jamais t∇ft\nabla f par H−1∇fH^{-1}\nabla f.

Que prévoir en lisant la carte de contour

Regardez la forme des courbes de niveau et la position du point de départ.

  • Si des cercles → le gradient vise le centre : un pas exact suffit

    Exemple : x2+y2x^{2}+y^{2} depuis (−6 ;8)(-6\,;8) : t=12t=\frac{1}{2}, arrivée en (0 ;0)(0\,;0)

  • Si des ellipses, départ sur un axe → un pas exact suffit aussi

    Exemple : x2+2y2x^{2}+2y^{2} depuis (3 ;0)(3\,;0) : ∇f=(6 ;0)\nabla f=(6\,;0), t=12t=\frac{1}{2}, arrivée en (0 ;0)(0\,;0)

  • Si des ellipses allongées, départ quelconque → zigzag à angles droits, convergence lente

    Exemple : x2+2y2x^{2}+2y^{2} depuis (2 ;1)(2\,;1) : ff divisée par 99 à chaque pas

  • Si une vallée courbe (bananes) → progrès rapide vers le fond, puis lent le long du fond

    Exemple : 2(x2−y)2+(1−x)22(x^{2}-y)^{2}+(1-x)^{2} : le fond est la parabole y=x2y=x^{2}

La rédaction attendue

Le correcteur coche des étapes. Les voici dans l'ordre, avec la phrase de conclusion qu'il attend mot pour mot.

Une itération avec recherche linéaire exacte

Quand l'utiliser : L'énoncé dit « effectuez une itération de la méthode du gradient avec recherche linéaire exacte ».

  1. 1 Calculer ∇f(x⃗k)\nabla f(\vec x_{k}) et l'écrire ; s'il est nul, s'arrêter : x⃗k\vec x_{k} est un point critique.
  2. 2 Écrire le point courant x⃗k−t∇f(x⃗k)\vec x_{k}-t\nabla f(\vec x_{k}), puis φ(t)\varphi(t) développée (ou la formule du pas si ff est quadratique, avec la HESSIENNE).
  3. 3 Résoudre φ′(t)=0\varphi'(t)=0 et justifier que c'est un minimum : φ′′>0\varphi''>0, ou g⃗⋅Hg⃗>0\vec g\cdot H\vec g>0.
  4. 4 Donner x⃗k+1\vec x_{k+1} et f(x⃗k+1)f(\vec x_{k+1}), et vérifier que ff a baissé.
  5. 5 Contrôler l'orthogonalité ∇f(x⃗k+1)⋅∇f(x⃗k)=0\nabla f(\vec x_{k+1})\cdot\nabla f(\vec x_{k})=0.

Phrase de conclusion

« Le pas optimal est tk=…>0t_{k}=…>0, minimum de φ\varphi car φ′′(t)>0\varphi''(t)>0 ; donc x⃗k+1=…\vec x_{k+1}=… et f(x⃗k+1)=…<f(x⃗k)f(\vec x_{k+1})=…<f(\vec x_{k}), avec ∇f(x⃗k+1)⊥∇f(x⃗k)\nabla f(\vec x_{k+1})\perp\nabla f(\vec x_{k}). »

Le piège : La troisième étape : un pas sans justification de minimum est un point critique de φ, pas encore un minimum.

Barème : Gradient 1 point, φ ou formule 1 point, pas justifié 1 point, nouvel itéré et valeur 1 point.

Démontrer que deux gradients successifs sont orthogonaux

Quand l'utiliser : L'énoncé demande de prouver le virage à angle droit de la recherche exacte.

  1. 1 Poser φ(t)=f(x⃗k−tg⃗k)\varphi(t)=f\left(\vec x_{k}-t\vec g_{k}\right) avec g⃗k=∇f(x⃗k)\vec g_{k}=\nabla f(\vec x_{k}).
  2. 2 Dériver par la règle de dérivation en chaîne : φ′(t)=−∇f(x⃗k−tg⃗k)⋅g⃗k\varphi'(t)=-\nabla f\left(\vec x_{k}-t\vec g_{k}\right)\cdot\vec g_{k}.
  3. 3 Écrire que tk>0t_{k}>0 est un minimum intérieur, donc φ′(tk)=0\varphi'(t_{k})=0.
  4. 4 Conclure : ∇f(x⃗k+1)⋅g⃗k=0\nabla f(\vec x_{k+1})\cdot\vec g_{k}=0.

Phrase de conclusion

« Comme tkt_{k} minimise φ\varphi sur ]0 ;+∞[]0\,;+\infty[, φ′(tk)=−∇f(x⃗k+1)⋅∇f(x⃗k)=0\varphi'(t_{k})=-\nabla f(\vec x_{k+1})\cdot\nabla f(\vec x_{k})=0 : les deux gradients sont orthogonaux. »

Le piège : Écrire la conclusion sans la règle de dérivation en chaîne : c'est elle que le correcteur note.

Vérifier avant de rendre

Cinq minutes de vérification récupèrent plus de points qu'un exercice de plus commencé à la hâte.

L'exercice type décortiqué

Deux itérations sur f(x,y)=2x2−3xy+3y2f(x,y)=2x^{2}-3xy+3y^{2}

Effectuez deux itérations de la méthode du gradient avec recherche linéaire exacte, à partir de x⃗0=(2 ;2)\vec x_{0}=(2\,;2). Comparez au minimum exact.

-3-2-1123-2,5-2-1,5-1-0,50,511,522,5x₀f = 8
Les courbes de niveau sont des ellipses inclinées et x⃗0\vec x_{0} n'est sur aucun de leurs axes : il faudra plusieurs pas.

Étape 1

∇f=(4x−3y ;−3x+6y)\nabla f=(4x-3y\,;-3x+6y), donc g⃗0=∇f(2 ;2)=(2 ;6)\vec g_{0}=\nabla f(2\,;2)=(2\,;6) et f(x⃗0)=8f(\vec x_{0})=8. Hessienne H=(4−3−36)H=\begin{pmatrix}4&-3\\-3&6\end{pmatrix}.

Pourquoi

Écrire la hessienne avant tout calcul de pas évite le piège du facteur 2.

Étape 2

φ(t)=f(2−2t ;2−6t)=80t2−40t+8\varphi(t)=f(2-2t\,;2-6t)=80t^{2}-40t+8, minimale en t0=14t_{0}=\frac{1}{4} (φ′′=160>0\varphi''=160>0). Formule : g⃗⋅g⃗g⃗⋅Hg⃗=40160\frac{\vec g\cdot\vec g}{\vec g\cdot H\vec g}=\frac{40}{160}.

Pourquoi

Les deux chemins donnent le même pas ; φ′(0)=−40=−∥g⃗0∥2\varphi'(0)=-40=-\|\vec g_{0}\|^{2} contrôle le signe.

Étape 3

x⃗1=(2 ;2)−14(2 ;6)=(32 ;12)\vec x_{1}=(2\,;2)-\frac{1}{4}(2\,;6)=\left(\frac{3}{2}\,;\frac{1}{2}\right), f(x⃗1)=92−94+34=3f(\vec x_{1})=\frac{9}{2}-\frac{9}{4}+\frac{3}{4}=3.

Pourquoi

On recalcule f dans f, pas dans φ : c'est la vérification de la baisse, de 8 à 3.

Étape 4

g⃗1=(6−32 ;−92+3)=(92 ;−32)\vec g_{1}=\left(6-\frac{3}{2}\,;-\frac{9}{2}+3\right)=\left(\frac{9}{2}\,;-\frac{3}{2}\right), et g⃗0⋅g⃗1=9−9=0\vec g_{0}\cdot\vec g_{1}=9-9=0.

Pourquoi

L'angle droit est attendu ; s'il manque, une erreur précède.

Étape 5

g⃗1⋅g⃗1=452\vec g_{1}\cdot\vec g_{1}=\frac{45}{2}, Hg⃗1=(452 ;−452)H\vec g_{1}=\left(\frac{45}{2}\,;-\frac{45}{2}\right), g⃗1⋅Hg⃗1=135\vec g_{1}\cdot H\vec g_{1}=135, donc t1=16t_{1}=\frac{1}{6} et x⃗2=(34 ;34)\vec x_{2}=\left(\frac{3}{4}\,;\frac{3}{4}\right), f(x⃗2)=98f(\vec x_{2})=\frac{9}{8}.

-3-2-1123-2,5-2-1,5-1-0,50,511,522,5x₀x₁x₂

Pourquoi

Le pas change d'une itération à l'autre (14\frac{1}{4} puis 16\frac{1}{6}) : la recherche exacte s'adapte à la courbure de chaque direction.

Étape 6

∇f=0⃗\nabla f=\vec 0 donne 4x=3y4x=3y et 3x=6y3x=6y, d'où (0 ;0)(0\,;0), minimum car 4>04>0 et det⁡H=15>0\det H=15>0. Et x⃗2=38x⃗0\vec x_{2}=\frac{3}{8}\vec x_{0} : ff est multipliée par 38\frac{3}{8} à chaque pas.

Pourquoi

La comparaison au minimum exact mesure la vitesse de la méthode, c'est la question qui suit toujours à l'examen.

Conclusion rédigée

« Après deux itérations, x⃗2=(34 ;34)\vec x_{2}=\left(\frac{3}{4}\,;\frac{3}{4}\right) et f(x⃗2)=98f(\vec x_{2})=\frac{9}{8}, contre f∗=0f^{*}=0 en (0 ;0)(0\,;0) ; chaque itération multiplie ff par 38\frac{3}{8}, la méthode converge sans atteindre le minimum. »

L'erreur classique sur cet exercice : Calculer le pas avec A=(2−32−323)A=\begin{pmatrix}2&-\frac{3}{2}\\-\frac{3}{2}&3\end{pmatrix} : on trouve 12\frac{1}{2} et l'on arrive en (1 ;−1)(1\,;-1), où ff vaut encore 88.

À savoir par cœur

  • • x⃗k+1=x⃗k−tk∇f(x⃗k)\vec x_{k+1}=\vec x_{k}-t_{k}\nabla f(\vec x_{k}), avec tk>0t_{k}>0 : le signe MOINS, toujours.
  • • φ(t)=f(x⃗k−t∇f(x⃗k))\varphi(t)=f\left(\vec x_{k}-t\nabla f(\vec x_{k})\right) et φ′(0)=−∥∇f(x⃗k)∥2\varphi'(0)=-\|\nabla f(\vec x_{k})\|^{2}.
  • • Quadratique : tk=g⃗⋅g⃗g⃗⋅Hg⃗t_{k}=\frac{\vec g\cdot\vec g}{\vec g\cdot H\vec g}, avec la HESSIENNE, celle des dérivées secondes.
  • • Recherche exacte : deux gradients successifs sont ORTHOGONAUX ; en dimension deux, les directions kk et k+2k+2 sont parallèles.
  • • Pas fixe sur x2+κy2x^{2}+\kappa y^{2} : facteurs 1−2t1-2t et 1−2κt1-2\kappa t, convergence si et seulement si les deux sont dans ]−1 ;1[]-1\,;1[.
  • • Zigzag sur x2+κy2x^{2}+\kappa y^{2} depuis (κ ;1)(\kappa\,;1) : ff multipliée par (κ−1κ+1)2\left(\frac{\kappa-1}{\kappa+1}\right)^{2} à chaque pas.
  • • Arrêt : ∥∇f∥<ε\|\nabla f\|<\varepsilon, en un point CRITIQUE qu'il reste à classer.

Questions fréquentes

Pourquoi la méthode du gradient avance-t-elle en zigzag ?

Parce qu'avec la recherche linéaire exacte, on s'arrête sur chaque droite au point où elle devient tangente à une courbe de niveau. Le nouveau gradient y est perpendiculaire à la droite, donc chaque pas tourne d'un angle droit par rapport au précédent. Dans une vallée allongée, ces virages successifs font un zigzag serré et lent vers le minimum.

Comment calculer le pas optimal à la main pour une fonction quadratique ?

On calcule le gradient g au point courant et la matrice hessienne H, celle des dérivées secondes. Le pas optimal vaut g scalaire g divisé par g scalaire H fois g. On peut aussi écrire la fonction phi de t le long de la droite de recherche, qui est une parabole, et prendre son sommet. Les deux calculs doivent donner le même nombre.

Pourquoi la méthode diverge-t-elle avec un pas fixe trop grand ?

Parce que la direction de descente ne garantit une baisse que pour un petit pas. Sur une fonction comme x carré plus kappa y carré, chaque coordonnée est multipliée à chaque pas par un facteur constant, un moins deux t et un moins deux kappa t. Si l'un de ces facteurs dépasse un en valeur absolue, la coordonnée grandit et les itérés s'éloignent du minimum.

Quand faut-il arrêter la méthode du gradient ?

On s'arrête quand la norme du gradient passe sous une tolérance fixée d'avance, par exemple un millième, parce que c'est la seule quantité calculable sans connaître le minimum. Ce critère ne garantit pas que le point soit proche du minimum, et le point atteint est seulement un point critique : il faut encore le classer, par le test des dérivées secondes.

Passer à la pratique

Exercices corrigés : La méthode du gradient

Une méthode se prouve sur une copie, pas sur une fiche. La série du même chapitre reprend chacun de ces pièges dans un exercice, avec le corrigé rédigé étape par étape.

  • 10 exercices corrigés
  • 100 points
  • 150 minutes
Faire les exercices
Il manque quelque chose dans cette fiche ? Une méthode, un piège, un exercice pour l'appliquer, une erreur repérée : dis-le-moi, je lis chaque demande.

L'envoi passe par ton espace gratuit : c'est ce qui me permet de te répondre et de te prévenir quand l'exercice est ajouté. Un courriel suffit, pas de mot de passe. Crée ton espace. Pas envie de créer un compte ? Écris-moi directement.

De quoi s'agit-il ?
Je lis chaque demande moi-même, personne d'autre ne la voit. Inutile d'écrire ton nom ou celui de ton école.
Quand ta demande est traitée, tu es prévenu par courriel et dans ton espace.

En envoyant, tu acceptes que je lise ta demande pour y répondre. Elle est gardée avec ton compte, effacée avec lui, et jamais publiée : politique de confidentialité.

Fiche précédente Extrema et optimisation sans contrainte Fiche suivante Les multiplicateurs de Lagrange

© Ahmed Squalli Houssaini. Fiche publiée sur www.letuteurscientifique.ca/fiches/mth1101-methode-gradient. Libre pour l'usage personnel et en classe ; sa republication ailleurs demande une autorisation écrite (mentions légales).

Voir aussi

Toutes les fiches Tous les exercices Tuteur de mathématiques

Vous cherchez un tuteur à Montréal pour ce chapitre ?

Contactez-moi pour une première séance. On reprend les points de méthode qui font perdre des points en évaluation, puis on les met à l'épreuve sur des exercices du niveau réel de l'examen.

Me contacter WhatsApp
Site par Studio Squalli