Méthode du gradient conjugué

Algorithmes 4 Méthodes de descente. Problèmes sans contraintes 4.1 Principe . . . . . . . . . . . . . . . . . . . . . . . 4.2 Méthode de relaxation . . . . . . . . . . . . . . . 4.3 Méthode du gradient . . . . . . . . . . . . . . . . 4.3.1 Méthode à pas variable . . . . . . . . . . . 4.3.2 Méthode à pas optimal . . . . . . . . . . . 4.4 Estimations et convergence dans le cas quadratique 4.4.1 Méthode à pas optimal . . . . . . . . . . . 4.4.2 Méthode de gradient à pas constant . . . . 4.5 Méthode du gradient

II.1- Méthode de Dichotomie ........................................................................................ | 5 | II.2- Méthode de NEWTON ......................................................................................... | 7 | III- Exercice 2 : Méthodes de gradient pour des fonctionnelles quadratiques ................... | 8 | III.1- Etude de Jn et résolution du problème Pn ........................................................ | 8 | III.2- Méthode du gradient

linéaires : les méthodes directes . . . . . . . . . . . . . IV.1 IV.2 IV.3 IV.4 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . La méthode de Gauss et quelques variantes . . . . . . . . . . . . . . . . . . Propriétés supplémentaires . . . . . . . . . . . . . . . . . . . . . . . . . . . Les méthodes QR/QL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . V La résolution de systèmes linéaires : les méthodes itératives V.1 V

Tous ces problèmes entrent dans une grande catégorie : L’optimisation Remarque : Maximiser F(x) = Minimiser –F(x) Donc minimiser et maximiser sont en fait le même problème ! Une fois de plus, c’est un problème mal posé : Il n’y a pas de méthode idéale. Il est facile de trouver un minimum local. Il est difficile trouver un minimum absolu B,D,F sont des minimums locaux D est le minimum absolu Cette recherche est d’autant plus longue est difficile si la fonction dépend de plusieurs

Resolution du systeme lineaire 2.1 Methode de relaxation . . . . . . . . . . . . 2.2 Methodes de descente . . . . . . . . . . . . 2.2.1 Methode du gradient a pas constant 2.2.2 Methode du gradient a pas optimal . 2.2.3 Methode du gradient conjugue . . . 3 Application . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1 1 1 1 3 5 6 1 2 2.1 Rappels de la partie I Resolution du systeme lineaire Methode de relaxation min J(xk+1

e e Le calcul de la valeur d’une fonction f en un x donn´ peut ˆtre long (il e e faut par exemple sommer les premiers termes d’une s´rie de somme f (x)). La e m´thode suivante ne demande qu’une ´valuation ` chaque it´ration. e e a e 1.2 ´ METHODE DE LA SUITE DE FIBONACCI F0 = F1 = 1; Fk+2 = Fk + Fk+1 . Rappel : La suite de FIBONACCI est donn´e par la formule de r´currence : e e Ses premiers termes sont donc : 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, etc... Le rapport de deux termes successifs

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % methodes de descentes, % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % % Resolution de A*x=b, A symetrique % % Methode GPF: Gradient a pas fixe % Methode GPO: Gradient a pas Opt. % Methode GC : Gradient Conjugue' % % METHODE COMP: Comparaison de toutes les méthodes %======================================= % CHOIX DE LA METHODE: %=======================================

Ecole Polytechnique Fédérale de Lausanne Faculté Sciences de Base Chaire de Recherche Opérationnelle Sud Est Projet de master 2005-2006 Etude et illustration de méthodes itératives d’optimisation non linéaire Travail présenté par : Thierno Diallo (section d’informatique) Enseignant responsable : Assistant responsable : Professeur Dominique de Werra Benjamin Leroy-Beaulieu Lausanne, avril 2006 Prof. D. de Werra Chaire de Recherche Opérationnelle Sud-Est EPFL, FSB - IMA - ROSE

Méthodes de gradient pour des fonctionnelles quadratiques Ibrahim Boutaleb Ecole des Mines de Nancy May 4, 2010 Abstract On va essayer d’ étudier di¤érentres méthodes de gradient dans le but de trouver le minimim d’ une fonctionnelle quadratique. Lors de cette étude, on utilisera la méthode de gradient à pas …xe, la méthode de gradient à pas optimal et la méthode de gradient conjugué. 1 La fonctionnelle Jn : de A 2 Mn (R) et le vecteur b 2 Rn dé…nis par : 1 2 0 :: :: 0 4 2 : : C C 2 : :

r Programmes de calcul par la méthode des éléments finis P. GUELLEC Ingénieur civil des Mines et A . D U B O U C H E T Technicien supérieur section de mécanique des roches Laboratoire central à la section de mécanique des roches duLC.P.C. Présentation M. PAN ET Chef du département de géotechnique Laboratoire central M A méthode des éléments finis est une technique d'analyse numérique de I problèmes ayant une formulation variationnelle ; à titre d'exemple, on imm peut citer