Méthode de Newton pour différentes décompositions matricielles et PDF

La méthode de Newton

La méthode de Newton. 1) Position du problème f est une fonction dérivable sur un intervalle I. L'équation f(x)=0 admet une racine unique ? sur l'intervalle

Analyse Numérique

Ceci montre que la méthode de Newton converge de façon quadratiquesi elle converge ! Pour s'assurer de sa convergence on peut essayer d'appliquer à g le ...

CHAPITRE 2

4 Méthode de Newton Pour approcher les racines de f (x) = 0 par la méthode du point fixe on ... On a alors l' algorithme de Newton suivant :.

Algorithme sur la méthode Newton-Raphson

5 nov. 2015 Algorithme sur la méthode. Newton-Raphson. 1 Historique. La méthode de résolution des équations numériques a été initiée par Isaac New-.

Méthode de Newton

Performance de la méthode de Newton. • Si la fonction n'est pas trop non-linéaire;. • Si la dérivée de f à la solution n'est pas trop proche de 0;.

Méthode de Newton locale pour loptimisation

Méthode de Newton locale pour l'optimisation. Michel Bierlaire michel.bierlaire@epfl.ch. EPFL - Laboratoire Transport et Mobilit´e - ENAC. Méthode de Newton

Méthode de Newton généralisée en mécanique du contact

8 août 2016 - This paper is devoted to studying the global convergence of the Newton method generalized to systems of non differentiable equations issued ...

Méthode de Newton pour différentes décompositions matricielles et

27 juin 2017 La méthode de Newton (parfois appelée méthode de Newton-Raphson) est un algorithme efficace qui permet de trouver numériquement une ...

Autour de la méthode de Newton

La méthode de Newton en analyse. Soit I un intervalle de R et f : I ? R une application dérivable. Pour déterminer une approximation numérique des

Méthode de Newton

Grâce à sa convergence quadratique et sa complexité raisonnable la méthode de Newton reste une des méthodes les plus utilisée. Le choix de F est un choix

Rapport de T.I.P.E

Licence Math

ematiques L2Methode de Newton pour dierentes decompositions matricielles et autres algorithmes de calcul de valeurs propresBenjamin MASSON realise sous la direction de Philippe CALDERO

27 juin 2017

Table des matieres

1 La methode de Newton 2

1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1.2 Presentation de la methode . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1.3 Point de vue graphique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2 La decomposition polaire 5

3 Methode de Newton pour la decomposition polaire 8

3.1 Verication informatique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4 Methode de Newton pour la decomposition de Dunford 12

5 Methode des puissances pour matrices symetriques 15

6 Methode de de

ation 18

6.1 Premiere approche : cas n=2. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

18 6.2 Elaboration d'un algorithme de calcul de valeurs propres. . . . . . . . . . . . . . . . .19

7 Factorisation de Choleski 21

8 FactorisationQR22

Chapitre 1

La methode de Newton

1.1 Introduction

La methode de Newton (parfois appelee methode de Newton-Raphson) est un algorithme ecace qui permet de trouver numeriquement une approximation precise d'un zero d'une fonction. La methode telle que decrite par Newton se place dans le contexte de fonction reelle. Nous nous interessons ici a un cadre plus general ou cet algorithme est applique aux matrices. Le principal avantage de cet algorithme est sa rapidite de convergence.

1.2 Presentation de la methode

Soitfune fonction reelle dont on cherche les zeros. Exemple: calculer une racine carree revient a annuler la fonctionf(x) =x2a, pour tout reela positif. Proposition 1Soita >0alors la suite(xk)k2N, denie parxk+1=xkf(xk)f

0(xk)etx0>0, converge

verspade maniere quadratique. C'est a dire, il existeC >0tel que, pour toutk1on ajxk+1paj< Cjxkpaj2. Autrement dit, la suite desxkconverge verspaet la precision de l'approximation double a chaque iteration.

Demonstration.Icif0(x) = 2xdonc on a

x k+1=xkx2ka2xk

2x2kx2k+a2xk

x2k+a2xk 12 x k+ax k On initialise enx0>0 ce qui va assurerxk>0 doncf0(xk)6= 0 pour toutket en particulier l'existence de la suite.

Or, pour tousx;y2R+on apxy12

(x+y) (autrement dit la moyenne geometrique est inferieure a la moyenne arithmetique). 2

On en deduitxk+1=12

(xk+ax k)papour tout entier naturel k.

De plus, on a

x k+1xk=12 xk+a2xkxk =12 xk+a2xk 12 ax kxk 12 ax2kx k 12 (paxk)(pa+xk)x k0: Donc (xn)n2Nest decroissante et minoree donc elle converge vers une limite`qui verie `=12 (`+a` ),2`=`+al ,`2=aor`0 donc`=pa. On a donc montre que la suite (xn)n2Nconverge vers`=pa. Interessons nous maintenant a la vitesse de convergence de la suite. NotonsFla fonction telle que x k+1=F(xk) on a alorsF(x) =12 x+ax .Fest continue sur ]0;+1[ donc en particulier sur [pa;x k] pour toutk, de plusFest derivable sur ]pa;x k[ pour toutk. Alors, d'apres le theoreme des accroissements nis, il existec2]pa;x k[ tel que :

F(pa)F(xk) =F0(c)paxk

Or,F(pa) =12

pa+apa 12 (pa+pa) =paet par denitionF(xk) =xk+1donc x k+1pa=F0(c)xkpa c2a2c2 xkpa or pour toutk1 on a 00

2x2kxkpa

12xk+pa

2x2k xkpa 12 pa +pa 2a xkpa =1pa xkpa ce qui donne au nal : xk+1pa c2a2c2 xkpa 1pa xkpa xkpa 1pa xkpa

2=Cxkpa

2avecC >0

On a donc montre qu'il existe un reel positifC=1pa tel que8k1 on ajxk+1paj Cjxkpaj2. 3

1.3 Point de vue graphique

D'un point de vue graphique, la suite des iteres (xk) est construite avec la methode suivante : on part dex0et on construitx1comme l'abscisse du point d'intersection entre la tangente afenx0et

l'axe desx. En continuant de la m^eme maniere, on obtient,xk+1l'abscisse du point d'intersection entre

la tangente afenxket l'axe desx. On rappelle que l'equation de la tangente afen un reelaest donnee pary=f0(a)(xa)+f(a) . On denitxk+1comme le reel qui verief0(xk)(xk+1xk)+f(xk) = 0 autrement ditxk+1=xkf(xk)f

0(xk).

On peut voir sur le graphique un exemple avecf(x) =x22, c'est a dire que l'on cherche a approcherp2 en partant dex0= 3.Figure1.1 { Exemple graphique de la methode de Newton pour approcherp2.

Chapitre 2

La decomposition polaire

Introduction

La decomposition polaire generalise celle bien connue dansC. En eet, on peut voir les nombres complexes comme GL

1(C). Ainsi, pour toutz2C, on peut poserZ= (z), alorsZ=OSavec

O=eietS= (r) oureiest la forme polaire du nombre complexez. Cette decomposition peut ^etre etendue a GL n(C), on aurait alorsZ=OSavecOune matrice unitaire etSune matrice hermitienne

denie positive. Pour la suite du chapitre, nous nous interesserons a la decomposition polaire pour des

matrices a coecients reels. On aura alors les matrices unitaires qui seront des matrices orthogonales

et les matrices hermitiennes seront des matrices symetriques. Proposition 2SoitMune matrice inversible reelle, c'est a direM2GLn(R), alors M se decompose de maniere unique comme produit de deux matricesOetSavecOorthogonale, c'est a direO2On(R), etSsymetrique denie positive, c'est a direS2S++n(R). De maniere plus generale, la multiplication matricielle induit l'homeomorphisme

1suivant :

:On(R)S++n(R)!GLn(R);(O;S)7!OS: Demonstration.L'applicationest bien denie et continue. Commencons par montrer sa surjec- tivite. SoitM2GLn(R), montrons qu'il existe un couple (O;S) avecO2On(R) etS2S++n(R) tel queM=OS.

La matrice

tMMest symetrique denie positive. En eet,tMM=tMInMc'est a dire quetMMest congruente

2a la matrice identite. D'apres le theoreme spectral, on peut diagonalisertMMdans une

base orthonormee de vecteurs propres associes aux valeurs propresi,i=f1;;ng. Ainsi : t MM=P0 B B@ 10 0n1 C

CAP1;1. Un homomorphisme est une application bijective continue telle que sa bijection reciproque est continue. Dans ce

paragraphe, nous montrerons seulement la bijectivite desans parler de la continuite de1.

2. On peut rappeler que deux matrices carreesA;Bsont dites congruentes s'il existe une matrice P telle queA=

tPBP. 5 pourP2On(R) convenable, eti>0 pour touti. On pose alors : S=P0 B B@p 10 0p n1 C CAP1: DoncSest symetrique, puisquePest orthogonale, etSest denie positive car ses valeurs propresp i>0, pour touti.

On a alors :

S 2=P0 B B@p 10 0p n1 C

CAP1P0

B B@p 10 0p n1 C CAP1 =P0 B B@p 10 0p n1 C CA0 B B@p 10 0p n1 C CAP1 =P0 B B@ 10 0n1 C

CAP1=tMM

De plus, si on pose :O=MS1, alors :

OO=tMS1MS1=tS1tMMS1=S1S2S1= In:

Ainsi,M=OS, avecO2On(R) etS2S++n(R) doncest surjective. Montrons maintenant queest injective. Supposons que l'on aitM=OS=O0S0avecO02On(R) etS02S++n(R). Alors on a :S2=tMM=t(O0S0)O0S0=tS0tO0O0S0=S0InS0d'ouS2=S02. Il reste a montrer que cela impliqueS=S0. Pour cela, on poseQunpolyn^ome d'interpolation3tel que pour touti,

Q(i) =p

i. Alors : S=P0 B B@p 10 0p n1 C

CAP1=PQ0

B B@0 B B@ 10 0n1 C CA1 C CAP1 =Q0 B B@P0 B B@ 10 0n1 C CAP11 C

CA=Q(S2) =Q(S02)

Or,S0commute avecS02, donc avecQ(S02) =S. DoncS0etSsont deux matrices symetriques denies

positives qui commutent entre elles, alors elles sont simultanement diagonalisables par une matrice3. On peut utiliser un polyn^ome d'interpolation de Lagrange. Pour cela, quitte a renumeroter lesi, on peut supposer

lesi;;rdistincts et lesr+1;;napparaissant parmi ceux-la. On peut donc prendre :

Q(X) =rX

i=1p iY 1jr j6=iXj ij: 6 orthogonale. Il existe une matrice de passageP0qui permet de les diagonaliser simultanement. Ainsi, si l'on note diag(i) =0 B B@ i0 0n1 C CA; on a :S0=P0diag(0i)P10etS=P0diag(i)P10avec0i(respectivementi) pouri=f1;;ngles valeurs propres deS0(respectivementS). Ainsi : S

02=S2)P0diag(0i) =P0diag(i)P10

) 81in;02i=2i ) 81in;0i=i;(S;S02S++n(R) donne0i;i2R+) )S=S0: Il suit immediatementO=O0, ce qui permet de montrer l'injectivite de. 7

Chapitre 3

Methode de Newton pour la

decomposition polaire Proposition 3La suite(Mk)deGLn(R)donnee parM0=MetMk+1=12

Mk(In+ (tMkMk)1)

est bien denie, converge versO, ouM=OSest la decomposition polaire deMdansGLn(R). La suite(tMkM)kconverge alors vers S. Demonstration.Montrons d'abord queMkest bien dans GLn(R) pour toutkce qui permettra aussi d'armer queMnest bien denie pour toutn. Tout d'abord, on a deja vu que pour une matriceA2GLn(R) alorstAAest symtrique denie positive.

Donc, (

tAA)1a toutes ses valeurs propres strictement positives, et comme Incommute avec (tAA)1 alors I n+(tAA)1a toutes ses valeurs propres strictement superieures a 1 donca fortioristrictement positives. C'est a dire, I n+(tMkMk)12GLn(R). Montrons par recurrence queMkest dans GLn(R) pour toutk.

Initialisation.Pourk= 0,Mk=M0=MavecMdans GLn(R).

Heredite.On supposeMk2GLn(R) montrons queMk+12GLn(R).Mk+1=12

Mk(In+(tMkMk)1)

or on a vu que (I n+(tMkMk)1)2GLn(R) et par hypothese de recurrenceMk2GLn(R). DoncMk+1 est le produit de deux matrices dans GL n(R), ce qui montre queMk+1est dans GLn(R). On a donc montre queMkest dans GLn(R) pour tout k. Donc, la decomposition polaire deMkexiste pour tout k, a savoirMk=OkSkavecOkmatricequotesdbs_dbs47.pdfusesText_47

[PDF] Méthode de Newton pour différentes décompositions matricielles et