Corrige Examen 2016-17 PDF Algorithme de gradient conjugué pour

Exercice 1 Méthode du gradient conjugué

Appliquer la méthode du gradient conjugué à partir de x(0). Exercice 2 Méthode de Cauchy (ou de plus forte pente). Soit la fonction ƒ suivante : On pose x(0).

Algorithme du gradient conjugué. • La lettre n désigne un entier

Proposition de corrigé. 1). La fonctionnelle J a bien un minimum car la On touche l`a au génie de Hestenes et Stiefel qui ont inventé la méthode du gradient ...

LICENCE 3 MATHEMATIQUES – INFORMATIQUE

préfère des méthodes plus sophistiquées telles sue la méthode "BICGSTAB" ou "GMRES". Corrigé de l'exercice 125 page 237 (Gradient conjugué préconditionné par

Analyse numérique avancée Corrigé du TD 1

18 févr. 2021 Exercice 1 : Convergence du gradient conjugué. 1. La majoration du ... méthode du gradient conjugué comme une méthode itérative et donc d ...

Méthodes Numériques : Optimisation

Nous abordons les algorithmes de type descente de gradient la méthode du gradient conjugué

Corrige Examen 2016-17

Algorithme 1 : Algorithme du gradient conjugué. Données : Un point initial x Etude de la convergence de l'Algorithme 2 avec la méthode exacte Le but de la fin ...

Analyse Numérique

2.2.4 Méthode du gradient à pas optimal. . . . . . . . . . . . . 14. 2.2.5 Méthode du gradient conjugué. . . . . . . . . . . . . . . . 15. 2.3 Exercices.

Optimisation

12 mars 2020 3.4 La méthode du gradient conjugué . ... Dans cet exercice on étudie une méthode de minimisation sans contraintes d'une fonction quadratique de ...

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

On utilisera le fait que si une fonction f : IRs → IR est continue finie

Untitled

Cours et exercices corrigés. Dr.BOUDIAF NAIMA1. 2017. 1n.boudiaf@univ&batna2.dz. Page 3 La méthode du gradient conjugué est une méthode de descente à pas ...

Exercice 1 Méthode du gradient conjugué

Appliquer la méthode du gradient conjugué à partir de x(0). Exercice 2 Méthode de Cauchy (ou de plus forte pente). —. Soit la fonction f suivante

LICENCE 3 MATHEMATIQUES – INFORMATIQUE

Semaine 2 : 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) :.

Cours danalyse numérique 2004-2005

12 sept. 2006 L. Sainsaulieu Calcul scientifique cours et exercices corrigés ... Remarque 1.16 (Sur la méthode du gradient conjugué) Il existe une mé-.

Corrige Examen 2016-17

Algorithme de gradient conjugué pour les moindres carrés : On suppose désormais que Le but de l'exercice est d'étudier la convergence d'un algorithme de ...

RO04/TI07 - Optimisation non-linéaire

Exercices du chapitre I . . Interprétation de la méthode du gradient conjugué . ... Exercice I.2 Calcul du gradient d'une fonction quadratique.

#7<9: 1>Optimisation Sans Contraintes

Chapitre3 : Algorithmes. 3.1 Méthode du gradient. 3.2 Méthode du gradient conjugué. 3.3 Méthode de Newton. 3.4 Méthode de relaxation. 3.5 Travaux pratiques.

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.

Algorithme du gradient conjugué. • La lettre n désigne un entier

Description de l'algorithme du gradient conjugué. L'état xk au pas suivant de l'algorithme est issu de xk?1 via un ... Proposition de corrigé.

Analyse numérique avancée Corrigé du TD 1

18 févr. 2021 Corrigé du TD 1 ... Exercice 1 : Convergence du gradient conjugué ... Ici nous utilisons le gradient conjugué comme une méthode directe

Université Aix Marseille 1 Licence de mathématiques Cours d

2 févr. 2017 L. Sainsaulieu Calcul scientifique cours et exercices corrigés pour ... du gradient conjugué est en fait une méthode d'optimisation pour la ...

Optimisation, algorithmique (MML1E31)(M1 Maths, 2016-2017)

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] Corrige Examen 2016-17 Algorithme de gradient conjugué pour