Analyse numérique

1A UE MATH1
Approximation polynomiale des fonctions

G. Chiavassa
 f(x1)
Contexte f(x0)
f(xi) f(xn)

f : [a, b] → ℝ, continue et connue en n+1 points distincts x0, x1, . . . , xn de [a, b]

➡ Objectif : approcher f par un polynôme P a x0 x1 … xi … xn b

f(x1) f(x1) f(x1)

P(x)
f(xi) f(xn) f(xn) f(xi) f(xn)
f(x0) f(xi) P(x) f(x0)
f(x0)
P(x)

a x0 x1 … xi … xn b a x0 x1 … xi … xn b a x0 x1 … xi … xn b
P interpolant P non-interpolant P dé ni par morceaux

• Existence, unicité de P
• Erreur d’approximation, erreur lorsque n →+∞
Questions :
• Choix des xi
• Calcul e ectif de P
fi
ff
Interpolation de Lagrange f(x1)
f(xi) f(xn)
P(x)
f(x0)

P est interpolant, i.e. ∀i = 0,...,n P(xi) = f(xi)

a x0 x1 … xi … xn b
Théorème 1
Il existe un unique polynôme Pn de degré inférieur ou égal à n véri ant la propriété précédente.
Il s’écrit
n n (x − xj)
∑ ∏ (xi − xj)
Pn(x) = f(xi) Li(x) avec Li(x) =
i=0 j=0,j≠i

Pn : polynôme d’interpolation de Lagrange de f aux points xi

Li : polynômes de base (générateurs) de Lagrange

Démonstration

fi
 Interpolation de Lagrange
Exemple : x0 = 0, x1 = 1, x2 = 2

En pratique, calcul et évaluation de Pn : méthode des di érences divisées, formule de Newton, (voir polycopié de cours)

1
f(x) = sin(x), x ∈ [−2π,2π] f(x) = , x ∈ [−2π,2π]
1+x 2

n=3 n=5
n=3 n=5

n=7 n = 10 n=7 n = 10

Programme interpolation_lagrange.m
ff
 Interpolation de Lagrange
Théorème 2
Soit f : [a, b] → ℝ, (n + 1) fois continûment di érentiable et Pn le polynôme de Lagrange aux points x0, x1, . . . , xn ∈ [a, b], alors
n
1
| Πn+1(x) | sup | f (n+1)(x) | avec Πn+1(x) =
∏
| f(x) − Pn(x) | ≤ (x − xi) ,
(n + 1)! a≤x≤b i=0
où de façon équivalente :

1
∥f − Pn∥∞ ≤ ∥Πn+1∥∞ ∥f (n+1)∥∞
(n + 1)!

Remarques
Exemples précédents
• Démonstration : théorème de Rolle (voir poly)
(n+1) • f(x) = sin(x) alors ∥f (n+1)∥∞ ≤ 1
• La convergence dépend donc des limites de Π n+1 et f
e −n (4π)n+1
• Πn+1(x) ne dépend que du choix des points d’interpolation ∥f − Pn∥ ≤ C ⟶ 0 si n → + ∞
e −n
n log n (n + 1)!
segmentation régulière ∥Πn+1∥∞ ≤ C (b − a)n+1
• n log n 1 (n+1)
• f(x) = alors ∥f ∥∞ ≃ (n + 1)!
1+x 2

e −n
Pas de convergence en général ∥f − Pn∥ ≤ C (4π)n+1 ⟶ + ∞ si n → + ∞
Oscillations : phénomène de Runge n log n
ff
 Interpolation de Lagrange
Théorème 3
Soit f : [a, b] → ℝ, continue et Pn le polynôme de Lagrange aux points x0, x1, . . . , xn ∈ [a, b], alors Démo

∥f − Pn∥∞ ≤ (1 + Λn) inf ∥f − q∥∞

deg q≤n
n

∑
avec Λn = ∥ | Li(x) | ∥∞ est la constante de Lebesgue.
i=0

Remarques n=5 n = 10

• n→+∞ ( deg q≤n

lim inf ∥f − q∥ ∞ )
= 0 c’est le théorème de Weierstrass

• Λn ne dépend que des points d’interpolation

• Malheureusement lim Λn = + ∞
n→+∞ n = 15 n = 20
2
• Points de Chebychef quasi-optimaux : Λn ≃ log n
π
1
• Dans ce cas dès que f est C ([a, b]) il y a convergence
Programme interpolation_lagrange.m
 Polynôme de meilleure approximation
f(x)
• n : ensemble des polynômes de degré ≤n
• E : espace vectoriel muni d’une norme ∥.∥E tel que Pn(x)
n⊂E
• f une fonction continue sur [a,b]
a b
➡ Existe-t-il un unique polynôme de n qui minimise la distance de fà n?

Existence: toujours, voir polycopié cours Unicité: deux cas classiques

Théorème 4 : Meilleure approximation uniforme

Si [a, b] est borné, Il existe un unique polynôme Pn ∈ n tel que ∥f − Pn∥∞ = inf ∥f − q∥∞ et lim ∥f − Pn∥∞ = 0
q∈ n n→+∞

Théorème 5 : Meilleure approximation quadratique

b

∫a
E espace de Hilbert muni du produit scalaire < f, g > = f(x)g(x)w(x)dx où w est une fonction poids

∥f∥22,w = < f, f > norme quadratique associée à w

Alors, il existe un unique polynôme Pn ∈ n tel que ∥f − Pn∥2,w = inf ∥f − q∥2,w

q∈ n
𝒫
𝒫
𝒫
𝒫
𝒫
𝒫
𝒫
𝒫
 Polynôme de meilleure approximation
Remarques

• Si ]a, b[ est borné alors lim ∥f − Pn∥2,w = 0

n→+∞

• Le polynôme de meilleure approximation quadratique est la projection orthogonale de f sur n

• On a n = vect{Tk, k = 0,...,n} où les {Tk} sont les polynômes orthogonaux pour le produit scalaire de E et donc
n
< f, Ti >
∑ < Ti, Ti >
Pn = Ti
i=0

• En pratique nécessite le calcul de < f, Ti > par méthodes numériques

• Di cile en général de calculer la meilleure approximation uniforme car L ∞(]a, b[) n’est pas un espace de Hilbert

1
Exemple Approximation de f(x) = par des polynômes de Chebyshev
1+x 2

n=5 n=10 n=20 n=30

Programme approx_chebyshev.m
𝒫
𝒫
ffi
 f(x1)
Méthode des moindres carrés f(xi)
f(xk)
Pn(x)
f(x0)
• k points distincts de [a, b] : x0, x1, . . . , xk
• f une fonction continue sur [a,b]
a x0 x1 … xi … xk b
Théorème 6 :
k
2
∑
Si k + 1 ≥ n + 1 Il existe un unique polynôme Pn ∈ n qui minimise la quantité | f(xi) − Pn(xi) |
i=0

En pratique n << k + 1: régression linéaire (n=1), quadratique (n=2), par exemple

Démonstration

n
Pn(x) = a0 + a1x + . . . + an x et on cherche donc les (aj)j=0,..,n qui minimisent la fonctionnelle
k
n 2
∑
J(a) = | f(xi) − a0 − a1xi − . . . − an xi |
i=0

n+1
Minimisation d’une fonction de ℝ ↦ ℝ : calcul point critique, condition second ordre
𝒫
Méthodes des moindres carrés
Démonstration
Méthodes des moindres carrés
Démonstration
Méthode des moindres carrés 1 3
f(x) = (x + 10x 2 − 5x) ,
600
1 ✴ k = 30 points [xk , f(xk) + ϵk] avec ϵk pertubation aléatoire
f(x) = , k = 100 points [xk , f(xk)]
1 + x2
600 P3(x) = 0.97 x 3 + 9.65 x 2 − 4.84 x + 6.86

n=5 n=10 n=2 ∥f − P2∥ = 0.44 n=3 ∥f − P3∥ = 0.24

n=20 n=30 n=4 ∥f − P4∥ = 0.24 Lagrange n=30

Programme moindre_carres.m
 Approximation polynomiale par morceaux
f(x1)

f : [a, b] → ℝ, continue et connue en k+1 points distincts x0, x1, . . . , xk de [a, b] f(xi) f(xk)
f(x0)
P(x)

Restriction de P sur l’intervalle ]xi−1, xi[ : Pi , est un polynôme

x − xi x − xi−1
a x0 x1 … xi … xk b
Linéaire : Pi(xi−1) = f(xi−1) et Pi(xi) = f(xi) Pi(x) = f(xi−1) + f(xi)
xi−1 − xi xi − xi−1 P dé ni par morceaux

P est continu sur [a, b]

10 points [xi , f(xi)]

Spline cubique : Pi est de degré 3 choisi tel que

Pi(xi−1) = f(xi−1) et Pi(xi) = f(xi)

P′i (xi−1) = P′i−1(xi−1) P′i′(xi−1) = P′i−1
′ (xi−1)

P est de classe C 2 sur [a, b]

5
∥f ∥∞ (max(hi))
(4) 4
∥f − P∥∞ ≤
384
lim ∥f − P∥∞ = 0
k−>+∞

1 (4)
∥f ∥∞ (max(hi))
3
∥f′ − P′∥∞ ≤
24 Programme approx_locale.m








fi
Conclusion
Interpolation de Lagrange Moindres carrés
• Ecriture explicite immédiate du polynôme • Nombre de points élevés, degré faible
• Convergence non assurée • Ecriture explicite non évidente
• Oscillations pour des ordres élevés • Très utilisée en pratique : lois experimentales, solutions de systèmes
• Ordre=nombre de points-1 linéaires, régression en statistique, clustering en IA, etc…
• Utilisation pour des applications théoriques (quadratures par ex.)
ou avec peu de points

Meilleure approximation Approximation locale

• Ecriture explicite du polynôme relativement facile si ordre faible • Nombre de points élevés, degré faible, (3 en général splines)
• Convergence assurée des que l’intervalle est borné • Ecriture explicite di cile : algorithmes numériques
• Cadre théorique : espaces de Hilbert, projection orthogonale • Très utilisée en pratique : lissage de courbes, génération et
• Calcul numérique de la projection non trivial si ordre élevé représentation de surfaces, CAO, Design, etc…
• Utilisation surtout pour des applications théoriques (quadratures,
approximation de solutions d’EDP, etc …) ou avec peu de points
ffi