[PDF] Corrige Examen 2016-17 PDF examen2016

Corrigé Les documents suivants sont autorisés : — Polycopiés distribués en Algorithme de gradient conjugué pour les moindres carrés : On suppose désormais que Dans la suite de l'exercice, f : Rn → R désigne une fonction deux fois

Etudier les paragraphes 3 3 1 (méthodes de descente) et 3 3 2 (algorithme du gradient conjugué, GC) Exercices proposés (avec corrigés) : 117 (exemple), 118

[PDF] Corrige Examen 2016-17

[PDF] Optimisation

ordre (gradient conjugué, B F G S ) sera nécessaire pour obtenir 5 décimales 3 5 Exercices corrigés Minimisation unidirectionnelle La plupart des méthodes

[PDF] 1 Exercice sur la fonctionnelle ROF 2 Méthode de gradient avec

2 Méthode de gradient avec projection à pas variable pour une fonc- tion quadratique elliptique On considère la problème de minimisation suivant : trouver

[PDF] Algorithme du gradient conjugué • La lettre n désigne un entier

Algorithme du gradient conjugué Proposition de corrigé 1) La fonctionnelle J a bien un minimum car la matrice A est symétrique définie positive

[PDF] feuilles de travaux dirigés - Ceremade - Université Paris Dauphine

l'algorithme du gradient conjugué? Calculer alors explicitement les deux premiers itérés et vérifier la finie convergence de l'algorithme Exercice 24 ( exercice

[PDF] Exercices - Feuille 5

o`u Mq est triangulaire inférieure inversible carrée d'ordre q

[PDF] Optimisation Sans Contraintes - Université de Souk Ahras

1 5 Suggestions et Corrigés 3 2 2 Méthode de gradient conjugué dans le cas quadratique 39 3 2 3 Méthode du Exercice 01 Montrer qu'une

[PDF] Optimisation

La méthode du gradient conjugué a été découverte en 1952 par Hestenes et Exercice 76 (Gradient conjugué pour une matrice non symétrique) Corrigé

[PDF] 98 CHAPITRE 2 PRÉLIMINAIRES

On retrouve la formule utilisée dans l'exemple du tableau 3 1 pour le calcul du pas θ˚ Exercice 3 6 4 [Application de l'algorithme du gradient conjugué] Appliquez l

Examen du mercredi 4 janvier 2017

Corrigé

Les documents suivants sont autorisés :

P olycopiésdis tribuésen cours et notes de cours manuscrites corr espondantes, Sujets de TP i mpriméset notes manuscrites corr espondantes. La consultation de tout autre document (livres, etc.) et l"utilisation de tout appareil élec- tronique sont interdites.

Exercice 1.(sur environ 12 points)

Rappel sur les fonctionnelles quadratiques :On rappelle qu"une fonctiong:Rn!Rest une fonctionnelle quadratique s"il existe une matrice carrée symétriqueA2 Mn(R), un vecteur b2Rnet une constantec2Rtels que

8x2Rn; g(x) =12

hAx;xi hb;xi+c (et alors la matriceA, le vecteurbet la constantecsont uniques). Fonctionnelle des moindres carrés :Soientn;p2Ndeux entiers non nuls. SoientA2 M p;n(R)une matrice rectangulaire,b2Rpun vecteur. On définit la fonctionf:Rn!Rpar f(x) =12 kAxbk2: Attention on utilisera la même notation pour la norme et le produit scalaire dansRnet dansRp, mais les vecteurs ne sont a priori pas de la même taille! 1. Montrer quefestunefonctionnellequadratiqueetpréciserlamatricecarréeA02 Mn(R), le vecteurb02Rnet la constantec02Rassociés àf. 2. Donner l"e xpressiondu gradient rf(x)et de la matrice hessienner2f(x)defen tout

pointx2Rn(on pourra se référer à un résultat du cours plutôt que de faire les calculs).

Montrer que fest convexe.

4. Montrer que fest fortement convexe si et seulement siker(A) =f0g. 5. Soit x2Rntelquerf(x)6= 0.Rappelerladéfinitiond"unedirectiondedescented2Rn au pointxet montrer qued2Rnest une direction de descente si et seulement si hAxb;Adi<0 (en particulierAd6= 0). 1

6.Soit x2Rntel querf(x)6= 0etdune direction de descente au pointx. Montrer que le

problème d"optimisation inft2Rf(x+td) admet une unique solution donnée par t ?=hrf(x);dikAdk2:(1) Algorithme de gradient conjugué pour les moindres carrés :On suppose désormais que ker(A) =f0g. On rappelle ci-dessous le pseudo-code de l"algorithme du gradient conjugué afin de minimiser une fonctionnelle quadratique g(x) =12 hA0x;xi hb0;xi+c0

lorsqueA0est symétrique définie positive (ce qui revient à résoudre le système linéaireA0x=

0). On rappelle que, par convention, pour cet algorithme ce sont les vecteurs opposésd(k)qui

sont des directions de descente.Algorithme 1 :Algorithme du gradient conjuguéDonnées :Un point initialx(0)2Rn, un seuil de tolérance" >0

Résultat :Un pointx2Rnproche dex?

Initialiserx:

x x(0); k 0;

Première itération :

Calculer d(0)=rg(x)(d(0)=rg(x(k)))

2. Calculer le pas de desc enteoptimal t(0)dans la direction de descented(0) 3.

Mettre à jour x:

x x(1)=x(0)t(0)d(0); (attention c"est bien un signe) k k+ 1; tant quekrf(x)k2> "2faire1.Calculer d(k)=rg(x(k)) +krg(x(k))k2krg(x(k1))k2d(k1). 2. Calculer le pas de descente optimal t(k)dans la direction de descented(k) 3.

Mettre à j ourx:

x x(k+1)=x(k)t(k)d(k); (attention c"est bien un signe) k k+ 1; fin7.En utilisant l"équation ( 1), donner l"expression des pas de descentet(0)ett(k),k>1, pour la fonctionf(x) =12 kAxbk2en fonction derf(x(0)),Aetd(0)pourt(0)etrf(x(k)), Aetd(k)pourt(k)(en faisant attention à la convention sur les directions de descentes). 2

8.Ecrire une fonction scilab

function x = grad_conj_moindres_carres(A, b, x0, eps) qui applique l"algorithme du gradient conjugué à la fonctionnellef(x) =12 kAxbk2en partant du pointx0et avec une tolérance"pour le critère d"arrêt. On pourra introduire une fonction intermédiaire qui calcule le gradient def(non obligatoire).

Solution de l"exercice 1.

1. f(x) =12 kAxbk2 12 hAxb;Axbi 12 hAx;Axi hb;Axi+12 hb;bi 12 hATAx;xi hATb;xi+12 kbk2:

Doncfest quadratique avec

0=ATA; b0=ATb; c=12

kbk2: 2. D"après les e xpressiondu gradient et de la matrice hessienne des fonctionnelles quadra- tiques, rf(x) =A0xb0=AT(AxB) et r

2f(x) =A0=ATA:

3.quotesdbs_dbs2.pdfusesText_3

[PDF] [PDF] Corrige Examen 2016-17

[PDF] LICENCE 3 MATHEMATIQUES – INFORMATIQUE