[PDF] Méthode de Newton PDF newton.pdf

x+ comme nouvelle approximation, et recommencer Méthode de Newton – p 8/ 41 Page 9 Equation à une inconnue

[PDF] Méthode de Newtonpdf

7 jui 2015 · Méthode de Newton Référence : Rouvière : Petit guide de calcul différentiel, Exercice 49 p 152 Cette méthode permet de trouver des

[PDF] Analyse Numérique

C'est un des inconvénients de la méthode de Newton : une initialisation faite Algorithme 2 8 : Résolution de P (x)=0 par la méthode de Newton à partir d'une

[PDF] Algorithme sur la méthode Newton-Raphson - Lycée dAdultes

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-

[PDF] Devoir de révision : la méthode de Newton

une approximation de x0 avec 10 décimales Exercice 6 Remarques et compléments sur la méthode de Newton Soit f : I → R une fonction de classe C2

[PDF] Méthode de Newton

x+ comme nouvelle approximation, et recommencer Méthode de Newton – p 8/ 41 Page 9 Equation à une inconnue

[PDF] Autour de la méthode de Newton - Annuaire IMJ-PRG

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 solutions

[PDF] 1 Convergence 2 Critère darrêt

Exercice 4 : Faire un dessin illustrant la méthode de Newton pour la fonction la méthode de Newton “perd” la convergence quadratique dans ce cas :

[PDF] Méthodes de résolution déquations

Figure 7 1 – Méthode de Newton appliquée à la fonction f(x) = x + x2 A gauche : fonction et valeurs de la série xn A droite : propriétés de convergence

Méthode de Newton

Michel Bierlaire

michel.bierlaire@epfl.ch

Laboratoire Transport et Mobilit

´e

EPFL - ENAC - TRANSP-OR

´ethode de Newton - p. 1/41

Newton locale

Conditions nécessaires d"optimalité

?f(x) = 0 Il s"agit d"un système d"équations non linéaires. Appliquons la méthode de Newton pour les équations.

Voir Bierlaire (2006), chapitre 7 pour rappel.

´ethode de Newton - p. 2/41

Equation à une inconnue

Résoudre

F(x) = 0

avec

F(x) =x2-2,?x= 2

Théorème de Taylor

F(?x+d) =F(?x) +dF?(?x) +o(|d|)

=?x2-2 + 2?xd+o(|d|) = 2 + 4d+o(|d|).

M´ethode de Newton - p. 3/41

Equation à une inconnue

Ignorons le terme d"erreur pour obtenir un

modèle m(?x+d) = 2 + 4d.

En posantx=?x+d, nous obtenons

m(x) = 2 + 4(x-2) = 4x-6. M

´ethode de Newton - p. 4/41

Equation à une inconnue-10-5051015

0 0.5 1 1.5 2 2.5 3 3.5 4

x f(x) m(x) M

´ethode de Newton - p. 5/41

Equation à une inconnue

1.51.61.71.81.922.12.22.32.42.5

1.9 1.95 2 2.05 2.1

x f(x) m(x) M

´ethode de Newton - p. 6/41

Equation à une inconnueModèle linéaire d"une fonction à une variable

SoitF:R→Rune fonction différentiable.

Lemodèle linéairedeFen?xest une fonctionm?x:R→Rdéfinie par m ?x(x) =F(?x) + (x-?x)F?(?x).

M´ethode de Newton - p. 7/41

Equation à une inconnue

Algorithme :1. Calculer le modèle linéaire en?x:

F(?x) + (x-?x)F?(?x) = 0,

2. Calculer sa racinex+

x +=?x-F(?x)

F?(?x),

3. Six+n"est pas une racine du problème de départ, considérer

x +comme nouvelle approximation, et recommencer. M

´ethode de Newton - p. 8/41

Equation à une inconnue

Critère d"arrêt :

En théorieF(x+) = 0.

En pratique, arithmétique finie.

On définit une précisionε, et la condition est M

´ethode de Newton - p. 9/41

Rappel

: Méthode de Newton - une variable

Objectif

Trouver une approximation de la solution de l"équation

F(x) = 0.

Input

La fonctionF:R→R;

La dérivée de la fonctionF?:R→R;

Une première approximation de la solutionx0?R;

La précision demandéeε?R,ε >0.

´ethode de Newton - p. 10/41

Rappel

: Méthode de Newton - une variable

Output

Une approximation de la solutionx??R

Initialisation

k= 0 It

´erations

1.xk+1=xk-F(xk)/F?(xk),

2.k=k+ 1.

Crit `ere d"arrˆet M

´ethode de Newton - p. 11/41

Rappel

: Méthode de Newton - nvariables

Objectif

Trouver une approximation de la solution du système d"équations

F(x) = 0.

Input

La fonctionF:Rn→Rn;

La matrice jacobienne de la fonctionJ:Rn→Rn×n; Une première approximation de la solutionx0?Rn;

La précision demandéeε?R,ε >0.

Output

Une approximation de la solutionx??Rn

´ethode de Newton - p. 12/41

Rappel

: Méthode de Newton - nvariables

Initialisation

k= 0 It

´erations

1. Calculerdk+1solution deJ(xk)dk+1=-F(xk).

2.xk+1=xk+dk+1.

3.k=k+ 1.

Crit `ere d"arrˆet M

´ethode de Newton - p. 13/41

Rappel: Méthode de Newton - nvariablesConvergence de la méthode de Newton nvariables

Soit un

ensemble convexe ouvertX?Rn, et une fonctionF:X→Rn. Supposons qu"il existex??X, une bouleB(x?,r)centrée enx?de rayonr, et une constanteρ >0tels queF(x?) = 0,B(x?,r)?X,J(x?)est inversible, etJest continue au sens de Lipschitz surB(x?,r), la constante de Lipschitz

étantM.

(suite...) M

´ethode de Newton - p. 14/41

Rappel: Méthode de Newton - nvariablesConvergence de la méthode de Newton nvariables (suite)Alors, il existeη >0tel que si

0?B(x?,η),

alors la suite(xk)kdéfinie par x k+1=xk-J(xk)-1F(xk)k= 0,1,... est bien définie et converge versx?. De plus,

ρ?xk-x??2.

(p. 204) M

´ethode de Newton - p. 15/41

Rappel: 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 defà la solution n"est pas trop proche de 0;

Six0n"est pas trop éloigné de la racine;

Alors la méthode de Newton converge très vite vers la solution. M

´ethode de Newton - p. 16/41

Algorithme

: Newton locale

Objectif

Trouver une approximation de la solution du système ?f(x) = 0. Input

Le gradient de la fonction?f:Rn→Rn;

Le hessien de la fonction?2f:Rn→Rn×n;

Une première approximation de la solutionx0?Rn;

La précision demandéeε?R,ε >0.

´ethode de Newton - p. 17/41

Algorithme

: Newton locale

Output

Une approximation de la solutionx??Rn

Initialisation

k= 0 M

´ethode de Newton - p. 18/41

Algorithme

: Newton locale It

´erations

1. Calculerdk+1solution de?2f(xk)dk+1=-?f(xk),

2.xk+1=xk+dk+1,

3.k=k+ 1.

Crit `ere d"arrˆet M

´ethode de Newton - p. 19/41

Newton locale

Mêmes propriétés que pour les équations1. convergenceq-quadratique dans les conditions favorables

2. divergence possible si le point de départ est trop éloignéde la

solution,

3. méthode non définie si?2f(xk)n"est pas inversible.

Inconvénient supplémentaire :

incapacité à distinguer minimum, maximum et point de selle

M´ethode de Newton - p. 20/41

Newton locale

minf(x1,x2) =1

2x21+x1cosx2,

x1x 2 M

´ethode de Newton - p. 21/41

Newton locale

minf(x1,x2) =1

2x21+x1cosx2,

x?-2x -1x 0x 1x 2 ¯x

0¯x

1 ¯x -1 ¯x -2

Point de départx0= (1 1)T. Convergence rapide.

´ethode de Newton - p. 22/41

Newton locale

Solution:

x 0 2? ?f(x?) =? 0 0?

2f(x?) =?

1-1 -1 0? -2 -1.5 -1 -0.5 0 0.5 1 1.5 2-6-4-20246 x 0x x1x 2 M

´ethode de Newton - p. 23/41

Newton locale

Solution:

x 0 2? ?f(x?) =? 0 0?

2f(x?) =?

1-1 -1 0? -0.4 -0.2 0 0.2 0.4 0.6 0.8 111.21.41.61.82 x 0x? x1x 2 M

´ethode de Newton - p. 24/41

Newton locale

Méthode rapide mais peu fiable

Interprétation géométrique

Equations : modèle linéaire à chaque itération

Optimisation : modèle quadratique

´ethode de Newton - p. 25/41

Newton localeModèle quadratique d"une fonction

Soitf:Rn→Rune fonction deux fois différentiable. Lemodèle quadratiquedefen?xest une fonctionm?x:Rn→Rdéfinie par m ?x(x) =f(?x) + (x-?x)T?f(?x) +1

2(x-?x)T?2f(?x)(x-?x),

où?f(?x)est le gradient defen?xet?2f(?x)est la matrice hessienne de fen?x. En posantd=x-?x, on obtient la formulation équivalente: m ?x(?x+d) =f(?x) +dT?f(?x) +1

2dT?2f(?x)d.

M´ethode de Newton - p. 26/41

Newton locale

min xm?x(x) =f(?x) + (x-?x)T?f(?x) +1

2(x-?x)T?2f(?x)(x-?x)

Condition suffisante d"optimalité (premier ordre) ?m?x(?x+d) =?f(?x) +?2f(?x)d= 0 c"est-à-dire d=-?2f(?x)-1?f(?x), ou encore x=?x- ?2f(?x)-1?f(?x),

M´ethode de Newton - p. 27/41

Newton locale

Condition suffisante d"optimalité (second ordre) ?2f(?x)définie positive Lorsque la matrice hessienne de la fonction est définie positive enxk, une itération de la méthode de Newton locale revient à minimiser le modèle quadratique de la fonction enxk, et ainsi définir x k+1= argminx?Rnmxk(x).

M´ethode de Newton - p. 28/41

Algorithme

: Modèle quadratique

Objectif

Trouver une approximation de la solution du système ?f(x) = 0.(1) Input

Le gradient de la fonction?f:Rn→Rn;

Le hessien de la fonction?2f:Rn→Rn×n;

Une première approximation de la solutionx0?Rn;

La précision demandéeε?R,ε >0.

´ethode de Newton - p. 29/41

Algorithme

: Modèle quadratique

Output

Une approximation de la solutionx??Rn

Initialisation

k= 0 M

´ethode de Newton - p. 30/41

Algorithme

: Modèle quadratique It

´erations

1. Construire le modèle quadratique

m ?x(?x+d) =f(?x) +dT?f(?x) +1

2dT?2f(?x)d,

2. Calculer

d k+1= argmindm?x(?x+d)

3.xk+1=xk+dk+1,

4.k=k+ 1.

Crit `ere d"arrˆet M

´ethode de Newton - p. 31/41

Algorithme

: Modèle quadratique Attention : si?2f(xk)n"est pas définie positive,... -4-20246x1-4 -20246x 2-20 02040
f(x1,x2) M

´ethode de Newton - p. 32/41

Algorithme

: Modèle quadratique Attention : si?2f(xk)n"est pas définie positive, le modèle n"est pas borné inférieurement -4-20246x1-4 -20246x 2-20 02040
m x0(x1,x2) Dans ce cas, l"algorithme ne peut être appliqué. M

´ethode de Newton - p. 33/41

Modèle quadratique

f(x) =-x4+ 12x3-47x2+ 60x. x k= 3 m

3(x) = 7x2-48x+ 81-15-10-50510152025

1 1.5 2 2.5 3 3.5 4 4.5 5 5.5

f(xk)f(xk+1)

f(x) m 3(x) M

´ethode de Newton - p. 34/41

Modèle quadratique

f(x) =-x4+ 12x3-47x2+ 60x. x k= 3 m

3(x) = 7x2-48x+ 81-2-1012345

2.6 2.8 3 3.2 3.4 3.6 3.8 4

f(xk)

f(xk+1) f(x) m 3(x) M

´ethode de Newton - p. 35/41

Modèle quadratique

f(x) =-x4+ 12x3-47x2+ 60x. x k= 4 m

4(x) =x2-4x-15-10-50510152025

1 1.5 2 2.5 3 3.5 4 4.5 5 5.5

x f(xk)f(xk+1) f(x) m 4(x) M

´ethode de Newton - p. 36/41

Modèle quadratique

f(x) =-x4+ 12x3-47x2+ 60x. x k= 4 m

4(x) =x2-4x

-4-202468101214

2 2.5 3 3.5 4 4.5

x f(xk)f(xk+1) f(x) m 4(x) M

´ethode de Newton - p. 37/41

Modèle quadratique

f(x) =-x4+ 12x3-47x2+ 60x. x k= 5 m

5(x) =-17x2+ 160x-375.-15-10-50510152025

1 1.5 2 2.5 3 3.5 4 4.5 5 5.5

x f(xk)f(xk+1) f(x) m 5(x) M

´ethode de Newton - p. 38/41

Modèle quadratique

f(x) =-x4+ 12x3-47x2+ 60x. x k= 5 m

5(x) =-17x2+ 160x-375.-12-10-8-6-4-202

4 4.2 4.4 4.6 4.8 5 5.2 5.4

f(xk)f(xk+1)

f(x) m 5(x) M

´ethode de Newton - p. 39/41

Modèle quadratiquePoint de Newton

Soitf:Rn→Rune fonction deux fois différentiable, et soitxk?Rn.

Lepoint de Newtondefenxkest le point

N=xk+dN

oùdNest solution du système d"équationsquotesdbs_dbs47.pdfusesText_47

[PDF] [PDF] Méthode de Newton

Méthode de Newton

Michel Bierlaire

Laboratoire Transport et Mobilit

EPFL - ENAC - TRANSP-OR

´ethode de Newton - p. 1/41

Newton locale

Conditions nécessaires d"optimalité

Voir Bierlaire (2006), chapitre 7 pour rappel.

´ethode de Newton - p. 2/41

Equation à une inconnue

Résoudre

F(x) = 0

F(x) =x2-2,?x= 2

Théorème de Taylor

F(?x+d) =F(?x) +dF?(?x) +o(|d|)

M´ethode de Newton - p. 3/41

Equation à une inconnue

Ignorons le terme d"erreur pour obtenir un

En posantx=?x+d, nous obtenons

´ethode de Newton - p. 4/41

Equation à une inconnue-10-5051015

0 0.5 1 1.5 2 2.5 3 3.5 4

´ethode de Newton - p. 5/41

Equation à une inconnue

1.51.61.71.81.922.12.22.32.42.5

1.9 1.95 2 2.05 2.1

´ethode de Newton - p. 6/41

SoitF:R→Rune fonction différentiable.

M´ethode de Newton - p. 7/41

Equation à une inconnue

F(?x) + (x-?x)F?(?x) = 0,

2. Calculer sa racinex+

F?(?x),

3. Six+n"est pas une racine du problème de départ, considérer

´ethode de Newton - p. 8/41

Equation à une inconnue

Critère d"arrêt :

En théorieF(x+) = 0.

En pratique, arithmétique finie.

´ethode de Newton - p. 9/41

Rappel

Objectif

F(x) = 0.

La fonctionF:R→R;

La dérivée de la fonctionF?:R→R;

Une première approximation de la solutionx0?R;

La précision demandéeε?R,ε >0.

´ethode de Newton - p. 10/41

Rappel

Output

Une approximation de la solutionx??R

Initialisation

´erations

1.xk+1=xk-F(xk)/F?(xk),

2.k=k+ 1.

´ethode de Newton - p. 11/41

Rappel

Objectif

F(x) = 0.

La fonctionF:Rn→Rn;

La précision demandéeε?R,ε >0.

Output

Une approximation de la solutionx??Rn

´ethode de Newton - p. 12/41

Rappel

Initialisation

´erations

1. Calculerdk+1solution deJ(xk)dk+1=-F(xk).

2.xk+1=xk+dk+1.

3.k=k+ 1.

´ethode de Newton - p. 13/41

Soit un

étantM.

´ethode de Newton - p. 14/41

0?B(x?,η),

ρ?xk-x??2.

´ethode de Newton - p. 15/41

Rappel: Méthode de Newton

Performance de la méthode de Newton

Interprétation géométrique