CHAPITRE 1: INTERPOLATION POLYNOMIALE ET
APPROXIMATION
Approximation au sens des moindres carrés
4 GC
Analyse Numérique
A.U. 2020/2021
Problématique: L’interpolation polynomiale
n’est pas toujours stable en dehors des
points de contrôle → Phénomène de Runge.
coûteuse en terme de temps de calcul
lorsque le nombre de points de contrôle est
élevé (nuage de points).
(cid:243) AA2: Approximation (ou régression)
polynomiale
Introduction
2
Historique:
1804: Carl Friedrich Gauss
1805: Adrien-Marie Legendre
1808: Robert Adrain
Equipe AN
Analyse Numérique (AN)
ESPRIT
Introduction
2
Historique:
1804: Carl Friedrich Gauss
1805: Adrien-Marie Legendre
1808: Robert Adrain
Problématique: L’interpolation polynomiale
n’est pas toujours stable en dehors des
points de contrôle → Phénomène de Runge.
coûteuse en terme de temps de calcul
lorsque le nombre de points de contrôle est
élevé (nuage de points).
(cid:243) AA2: Approximation (ou régression)
polynomiale
Equipe AN
Analyse Numérique (AN)
ESPRIT
3
Objectif: Comparer des données expérimentales à un modèle polynomial censé
décrire ces données.
Le modèle polynomial est une famille de polynômes:
P (x, Λ)
(cid:46) (cid:38)
Variable réelle
un ou plusieurs paramètres inconnus
"les coefficients du polynôme"
Equipe AN
Analyse Numérique (AN)
ESPRIT
Objectif: Trouver la droite d’équation
y = λ0 + λ1x
(cid:124)
(cid:123)(cid:122)
P (x)
(cid:125)
la plus proche des points (xi, yi) au sens des moindres carrés
Approximation (ou régression) linéaire
4
Soient (n + 1) points (xi, yi), i ∈ {0, 1, · · · , n}, d’abscisses deux à deux distinctes. On
note
X =
, Y =
x0
...
xi
...
xn
.
y0
...
yi
...
yn
Equipe AN
Analyse Numérique (AN)
ESPRIT
Approximation (ou régression) linéaire
4
Soient (n + 1) points (xi, yi), i ∈ {0, 1, · · · , n}, d’abscisses deux à deux distinctes. On
note
X =
, Y =
x0
...
xi
...
xn
.
y0
...
yi
...
yn
Objectif: Trouver la droite d’équation
y = λ0 + λ1x
(cid:125)
(cid:124)
(cid:123)(cid:122)
P (x)
la plus proche des points (xi, yi) au sens des moindres carrés
Equipe AN
Analyse Numérique (AN)
ESPRIT
Le problème consiste à minimiser une fonction des résidus ei.
Quelle est l’expression de cette fonction
Quelle est la norme à considérer
Illustration de la méthode
5
(S1)
e0 = P (x0) − y0 = λ0 + λ1x0 − y0
...
ei = P (xi) − yi = λ0 + λ1xi − yi
(cid:46)
...
en = P (xn) − yn = λ0 + λ1xn − yn
résidu
(ou perturbation)
en (xi, yi)
Equipe AN
Analyse Numérique (AN)
ESPRIT
Illustration de la méthode
5
(S1)
e0 = P (x0) − y0 = λ0 + λ1x0 − y0
...
ei = P (xi) − yi = λ0 + λ1xi − yi
(cid:46)
...
en = P (xn) − yn = λ0 + λ1xn − yn
résidu
(ou perturbation)
en (xi, yi)
Le problème consiste à minimiser une fonction des résidus ei.
Quelle est l’expression de cette fonction
Quelle est la norme à considérer
Equipe AN
Analyse Numérique (AN)
ESPRIT
Notons Λ =
λ0
λ1
6
et ε =
e0
...
ei
...
en
et considérons la fonction
F (Λ) = ||ε||2
2 = e2
0 + · · · + e2
n,
où || . ||2 désigne la norme euclidienne.
Ajuster les points (xi, yi) par une droite au sens des moindres carrés revient à
minimiser la fonction F .
(cid:121)
Trouver le vecteur Λ pour que F
soit minimale
Equipe AN
Analyse Numérique (AN)
ESPRIT
Résolution: "Méthode matricielle"
Le système (S1) peut s’écrire matriciellement comme suit:
7
=
Publicité
e0
...
ei
...
en
(cid:124) (cid:123)(cid:122) (cid:125)
ε
(cid:124)
1 x0
...
...
1 xi
...
...
1 xn
(cid:123)(cid:122)
A
(cid:125)
−
λ0
λ1
(cid:124) (cid:123)(cid:122) (cid:125)
Λ
y0
...
yi
...
yn
(cid:124) (cid:123)(cid:122) (cid:125)
Y
Le vecteur Λ minimisant F vérifie
0
0
∇F (Λ) =
=
(Λ)
(Λ)
∂F
∂λ0
∂F
∂λ1
.
(λ0, λ1) est un point critique de F
Equipe AN
Analyse Numérique (AN)
ESPRIT
8
En calculant ∇F , on trouvera que
∇F (Λ) = 2 tA(A Λ − Y )
⇒ tA(A Λ − Y ) =
⇒ tA A Λ = tA Y.
0
0
D’où
On peut prouver aussi que
Λ = (tA A)−1 tA Y
Λ =
=
λ0
λ1
Y − λ1X
XY −XY
2
X 2−X
,
n
(cid:88)
xi
i=0
n + 1
, Y =
n
(cid:88)
yi
i=0
n + 1
, XY =
n
(cid:88)
xiyi
i=0
n + 1
avec X =
n
(cid:88)
x2
i
i=0
n + 1
.
et X 2 =
Equipe AN
Analyse Numérique (AN)
ESPRIT
Exercice
9
Considérons le tableau de l’exercice donné dans la section Interpolation polynomiale.
xi
yi
x0 = −1
y0 = 2
x1 = 0
y1 = 1
x2 = 1
y2 = −1
Trouver l’équation de la droite qui ajuste au mieux les points (x0, y0), (x1, y1) et
(x2, y2) au sens des moindres carrés.
Equipe AN
Analyse Numérique (AN)
ESPRIT
On a
tA A =
1
1 1
−1 0 1
1
1
1 −1
0
1
=
3 0
0 2
Solution
10
Soit P ∈ R1[X] défini par P (x) = λ0 + λ1x dont la courbe représentative ajuste au
mieux les points (x0, y0), (x1, y1) et (x2, y2) au sens des moindres carrés et A la
matrice donné par
1 x0
1 x1
1 x2
1 −1
=
1
1
.
0
1
A =
Equipe AN
Analyse Numérique (AN)
ESPRIT
Solution
10
Soit P ∈ R1[X] défini par P (x) = λ0 + λ1x dont la courbe représentative ajuste au
mieux les points (x0, y0), (x1, y1) et (x2, y2) au sens des moindres carrés et A la
matrice donné par
1 x0
1 x1
1 x2
1 −1
=
1
1
.
0
1
A =
Publicité
On a
tA A =
1
1 1
−1 0 1
1 −1
1
1
0
1
=
3 0
0 2
Equipe AN
Analyse Numérique (AN)
ESPRIT
Comme (tA A)−1 =
, alors
1
3 0
0 1
2
11
Λ =
λ0
λ1
= (tA A)−1 tA Y
1
3 0
0 1
2
1
1 1
−1 0 1
2
1
−1
1
3
− 1
1
3
1
3
2 0 1
2
2
1
−1
.
2
3
− 3
2
=
=
=
Equipe AN
Analyse Numérique (AN)
ESPRIT
12
Par conséquent,
P (x) =
2
3
−
3
2
x.
Retrouvons le résultat en utilisant la formule des moyennes arithmétiques.
Comme X = 0, Y = 2
3 , XY = −1 et X 2 = 2
3 , alors
λ0
λ1
=
=
Y − λ1X
XY −XY
2
X 2−X
.
2
3
− 3
2
Λ =
D’où le résultat.
Equipe AN
Analyse Numérique (AN)
ESPRIT
Objectif: Déterminer l’expression du polynôme P ∈ Rp[X], défini par
P (X) = λ0 + λ1x + · · · + λpxp,
dont la courbe représentative est la plus proche des points (xi, yi)
au sens des moindres carrés
Approximation (ou régression) polynomiale
13
Soient (n + 1) points (xi, yi), i ∈ {0, 1, · · · , n}, d’abscisses deux à deux distinctes. On
note
X =
, Y =
x0
...
xi
...
xn
.
y0
...
yi
...
yn
Equipe AN
Analyse Numérique (AN)
ESPRIT
Approximation (ou régression) polynomiale
13
Soient (n + 1) points (xi, yi), i ∈ {0, 1, · · · , n}, d’abscisses deux à deux distinctes. On
note
X =
, Y =
x0
...
xi
...
xn
.
y0
...
yi
...
yn
Objectif: Déterminer l’expression du polynôme P ∈ Rp[X], défini par
P (X) = λ0 + λ1x + · · · + λpxp,
dont la courbe représentative est la plus proche des points (xi, yi)
au sens des moindres carrés
Equipe AN
Analyse Numérique (AN)
Publicité
ESPRIT
Le système (S1) peut s’écrire matriciellement comme suit:
1 x0 x2
0
· · · xp
0
λ0
e0
...
...
ei
en
(cid:124) (cid:123)(cid:122) (cid:125)
ε
...
...
(cid:124)
...
i
...
...
...
y0
...
...
yi
yn
(cid:124) (cid:123)(cid:122) (cid:125)
Y
=
1 xi x2
i
· · · xp
λi
−
1 xn x2
n · · · xp
n
λp
(cid:123)(cid:122)
A
(cid:125)
(cid:124) (cid:123)(cid:122) (cid:125)
Λ
Λ = (tA A)−1 tA Y
En appliquant le même raisonnement de l’approximation polynomiale, on aura
14
(Sp)
e0 = P (x0) − y0 = λ0 + λ1x0 + · · · + λpxp
...
ei = P (xi) − yi = λ0 + λ1xi + · · · + λpxp
...
en = P (xn) − yn = λ0 + λ1xn + · · · + λpxp
0 − y0
I − yi
n − yn
Equipe AN
Analyse Numérique (AN)
ESPRIT
14
(Sp)
e0 = P (x0) − y0 = λ0 + λ1x0 + · · · + λpxp
...
ei = P (xi) − yi = λ0 + λ1xi + · · · + λpxp
...
en = P (xn) − yn = λ0 + λ1xn + · · · + λpxp
0 − y0
I − yi
n − yn
Le système (S1) peut s’écrire matriciellement comme suit:
· · · xp
1 x0 x2
0
0
...
...
· · · xp
1 xi x2
i
i
...
...
1 xn x2
n · · · xp
n
(cid:123)(cid:122)
A
En appliquant le même raisonnement de l’approximation polynomiale, on aura
λ0
...
λi
...
λp
(cid:124) (cid:123)(cid:122) (cid:125)
(cid:125)
Λ
y0
...
yi
...
yn
(cid:124) (cid:123)(cid:122) (cid:125)
Y
e0
...
ei
...
en
(cid:124) (cid:123)(cid:122) (cid:125)
ε
−
=
(cid:124)
Equipe AN
Λ = (tA A)−1 tA Y
Analyse Numérique (AN)
Publicité
ESPRIT
Exercice
15
Dans l’exercice précédent,
1 Déterminer le polynôme P ∈ R2[X] qui ajuste au mieux les points (x0, y0), (x1, y1)
et (x2, y2).
2 Que peut-on constater?
Equipe AN
Analyse Numérique (AN)
ESPRIT
On a
1 1
1 −1 1
3 0 2
tA A =
−1 0 1
1
1
1
1
0
1
0
1
0 1
=
0 2 0
2 0 2
Solution
16
1 Soit P ∈ Rp[X] défini par P (x) = λ0 + λ1x + · · · + λpxp dont la courbe
représentative ajuste au mieux les points (x0, y0), (x1, y1) et (x2, y2) au sens des
moindres carrés et A la matrice donné par
A =
1 x0 x2
0
1 x1 x2
1
1 x2 x2
2
1 −1 1
=
1
1
0
1
.
0
1
Equipe AN
Analyse Numérique (AN)
ESPRIT
Solution
16
1 Soit P ∈ Rp[X] défini par P (x) = λ0 + λ1x + · · · + λpxp dont la courbe
représentative ajuste au mieux les points (x0, y0), (x1, y1) et (x2, y2) au sens des
moindres carrés et A la matrice donné par
A =
1 x0 x2
0
1 x1 x2
1
1 x2 x2
2
1 −1 1
=
1
1
0
1
.
0
1
On a
1
1 1
1 −1 1
tA A =
−1 0 1
1
0 1
1
1
0
1
=
0
1
3 0 2
0 2 0
2 0 2
Equipe AN
Analyse Numérique (AN)
ESPRIT
1
0 −1
17
Comme (tA A)−1 =
0
1
2
−1 0
Λ =
λ0
λ1
λ2
, alors
0
3
2
= (tA A)−1 tA Y
1
0 −1
1
1 1
0
3
2
−1 0 1
1
0 1
−1
2
1
=
0
1
2
−1 0
=
.
1
− 3
2
− 1
2
Equipe AN
Analyse Numérique (AN)
ESPRIT
18
Par conséquent,
P (x) = 1 −
3
2
x −
1
2
x2.
2 Le polynôme d’approximation P trouvé est le polynôme qui interpole les points
(x0, y0), (x1, y1) et (x2, y2).
Equipe AN
Analyse Numérique (AN)
ESPRIT