Analyse numérique avancée Corrigé du TD 1 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 ...

Sup-Galilée - MACS-2 Analyse numérique avancée

Analyse numérique avancée

Corrigé du TD 1

M. Kern

18 février 2021

Merci à :

- Matthieu Grondin et Christophe Sive pour l"exercice 1; - Imad Badda et Martin Duguey pour l"exercice 2; - Alexandre Chautard et Sarobidy Randimbiarison pour l"exercice 4; - Yphta Mbangue Lobe et Youssouf Traore pour l"exercice 5; - Lionel Ouedraogo et Bahassane Zalhata pour l"exercice 6.

Exercice 1 : Convergence du gradient conjugué

1La majoration du cours (inégalité (1.18)) conduit à

kln p1p+ 1 log"2 soit (attention aux signes, les deux quantités dans les logs sont plus petites que 1) k1ln p1p+ 1 log2" Il est utile d"effectuer un développement limité de l"argument du logarithme dans la limite1. En écrivant 1log p1p+ 1 =1log

12p+ 1

p 2 on obtient le résultat plus simple à interpréter : k'p 2 ln2" On remarque que la majoration analogue pour la méthode du gradient à pas optimal fait intervenir la quantité, alors qu"ici on ap. Siest grand, la différence est importante. 1 Sup-Galilée - MACS-2 Analyse numérique avancée

2D"après le résultat rappelé dans le cours (formule en bas de la page 18, voire aussi

les notes sur le Laplacien), le conditionnement de la matrice du Laplacien sur une grille avecNpoints par direction (donc avec un pash= 1=(N+ 1), et le nombre d"inconnues estn=N2), vérifie pourhpetit (A) =cos

2N2(N+ 1)sin

2N2(N+ 1)

4 2h2:

D"après la question précédente, le nombre d"itérations nécessaires pour réduire l"erreur

d"un facteur"est donc, au premier ordre k'h4log2" Pour atteindre un niveau de réduction de l"erreur fixé, le nombre d"itérations sera donc proportionnel au pas du maillage.

3Il est naturel de choisir= 1=n, puisque dans ce casp(n) = 0et qu"on a alors

l"inégalité jp()j jq()j;82[0;n]: La majoration du Corollaire 1.1 du cours permet donc d"écrire kxkxkAmax2[c;d]jq()jkx0xkA: En choisissantqde degrén1qui minimise la quantité correspondante au max, on utilise

le résultat rappelé dans l"énoncé, mais aveckremplacé park1(une itération pour " se

débarrasser » de la plus grande valeur propre), etremplacé par~=d=c, qui peut être beaucoup plus petit. En reprenant l"estimation simplifiée, on a donc k'1 +p~2 ln2"

Exercice 2 : Coût du gradient conjugué

Remarque préliminaire: les estimations de coût de calculs doivent toujours être interprétées avec précaution. Tout d"abord, on ne retient que le terme dominant. Ensuite,

le modèle de coût élémentaire utilisé n"est pas précisé : par exemple, les additions et les

multiplications sont-elle comptées ensemble ou séparément? Cela ne change pas le terme dominant, mais introduit évidemment un facteur 2. Enfin, sur les ordinateurs actuels, le coût principal d"un calcul est plus dû aumouvementdes données qu"au calcul. 2 Sup-Galilée - MACS-2 Analyse numérique avancée

1Dans l"algorithme du gradient conjugué (Algorithme 1.2), les trois opérations conte-

nant des combinaisons linéaires ont un coût proportionnel àn(la taille du système). Il en

est de même pour les deux produits scalaires. Il reste donc le calcul deAp(il est bien entendu inutile d"effectuer ce calcul deux fois,

on sauve le résultat dans un vecteur intermédiaire). Pour une matrice pleine générale, cette

opération a un coût proportionnel àn2.

Le coût total est évidemment le coût d"une itération multiplié par le nombre d"itérations.

Ici, nous utilisons le gradient conjugué comme une méthode directe, et donc nous comptons lesnitérations pour obtenir la solution exacte. Dans ce cas, le coût total de la méthode est proportionnel àn3. C"est le même ordre de grandeur que pour la méthode Cholesky ou de Gauss, mais une estimation plus précise montre que le coût du gradient conjugué est plus important que pour ces deux méthodes.

2Si maintenantAest la matrice du Laplacien sur une grille avecNpoints par coté,

le coût de l"opération " produit matrice vecteur » devient proportionnel àN. En effet, la

matrice en question a 5 diagonales non-nulles, donc le calcul de chaque élément du produit ne demande au plus que 5 opérations (addition et multiplication). Le coût d"une itération devient donc proportionnel àn(nest le nombre d"inconnues, avecn=N2). Et dans ce cas, il est naturel d"employer la méthode du gradient conjugué comme

une méthode itérative, et donc d"estimer le nombre d"itérations pour réduire l"erreur d"un

facteur fixé (la valeur du facteur ne change pas la complexité). D"après l"exercice précédent

(question 2), ce nombre d"itération est proportionnel àN=pn, ce qui montre que le coût total est proportionnel àn3=2. Une comparaison juste avec les méthodes directes considère

les méthodes spécialisées pour les matrices creuses, et conduisent à une complexité du même

ordre. Pour conclure, notons qu"il existe des méthodes " optimales », c"est-à-dire avec un

coût proportionnel àn, pour résoudre ce problème : il s"agit des méthodes multigrilles. On

ne peut pas faire mieux, puisqu"il faut évidemment que chaque inconnue intervienne dans le calcul de la solution, d"où un coût minimal proportionnel àn. Exercice 3 : Récurrences à 3 terme et algorithme de

Lanczos

1On prend les notations du Chapitre 1 du cours.

On part de la relation (1.8) qui définitpk, que l"on rend explicite, p k=1 k(xk+1xk)

et de la même relation écrite au rangk1, et l"on reporte ces égalités dans la récurrence

depk(1.10), on obtient 1 k(xk+1xk) =rk+k11 k1(xkxk1) 3 Sup-Galilée - MACS-2 Analyse numérique avancée ce qui donne x k+1=krk+ 1 +k k1 k1 x kk k1 k1xk1: On multiplie cette égalité parA, on change de signe, et on ajoutebde chaque côté, en remarquant que la somme des coefficients dexketxk1vaut 1 : (*)rk+1=kArk+ 1 +k k1 k1 r kk k1 k1rk1:

2Puisque le vecteursqkest, à un facteur multiplicatif près, égal àrk1, on sait que

(q1;:::;qk)forme une base orthonormée deKk(r0)(le vecteurqkest identique à celui noté v kau Chapitre 2). On peut donc poserxk=x0+Qkyk, avecyk2Rk,etrk=r0AQkyk. Comme on sait quexkestcaractérisédansx0+Kk(r0)par la conditionrk?Kk(r0),ykvérifie Q

Tk(r0AQkyk);soitQTkAQkyk=QTkr0:

On note que, puisqueAest définie positive et queQkest de rang maximum, la matrice Q TKAQkest également définie positive, ety)kest ainsi bien défini.

3On part de la relation (*) dans laquelle on remplacerjparkrjkqj+1pourj=k

1;k;k+ 1, et on utilise la définition dek=krk+1k2krkk2pour obtenir, après un court calcul

Aq k=p k1 k1q k+1+1 k1+k2 k2 q kp k2 k2q k1:

Si l"on désigne parTkla matrice tridiagonale :

T k=0quotesdbs_dbs2.pdfusesText_3

[PDF] Analyse numérique avancée Corrigé du TD 1