Méthodes numériques Cours 2eme année licence

Chapitre 3
Interpolation Polynomiale
1. Introduction
A partir d’une fonction f ( x) connue seulement en (n  1) point de la forme
 xi , f ( xi )  , i  0,...., n , peut on construire une approximation de f ( x) pour tout x ?

Les point  xi , f ( xi )  sont appelés points d’interpolation et peuvent provenir des

données expérimentales ou d’une table.

 Définition :

Soit f une fonction réelle définie sur un intervalle  a, b contenant (n  1) points

distincts x0 , x1 ,..., xn .

Soit Pn un polynôme de degré inferieur ou égale n .on dis que Pn est interpolant de f
ou interpole f on x0 , x1 ,..., xn

Pn ( x)  f ( xi ) i  0,..., n

2. Les méthodes utilisées :

2.1. Polynôme de Lagrange
Soit à calculer f ( x) pour x  2 , connaissant f (1)  3,716 et f (3)  1,623 (figure 1)

y0

y1

x0=1 x=2 x1=3 x

12
Méthodes numériques Cours 2eme année licence

Les propriétés de la droite dans l’intervalle  x0 , x1  nous permettent d’écrire :

y0  y y0  y1

x0  x x0  x1

y étant la valeur approchée de f (2)

x  x1 x  x0
y y0  y1
x0  x1 x1  x0

On peut alors calculer la valeur approchée de f (2)

Cette formule est appelée polynôme de Lagrange

 Formule générale

On appelle interpolant de Lagrange les polynômes Li définis pour i  0,..., n par

n x  xj
Li ( x)  
j i xi  x j

n
si on prend Pn ( x)   Li ( x). f ( xi ) alors Pn ( x)  f ( xi ) i  0,.., n
i 0

Exemple :

x0  0 ; x1  1 ; x2  2

f ( x0 )  4 ; f ( x1 )  2 ; f ( x2 )  2

Calculer le polynôme de Lagrange

Solution :

On a 3 points donc le degré de polynôme est  2

2
P2 ( x)   Li ( x) f ( xi ) L0 ( x) f ( x0 )  L1 ( x) f ( x1 )  L2 ( x) f ( x2 )
i 0

( x  x1 )( x  x2 ) ( x  1)( x  2) 1 2
L0 ( x)    ( x  3x  2)
( x0  x1 )( x0  x2 ) (0  1)(0  2) 2

( x  x0 )( x  x2 ) ( x  0)( x  2)
L1 ( x)    ( x 2  2 x)
( x1  x0 )( x1  x2 ) (1  0)(1  2)

13
Méthodes numériques Cours 2eme année licence

( x  x0 )( x  x1 ) ( x  0)( x  1) 1 2
L2 ( x)    ( x  x)
( x2  x0 )( x2  x1 ) (2  0)(2  1) 2

Donc

1 1
P2 ( x)  ( x 2  3x  2).(4)  ( x 2  2 x).(2)  ( x 2  x).(2)
2 2

P2 ( x)  2 x2  6 x  4  2 x2  4 x  x2  x

P2 ( x)  3x 2  9 x  4

 Estimation de l’erreur :

On démontre que l’erreur commise en interpolant f ( x) par le polynôme de Lagrange

Pn ( x) en (n  1) points vérifie :

n
M
f ( x)  Pn ( x)  
(n  1)! i 0
x  xi

Avec M  max f ( n1)      x0 , xn 

2.2. Polynôme de Newton

On appelle interpolant de Newton le polynôme Pn ( x) donnée par

Pn ( x)  C0  C1 ( x  x0 )  C2 ( x  x0 )( x  x1 )  .........  Cn ( x  x0 )( x  x1 )......( x  xn1 )

L’aspect intéressant de cette formule apparait lorsqu’on essaie de déterminer les

(n  1) coefficients Ci , de telle sorte que Pn ( x) passe par les (n  1) points
d’interpolation ( xi , f ( xi )).

 Calcul des coefficients Ci :

Pour calculer les coefficients, on utilise les différences divisées. on définit les
différences divisées d’ordre i de f au point xi comme suit :

C0    f ( x0 )  f ( x0 )

f ( x1 )  f ( x0 )
C1    f ( x0 ), f ( x1 ) 
x1  x0

14
 Méthodes numériques Cours 2eme année licence

  f ( x1 ),......, f ( xi )    f ( x0 ),........, f ( xn1 ) 

Ci    f ( x0 ), f ( x1 ),..........., f ( xi )   Pour i  2
xi  x0

Pour calculer les différences divisées on peut construire le tableau suivant :

i xi f ( xi ) Ordre 1 Ordre 2 Ordre 3

0 x0 f ( x0 ) C0 C1
  f ( x0 ), f ( x1 ) C2
1 x1 f ( x1 )   f ( x0 ), f ( x1 ), f ( x2 ) C3
  f ( x1 ), f ( x2 )   f ( x0 ), f ( x1 ), f ( x2 ), f ( x3 )
2 x2 f ( x2 )   f ( x1 ), f ( x2 ), f ( x3 )
  f ( x2 ), f ( x3 )
3 x3 f ( x3 )

n-2 xn 2 f ( xn2 )
  f ( xn2 ), f ( xn1 )   f ( xn3 ), f ( xn2 ), f ( xn1 ), f ( xn )
n-1
xn 1 f ( xn1 )   f ( xn2 ), f ( xn1 ), f ( xn )
n   f ( xn1 ), f ( xn )
xn f ( xn )

Exemple :

Trouver le polynôme de Newton qui passe par les points suivants :

x0  0 ; x1  1 ; x2  2 ; x3  0

f ( x0 )  1 ; f ( x1 )  4 ; f ( x2 )  8 ; f ( x3 )  14

Solution

On a 4 points donc le degré de polynôme est 3

P3 ( x)  C0  C1 ( x  x0 )  C2 ( x  x0 )( x  x1 )  C3 ( x  x0 )( x  x1 )( x  x2 )

On construire le tableau pour calcule les coefficients

15
 Méthodes numériques Cours 2eme année licence

i xi f ( xi ) Ordre 1 Ordre 2 Ordre 3

C0
0 x0  0 f ( x0 )  1 C1
  f ( x0 ), f ( x1 )  C2
3   f ( x0 ), f ( x1 ), f ( x2 )   C3
1 x1  1 f ( x1 )  4 1   f ( x0 ), f ( x1 ), f ( x2 ), f ( x3 )  
  f ( x1 ), f ( x2 )  2 1
4 6
2 x2  2 f ( x2 )  8   f ( x1 ), f ( x2 ), f ( x3 ) 
  f ( x2 ), f ( x3 )  1
3 x3  3 f ( x3 )  14 6

Donc

1 1
P3 ( x)  1  3( x  0)  ( x  0)( x  1)  ( x  0)( x  1)( x  2)
2 6

1 2 1 1 1 1
P3 ( x)  1  3x  x  x  x3  x 2  x
2 2 6 2 3

1 3 17
P3 ( x)  x  x 1
6 6

 Estimation de l’erreur :

On démontre que l’erreur commise en interpolant f ( x) par le polynôme de Newton

Pn ( x) en (n  1) points vérifie :

n
f ( x)  Pn ( x)  Cn . x  xi
i 0

16
Méthodes numériques Cours 2eme année licence

Chapitre 4
Résolution des systèmes d’équations linéaires
1. Introduction
Dans ce chapitre, nous allons aborder deux principales méthodes de résolution des
systèmes linéaire à savoir (méthodes directes, méthodes itératives) pour une matrice
carrée. De façon générale, un système d’équations linéaires est un ensemble
d’équations portant sur les mêmes inconnues.

En général, un système de n équation linéaires à n inconnues peut être écrit sous la

forme suivante :

a11 x1  a12 x 2  ............  a1n x n  b1



a 21 x1  a 22 x 2  ............  a 2 n x n  b2





a n1 x1  a n 2 x 2  ............  a nn x n  bn




Ou x1 , x2 ,............, xn sont les inconnues

Un système d’équations linéaires peut aussi s’écrire sous la forme matricielle

Ax  b

Ou A est une matrice de taille n  n , x est un vecteur de taille n et b est un vecteur de

taille n

 a11 a12 .......... a1n   x1   b1 

     
 a 21 a 22 ........... a 2 n   x2   b2 
     
A  ; x  ; b 
 ............     
     
a    b 
 n1 a n 2 ............ a nn   xn   n

17
Méthodes numériques Cours 2eme année licence

La résolution du système précédent ( Ax  b ) peut s’effectuer par plusieurs méthodes :

 Une méthode classique (Cramer).

 Les méthodes directes.
 Les méthodes itératives.

2. Méthode de Cramer
C’est certainement la méthode la plus connue de résolution des systèmes linéaires.
Cette méthode repose sur les déterminants

det Ai
Si det A  A  0  le système admet une solution unique x donnée par xi 
det A

Ou Ai est la matrice obtenue en remplaçant dans A la ieme colonne par b

Remarque : Cette méthode exige un grand nombre d’opérations de calcul. Par

exemple pour n  10 , cramer nécessite 3.108 opérations.

Donc notre objectif, on va aborder d’autres méthodes qui nécessitent un nombre limité
d’opérations de calcul.

3. Les Méthodes directes

Une méthode est dite directe, si elle donne au bout d’un nombre fini d’opérations une solution
exacte du problème. Cette méthode est utilisée généralement lorsque n  100

3.1. Méthode de Gauss ordinaire :

Cette méthode est basée sur la transformation du système linéaire Ax  b en un

système équivalent A' x  b' , A' est une matrice triangulaire supérieure.

Principe :

  A( n ) ; b ( n ) 
A, b transforma
tion
A(n ) Matrice triangulaire supérieure

a11(1) (1)
a12 .......a1(1n) b1(1)  a11
(n) (n)
a12 .......a1(nn ) b1( n ) 
 (1) (1)   
a 21 a 22 .......a 2(1n) b2(1)   0
(n)
a 22 .......a 2( nn) b2( n ) 
 .........   ......... 
 (1)   
a n1 bn(1)   0 bn( n ) 
(1) (1) (n)
a n1 ......a nn 0 ......a nn

Puis on résoudre le système A( n) x  b ( n)

Dont x la solution exacte du système Ax  b

18
Méthodes numériques Cours 2eme année licence

Les étapes :

On pose A  A(1) ; b  b (1)

Si a11(1)  0 on fait l’opération suivante

 L1(2)  L1(1)

 (2) ai(1)
 Li  Li  a (1) L1
(1) 1 (1)

 11

On obtient alors :

a11
( 2) ( 2)
a12 .......a1(n2) b1( 2) 
 
A 
( 2)
0 a 22 .......a 2( 2n) b2( 2) 
( 2)
;b ( 2)

 0 ......... 
 ( 2) 
 0 a n( 12) bn 
( 2)
......a nn

Et ainsi de suite :

 L(kk 1)  L(kk )


A la kème étapes ai(1k ) ( k ) ; akk  0
(k )
 ( k 1)
 Li  Li  a ( k ) Lk
(k )

 kk

a11
(n)
.x1  a12
(n)
.x 2  .........  a1(nn ) .x n  b1( n )

0  a 22 .x n  .........  a 2 n .x n  b2
(n) (n) (n)

Résolution de A( n) x  b ( n) 

0  0  ..................  a ( n ) .x  b ( n )
 nn n n

Exemple 1:

Soit le système linéaire suivant

 x1  3.x 2  3x3  0

2 x1  3x 2  0
3x  2 x  6 x  11
 1 2 3

Résoudre le système par la méthode de Cramer et Gauss

Solution :

19
Méthodes numériques Cours 2eme année licence

La solution par la méthode de Cramer et x1  3 ; x2  2 ; x3  1

La méthode de Gauss :

Les étapes :

 1 3 3 0
   
 1ère étape On pose A  A   2 3 0;b  b   0 
(1) (1)

 3 2 6 11
   

a11(1)  0 On fait l’opération suivante


 (2)
 L1  L1
(1)

 (2) (1)
a21
 2L  L(1)
2  L(1)  L(1)
(1) 1 2  2 L1
(1)

 a11
 (1)
a31
 L3  L3  (1) L1(1)  L(1)
(2) (1)
3  3L1
(1)

 a11

1 3 3 ; 0 
 A ; b   0 3 6 ; 0 
(2) (2)
On obtient alors :  
0 7 3 ;11

 2ème étape :
(2)
a22  0 On fait l’opération suivante


 L(3)  L(2)
 1 1

 L2  L2
(3) (2)

 (2)
 L(3) a32 7 (1)
 L(2)
 L(2)  L(2)
3  L1

3 3 (2) 2
a22 3

1 3 3 ; 0 
 A ; b   0 3 6 ; 0 
(3) (3)
On obtient alors :  
0 0 11 ;11

20
Méthodes numériques Cours 2eme année licence

 x1  3x2  3x3  0  x1  3x2  3x3  x1  3

  
Résolution de A x  b (3) (3)
 0  3x2  6 x3  0   x2  2 x3   x2  2
0  0  11x  11 x  1 x  1
 3  3  3

3
 
Donc, la solution est X   2 
1
 

3.2. Méthode de Gauss - Jordan :

Cette méthode est basée sur la transformation de la matrice A en une matrice identité

 I ; b ' 

A, b transforma
tion

D’ou A.x  b I .x  b' x  b'

Les étapes

1ère étape

On pose A  A(1) ; b  b (1)

a11(1) (1)
a12 .......a1(1n) b1(1)  L1(1)
 (1) 
A; b  A(1) ; b (1) 
(1)
a a 22 .......a 2(1n) b2(1)  L(21)
  21
 ......... 
 (1) 
a n1 a n(11) bn(1)  L(n1)
(1)
......a nn

Si a11(1)  0 on fait l’opération suivante

 ( 2) 1 (1) 1 a12( 2)
.......a1(n2) b1( 2)  L1( 2)
L1  a (1) L1  
A 
( 2)
0 a 22 .......a 2( 2n) b2( 2)  L(22)
 11 ( 2)
; b ( 2) 
L( 2)  L(1)  a (1) L( 2)  ......... 
; i  2, n  
 i i i1 1
0 a n1
( 2) ( 2)
......a nn bn( 2)  L(n2)

Kème étape : akk  0

(k )

 ( k 1) 1 (k )
 Lk  a ( k ) Lk
 kk

 Li  Li  aik( k ) L(kk 1) i  k

( k 1) (k )



A la dernière étape on obtient

21
Méthodes numériques Cours 2eme année licence

A.x  b  I .x  b( n1) ; b( n1)  bi( n1) 1  i  n

Remarque :

Cette méthode est aussi conseillée pour inverser une matrice, il suffit d’effectuer les
opérations précédentes sur le système  A; I     I ; A1 
transformation
 

Exemple 2:

Trouver la solution de système par la méthode de gauss-Jordan

1 3 4 0
   
A  2 2 0 b 4 
3 3 6 12 
   

Solution :

Les étapes

 1ère étape

1 3 4; 0  L1
(1)

On pose A  A(1) ; b  b (1)  A; b   A(1) ; b(1)   2 2 0; 4  L(2)

2

 3 3 6;12  L3
(3)

 (2) 1 (1)
 L1  a (1) L1  L1
(1)

 11

a11  0 On fait l’opération suivante  L2  L2  a21 L1  L2  2 L1

(1) (2) (1) (1) (2) (1) (2)

 (2)
 L3  L3  a31 L1  L3  3L1
(1) (1) (2) (1) (2)



1 3 4 ;0 
 
On obtient alors :  A ; b   0 4 8 ; 4 
(2) (2)

0 6 6 ;12 

 2ème étape
(2)
a22  0 On fait l’opération suivante

22
Méthodes numériques Cours 2eme année licence

 L1(3)  L1(2)  a12(2) L(3)

2  L1  3L2
(2) (3)


 (3) 1 (2) 1 (2)
 L2  (2) L2  L2
 a 22  4
 L(3)  L(2)  a (2) L(3)  L(2)  6 L(3)
 3 3 32 2 3 2

1 0 2 ;3 
 
On obtient alors :  A ; b   0 1 2 ; 1
(3) (3)

0 0 6 ;6 

 3ème étape
(3)
a33  0 On fait l’opération suivante


 L(4)  L(3)  a (3) L(3)  L(3)  2 L(4)
 1 1 13 2 1 3

 L2  L2  a23 L2  L2  2 L3
(4) (3) (3) (3) (3) (4)
On obtient alors :
 1 (3) 1 (3)
 L(4)
3  (3) L3  L3
 a33 6
1 0 2 ;5 
 A ; b   0 1 0 ; 3
(4) (4)
 
0 0 1 ;1 

5
 
Donc : I .x  b (4)
 x   3 
1
 

3.3. Décomposition LU :

On suppose que le système Ax  b admet une solution unique et que A soit une
matrice carrée. L’idée de la décomposition L U et de décomposer A  L.U avec

L matrice triangulaire inferieure

U matrice triangulaire supérieure

Pour pouvoir faciliter la résolution de Ax  b en deux étapes simple

Ly  b (1)

Ux  y (2)

23
Méthodes numériques Cours 2eme année licence

La matrice U est obtenue par la méthode Gauss ( A( n) x  b ( n) ) telle que on pose

U  A(n)

 1 0 0
 
  21 1 0 0 aik( k )
La matrice L    ; telle que  ik 
1 a kk( k )
 
  
 n1 nn1 1 

Remarque : la décomposition LU n’existe pas toujours sur A même si elle est

inversible.

Si  kk( k )  0 la méthode de Gauss est applicable et donc A se factorise sous forme LU

Exemple 3 :

Résoudre le système par la décomposition LU

 1 3 3 0
   
A   2 3 0 b 0 
 3 2 6 11
   

Solution
Déterminer la matrice U  A(n) par la méthode de Gauss d’après exemple 1 on obtient :
1 3 3 
 
U  A   0 3 6 
(3)

 0 0 11 
 
 
 1 0 0 1 0 0
  a(k )  
La matrice L    21 1 0   ik  ik( k ) donc L  2 1 0
 akk
 31  32 1   7 
3 1
 3 

la résolution de Ax  b en deux étapes simple

  
 1 0 0   y1   0   y1  0  y1  0
      
Ly  b   2 1 0   y2    0   2 y1  y2  0   y2  0
   y  11   y  11
1 3    3 y1  y2  y3  11  3
7 7
3
 3   3

24
Méthodes numériques Cours 2eme année licence

 1 3 3  x1   y1   x1  3x2  3x3  0  x1  3
      
U .x  y   0 3 6  x2    y2   3x2  6 x3  0   x2  2
 0 0 11  x   y  11x  11 
  3   3   3  x3  1

4. Les Méthodes itératives :

Lorsque n est très grand (n≥100) la résolution des systèmes Ax  b pour les méthodes
directes deviennent toujours compliqués, on fait appel donc à des méthodes dites
itératives.

D’une manière générale : on décompose A sous la forme.

A  L A  U A  DA

D A La matrice diagonale avec DA ii  aii

L A La matrice triangulaire inferieure avec LA ij  aij ;i  j

U A La matrice triangulaire supérieure avec U A ij  aij ;i  j

La différence entre la solution exacte et la solution approchée notée

e  x  x k ..............(1)

On multiplie l'équation (1) par A on obtient

A.e  A.x  A.x k ..............(2)

r ( k )  A.x k .

Le nombre r ( k ) est appelé résidu

Plusieurs méthodes itératives utilisant une approximation B  A et résolvent

B.e  b  A.x k ..............(3)

Au lieu (A) la correction e( k ) obtenue n’étant en général pas exacte, elle définit une
nouvelle approximation

x k 1  x k  e k ..............(4)

La résolution du système peut s’effectuer par plusieurs méthodes

25
Méthodes numériques Cours 2eme année licence

4.1 Méthode de Jacobi :

On suppose que aii  0 en utilisant B j  DA ce qui mène à la suite des solutions

approchées

x k 1  x k  DA1 .(b  A.x k )

Ou encore (comme les éléments diagonaux de DA1. A valent 1)

 
1  n
k 
 bi   aij .x j 
k 1
x i  ; i  1,.., n
aii  j 1 
 i j 

4.2. Méthode de Gauss Seidel :

On suppose que aii  0 en utilisant B j  LA ce qui mène à la suite des solutions

approchées

x k 1  x k  LA1 .(b  A.x k )

Ou encore

1  n n 
xik 1   bi   aij .x kj 1   aij .x kj  ; i  1,.., n
 
aii  j i j i 

Exemple 4:

Calculer les 4 premières itérations par les deux méthodes

 2 1 0  1 0
     
A   1 4 1 b  1 avec x   0 
0

 0 1 2   1 0
     

Solution :

 On utilise la méthode de Jacobi

 
1  n
k 
 bi   aij .x j 
k 1
x i  ; i  1,.., n
aii  j 1 
 i j 

26
Méthodes numériques Cours 2eme année licence

Le système s’écrite

 k 1 1
 x1 
a11

b1   a12 x2k  a13 x3k 
 
 k 1 1
x1  1  x2k 
 
2
 k 1 1
 x2 
a22
 

b2   a21 x1k  a23 x3k    x2k 1  1  x1k  x3k 
1
4
 
 k 1 1  k 1
  x3  2 1  x2 

1
b3   a31 x1k  a32 x2k 
k
 x3 
 a33 

0
A partir de x   0  on trouve :
0

0
 

k 0 1 2 3 4
x1 0 0,5 0 ,625 0 ,75 0 ,78125
x2 0 0,25 0, 5 0 ,5625 0,625
x3 0 0,5 0,625 0 ,75 0,78125

 On utilise la méthode de Gauss Seidel

1  n n 
xik 1   bi   aij .x kj 1   aij .x kj  ; i  1,.., n
 
aii  j i j i 

Le système s’écrit

 k 1 1
 x1 
a

b1   a12 x2k  a13 x3k  
 k 1 1
 x1  1  x2k 
 11

2
 k 1 1
 x2 
a22
 

b2   a21 x1k 1  a23 x3k    x2k 1  1  x1k 1  x3k 
1
4
 
 k 1 1  k 1 1

b3   a31 x1k 1  a32 x2k 1   x3  2 1  x2 

k 1
 x3 
 a33 

0
A partir de x   0  on trouve :
0

0
 

k 0 1 2 3 4
x1 0 0,5 0 ,6875 0,796875 0,82421875
x2 0 0,375 0, 59375 0,6484375 0,66210938
x3 0 0,6875 0,796875 0,82421875 0,83105469

27
Méthodes numériques Cours 2eme année licence

 Critère d’arrêt :

Les critères largement utilisés pour les méthodes itératives sont données par les
formules suivantes:

xin  xin1   ; i  1,...., n

x( n )  x( n1)   Erreur absolue

x ( n )  x ( n 1)
 Erreur relative
x( n)

 Condition de Convergence

D’après ce qui précède des conditions nécessaire et suffisante (CNS) sur LA et DA

pour qu'elles soient inversibles.

Il y a aussi des conditions suffisantes si la matrice A est une matrice à diagonale

strictement dominante, la méthode de Jacobi et Gauss-Seidel est convergente quel
que soit le vecteur initial x (0) ce qui veut dire:
n
 i  1,.., n aii   aij
j 1
j i

28