Méthodes Numériques
Dr. Salma Chabbar
LERMA - Ecole Mohammadia d’Ingénieurs
Qu’est ce que
Les méthodes numériques ??
Outil de calcul efficace pour résoudre
des problèmes de l’ingénieur
Structure, hydraulique,
Aéronautique, Automobile, Pollution
Biologie, Médecine,
Finance, Economie, …
Problème Ingénierie
Partie théorique: Modélisation Mise en œuvre: Implémentation
Résolution: Méthodes
mathématique Informatique
Numériques
Simulation et Validation
MODELISATION
Choix d’équations décrivant le problème
étudié
Equations aux dérivées partielles (E.D.P)
Equations différentielles
Simplifications et hypothèses convenables
Cohérence, vision globale, paramètres adéquats
Méthodes Numériques
Choix de la méthode d’approximation ou de
résolution du problème considéré.
Exp. Système linéaire ou non linéaire,
EDP: Différences finis, Eléments finis, Volumes
finis …
• Critères mathématiques
• Adéquation au problème considéré
• Coût, Convergence …
INFORMATIQUE
Mise en œuvre des méthodes
numériques adoptées
Choix du logiciel ou langage, code
ouvert, optimal, souple…
SIMULATION
• Résultats numériques et Interprétation
• Validation du code : comparaison avec
des résultats réels.
Résultats numériques
Mesures d’expériences
pratiques
Méthodes Numériques
Les équations
Utilisées pour modéliser plusieurs phénomènes:
la diffusion de la chaleur, la propagation des ondes,
la pollution, l’écoulement d’un fluide, etc…
souvent, se ramènent après discrétisation à des
systèmes linéaires avec des milliers d’équations.
L’approximation d’une solution du problème considéré
nécessite:
La discrétisation,
La résolution du système linéaire ou non linéaire
L’interpolation.
Méthodes numériques
Permettent de passer:
• d’un problème exact à un problème approché en utilisant
la dérivation ou l’intégration numérique.
• d’un problème continu à un problème discret:
discrétisation
Et de:
• Chercher une solution approchée en des points donnés
via la résolution de systèmes linéaires ou non linéaires
et en d’autres points en utilisant l’interpolation.
• Ce sont les notions que nous allons voir en commençant
par l’interpolation.
Plan du cours
I. Approximation et Interpolation
II. Intégration et dérivation numérique
III. Résolution des systèmes linéaires
- Méthodes directes
- Méthodes itératives
IV. Résolution des équations et systèmes
non linéaires
V. Calcul des valeurs et vecteurs propres
Approximation et Interpolation
Partie I
Polynôme d’interpolation
de Lagrange
f(x) fonction connue par ses valeurs yi = f(xi)
aux points xi (n+1 points distincts),
• on construit un polynôme P(x) passant par ces
points.
• Le polynôme d'interpolation P(x) est un
polynôme approchant f(x) et tel que
P(xi) = f(xi)
• P(x) permet de calculer une valeur approchée
de f(x) en un point x différent des xi .
Interpolation linéaire
• Soit f(x) connue en deux points x0 et x1, on
cherche P1(x) polynôme approchant f(x) et
vérifiant:
• P1(x0) = f(x0) (1)
et
• P1(x1) = f(x1) (2)
• P1(x) = a x + b , il suffit d’écrire les deux
équations (1) et (2) pour déterminer a et b.
Interpolation linéaire
• Une autre méthode consiste à écrire P1(x) dans
la base des polynômes de Lagrange de degré 1,
L0(x) et L1(x)
• L0(x) et L1(x) sont déterminés par:
L0(x0) = 1 et L0(x1) = 0
L1(x0) = 0 et L1(x1) = 1
• L0(x) et L1(x) sont des polynômes de degré 1,
linéairement indépendants, ils forment une base
de l’espace des polynômes de degré 1.
Interpolation linéaire
x - xj
Li ( x)
xi - xj
i et j distincts et égaux à 0 ou 1.
et
P1(x) = f(x0)L0(x) + f(x1)L1(x)
Interpolation linéaire
Exemple
Ecrire le polynôme d’interpolation
approchant la fonction f(x) connue par
f(0) = 1 et f(1) = 3
Construction du polynôme de
Lagrange
A l'aide de (n+1) points distincts xi , et n+1
valeurs yi= f(xi), i = 0, ... , n on construit le
polynôme d'interpolation de Lagrange
Pn(x) de degré n par:
Polynômes de base
de Lagrange
• Les polynômes Li vérifient la propriété suivante
• Ils forment une base de l’espace des
polynômes de degré au plus n.
Exemple - Interpolation
quadratique
Déterminer le polynôme d’interpolation
quadratique, approchant la fonction f(x)
connue par
f(-1) = 2, f(0) = 1 et f(1) = 3
Méthode des différences divisées
Une autre façon d’écrire Pn(x)
Pn(x) = a0 + a1(x-x0) + a2(x-x0)(x-x1) + …
+ an(x-x0)(x-x1)…(x-xn-1)
Pn(xi) = f(xi) pour i = 0,…,n
Pn(x0) = f(x0) => a0 = f(x0)
Pn(x1) = f(x1) => a1 = ? (Première différence divisée)
Pn(x2) = f(x2) => a2 = ? (Deuxième différence divisée)
Différences divisées
Définition
1) On appelle différence divisée d’ordre 1 de
f aux points x0,x1, le quotient
f[x0,x1] = f(x1) - f(x0) / x1 - x0
2) On appelle différence divisée d’ordre i de
f aux points x0,x1,…,xi, le quotient
f[x0,x1 ,…,xi] = f[x1,x2 ,..,xi]-f[x0,x1 ,.,xi-1] / xi- x0
Polynôme d’interpolation
On montre que
Pn(x) = a0 + a1(x-x0) + a2(x-x0)(x-x1) + …
+ an(x-x0)(x-x1)…(x-xn-1)
Avec ai = f[x0,x1 ,…,xi]
Intérêt principal de la méthode:
Calculer Pn(x) à partir de Pn-1(x), en ajoutant
le terme de degré n, an étant calculé par la
nième différence divisée à partir des différences
divisées précédentes.
Table des différences divisées
Exemple - Interpolation
quadratique
Déterminer le polynôme d’interpolation
par la méthode des différence divisées
approchant la fonction f(x) connue par :
1/ f(-1) = 2, f(0) = 1 et f(1) = 3
2/ f(0) = 1, f(1) = 5, f(3) = 49 et f(-1)=1
Méthode d’Aïtken
• Cette méthode permet de construire le
polynôme d’interpolation de degré n à partir de
deux polynômes d’interpolation de degré n-1.
• Soit Pn-1(x) le polynôme de degré n-1 passant
par les n points (xi,yi), i = 0,...,n-1
• Soit Qn-1(x) le polynôme de degré n-1 passant
par les n points (xi,yi),i = 1,...,n
• On construit le polynôme d'interpolation de
Lagrange Pn(x) de degré n en utilisant Pn-1(x) et
Qn-1(x)
• Soit : Pn(x) = a(x) Pn-1(x) + b(x) Qn-1(x)
avec a(x) et b(x) des polynômes de degré 1.
tq: a(xn) = 0 et b(x0) =0
• On montre que :
Pn(x) = [(x – x0) Qn-1(x) – (x – xn) Pn-1(x)] /(xn – x0)
• Expression qui vérifie bien :
Pn(xi) = yi pour i = 0,...,n
Unicité
• Soit (x0,x1,…,xn), tq ∀ i≠j xi ≠ xj
∃! P tq deg(P) ≤ n tq P(xi) = f(xi) ∀ i
Démonstration:
• Supposons qu’il existe deux polynômes
d’interpolation de Lagrange: Pn(x) et Qn(x)
• Il suffit de remarquer que Pn-Qn est un
polynôme de degré n qui admet n+1
racines.
• On en déduit que Pn= Qn
Erreur d'interpolation
Interpolation d’Hermite
L'interpolation de Lagrange, présente l'inconvénient
de donner une qualité médiocre : entre les points
d'interpolation la différence entre une fonction et
son polynôme d'interpolation peut être grande, par
ailleurs il y a manque de régularité aux nœuds,
même si le nombre de points est très grand.
Pour remédier à cela on peut essayer d'utiliser non
seulement les valeurs d'une fonction mais aussi
celles de ses dérivées : c'est l'interpolation
d'Hermite.
Exemple
• Comparaison graphique entre interpolation
lagrangienne et hermitienne de la function:
• f(x) =sin(2x+π/4)+1
• en trois points x0=-1, x1=1/2, x2=2.
Interpolation d’Hermite
Les problèmes d'interpolation de Lagrange font
intervenir les valeurs de polynômes en certains
points, mais ne tiennent pas compte des
dérivées.
Si les valeurs des dérivées sont données, on
parle d'interpolation d'Hermite. Si l'on donne par
exemple les valeurs d'une fonction et de sa
dérivée en n+1 points, on peut construire un
polynôme de degré 2n+1, l'écriture du polynôme
utilise les polynômes de Lagrange
Interpolation d’Hermite
Soit P(x) = ∑ Hk(x) f(xk) + ∑ Fk (x) f’(xk)
Avec
Hk(x) = [1-2(x-xk)Lk’(xk)]Lk2(x)
Fk (x) = (x-xk)Lk2(x)
Lk(x) étant le polynôme de base de Lagrange
de degré n.
On vérifie que P(x) est un polynôme de degré 2n+1
qui vérifie P(xk) = f(xk) et P’(xk) = f’(xk) pour k =0,…n
Approximation au sens des
moindres carrés
• On cherche une droite y=ax+b qui approche
au mieux un nuage de points donnés (xi,yi).
• il faut choisir une mesure de l'écart entre la
droite et ce nuage de points expérimentaux:
Moindres carrés
• On choisit en général le carré de la différence
entre les points de la droite et les points
expérimentaux (xi,yi):
• Il s’agit de déterminer a et b de façon à minimiser
la fonction J(a,b).
• Un minimum d'une fonction de plusieurs variables
est atteint en un point où les dérivées partielles
s'annulent
Moindres carrés
Il s’agit donc:
• de résoudre un système de deux équations à
deux inconnues (a et b);
• de trouver la droite qui minimise l’écart J(a,b), on
parle de droite des moindres carrés.
Intégration numérique
• Soit f(x) une fonction donnée sur un
intervalle [a,b], souvent il est difficile ou
même impossible de calculer une primitive
de f.
• Pour calculer la valeur de
il faut souvent utiliser une méthode
d'intégration numérique pour calculer une
valeur approchée.
Intégration numérique
• On suppose que la valeur de f est connue en un
nombre fini de points: a≤x0<x1 …< xn≤b
• On peut déterminer le polynôme d’interpolation
associé à la discrétisation x0<x1 …< xn et
approcher I(f) à l’aide d’une formule de
quadrature :
avec
Calcul de l’erreur
On sait que
L’erreur sur la formule d’intégration est donnée par
Notons F(x) = (x-x0)(x- x 1)…(x-x n)
Calcul de l’erreur
Calcul de l’erreur
Formules élémentaires
Formule du rectangle à gauche (f connue en 1
point x0=a donc n =0):
Cette formule peut être déduite à partir de
l’approximation de f(x) par le polynôme d’interpolation
de degré 0. L’erreur est de:
Dans le cas des formules du rectangle à gauche ou à droite.
Formules élémentaires
Formule du point milieu (f connue en 1 point
x0= (a+b)/2 donc n =0)
où ξ est le point milieu de l’intervalle (a,b)
Formules élémentaires
Formule du trapèze (f connue en 2 points: x0=a
et x1=b donc n =1)
Formule obtenue à partir de l’interpolation
linéaire
Formules élémentaires
• Formule de Simpson(f connue en 3 points: x0=a,
x1=b et x2=m= (a+b)/2, donc n =2)
• L’erreur est
Formules composées
• On peut améliorer l’approximation de
l’intégrale en découpant l'intervalle [a, b]
en n sous – intervalles.
• On calcule alors la valeur approchée de
l'intégrale sur l'intervalle [a, b] comme la
somme des valeurs sur chaque sous –
intervalle avec des points équidistants.
Formules composées
La formule des rectangles composée s’écrit
L’erreur est :
Formules composées
Pour la méthode du point milieu, la formule devient
où mk est le milieu du k-ième sous-intervalle.
Les n sous-intervalles sont identiques, ils sont
de la forme [a + k h, a + (k+1) h],
avec h = (b-a)/n et k = 0, 1, 2, ..., n-1.
Formules composées
Pour la méthode des trapèzes, la formule
composée est
L’erreur est
Formules composées