Chapitre 3:

Résolution d’équations non

linéaires
MR1

1
2
 f(x)=0
• Recherche par dichotomie } n 1

}
• méthode de point fixe Aussi lorsque
• méthode de Newton-Raphson n 2

Principe :
trouver une méthode itérative xk+1 = g(xk) qui converge vers la solution

3
Recherche par dichotomie

4
 algorithme
si f ( a ) f ( b )  0 alors Mé thode de la dichotomie
ab
c
2 f(b)

i1
tant que f (c )  
si f ( a ) f ( c )  0 alors a c=a+b/2 b

a c
sinon

f(x)
b c
finsi
ab
c f(c)

2
i  i 1
fin tant que f(a)

zero  c
nbritera  i
finsi 5
Conditions suffisantes sur g : dérivable et |g'(x)| < 1

ou
6
Méthode du point fixe

7
début algorithme
xa  x0
i1
Tantque erreur  eps
xn  g ( x a )
erreur  abs(xn - x a )
x a  xn
i  i 1
f int antque
zero  xn
nbritera  i
fin 8
 Méthode du point fixe
• Exemple en dimension 1
– résolution de x2 - 2 = 0 sur [1, 2]
– choix de g :
• g1(x) = 2/x g'1(x) = -2/x2 g'1(û) = -1
• g2(x) = 2x - 2/x g'1(x) = 2+2/x2 g'1(û) = 3
• g3(x) = x/2 + 1/x g'1(x) = 1/2-1/x2 g'1(û) = 0
g1 g2 g3
u0 = 1 u0 = 0.999 u0 = 1
u1 = 2 u1 = -0.0402 u1 = 1.5000 |g'(û)| < 1
u2 = 1 u2 = 49.668 u2 = 1.4167 convergence
u3 = 2 u3 = 99.296 u3 = 1.4142 assurée
u4 = 1 u4 = 198.57 u4 = 1.4142
9
 Méthode du point fixe
• Exemple en dimension 1
– résolution de x2 - 2 = 0 sur [1, 2]
– choix de g :
• g1(x) = 2/x g'1(x) = -2/x2 |g'(x)| > 1
• g2(x) = 2x - 2/x g‘2(x) = 2+2/x2 |g'(x)| > 1
• g3(x) = x/2 + 1/x g‘3(x) = 1/2-1/x2 |g'(x)| < 1
g1 g2 g3
x0 = 1 x0 = 0.999 x0 = 1
x1 = 2 x1 = -0.0402 x1 = 1.5000 |g'(x)| < 1
x2 = 1 x2 = 49.668 x2 = 1.4167 convergence
x3 = 2 x3 = 99.296 x3 = 1.4142 assurée
x4 = 1 x4 = 198.57 x4 = 1.4142
10
 Méthode de Newton
• En dimension 1 :
– on considère l'approximation affine :
f xk  h  f xk   f xk h  h  h2 
– on cherche h tel que f(xk+h)=0 soit si on
négligef (les terme en h 2

h 
x )
k f xk 
f '( x ) xk 1  xk  h  xk 
k
f xk 
– et ainsi

11
Méthode de Newton

12
début algorithme
xa  x0
i 1
Tantque erreur  eps
xn  x a  F ( x a ) / F ( x a )
erreur  abs(xn - x a )
x a  xn
i  i 1
F int antque
zero  xn
nbritera  i
fin 13
 Méthode de Newton
• Illustration 2

y=tanh(x)cos(x2)+x-2 1.5

1
y(x)

y'=(1-tanh2(x))cos(x2) 0.5

-2tanh(x)sin(x2)x+1 0

-0.5

-1

-1.5

-2
0 0.5 1 1.5 2 2.5 3
14
 Méthode de Newton
0.5

• Illustration u2= 2.1380

0
y=tanh(x)cos(x )+x-2
2

y'=(1-tanh2(x))cos(x2) u1 = 2.1627
-2tanh(x)sin(x2)x+1 -0.5

u0 = 2
u1 = 2.1627
u2 = 2.1380 -1
1.9 1.95 2 2.05 2.1 2.15 2.2

u3 = 2.1378 u0 = 2
15
u4 = 2.1378
16
 En dimension n :
Méthode de Newton
• En dimension n :
– on considère l'approximation affine : f : R n  R n
f ( xk  h)  f ( xk )  f ( xk )h
– on cherche h tel que f(xk+h)=0
soit f x h  f x  système linéaire !
k k

x0 initialisation
– et ainsi f ( xk )h  f ( xk ) système linéaire
x k 1  x k  h itèration
 f1
 xk  f1 xk   f1 xk 
 x1 x2 xn 
 f 2 
La matrice jacobiennef xk   x1 kx    
 
    
 f n x   
17
fn
x 
 x k
xn
k 
 1 
Exemple
 1
 cos( xy ) 
 2
 x 2  e  y 3
 x0 1

 y0 0

18
 Méthode du point fixe

• Exemple en dimension 3
 1
 3 x  cos( yz )  0
2  f1 ( x, y, z ) 0
 2 2
 x  81( y  0.1)  sin( z )  1.06 0 
 10  3  f 2 ( x, y, z ) 0
 xy  f ( x, y, z ) 0
 e  20 z  0
3  3

 1 1
 x  cos( yz ) 
3 6
 1 2  x  g1 ( y , z )
 y  x  sin( z )  1.06  0.1 
 9  y  g 2 ( x, z )
z 1  xy 10  3  z  g ( x, y )
 e   3
 20 3 19
 Méthode du point fixe
• Exemple en dimension 3
 1
 3 x  cos( yz )  0
2  f1 ( x, y, z ) 0
 2 2
 x  81( y  0.1)  sin( z )  1.06 0 
 10  3  f 2 ( x, y, z ) 0
 xy  f ( x, y, z ) 0
 e  20 z  0
3  3

 1 1
 x  cos( yz ) 
3 6
 1 2  x  g1 ( y , z )
 y  x  sin( z )  1.06  0.1 
 9  y  g 2 ( x, z )
z 1  xy 10  3  z  g ( x, y )
 e   3
 20 3 20
 Méthode du point fixe
• Exemple en dimension 3 (suite)
– valeurs initiales (x0=0.1 ; y0=0.1 ; z0=-0.1)
 1 1
 xk  cos( y k  1 z k  1 ) 
3 6
 1 2
–  yk  xk  1  sin( z k  1 )  1.06  0.1
 9
z 1  xk  1 yk  1 10  3
 e 
 k 20 3

– convergence vers (0.5 ; 0.0 ; -0.5236)

– résultat théorique: (0.5 ; 0.0 ; -/6)
21
 Méthode du point fixe
• Comment essayer d'accélérer la
convergence
– remplacer les valeurs par leurs "dernières"
estimations
• (cf. Gauss-Siedel pour les systèmes linéaires)
 1 1
 xk  cos( y k  1 z k  1 ) 
3 6
– exemple :  1 2
 yk  xk  sin( z k  1 )  1.06  0.1
 9
z 1  xk yk 10  3
 e 
 k 20 3 22
23