[PDF] LICENCE 3 MATHEMATIQUES – INFORMATIQUE

View - Download LICENCE 3 MATHEMATIQUES – INFORMATIQUE

Previous PDF

Next PDF

LICENCE 3 MATHEMATIQUES - INFORMATIQUE.

MATHEMATIQUES GENERALES.

L3MiMG.

Expédition dans la semaine n°EtapeCode UEN° d'envoi de l'UE

472L3MATSMI5U4T2

Nom de l'UE : Analyse numérique et optimisation

Le cours contient 3 chapitres (systèmes linéaires, systèmes non linéaires, optimisation). Pour chaque semaine, il est

proposé d'étudier une partie du cours, de faire des exercices (corrigés) et, éventuellement, de réaliser un TP en

python. Les TP sont conseillés mais non obligatoires. Deux devoirs sont à rendre afin de bénéficier d'une note de

contrôle continu. note finale=max(note-examen, 1/3(2 note-examen + note-contrôle-continu)). - Contenu de l'envoi : Polycopié, chapitre 1, paragraphe 5. TP 3 - Guide du travail à effectuer

Semaine 1 :

Etudier les paragraphes 1.5.1 (méthodes itératives, définition et propriétés) Exercice proposé (avec corrigé) : 55 (convergence de suites)

Semaine 2 :

Etudier le paragraphe 1.5.2, méthodes de Richardson et Jacobi. Exercices proposés (avec corrigés) : 56 (sur Richardson) et 57 (sur Jacobi)

Semaine 3 :

Etudier le paragraphe 1.5.2, méthode de Gauss-Seidel Exercices proposés (avec corrigés) : 58 (comparaison Jacobi/Gauss-Seidel) et 59 (Jacobi avec relaxation). commencer le deuxième TP 3 (Jacobi, Gauss-Seidel)

Semaine 4 :

Etudier les paragraphes 1.5.2, méthodes SOR et SSOR, et 1.5.3 (méthodes par blocs) Exercice proposés(avec corrigé) : 65 (Jacobi et Gauss-Seidel). Finir le TP 3 (SOR)

L'exercice 72 fait partie du premier devoir (à rendre en janvier)-Coordonnées de l'enseignant responsable de l'envoi

T. Gallouet, CMI, 39 rue Joliot Curie, 13453 marseille cedex 13 email : thierry.gallouet@univ-amu.fr Vous pouvez aussi consulter la page web: http://www.cmi.univ-mrs.fr/~gallouet/tele.d/anum.d et me poser des questions par email

A i x M a r s e i l l e U n i v e r s i t é - C e n t r e d e T é l é - E n s e i g n e m e n t S c i e n c e sCase ??. ?, place Victor Hugo. 1???1 Marseille Cedex 0?.

http://www.ctes.univ-provence.fr P o u r r a p p r o c h e r l a c o n n a i s s a n c e

1.5. MÉTHODES ITÉRATIVESCHAPITRE 1. SYSTÈMES LINÉAIRES

1.5 Méthodes itératives

Les méthodes directes sont très efficaces : elles donnent la solution exacte (aux erreurs d"arrondi près) du système

linéaire considéré. Elles ont l"inconvénient de nécessiter une assez grande place mémoire car elles nécessitent le

stockage de toute la matrice en mémoire vive. Si la matrice est pleine, c.à.d. si la plupart des coefficients de la

matrice sont non nuls et qu"elle est trop grosse pour la mémoire vive de l"ordinateur dont on dispose, il ne reste

plus qu"à gérer habilement le "swapping" c"est-à-dire l"échange de données entre mémoire disque et mémoire

vive pour pouvoir résoudre le système.

Cependant, si le système a été obtenu à partir de la discrétisation d"équations aux dérivés partielles, il est en

général "creux", c.à. d. qu"un grand nombre des coefficientsde la matrice du système sont nuls; de plus la matrice

a souvent une structure "bande",i.e.les éléments non nuls de la matrice sont localisés sur certaines diagonales.

On a vu au chapitre précédent que dans ce cas, la méthode de Choleski "conserve le profil" (voir à ce propos page

45). Si on utilise une méthode directe genre Choleski, on aura donc besoin de la place mémoire pour stocker la

strucutre bande.

Lorsqu"on a affaire à de très gros systèmes issus par exemplede l"ingénierie (calcul des structures, mécanique des

fluides, ...), oùnpeut être de l"ordre de plusieurs milliers, on cherche à utiliser des méthodes nécessitant le moins

de mémoire possible. On a intérêt dans ce cas à utiliser des méthodes itératives. Ces méthodes ne font appel qu"à

des produits matrice vecteur, et ne nécessitent donc pas le stockage du profil de la matrice mais uniquement des

termes non nuls. Par exemple, si on a seulement 5 diagonales non nulles dans la matrice du système à résoudre,

système denéquations etninconnues, la place mémoire nécessaire pour un produit matrice vecteur est6n. Ainsi

pour les gros systèmes, il est souvent avantageux d"utiliser des méthodes itératives qui ne donnent pas toujours la

solution exacte du système en un nombrefini d"itérations,mais qui donnentune solution approchéeà coût moindre

qu"une méthode directe, car elles ne font appel qu"à des produits matrice vecteur. Remarque 1.45(Sur la méthode du gradient conjugué).

Il existe une méthode itérative "miraculeuse" de résolution des systèmes linéaires lorsque la matriceAest symé-

trique définie positive : c"est la méthode du gradient conjugué. Elle est miraculeuse en ce sens qu"elle donne la

solution exacte du systèmeAx=ben un nombre fini d"opérations (en ce sens c"est une méthode directe) : moins

denitérations oùnest l"ordre de la matriceA, bien qu"elle ne nécessite que des produits matrice vecteurou des

produits scalaires. La méthode du gradient conjugué est en fait une méthode d"optimisation pour la recherche du

minimum dansIRnde la fonction deIRndansIRdéfinie par :f(x) =1

2Ax·x-b·x. Or on peut montrer que

lorsqueAest symétrique définie positive, la recherche dexminimisantfdansIRnest équivalent à la résolution

du systèmeAx=b. (Voir paragraphe 3.2.2 page 215.) En fait, la méthode du gradient conjugué n"est pas si

miraculeuse que cela en pratique : en effet, le nombrenest en général très grand et on ne peut en géneral pas

envisager d"effectuer un tel nombre d"itérations pour résoudre le système. De plus, si on utilise la méthode du

gradient conjuguébrutalement, non seulement elle ne donnepas la solution ennitérations en raison de l"accumu-

lation des erreurs d"arrondi, mais plus la taille du systèmecroît et plus le nombre d"itérations nécessaires devient

élevé. On a alors recours aux techniques de "préconditionnement". Nous reviendrons sur ce point au chapitre 3.

La méthode itérative du gradient à pas fixe, qui est elle aussiobtenue comme méthode de minimisation de la

fonctionfci-dessus, fait l"objet de l"exercice 56 page 108 et du théorème 3.19 page 224.

1.5.1 Définition et propriétés

SoitA?Mn(IR)une matrice inversible etb?IRn, on cherche toujours ici à résoudre le système linéaire (1.1)

c"est-à-dire à trouverx?IRntel queAx=b, mais de façon itérative, c.à.d. par la construction d"une suite.

Définition 1.46(Méthode itérative).On appelle méthode itérative de résolution du système linéaire(1.1)une

méthode qui construit une suite(x(k))k?IN(où l"itéréx(k)est calculé à partir des itérésx(0)...x(k-1)censée

converger versxsolution de(1.1)). Bien sûr, on souhaite que cette suite converge vers la solutionxdu système.

Analyse numérique I, télé-enseignement, L397Université d"Aix-Marseille, R. Herbin, 17 novembre 2017

1.5. MÉTHODES ITÉRATIVESCHAPITRE 1. SYSTÈMES LINÉAIRES

Définition 1.47(Méthode itérative convergente).On dit qu"une méthode itérative est convergente si pour tout

choix initialx(0)?IRn,on a : x (k)-→xquandk→+∞

qui soit "proche" deA, mais plus facile queAà inverser. On appelle matrice de préconditionnementcettematrice

P. On écrit alorsA=P-(P-A) =P-N(avecN=P-A), et on réécrit le système linéaireAx=bsous la forme

Px= (P-A)x+b=Nx+b.(1.91)

Cette forme suggère la construction de la suite(x(k))k?INà partir d"un choix initialx(0)donné, par la formule

suivante :Px(k+1)= (P-A)x(k)+b =Nx(k)+b,(1.92) ce qui peut également s"écrire :. x (k+1)=Bx(k)+c,avecB=P-1(P-A) = Id-P-1A=P-1Netc=P-1b.(1.93) Remarque 1.48(ConvergenceversA-1b).SiPx(k+1)= (P-A)x(k)+bpour toutk?INetx(k)-→¯xquand

k-→+∞alorsP¯x= (P-A)¯x+b, et doncA¯x=b, c.à.d.¯x=x. En conclusion, si la suite converge, alors

elle converge bien vers la solution du système linéaire. On introduit l"erreur d"approximatione(k)à l"itérationk, définie par e (k)=x(k)-x, k?IN(1.94)

oùx(k)est construit par (1.93) etx=A-1b.Il est facile de vérifier quex(k)→x=A-1blorsquek→+∞si

et seulement sie(k)→0lorsquek→+∞ Lemme 1.49.La suite(e(k))k?INdéfinie par(1.94)est également définie par e (0)=x(0)-x e (k)=Bke(0)(1.95)

DÉMONSTRATION- Commec=P-1b=P-1Ax, on a

e (k+1)=x(k+1)-x=Bx(k)-x+P-1Ax(1.96) =B(x(k)-x).(1.97)

Par récurrence surk,

e (k)=Bk(x(0)-x),?k?IN.(1.98)

Théorème 1.50(Convergencede la suite).SoitAetP?Mn(IR)des matrices inversibles. Soitx(0)donné et soit

(x(k))k?INla suite définie par(1.93).

1. La suite(x(k))k?INconverge, quel que soitx(0), versx=A-1bsi et seulement siρ(B)<1.

2. La suite(x(k))k?INconverge,quel que soitx(0), si et seulement si il existe une norme induite notée?·?telle

que?B?<1.

Analyse numérique I, télé-enseignement, L398Université d"Aix-Marseille, R. Herbin, 17 novembre 2017

1.5. MÉTHODES ITÉRATIVESCHAPITRE 1. SYSTÈMES LINÉAIRES

DÉMONSTRATION-

1. On a vu que la suite(x)(k))k?INdéfinie par (1.93) converge versx=A-1bsi et seulement si la suitee(k)définie

par (1.95) tend vers0. On en déduit par le lemme 1.33 que la suite(x)(k))k?INconverge (versx), pour toutx(0), si

et seulement siρ(B)<1.

2. Si il existe une norme induite notée? · ?telle que?B?<1, alors en vertu du corollaire 1.33,ρ(B)<1et donc la

méthode converge pour toutx(0).

Réciproquement, si la méthode converge alorsρ(B)<1, et donc il existeη >0tel queρ(B) = 1-η.Prenons

maintenantε=η ce qui démontre le résultat.

Pour trouver des méthodes itératives de résolution du système (1.1), on cherche donc une décomposition de la

matriceAde la forme :A=P-(P-A) =P-N, oùPest inversible et telle que le systèmePy=dsoit un système facile à résoudre (par exemplePdiagonale ou triangulaire).

Estimation de la vitesse de convergenceSoitx(0)?IRndonnéet soit(x(k))k?INla suite définie par (1.93). On

a vu que, siρ(B)<1,x(k)→xquandk→ ∞, oùxest la solution du systèmeAx=b. On montre à l"exercice

75 page 140 que (sauf cas particuliers)

?x(k+1)-x?

indépendammentde la norme choisie surIRn. Le rayon spectralρ(B)de la matriceBest donc une bonne estima-

tion de la vitesse de convergence. Pour estimer cette vitesse de convergence lorsqu"on ne connaît pasx, on peut

utiliser le fait (voir encore l"exercice 75 page 140) qu"on aaussi ?x(k+1)-x(k)? ?x(k)-x(k-1)?-→ρ(B) :lorsquek→+∞,

ce qui permet d"évaluer la vitesse de convergence de la méthode par le calcul des itérés courants.

1.5.2 Quelques exemples de méthodes itératives

Une méthode simpliste

Le choix le plus simple pour le systèmePx= (P-A)x+bsoit facile à résoudre (on rappelle que c"est un

objectif dans la construction d"une méthode itérative) estde prendre pourPla matrice identité (qui est très facile

à inverser!). Voyons ce que cela donne sur la matrice

A=?2-1

-1 2? .(1.99)

On a alorsB=P-A=?-1 1

1-1? .Les valeurs propres deBsont 0 et -2 et on a doncρ(B) = 2>1. La suite

(e(k))k?INdéfinie pare(k)=Bke(0)n"est donc en général pas convergente. En effet, sie(0)=au1+bu2, où

u 1=?1 -1?

est vecteur propre deBassocié à la valeur propreλ=-2, on ae(k)= (-2)kaet donc|e(k)| →+∞

lorsquek→ ∞dès quea?= 0. Cette première idée n"est donc pas si bonne...

Analyse numérique I, télé-enseignement, L399Université d"Aix-Marseille, R. Herbin, 17 novembre 2017

1.5. MÉTHODES ITÉRATIVESCHAPITRE 1. SYSTÈMES LINÉAIRES

La méthode de Richardson

Affinons un peu et prenons maintenantP=βId, avecβ?IR. On a dans ce casP-A=βId-AetB= Id-1

βA= Id-αAavecα=1β. Les valeurs propres deBsont de la forme1-αλ, oùλest valeur propre deA.

Pour la matriceAdéfinie par (1.99), les valeurs propres deAsont 1 et 3, et les valeurs propres de

B=?1-2α α

α1-2α,?

sont1-αet1-3α. Le rayon spectral de la matriceB, qui dépend deαest doncρ(B) = max(|1-α|,|1-3α|),

qu"on représente sur la figure ci-dessous. La méthode itérative s"écrit x (0)?IRndonné, x (k+1)=Bx(k)+c,avecc=αb.(1.100) Pour que la méthode converge, il faut et il suffit queρ(B)<1, c.à.d.3α-1<1, doncα <2

3. On voit que le

choixα= 1qu"on avait fait au départ n"était pas bon. Mais on peut aussicalculer le meilleur coefficientαpour

avoir la meilleure convergence possible : c"est la valeur deαqui minimise le rayon spectralρ; il est atteint pour

1-α= 3α-1, ce qui donneα=1

2. Cette méthode est connue sous le nom deméthode de Richardson8. Elle est

souvent écrite sous la forme : x (0)?IRndonné, x (k+1)=x(k)+αr(k),

oùr(k)=b-Ax(k)est le résidu. On vérifie facilement que cette forme est équivalente à la forme (1.100) qu"on

vient d"étudier. $1/3$ $1$1/2 |1-α|

αρ(B)|1-3α|

FIGURE1.4: Rayon spectral de la matriceBde Richardson en fonction du coefficientα.

La méthode de Jacobi

Dans le cas de l"exemple de la matriceAdonné par (1.99), la méthode de Richardson avec le coefficient optimal

α=1

2revient à prendre comme décomposition deA=P+A-Pavec comme matriceP=D, oùDest la

8. Lewis Fry Richardson, (1881-1953) est un mathématician,physicien, météorologue et psychologue qui a introduit lesméthodes ma-

thématiques pour les prévisions métérologiques. Il est également connu pour ses travaux sur les fractals. C"était un pacifiste qui a abandonné

ses travaux de météorologie en raison de leur utillisation par l"armée de l"air, pour se tourner vers l"étude des raisonsdes guerres et de leur

prévention.

Analyse numérique I, télé-enseignement, L3100Université d"Aix-Marseille, R. Herbin, 17 novembre 2017

1.5. MÉTHODES ITÉRATIVESCHAPITRE 1. SYSTÈMES LINÉAIRES

matrice diagonale dont les coefficients sont les coefficients situés sur la diagonale deA. Laméthode de Jacobi9

consiste justement à prendreP=D, et ce même si la diagonale deAn"est pas constante.

Elle n"est équivalente à la méthode de Richardson avec coefficient optimal que dans le cas où la diagonale est

constante; c"est le cas de l"exemple (1.99), et donc dans ce cas la méthode de Jacobi s"écrit x (0)=? x(0)1 x(0)2? ?IR2donné, x (k+1)=? x(k+1) 1 x(k+1) 2? =BJx(k)+c,avecBJ=?01 21
20,? etc=12b.(1.101)

Dans le cas d"une matriceAgénérale, on décomposeAsous la formeA=D-E-F, oùDreprésente la

diagonale de la matriceA,(-E)la partie triangulaire inférieure et(-F)la partie triangulaire supérieure :

D=??????a

1,10...0

0 .......0

0 0an,n??????

,-E=??????0 0...0 a

2,1......

.......0 a n,1... an-1,n0?????? et-F=??????0a1,2... a1,n......... .......an,n-1

0...0-0??????

(1.102)

La méthode de Jacobi s"écrit donc :

?x(0)?IRn

Dx(k+1)= (E+F)x(k)+b.(1.103)

Lorsqu"on écrit la méthode de Jacobi comme sous la forme (1.93) on aB=D-1(E+F); on noteraBJcette

matrice : B

J=???????0-a1,2

a1,1...--a1,na1,1 a2,1 a2,2...--a2,na2,2............ an,1 an,n...--an-1,nan,n0???????

La méthode de Jacobi s"écrit aussi :

?x (0)?IRn a i,ix(k+1) i=-? jia i,jx(k) j+bii= 1,...,n.(1.104)

La méthode de Gauss-Seidel

Dans l"écriture (1.104) de la méthode de Jacobi, on pourraitremplacer les composantesx(k) jdans la somme pour j < ipar les composantesx(k+1) j, puisqu"elles sont déjà calculées au moment où l"on calculex(k+1) i. C"est l"idée de la méthode de Gauss-Seidel

10qui consiste à utiliser le calcul des composantes de l"itéré(k+ 1)dès qu"il est

effectué. Par exemple, pour calculer la deuxième composantex(k+1)

2du vecteurx(k+1), on pourrait employer la

9. Carl G. J. Jacobi, (1804 - 1851), mathématicien allemand.Issu d"une famille juive, il étudie à l"Université de Berlin, où il obtient

son doctorat à 21 ans. Sa thèse est une discussion analytiquede la théorie des fractions. En 1829, il devient professeur de mathématique à

pensionnaire royal jusqu"à sa mort. Sa lettre du 2 juillet 1830 adressée à Legendre est restée célèbre pour la phrase suivante, qui a fait couler

beaucoup d"encre : "M. Fourier avait l"opinion que le but principal des mathématiques était l"utilité publique et l"explication des phénomènes

naturels; mais un philosophe comme lui aurait dû savoir que le but unique de la science, c"est l"honneur de l"esprit humain, et que sous ce titre,

une question de nombres vaut autant qu"une question du système du monde." C"est une question toujours en discussion....

10. Philipp Ludwig von Seidel (Zweibrücken, Allemagne 1821- Munich, 13 August 1896) mathématicien allemand dont il estdit qu"il a

découvert en 1847 le concept crucial de la convergence uniforme en étudiant une démonstration incorrecte de Cauchy.

Analyse numérique I, télé-enseignement, L3101Université d"Aix-Marseille, R. Herbin, 17 novembre 2017

1.5. MÉTHODES ITÉRATIVESCHAPITRE 1. SYSTÈMES LINÉAIRES

"nouvelle" valeurx(k+1)

1qu"on vient de calculer plutôt que la valeurx(k)

1comme dans (1.104); de même, dans le

calcul dex(k+1)

3, on pourrait employer les "nouvelles" valeursx(k+1)

1etx(k+1)

2plutôt que les valeursx(k)

1etx(k)

2. Cette idée nous suggère de remplacer dans (1.104)x(k) jparx(k+1) jsij < i. On obtient donc l"algorithme suivant : ?x(0)?IRn a i,ix(k+1) i=-? jP-A=F:?x0?IRn (D-E)x(k+1)=Fx(k)+b.(1.106) Si l"on écrit la méthode de Gauss-Seidel sous la formex(k+1)=Bx(k)+c, on voit assez vite queB= (D-E)-1F; on noteraBGScette matrice, dite matrice de Gauss-Seidel.

Ecrivonsla méthodedeGauss-Seidel dansle cas dela matriceAdonnéepar(1.99) : ona dansce casP=D-E=?2 0

-1 2? , F=?0 10 0,? .L"algorithme de Gauss-Seidel s"écrit donc : x (0)=? x(0)1 x(0)2? ?IR2donné, x (k+1)=? x(k+1) 1 x(k+1) 2? =BGSx(k)+c,avecBGS=?0 001 4? etc=? 1 20 1 412?
b.(1.107)

On a doncρ(BGS) =1

4. Sur cet exemple la méthode de Gauss-Seidel converge donc beaucoup plus vite que la

méthode de Jacobi : Asymptotiquement, l"erreur est diviséepar 4 à chaque itération au lieu de 2 pour la méthode

de Jacobi. On peut montrer que c"est le cas pour toutes les matrices tridiagonales, comme c"est énoncé dans le

théorème suivant :

Théorème 1.51(Comparaison de Jacobi et Gauss-Seidel pour les matrices tridiagonales).On considère une ma-

triceA?Mn(IR)tridiagonale, c.à.d. telle queai,j= 0si|i-j|>1; soientBGSetBJles matrices d"itération

respectives des méthodes de Gauss-Seidel et Jacobi, alors :

ρ(BGS) = (ρ(BJ))2.

Pour les matrices tridiagonales, la méthode de Gauss-Seidel converge (ou diverge) donc plus vite que celle de

Jacobi.

La démonstration de ce résultat se fait en montrant que dans le cas tridiagonal,λest valeur propre de la matrice

d"itération de Jacobi si et seulement siλ2est valeur propre de la matrice d"itération de Gauss-Seidel. Elle est

laissée à titre d"exercice.

Méthodes SOR et SSOR

L"idée de la méthode de sur-relaxation (SOR = Successive Over Relaxation) est d"utiliser la méthode de Gauss-

Seidel pour calculer un itéré intermédiaire˜x(k+1)qu"on "relaxe" ensuite pour améliorer la vitesse de convergence

de la méthode. On se donne0< ω <2, et on modifie l"algorithme de Gauss-Seidel de la manière suivante :

?x 0?IRn a i,i˜x(k+1) i=-? jAnalyse numérique I, télé-enseignement, L3102Université d"Aix-Marseille, R. Herbin, 17 novembre 2017

1.5. MÉTHODES ITÉRATIVESCHAPITRE 1. SYSTÈMES LINÉAIRES

(Pourω= 1on retrouve la méthode de Gauss-Seidel.)

L"algorithme ci-dessus peut aussi s"écrire (en multipliant parai,ila ligne 3 de l"algorithme (1.108)) :

?x (0)?IRn a i,ix(k+1) i=ω?? jia i,jx(k) j+bi?? +(1-ω)ai,ix(k) i.(1.109)

On obtient donc

(D-ωE)x(k+1)=ωFx(k)+ωb+ (1-ω)Dx(k). La matrice d"itération de l"algorithme SOR est donc B

ω=?D

ω-E?

-1 (F+?1-ωω?

D) =P-1N,avecP=Dω-EetN=F+?1-ωω?

D.

Il est facile de vérifier queA=P-N.

Proposition 1.52(Condition nécessaire de convergence de la méthode SOR). SoitA?Mn(IR)et soietD,EetFles matrices définies par(1.102); on a doncA=D-E-F. SoitBωla

matrice d"itération de la méthode SOR (et de la méthode de Gauss-Seidel pourω= 1) définie par :

Bquotesdbs_dbs1.pdfusesText_1

[PDF] exercices corrigés microéconomie 1ère année

[PDF] exercices corrigés microéconomie équilibre général

[PDF] exercices corrigés mitose

[PDF] exercices corrigés mouvement des satellites

[PDF] exercices corrigés mouvement seconde

[PDF] exercices corrigés ondes seconde

[PDF] exercices corrigés ondes terminale s

[PDF] exercices corrigés optimisation non linéaire

[PDF] exercices corrigés optique géométrique pdf

[PDF] exercices corrigés optique ondulatoire mp

[PDF] exercices corrigés orthogonalité dans l'espace

[PDF] exercices corrigés outlook 2010

[PDF] exercices corrigés pendule elastique

[PDF] exercices corrigés pert pdf

[PDF] exercices corrigés ph des solutions aqueuses