Calcul I MTH1101 • Polytechnique Montréal • La méthode du gradient
La méthode du gradient : exercices corrigés de MTH1101 (Polytechnique)
La méthode du gradient : exercices de MTH1101 (Polytechnique)
Nom : Classe : Date :
Corrigé
Durée conseillée : 2 h 30 · Sans calculatrice · 10 exercices https://www.letuteurscientifique.ca/exercices/mth1101-methode-gradient
Voici dix exercices corrigés sur la méthode du gradient, l'algorithme d'optimisation de la section 5.2 de Stewart, *Calcul à plusieurs variables* (« Optimisation sans contraintes, recherche linéaire et méthode du gradient »), que le cours MTH1101 de Polytechnique Montréal appuie sur les notes du professeur, après les extrema sans contrainte et avant les multiplicateurs de Lagrange.
Ce que couvre la série, les pièges traités
Le chapitre est évalué à l'examen final. On ne cherche plus le minimum en résolvant ∇f=0 : on part d'un point et on descend, xk+1=xk−tk∇f(xk), comme le font les logiciels d'ingénierie et d'apprentissage automatique.
Le fil de la série : −∇f dit où la pente est la plus raide ICI, pas où se trouve le minimum. La méthode est donc un ALGORITHME qui corrige sa direction à chaque pas, et le pas t se CHOISIT : trop grand, il fait remonter ou diverger ; exact, il impose un virage à angle droit, d'où le zigzag dans une vallée allongée.
Les pièges nommés en chemin : le signe moins oublié, un pas négatif qui trahit la mauvaise direction, la matrice des coefficients prise pour la hessienne (le pas doublé ne fait aucun progrès), une baisse au premier pas prise pour une preuve de convergence, un petit gradient pris pour la proximité du minimum, un point de selle pris pour un minimum. Tout se fait sans calculatrice, comme à l'examen, où le seul document permis est votre aide-mémoire d'une feuille recto verso : les fonctions sont choisies pour que les itérés tombent en fractions.
Faites chaque exercice au complet avant d'ouvrir la correction : c'est en cherchant qu'on apprend, pas en lisant la solution.
Tes séries en favori t'attendent dans ton espace, du téléphone à l'ordinateur. C'est gratuit : un courriel suffit, sans mot de passe, et tu reviens ici.
Le devoir sans corrigé, un exercice par page, et le corrigé à part : c'est dans ton espace gratuit. Un courriel suffit, sans mot de passe, et tu reviens ici.
•QUADRATIQUE f(x)=21x⋅Hx−b⋅x+c, H la hessienne, g=∇f(xk) : tk=g⋅Hgg⋅g, et f baisse de 2g⋅Hg(g⋅g)2.
•ORTHOGONALITÉ : en recherche exacte, ∇f(xk+1)⋅∇f(xk)=0 ; la droite de recherche est tangente à une courbe de niveau au point d'arrivée.
•PAS FIXE sur x2+κy2 : chaque coordonnée est multipliée par 1−2t et 1−2κt ; convergence si et seulement si 0<t<κ1 (pour κ≥1).
•ZIGZAG : sur x2+κy2 depuis (κ;1), f est multipliée par (κ+1κ−1)2 à chaque pas ; des cercles (κ=1) donnent le minimum en un pas.
•ARRÊT : ∥∇f(xk)∥<ε. On s'arrête en un point CRITIQUE, qui reste à classer, et un petit gradient ne garantit pas la proximité du minimum.
Partie A : les bases (/50)
Exercice 1 : La direction de plus forte descente, et le pas qui fait remonter
10 réponses vérifiables
On cherche le minimum de f(x,y)=x2+4y2 par la méthode du gradient. Partant d'un point xk, la méthode se déplace dans la direction −∇f(xk) : xk+1=xk−t∇f(xk), où le nombre t>0 s'appelle le PAS.
La figure donne les courbes de niveau f=2, f=8 et f=18, et le point de départ P(2;1), qui est sur la courbe f=8.
a) Calculez ∇f(P) et sa norme, au centième.
b) Donnez le vecteur unitaire u de plus forte descente en P et la dérivée directionnelle Duf(P), au centième. La direction −∇f(P) pointe-t-elle vers le minimum (0;0) ? Justifiez, puis dites ce que la figure montre.
c) Faites un pas avec t=101 : donnez x1 et f(x1).
d) Refaites ce pas avec t=21 et calculez f(x1). En étudiant φ(t)=f(P−t∇f(P)), trouvez tous les pas t>0 qui font réellement descendre.
Voir la correction
Réponses
a)∇f(P)=(4;8), ∥∇f(P)∥=45≈8,94
b)u=−51(1;2), Duf(P)=−45≈−8,94 ; non, la droite de descente passe par (0;−3), pas par l'origine
∂x∂f=2x et ∂y∂f=8y, donc ∇f(P)=(4;8) et ∥∇f(P)∥=16+64=80=45≈8,94. Le gradient a une composante en y double de celle en x alors que P est deux fois plus loin de l'axe des ordonnées que de l'axe des abscisses : c'est le facteur 4 devant y2 qui rend la fonction quatre fois plus « raide » dans la direction y.
b)
La plus forte descente se fait dans la direction opposée au gradient : u=−∥∇f(P)∥∇f(P)=−51(1;2), et le taux de variation y vaut Duf(P)=∇f(P)⋅u=−∥∇f(P)∥=−45≈−8,94. Cette direction ne vise PAS le minimum. La droite de descente est (2−s;1−2s) : elle coupe l'axe des ordonnées en s=2, au point (0;−3), et ne passe jamais par l'origine, puisque 2−s=0 et 1−2s=0 demandent deux valeurs de s différentes. La direction vers le minimum serait (−2;−1). Sur la figure, −∇f(P) est perpendiculaire à la courbe de niveau f=8 en P (chapitre du gradient), et comme l'ellipse est aplatie, cette perpendiculaire plonge vers l'axe des abscisses au lieu de viser le centre. C'est tout le fil du chapitre : −∇f est la meilleure direction LOCALE, pas la bonne direction GLOBALE, et c'est pourquoi la méthode a besoin de plusieurs pas.
c)
x1=(2;1)−101(4;8)=(58;51), et f(x1)=2564+4×251=2568=2,72. La valeur passe de 8 à 2,72 : le pas a fait descendre, et bien. Remarquez que x1 est déjà proche de l'axe des abscisses : la coordonnée y, la plus pénalisée, a été corrigée en premier.
d)
x1=(2;1)−21(4;8)=(0;−3) et f(x1)=36 : on a REMONTÉ de 8 à 36, en partant pourtant dans la direction de plus forte descente. La dérivée directionnelle négative ne garantit la descente que pour un pas assez petit, parce qu'elle décrit f AU POINT P. Pour savoir jusqu'où on peut aller, on étudie la fonction d'une variable φ(t)=f(2−4t;1−8t)=(2−4t)2+4(1−8t)2=272t2−80t+8. Alors φ(t)<8⟺272t2−80t<0⟺8t(34t−10)<0⟺0<t<175, avec 175≈0,294. Le pas 101 est dans cet intervalle, le pas 21 en sort. φ est une parabole tournée vers le haut, de sommet t=345, exactement au milieu de l'intervalle : un pas DEUX fois trop grand ramène au niveau de départ, un pas plus grand encore fait monter. Cette fonction φ est l'outil central du chapitre : la recherche linéaire exacte consiste à prendre son minimum.
Les points se gagnent avant la correction ; après, tu peux encore t'entraîner.
Pour toi :
Coche ici les exercices faits ou à revoir : un compte gratuit, sans mot de passe, retient tes coches et tes réponses justes d'une visite à l'autre, te dit quel chapitre attaquer ensuite et te permet de demander l'exercice qui te manque. Crée ton espace, un courriel suffit.
Exercice 2 : Une itération avec recherche linéaire exacte
13 réponses vérifiables
Soit f(x,y)=x2−2xy+2y2−2x−2y et le point de départ x0=(0;1).
Une itération de la méthode du gradient avec RECHERCHE LINÉAIRE EXACTE choisit le pas t0 qui minimise la fonction d'une variable φ(t)=f(x0−t∇f(x0)) pour t≥0, puis pose x1=x0−t0∇f(x0).
a) Calculez ∇f(x,y), puis ∇f(x0) et f(x0).
b) Écrivez φ(t) sous forme développée et déterminez le pas optimal t0. Justifiez qu'il s'agit bien d'un minimum.
c) Donnez x1 et f(x1), puis calculez le produit scalaire ∇f(x0)⋅∇f(x1).
d) Un élève écrit x0+t∇f(x0) au lieu de x0−t∇f(x0), minimise sa fonction de t et trouve t=−41. Que s'est-il passé, et à quel point arrive-t-il s'il garde ce t ?
e) Trouvez le minimum exact x∗ de f en résolvant ∇f=0, et la valeur f∗. Par quel facteur l'écart f−f∗ a-t-il été multiplié en une itération ?
Voir la correction
Réponses
a)∇f=(2x−2y−2;−2x+4y−2), ∇f(x0)=(−4;2), f(x0)=0
b)φ(t)=40t2−20t, t0=41 (φ′′=80>0)
c)x1=(1;21), f(x1)=−25, ∇f(x1)=(−1;−2), produit scalaire 0
d)Il a suivi +∇f, la montée ; t=−41 redonne le même point (1;21)
e)x∗=(3;2), f∗=−5 ; l'écart passe de 5 à 25, facteur 21
a)
∂x∂f=2x−2y−2 et ∂y∂f=−2x+4y−2. En x0=(0;1) : ∇f(x0)=(0−2−2;0+4−2)=(−4;2), et f(x0)=2−2=0. La direction de descente est donc −∇f(x0)=(4;−2) : on part vers la droite et vers le bas.
b)
Le point courant de la droite de recherche est x0−t∇f(x0)=(4t;1−2t). On substitue : φ(t)=16t2−2(4t)(1−2t)+2(1−2t)2−8t−2(1−2t), soit 16t2−8t+16t2+2−8t+8t2−8t−2+4t=40t2−20t. Alors φ′(t)=80t−20 s'annule en t0=41, et φ′′(t)=80>0 : c'est le minimum de la parabole, donc le minimum de φ sur [0;+∞[. Contrôle utile : φ(0)=0=f(x0), et φ′(0)=−20=−∥∇f(x0)∥2, négatif comme il se doit en direction de descente. Le piège de ce calcul est purement algébrique : un signe perdu dans −2(4t)(1−2t) déplace le sommet, et toute la suite est fausse. Développez lentement.
c)
x1=(0;1)−41(−4;2)=(1;21) et f(x1)=φ(41)=1640−5=−25 ; on recalcule directement : 1−1+21−2−1=−25. Puis ∇f(x1)=(2−1−2;−2+2−2)=(−1;−2) et ∇f(x0)⋅∇f(x1)=(−4)(−1)+(2)(−2)=0. Les deux gradients sont ORTHOGONAUX : ce n'est pas une coïncidence, c'est la propriété de la recherche exacte, démontrée à l'exercice 5. Au point où l'on s'arrête, la droite de recherche est tangente à une courbe de niveau, donc le nouveau gradient lui est perpendiculaire, et le pas suivant tourne d'un angle droit.
d)
Avec x0+t∇f(x0)=(−4t;1+2t), la fonction devient 40t2+20t, de minimum en t=−41. Un pas NÉGATIF est le signal d'alarme : l'élève a pris la direction de plus forte MONTÉE, et sa fonction de t ne fait que monter pour t>0. S'il garde t=−41, il arrive en (−4t;1+2t)=(1;21), le même point : deux erreurs de signe se sont compensées. Sur une copie, ce n'est pas un calcul juste, c'est une méthode fausse ; le correcteur retire les points de la méthode. Retenez le contrôle : φ′(0) doit valoir −∥∇f∥2<0, et le pas optimal doit être positif.
e)
∇f=0 donne 2x−2y=2 et −2x+4y=2 ; en additionnant, 2y=4, donc y=2 et x=3. La hessienne a fxx=2>0 et D=2×4−(−2)2=4>0 : c'est un minimum, et même le minimum global d'une quadratique à hessienne définie positive. f∗=f(3;2)=9−12+8−6−4=−5. L'écart à l'optimum valait f(x0)−f∗=5 et vaut −25+5=25 après une itération : il a été divisé par 2. Une seconde itération, à partir de ∇f(x1)=(−1;−2), donnerait le pas 21, le point x2=(23;23) et f(x2)=−415 : l'écart vaut 45, encore divisé par 2. La méthode s'approche du minimum sans jamais l'atteindre exactement, et c'est la comparaison avec f∗ qui mesure sa vitesse.
Les points se gagnent avant la correction ; après, tu peux encore t'entraîner.
Pour toi :
Exercice 3 : Le pas optimal par la formule, et le facteur 2 de la hessienne
14 réponses vérifiables
Pour une fonction quadratique dont la hessienne est H, la recherche linéaire exacte a une formule : en notant g=∇f(xk), le pas optimal est tk=g⋅Hgg⋅g (on l'admet ici ; l'exercice 5 la démontre).
On l'applique à f(x,y)=x2+2xy+3y2, dont le minimum est (0;0), à partir de x0=(3;0).
a) Écrivez la hessienne H de f sous forme de tableau 2×2.
b) Calculez ∇f(x0), le pas t0 par la formule, le point x1 et f(x1).
c) Un élève écrit f(x)=x⋅Ax avec A=(1113), et met A à la place de H dans la formule. Quel pas trouve-t-il, et que vaut f au point où il arrive ? Expliquez le résultat avec la parabole φ.
d) Faites la deuxième itération : ∇f(x1), t1, x2 et f(x2).
e) Comparez x2 à x0 et déduisez-en f(xk) pour tout k. Après combien d'itérations a-t-on, pour la première fois, f(xk)<10−4 ?
c)t=31, double du bon ; il arrive en (1;−2) où f=9=f(x0) : aucun progrès
d)∇f(x1)=(2;−2), t1=21, x2=(1;0), f(x2)=1
e)x2=31x0, f(xk)=3k9 ; f(xk)<10−4 dès k=11
a)
fxx=2, fxy=fyx=2 et fyy=6, donc H=(2226). Les coefficients de f sont 1, 2 et 3 ; ceux de H sont leurs dérivées secondes, ce qui DOUBLE les termes carrés (x2 donne 2, 3y2 donne 6) et garde le terme croisé (2xy donne 2). C'est exactement l'endroit où la question c) va piéger.
b)
∇f=(2x+2y;2x+6y), donc ∇f(x0)=(6;6). Puis g⋅g=72, Hg=(12+12;12+36)=(24;48) et g⋅Hg=144+288=432, d'où t0=43272=61. Alors x1=(3;0)−61(6;6)=(2;−1) et f(x1)=4−4+3=3. Contrôle par φ : φ(t)=f(3−6t;−6t)=216t2−72t+9, de sommet t=43272=61, le même. La formule évite de développer φ, mais elle exige la vraie hessienne.
c)
Avec A : Ag=(12;24) et g⋅Ag=216, d'où t=21672=31, exactement le double du bon pas, puisque H=2A. Le point obtenu est (3;0)−31(6;6)=(1;−2), et f(1;−2)=1−4+12=9 : la valeur de DÉPART. Aucun progrès, ce qui s'explique sans calcul : φ est une parabole symétrique autour de son sommet t0, donc φ(2t0)=φ(0). Le pas doublé saute par-dessus la vallée et retombe à la même hauteur de l'autre côté. Avec un pas triplé, f aurait augmenté. Retenez le geste : la formule s'écrit avec la hessienne, celle des DÉRIVÉES SECONDES, et f(x)=21x⋅Hx, avec le facteur 21.
d)
∇f(x1)=(4−2;4−6)=(2;−2), orthogonal à (6;6) comme il se doit après une recherche exacte. g⋅g=8, Hg=(4−4;4−12)=(0;−8), g⋅Hg=16, d'où t1=168=21. Alors x2=(2;−1)−21(2;−2)=(1;0) et f(x2)=1. Le pas a changé d'une itération à l'autre (61 puis 21) : la recherche exacte s'adapte à la courbure de f dans chaque direction, c'est son avantage sur un pas fixe.
e)
x2=(1;0)=31x0. Or f n'a pas de terme du premier degré : si l'on multiplie le point par λ, le gradient est multiplié par λ et la formule du pas donne le MÊME pas. Les itérations à partir de x2 sont donc celles à partir de x0, divisées par 3 : x2k=3kx0 et x2k+1=3kx1. Comme f(λx)=λ2f(x), on obtient f(x2k)=9k9 et f(x2k+1)=9k3, soit dans les deux cas f(xk)=3k9 : chaque itération divise f par 3. Enfin 3k9<10−4⟺3k>90000 ; or 310=59049 et 311=177147, donc k=11. La méthode converge, mais à vitesse constante : un facteur 3 par pas, onze pas pour gagner quatre décimales.
Les points se gagnent avant la correction ; après, tu peux encore t'entraîner.
Pour toi :
Exercice 4 : Le pas fixe : quand la méthode diverge
9 réponses vérifiables
Pour éviter une recherche linéaire à chaque itération, on peut garder un PAS FIXE t>0 : xk+1=xk−t∇f(xk) pour tout k. On étudie ce choix sur f(x,y)=x2+5y2, de minimum (0;0), en notant xk=(xk;yk).
a) Montrez que xk+1=(1−2t)xk et yk+1=(1−10t)yk. Donnez les deux facteurs pour t=41.
b) Avec t=41 et x0=(5;1), calculez f(x0), f(x1) et f(x2). Le fait que f ait diminué au premier pas prouve-t-il que la suite converge ?
c) Pour quelles valeurs de t la suite converge-t-elle vers (0;0) quel que soit le point de départ ?
d) Le pas fixe le plus rapide est celui qui rend le plus petit possible le plus grand des deux facteurs ∣1−2t∣ et ∣1−10t∣. Trouvez-le et donnez ce facteur.
e) Avec ce pas, montrez que ∥xk∥ est multiplié par ce facteur à chaque itération, et trouvez le plus petit k pour lequel la distance au minimum est divisée par au moins 100.
Voir la correction
Réponses
a)∇f=(2x;10y) ; pour t=41 : facteurs 21 et −23
b)f(x0)=30, f(x1)=235, f(x2)=8215 ; non, yk=(−23)k diverge
c)∣1−2t∣<1 et ∣1−10t∣<1, soit 0<t<51
d)1−2t=10t−1, t=61, facteur 32
e)∥xk∥=(32)k∥x0∥ ; (23)12≈129,7>100, donc k=12
a)
∇f(x,y)=(2x;10y), donc xk+1=xk−2txk=(1−2t)xk et yk+1=yk−10tyk=(1−10t)yk. Les deux coordonnées évoluent SÉPARÉMENT, chacune multipliée à chaque pas par un facteur constant, d'où xk=(1−2t)kx0 et yk=(1−10t)ky0. Pour t=41 : 1−21=21 et 1−410=−23. Le facteur en y est plus grand que 1 en valeur absolue : c'est déjà la réponse à la question suivante.
b)
f(x0)=25+5=30. x1=(25;−23) et f(x1)=425+445=235=17,5. x2=(45;49) et f(x2)=1625+16405=8215=26,875. La valeur a baissé puis REMONTÉ. Le premier pas a trompé : il a beaucoup gagné sur x, qui pesait 25 dans f(x0), et perdu sur y, qui ne pesait que 5. Mais yk=(−23)k change de signe et grandit à chaque pas : les itérés sautent d'un bord de la vallée à l'autre, toujours plus haut, et f(xk)→+∞. Une baisse au premier pas ne prouve RIEN ; c'est le facteur de chaque coordonnée qui décide.
c)
xk→0 pour tout x0 si et seulement si ∣1−2t∣<1, soit 0<t<1 ; yk→0 pour tout y0 si et seulement si ∣1−10t∣<1, soit 0<t<51. Il faut les DEUX, donc 0<t<51. La contrainte vient de la direction la plus courbée : la dérivée seconde fyy=10 impose t<102. Plus la vallée est étroite dans une direction, plus le pas fixe doit être petit pour TOUTES les directions, y compris celles où l'on avancerait vite.
d)
Pour 0<t<51, ∣1−2t∣=1−2t décroît et ∣1−10t∣ décroît jusqu'en 101 puis croît. Le plus grand des deux est minimal quand ils sont égaux, avec 1−10t<0 : 1−2t=10t−1, d'où t=61, et les deux facteurs valent 32 et −32. À gauche de 61, la coordonnée x est trop lente ; à droite, la coordonnée y oscille trop fort. Même le meilleur pas fixe ne fait gagner qu'un facteur 32 par pas.
e)
Avec t=61, xk+1=(32xk;−32yk), donc ∥xk+1∥=32∥xk∥ et ∥xk∥=(32)k∥x0∥. On cherche (23)k≥100. À la main : (23)2=2,25, (23)4≈5,06, (23)8≈25,6, (23)12≈25,6×5,06≈129,7 et (23)11≈86,5. Donc k=12. Douze itérations pour deux décimales, sur une fonction de deux variables : c'est le prix du pas fixe, et la raison pour laquelle on règle le pas sur la direction la plus courbée.
Les points se gagnent avant la correction ; après, tu peux encore t'entraîner.
Pour toi :
Exercice 5 : Démontrer : gradients successifs orthogonaux et formule du pas
7 réponses vérifiables
Soit f une fonction de deux variables dont les dérivées partielles sont continues, xk un point où gk=∇f(xk)=0, et φ(t)=f(xk−tgk). La recherche linéaire exacte prend pour tk>0 le minimum de φ, et xk+1=xk−tkgk.
a) Par la dérivation en chaîne, montrez que φ′(t)=−∇f(xk−tgk)⋅gk. Que vaut φ′(0) ? Application : gk=(1;−2).
b) Déduisez-en que ∇f(xk+1)⋅∇f(xk)=0. Interprétez avec les courbes de niveau : où le pas s'arrête-t-il ?
c) On suppose f(x)=21x⋅Hx−b⋅x+c, de gradient Hx−b. Montrez que φ(t)=f(xk)−tgk⋅gk+2t2gk⋅Hgk, puis donnez tk et la baisse f(xk)−f(xk+1). Application : H=(4112) et gk=(1;−2).
d) Pourquoi a-t-on g⋅Hg>0 pour tout g=0 avec cette matrice H ? Que se passerait-il pour φ sinon ?
e) Dans le plan, comparez la direction de gk+2 à celle de gk. Qu'en déduit-on pour le trajet des itérés ?
Voir la correction
Réponses
a)φ′(0)=−∥gk∥2<0 ; ici φ′(0)=−5
b)φ′(tk)=0 donne gk+1⋅gk=0 ; le pas s'arrête où la droite de recherche est tangente à une courbe de niveau
d)g⋅Hg=4(g1+4g2)2+47g22>0 (detH=7>0, 4>0) ; sinon φ n'aurait pas de minimum
e)gk+2 est parallèle à gk : le trajet zigzague entre deux directions perpendiculaires
a)
Posons r(t)=xk−tgk, dont la dérivée est le vecteur constant r′(t)=−gk. La dérivation en chaîne pour φ(t)=f(r(t)) donne φ′(t)=∇f(r(t))⋅r′(t)=−∇f(xk−tgk)⋅gk. En t=0 : φ′(0)=−gk⋅gk=−∥gk∥2, strictement négatif puisque gk=0. Pour gk=(1;−2) : φ′(0)=−5. C'est la preuve que −gk est une direction de DESCENTE : φ décroît au départ, donc il existe des pas t>0 qui font baisser f. Rien ne dit en revanche jusqu'où (exercice 1).
b)
Le minimum tk>0 de φ est un point intérieur où φ est dérivable, donc φ′(tk)=0, c'est-à-dire −∇f(xk+1)⋅gk=0 : ∇f(xk+1)⋅∇f(xk)=0. Géométriquement, en xk+1 le nouveau gradient est perpendiculaire à la droite de recherche ; or il est aussi perpendiculaire à la courbe de niveau qui passe par xk+1. La droite de recherche est donc TANGENTE à cette courbe de niveau : on avance tant qu'on traverse des niveaux de plus en plus bas, et l'on s'arrête au point où la droite ne fait plus que frôler un niveau. C'est ce qui produit le virage à angle droit de chaque itération.
c)
Avec g=gk et H symétrique, développons : f(xk−tg)=21(xk−tg)⋅H(xk−tg)−b⋅(xk−tg)+c=f(xk)−tg⋅(Hxk−b)+2t2g⋅Hg, et Hxk−b=g. Donc φ(t)=f(xk)−tg⋅g+2t2g⋅Hg, parabole de sommet tk=g⋅Hgg⋅g, et la baisse vaut φ(0)−φ(tk)=2g⋅Hg(g⋅g)2. Application : Hg=(4−2;1−4)=(2;−3), g⋅Hg=2+6=8, g⋅g=5, donc tk=85 et la baisse vaut 1625. Le 21 devant x⋅Hx est indispensable : c'est lui qui fait que H est la hessienne.
d)
g⋅Hg=4g12+2g1g2+2g22=4(g1+4g2)2+47g22, somme de deux carrés à coefficients positifs, nulle seulement si g2=0 puis g1=0. C'est le critère du test des dérivées secondes : fxx=4>0 et detH=8−1=7>0. Le coefficient de t2 dans φ est alors positif, la parabole est tournée vers le haut et son sommet est un minimum. Si g⋅Hg était négatif ou nul (point de selle, maximum), φ décroîtrait sans fin dans certaines directions : la formule donnerait un « pas » négatif ou infini, et la recherche exacte n'aurait pas de sens.
e)
Par b), gk+1⊥gk et gk+2⊥gk+1. Dans le plan, deux vecteurs perpendiculaires au même vecteur non nul sont PARALLÈLES : gk+2 est parallèle à gk. Les pas successifs n'utilisent donc que deux directions perpendiculaires, en alternance : le trajet est un escalier, ou un zigzag, et jamais une ligne droite vers le minimum. C'est ce qu'on lit sur les cartes des exercices 6 et 10. En dimension 3 ou plus, seul l'angle droit entre deux pas CONSÉCUTIFS subsiste.
Les points se gagnent avant la correction ; après, tu peux encore t'entraîner.
Pour toi :
Partie B : problèmes et raisonnement (/50)
Exercice 6 : Le zigzag lu sur une carte de contour
10 réponses vérifiables
La figure montre les courbes de niveau f=12, f=3 et f=43 de f(x,y)=x2+3y2, et les quatre premiers itérés x0=(3;1), x1, x2, x3 de la méthode du gradient avec recherche linéaire exacte. Le repère est orthonormé : les angles se lisent tels qu'ils sont.
a) Lisez x1 sur la figure, puis retrouvez-le par le calcul : ∇f(x0), le pas t0 et x1.
b) Calculez x2, puis vérifiez par un produit scalaire l'angle droit que la figure montre en x1.
c) Montrez par récurrence que xk=(21)k(3;(−1)k), et donnez f(xk). Calculez f(x4).
d) On arrête l'algorithme dès que ∥∇f(xk)∥<10−3. À quelle itération s'arrête-t-il ? On utilisera 2≈1,414.
e) Plus généralement, pour f(x,y)=x2+κy2 avec κ≥1 et x0=(κ;1), montrez que x1=ρ(κ;−1) avec ρ=κ+1κ−1. Que se passe-t-il pour κ=1 ? Donnez ρ et le facteur de baisse de f par itération pour κ=9.
Voir la correction
Réponses
a)∇f(x0)=(6;6), t0=41, x1=(23;−21)
b)x2=(43;41) ; (x1−x0)⋅(x2−x1)=0
c)f(xk)=4k12 ; f(x4)=643
d)∥∇f(xk)∥=2k62 ; 2k>8485 dès k=14
e)κ=1 : minimum atteint en un pas ; κ=9 : ρ=54, f multipliée par 2516
a)
La figure place x1 vers (1,5;−0,5). Calcul : ∇f=(2x;6y), donc ∇f(x0)=(6;6). Avec la hessienne H=(2006), g⋅g=72 et g⋅Hg=72+216=288, d'où t0=28872=41 et x1=(3;1)−41(6;6)=(23;−21). On peut aussi minimiser φ(t)=(3−6t)2+3(1−6t)2, dont la dérivée −12(3−6t)−36(1−6t) s'annule en t=41. Le point est sur la courbe f=3 : la valeur est passée de 12 à 3, et le segment [x0x1] touche cette ellipse sans la traverser.
b)
∇f(x1)=(3;−3) ; g⋅g=18, g⋅Hg=18+54=72, t1=41 et x2=(23−43;−21+43)=(43;41). Les deux déplacements sont x1−x0=(−23;−23) et x2−x1=(−43;43), de produit scalaire 89−89=0. L'angle droit vu sur la figure est la propriété démontrée à l'exercice 5 : chaque déplacement est parallèle au gradient, et deux gradients successifs sont orthogonaux. Attention, cet angle ne se VOIT droit que dans un repère orthonormé ; avec des unités différentes sur les axes, le zigzag paraîtrait oblique.
c)
Pour k=0, (3;1) convient. Si xk=s(3;±1) avec s=(21)k, le gradient vaut s(6;±6) ; les deux sommes de la formule sont multipliées par s2, donc le pas reste 41 et xk+1=s(3−46;±(1−46))=2s(3;∓1). D'où xk=(21)k(3;(−1)k) pour tout k. Alors f(xk)=4k1(9+3)=4k12 : chaque itération divise f par 4, et f(x4)=25612=643.
d)
∇f(xk)=(21)k(6;±6), de norme 2k62. La condition 2k62<10−3 équivaut à 2k>60002≈8485. Or 213=8192<8485 et 214=16384 : l'algorithme s'arrête à k=14. À ce moment, f(x14)=41412≈4,5×10−8 et ∥x14∥=21410≈1,9×10−4. Le critère porte sur le gradient parce que, dans un vrai problème, on ne connaît ni x∗ ni f∗ : c'est la seule quantité qu'on peut calculer.
e)
∇f(x0)=(2κ;2κ) et φ(t)=(κ−2κt)2+κ(1−2κt)2. En posant s=2κt, φ′=0 donne (κ−s)+κ(1−s)=0, soit s=κ+12κ. Alors x1=(κ−s;1−s)=(κ+1κ(κ−1);κ+11−κ)=ρ(κ;−1). Le même raisonnement qu'en c) donne xk=ρk(κ;(−1)k) et f(xk)=ρ2kf(x0). Pour κ=1, les courbes de niveau sont des cercles, ρ=0 et x1=(0;0) : le gradient vise le centre, un seul pas suffit. Pour κ=3 on retrouve ρ=21. Pour κ=9, ρ=108=54 et f n'est multipliée que par 2516 à chaque pas ; pour κ=99, par (5049)2≈0,96. Plus la vallée est allongée, plus le zigzag est serré et lent : c'est la faiblesse connue de la méthode.
Les points se gagnent avant la correction ; après, tu peux encore t'entraîner.
Pour toi :
Exercice 7 : Une vallée courbe : la méthode hors des quadratiques
11 réponses vérifiables
Soit f(x,y)=2(x2−y)2+(1−x)2. La figure montre les courbes de niveau f=1, f=83 et f=41, la parabole y=x2 en pointillé, le point de départ x0=(0;0) et le point (1;1). Les courbes de niveau sont des « bananes » qui suivent la parabole.
Ici f n'est PAS quadratique : la formule du pas des exercices précédents ne s'applique plus, il faut minimiser φ elle-même.
a) Montrez que (1;1) est le minimum global de f. Calculez f(x0) et ∇f(x0).
b) Première itération avec recherche exacte : écrivez φ(t), montrez que φ′ a une seule racine et que c'est t0=41. Donnez x1 et f(x1).
c) Deuxième itération : ∇f(x1), le pas t1, x2 et f(x2).
d) Pour la troisième itération, ∇f(x2)=(−1;0) et φ′(t)=4t(1+t)(1+2t)+2t−1. Calculez φ′(101) et φ′(51) en fractions, et concluez sur t2.
e) Où se trouve x2 par rapport à la parabole ? Calculez sa distance au minimum, au centième, et expliquez pourquoi la méthode progresse lentement dans cette vallée.
d)φ′(101)=−12534, φ′(51)=12593 : t2∈]101;51[, racine d'un polynôme de degré 3
e)x2 est sur la parabole ; distance 413≈0,90 ; les pas perpendiculaires ne peuvent pas suivre une vallée courbe
a)
f est une somme de deux carrés, donc f≥0, et f(1;1)=2(1−1)2+0=0 : (1;1) est un minimum global. Il est même unique : f=0 exige x=1 et y=x2=1. Pas besoin du test des dérivées secondes, l'inégalité f≥0 décide. Le premier terme est nul sur toute la parabole y=x2 : c'est le FOND DE LA VALLÉE, et le second terme le fait descendre doucement vers x=1. f(x0)=0+1=1. Puis fx=8x(x2−y)−2(1−x) et fy=−4(x2−y), donc ∇f(x0)=(−2;0).
b)
On se déplace selon −∇f(x0)=(2;0) : le point courant est (2t;0) et φ(t)=2(4t2)2+(1−2t)2=32t4+(1−2t)2. Alors φ′(t)=128t3−4(1−2t)=128t3+8t−4 et φ′′(t)=384t2+8>0 : φ′ est strictement croissante, elle s'annule une seule fois, et c'est en un minimum de φ. On vérifie φ′(41)=2+2−4=0. Donc t0=41, x1=(21;0) et f(x1)=2×161+41=83. L'équation φ′=0 est de degré 3 : on l'a résolue parce qu'elle avait une racine évidente, et l'argument de monotonie garantit qu'il n'y en a pas d'autre. Sans lui, la réponse est incomplète.
c)
En x1 : x2−y=41, donc fx=8×21×41−2×21=0 et fy=−1 : ∇f(x1)=(0;−1), orthogonal à (−2;0) comme le veut la recherche exacte, même pour une fonction non quadratique. Le point courant est (21;t) et φ(t)=2(41−t)2+41, minimale en t1=41. Donc x2=(21;41) et f(x2)=0+41=41.
d)
En x2, x2−y=0, donc fx=−1, fy=0. Le point courant est (21+t;41), avec x2−y=t+t2, et φ(t)=2(t+t2)2+(21−t)2, de dérivée 4t(1+t)(1+2t)+2t−1. En 101 : 4×101×1011×1012=1000528, et 1000528+1000200−1=−1000272=−12534. En 51 : 4×51×56×57=125168, et 125168+12550−125125=12593. Comme φ′ est continue et change de signe, le théorème des valeurs intermédiaires donne une racine dans ]101;51[, unique car φ′ est croissante sur [0;+∞[ (produit de facteurs positifs croissants, plus 2t). Le pas n'a plus de forme simple : en pratique, une recherche linéaire se fait alors par un algorithme à une variable (bissection), ou on se contente d'un pas qui fait « assez » baisser f.
e)
41=(21)2 : x2 est SUR la parabole, au fond de la vallée, après deux pas. Pourtant sa distance au minimum vaut 41+169=413≈0,90, contre 2≈1,41 au départ et 25≈1,12 après un pas : f a été divisée par 4, la distance seulement par 1,6. Au fond d'une vallée, la pente transversale est nulle et la pente LE LONG de la vallée est faible ; or la méthode n'avance qu'en segments perpendiculaires entre eux, alors que le fond est COURBE. Chaque pas sort de la parabole, le suivant y revient, et l'itéré remonte vers (1;1) par petits zigzags. C'est le comportement classique sur la fonction de Rosenbrock, dont celle-ci est une version douce.
Les points se gagnent avant la correction ; après, tu peux encore t'entraîner.
Pour toi :
Exercice 8 : Cinq affirmations à corriger
8 réponses vérifiables
Chacune des cinq affirmations ci-dessous est FAUSSE. Pour chacune, faites le calcul demandé, qui la réfute, puis écrivez l'énoncé juste.
Toutes viennent de la même confusion : prendre la direction de plus forte descente, qui est une information LOCALE, pour une information sur le minimum.
a) « Avec la recherche linéaire exacte, la méthode du gradient atteint le minimum d'une quadratique en un seul pas, puisqu'elle prend le meilleur pas. » Pour f(x,y)=x2+9y2 et x0=(9;1), calculez f(x0) et f(x1).
b) « Si l'on remplace −∇f par le vecteur unitaire de même direction, la recherche exacte donne le même pas t. » Pour f(x,y)=x2+y2 et x0=(3;4), donnez le pas optimal t avec −∇f(x0), puis le pas optimal s avec le vecteur unitaire.
c) « Deux directions de descente successives sont parallèles, puisque la méthode suit toujours la pente. » Pour f(x,y)=2x2+y2 et x0=(1;2), faites une itération exacte et calculez ∇f(x0)⋅∇f(x1).
d) « Si ∥∇f(xk)∥<10−2, alors xk est à moins de 10−2 du minimum. » Pour f(x,y)=200x2+y2, calculez ∥∇f∥ au point (21;0) et la distance de ce point au minimum.
e) « Quand la méthode du gradient s'arrête parce que ∇f=0, elle a trouvé un minimum. » Pour f(x,y)=x2−y2 et x0=(1;0), faites une itération exacte et dites où l'on arrive.
Voir la correction
Réponses
a)f(x0)=90, x1=(536;−54), f(x1)=5288=57,6 ; un seul pas seulement si ∇f(x0) vise le centre
b)t=21 mais s=5=∥∇f(x0)∥t ; le PAS change, le POINT x1=(0;0) est le même
c)t0=31, x1=(−31;32), produit scalaire 0 : elles sont orthogonales
d)∥∇f∥=2001=0,005 mais la distance vaut 21
e)t=21, x1=(0;0), où ∇f=0 : c'est un point de selle
a)
Faux. f(x0)=81+9=90, ∇f(x0)=(18;18), et avec H=(20018) : t0=648+5832648=101. Donc x1=(9−1,8;1−1,8)=(536;−54) et f(x1)=251296+25144=5288=57,6. Le meilleur pas sur la droite de recherche n'est pas le meilleur point du plan : la droite ne passe pas par le minimum. Énoncé juste : « la recherche exacte minimise f SUR LA DROITE de recherche ; le minimum n'est atteint en un pas que si −∇f(x0) pointe vers lui, ce qui arrive pour des courbes de niveau circulaires ou un départ sur un axe de l'ellipse ».
b)
Faux. ∇f(x0)=(6;8), de norme 10. Avec −∇f : φ(t)=(3−6t)2+(4−8t)2=25(1−2t)2, minimale en t=21. Avec le vecteur unitaire −51(3;4) : le point courant est (3−53s;4−54s), minimal en s=5. Dans les deux cas on arrive en (0;0) : le POINT ne dépend pas de la longueur du vecteur direction, mais le nombre t en dépend, s=∥∇f∥t. Le piège est réel sur une copie : un pas donné « t=0,1 » n'a de sens qu'avec la convention de l'énoncé, xk−t∇f(xk) sans normalisation dans le cours de MTH1101. Énoncé juste : « normaliser la direction multiplie le pas optimal par ∥∇f∥ et laisse xk+1 inchangé ».
c)
Faux. ∇f=(4x;2y), ∇f(x0)=(4;4), t0=64+3232=31, x1=(1−34;2−34)=(−31;32) et ∇f(x1)=(−34;34). Produit scalaire : −316+316=0. Énoncé juste : « avec la recherche exacte, deux gradients successifs sont ORTHOGONAUX ; ce sont les directions k et k+2 qui sont parallèles, en dimension deux ». La méthode suit la pente au départ de chaque pas, pas pendant le pas : une fois lancée sur sa droite, elle ne tourne plus jusqu'au point de tangence.
d)
Faux. ∇f=(100x;2y), donc en (21;0) : ∇f=(2001;0), de norme 0,005<10−2. Pourtant la distance au minimum (0;0) vaut 21, cinquante fois plus. Une fonction TRÈS PLATE dans une direction a un petit gradient loin de son minimum. Énoncé juste : « un petit gradient dit que la pente est faible, pas que l'on est près du minimum ; le critère ∥∇f∥<ε est un critère d'arrêt pratique, pas une garantie de précision sur x ». Sur ce point, f=8001 : c'est plutôt la VALEUR de f qui est presque optimale.
e)
Faux. ∇f=(2x;−2y), ∇f(x0)=(2;0), et φ(t)=(1−2t)2, minimale en t=21 : x1=(0;0), où ∇f=0. L'algorithme s'arrête. Mais f(0;y)=−y2<0=f(0;0) : l'origine est un point de SELLE, le test des dérivées secondes donne D=(2)(−2)−0=−4<0. Énoncé juste : « la méthode s'arrête en un POINT CRITIQUE ; il faut ensuite le classer ». En pratique un départ générique, comme (1;0,01), s'éloigne de la selle, car la composante en y grandit à chaque itération, mais rien n'est garanti sans hypothèse sur f.
Les points se gagnent avant la correction ; après, tu peux encore t'entraîner.
Pour toi :
Exercice 9 : Apprentissage automatique : le taux d'apprentissage et l'échelle des variables
10 réponses vérifiables
Un modèle prédit une valeur y^=w1x1+w2x2 à partir de deux variables x1 et x2. On règle les poids (w1;w2) en minimisant la PERTE L=21∑(y^−y)2 sur les exemples d'entraînement, par la méthode du gradient à pas fixe : en apprentissage automatique, le pas s'appelle le TAUX D'APPRENTISSAGE η, et une itération une ÉPOQUE.
Jeu A : deux exemples, (x1;x2;y)=(1;1;3) et (1;−1;1). Jeu B : les mêmes, mais x2 est mesuré dans une unité trois fois plus petite, d'où (1;3;3) et (1;−3;1). La figure montre deux courbes de niveau de chaque perte : LA en pointillé, LB en trait plein. Partout, on part de w0=(0;0).
a) Montrez que LB=w12+9w22−4w1−6w2+5 et donnez son minimum et la valeur de la perte en ce minimum. (On admet LA=w12+w22−4w1−2w2+5.)
b) Sur le jeu A, avec η=21 : faites une époque. Où arrive-t-on ?
c) Sur le jeu B, notez e1=w1−2 et e2=w2−31. Montrez que chaque époque multiplie e1 par 1−2η et e2 par 1−18η. Pour quels η l'apprentissage converge-t-il ? Que se passe-t-il avec le taux η=21 du jeu A ?
d) Sur le jeu B, avec η=101 : calculez w1, puis la perte après une et deux époques. Justifiez que 101 est le meilleur taux fixe pour ce jeu.
e) Avec η=101, combien d'époques faut-il pour diviser la distance au minimum par 100 ? On donne ln2≈0,693 et ln10≈2,303. Quelle leçon pratique en tirer ?
b)w1=(0;0)−21(−4;−2)=(2;1), le minimum de LA, en une époque
c)0<η<91 ; avec η=21, e2 est multiplié par −8 : divergence
d)w1=(52;53), L=516=3,2 puis 125256=2,048 ; ∣1−2η∣=∣1−18η∣ en η=101
e)(45)k>100, k>0,2244,606≈20,6, donc 21 époques ; mettre les variables à la même échelle
a)
LB=21[(w1+3w2−3)2+(w1−3w2−1)2]. En développant, les doubles produits ±6w1w2 se compensent et LB=21[2w12+18w22−8w1−12w2+10]=w12+9w22−4w1−6w2+5. En complétant les carrés, LB=(w1−2)2+9(w2−31)2 : le minimum est (2;31) et la perte y vaut 0, car deux poids suffisent à reproduire exactement deux exemples. Le modèle appris est le même que pour le jeu A, de minimum (2;1) : w2 est divisé par 3 parce que x2 est multiplié par 3.
b)
∇LA=(2w1−4;2w2−2), qui vaut (−4;−2) en w0. Avec η=21, w1=(0;0)−21(−4;−2)=(2;1) : c'est le minimum, atteint en UNE époque. Ce n'est pas de la chance : LA=(w1−2)2+(w2−1)2 a des courbes de niveau circulaires (les cercles en pointillé), le gradient vise donc toujours le centre, et le pas 21 est exactement celui qui l'atteint.
c)
∇LB=(2w1−4;18w2−6)=(2e1;18e2). Une époque donne e1←e1−2ηe1=(1−2η)e1 et e2←(1−18η)e2. L'apprentissage converge pour tout départ si et seulement si ∣1−2η∣<1 et ∣1−18η∣<1, soit 0<η<91. Avec le taux du jeu A, η=21, le facteur de e2 vaut 1−9=−8 : l'erreur sur w2 est multipliée par −8 à chaque époque et la perte explose. Même modèle, même taux : un simple CHANGEMENT D'UNITÉ suffit à faire diverger l'entraînement : la variable x2 multipliée par 3 multiplie la courbure ∂w22∂2L par 9, et c'est la plus forte courbure qui impose le taux.
d)
∇LB(w0)=(−4;−6), donc w1=(104;106)=(52;53). Les facteurs valent 54 et −54 ; comme LB=e12+9e22, chaque époque multiplie la perte par 2516 : L(w0)=4+1=5, L(w1)=516=3,2, L(w2)=125256=2,048. Contrôle direct : (52−2)2+9(53−31)2=2564+9×22516=2564+2516=516. Le taux 101 est le meilleur : le plus grand des deux facteurs ∣1−2η∣ (décroissant) et ∣1−18η∣ (croissant au-delà de 181) est minimal quand ils sont égaux, 1−2η=18η−1, soit η=101. Le zigzag de w2 autour de 31 est la signature de ce compromis.
e)
∣e1∣ et ∣e2∣ sont tous deux multipliés par 54, donc la distance au minimum aussi. On veut (54)k≤1001, soit kln45≥ln100. Or ln45=ln10−3ln2≈2,303−2,079=0,224 et ln100≈4,606, d'où k≥20,6 : il faut 21 époques, contre UNE pour le jeu A. Contrôle : (45)20≈86,7 et (45)21≈108,4. La leçon est celle de tous les praticiens : avant d'entraîner un modèle par descente de gradient, on remet les variables à la MÊME ÉCHELLE (on les « normalise »). Cela arrondit les courbes de niveau de la perte, et un taux unique convient alors à toutes les directions.
Les points se gagnent avant la correction ; après, tu peux encore t'entraîner.
Pour toi :
Exercice 10 : Le coût d'un réseau à régler : la puissance dissipée
12 réponses vérifiables
Un réseau relie une source à 12 V à la masse par trois résistances de 1Ω en série. On note u et v les potentiels des deux nœuds intermédiaires. Pour des potentiels (u;v) quelconques, la puissance dissipée serait P(u,v)=(12−u)2+(u−v)2+v2, en watts. Les potentiels réels sont ceux qui minimisent P : c'est le principe de dissipation minimale.
Sur un réseau de milliers de nœuds, on ne résout pas le système à la main : on fait descendre le coût P par un algorithme. On le fait ici sur deux nœuds, avec la recherche linéaire exacte, dont la hessienne vaut H=(4−2−24). Le schéma ci-dessous représente le réseau.
a) Trouvez le minimum exact de P en résolvant ∇P=0, et la puissance minimale P∗. Interprétez.
b) À partir de x0=(0;0), faites une itération : ∇P(x0), le pas t0, x1 et P(x1).
c) Faites deux itérations de plus. Donnez x2, x3, P(x3), et la suite des écarts P(xk)−P∗ pour k=0 à 3.
d) Dans un vrai réseau, P∗ est inconnue : on s'arrête quand ∥∇P(xk)∥<10−2. Calculez ∥∇P(xk)∥ pour k=1,2,3, devinez la loi et donnez l'itération d'arrêt.
e) Un technicien part plutôt de x0=(6;6). Faites une itération et expliquez le résultat.
Voir la correction
Réponses
a)(u;v)=(8;4), P∗=48 W : le diviseur de tension, 4 A dans chaque résistance
e)∇P=(−12;12), t=61, x1=(8;4) : le minimum en un pas, car ∇P(x0)=6(x0−x∗)
a)
Pu=−2(12−u)+2(u−v)=4u−2v−24 et Pv=−2(u−v)+2v=−2u+4v. ∇P=0 donne u=2v, puis 8v−2v=24 : v=4 et u=8. La hessienne a Puu=4>0 et D=16−4=12>0 : c'est le minimum, unique. P∗=16+16+16=48 W. On retrouve le diviseur de tension : trois résistances égales se partagent les 12 V en trois chutes de 4 V, un courant de 4 A les traverse, et 3×42×1=48 W. Le principe de dissipation minimale redonne les lois de Kirchhoff.
b)
∇P(x0)=(−24;0). Formule du pas : g⋅g=576, Hg=(−96;48), g⋅Hg=2304, d'où t0=2304576=41. Alors x1=(0;0)−41(−24;0)=(6;0) et P(x1)=36+36+0=72. Le gradient ne portait que sur u : la méthode n'a réglé que le premier nœud, en lui donnant le potentiel qui équilibre ses deux voisins, 212+0=6.
c)
∇P(x1)=(24−0−24;−12)=(0;−12), orthogonal au précédent ; g⋅g=144, g⋅Hg=4×144=576, t1=41 et x2=(6;3), avec P(x2)=36+9+9=54. Puis ∇P(x2)=(24−6−24;−12+12)=(−6;0), t2=41 et x3=(215;3), avec P(x3)=481+481+9=49,5. Les écarts à P∗ valent 96, 24, 6, 23 : divisés par 4 à chaque itération après la première. Le trajet est un ESCALIER, un nœud réglé à la fois sur son équilibre local, ce que l'exercice 5 annonçait : en dimension deux, les directions alternent.
d)
∥∇P(x1)∥=12, ∥∇P(x2)∥=6, ∥∇P(x3)∥=3 : la norme est divisée par 2 à chaque pas, ∥∇P(xk)∥=2k−112 pour k≥1, ce qu'on prouve comme à l'exercice 6, la configuration se reproduisant à l'échelle 41 tous les deux pas. Le critère 2k−112<10−2 équivaut à 2k−1>1200 ; or 210=1024 et 211=2048, donc k−1=11 et l'algorithme s'arrête à k=12. L'écart vaut alors 41124, environ 6×10−6 W : le critère sur le gradient est ici plus exigeant que nécessaire sur le coût, et c'est le seul qu'on peut calculer sans connaître P∗.
e)
∇P(6;6)=(24−12−24;−12+24)=(−12;12), g⋅g=288, Hg=(−72;72), g⋅Hg=1728, donc t=61 et x1=(6+2;6−2)=(8;4) : le minimum exact, en UN pas. Ce n'est pas un hasard : x0−x∗=(−2;2) et ∇P(x0)=(−12;12)=6(x0−x∗). Le gradient est colinéaire au vecteur qui va du minimum au point : −∇P VISE le minimum, parce que le point de départ est sur un axe des ellipses de niveau. C'est l'exception qui confirme le fil du chapitre : en général −∇P ne vise pas le minimum, et la méthode zigzague.
Les points se gagnent avant la correction ; après, tu peux encore t'entraîner.
Il manque quelque chose dans cette série ?Un type d'exercice que ton prof donne, un énoncé qui te bloque, 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.
Contactez-moi pour une première séance. On reprend la recherche linéaire à la main, le choix du pas et la lecture des itérés sur une carte de contour, jusqu'à ce que chaque virage du zigzag s'explique.