Calcul numérique

Pr. Keltoum Chahour

13 mars 2023

Calcul numérique 1 / 37
Introduction au calcul numérique approché

Interpolation de fonctions

Intégration numérique

Calcul numérique 2 / 37
Calcul numérique approché
▶ On cherche à évaluer de manière numérique l’exponentielle
Z = exp(x). Trouver z̃ approchant numériquement z.
▶ Une méthode consiste à utiliser la série de Taylor :
+∞ k
X x
(∀x ∈ R) exp(x) =
k!
k=0
▶ En considérant des ressources de calcul limitées, on en est
réduit à déterminer :
K
X xk
z̃ =
k!
k=0

Pour le calcul de l’exponentielle, on commet donc une

erreur !

Calcul numérique 3 / 37
Calcul numérique approché : erreurs

Erreurs relatives aux données d’entrée

▶ Erreur de mesure Il s’agit de la différence entre la valeur

exacte x et la valeur mesurée x̃ :

∆x = |x − x̃|
▶ Erreur d’arrondi Elle est générée par la différence entre la
valeur exacte x et la valeur arrondie fl(x) = x̂ :

∆x = x − x̂

Calcul numérique 4 / 37
Calcul numérique approché : erreurs

Exemple : On veut calculer avec la calculatrice la somme entre

x1 = 6.2317 × 107 et x2 = 2.179 × 102 .
La valeur exacte du calcul est x = 6.23172179 × 107 et la valeur
calculée est x̂ = 6.2317 × 107 .

Erreurs résultantes d’un calcul

▶ Erreur de troncature Dans le calcul de l’exponentielle par

exemple, l’erreur de troncature vaut :
+∞ k
X x
T = z − z̃ =
k!
K +1

Calcul numérique 5 / 37
Calcul numérique approché : Type d’erreurs

▶ Erreur absolue

∆z = z − z̃
▶ Erreur relative

z − z̃
δz =
z

Calcul numérique 6 / 37
Calcul numérique approché
Exemple de l’exponentielle :
+∞ k K
X x X xk
z= ; z̃ =
k! k!
k=0 k=0

▶ Quelques résultats numériques sur l’erreur :

Calcul numérique 7 / 37
Interpolation de fonctions

Soit f une fonction continue définie sur [x0 , xn ] ∈ R, on peut

approcher la fonction f par une fonction d’approximation qui
coïncide avec f en n points xi .

→ On dit on a fait une interpolation de la fonction f sur

l’intervalle [x0 , xn ]. En général, les fonctions d’approximation sont :
▶ Des polynômes : les polynômes de Lagrange, polynômes
d’Hermite par exemple.
▶ Des fractions rationnelles.
▶ Des fonctions trigonométriques : les séries de Fourrier par
exemple.

Calcul numérique 8 / 37
Interpolation de Lagrange

Théorème : Soit x0 . . . xn , (n + 1) points où f est connue, il existe

un unique polynôme Pn (x) tel que : Pn (xi ) = f (xi ).

Polynômes d’interpolation de Lagrange

Pour construire Pn , on peut utiliser les polynômes de Lagrange,
notés Li tels que :
n n
X Y x − xj
Pn (x) = f (xi )Li (x) avec Li (x) =
xi − xj
i=0 j=0,j̸=i

Calcul numérique 9 / 37
Interpolation de Lagrange

▶ Pour n = 1 : P1 (x) = L0 (x)f (x0 ) + L1 (x)f (x1 )

(x − x1 ) (x − x0 )
L0 (x) = , L1 (x) =
(x0 − x1 ) (x1 − x0 )
▶ Pour n = 2 : P2 (x) = L0 (x)f (x0 ) + L1 (x)f (x1 ) + L2 (x)f (x2 )

(x − x1 )(x − x2 ) (x − x0 )(x − x2 )
L0 (x) = , L1 (x) = ,
(x0 − x1 )(x0 − x2 ) (x1 − x0 )(x1 − x2 )

(x − x0 )(x − x1 )
L2 (x) =
(x2 − x0 )(x2 − x1 )

Calcul numérique 10 / 37
Interpolation de Lagrange

Figure – Exemple d’interpolation de Lagrange.

Calcul numérique 11 / 37
Interpolation d’Hermite
Théorème : Soit n + 1 points où f et ses k me dérivées sont
connues, il existe un unique polynôme Pm (x) tel que :
(j)
Pm (xi ) = f (j) (xi ) avec j = 0, . . . , ki et m = n + k0 + · · · + kn .

Polynôme d’interpolation d’Hermite

ki
n X
X
Pm (x) = f (j) (xi )hij (x)
i=0 j=0

ki
(x − xi )j
Clj qil−j (xi )hil (x)
X
hij = qi (x) −
j!
l=j+1

(x − xi )ki
hiki = qi (x)
ki !
qi (x) = Li (x)k+1

Calcul numérique 12 / 37
Interpolation d’Hermite
Exemple : On considère la fonction f (x) = xsin(2x + π4 ) + 1 en 3
points : −1, 21 , 2. L’interpolation hermitienne est plus précise que
l’interpolation lagrangienne.

Figure – Comparaison : interpolation d’Hermite et de Lagrange.

Calcul numérique 13 / 37
Approximation polynômiale au sens des moindres carrés
On cherche les composantes αi d’un polynôme dans une base de
polynômes ei telles que la distance
Pentre la fonction f et le
n
polynôme d’approximation Pp = i=0 αi ei soit minimale au sens
des moindres carrés.

Définition : Soit I un intervalle borné sur lequel f est définie, on

appelle la distance des moindres carrées la mesure définie par :
Z
|f (x) − Pp (x)|2 dx
I

Si on a n + 1 points discrets :
n
X
|f (xi ) − Pp (xi )|2
i=0

Calcul numérique 14 / 37
Approximation polynômiale au sens des moindres carrés

Théorème : A p fixé, il existe un unique polynôme qui minimise la

distance des moindres carrés.

Exemple : On considère n + 1 points de l’intervalle I et on prend :

ei = x i la base canonique. On cherche :

min ||Aα − b||2

α

Avec : Aij = xij et bi = f (xi ), i = 0, . . . , n et j = 0, . . . , p

Ca revient à résoudre le problème :

AT Aα = AT b

Calcul numérique 15 / 37
Erreur d’interpolation

Définition : On définie l’erreur d’intérpolation par :

En (x) = f (x) − Pn (x)

Théorème : Si f est n + 1 fois dérivable sur [x0 , xn ], alors

∀x, ∃ζ ∈ [x0 , xn ] tel que :
n
f (n+1) (ζ) Y
En (x) = (x − xi )
(n + 1)!
i=0

Le choix des points d’interpolation est important !

Calcul numérique 16 / 37
Erreur d’interpolation

Comment choisir les points d’interpolation ? ?

Les racines du polynôme de Tchebychev :

x0 + xn xn − x0 2(n − i) + 1
xi = + cos( )π
2 2 2n + 2
Dans ce cas, l’erreur est :

f (n+1) (ζ) x0 − xn n+1

En (x) = 2 ( )
(n + 1)! 4

L’erreur ne dépend plus du choix des points d’interpolation

intérieurs, ceci dit la convergence est uniforme.

Calcul numérique 17 / 37
Intégration numérique

Soit f une fonction intégrable au sens de Riemann définie sur

l’intervale I ∈ R. On cherche une méthode numérique pour
approcher l’intégrale de f par une somme finie :
Z n
X
f (x)dx ≃ ai f (xi )
I i=0

Il existe 3 types de méthodes :

▶ Les méthodes de Newton-Cotes simple.
▶ Les méthodes de Newton-Cotes composites.
▶ Les méthodes de Gauss.

Calcul numérique 18 / 37
Méthodes de Newton-Cotes simples

Les méthodes de Newton-Cotes simple ne permettent pas à elles

seules d’atteindre des précisions sur des intervalles [a, b]. En
revanche, elles deviennent plus précise lorsque |b − a| → 0. Elles
constituent donc la base élémentaire des méthodes composites.

Principe : Approximer la fonction f à intégrer par un polynôme

P(x) ≈ f (x), si l’approximation est suffisament bonne on a :
Z b Z b
f (x)dx ≈ P(x)dx
a a

Calcul numérique 19 / 37
Méthodes de Newton-Cotes simples

▶ On choisit un polynôme d’ordre p qui coïncide avec f en p + 1

points distincts, espacés régulièrement sur l’intervalle [a, b].
Ces points sont situés aux positions :

b−a
xk = a + kh, k ∈ [0, p] avec h=
p
∀k ∈ [0, p] P(xk ) = fk = f (xk )
▶ Le degré de polynôme définit l’ordre de la méthode
d’intégration.

Calcul numérique 20 / 37
Méthodes de Newton-Cotes simples

Méthode du rectangle (p = 0)
▶ On prend le polynôme de degré 0, à savoir le polynôme
constant :
P0 (x) = f (a) = f0
▶ L’intégrale approché

∼
Z b
I = P0 (x)dx = (b − a) f0
a

Calcul numérique 21 / 37
Méthodes de Newton-Cotes simples
Méthode du rectangle (p = 0)

▶ L’erreur peut être estimée en utilisant le développement en

série de Taylor, on trouve pour h = b − a :

h2 ′ h2
∃ζ ∈ [a, b] ϵ0 = f (ζ) c.a.d |ϵ0 | ≤ sup(|f ′ |)
2 2 [a,b]
Calcul numérique 22 / 37
Méthodes de Newton-Cotes simples

Méthode du point milieu (p=0)

▶ On prend toujours le polynôme de degré 0, cette fois au point
milieu :
a+b
P0′ (x) = f ( )
2
▶ L’intégrale approché
∼ Z b
′ a+b
I = P0′ (x)dx = (b − a) f ( )
a 2

Calcul numérique 23 / 37
Méthodes de Newton-Cotes simples
Méthode du point milieu (p=0)

▶ En utilisant le développement en série de Taylor, on trouve

l’erreur pour h = b − a :

h3 ′′ h3
∃ζ ∈ [a, b] ϵ′0 = f (ζ) c.a.d |ϵ′0 | ≤ sup(|f ′′ |)
24 24 [a,b]
Calcul numérique 24 / 37
Méthodes de Newton-Cotes simples

Méthode des trapèzes (p =1)

▶ On utilise le polynôme de degré 1 (la droite) qui passe par
f0 = f (a) et f1 = f (b) :

f0 + f1 f1 − f0 a+b
+ (x − )
2 b−a 2
▶ L’intégrale approché

∼
Z b
f0 + f1
I1 = P1 (x)dx = (b − a)
a 2

Calcul numérique 25 / 37
Méthodes de Newton-Cotes simples
Méthode des trapèzes (p =1)

▶ L’erreur pour h = b − a : est telle que :

h3 ′′ h3
∃ζ ∈ [a, b] ϵ1 = − f (ζ) c.a.d |ϵ1 | ≤ sup(|f ′′ |)
12 12 [a,b]

Calcul numérique 26 / 37
Méthodes de Newton-Cotes simples

Méthode de Simpson (p=2)

▶ Cette méthode utilise le polynôme de degré 2 (la parabole) qui
passe par les 3 points : f0 = f (a), f1 = f ( a+b
2 ) et f2 = f (b) :

f2 − 2f1 + f0 f2 − f0
P2 (x) = 2 (x − x1 )2 + (x − x1 ) + f1
(x2 − x0 )2 x2 − x0
▶ L’intégrale approché

∼ b
f0 + 4f1 + f2
Z
I2 = P2 (x)dx = (b − a)
a 6

Calcul numérique 27 / 37
Méthodes de Newton-Cotes simples
Méthode de Simpson (p=2)

▶ L’erreur pour h = (b − a)/2 : est telle que :

h5 (4) h5
∃ζ ∈ [a, b] ϵ2 = − f (ζ) c.a.d |ϵ2 | ≤ sup(|f (4) |)
90 90 [a,b]

Calcul numérique 28 / 37
Méthodes de Newton-Cotes simples
Autres méthodes
On peut utiliser des polynômes de degrés supérieurs, on trouve des
méthodes d’intégration d’ordres élevés :
▶ Méthode de Simpson 3/8 (p =3)
∼ f0 + 3f1 + 3f2 + f3
I = (b − a)
8
3h5 (4)
ϵ=− f (ζ)
80
▶ Méthode de Boole (p=4)
∼ 7f0 + 12f1 + 32f2 + 12f3 + 7f4
I = (b − a)
90
8h7 (6)
ϵ=− f (ζ)
945

Calcul numérique 29 / 37
Méthodes de Newton-Cotes composites

▶ On subdivise l’intervalle [a, b] en n sous-intervalles [xk , xk+1 ],

∼
on calcule une approximation de l’intégrale Ik avec
k ∈ [0, m − 1] sur chaque petit intervalle par des méthodes de
Newton-Cotes simples, puis on déduit l’intégrale totale :

∼ m−1
X∼
I = Ik
k=0
▶ Si on prend m intervalles continus, la méthode de
Newton-Cotes composite définit n = m × p sous-intervalles au
total et nécessite l’évaluation de f en n + 1 points.

Calcul numérique 30 / 37
Méthodes de Newton-Cotes composites
Méthodes des rectangles (p=0, n=m)
∼
▶ I0,k = (xk+1 − xk )fk = hfk
▶ L’intégrale totale :

∼
I0 = h(f0 + f1 + · · · + fn−1 + 0 × fn )
n−1
X
=h fk
k=0
▶ L’erreur pour h = (b − a)/n est la somme sur les erreurs :

n−1 n−1
X h2 X ′
ϵ0 = ϵ0,k = f (ζk )
2
k=0 k=0
h2
= nf ′ (ζ)
2
(b − a)2
|ϵ0 | ≤ sup(|f ′ |)
Calcul numérique 2n [a,b] 31 / 37
Méthodes de Newton-Cotes composites

Méthode des trapèzes (p=1,n=m)

∼ f + fk+1
▶ I0,k = (xk+1 − xk ) k
2
▶ L’intégrale totale :

∼ f0 + 2f1 + · · · + 2fn−1 + fn
I0 = h
2
n−1
f0 X fn
= h( + fk + )
2 2
k=0

Calcul numérique 32 / 37
Méthodes de Newton-Cotes composites

Méthode des trapèzes (p=1,n=m)

▶ L’erreur pour h = (b − a)/n :

n−1
X
ϵ1 = ϵ1,0 /2 + ϵ1,k + ϵ1,n /2
k=1
n−1
h3 ′′ X h3
=− (f (ζ0 )/2 + f ′′ (ζk ) + f ′′ (ζn )/2) = − nf ′′ (ζ)
12 12
k=1
(b − a)3
|ϵ1 | ≤ sup(|f ′′ |)
12n2 [a,b]

Calcul numérique 33 / 37
Méthodes de Newton-Cotes composites
Méthode de Simpson (p=2, n=2m)
∼ f + 4fk+1 + fk+2
▶ I2,k = (xk+2 − xk ) k
6
▶ L’intégrale totale :

∼ f0 + 4f1 + 2f2 + 4f3 + · · · + 2fn−2 + 4fn−1 + fn

I2 = h
3
n/2−1 n/2−1
h X X
= (f0 + 4 f2k+1 + 2 f2k + fn )
3
k=0 k=1
▶ L’erreur :

h5 (4)
ϵ2 = − mf (ζ)
90
(b − a)5
|ϵ2 | ≤ sup(|f (4) |)
180n4 [a,b]
Calcul numérique 34 / 37
Méthodes de Gauss
On cherche une formule de quadrature tel que l’intégration de
l’approximation de f par un polynôme de degré p soit exacte. Sur
chaque intervalle, on remplace f par un polynôme d’ordre n :
n n
X Y f (n+1) (ζ)
f (x) = Li (x)f (xi ) + (x − xi )
(n + 1)!
i=0 i=0

On s’intéresse à l’intégrale pondérée par w (x) :

Z b n
X
f (x)w (x)dx ≈ wi f (xi )
a i=0

On cherche les poids wi et les points d’intégration xi tels que

l’intégration soit exacte pour un polynôme de degré 2n + 1 :
▶ Les xi sont les racines des polynômes orthogonaux de degré
n + 1 pour le poids w (x).
▶ Les wi sont données par : wi = ab Li (x)w (x)dx
R

Calcul numérique 35 / 37
Méthodes de Gauss

Gauss-Legendre

Pour [a, b] = [−1, 1] et w (x) = 1

▶ Les points d’intégration sont les racines du polynôme de
Legendre de degré n + 1.

P0 (x) = 1, P1 (x) = x
(n + 1)Pn+1 (x) = (2n + 1)xPn (x) − nPn−1
R1
▶ Les poids sont donnés par : wi = −1 Li (x)dx

Calcul numérique 36 / 37
Méthodes de Gauss

Gauss-Tchebychev

Pour [a, b] = [−1, 1] et w (x) = √ 1

1−x 2
▶ Les points d’intégration sont les racines du polynôme de
Tchebychev de degré n + 1 :

(2i + 1)π
xi = cos(
2n + 2
R 1 Li (x)
▶ Les poids sont donnés par : wi = −1 √ dx
1−x 2

Calcul numérique 37 / 37