Méthodes numériques
Sommaire
Chapitre 1 : Résolution de l’équation f(x)=0.
̶ Méthode de bissection.
̶ Méthode des approximations successives.
̶ Méthode de Newton.
Chapitre 2 : Résolution des systèmes d’équations linéaires.
̶ Analyse matricielle.
̶ Méthodes directes : Gauss, Jordan, Cholesky.
̶ Méthode itératives : Jacobi, Gauss, Seidel.
Chapitre 3 : Calcul numérique des valeurs et vecteurs propres.
Chapitre 4 : Méthodes d’interpolation.
̶ Méthode de Lagrange.
̶ Méthode de Newton.
Chapitre 5 : Approximation des fonctions.
Chapitre 6 : Intégration numérique (Newton-Cotes et Simpson).
Chapitre 7 : Equations différentielles.
1
2
Chapitre 1 : Résolution des équations non linéaires
I. Méthode de la bissection
Le terme bissection signifie deux parties (2 intervalles), cette méthode est basée sur le théorème de la
valeur intermédiaire. Elle est aussi appelée méthode de Dichotomie.
Théorème des valeurs intermédiaires : Si une fonction f est continue sur un intervalle [a,b] et qu’elle
change de signe, c’est-à-dire : f(a) f(b)< 0, alors la fonction admet au moins une solution (une racine)
dans cet intervalle.
I.1. Procédure de calcul :
ab
Prendre x0
2
a x1 x0 b
f (a) 0 f ( x1 ) f ( x0 ) f (b) 0
Si f ( x0 ) 0 , alors f ( x0 ) f (a) 0
a x0
Soit x1
2
Si f ( x1 ) 0 , alors f ( x1 ) f (a) 0 , ……………………et on continue :
I.2. Condition d’arrêt :
La procédure s’arrête si xn1 xn
I.3. Nombre des interactions :
ln (b a )
n ; n
ln(2)
ε : c’est une précision (décimale, erreur, %) de calcul choisie en avance.
n : nombre d’itérations
Exemple01: trouver une valeur approchée de la solution de f(x)=0 par la méthode de bissection
dans l’intervalle 1,2 .
f ( x) x3 2 x 4 , à deux décimales après virgule.
2
Solution:
x 1 f (1) 1 x 2 f (2) 8 f (1) f (2) 1 8 8 0
Alors, le zéro existe entre [1,2].
2 1
ln
n
100
6.64 n 7 itérations
ln(2)
n xn a b F(x)
0 (1+2)/2=1,5 1 2 2,375>0
1 (1+1,5)/2=1,25 1 1,5 .
2 . . . .
3 . . . .
4 . . . .
5 . . . .
6 . . . .
7 . . . .
I.4. Avantages de la méthode de Dichotomie :
- La méthode ne pose pas de condition sur la fonction f à résoudre.
- La convergence vers la solution est garantie.
I.5. Inconvénients (limitations) de la méthode :
- La convergence vers la solution par cette méthode est lente (surtout si la précision est grande (c.à.d. ε
est faible)).
II. Méthode des approximations successives (Méthode du point fixe)
II.1. Définition : Pour résoudre l’équation f(x)=0, il faut écrire cette fonction sous la forme : x= g(x) où la
fonction g(x) doit vérifier les deux conditions suivantes :
g ( x) a, b
x a, b
g ( x) 1
'
a, b l’intervalle ou se situe la solution.
II.2. Procédure de calcul: Soit: x0 a, b
x1 g ( x0 )
x2 g ( x1 )
xn 1 g ( xn )
II.3. Condition d’arrêt : On s’arrête par la suite si xn1 xn
Exemple 2 : Résoudre l’équation suivante par la méthode des approximations successives :
x3 x 1 0
prendre une précision de deux décimales.
3
Solution : soit les fonctions suivantes :
1. x x 3 1
1
2. x 2
x 1
x 1
3. x 2
x
1
4. x ( x 1) 3
Soit l’intervalle [1,2]
Question : quelle fonction g(x) vérifie les deux conditions ?
Réponse : l’équation 4 :
* g ( x) 1, 2, x 1, 2
1
x 1
2 / 3
* g '( x)
3
1
g '(1) 0.2 1, g '(2) 0.16 1 , Alors g ( x) ( x 1) 3 , et la méthode des approximations successives est
applicable.
Procédure de calcul : soit x0 1.5
x1 g ( x0 ) g (1.5) 1.35
x2 g ( x1 ) g (1.35) 1.32
x3 g ( x2 ) g (1.32) 1.32
A deux décimal près, la solution converge rapidement vers la solution x3 1.32 .
Condition d’arrêt : xn1 xn 1.32 1.32 0 0.01
III. Méthode de Newton :
La méthode de Newton est utilisée pour résoudre l’équation f ( x) 0 sous les contions de convergence
suivantes :
1. f (a) f (b) 0
2.La fonction f est deux fois dérivable; f '( x) et f ''( x) gardent les signes dans l’intervalle a, b .
3.Si x0 est une solution de départ : f ( x0 ) f ''( x0 ) 0 .
III.1. Procédure de calcul :
Si les trois conditions sont réalisées alors la procédure de calcul est donnée par la suite :
f ( xn )
xn 1 xn
f '( xn )
III.2. Condition d’arrêt : xn1 xn
Exemple : soit f ( x) x 3 4 x 2 10 en utilisant la méthode de Newton,
trouver la solution approchée de f ( x) .
4
Solution :
1. f (1) 5; f (2) 14; f (1) f (2) 0
f '( x) 3x 2 8x
2.
f ''( x) 6 x 8
Les deux dérivées ne sont pas nulles et sont toujours positives x 1, 2
3.Soit :
x0 1.5; f ( x0 ) f (1.5) 2.375
f ''( x0 ) f ''(1.5) 17
f ( x0 ) f "( x0 ) 2.375 17 0
Procédure de calcul :
f ( x0 ) 2.37
x1 x0 1.5 1.3736
f '( x0 ) 18.75
f ( x1 ) f 1.3736
x2 x1 1.3736 1.3652
f '( x1 ) f ' 1.3736
f ( x2 )
x3 x2 1.3652
f '( x2 )
Donc la solution est x3 1.3652 .
Remarque : La méthode de Newton converge beaucoup plus rapidement mais seul inconvénient sont les
conditions posées sur la fonction (f).
5
2
Chapitre 2 : Résolution des systèmes d’équations linéaires
Première partie : Analyse matricielle
I.Introduction
Dans la pratique nous devrons résoudre un système d’équations pour trouver des
déplacements, des déformations, des contraintes, des réactions…etc
En générale, ces équations peuvent être écrites sous la forme suivante :
a11 x1 a12 x2 ..... a1m xm b1
a x a x ..... a x b
21 1 22 2 2m m 2
an1 x1 an 2 x2 ..... anm xm bn
Cette écriture peut être mise sous une forme matricielle tels que :
a11 a12 .... a1m x1 b1
a a .... a x b
21 22 2m 2 2
an1 an 2 .... anm
xn
bn
Le but est de trouver le vecteur :
x1
x2
x où : ax b
xn
II.Rappel sur les matrices
Une matrice est un tableau avec des lignes (n) et des colonnes (m) notés par A( n , m ) ; avec
A une matrice de dimension (n,m).
Matrice ligne : c’est une matrice avec une seule ligne, c’est-à-dire A(1, m) .
Matrice colonne : matrice à une colonne, c'est-à-dire A(n,1) .
Matrice carrée : si n=m c’est-à-dire A(n, n) .
Matrice diagonale : si tous les éléments de la matrice sont nuls à parts la
diagonale.
Matrice unité : c’est une matrice diagonale dont tous les aij 1 .
6
Matrice triangulaire : une matrice est dite triangulaire supérieure si tous les
1 2 3
éléments en dessous de la diagonale sont nuls. 0 5 4
0 0 5
Une matrice est dite triangulaire inférieure si tous les éléments au-dessus de la
diagonale sont nuls.
1 0 0
2 5 0
6 3 5
Matrice transposée : une matrice devient transposée si on permute les lignes par
les colonnes de façon respective, on la note At.
1 1 2 1 3 5
A 3 0 1 ; A 1
t
0 7
5 7 4 2 1 4
Propriétés :
A
t t
A
A B At Bt
t
A B At Bt
t
B Bt
t
( est un nombre réel)
Remarque : une matrice symétrique est une matrice qui coïncide avec sa transposée.
II.Opération sur les matrices.
a) Addition de deux matrices :
Soit A (aij ) nm ; B (bij ) nm ; A B (Cij ) nm ( aij ) nm (bij ) nm
Exemple :
1 1 2 1 2 1 2 1 1
A 3 1 4 ; B 3 5 1 ; A B 6 6
5
5 2 0 0 1 0 5 3 0
b) Multiplication par un scalaire : A (aij ) nm ( aij ) nm
c) Produit de deux matrices : La multiplication de deux matrices
A (aij ) nm ; B (b jk ) mp
Remarque : le nombre de colonnes de A doit être égale au nombre de lignes de B.
7
m
Le produit obéit à la formule suivante A B (cik ) np ; Cij aik bkj
k 1
ème ème
C'est donc la somme des produits de la i ligne de A par la j ligne de B.
Exemple :
1 2 1 4 2 1 3
A 1 0 3 ; B 1 1 0 0 ;
2 1 4 2 1 1 3
A B
=
A B=
d) Matrice inversible : une matrice est dite inversible si son déterminant n’est pas nul
c'est-à-dire det( A) 0 . B est une matrice inverse de A si : AB = BA = I.
Propriété :
(A B)-1 = B-1 A-1
(A-1)t = (At)-1
e) Déterminant d’une matrice :
- Cas n m 1: A [a]; det( A) a
a11 a12
- Cas n m 2 : A ; det( A) a11 a22 a21 a12
a21 a22
n
-Cas n = m > 3: on donne : det( A) (1)i k aik det( M ij )
k 1
Exemple :
A= ; B= ; C=
1 1
det( A) 5
2 3
8
1 2 1
1 1 3 1 3 1
det( B ) 3 1 1 1 2 1 8
1 0 2 0 2 1
2 1 0
1 1 0
1 3 1 0 1 0
det(C ) 2 1 3 1 2 1 0
0 1 0 1 1 3
1 0 1
f) Inverse d’une matrice:
A 1
A
* t
det A
A : c’est une matrice transposée de la matrice des cofacteurs. (A
* t *
est une matrice des cofacteurs).
A* aij ; aij * 1
* i j
det( M ij )
a11* a12*
1 det M 11 1 det M 12
11 1 2
*
A a21
*
Deuxième partie : Résolution d’un système d’équations linéaires par les
méthodes discrètes.
III.1. Méthode de Gauss (1777-1855)(Elimination de Gauss)
III.1.1. Définition :
La méthode de Gauss consiste à éliminer tous les termes éléments en dessous de la diagonale d’une
matrice augmentée.
Matrice augmentée : la matrice augmentée est une matrice dont on fait ajouter les éléments de la matrice
[B] à droite de la matrice [A], c'est-à-dire [A](x) = [B]
D’où :
A=
La matrice augmentée de A s’écrit :
La méthode de Gauss (dite aussi méthode d’élimination de Gauss) consiste à mettre a 21 = a31 = a32 = 0.
Exemple : Résoudre le système suivant.
9
2x1 + x 2 + 2x 3 = 10
6x1 + 4x 2 = 26
8x + 5x + x = 35
1 2 3
Solution :
Ecriture en forme matricielle, c'est-à-dire : [A](x) = [B]
2 1 2 x1 10
6 4 0 x 26
2
8 5 1
x3 35
La matrice augmentée :
2 1 2 10
6 4 0 26
8 5 1 35
2 1 2 10 2 1 2 10 2 1 2 10
6 4 0 26 L 3L 0 1 6 4 0 1 6 4
2 1
8 5 1 35 L3 4 L1 0 1 7 5 L3 L2 0 0 1 1
x3 1 x3 1
x2 6 x3 4 x2 2
2 x x 2 x 10 x 3
1 2 3 1
III.2.Méthode de Gauss (1777-1855)-Jordan (1838-1922).
Définition :
La méthode de Jordan est une correction de celle de Gauss, elle consiste à convertir la matrice A en une
matrice unité et ainsi la solution est obtenue directement à partir de la diagonale.
A= I=
Exemple : Résoudre le système d’équation suivant.
x1 -x 2 + 2x 3 = 5
3x1 + 2x 2 +x 3 = 10
2x -3x -2x = -10
1 2 3
Solution :
Ecriture en forme matricielle :
La matrice augmentée :
L2 – 3L1 ; L3 – 2L1
L2/5 L1 + L2 ; L3 – L2
10
L3/-7 L1 – L3 ; L2 + L3
x1 1
x2 2
x 3
3
III.3.Méthode de Cholesky (1875-1918).
Définition :
Cette méthode consiste à décomposer la matrice A en un produit de deux matrices c'est-à-dire :
[A] = [L][M].
[L] : une matrice triangulaire inférieure avec tous les éléments L 11 = L22 = L33 = 1.
[M] : une matrice triangulaire supérieure c'est-à-dire :
Soit A = (3 3)
Et ainsi on trouve les éléments (Lij) et (Mij).
La solution : Résoudre [A](x)=[B] revient à résoudre [L][M]=[B].
Pour trouver (x) on passe par deux étapes :
[L][M](x) = [B] trouver [Y]
[M](x) = [Y] trouver [X].
Exemple : Résoudre le système suivant :
x1 +2x 2 + x 3 -1 =0
2x1 + x 2 +3x 3 +2 = 0
x +2x + 4x 3 0
1 2 3
Solution : forme matricielle :
Décomposition de A :
M11 = 1 , M12 = 2 , M13 = 1
L21M11 = 2 L21 = 2
L21M12 + M22 = 1 M22 = -3
L21M13 + M23 = 3 M23 = 1
L31M11 = 1 L31 = 1
L31M12 + L32M23 + M33 = 4 M33 = 3
L= ;M=
11
Au lieu de résoudre [A](x) = [B].
y1 1
[L][Y] = [B] = y 2 4
y 4
3
x3 1.3333
[M][X] = [Y] x2 1.7777
x 1.221
1
Troisième partie : Méthodes itératives pour la solution des systèmes
d’équations linéaires.
I.Introduction :
Question : Itératives ?
Réponse : Cela vient du mot itération c'est-à-dire étape, pas.
Question : Quel est le type de la solution dans les méthodes :
Réponse : a) Directe : solution exacte.
b) Itérative : solution approchée (approximatif).
Question : pourquoi on utilise les méthodes itératives ?
Réponse : En réalité les problèmes rencontrés sont de matrice A d’ordre (n) très élevés
(nombre de colonnes et de lignes est grand). Donc il est impossible d’utiliser les méthodes directes.
Dans ce chapitre, on se base sur les deux méthodes itératives suivantes :
Méthode de Jacobi.
Méthode de Gauss-Seidel.
Principe des méthodes itératives :
Sortie
Entrer ̶ Lois ̶ Condition d’arrêt
Initialisation ̶ Algorithme ̶ Erreur
̶ Boucle compteur ̶ Précision
VI.1 Méthode de Jacobi :
Cette méthode consiste à résoudre un système d’équations linéaires de (n) équation avec (n) inconnus.
Soit résoudre le système suivant :
a11x1 + a12x2 + + a1nxn = b1
a21x1 + a22x2 + + a2nxn = b2
an1x1 + an2x2 + + annxn = bn
Procédure :
On fait sortir les xi (i=1 à n) des équations correspondantes, tel que :
12
x1 = [b1 – (a12x2 + a13x3 + + a1nxn ]
x2 = [b2 – (a21x1 + a13x3 + + a2nxn ]
xn = [bn – (an1x1 + an2x2 + + ann-1xn-1 ]
D’où le système d’équation peut se mettre sous la formule générale suivante:
= [bi – ]
-Initialisation: (itération zéro: k=0)
Pour k=0: xi(0) = 0 ; (x1(0) = x2(0) = = xn(0) = 0).
-Calcul itérative
Itération k= X1 X2 X3 X4 …
0 0 0 0 0
1 X X X X
2 X X X X
3 X X X X
4 X X X X
Condition d’arrêt : On ne s’arrête que si i = 1 à n. |xik+1 – xik| < ; : donné.
Exemple :
Résoudre le système suivant pa la méthode de Jacobi avec une erreur de 0,005.
8x1 + x2 – x3 = 8
x1 – 7x2 + 2x3 = -4
2x1 + x2 + 9x3 = 12
Solution :
x1 = 1/8 [8 – x2 + x3]
x2 = 1/7 [4+ x1 +2x3]
x3 = 1/9 [12 – 2x1 – x2]
x1k+1 = 1 - 0,125x2k + 0,125x3k
x2k+1 = 0,571 + 0,142x1k + 0,285x3k
x3k+1 = 1,333 - 0,222x1k + 0,111x2k
Initialisation : pour k=1, x1(1) = x2(1) = x3(1) = 0
Itération 1 : k=2
x1(2) = 1 - 0,125 0 + 0,125 0 = 1
x2(2) = 0,571 - 0,142 0 + 0,285 0 = 0,571
13
x3(2) = 1,333 - 0,222 0 + 0,111 0 = 1,333
Vérification : Tous les xi(2) ne vérifient pas la condition d’arrêt.
Itération 2 : k=3
x1(3) = 1 - 0,125 0,571 + 0,125 1,333 = 1,095
x2(3) = 0,571 - 0,142 1 + 0,285 1,333 = 1,092
x3(3) = 1,333 - 0,222 1 + 0,111 0,571 = 1,047
Vérification : Tous les xi(3) ne vérifient pas la condition d’arrêt.
Itération k= X1 X2 X3
1 1 0,571 1,333
2 1,095 1,095 1,048
3 0,955 1,026 0,969
4 0,993 0,990 1
5 1,002 0,998 1,004
6 1,001 1,001 1,001
x1(6) = x2(6) = x3(6) = 1,001 qui est la valeur la plus proche de la valeur exacte x=1.
VI.2. Méthode de Gauss-Seidel :
Définition :
La méthode de Gauss-Seidel est une modification de la méthode de Jacobi.
K=0 x10= x20=.........= x30=0
K=1
x1k+1 = 1 – 3x2k + x3k
x2k+1 = 2 + 3x1k+1 – x3k
x3k+1 = 5 – x2k+1 + x1k+1
Elle consiste à injecter toutes les nouvelles valeurs xik+1 trouvées dans la même itération.
C’est-à-dire chaque nouvelle valeur xik+1 trouvée dans la même itération écrase l’ancienne valeur xik.
Convergence des méthodes de Jacobi et de Gauss-Seidel :
Il suffit que l’une des conditions suivantes soit vérifiée, qu’elle converge :
Si la matrice (A) est une matrice dominante, les deux méthodes convergent.
Si la matrice (A) est une matrice symétrique définie positive, la méthode de Gauss-Seidel converge
mais pas forcément celle de Jacobi.
Remarque : Si un système d’équation converge vers une solution cela veut dire qu’il vérifie les deux
conditions de convergences (conditions suffisantes).
Définition :
1.Une matrice est dite diagonale dominante si |aii| > .
Exemple :
A= |2| > |0|+|1| ; |-6| > |1|+|2| ; |7| > |1|+|-2|.
14
2.Une matrice définie positive si tous les mineurs diagonaux sont positifs.
Exemple :
Dans l’exemple précédent, on résous un système d’équations linéaires par la méthode de Gauss-Seidel.
Avec une erreur de .
8x1 + x2 – x3 = 8
x1 – 7x2 + 2x3 = -4
2x1 + x2 + 9x3 = 12
x1k+1 = 1 - 0,125x2k + 0,125x3k
x2k+1 = 0,571 + 0,142x1k + 0,285x3k
x3k+1 = 1,333 - 0,222x1k + 0,111x2k
Initialisation : x1 = x2 = x3 = 0
Itération1 : k=1
x1 = 1
x2 = 0,571 + 0,142(1) + 0,285(0)
x3 = 1,333 + 0,222(1) - 0,111(0,714) = 1,032
Itération2 :
x1= 1 - 0,125(0,714) + 0,125(1,032) = 1,039
x2 = 0,571 + 0,142(1,039) + 0,285(1,032) = 1,012
x3 = 1,333 + 0,222(1,039) - 0,111(1,012) = 0,997
Itération3 :
x1= 1 - 0,125(1,012) + 0,125(0,997) = 0,998
x2 = 0,571 + 0,142(0,998) + 0,285(0,997) = 0,996
x3 = 1,333 - 0,222(0,998) - 0,111(0,996) = 1,0008
k X1 X2 X3
1 1 0,714 1,032
2 1,039 1,012 0,997
3 0,997 0,996 1,001
4 1,0006 0,9998 1,001
Test d’arrêt:
|1,0006 – 0,997| = 0,0036 <
|0,9998 – 0,996| = 0,0038 <
15
|1,001 – 1,001| = 0 <
Chapitre 3 : Intégration numérique
I. Introduction :
Question : Pourquoi utilise-t-on l’intégration numérique ?
Réponse : On utilise l’intégration numérique lorsqu’il est impossible ou difficile d’intégrer une fonction
(f) continue sur un intervalle [a,b].
Question : Qu’est-ce que l’intégration numérique ?
Réponse : L’intégration numérique consiste à décomposer l’intégrale de la fonction d’un polynôme plus
l’erreur.
E : erreur due à l’approximation.
Pn(x) : polynôme de degré (n).
Pour trouver Pn(x), il est indispensable de passer des formules mathématiques, tel que la formule de
Lagrange.
Ce qui nous donne des formules appelées formules de Newton-Côtes.
Remarque : dans ce cours, on s’intéressera à des cas particuliers correspondants à la valeur de n des ce
polynôme, c'est-à-dire :
Si n =1 : Méthode de trapèze
Si n =2 : Méthode de Simpson 1/3
Si n =3 : Méthode Simpson 3/8
II.Méthode de Trapèze :
On souhaite évaluer l’intégrale où est une fonction connue en deux points ou encore une
fonction n’ayant pas de primitive.
La solution consiste à remplacer la formule par un polynôme de degrés 1 passant par les points (x 0, f(x0))
et (x1, f(x1)).
La valeur approximative de l’intégrale correspond à l’aire qui se trouve sous la courbe du polynôme.
Cette aire forme un trapèze d’où le nom de la méthode.
f(x1)
f(x0)
Aire d’un trapèze
16
x1
x0
Cette méthode a deux formes :
II.1. Méthode du trapèze simple :
Pour cela on donne la forme de l’intégrale suivante :
f(x1)
f(x2)
x0 x1
Exemple : Calculer
II.2. Méthode de trapèze composé :
Cette méthode consiste à diviser l’intervalle [x0,x1] en sous intervalles.
La longueur de chaque intervalle est désigné par , n : est le nombre d’intervalles.
La forme de l’intégrale devient alors :
Exemple : calculer par la méthode du trapèze composé à quatre intervalles.
Solution : n=4 , h=
17
X0 = a
II.3. L’erreur de la méthode de trapèze.
L’erreur est donnée par la formule :
avec M2 : max[a,b] (f"(x))
II. Méthode de Simpson 1/3.
Cette méthode utilise un polynôme de degré 2 dont la courbe passe par trois points (x 0,f(x0)), (x1,f(x1)),
(x2,f(x2)).
Le polynôme est donné par la formule suivante :
Question : démontrer la formule :
Remarque : le facteur 1/3 qui multiplie le (h) est à l’origine du nom de la méthode.
Exemple : calculer par la méthode de Simpson 1/3.
Solution :
Amélioration de Simpson 1/3 :
On peut améliorer la méthode de Simpson 1/3 en divisant l’intervalle équidistant et en utilisant
Simpson1/3 pour chaque paire d’intervalle.
La formule devient alors :
Remarque :
Le premier et le dernier terme sans multiplication.
Les paires sont multipliées par 2.
Les impaires sont multipliées par 4.
Exemple : Trouver par Simpson 1/3 amélioré avec 4 intervalles.
Solution :
L’erreur de Simpson 1/3.
L’erreur est donnée par la formule :
18
M4= max[a,b]|f"(x)|
Remarque : Cette méthode est précise (l’erreur =0) si le polynôme est de degré (la quatrième
dérivée est nulle).
V.I. Méthode de Simpson 3/8.
Si on utilise un polynôme de degré 3 dans l’intervalle [x0, x3] et passant par les points (x0, f(x0)), (x1,
f(x1)), (x2, f(x2)), (x3, f(x3)) la formule de Simpson 3/8 s’écrit :
Amélioration de Simpson 3/8 :
On peut également composer cette méthode en divisant l’intervalle [a,b] en 3n sous intervalle, tel que :
et on obtient :
19