M315 : Analyse numérique et approximationObjectifsetplandecours 0.1 Objectifs →Approximationdefonctions,courbessurfaces,intégrales. →Déﬁnirenquelsensonconsidèrel’approximation

Université des Sciences et Technologies de LilleU.F.R. de Mathématiques Pures et Appliquées

M315 : Analyse numérique etapproximation

Notes de cours par Clément Boulonne

L3 Mathématiques 2008 - 2009

Table des matières

Objectifs et plan de cours 40.1 Objectifs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40.2 Plan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40.3 Bibliographie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

1 Approximation par des fonctions splines 51.1 Rappel sur l’interpolation polynomiale . . . . . . . . . . . . . . . . . . . . . . . 5

1.1.1 Existence et unicité du polynôme d’interpolation . . . . . . . . . . . . . . 51.1.2 Formule de Lagrange du polynôme d’interpolation . . . . . . . . . . . . . 61.1.3 Base de Newton - Différences divisées . . . . . . . . . . . . . . . . . . . . 61.1.4 Formule de l’erreur d’interpolation . . . . . . . . . . . . . . . . . . . . . 71.1.5 Quelques problèmes d’interpolation polynômiale . . . . . . . . . . . . . . 7

1.2 Fonctions splines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81.3 Splines cubiques interpolants . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91.4 Propriété extremale des splines de degré impair . . . . . . . . . . . . . . . . . . 131.5 La base des B-splines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141.6 Estimation de l’erreur . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 181.7 Courbes splines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

1.7.1 Définitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 221.7.2 Courbe ouverte . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 231.7.3 Courbes fermés périodiques . . . . . . . . . . . . . . . . . . . . . . . . . 261.7.4 Algorithme d’évaluation de De Boor-Cox . . . . . . . . . . . . . . . . . . 28

2 Approximation au sens des moindres carrés 292.1 Meilleure approximation dans un espace normé . . . . . . . . . . . . . . . . . . 29

2.1.1 Premiers résultats . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 292.1.2 Unicité de la meilleure approximation . . . . . . . . . . . . . . . . . . . . 30

2.2 Meilleure approximation dans un espace préhilbertien . . . . . . . . . . . . . . . 312.2.1 Algorithme de Gram-Schmidt . . . . . . . . . . . . . . . . . . . . . . . . 342.2.2 Approximation à une précision donnée . . . . . . . . . . . . . . . . . . . 35

3 Polynômes orthogonaux et formules de quadrature 373.1 Quelques propriétés des polynômes orthogonaux . . . . . . . . . . . . . . . . . . 373.2 Exemples de familles de polynômes orthoognaux . . . . . . . . . . . . . . . . . . 403.3 Formule de quadrature . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41

3.3.1 Formules de quadrature interpolatoire . . . . . . . . . . . . . . . . . . . . 423.3.2 Méthodes composites . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 453.3.3 Formules de quadrature de Gauss . . . . . . . . . . . . . . . . . . . . . . 46

2

3

4 Approximation en norme uniforme 504.1 Réduction de l’erreur d’une approximation . . . . . . . . . . . . . . . . . . . . . 504.2 Caractérisation de la meilleure approximation . . . . . . . . . . . . . . . . . . . 514.3 Algorithme de calcul de Remez (exchange algorithm) . . . . . . . . . . . . . . . 53

Objectifs et plan de cours

0.1 Objectifs→ Approximation de fonctions, courbes surfaces, intégrales.→ Définir en quel sens on considère l’approximation.→ Donner les algorithmes pour construire les approximations.→ Estimation d’erreurs.→ Définir les espaces où on cherche l’approximation.

0.2 Plan1) Approximation de fonctions et de courbes par des fonctions splines (polynomial par mor-

ceaux). Algorithmes de calcul, estimations d’erreurs.2) Meilleure approximation dans l’espace normé, les espaces d’Hilbert, au sens des moindres

carrés.3) Polynômes orthogonaux. Application au calcul d’intégrales.4) Meilleure approximation uniforme (L∞), existence, unicité, caractérisation de la meilleure

approximation. Algorithme de calcul.

0.3 Bibliographie1) Philip J. Davis : Interpolation and Approximation, Dover Publications, 19762) M.J.D Powell : Approximation Theory and Methods, Cambridge University Press, 19813) Jean-Pierre Demailly : Analyse numérique et équations différentielles, Grenoble Sciences,

20064) Carl de Boor : A Practical Guide to Splines

4

Chapitre 1

Approximation par des fonctionssplines

1.1 Rappel sur l’interpolation polynomialeEtant données x0, x1, ..., xn ∈ R distincts et les valeurs f(x0), f(x1), ..., f(xn). Il existe un et

un seul polynôme pn de degré ≤ n tel que :

pn(xi) = f(xi), i = 0, ..., n

1.1.1 Existence et unicité du polynôme d’interpolationOn aura donc :

pn(x) = a0 + a1x+ ...+ anxn

Les conditions d’interpolation se resument par la résolution du système linéaire suivant :1 x0 x2

0 · · · xn01 x1 x2

1 · · · xn1... ... . . .1 xn x2

n · · · xnn

︸︷︷︸

Matrice de Vandermonde

a0a1...an

=

f(x0)f(x1)

...f(xn)

︸︷︷︸

n+1 équations à n+1 inconnus

(∗)

Soit :∆ = detA =

∏0≤j<i≤n

(xj − xi) 6= 0

Cela implique que le système linéaire (∗) a une solution unique.

5

6 Chapitre 1. Approximation par des fonctions splines

1.1.2 Formule de Lagrange du polynôme d’interpolationLa formule de Lagrange du polynôme d’interpolation est la suivante :

pn(x) =n∑j=0

f(xj)lj(x)

avec :lj(x) =

n∏i=0,i 6=j

(x− xi)(xj − xi)

pour j = 0, ..., n

On appelle (l0, ..., ln) la base de Lagrange. Les lj (j = 0, ..., n) suivent la propriété suivante :Propriété 1.1.1. lj(xk) = δjk.

1.1.3 Base de Newton - Différences diviséesNotation. Notons par [x0, x1, ..., xk]f le coefficient dominant du polynôme pk (qui interpole faux points x0, ..., xk), c’est-à-dire :

[x0, ..., xk]f =k∑j=0

xj∏i=0,i 6=j xj − xi

[x0, ..., xk]f est appelé différence d’ordre k de f .Si on considère pk − pk−1, c’est un polynôme de degré ≤ k.

pk(xi)− pk−1(xi) = 0, i = 0, ..., k − 1Le coefficient dominant est [x0, x1, ..., xk]f est :

(pk − pk−1)(x) =k−1∏i=0

(x− xi)[x0, x1, ..., xk]f ⇒ pk(x) = pk+1(x) + [x0, ..., xk]fk−1∏i=0

(x− xi)

Par réccurence :pn(x) = f(x0) +

n∑k=1

([x0, x1, ..., xk]f

k∏i=0

(x− xi))

La formule précédente est appelée la formule de Newton. La base de Newton est la suivante :(x− x0), (x− x0)(x− x1), ..., (x− x0)(x− x1)...(x− xn)

Calcul recursif des différences divisées

[x0]f = f(x0)[x0, x1, ..., xk]f = [x1,...,xk]f−[x0,...,xk−1]f

xk−x0

On a :[xi]f = f(xi)

Démonstration. Voir M206 II-1.5.

pk(x) = (x− x0)qk−1(x)− (x− xk)pk−1(x)xk − x0

qk−1 est le polynôme d’interpolation aux points x1, ..., xk.

Chapitre 1. Approximation par des fonctions splines 7

1.1.4 Formule de l’erreur d’interpolationTheorème 1.1.2. Soient x, x0, ..., xn ∈ [a, b] et f ∈ Cn+1([a, b]). Alors ∃ξx ∈] min(x, xi),max(x, xi)[tel que :

f(x)− pn(x) = 1(n+ 1)!Πn+1(x)f (n+1)(ξx)

avec :Πn+1(x) =

n∏i=0

(x− xi)

Démonstration. Voir M206 II-1.6. Elle est bassée sur le théorème de Rolle.

1.1.5 Quelques problèmes d’interpolation polynômialeL’erreur d’interpolation dépend du choix des abscisses et de la régularité de la fonction.

Exemple 1.1.1. Si on choisit des abscisses équidistribuées dans [a, b], c’est-à-dire :

xj = a+ jh, h = b− an

On peut montrer que :

|f(x)− pn(x)| =≤hn+1

n+ 1 maxx∈[a,b]

|f (n+1)(x)| ≤ ε

→ on obtient de bonnes approximation si f est "suffisament" régulière.Problème. f ∈ C([a, b])\C1([a, b])Exemple 1.1.2. On peut prendre comme abscisses les :

xi = cos( 2i+ 1

2n+ 2π), i = 0, ..., n

Les xi representent les racines des polynômes de Tchebychev1.Un polynôme de degré élevé présent souvent des oscillations qui peuvent provoquer des

erreurs de grand module (phénomène de Runge).Exemple 1.1.3. On considère : f(x) = 1

x2+1 , x ∈ [−1, 1]

1Tn(cos(x)) = cos(nx)


La courbe en rouge représente la fonction f(x), la courbe bleue est le polynôme interpolateurde degré 5 et la courbe verte est le polynôme interpolateur de degré 9. L’approximation est deplus en plus mauvaise.

Donc : pour une fonction regulière et des points équidistants, |f(x)−pn(x)| ne converge pasvers 0 et n’est pas bornée pour certains x.

Pour remédier à ce type de problème, on va chercher l’approximation dans une autre classede fonctions : fonctions splines.

On considère une partition de l’intervalle [a, b] :

a = t0 < t1 < ... < tn = b

et on va construire s telle que :• ∀j ∈ 1, ..., n, sj = s|[lj ,lj+1] ∈ Pk (espace des polynômes de degré ≤ k).• s ∈ Cm([a, b]) pour m le plus grand possible.

s1(x) =k∑j=0

aj(x− t1)j, aj = s(j)1 (t1)j! = s(j)(t−1 )

j!

s2(x) =k∑j=0

bj(x− t1)j, bj = s(j)2 (t1)j! = s(j)(t+1 )

j!

Pour avoir une régularité Cm :• s(j)(t1) = s(j)(t+1 ), j = 0, ...,m• aj = bj, j = 0, ...,m.• Si m > k ⇒ s est un polynôme de degré ≤ k. On doit avoir m < k. Donc on va considérerm = k.

1.2 Fonctions splinesDéfinition 1.2.1. n, k des entiers ≥ 1, t0 < t1 < ... < tn noeuds de la subdivision. On considèreSk = Sk(t0, t1, ..., tn) l’espace des fonctions s : [t0, tn]→ R de classe Ck−1([t0, tn]) et telles que :

s|[tj−1,tj ] ∈ Pk, j = 1, ..., n

est un espace vectoriel (sous-espace vectoriel de Ck−1([a, b])).

Lemme 1.2.1. On considère les n+ k fonctions suivantes :pj(x) = (x− t0)j, j = 0, ..., k

ϕj(x) = (x− tj)k+ =

(x− tj)k si x ≥ tj

0 si x < tj, j = 1, .., n− 1

{pj}j=0,...,k ∪ {ϕj}j=1,...,n forment une base Sk(t0, ..., tn) et donc dim(Sk) = n+ k.

∀s ∈ Sk, s(x) =k∑j=0

ajpj(x) +n−1∑j=1

bjϕj(x)

avec :aj = s(j)(t+0 )

j! et bj =s(k)(t+j )− s(k)(t−j )

k!


Démonstration. Les fonctions appartiennent à Sk :(i) évident pour pj(ii) ϕ(l)

j (t−j ) = 0, ∀l, ϕ(l)j (t+j ) = 0, ∀l ≤ k − 1 et ϕ(k−1)

j (t+j ) = k!.Il suffit de montrer que : ∀s ∈ Sk, ∃!a0, ..., ak, b1, ..., bn−1 tel que :

s =k∑j=0

ajpj +n−1∑j=1

bjϕj

On procède par réccurence sur n. Pour n = 1, Sk(t0, t1) = {p|[t0,t1], p ∈ Pk}. {p0, ..., pk} est labase de Taylor. Supposons vrai pour n − 1. Soit s ∈ Sk(t0, ..., tn), s|[t0,tn−1] ∈ Sk(t0, ..., tn−1) etpar réccurence :

∃!a0, ..., ak, b1, ...bn−2, s|[t0,tn−1] = s(x) =k∑j=0

ajpj(x) +n−2∑j=1

bjϕj(x)

Au voisinage de tn−1, s et ϕn−1 ∈ Ck−1 et s ∈ Ck. ∀b ∈ R, ∀l = 0, ..., k − 1, on considère :(s− s− bϕn−1)(l).

(t+n−1) = (s− s)(l)(t−n−1) = 0l = k :

(s− s− bϕn−1)(k)(t+n−1) = s(k)(t+n−1)− s(k)(t+n−1)− bk! (1.1)= s(k)(t+n−1)− s(k)(t−n−1)− bk! (1.2)= s(k)(t+n−1)− s(k)(t−n−1)− bk! (1.3)

Le passage de (1.1) à (1.2) s’explique par s ∈ Ck et (1.2)→ (1.3) par s = s|[t0,tn−1].Sur [tn−1, tn], p = s− s− bϕn−1 est un polynôme de degré k tel que :p(l)(t+n−1) = 0, l = 0, ..., k − 1

p(k)(t+n−1) = 0 pour b = bn−1

avec :bn−1 = s(k)(t−n−1s

(k)(t−n−1)k!

bn−1 est choisi tel que (1.3) = 0. Donc :

p = 0⇔ s(x) = s(x) + bn−1ϕn−1(x), x ∈ [tn−1, tn]

Vrai pour [t0, tn].

1.3 Splines cubiques interpolantsOn considère le cas où k = 3.

Theorème 1.3.1. Pour toute fonction f , il existe s ∈ S3(t0, ..., tn) vérifiant les conditionsd’interpolation.

s(ti) = f(ti), i = 0, ..., nDe plus, s est unique si on impose :

(a) les valeurs de s′′(t0) et s′′(tn)


ou(b) les valeurs s′(t0) et s′(tn).

Si de plus, f ∈ C2([a, b]) et si :(a∗) s′′(t0)− s′′(tn) = 0, splines naturelles.

ou(b∗) s′(t0) = f ′(t0) et s′(tn) = f ′(tn),

Alors :‖s′′‖L∞([a,b]) = max

[a,b]|s′′(x)| ≤ 3‖f ′′‖L∞([a,b])

Remarque. dimS3(t0, ..., tn) = n+3. On a n+1 conditions d’interpolation et 2 autres conditions((a) et (b)).

Démonstration pour le cas (a). On note sj = s(tj) = f(tj) = fj (pour j = 0, ..., n). On noteaussi s′′j = s′′(tj) et ∆tj = tj+1 − tj. comme s ∈ S3 alors s ∈ C2 et donc s′′ est linéaire parmorceaux. Donc pour x ∈ [tj, tj+1],

s′′(x) = s′′jtj+1 − xtj+1 − tj

+ s′′j+1x− tjtj+1 − tj

Si on intégre deux fois la fonction s′′ :

s′(x) = −s′′j(tj+1 − x)2

2∆tj+ s′′j+1

(x− tj)2

2∆tj+ αj (1.4)

s(x) = s′′j(tj+1 − x)3

6∆tj+ s′′j+1

(x− tj)3

6∆tj+ αj(x− tj) + βj

Ici, on a utilisé que s est un polynôme de degré 3 par morceaux et que s ∈ C2. On utilise ensuiteles conditions d’interpolation : sj = fj et la continuité :

fj = s′′j∆t2j6 + βj (1.5)

fj+1 = s′′j+1∆t2j6 + αj∆tj + βj (1.6)

De (1.5), on détermine les βj et de (1.6), les αj. Reste à imposer que :

s′(t+j ) = s′(t−j ), j = 1, ..., n− 1 (1.7)

Pour calculer s′(t−j ), on considère (1.4) sur l’intervalle [tj−1, tj] et s′(t+j ), on considère (1.4) surl’intervalle [tj, tj+1].

s′(t+j ) = −s′′j∆tj2 + αj (1.8)

On fait (1.5)− (1.6) qu’on diviser par ∆tj :

fj+1 − fj∆tj

= [tj, tj+1]f − s′′j+1∆tj6 − s′′j

∆tj6 + αj

Rappel. [tj, tj+1]f est la différence divisée au points tj, tj+1 de f .


Donc (1.8) devient :

s′(t+j ) = −s′′j∆tj2 − s′′j+1

∆tj6 + s′′j

∆tj6 + [tj, tj+1]f

Pour s′(t−j ) :

s′(t−j ) = s′′j∆tj−1

2 + αj−1 = s′′j∆tj−1

2 − s′′j∆tj−1

6 − s′′j−1∆tj−1

6 + [tj−1, tj]f

Donc (1.7) s’écrit :

∆tj−1

6 s′′j−1 + ∆tj−1 + ∆tj3 s′′j + ∆tj

6 s′′j+1 = [tj, tj+1]f − [tj−1, tj]f

12

∆tj−1

∆tj−1 + ∆tj︸︷︷︸1−γj

s′′j−1 + s′′j + 12

∆tj∆tj+1 + ∆tj︸︷︷︸

γj

s′′j+1 = 3[tj−1, tj, tj+1]f

12(1− γj)s′′j−1 + s′′j + 1

2γjs′′j+1 = 3[tj−1, tj, tj+1], j = 1, ..., n− 1

On a fixé s′′0 et s′′n. On a alors à résoudre AX = Y :

1 1

2γ112(1− γ2) 1 1

2γ2. . . . . . . . .

12(1− γn) 1

s′′1s′′2...

s′′n−1

=

3[t0, t1, t2]f − 12(1− γ1)s′′0

3[t1, t2, t3]f...

3[tn−3, tn−2, tn−1]f3[tn−2, tn−1, tn]f − 1

2γns′′n

Il reste à montrer que A inversible, Y = 0⇒ X = 0. Soit :

|xp| = ‖X‖∞ = max1≤j≤n

|xj|, 1 ≤ p ≤ n− 1

≤∣∣∣∣1− γp2 xp−1 + xp + γp

2 xp+1

∣∣∣∣ = |yp|‖x‖∞ = |xp| ≤ |yp|+

1− γp2 |xp+1|+

γp2 |xp| ≤ ‖y‖∞ + 1

2‖x‖∞

‖x‖∞2 ≤ ‖y‖∞ ⇔ ‖x‖∞ ≤ 2‖y‖∞

⇒ (y = 0⇒ x = 0)⇒ A inversible ⇒ solution unique.

‖s′′‖L∞[t0,tn] ≤ max0≤j≤n−1

maxx∈[tj ,tj+1]

|s′′j |∣∣∣∣∣tj+1 − x

∆tj

∣∣∣∣∣+ |s′′j+1|∣∣∣∣∣x− tj∆tj

∣∣∣∣∣≤ max

1≤j≤n|s′′j | = ‖x‖∞ ≤ 2‖y‖∞

‖y‖∞ = 3 max1≤j≤n−1

|[tj−1, tj, tj+1]f︸︷︷︸f ′′(ξj)

2 car f∈C2

≤ 32‖f

′′‖L∞[t0,tn]


Corollaire. Soit sn(f) le spline cubique interpolant :

s′(t0) = f ′(t0), s′(tn) = f ′(tn)

Alors f ∈ C2([t0, tn]), on a :

‖f − sn(f)‖L∞[tj ,tj+1] ≤12(∆tj) inf

σ∈S1(t0,...,tn)‖f ′′ − σ‖L∞[t0,tn]

et si f ∈ C4([t0, tn]) :

‖f − sn(f)‖L∞ ≤116 max

js(tj)4‖f (4)‖L∞([t0,tn]) ≤ ε

Démonstration. σ ∈ S3(t0, t1, ..., tn), σ + sn(f) ∈ Sn et vérifie les conditions d’interpolationpour σ + f . Par unicité de la spline cubique interpolante :

sn(σ + f) = σ + sn(f)

Soit g ∈ C2([tj, tj+1]) et on considère le polynôme de degré 1, qui interpole g aux points tj, tj+1et l’erreur d’interpoltaion vérifie :

maxx∈[tj ,tj+1]

∣∣∣∣∣g(x)− g(tj+1)x− tjtj+1 − tj

− g(tj)x− tj+1

tj − tj+1

∣∣∣∣∣ ≤ 12 maxξ∈[tj ,tj+1]

|g′′(ξ)| max[tj ,tj+1]

|(x−tj)(x−tj+1)| ≤(∆tj)2

8 ‖g′′‖L∞(1.9)

On applique ce résultat à :

g(x) = f(x)− sn(f)(x) = (f + σ − sn(f + σ))(x), g(tj)− g(j+1) = 0

‖g‖L∞([tj ,tj+1] = ‖f − sn(f)‖L∞([tj ,tj+1] ≤(∆tj)2

8 infσ∈S3‖f ′′ + σ′′ − sn(f + σ)′′‖L∞

En appliquant le résultat du Théorème 1.3.1..

‖s′′n(f + σ)‖L∞([t0,tn]) ≤ 3‖(f + σ)′′‖L∞([t0,tn])

Donc :‖g‖L∞([t0,tn]) ≤

12[∆tj)2 inf

σ∈S3‖f ′′ + σ′′‖

On applique maintenant (1.9) à la fonction g = f ′′ (∈ C2) et on prend σ ∈ S3 interpole auxpoints ti.

‖f ′′ − σ‖L∞[tj ,tj+1] ≤(∆ti)2

8 ‖f (4)‖L∞[tj ,tj+1]

‖f ′′ − σ‖L∞[t0,tn] ≤18 max(∆tj)2‖f (4)‖L∞([t0,tn]

‖f − sn(f)‖L∞[t0,tn] ≤116 max

j(∆tj)4‖f (4)‖l∞[t0,tn]


1.4 Propriété extremale des splines de degré impairSoient a = t0 < t1 < ... < tn = b et 1 ≤ k ≤ n− 1 :

Définition 1.4.1. s ∈ S2k−1(t0, t1, ..., tn) est dite spline naturelle si ∀l = k, k + 1, ..., 2k − 2 :

s(l)(a) = s(l)(b) = 0 (2k − 2 conditions)

Une fonction g est dite interpolante de f si et seulement si g(tj) = f(tj), j = 0, ..., n.

Theorème 1.4.1 (Théorème de minimisation). Il existe une unique spline naturelle interpo-lante s ∈ S2k−1. De plus, pour toute fonction g ∈ Ck([a, b]) interpolante, on a :

‖g(k)‖L2([a,b]) ≥ ‖s(k)‖L2([a,b])

avec égalité g = 0.

Remarque. • Pour k = 2, on obtient avec une autre caractérisation des splines naturellesinterpolnates.

– dimS2k−1(t0, ..., tn) = n+ 2k− 1, le sous-espace des splines naturelles reste de dimensionm ≥ n+ 1.

Lemme 1.4.2. Soient s spline naturelle d’interpolation et g ∈ Ck([a, b]) une fonction d’inter-polation. Alors :

I =∫ b

as(k)(x)(g(k)(x)− s(k)(x))dx = 0

Démonstration. Intégration par parites (s ∈ C2k+1) k − 1 fois :

I =[s(k)(x)(g − s)(k+1)(x)

]ba−∫ b

as(k−1)(x)[(g − s)(k−1)(x))dx

= ...

=k−2∑j=0

(−1)j[s(k+j)(x)(g − s)(k−1−j)(x)

]ba︸︷︷︸

=0

+(−1)k−1∫ b

as(2k−1)(x)(g′(x)− s′(x))dx

= (−1)k−1n−1∑j=0

ej

∫ tj+1

tj(g′(x)− s′(x))dx

= (−1)k−1n−1∑j=0

ej

[g(x)− f(x)

]tj+1

tj︸︷︷︸=0

Démonstration du Théorème 1.4.1. Soit {b1, b2, ..., bn+2k−1} base S2k−1. Donc :

s(x) =n+2k−1∑i=1

αibi(x)

Les combinaisons de spline naturelle s’écrit :

s(l)(a) =n+2k−1∑i=1

αib(l)i (a) = 0, l = k, ..., 2k − 2 (1.10)


s(l)(b) =n+2k−1∑i=1

αib(l)i (b) = 0, l = k, ..., 2k − 2 (1.11)

Les conditions d’interpolations :

s(tj) =n+2k−1∑i=1

αibi(tj) = f(tj), j = 0, ...n (1.12)

(1.10), (1.11) et (1.12) forment un système linéaires de 2k + n − 1 équations et 2k + n − 1inconnues.

Aα = c, A ∈M(2k+n−1)(2k+n−1), c =

0...0

f(t0)...

f(tn)

Il suffit de démonter que A est inversible et donc il suffit de montrer c = 0 ⇒ α = 0 pourconclure l’existence et l’unicité. Soit f = 0 ⇒ c = 0. On va utiliser le Lemme 1.4.2. avecg = 0 (interpolante). ∫ b

a(s(k)(x))2dx = 0⇒ s(k) = 0

s est un polynôme de degré k − 1 aec n+ 1 zéros aux points ti ⇒ s = 0.

Propriété 1.4.3 (Propriété de minimalité).∫ b

ag(k)(x)2dx−

∫ b

as(k)(x)2dx =

∫ b

a(g(k) − s(k))(x)︸︷︷︸

≥0

+2∫ b

as(k)(x)f (k)(x)dx− 2

∫ b

as(k)(x)dx

≥ −2∫ b

as(k)(x)(s(k)(x)− g(k)(x))︸︷︷︸

=0

dx

⇒ ‖g(k)‖L2[a,b] =(∫ b

ag(x)2dx

)1/2

≥(∫ b

as(k)(x)dx

)1/2

︸︷︷︸‖s(k)‖L2

On a égalité si et seulement si :∫ b

a(g(k) − s(k))2(x)dx = 0

g(k) − s(k)|[a,b] = 0⇒ g − s ∈ Pk−1 s’annule en n+ 1 points ⇒ g = s.

1.5 La base des B-splines– fonctions positives "localisés" support compact (non nulles dans un petit nombre de sousintervalles).


Définition 1.5.1. Etant donnés ... < t0 < t1 < ... < tn < .... On définit réccursivement :N0j (x) =

1 sur [tj, tj+1]0 sinon

Nkj (x) = x− tj

tj+k − tjNk−1j (x) + tj+k+1 − x

tj+k+1 − tj+1Nk−1j+1 (x)

Considérons le cas particulier des noeuds équidistants :

∀j, tj = t0 + jh

et on note Nk = Nk0 la B-spline pour tj = j. Aolors :

Nkj (x) = Nk

(x− tjh

)

Exemple 1.5.1.

N10 (x) = xN0

0 (x)− (1− x)N01 (x) =

x si x ∈ [0, 1]2− x si x ∈ [1, 2]

et ;

N20 (x) = x

2N10 (x) + 3− x

2 N11 (x)

avec :

N11 =

x− 1 si x ∈ [1, 2]3− x si x ∈ [2, 3]

Donc :

N20 (x) =

x2

2 si x ∈ [0, 1]−x2 + 3x− 3/2 si x ∈ [1, 2](3−x)2

2 si x ∈ [2, 3]


Theorème 1.5.1 (Propriété des B-Splines). a) ∀x ∈ [tj, tj+k+1[, Nkj (x) > 0 et ∀x 6∈ [tj, tj+k+1[,

Nkj (x) = 0, c’est-à-dire supp(Nk

j ) = [tj, tj+k+1].

b)∑j∈Z

Nkj (x) = 1 et pour x ∈ [tr, tr+1],

k∑j=r−k

Nkj (x) = 1 (k + 1 splines naturelles).

c) On note Df = f ′. Pour k ≥ 1, x 6∈ {ti} :

DNkj (x) = k

(Nk−1j (x)

tj+k − tj−

Nk−1j+1 (x)

tj+k+1 − tj+1

)

d) Nkj |[t0,tn] ∈ Sk([t0, tn])

Démonstration. a) k = 0, trivial.

Nkj (x) = x− tj

tj+k − tj︸︷︷︸>0

Nk−1j (x)︸︷︷︸

=0 si x 6∈|tj ,tj+k[

+ tj+k+1 − xtj+k+1 − tj+1︸︷︷︸

>0

Nk−1j+1 (x)︸︷︷︸

=0 si x∈[tj+1,tj+k+1[

Nkj (x) > 0, ∀x ∈ [tj, tj+k+1[

b) Soit x ∈ [tr, tr+1[, ∀j tel que j + k + 1 ≤ r (⇔ j ≤ r − k + 1) ⇒ Nkj (r) = 0 et ∀j tel que

j ≥ r + 1⇒ Nkj (x) = 0. Donc :

∑j∈Z

Nkj (x) =

r∑j=r−k

Nkj (x)

=∑j

x− tjtj+k − tj

Nk−1j (x) +

∑j

tj+k+1 − xtj+k+1 − tj+1

Nk−1j+1 (x)

=∑j

x− tjtj+k − tj

Nk−1j (x) +

∑j

tj+k − xtj+k − tj

Nk−1j

=∑j

Nk−1j (x) = 1


c) k = 1, x ∈ [tj, tj+1[, N1j (x) = x− tj

tj+1 − tj⇒ DN1

j =N0j (x)

tj+1 − tjet x ∈]tj+1, tj+2[, N1

j (x) =

tj+2 − xtj+2 − tj+1

⇒ DN1j = N j+1

0 (x)tj+2 − tj−1

.

DN1j (x) =

N0j (x)

tj+1 − tj−

N0j (x)

tj+2 − tj+1pour x ∈]tj, tj+2[

On peut montrer par reccurence que ;

DNkj (x) =

Nk−1j (x)

tj+k − tj+ x− tjtj+k − tj

DNk+1j (x)−

Nk−1j+1 (x)

tj+k+1 − tj+1+ tj+k+1 − xtj+k+1 − tj+1

DNk−1j+1 (x)

d) Par la Définition 1.5.1, Nkj ∈ C(R), k ≥ 1.

1) Régularité : Nkj ∈ Ck−1(R) ? Si on applique c), on obtient ∀k ≥ 2, Nk

j ∈ C1(R).Reccurence : si ∀k ≥ l, Nk

j ∈ Ck−1(R), ∀k ≥ l + 1, D(Nkj ) ∈ Cl−1(R)⇒ Nk

j ∈ Cl(R).2)

Nkj (x) = x− tj

tj+k − tjNk−1j (x)︸︷︷︸∈Pk−1

− tj+k+1 − xtj+k+1 − tj+1

Nk−1j+1 (x)︸︷︷︸∈Pk−1

Cela implique que Nkj |[tr,tr+1[ ∈ Pk.

On va proposer une nouvelle base pour Sk(t0, t1, ..., tn). Pour j = −k,−k + 1, ..., 0, ..., n, lesB-Splines Nk

j sont non nulles dans [a, b] et Nkj ∈ Sk(t0, ..., tn).

Theorème 1.5.2. Soient :

t−k < t−k+1 < ... < t−1︸︷︷︸quelconque

< t0 < t1 < ... < tn < tn+1 < ... < tn+k︸︷︷︸quelconque

Alors {Nkj }n−1

j=−k forment une base de Sk(t0, t1, ..., tn)

Démonstration. Par réccurence qu’elles sont linéairement indépendantes.

k = 0, x ∈ [tl, tl+1[,n−1∑j=0

ajN0j (x) = 0⇔ al = 0

Suppsons pour k − 1 :n−1∑l=−k

alNkl = 0⇒

n−1∑l=−k

alDNkl (x) = 0⇒

n∑l=−k

alk

(Nk−1l (x)

tl+k − tl−

Nk−1l+1 (x)

tl+k+1 − tl+1

)= 0

Nk−1−k |[tO,tn] ≡ 0, Nk−1

n |[t0,tn] ≡ 0


n−1∑l=−k+1

alkNk−1l (x)

tl+k − tl−

n−2∑l=−k

alkNk−1l+1 (x)

tl+k+1 − tl+1= 0⇒ k

n+1∑j=−k+1

(al − al−1)Nk−1l (x)

tl+k − tl= 0

Par hypothèse de reccurence, al = al−1 pour l = −k+1, ..., n+1⇔ an−1 = an−2 = ... = a−k = a.n−1∑l=−k

aNkl (x) = 0⇔ a

n−1∑l=−k

Nkl (x)︸︷︷︸

=1

= 0⇔ a = 0

Donc al = 0, l = −k, ..., n− 1.

Avantages.• Si on dispose :

s(x) =∑j

γjNkj (x) ≈approx s(x) =

∑j

γjNkj (x)

avec |γj − γj| < ε. Alors :

|s(x)− s(x)| ≤∑j

|γj − γj|Nkj (x) ≤ ε

∑Nkj (x) ≤ ε

On a stabilité numérique (petite perturbation des coefficients ⇒ petites variations de lavaleurs de la spline).• Si on perturbe un coefficient de :

s(x) =n−1∑j=−k

γjNkj (x)

alors on change s que dans un petit intervalle :

s(x) =n−1∑j=−k

γjNkj avec

γj = γj, j 6= l

γl 6= γl

|s(x)− s(x)| = |γl − γl|Nkl (x) 6= 0, x ∈ [tl, tl+k+1]

• A = (Nkj (xk)j,l) forme une matrice creuse.

1.6 Estimation de l’erreurOn se donne k ≥ 0 et n ≥ 1 et on se donne des abscisses :

t−k < t−k+1 < ... < t−1 < t0 < t1 < ... < tn < tn+1 < ... < tn+k

On a a = t0, b = tn, h = max(tj+1 − tj), Sk = Sk(t0, ..., tn). On va étudier l’erreur d’approxi-mation d’une fonction f ∈ Cn([a, b]) par une fonction.Notation. On note :• ‖f‖ = max

x∈[a,b]|f(x)|

• ω(f, σ) = max{|f(x)− f(y), (x, y) ∈ [a, b], |x− y| < σ} (module de continuité)• d(f,Sk) = inf

s∈Sk‖f − s‖

Theorème 1.6.1 (Théorème de meilleure approximation). a) Pour f ∈ C0([a, b]), d(f,Sk) ≤ω(f, (k + 1)h/2).


b) Pour f ∈ C1([a, b]), d(f,Sk) ≤ (k + 1)h2‖f′‖.

c) Pour f ∈ Ck+1([a, b]), d(f,Sk) ≤ (k + 1)!(h2

)k+1‖f (k+1)‖.

Démonstration. Soit xj l’élément le plus proche de tj+tj+k+12 dans [a, b].

– Si tj+tj+k+12 ∈ [a, b] alors xj = tj+tj+k+1

2 ,– Si tj+tj+k+1

2 > b alors xj = b,– Si tj+tj+k+1

2 < a alors xj = a.

⇒ ∀x ∈ [tj, tj+k+1] ∩ [a, b], on a :

|x− xj| ≤tj+k+1 − tj

2 = 12

k∑l=0

(tj+l+1 − tj+l)︸︷︷︸≤h

≤ (k + 1)h2︸︷︷︸ε

a) Soit f ∈ C0([a, b]) et on considère l’élément de Sk :

S(f)(x) =n−1∑j=−k

f(xj)Nkj (x)

où– x ∈ [tk, tk+1] ∩ [a, b]– {Nk

j }n−1j=−k base de Sk.

alors :

|f(x)− S(f)(x)| =

∣∣∣∣∣∣∣∣∣∣∣f(x)

n−1∑j=−k

Nkj (x)

︸︷︷︸=1

−n−1∑j=−k

f(xj)Nkj (x)

∣∣∣∣∣∣∣∣∣∣∣=

∣∣∣∣∣∣∣∣n−1∑j=−k

(f(x)− f(xj))︸︷︷︸≤ω(f,ε)

Nkj (x)

∣∣∣∣∣∣∣∣≤ ω(f, ε)

∣∣∣∣∣∣∣j = −kn−1Nkj (x)︸︷︷︸

=1

∣∣∣∣∣∣∣ = ω(f, ε)

∀x ∈ [a, b], |f(x)− S(f)(x)| ≤ ω(f, ε)→ d(f,Sk) ≤ ‖f − S(f)‖ ≤ ω(f, ε).b) D’après l’inégalité des accroissements finis, ∃ξj ∈] min(x, xj),max(x, xj)[ tel que :

|f(x)− f(xj)| = |f ′(ξj)||x− xj| ≤ ‖f ′‖ε⇒ d(f,Sk) ≤ ‖f ′‖ε

c) Par réccurence sur k• k = 0, voir cas b).


• Supposons la propriété vraie pour k = 1 et montrons le résultat pour k. Soit f ∈Ck+1([a, b]) alors g = f ′ ∈ Ck([a, b]). Alors par l’hypothèse de réccurence :

∃σ ∈ Sk−1, ‖g − σ‖ ≤ k!(h

2

)k‖g(k)‖ (1.13)

On pose :f(x) =

∫ x

af ′(s)ds = f(x)− f(a) (f = f − f(a))

σ(x) =∫ x

aσ(s)ds⇒ σ′ = σ ∈ Sk−1 ⇒ σ ∈ Sk

Donc :

d(f,Sk) = d(f − f(a),Sk) = d(f − σ,Sk)b)= (k + 1)h2‖(f − σ)′‖

= (k + 1)h2‖ f′︸︷︷︸g

−σ‖ = (k + 1)h2‖g − σ‖

(1.13)= (k + 1)h2k!(k

2

)k‖f (k+1)‖

= (k + 1)!(h

2

)k+1

‖f (k+1)‖

Remarque. Si n = 1 alors Sk = Pk et on obtient une borne supérieure pour la distance :

d(f,Pk) ≤(b− a

2

)k+1

(k + 1)!‖f (k+1)‖

Mais cette borne n’est pas suffisament fine.

Theorème 1.6.2. Soit f ∈ Ck+1([a, b]) :

d(f,Sk) ≤ 2(b− a

2

)k+1 ‖f (k+1)‖(k + 1)!

obtenue par le polynôme d’interpolation aux abscisses de Tchebychev.

On considère l’opérateur linéaire :

S : C0([a, b]) → C0([a, b])f 7→ S(f)

où :S(f)(x) =

n∑j=−k

aj(f)Nkj (x) (1.14)

avec :aj : C0([a, b]) → R

f 7→ aj(f)


tel que aj linéaire (∀λ, µ ∈ R, ∀f, g ∈ C0([a, b]), aj(λf + µg) = λaj(f) + µaj(g)) et :

aj = f(xj) =∑i∈I

(xi) (coefficient d’une spline d’interpolation)

On définit la norme de l’opérateur S, ‖S‖, comme la plus petite constante L tel que :

‖S(f)‖ ≤ L‖f‖, ∀f ∈ C0([a, b])

Lemme 1.6.3 (Lemme de Céa). Soit S définit par (1.14) et E un sous-espace vectoriel invariantde C0([a, b]), c’est-à-dire ∀g ∈ E, S(g) = g. Alors :

‖f − S(f)‖ ≤ (1− ‖S‖)d(f, E)

Démonstration. ∀g ∈ E , ‖f − S(f)‖ = ‖f − g + g − S(f)‖. On utilise le fait que S est linéaireet S(g) = g.

‖f − g + g − S(f)‖ = ‖f − g − S(f − g)‖≤ ‖f − g‖+ ‖S(f − g)‖= (1 + ‖S‖)‖f − g‖

⇒ ‖f − S(f)‖ ≤ (1 + ‖S‖)d(f, E).Exemple 1.6.1. Considérons le cas d’une spline interpolante. On se donne n+ k points d’in-terpolation distincts :

a ≤ x−k ≤ x−k+1 ≤ ... ≤ xn−1 ≤ b

(pas nécessairement les noeuds de la spline). Si on veut déterminer Sik(f) ∈ Sk tel que :

Sik(f)(xj) = f(xj), j = −k, ..., n− 1

On a :Sik(f) =

n−1∑j=−k

aj(f)Nkj

Sik(f)(x) =n−1∑j=−k

aj(f)Nkj (xl) = f(xl), l = −k, ..., n− 1

On définit :

b =

f(x−k)

...f(xn−1)

, A =(Nkj (xl)

)j,l

On rappelle que A est une matrice creuse (propriété des B-splines). On a donc à résoudre lesystème linéaire suivant :

A

a−k(l)

...an−1(l)

= b

Si A est inversible (bon choix des abscisses) alors on a :a−k(l)

...an−1(l)

= A−1b⇒ linéarité des aj

Or : ∀g ∈ Sk, Sik(g) = g donc E = Sk. On utilise le lemme de Céa :

‖f − Sik(f)‖ ≤ (1 + ‖Sik‖)d(f,Sk) (théorème de meilleure approximation)


Cas particulier. k = 1. On pose xl = tl+1 :

Nkj (xl) = N1

j (tl+1) = δj,l ⇒ A = In

alors :

Si1(f)(x)n−1∑j=1

f(tl+1)N1j (x)⇒ |Si1(x)| ≤ max

l|f(tl+1)|

∑j

N1j (x)︸︷︷︸

= 1 ≤ ‖f‖

Donc :‖Si1(f)‖ ≤ ‖f‖ ⇒ ‖Si1(f)‖ = 1

Donc :‖f − Si1(f)‖ ≤ (1 + ‖Si1(f)‖︸︷︷︸

=1

)d(f,Sk) = 2 d(f,Sk)︸︷︷︸≤‖f−Sj1(f)‖

⇒ ‖f − Si1(f)‖ ≤ 2d(f,Sk) ≤ 2‖f − Si1(f)‖

⇒ 12‖f − S

i1(f)‖ ≤ d(f,Sk) ≤ ‖f − Si1(f)‖

Donc la spline interpolante est la meilleure approximation à un facteur 2 près.

1.7 Courbes splines

1.7.1 DéfinitionsDéfinition 1.7.1. Etant donnés des points {pi}i∈I du plan ou de l’espace. Une courbe splined’ordre k est une combinaison linéaire des points pi dont les coefficients sont des B-splines.

Sk(t) =∑i∈I

piNki (t), t ∈ [inf

i∈I(ti), sup

i∈I(ti)]

La ligne brisée joignant ces points s’appelle le polygône spline ou le S-polygône.

Sk(t) est dans l’enveloppe connexe des points pi, i = r − k, ..., r pour t ∈ [tr, tr+1] :

Sk(t) =r∑

i=r−kpiN

ki (t)


1.7.2 Courbe ouverte

On choisit un intervalle [a, b] pour le paramètre t. Si on n+k sommets pi dans le S-polygône,on souhaite construire une courbe d’extrémités p1 et pn+k tel que :

Sk(a) = p1 et Sk(b) = pn+k

On va diviser l’intervalle [a, b] en n sous-intervalles et prendre k + 1 noeuds confondus en a eten b :

t1 = ... = tk = tk+1︸︷︷︸k+1 noeuds

= a < tk+2 < ... < tn+k < b = tn+k+1 = tn+k+2 = ... = tn+2k+1︸︷︷︸k+1 noeuds

(1.15)

Splines quadratiques avec noeuds confondus

On rappelle :

Nki (x) = x− ti

ti+k − tiNk−1i (x) + ti+k+1 − x

ti+k+1 − ti+1Nk−1i+1 (x)

Mais si ti+k = ti, la formule précédente n’est plus valable. On va ainsi mettre x−titi+k−ti

"encontribution 0".

Si on confond l points, on perd l − 1 degrés de régularité dans la B-spline.


Revenons à la construction de la courbe ouverte.

Proposition 1.7.1. Avec les notations (1.15), on peut construire les B-splines {Nki }n+k

i=1

Sk(t) =m+k∑i=1

piNki

C’est une courbe spline telle que Sk(a) = p1 et Sk(b) = pn+k.

Démonstration. En a = tk+1, les seuls splines non nulles sont Nk1 , ..., N

kk . Si i noeuds coincident

en un point, on a une continuité k− i. Donc pour j = 2, ..., k + 1, k + 2− j noeuds coincident.On a donc une continuité de j − 2 mais au moins une continuité C0. Donc : Nk

j (tk+1) = 0 etNk

1 (tk+1) 6= 0. Or :n+k∑i=1

Nki (t) = 1

Donc Nk1 (tk+1) = 1⇒ Sk(tk+1) = p1.


Même raisonnement avec tn+k+1 = b : les seules B-splines non nulles Nkn(t), ..., Nk

n+k(t). Pourj = n, ..., n+ k − 1, la continuité entraine que Nk

j (tn+k+1) = 0 :

Sk(tn+k+1) =n+k∑i=n

piNki (tn+k+1) = pn+k

Dnas le cas où les noeuds intérieurs sont simples, la courbe est formée de n arcs polynomiauxde degré k et elle est de classe Ck−1.

Exemple de courbe spline quadratique ouverte

Exemple 1.7.1. Soient k = 2, n = 4 et P = {p1, p2, ..., p6} un ensemble de points.

t1 = t2 = t3 = a < t4 < t5 < t6 < b = t7 = t8 = t9

Soit C = {1, 1, 1, 2, 3, 4, 5, 5, 5} un ensemble de noeuds et [a, b] = [1, 5].

S2(t) =6∑i=1

piN2i (t)

S2(1) =6∑i=1

piN2i ( t3︸︷︷︸

=t1

) = p1, S2(5) = p6

S2(2) = S2(t4) = p2N22 (t4) + p3N

23 (t4) = 1

2(p2 + p3)

S2(3) = S2(t5) = p3N23 (t5) + p4N

24 (t5) = 1

2(p3 + p4)

S2(4) = S2(t6) = 12(p4 + p5)

Pour les dérivées :

S ′2(t) =6∑i=1

pi

(N1i (t)

ti+2 − ti−

N1i+1(t)

ti+3 − ti+1

)=

6∑i=2

N1i (pi − pi−1)


Calcul des dérivées :

S ′2(t3) = S ′2(1) = p2 − p1

S ′2(t4) = S ′2(2) = p3 − p2

S ′2(t5) = S ′2(3) = p4 − p3

S ′2(t6) = S ′2(4) = p5 − p4

S ′2(t7) = S ′2(5) = p6 − p5

1.7.3 Courbes fermés périodiques

On se fixe un S-polygone {p1, ..., pn} :

pr+ns = pr, r = 1, ..., n, s ∈ Z

t1 < ... < tk a = tk+1 < tk+2 < ... < tn+k < b︸︷︷︸(∗)

= tn+k+1 < tn+k+2 < ... < tn+2k+1

(∗) : et on impose aux absicsses la même périodicité (ti+1 − ti = ti+ns+1 − ti+ns).

Sk(a) =k∑i=1

piNki (a)

Sk(b) =k+n∑i=n+1

piNki (b) =

k∑i=1

pi+nNki+n(b)

=k∑i=1

piNki+n(a+ nk)

=k∑i=1

piNki+2n(a) (si les points sont équidistribués)

=k∑i=1

piNki (a) = Sk(a)

Sk(t) =n+k∑i=1

piNki (t)

Exemple 1.7.2. Soient k = 2, n = 6 et une suite de noeuds uniforme (équidistants).

P = {p1, p2, p3, ..., p6}

C = {−1︸︷︷︸t1

, 0, 1︸︷︷︸t3

, 2, ..., 7︸︷︷︸=t9

, 8, 9}


S2(t) =8∑i=1

piN2i (t), p7 = p1, p8 = p2, ...

S2(1) = S2(t3) = S2(7) = S2(t9) = 12(p1 + p2)

S2(ti) = 12(pi + pi+1)

N21 (0) = N2

2 (0) = 1/2


S ′2(t) = 28∑i=1

pi

(N1i (t)

ti+2 − ti−

N1i+1(t)

ti+3 − ti−1

)

= p1N11 (t) +

8∑i=2

(pi − pi−1)N1i + p8N

19

i = 1, ..., 8, S ′2(t1) = pi−1 − pi−2

1.7.4 Algorithme d’évaluation de De Boor-CoxAlgorithme 1.7.1. Soit t ∈ [tr, tr+1] et Sk(t) = ∑r

i=r−k piNki (t). Le calcul de Sk(t), t ∈ [tr, tr+1]

peut se faire recursivement.DeBoor-Cox()1 for i← r − k to r2 do p

[0]i ← pi

3 for j ← 0 to k − 14 do for i← r to r + j + k

5 do p[j+1]i = t− ti)p[j]

i + (ti+k−j − t)p[j]i−1

ti+k−j − ti67 p[k]

r = pk(t)Dans l’algorithme, il y a 1

2(k + 1)k combinaisons linéaires.

Démonstration. On définit récursivement les quantités suivantes :

reccurence sur m :

d0i = di

dmi = αk−m+1i dm−ii + (t− αk−m+1

i )dm−1i−1

avec αi = t− titi+j − ti

r∑i=r−k+m

dmi Nk−mi (t) =

r∑i=r−k+m

dmit− ti

ti+k−m − tiNk−m−1i (t)

=r∑

i=r−k+mdm+1i Nk−m−1

i (t)

= dkrNr0(t) = dkr

pour m = 0 :S(t) =

r∑i=r−k

d0iN

ki (t) =

∑piN

ki (t) = Sk(t)

Chapitre 2

Approximation au sens des moindrescarrés

2.1 Meilleure approximation dans un espace normé

2.1.1 Premiers résultatsSoit V un espace vectoriel muni d’une norme ‖ · ‖ et on considère un sous-espace U ⊂ V de

dimension finie.

Theorème 2.1.1. ∀f ∈ V , ∃u∗ ∈ U tel que :

‖f − u∗‖ = infu∈U‖f − u‖

u∗ est une1 meilleure approximation de f dans U .

Démonstration. Soit U ′ ⊂ U , U ′ = {u ∈ U, ‖u‖ ≤ 2‖f‖} borné fermé d’un espace de dimensionfinie donc un compact (O ∈ U ′).

d∗ = infu∈U‖u− f‖ ⇒ ∃(ui)i∈N ⊂ U, lim

i→∞‖ui − f‖ = d∗

On peut extraire de (ui) une sous-suite convergente vers u.

∀ε > 0,∃k ∈ N, ‖uk − f‖ ≤ d+ ε/2, ‖uk − u‖ ≤ε

2 (2.1)

‖f − u‖ ≤ ‖f − uk‖+ ‖uk − u‖ ≤ d∗ + ε (2.2)(2.1) + (2.2) implique deux propriétés :

‖f − u‖ ≤ d∗ (2.3)

‖f − u‖ ≥ d∗ (2.4)(2.3) + (2.4)⇒ ‖f − u‖ = d∗. Cela implique donc que u meilleur approximant d f dans U ′.

Prenons u ∈ U\U ′ :

‖u− f‖ ≥ ‖u‖ − ‖f‖ ≥ 2‖f‖ − ‖f‖ = ‖f‖ ≥ ‖f − u‖ car u ∈ U

⇒ u meilleur approximant de f dans U .1On n’a pas encore montré qu’elle est unique

29

30 Chapitre 2. Approximation au sens des moindres carrés

Exemple 2.1.1. Dans l’espace C([a, b)), on a les normes p :

‖f‖p =(∫ b

a|f(x)|pdx

)1/p

, 1 ≤ p <∞

et‖f‖∞ = max

[a,b]|f(x)|

Pour p = 2, la norme ‖f‖ provient d’un produit scalaire.

Remarque. Si on trouve une meilleure approximant en norme∞ avec une erreur petite, les deuxnormes (norme 1 et norme 2) le seront aussi.

Proposition 2.1.2. ∀f ∈ C([a, b]) :

‖f‖1 ≤ (b− a)1/2‖f‖2 ≤ (b− a)‖f‖∞

Démonstration. En utilisant Cauchy-Schwartz :

‖e‖1 =∫ b

a|e(x)|dx

≤(∫ b

a|e(x)|2dx

)1/2 (∫ b

a1dx

)1/2

≤ ‖e‖2(b− a)1/2

‖e‖2 =(∫ b

a|e(x)|2dx

)1/2

≤(∫ b

a‖e‖2

∞dx

)1/2

= ‖e‖∞(b− a)1/2

Définition 2.1.1. La norme 2 s’appelle la norme au sens des moindres carrés (ou normeeuclidienne).

La norme ∞ s’appelle la norme uniforme (ou min-max).

2.1.2 Unicité de la meilleure approximationDéfinition 2.1.2. Un ensemble S d’un espace vectoriel V est convexe (respectivement stricte-ment convexe) si et seulement si :

∀s0, s1 ∈ S, θs0 + (1− θ)s1 ∈ S, ∀θ ∈ [0, 1]

(resp. {θs0 + (1− θ)s1, θ ∈]0, 1[} ⊂◦S})

avec◦S = l’interieur de S.

Définition 2.1.3. Une norme est strictement convexe si et seulemenet si B(0, 1) = {x ∈V, ‖x‖ < 1} est strictement convexe.

Chapitre 2. Approximation au sens des moindres carrés 31

Theorème 2.1.3. Soit S un sous-ensemble connexe d’un espace vectoriel normé V et f ∈ V :a) si f ∈ V a une meilleure approximation dans S alors l’ensemble des meilleures approxima-

tions de f est un convexe.b) Si de plus la norme est strictement convexe alors il existe au plus une meilleure approxima-

tion.

Démonstration. a) Soit s∗ une meilleure approximation de f , d∗ = ‖f − s∗‖. L’ensemble desmeilleures approximations est S ∩B(f, d∗). Or S et B(f, d∗) sont des convexes.

b) Supposons qu’il y en a deux meilleures approximations distinctes s0 et s1 de f dans S.

‖s0 − f‖ = ‖s1 − f‖ = d∗

B(f, d∗) est strictement convexe par hypothèse :

‖1/2(s0 + s1)− f‖ < d∗

Ce qui est absurde.

Exemple 2.1.2. 1) Pour V ⊂ C([a, b]), la norme 2 est strictement convexe.2) Les normes 1 et ∞ ne sont pas strictement convexes.

2.2 Meilleure approximation dans un espace préhilber-tien

Soit V muni d’un produit scalaire <,> sur R.Rappel. Un produit scalaire sur V est une application <,>: V × V → R avec les propriétéssuivantes :(i) bilinéarité :

< v1 + λv2, w >=< v1, w > +λ < v2, w >

< v,w1 + λw2 >=< v,w1 > +λ < v,w2 >

(ii) symétrie : < v,w >=< w, v >

(iii) < v, v >≥ 0 avec égalité si et seulement si v = 0.Au produit scalaire, on associe :– une norme : ‖x‖ = √< x, x >.– l’inégalité de Cauchy-Schwartz : | < x, y > | ≤ ‖x‖‖y‖– l’égalité du parallélogramme : ‖x+ y‖2 + ‖x− y‖2 = 2‖x‖2 + 2‖y‖2

Exemple 2.2.1. 1) L2ω([a, b]) = {f,

∫ ba f(x)2ω(x)dx < +∞}

< f, g >=∫ b

af(x)g(x)ω(x)dx, ω = fonction poids

2) Produit scalaire discret sur Rn :

< x, y >=n∑i=1

xiyiωi, ω ∈ Rn, ωi > 0, ∀i


3) Espaces des suites : l2 = {(li)i∈N,∑∞i=1 |li|2 <∞}

< x, y >=∞∑i=1|xiyi|

Proposition 2.2.1. Soit U un sous-espace de dimension finie. Comme ‖ · ‖2 est strictementconvexe, une norme déduite d’un produit scalaire :

∀f ∈ V, ∃u∗ ∈ U, ‖f − u∗‖ = infu∈U‖f − u‖

Exemple 2.2.2. Si V = C([a, b]), u ∈ P\, f ∈ V . On cherche p∗ ∈ Pn qui minimise sur Pn,Sk(t0, ..., tn) : ∫ b

a(p(x)− f(x))2ω(x)dx

L’avantage est que l’on peut considérer l’approximation discrète en moindres carrés si l’ondispose des valeurs de f : si yi = f(xi), i = 1, ..., N avec une variance 1

wi. On considère :

< f, g >N=N∑i=1

wif(xi)g(xi)

< f, f >N= 0⇒ f = 0

Ce n’est pas une norme sur PN mais sur PN−1

Theorème 2.2.2 (Caractérisation). Soit U un espace vectoriel de dimension finie de V (espacepréhilbertien de produit scalaire <,>). Soit f ∈ V alors p∗ est la meilleure approximation de fdans U si et seulement si l’erreur e∗ = f − p∗ vérifie les propriétés d’orthogonolité :

< e∗, p >= 0, ∀p ∈ U (2.5)

Démonstration. (⇒) Supposons par l’absurde qu’il existe p ∈ U tel que < e∗, p >= 0. Onconsidère l’approximant p∗ + λp, λ ∈ R∗.

‖f − (p∗ + λp)2‖ = < f − p∗ + λp, f − p∗ + λp >

= ‖f − p‖2 − 2λ < f − p∗, p > +λ2‖p‖ =: q(x)

Le minimum est atteint quand q′(λ) = 0 ⇔ λ = ‖p‖2

<e∗,p>et pas pour λ = 0, p∗ n’est pas

une meilleure approximation, ce qui est absurde. Donc ∀p ∈ U,< e∗, p >= 0.(⇐) Soit < e∗, p >= 0, ∀p ∈ U et on prend q ∈ U .

‖f − q‖2 − ‖f − p∗‖2 = < f − q, f − q > − < f − p∗, f − p∗ >= ‖f‖2 − 2 < f, q > +‖q‖2 − ‖f‖2 + 2 < f, p∗ > +‖p∗‖2

= 2 < f, p∗ − q > +‖q‖2 − ‖p‖2 + 2 < p∗, p∗ − q > −2 < p∗, p∗ − q >= ‖p∗‖2 − 2 < p∗, q > +‖q‖2︸︷︷︸

‖p∗−q|2+2<e∗,p∗−q>=‖p∗−q‖2

+2 < f − p∗, p∗ − q >

‖f − q‖2 = ‖f − p∗‖2 + ‖p∗ − q‖2 ≥ ‖q − p∗‖2

q meilleure approximation ⇔ p∗ = q ⇒ p∗ meilleure approximation.


Remarque. 1) Unicité de la meilleure approximation.

‖f − q‖ = ‖f − p∗‖ ⇔ q = p∗

2) q = 0 :‖f‖2 = ‖p∗‖2 + ‖f − p‖2 (2.6)

Corollaire (méthode de calcul du meilleur approximant). Pour calculer la meilleure approxi-mation, étant donné une base {ui}ni=1 de U , soit :

p∗ =n∑i=1

α∗iui

On résoud le système :

< f −n∑i=1

α∗iui, uj >= 0, j = 1, ..., n (2.7)

On a ainsi :

(2.5) ⇔ < e∗, ui >= 0

(2.7) ⇔n∑i=1

α∗i < ui, uj >=< f, uj >, j = 1, ..., n

La recherche de la meilleure approximation revient à résoudre un système linéaire de n équationsà n inconnues. Ce système d’équations est appelé les équations normales. Gn =

(< ui, uj >

)i,j

est appelé matrice de Gram et elle est définie positive.

Démonstration. On montre que la matrice Gn de Gram de dimension n est définie positive :

aTGna = (a1, ..., an)Gn

a1...an

=(<

n∑i=1

aiui, u1 >,<n∑i=1

aiui, u2 >, ..., <n∑i=1

aiui, un >

)a1...an

= <

n∑i=1

aiui,n∑i=1

aiui >=∥∥∥∥∥n∑i=1

aiui

∥∥∥∥∥2

≥ 0

et = 0⇔ ai = 0, ∀i.

Rapport avec les moindres carrés discrets A ∈ Rn×m avec m > n, A = [A1, A2, ..., An].On cherche min ‖b− Ax‖2 (c’est-à-dire ‖b−∑xiA

i‖2, x ∈ Rn). Soit V = Rn et U = ImA =<A1, A2, ..., An >. Résoudre au sens des moindres carrés le système Ax = b équivaut à chercherla meilleure approximation de b dans U . Si A est de rang maximal, < A1, A2, ...An > est unebase de U .

Gn =< Ai, Aj >= ATA (matrice des équations normales)

c =

< b,A1 >< b,A2 >

...< b,A”n >

= AT b


Système des équations normales :

ATAx = AT b→ QR = A

Pour éviter les problèmes de stabilité associés à la résolution du système Gnα = 0, on vaconsidérer une base orthogonale de l’espace U .

< ui, uj >= 0⇒ matrice de Gram diagonale

Le meilleur approximant est :p∗ =

n∑i=0

< f, ui >

< ui, ui >ui

2.2.1 Algorithme de Gram-SchmidtAlgorithme 2.2.1. Soit (ui)ni=0 base de U , on veut (vi)ni=0 une base orthonormée.()1 v0 = u02 for i← 1 to n3 do p∗ = ∑i−1

j=0<ui,uj>uj‖uj‖2

4 vi = ui − p∗

Démonstration. Par réccurence, p∗ est la meilleure approximation de vi dans < v0, ..., vn−1 >=<u0, ..., un−1 >. Par la caractérisation de la meilleure approximation :

vi ⊥ v0, ..., vi−1, < vi, vj >= 0, j = 0, ..., i− 1

Lemme 2.2.3. Soit U ⊂ V espace préhilbertien avec une base orthogonale (u0, u1, ..., un).

∀f ∈ V, Πn(f) =n∑i=0

< f, ui > ui

est la meilleure approximation. Alors :

Πn : V → Uf 7→ Πn(f)

a) est linéaire (linéarité du produit scalaire),b) est un projecteur : Π2

n = Πn et,c) ∀f ∈ V , ‖f‖2 = ‖Πn(f)‖2 + ‖f − Πn(f)‖2 et en particulier :

‖Πn‖ = supf∈V

‖Πn(f)‖‖f‖

= 1

Démonstration. a)

Πn(Πn(f)) =n∑i=0

< Πn(f), ui >︸︷︷︸<f,ui>

= Πn(f)

b)∀q ∈ U, ‖f − q‖2 = ‖f − p∗‖2 + ‖p∗ − q‖2 ⇔ ‖f‖2 = ‖f − p∗‖ − ‖p∗‖

c) ‖Πn(f)‖2 = ‖f‖2, f ∈ U . Donc Πn(f) = f .


2.2.2 Approximation à une précision donnéeProblème. Soit (ui)i des éléments de V , f ∈ V et on veut construire une approximation de fcomme combinaison linéaire des premières n+ 1 fonctions de la suite. C’est-à-dire déterminern tel que ‖f − p∗n‖ ≤ δ ⇒ ‖f − p∗n‖2 ≤ δ2 ⇔ ‖p∗n‖2 ≥ ‖f‖2 − δ2.

Initialisation : On pose v0 = u0 (n = 0) :

p∗0 =< f, v0v0

‖v0‖2 (c’est-à-dire ‖f‖2 − δ2)

()1 while ‖pn‖2 < ‖f‖2 − δ2

2 do n=n+13 Calculer vn par Gram− Schmidt4 Calculerp∗n = p∗n−1 + <f,vn>

‖vn‖2 vn

5 Calculer‖p∗n‖ = ‖p∗n−1‖+ <f,vn>2

‖vn‖2

‖p∗n‖2 =∥∥∥∥∥n∑i=0

< f, vi >

‖vi‖2 vi

∥∥∥∥∥2

=n∑i=0

< f, vi >2

‖vi‖2

Lemme 2.2.4 (Inégalité de Bessel). Soit (u0, ..., un−1) ∈ V orthonormée. Alors ∀f ∈ V :∞∑j=0

< f, ui >2= ‖f‖2

avec égalité ∀f ∈ V (égalité de Parseval) si et seulement si < u0, ..., un > est dense dans V .

Exemple 2.2.3 (Approximation polynomial en moindres carrés).

Problème. Déterminer un polynôme p ∈ Pn qui approche au mieux au sens des moindrescarrés un nuage de points (xj, f(xj))Nj=0 avec N > n, xj distincts.

Soit ui(x) = xi pour i = 0, ..., n, ainsi on définit :

p(x) =N∑i=0

aiui(x)


On cherche à déterminer (a0, a1, ..., an)T tel que :N∑j=0

(f(xj)− p(xj))2 soit minimum

b =

f(x0)f(x1)

...f(xn)

, A = (ui(xj))i,j, a =

a0...an

p(x0)p(x1)...

p(xN)

= a0

u0(x0)

...uN(x0)

+ ...+ an

u0(xN)

...uN(xN)

= Aa

Minimiser ‖b− Aa‖22, c’est résoudre le système d’équations normales.

ATAa = AT b

On peut faire mieux en utilisant la décomposition QR de A.

‖b− Aa‖22A=QR= ‖b−QRa‖2

2 = ‖Qtb−Ra‖22 = ‖c1R1a‖2

2 + ‖c2‖22

Qtb =(c1c2

)

cond(R1) =√

cond(ATA)

Application 2.2.1 (Approximation des fonctions périodiques, séries de Fourier). V = C2π :espace des fonctions continues périodiques.

f(x+ 2π) = f(x), 0 < x < +∞

U = Dn, l’espaces des polynômes trigonométriques :

Dn = {q, q(x) = 12a0 +

n∑j=1

aj cos(jx) + bj sin(jx)}

muni du produit scalaire :< f, g >=

∫ π

−πf(x)g(x)∫ π

−π cos(jx) cos(kx)dx = 0∫ π−π sin(jx) sin(kx)dx = 0

}j 6= k

∫ π

−πsin(jx) cos(kx) = 0, ∀j,∀k

{1, sin x, cosx, sin 2x, cos 2x, ..., sinnx, cosnx} base orthogonale de Dn. Les polynômes p ∈ Dnqui minimise ‖f − p‖2 est donné par :

aj = − 1π

∫ π

−πf(θ) cos(jθ)dθ

bj = − 1π

∫ π

−πf(θ) sin(jθ)dθ

Chapitre 3

Polynômes orthogonaux et formules dequadrature

Le cas particulier important dans l’approximation en moindres carrés correspond à l’ap-proximation dans l’espace U = Pn. Nous allons caractériser les bases orthogonales par rapportau produit scalaire :

< f, g >=∫ b

af(x)g(x)ω(x)dx avec ω > 0 dans [a, b]

Une base orthonormale est obtenue par Gram-Schmidt appliqué à la base canonique.

3.1 Quelques propriétés des polynômes orthogonauxTheorème 3.1.1 (Relation de réccurence à 3 termes). La suite (pi)i≥0 définie par :

pi+1(x) = (x− αi)pi(x)− βipi−1, i ≥ 1

p0(x) = 1, p1(x) = (x− α0)p0(x)avec :

αi = < pi, xpi >

‖pi‖2

βi = ‖pi‖2

‖pi−1‖2

vérifie :a) ∀i, pi est un polynôme de degré u de coefficient dominant 1 (unitaire).b) < pi, pj >= 0, ∀j 6= i, c’est-à-dire (p0, ..., pn) forment une base orthogonale de Pn.

Démonstration. a) trivial par les conditions initiales + réccurence.b) Par réccurence :

n = 1, < p1, p0 >=< xp0, p0 > −α0 < p0, p0 >= 0

Supposons que {p0, ..., pn} sont orthogonaux. On veut montrer que pn+1 ⊥ p0, , ...pn. Onconsidère le polynôme xpn et :

pn+1 = xpn(x)−n∑i=0

< xpn, pi >

< pi, pi >pi︸︷︷︸

meil. approx. de xpn dans {p0,...,pn}

⊥ p0, ..., pn

37

38 Chapitre 3. Polynômes orthogonaux et formules de quadrature

< xpn, pi >=< pn, xpi >= 0 pour i ≤ n− 2

pn+1(x) = xpn(x)−< xpn−1, pn−1 >

< pn−1, pn−1 >pn−1 −

< xpn, pn >

< pn, pn >︸︷︷︸αn

pn

= xpn(x)− αnpn(x)−< xpn, pn−1 >

< pn−1, pn−1 >pn−1

Mais :< xpn, pn−1 >=< pn−1, xpn−1 >=< pn, pn−1 >

Remarque. 1) {pi}ni=0 base de Pn. Ils sont linéairement indépendants.n∑i=0

λipi = 0⇒n∑i=0

λi < pi, pj >= 0

λj < pj, pj >= 0⇒ λj = 0

2) Si φn+1 est un polynôme orthogonal de degré n+1 alors φn+1 = cpn+1 (la suite des polynômesest définie à une constante multiplicative près).

φn+1 =n+1∑i=1

λipi

< φn+1, pj >= λj < pj, pj >= 0, j = 0, ..., n⇒ λj =, ∀j = 1, .., n→ φn+1 = λn+1pn+1

Theorème 3.1.2 (Entrelacement des racines). Le polynôme pn admet n racines distincts dansl’intervalle ]a, b[ :

a < x1,n < x2,n < ... < xn,n < b

et les zéros de pn entrelacent ceux de pn+1 :

a < x1,n+1 < x1,n < x2,n+1 < x2,n < ... < xj,n < xj,n+1 < xj+1,n < ... < xn,n < xn+1,n < b

Démonstration. 1) Soient {y1, ..., yn} les points dans ]a, b[ où pn change de signe. On construitle polynôme :

p(x) = ±n∏i=1

(y − yi)

qui a les mêmes changements de signe que pn dans [a, b] et donc pn(x)p(x) ≥ 0 et s’annuleen n points. Soit ω > 0 :

< p, pn >=∫ b

ap(x)pn(x)ω(x)︸︷︷︸

≥0

dx > 0

Dû aux propriétés d’orthogonalité de pn :

deg(p) ≥ n (3.1)

deg(p) ≤ n (3.2)(3.1) + (3.2)⇒ deg(p) = n⇒ y1, ..., yn sont les racines distincts de pn dans ]a, b[.

Chapitre 3. Polynômes orthogonaux et formules de quadrature 39

2) Entrelacements des racines : par réccurence• k = 1, trivial.• Supposons vrai pour k et montrons pour k + 1.

pk−1(xj,k) =k−1∏i=1

(xj,k − xi,k−1)

=j−1∏i=1

(xj,k − xi,k−1)︸︷︷︸>0

k−1∏i=j

(xj,k − xi,k−1)︸︷︷︸(−1)k−jpk−1(xj,k)>0

= βk︸︷︷︸≥0

pk−1(xj,k)

avec1

sgn(pk+1(xj,k) = − sgn(pk−1(xj,k) = (−1)k−j+1

pk+1(xk,k) < 0, limx→∞

pk+1(x) = +∞

Donc il existe un xk+1,k+1 > xk,k.

(−1)kpk+1(x1,k) > 0, limx→−∞

(−1)k−1pk+1(x) = −∞

Donc il existe une racine de pk+1, x1,k+1 > x1,k.Pour chaque intervalle ]xj,k, xj+1,k[ :

pk+1(xj,k)pk+1(xj+1,k) < 0

donc il y a au moins une racine de pk+1 donc ]xj,k, xj+1,k[ pour j = 1, ..., k− 1. On a ainsik+ 1 racines + 2 extrémités = k+ 1. Cela implique qu’il y a exactement une racine danschaque intervalle.

Theorème 3.1.3 (Caractérisation). Soit {ω(x), a ≤ x ≤ b} une fonction (poids) conntiue.Une fonction φk+1 ∈ C([a, b]) vérifie les conditions d’orthogonalité :∫ b

aφk+1(x)p(x)ω(x)dx = 0, ∀p ∈ Pk

si et seulement si ∃u ∈ Ck+1([a, b]) telle que :(i) ω(x)φk+1(x) = u(k+1)(x) pour a ≤ x ≤ b.(ii) u(i)(a) = u(i)(b) = 0, i = 0, ..., k.

Démonstration. (⇐)∫ b

aω(x)φk+1p(x)dx =

∫ b

au(k+1)(x)p(x)dx (3.3)

= (−1)k+1∫ b

au(x) p(k+1)(x)︸︷︷︸

=0, ∀p∈Pk

dx (3.4)

= 0

Pour passer de l’étape (3.3) à l’étape (3.4), on fait une intégration par parties en remar-quant u(i)(b) = u(i)(a) = 0.

1sgn(x) =

{−1 si x < 01 si x ≥ 0


– On définit u par ω(x)φk+1(x) = u(k+1)(x) avec constante d’intégration u(i)(a) = 0 pouri = 0, ..., k. ∫ b

au(k+1)(x)p(x)dx = 0, ∀p ∈ Pk

On choisit p(x) = (b− x)j, pj(x), j ≤ k.∫ b

au(k+1)(x)(b− x)j = 0 ⇒ ... (3.5)

⇒[(−1)ju(k−j)p

(j)j

]ba= (−1)jj!u(k−j)(b) = 0

⇒ u(k−j)(b) = 0

u vérifie donc les propriétés (i) et (ii)

On va maintenant proposer des choix de fonctions tels que φk+1 est un polynôme de degrék + 1.

3.2 Exemples de familles de polynômes orthoognauxExemple 3.2.1 (Polynômes de Jacobi). Soient un intervalle d’orthogonalité [a, b] = [−1, 1],une fonction poids ω(x) = (1 − x)α(1 + x)β (avec α, β > −1), on définit les polynômes deJacobi :

u(x) = (1− x)α+k+1(1 + x)β+k+1

On a ainsi :u(k+1)

ω(x) est un polynôme de degré k + 1

On a la représentation :

pk((x) = (1− x)−α(1 + x)−β dk

dxk

[(1− x)α(1 + x)β+k

](3.6)

(4.6) est la formule de Rodrigue. Elle peremt d’obtenir des expressions algébriques pour αk etβk.

Exemple 3.2.2 (Cas particulier). 1. α = β = 0 : polynômes de Legendre avec ω(x) = 1.2. α = β = −1/2 : polynômes de Tchebychev de première espèce pj(x) = Tj(x) , ω(x) =

1√1−x2 .

3. α = β = 1/2 : polynômes de Tchebychev de seconde espèce pj(x) = Uj(x), ω(x) =√1− x2.

Exemple 3.2.3 (Polynômes de Laguerre). Soient l’intervalle d’orthogonalité [a, b] = [0,+∞],une fonction poids ω(x) = e−x. On définit les polynômes de Laguerre :

u(x) = e−xxk+1

Lk(x) = exdk

dxk(e−xxk)


Exemple 3.2.4 (Polynômes d’Hermite). Soient l’intervalle d’orthogonalité [a, b] = R, ω(x) =e−x

2 ,u(x) = e−x2xk+1. On définit les polynômes d’Hermite :

Hk(x) = e−x2 dk

dxk(e−x2

xk)

Exemple 3.2.5 (Un peu plus sur les polynômes de Tchebychev). Tn(θ) = cos(nθ) (changementde varibles cos θ = x). Tn est un polynôme de degré n en cos θ.∫ 1

−1(1− x2)1/2Tj(x)Tk(x) = 0, ∀j 6= 0

∫ π

0cos(jθ) cos(kθ)dθ = 1

2

∫ π

0cos((k + j)θ)− cos((k − j)θ)dθ

= 0

• On connait tous les racines :

cos(nθ) = 0 ⇔ nθ = π

2 + kπ

⇔ θ = π + 2nkπn

– cos(α + β) + cos(α− β) = 2 cos(α) cos(β). On pose α = kθ et β = θ :

cos(k + 1)θ)︸︷︷︸Tk+1(x)

+ cos((k − 1)θ)︸︷︷︸Tk−1(x)

= 2 cos(kθ)︸︷︷︸Tk(x)

cos θ

Donc :Tk+1(x) + Tk−1(x) = 2Tk(x)x⇒ Tk+1(x) = 2xTk(x)− Tk−1(x)

De même pour les polynômes de Tchebychev de second degré.

Un(x) = sin((n+ 1) arccos(x))sin(arccos(x))

3.3 Formule de quadrature

I(f) =∫ b

af(x)ω(x), ω > 0

On veut calculer une valeur approchée de I(f).

Définition 3.3.1. Une formule de quadrature à n points est donnée :

In(f) =n∑i=1

ωif(xi), xi ∈ [a, b]

Le degré de précision est l’entier m tel que :

I(xk) = In(xk) k = 0, ...,mI(xm+1) 6= In(xm+1)

C’est le degré du polynôme du plus haut degré pour lequel la formule est exacte.


3.3.1 Formules de quadrature interpolatoireLemme 3.3.1. Les trois affirmations suivantes sont équivalentes :(i) In admet un degré de précision ≥ n− 1.(ii) In est interpolatoire (⇔ In(f) = I(pn) où pn est un polynôme de degré n− 1 qui interpole

f aux points xi)(iii) ∀j, ωj = I(lj) où lj sont les polynômes de Lagrange :

lj(x) =n∏

i,j=1i 6=j

x− xixj − xi

, lj(xi) = δij

Démonstration. (i)⇒ (iii) lj = ∑n−1k=0 akx

k

I(lj) =m∑k=0

akI(xk)

=m∑k=0

akIm(xk)

= In

(m−1∑k=0

akxk

)= Im(lj)

=m∑i=1

ωilj(xi) = ωj

(iii)⇒ (ii) pn = ∑ni=1 li(x)f(x), polynôme d’interpolation :

I(pn) =n∑i=1

f(xi)I(li)

=n∑i=1

ωif(xi) = In(f)

(ii)⇒ (i) Pour k = 0, ..., n− 1, I(xk) = In(xk).

Exemple 3.3.1 (ω = 1). 1) Formule des trapèzes :

ITr2 (f) = b− a

2 (f(a) + f(b))


2) Formule du point milieu :

IM1 (f) = (b− a)f(a+ b

2

)

Il suffit de montrer que I(x) = IM1 (x).

IM1 (x) = (b− a)b+ a

2

I(x) =∫ b

axdx = b2 − a2

2

Theorème 3.3.2. Pour toute formule de quadrature, In interpolante :

∀f ∈ Cn([a, b]), |I(f)− In(f)| ≤ ‖f(n)‖[a,b]

n!

∫ b

a|Πn(x)|ω(x)dx

avec :Πn(x) =

n∏i=1

(x− xi)

Démonstration. Formule de Cauchy pour l’erreur d’interpolation.

f(x)− pn(x) = f (n)(ξ)n! Πn(x), ξ ∈ [a, b], ‖f‖[a,b] = max

[a,b]|f(x)|

Exemple 3.3.2. 1) Régle des trapèzes :

|I(f)− ITrr (f)| ≤ ‖f

′′‖2

∫ b

a(x− a)(b− x)dx

= ‖f′′‖

12 (b− a)3

2) Régle du point milieu :

|I(f)− IM1 (f)| ≤ ‖f ′‖∫ b

a

(x− a+ b

2

)dx

= (b− a)2

4 ‖f ′‖


On peut pousser l’analyse d’erreur un peu plus loin. L’erreur d’interpolation peut s’écrire :

f(x)− pn(x) = [x1, ..., xn, x]fΠn(x)

L’erreur dans le calcul d’interpolation :

I(f)− In(f) =∫ b

a[x1, ..., xn, x]fΠn(x)dx

Cette formule peut simplifier dans certaines situations.a) Si Πn(x) est de signe constant sur [a, b] : par le théorème de la moyenne :

I(f)− In(f) = [x1, ..., xn, ξ]f∫ b

aΠn(x)dx

et de plus si f ∈ Cn([a, b])

I(f)− In(f) = f (n)(η)n!

∫ b

aΠn(x)dx avec η ∈]a, b[

b) Si∫ ba Πn(x)dx = 0 : formule de réccurence pour les différences divisées :

[x1, x2, ..., xn+1, x]f = [x1, ..., xn+1]f + [x1, ..., xn+1, x]f (x− xn)∫ b

a[x1, ..., xn, x]f =

∫ b

a[x1, ..., xn, xn+1](x− xn)Πn(x)dx

Si on choisit xn+1 de telle sorte que Πn+1(x) = (x− xn+1)Πn(x) soit de signe constant :

I(f)− In(f) = f (n+1)(ξ)(n+ 1)!

∫ b

aΠn(x)

Pour la règle du point milieu :

Π1(x) =(x− a+ b

2

)

∫ b

aΠ1(x) =

[(x− a+b2

)2

]ba= 0

On choisit un deuxième point x1 = x2 = a−b2 .

Π2(x)(x− a+ b

2

)2

≥ 0 signe constant

I(f)− IM1 (f) = f ′′(ξ)2

∫ b

a

(x− a+ b

2

)2

dx

= f ′′(ξ)2

[13

(x− a+b

22

)]ba

= f ′′(ξ)2

2(b− a)3

24= f ′′(ξ)

24 (b− a)3

Pour la construction des formules de type interpolante :


(a) Soit on construit le polynôme d’interpolation pn aux points xi, i = 1, ..., n et on calcule :

In(f) =∫ b

apn(x)dx

=n∑i=1

Aifi(x) avec Ai =∫ ba li(x)dx

(b) Soit on pose :

In(f) =n∑i=1

Aif(xi)

et on calcule les coefficients Ai de la combinaison linéaire de sorte que la formule soit exactepour les monomes 1, x, ..., xn−1.

n∑i=1

Aixji =

∫ b

axjdx, j = 0, ..., n− 1

où∫ ba x

jdx constitue un système linéaire de n équations à n inconnues (Ai).

3.3.2 Méthodes compositesPour pouvoir contrôler l’erreur (c’est-à-dire construire des formules précises à une précision ε

près), l’idée est de diviser l’intervalle en N sous-intervalles et appliquer la formule d’intégrationà chacun. L’amplitude des sous-intervalles viendra comme paramètre de l’erreur de l’erreur etpermettra lde le choisir pour obtenir la précision voulue.

Etant donnée a = t0 < t1 < ... < tN = b et une formule de quadrature sur [a, b].

I [a,b](f) =n∑i=1

ωif(xi)

∫ d

cg(t)dt = d− c

b− a

∫ b

ag(ϕ(x))dx (3.7)

avecϕ : [a, b] → [c, d]

x 7→ t = c+ d−cb−a(x− a)

(3.7)⇔ d− cb− a

I [a,b](g ◦ ϕ)

I [c,d](g) = d− cb− a

n∑i=1

ωig

(c+ d− c

b− a(xi − a)

)∫ b

af(x)dx =

N−1∑k=0

∫ tk+1

tk

f(x)dx

Définition 3.3.2. On définit la méthode composite par :

I(N)(f) =N−1∑k=1

I [tk,tk+1](f)

=N−1∑k=1

(n∑i=1

tk+1 − tkb− a

ωif(tk + tk+1 − tk

b− a(xi − a)

))


Formule des trapèzes composites

I[a,b]2 = b− a

2 (f(a) + f(b))

I[ti,ti+1]2 = ti+1 − ti

2 (f(ti+1)− f(ti))

ITr(N)([a, b])(f) =

N−1∑i=0

I[ti,ti+1]2 =

N−1∑i=0

ti+1 − ti2 (f(ti−1)− f(ti))

Dans le cas des points équidistribuées :

h = ti+1 − ti, i = 0, ..., N − 1

ITr(N)([a, b])(f) = h

2

[f(b) + f(a) + 2

N−1∑i=1

f(ti)]

L’erreur commise est :

ETr(N)(f) =

∫ b

af(x)dx− ITr

(N)([a, b])(f)

=N−1∑i=0

(∫ ti+1

tif(x)dx− I [ti,ti+1]

2 (f))

(3.8)

La formule (3.8) est vraie si f ∈ C2([a, b]).

(3.8) =N−1∑i=0

12f′′(ξi)

(ti+1 − ti)3

6 , ξi ∈]ti, ti+1[

= h3

12

N−1∑i=0

f ′′(ξi)

= h3N

12

∑N−1i=0 f ′′(ξi)N︸︷︷︸

théorème de la moyenne

= b− a12 f ′′(ξ)h2

Si |f ′′(x)| ≤M , ∀x ∈ [a, b]|ETr

(N)(f)| ≤ b− a12 Mh2

Pour calculer∫ ba f(x)dx avec une précision ε, il suffit de considérer un nombre N de sous-

intervalles tels que :b− a12 Mh2 ≤ ε⇔ h ≤

√ε

12b− a

1M

3.3.3 Formules de quadrature de Gauss

I(f) =∫ b

af(x)ω(x)dx, ω ≥ 0 sur [a, b]

In(f) =n∑i=1

Aif(xi), 2n paramètres

Si on fixe les xi, on construit les formules interpolatoire de degré de précision n − 1. Si on leslaisse libres, quel espace dans lequel la formule peut être exacte ?


Lemme 3.3.3. Soit In(f) = ∑ni=1 Aif(xi) une fomrule de quadrature avec un degré de précision

m. Alors m < 2n et si m− 2n− 2, 2n− 1 alors Ai > 0, ∀i.

Démonstration. Supposons, par l’absurde, m ≥ 2n. On construit le polynôme :

p(x) =n∏i=1

(x− xi)2

C’est un polynôme de degré 2n.

I(p) = In(p) =n∑i=1

Aip(xi) = 0

Or :I(p) =

∫ b

ap(x)ω(x)dx > 0

Ce qui est contradictoire. Donc m < 2n. Maintenant, supposons m ≥ 2n− 2, on choisit :

p(x) = lj(x) =

n∏i=ji 6=j

(x− xi)2

(xj − xi)

2

Ce polynôme est le polynôme de Lagrange et a un degré 2n− 2.

In(p) =n∑i=1

Ailj(xi)2 = Aj = I(p) > 0, ∀j

Theorème 3.3.4. Soit pn le nième polynôme orthogonal par rapport au produit scalaire :

< f, g >=∫ b

af(x)g(x)ω(x)dx

et soient a ≤ x1 < x2 < ... < xn ≤ b ses racines. Alors

In(f) =n∑j=1

Ajf(xj) avec Aj = I(lj), j = 1, ..., n (3.9)

(3.9) a un degré de précision de 2n − 1, elle est unique et c’est la formule de quadrature deGauss.

Démonstration. Soit p ∈ P2n−1 et il suffit de montrer que I(p) = In(p). On considèrela division euclidienne p = qpn + r avec r est un polynme de degré ≤ n − 1. CommeAj = I(lj) pour j = 1, ..., n, c’est une formule interpolatoire donc In(r) = I(r)

In(p) = In(qpn) + In(r) (3.10)

=n∑j=1

Ajq(xj)p(xj)︸︷︷︸=0

+I(r) = 0 + I(r) (3.11)

et :I(qpn) =

∫ b

aq(x)pn(x)ω(x)dx = 0 car q ∈ Pn−1

Donc :(3.11) = I(qpn) + I(r) = I(p)


Unicité : Supposons que l’on a :In(f) =

n∑i=1

Aif(xi)

la formule de quadrature de Gauss avec Ai = I(lj), lj est le polynôme de Lagrange associéaux abscisses xi.

In (pnli)︸︷︷︸∈P2n−1

= I(pnli) =∫ b

apn(x)li(x)ω(x) = 0 par othogonalité

=n∑j=1

Ajpn(xj)li(xj) = Aipn(xi)

Pour i = 1, ..., n, Aipn(xi) = 0. En utilisant le lemme 3.3.3 et en sachant que Ai > 0, ona ainsi que pn(xi) = 0 avec i = 1, ..., n et donc :

xi = xi, i = 1, ..., n⇒ In = In

Theorème 3.3.5. Soit pn le polynôme de degré n orthonormal par rapport au produit scalaire

< f, g >=∫ b

af(x)g(x)ω(x)dx

de coefficient de tête χn (c’est-à-dire pn(x)− χnxn ∈ Pn−1)

∀f ∈ C2n−1([a, b]), ∃ξi ∈ [a, b], I(f)− In(f) = f (2n−1)(ξ)(2n− 1)!

1χ2n

Démonstration. Soit p ∈ P2n−1 qui vérifie les conditions d’interpolation suivantes : p(xi) = f(xi), i = 1, ..., np′(xi) = f ′(xi), i = 1, ..., n

polynôme d’interpolation d’Hermite

On a montré l’existence et l’unicité de la formule de quadrature de Gauss, on veut maintenantmontrer sa formule d’erreur.

∃ξ ∈ [a, b], f(x)− p(x) = f (2n−1)

(2n− 1)!

n∏j=1

(x− xj)2

On pose :

m = min[a,b]

f (2n−1)(x)(2n− 1)! , M = max

[a,b]

f (2n−1)(x)(2n− 1)!

m ≤ (f(x)− p(x))χ2n(∏n

j=1(x− xj)2)χ2n

≤M ⇔ mpn(x)2 ≤ χ2n(f(x)− p(x)) ≤Mpn(x)2

∫ b

apn(x)2ω(x)dx = 1

m ≤ χ2nI(f − p) ≤M

I(f − p) = I(f)− I(p) = I(f)− In(p) (3.12)= I(f)− In(f)


La formule (3.12) est vraie car le degré de précision est 2n− 1.

In(p) =n∑i=1

Aip(xi) =n∑i=1

Aif(xi) = In(f)

m

χ2n

≤ I(f)− In(f) ≤ M

χ2n

Par le théorème des valeurs intermédiaires :

∃ξ ∈ [a, b], I(f)− In(f) = 1χ2n

f (2n−1)

(2n− 1)!

Exemple 3.3.3. χn = 2n−(1/2) pour les polynômes de Tchebychev.

1χ2n

≤ 2(b− a

4

)2n

Chapitre 4

Approximation en norme uniforme

Problème. Calculer la meilleure approximation (si existence) d’une fonction continue sur uncompact en norme uniforme dans un espace de dimension finie. Plus précisement, V = C([a, b]),‖ · ‖ = ‖ · ‖∞, ‖f‖∞ = max[a,b] |f(x)|, U est un espace vectoriel de dimension finie. On veutdéterminer p∗ ∈ U tel que :

‖f − p∗‖∞ = minp∈U‖f − p‖∞

Si p∗ existe, on l’appelle meilleur approximant en norme uniforme ou en norme min-max.

On veut ainsi chercher :– les problèmes d’existence et d’unicité,– la caractérisation,– des algorithmes de calcul.

4.1 Réduction de l’erreur d’une approximationProblème. Etant donnée une approximation p ∈ U de f , peut-on la changer de façon à trouverune meilleure approximation (c’est-à-dire trouver q ∈ U tel que ‖(p+ θq)− p‖∞ < ‖f − p‖∞.

Soit Z un sous-ensemble fermé de [a, b]. On cherche p ∈ U qui minimise maxx∈Z |f(x)−p(x)|.

Theorème 4.1.1. f ∈ C([a, b]), p∗ ∈ U , ZM l’ensemble des points de Z dans lequel l’erreuratteint son maximum.

|f(x)− p∗(x)| = ‖f − p∗‖∞,ZAlors p∗ minimise l’expression maxx∈Z |f(x)−p∗(x)| dans U (p∗ est solution de la minimisationminp∈U ‖f − p‖∞,Z) si et seulement s’il n’existe pas de p ∈ U tel que :

e∗(x) = (f(x)− p∗(x))p(x) > 0, ∀x ∈ ZM (4.1)

Démonstration. (⇐) Supposons que p∗ n’est pas optimal :

∃p ∈ U , ∃θ > 0, |f(x)− (p∗(x)− θp(x))| < |f(x)− p∗(x)|, ∀x ∈ ZM⇒ (f(x)− p∗(x))p(x) > 0, ∀x ∈ Zn

et sgn(f(x)− p∗(x)) = sgn(p(x)), ∀x ∈ Zn.(⇒) Supposons que (4.1) est vérifiée. Il reste à montrer que, pour une valeur de θ,

maxx∈Z|f(x)− p∗(x)− θp(x)| < max

x∈Z|f(x)− p∗(x)|︸︷︷︸‖e∗‖∞,Z

.

50

Chapitre 4. Approximation en norme uniforme 51

Supposons sans perte de généralité que

|p(x)| ≤ 1, ∀x ∈ [a, b].

On définit l’ensembleZ0 = {x ∈ Z, p(x).e∗(x) ≤ 0},

on a ainsi Z0 ∩ ZM = ∅. Soitd = max

x∈Z0|e∗(x)|,

d < maxx∈Z|e∗(x)| (4.2)

Si Z0 = ∅ alors d = 0. Choissions

θ = 12

[maxx∈Z|e∗(x)| − d

]> 0.

Ainsi,Z est fermé ⇒ ∃ξ ∈ Z, |e∗(ξ)− θp(ξ)| = max

x∈Z|e∗(x)− θp(x)|

(i) Supposons ξ ∈ Z0

maxx∈Z|ex − x)− θp(x)| = |e∗(ξ)|+ θ|p(ξ)|

≤ d− 12d+ 1

2 maxx∈Z|e∗(x)|

< maxx∈Z|e∗(x)|

⇒ p∗ n’est pas meilleur approximant

(ii) Supposons ξ /∈ Z0 ⇒ p(ξ) et e∗(ξ) ont le même signe et

|e∗(ξ)− θp(ξ)| < max (|e∗(ξ), θ|p(ξ)|) ≤ maxx∈Z|e∗(x)|

⇒ p n’est pas meilleur approximant.Donc pour vérifier si on a un meilleur approximant, il suffit de regarder l’ensemble desvaleurs extrêmales de e∗.

4.2 Caractérisation de la meilleure approximation

Soit U = Pn. Si p ∈ Pn alors p a au plus n changements de signe. Donc si e∗(x) change designe plus de n fois dans ZM alors p∗ est la meilleure approximation.

Inversement, si le nombre de changement de signe de e∗ est ≤ n (aux points ηk, k = 1, ..., n)alors en choissant

p(x) =n∏k=1

(x− ηk)

on montre que p∗ n’est pas optimale.

Définition 4.2.1. U vérifie la condition de Haar si et seulement si ∀p ∈ U , p 6= 0 le nombrede racines de {p(x) = 0, a ≤ x ≤ b} est inférieure à la dimension de l’espace.

52 Chapitre 4. Approximation en norme uniforme

Remarque. Une définition de la condition de Haar est la suivante : « Si {φi}ni=0 base de U , ∀ξipour i = 0, ..., n où les ξi forment une subdivision de [a, b] (a ≤ ξ0 < ξ1 < ... < ξn ≤ b) alors lamatrice

[φi(ξj)

]ni,j=0

est inversible. »

Pour U = Pn,

[φi(ξj)] =

1 ξ0 · · · ξn01 ξ1 · · · ξn1... ... ...1 ξn · · · ξnn

.

Theorème 4.2.1 (Théorème de caractérisation). Soit U un espace de dimension n + 1 deC([a, b]) vérifiant la condition de Haar. Alors p∗ est la meilleure approximation minimax def ∈ C([a, b]) si et seulement il existe n + 2 points {ξ∗i , i = 0, ..., n + 1} tel que a ≤ ξ∗0 < ξ∗1 <... < ξ∗n+1 < b,

|f(ξ∗i )− p∗(ξ∗i )| = ‖f − p∗‖∞, i = 1, ..., n+ 1,f(ξ∗i+1)− p∗(ξ∗i+1) = −(f(ξ∗i )− p∗(ξ∗i )), i = 0, ..., n.

(4.3)

Démonstration. (⇒) Supposons l’existence des {x∗i , i = 0, ..., n+ 1} vérifiant (4.3),

∃ηi ∈]ξ∗i , ξ∗i+1[, f(ηi)− p∗(ηi) = 0, i = 0, ...n.

On a n+ 1 changement de signe p/e∗(x)⇒ p∗ optimal et condition de Haar.(⇒) p∗ meilleure approximation⇒ e∗ doit avoir au moins n+1 changement de signes (sinonsoient η1, ..., ηn les points de changement de signe, on peut construire p ∈ U qui a commeracines les ηi), ce qui permet de définir n+ 2 points ξ∗i vérifiant (4.3).

Preuve de minimalité des polynômes de Tchebychef, ‖p‖∞,[−1,1]

Rappel (Polynômes de Tchebychef). On définit le nième polynôme de Tchbeychef par

Tn(x) = 2xTn−1(x) + Tn−2(x),

sachant que les premies polynômes de Tchebychev sont

T0(x) = 1, T1(x) = x.

DoncTn(x) = 2n−1xn + · · · .

et∀x ∈ [−1, 1], Tn(x) = arccos θ où x = cos θ

Corollaire.arg

(minp∈Pn

max−1≤x≤1

|p(x)|)

= 12n−1Tn,

où p est de degré n et unitaire. On a ainsi ∀x ∈ [−1, 1], |Tn(x)| ≤ 1,

|Tn(x)| = 1⇔ | cosnθ| = 1.

Pour nθ = kπ, où k = 0, ...n,θk = kπ

n, k = 0, ..., n.

Chapitre 4. Approximation en norme uniforme 53

minc0,...,cn−1∈Rn

max−1≤x≤1

∣∣∣∣∣xn +n−1∑i=0

cixi

∣∣∣∣∣⇔ chercher le meilleur approximant dans Pn−1 en norme uniforme pour la fonction f(x) = xn

dans [−1, 1].

e(x) = xn +n−1∑i=0

cixi = 1

2n−1Tn(x).

On choisit ξ = cos(θn−i),

Tn(ξi) = (−1)i+1, ξ0 < ξ1 < ... < ξn

|Tn(ξ)| = 1 = ‖Tn‖∞,Tn(ξi+1) = −Tn(ξi).

Corollaire. U un sous-espace linéaire de C([a, b]) de dimension n+ 1 vérifiantla condition deHaar et a ≤ ξ0 < ξ1 < ... < ξn+1 ≤ b. Soit f ∈ C([a, b]). Alors p∗ ∈ U minimise

max0≤i≤n+1

|f(ξi)− p(ξi)|,

pour p ∈ U si et seulement si

f(ξi+1)− p∗(ξi+1) = − [f(ξi)− p∗(ξi)] , i = 0, ..., n.

Soit Z = {ξi, i = 0, ..., n+ 1}. La fonction p∗ peut être calculée par

h = f(ξ0)− p∗(ξ0)

On choisit une base pour l’espace {φi}ni=0,

p∗(x) =n∑j=0

λjφj(x),

les λj sont solution du système linéaire

f(ξi)−n∑j=0

λjφj(ξi) = (−1)ih, i = 0, ..., n+ 1.

Ce système a toujours une solution (qui est le meilleur approximant) pour tout f ⇒ la matricedu système à résoudre doit être inversible ⇒ la solution est unique.

4.3 Algorithme de calcul de Remez (exchange algorithm)Cet algorithme permet le calcul de p ∈ U (qui vérifie la condition de Haar) qui minimise

‖f − p‖∞ = maxx∈[a,b]

|f(x)− p(x)|.

C’est l’algorithme itératif qui génère un ensemble de points (ξi)n+1i=0 à chaque étape qui converge

vers {ξ∗i , i = 0, ..., n+ 1} vérifiant (4.3).Itération :

54 Chapitre 4. Approximation en norme uniforme

1) On part d’un ensemble {ξi,, i = 0, ..., n+ 1} et on calcule p ∈ U minimisant

max0≤i≤n+1

|f(ξi)− p(ξi)|,

en résolvant le système linéaire

f(ξi)− p(ξi) = (−1)ih, i = 0, ..., n

en posant h := f(ξ0)− p(ξ0). On sait que |h| ≤ ‖f − p∗‖ ≤ ‖f − p‖∞.2) On considère la fonction erreur

e(x) = f(x)− p(x)

et on calcule les abscisses des points extremaux, soit η tel que

|f(η)− p(η)| = ‖f − p‖∞

3) On caclule δ := |f(η)− p(η)| − |h|. Si η est suffisament petit alors on arrête l’algorithme car

‖f − p‖∞ ≤ ‖f − p∗‖∞ + δ,

4) sinon on échange l’ensemble de référence

{ξ∗i , i = 0, ..., n+ 1}.

Si on considère la fonction h(ξ0, ..., ξn) = |h|, le but de l’itération est d’augmenter la veleurde h le plus possible.

Documents

M315 : Analyse numérique et approximationObjectifsetplandecours 0.1 Objectifs →Approximationdefonctions,courbessurfaces,intégrales. →Déﬁnirenquelsensonconsidèrel’approximation