Click here to load reader

M315 : Analyse numérique et approximation

  • View
    847

  • Download
    10

Embed Size (px)

DESCRIPTION

Notes de CoursM315 : ANALYSE NUMERIQUE ET APPROXIMATIONClément BoulonneWeb : http://clementboulonne.new.frMail : [email protected]é des Sciences et Technologies de LilleU.F.R de Mathématiques Pures et AppliquéesLicence de Mathématiques — Semestre 62008 - 2009

Text of M315 : Analyse numérique et approximation

Universit des Sciences et Technologies de LilleU.F.R. de Mathmatiques Pures et AppliquesM315 : Analyse numrique etapproximationNotes de cours par Clment BoulonneL3 Mathmatiques 2008 - 2009Table des matiresObjectifs et plan de cours 40.1 Objectifs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40.2 Plan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40.3 Bibliographie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 Approximation par des fonctions splines 51.1 Rappel sur linterpolation polynomiale . . . . . . . . . . . . . . . . . . . . . . . 51.1.1 Existence et unicit du polynme dinterpolation . . . . . . . . . . . . . . 51.1.2 Formule de Lagrange du polynme dinterpolation . . . . . . . . . . . . . 61.1.3 Base de Newton - Dirences divises . . . . . . . . . . . . . . . . . . . . 61.1.4 Formule de lerreur dinterpolation . . . . . . . . . . . . . . . . . . . . . 71.1.5 Quelques problmes dinterpolation polynmiale. . . . . . . . . . . . . . 71.2 Fonctions splines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81.3 Splines cubiques interpolants . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91.4 Proprit extremale des splines de degr impair . . . . . . . . . . . . . . . . . . 131.5 La base des B-splines. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141.6 Estimation de lerreur . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 181.7 Courbes splines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 221.7.1 Dnitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 221.7.2 Courbe ouverte . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 231.7.3 Courbes ferms priodiques . . . . . . . . . . . . . . . . . . . . . . . . . 261.7.4 Algorithme dvaluation de De Boor-Cox. . . . . . . . . . . . . . . . . . 282 Approximation au sens des moindres carrs 292.1 Meilleure approximation dans un espace norm . . . . . . . . . . . . . . . . . . 292.1.1 Premiers rsultats . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 292.1.2 Unicit de la meilleure approximation . . . . . . . . . . . . . . . . . . . . 302.2 Meilleure approximation dans un espace prhilbertien. . . . . . . . . . . . . . . 312.2.1 Algorithme de Gram-Schmidt . . . . . . . . . . . . . . . . . . . . . . . . 342.2.2 Approximation une prcision donne . . . . . . . . . . . . . . . . . . . 353 Polynmes orthogonaux et formules de quadrature 373.1 Quelques proprits des polynmes orthogonaux. . . . . . . . . . . . . . . . . . 373.2 Exemples de familles de polynmes orthoognaux . . . . . . . . . . . . . . . . . . 403.3 Formule de quadrature . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 413.3.1 Formules de quadrature interpolatoire . . . . . . . . . . . . . . . . . . . . 423.3.2 Mthodes composites. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 453.3.3 Formules de quadrature de Gauss . . . . . . . . . . . . . . . . . . . . . . 46234 Approximation en norme uniforme 504.1 Rduction de lerreur dune approximation . . . . . . . . . . . . . . . . . . . . . 504.2 Caractrisation de la meilleure approximation . . . . . . . . . . . . . . . . . . . 514.3 Algorithme de calcul de Remez (exchange algorithm) . . . . . . . . . . . . . . . 53Objectifs et plan de cours0.1 ObjectifsApproximation de fonctions, courbes surfaces, intgrales.Dnir en quel sens on considre lapproximation.Donner les algorithmes pour construire les approximations.Estimation derreurs.Dnir les espaces o on cherche lapproximation.0.2 Plan1)Approximation de fonctions et de courbes par des fonctions splines (polynomial par mor-ceaux). Algorithmes de calcul, estimations derreurs.2)Meilleure approximation dans lespace norm, les espaces dHilbert, au sens des moindrescarrs.3)Polynmes orthogonaux. Application au calcul dintgrales.4)Meilleure approximation uniforme (L), existence, unicit, caractrisation de la meilleureapproximation. 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 numrique et quations direntiel les, Grenoble Sciences,20064)Carl de Boor : A Practical Guide to Splines4Chapitre 1Approximation par des fonctionssplines1.1 Rappel sur linterpolation polynomialeEtant donnes x0, x1, ..., xn R distincts et les valeurs f(x0), f(x1), ..., f(xn). Il existe un etun seul polynmepn de degr n tel que :pn(xi) = f(xi),i = 0, ..., n1.1.1 Existence et unicit du polynme dinterpolationOn aura donc :pn(x) = a0 + a1x + ... + anxnLes conditions dinterpolation se resument par la rsolution du systme linaire suivant :

1 x0x20 xn01 x1x21 xn1.........1 xnx2n xnn

. .. .Matrice de Vandermonde

a0a1...an

=

f(x0)f(x1)...f(xn)

. .. .n+1 quations n+1 inconnus()Soit : = det A =0j k s est un polynme de degr k. On doit avoir m < k. Donc on va considrerm = k.1.2 Fonctions splinesDnition 1.2.1.n, k des entiers 1, t0< t1< ... < tn noeuds de la subdivision. On considreok = ok(t0, t1, ..., tn) lespace des fonctionss : [t0, tn] R de classe (k1([t0, tn]) et telles que :s[[tj1,tj] {k,j = 1, ..., nest un espace vectoriel (sous-espace vectoriel de (k1([a, b])).Lemme 1.2.1. On considre lesn + k fonctions suivantes :

pj(x) = (x t0)j,j = 0, ..., kj(x) = (x tj)k+ =

(x tj)ksix tj0 six < tj,j = 1, .., n 1pjj=0,...,k jj=1,...,n forment une base ok(t0, ..., tn) et donc dim(ok) = n + k.s ok,s(x) =kj=0ajpj(x) +n1j=1bjj(x)avec :aj =s(j)(t+0 )j!etbj =s(k)(t+j ) s(k)(tj )k!Chapitre 1. Approximation par des fonctions splines 9Dmonstration. Les fonctions appartiennent ok :(i)vident pourpj(ii) (l)j(tj ) = 0, l,(l)j(t+j ) = 0, l k 1 et(k1)j(t+j ) = k!.Il sut de montrer que : s ok, !a0, ..., ak, b1, ..., bn1 tel que :s =kj=0ajpj +n1j=1bjjOn procde par rccurence surn. Pourn = 1, ok(t0, t1) = p[[t0,t1],p {k. p0, ..., pk est labase de Taylor. Supposons vrai pourn 1. Soits ok(t0, ..., tn),s[[t0,tn1] ok(t0, ..., tn1) etpar rccurence :!a0, ..., ak, b1, ...bn2,s[[t0,tn1] = s(x) =kj=0ajpj(x) +n2j=1bjj(x)Au voisinage detn1, s etn1 (k1et s (k. b R, l= 0, ..., k 1, on considre :(s s bn1)(l).(t+n1) = (s s)(l)(tn1) = 0l = k :(s s bn1)(k)(t+n1) = s(k)(t+n1) s(k)(t+n1) bk! (1.1)= s(k)(t+n1) s(k)(tn1) bk! (1.2)= s(k)(t+n1) s(k)(tn1) bk! (1.3)Le passage de (1.1) (1.2) sexplique par s (ket (1.2) (1.3) pars = s[[t0,tn1].Sur [tn1, tn],p = s s bn1 est un polynme de degrk tel que :

p(l)(t+n1) = 0,l = 0, ..., k 1p(k)(t+n1) = 0 pourb = bn1avec :bn1 =s(k)(tn1s(k)(tn1)k!bn1 est choisi tel que (1.3) = 0. Donc :p = 0 s(x) = s(x) + bn1n1(x),x [tn1, tn]Vrai pour [t0, tn].1.3 Splines cubiques interpolantsOn considre le cas ok = 3.Theorme1.3.1. Pourtoutefonctionf, il existes o3(t0, ..., tn)vriantlesconditionsdinterpolation.s(ti) = f(ti),i = 0, ..., nDe plus,s est unique si on impose :(a)les valeurs des

(t0) ets

(tn)10 Chapitre 1. Approximation par des fonctions splinesou(b)les valeurss

(t0) ets

(tn).Si de plus,f (2([a, b]) et si :(a) s

(t0) s

(tn) = 0, splines naturel les.ou(b) s

(t0) = f

(t0) ets

(tn) = f

(tn),Alors :|s

|L([a,b]) = max[a,b] [s

(x)[ 3|f

|L([a,b])Remarque. dimo3(t0, ..., tn) = n+3. On a n+1 conditions dinterpolation et 2 autres conditions((a) et (b)).Dmonstration pour le cas (a). On notesj=s(tj) =f(tj) =fj(pourj = 0, ..., n). On noteaussi s

j=s

(tj) et tj=tj+1 tj. commes o3alorss (2et doncs

est linaire parmorceaux. Donc pourx [tj, tj+1],s

(x) = s

jtj+1xtj+1tj+ s

j+1x tjtj+1tjSi on intgre deux fois la fonctions

:s

(x) = s

j(tj+1x)22tj+ s

j+1(x tj)22tj+ j(1.4)s(x) = s

j(tj+1x)36tj+ s

j+1(x tj)36tj+ j(x tj) + jIci, on a utilis que s est un polynme de degr 3 par morceaux et que s (2. On utilise ensuiteles conditions dinterpolation :sj = fj et la continuit :fj = s

jt2j6+ j(1.5)fj+1 = s

j+1t2j6+ jtj + j(1.6)De (1.5), on dtermine lesj et de (1.6), lesj. Reste imposer que :s

(t+j ) = s

(tj ),j = 1, ..., n 1 (1.7)Pour calculers

(tj ), on considre (1.4) sur lintervalle [tj1, tj] ets

(t+j ), on considre (1.4) surlintervalle [tj, tj+1].s

(t+j ) = s

jtj2+ j(1.8)On fait (1.5) (1.6) quon diviser par tj :fj+1fjtj= [tj, tj+1]f s

j+1tj6s

jtj6+ jRappel. [tj, tj+1]fest la dirence divise au pointstj, tj+1 def.Chapitre 1. Approximation par des fonctions splines 11Donc (1.8) devient :s

(t+j ) = s

jtj2s

j+1tj6+ s

jtj6+ [tj, tj+1]fPours

(tj ) :s

(tj ) = s

jtj12+ j1 = s

jtj12s

jtj16s

j1tj16+ [tj1, tj]fDonc (1.7) scrit :tj16s

j1 + tj1 + tj3s

j + tj6s

j+1 = [tj, tj+1]f [tj1, tj]f12tj1tj1 + tj. .. .1js

j1 + s

j + 12tjtj+1 + tj. .. .js

j+1 = 3[tj1, tj, tj+1]f12(1 j)s

j1 + s

j + 12js

j+1 = 3[tj1, tj, tj+1],j = 1, ..., n 1On a xs

0 ets

n. On a alors rsoudreAX = Y:

112112(1 2) 1122.........12(1 n) 1

s

1s

2...s

n1

=

3[t0, t1, t2]f 12(1 1)s

03[t1, t2, t3]f...3[tn3, tn2, tn1]f3[tn2, tn1, tn]f 12ns

n

Il reste montrer queA inversible,Y= 0 X = 0. Soit :[xp[ = |X| =max1jn[xj[, 1 p n 1

1 p2xp1 + xp +p2 xp+1

= [yp[|x| = [xp[ [yp[ + 1 p2[xp+1[ +p2 [xp[ |y| + 12|x||x|2 |y| |x| 2|y| (y = 0 x = 0) A inversible solution unique.|s

|L[t0,tn] max0jn1maxx[tj,tj+1][s

j[

tj+1xtj

+[s

j+1[

x tjtj

max1jn[s

j[ = |x| 2|y||y| = 3 max1jn1[[tj1, tj, tj+1]f. .. .f

(j)2carfC2 32|f

Search related