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

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 ...

Algorithme du gradient conjugu´e.La lettrend´esigne un entier sup´erieur ou ´egal `a 1,Aune matrice r´eelle carr´ee

d"ordrensym´etrique d´efinie positive etbun vecteur de IRn. On note?

,?le

produit scalaire usuel dans IR n.

1) Montrer que la r´esolution du syst`eme lin´eaire

(1)Ax=b ´equivaut `a rechercher le minimum, pourxappartenant `a IRn, de la fonctionnelle (2)J(x) =1

2(x, Ax)-(b, x).

2)Description de l"algorithme du gradient conjugu´e.

Initialisation :x0?IRn, w0=Ax0-b.

It´eration de l"algorithme.

On suppose connus l"´etatxk-1apr`es laki`emeit´eration ainsi que la direction de descentewk-1.L"´etatxkau pas suivant de l"algorithme est issu dexk-1via un incr´ement proportionnel `a la direction de descente : (3)xk=xk-1+ρk-1wk-1 de fa¸con `a minimiser la fonctionnelle J : On introduit ´egalement le gradientgkdeJau pointxk: (5)gk=Axk-b.

2.1) Calculer le coefficientρk-1en fonction degk-1,wk-1etA.

2.2) Montrer que l"on a

(6)?gk, wk-1?= 0. La nouvelle direction de descentewkest recherch´ee sous la forme (7)wk=gk+αkwk-1 de sorte quewksoit orthogonal `a la directionwk-1pour le produit scalaire associ´e `a la matriceAc"est `a dire : (8)?wk, Awk-1?= 0. 1

2.3) Calculer la valeur deαken fonction degk, wk-1etA.On notera que le

choix plus simpleαk= 0 conduit `a la m´ethode du gradient simple, o`u la direction de descente de l"algorithmewkcorrespond `a la ligne de plus grande pentegk.

3)L"algorithme converge en au plus n ´etapes.

3.1) Remarquer que si les gradients successifsg0, g1, ... ,gk-1sont non nuls

mais quegkest nul, alors l"´etatxkest la solution du syst`eme lin´eaire (1).

3.2) On suppose dans cette question que tous les gradientsgjsont non nuls

jusqu"`a l"´etapemincluse. Montrer qu"on a alors les relations d"orthogonalit´e suivantes : On pourra raisonner par r´ecurrence surkpour l"ensemble des quatre propri´et´es et d´emontrer les relations (9) `a (12) dans l"ordre o`u elles apparaissent.

3.3) Montrer que l"algorithme converge en au plus n it´erations.

4) Propri´et´es auxiliaires.

4.1) Montrer que l"on a

(13)αk=?gk?2 ?gk-1?2. En d´eduire que le calcul tr`es pr´ecis des produits scalaires est crucial pour assurer le succ`es pratique (informatique) de la convergence de la m´ethode.

4.2) Montrer que l"´etatxkr´ealise le minimum de la fonctionnelleJsur le sous-

espace affinex0+< w0, ... , wk-1>passant par le pointx0et d"espace vecto- riel associ´e engendr´e par les vecteursw0, ... , wk-1.Quel commentaire pouvez- vous faire ? FD, octobre 1993, janvier 1995, aoˆut 1999, juillet 2002, novembre 2006. 2

Algorithme du gradient conjugu´e.Proposition de corrig´e.1) La fonctionnelleJa bien un minimum car la matriceAest sym´etrique

d´efinie positive. L"´equation d"Euler au point de minimum s"´ecrit ici : J ?(x)(Ax-b) = 0,ce qui montre la propri´et´e.

2.1) On a simplement

(14)ρk-1=-(gk-1, wk-1) (wk-1, Awk-1).

2.2) La condition pr´ec´edente a ´et´e obtenue en ´ecrivant qu"au pointxk,la

fonctionnelleJest minimale si on la restreint `a la droite affine passant parxk-1 et dirig´ee par le vecteurwk-1ce qui s"exprime en annulant le gradient deJau pointxkdans la directionwk-1,ce qui constitue exactement la condition (6).

2.2) On a imm´ediatement

(15)αk=-(gk, Awk-1) (wk-1, Awk-1).

3.1) D`es que l"un des gradientsgmest nul, on est en un pointxmqui est

solution du syst`eme (1) et l"algorithme ne pr´esente plus alors aucun int´erˆet puisque l"on a r´esolu le probl`eme pos´e.

3.2) On montre la propri´et´e par r´ecurrence.

La propri´et´e est vraie pourk= 1.On remarque quew0=g0est non nul en vertu de la question pr´ec´edente. On a ensuite (g1, w0) = 0 compte tenu de la relation (6). Si on consid`ere la relation (7) pourk= 1 et qu"on la multiplie scalairement parg1,on obtient (g1, w1) =?g1?2,ce qui montre quew1est non nul puisqueg1est non nul. Le num´erateur comme le d´enominateur de l"expression (14) qui permet de calculerρ0sont non nuls, doncρ0est non nul et la relation (10) est vraie `a l"ordrek= 0.La relation (11) est une cons´equence simple du choix de la direction de descente initiale : (g1, g0) = (g1, w0) = 0 compte tenu de la relation (9). Enfin, la relation (12) exprime simplement la relation (8) pour k= 1. On suppose les relations (9) `a (12) v´erifi´ees jusqu"`a l"ordrekinclus et on les ´etend pour l"indicek+ 1, en supposantgk+1non nul. On remarque d"abord que la relation (3) entraˆıne clairement (16)gk+1=gk+ρkAwk. On a d"une part (gk+1, wk) = 0 compte tenu de la relation (6) et pourj < k, on a d"autre part (gk+1, wj) = (gk+1-gk, wj) + (gk, wj) =ρk(Awk, wj) compte tenu de (16) et de l"hypoth`ese de r´ecurrence (9). Or cette derni`ere expression est 3 nulle en vertu de l"hypoth`ese de r´ecurrence (12), donc la relation (9) est ´etablie. Si on multiplie scalairement l"identit´e (7) ´ecrite au rangk+1 pargk+1,la relation (9) que nous venons de d´emontrer entraˆıne que l"on a (17) (gk+1, wk+1) =?gk?2, et la relation (10) est alors une cons´equence simple de la relation qui permet de calculerρk.Exprimonsgjgrˆace `a la relation (7) (consid´er´ee aveck=j). Il vient (gk+1, gj) = (gk+1, wj)-αj(gk+1, wj-1) et cette expression est nulle compte tenu de la relation (9) prise `a l"ordrek+ 1. Ceci montre la relation (11). La relation (12) est la cons´equence de la relation (8) pourj=ket du calcul suivant pourj < k: (wk+1, Awj) = (gk+1, Awj) compte tenu de (7) et de (12) = (gk+1,1

ρj(gj+1-gj)) en vertu de (16)

= 0compte tenu de (11) . La propri´et´e est donc d´emontr´ee par r´ecurrence.

3.3) Compte tenu de la relation (11), la suite de gradientsg0, g1, ... , gkest

compos´ee de vecteurs orthogonaux deux `a deux jusqu"`a un ordremet ceci a lieu dans l"espace IR n.La conclusion est alors claire.

4.1) Dans la relation (15), on exprime le vecteurAwk-1au num´erateur et

au d´enominateur `a l"aide de la relation (16) et on utilise la relation (11) pour le num´erateur. Il vient : k=?gk?2 (gk-1, wk-1) et la relation (13) est alors cons´equence directe de la relation (17).

4.2) Si on ´ecrit l"in´equation d"Euler qui caract´erise le minimum de la fonction

convexe d´erivableJsur le convexe ferm´ex0+< w0, ... wk-1>,atteint au pointy?IRnil vientJ?(y)wj= 0 pour toutj= 1,2,...,k-1.Mais le choixy=xkv´erifie ces relations puisque d"une partxkappartient au convexe x

0+< w0, ... wk-1>,compte tenu de l"initialisation de l"algorithme et de la

relation constitutive (3) et d"autre partJ?(xk)wj= (gk, wj) lequel est nul en vertu de la relation (9). Cette propri´et´e montre que le pointxk, con¸cu initialement `a la relation (4) pour minimiser la fonctionnelleJle long de la droite affine passant parxk-1 et dirig´ee selon le vecteurwk-1la minimise en fait sur tout un sous espace de dimensionk! On touche l`a au g´enie de Hestenes et Stiefel qui ont invent´e la m´ethode du gradient conjugu´e en 1952. FD, octobre 1993, janvier 1995, aoˆut 1999, juillet 2002, novembre 2006. 4quotesdbs_dbs18.pdfusesText_24

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

,?le