Mathematiques assistees par ordinateur Chapitre Approximation polynomiale

De
Publié par

Mathematiques assistees par ordinateur Chapitre 7 : Approximation polynomiale Michael Eisermann Mat249, DLST L2S4, Annee 2008-2009 www-fourier.ujf-grenoble.fr/˜eiserm/cours _ mao Document mis a jour le 6 juillet 2009 1/23

  • approximation polynomiale

  • norme uniforme

  • polynomes orthogonaux

  • methode de calcul efficace

  • questions d'approximation

  • retour sur l'interpolation de lagrange theoreme

  • riche theorie des polynomes orthogonaux

  • theoreme de weierstrass

  • interpolation de lagrange


Publié le : mardi 19 juin 2012
Lecture(s) : 39
Source : www-fourier.ujf-grenoble.fr
Nombre de pages : 23
Voir plus Voir moins
Math´ematiquesassist´eesparordinateur Chapitre 7 : Approximation polynomiale
Michael Eisermann
Mat249, DLST L2S4, Anne´ e 2008-2009 www-fourier.ujf-grenoble.fr/˜eiserm/cours # mao Documentmis`ajourle6juillet2009
/123
Objectifs de ce chapitre Ce chapitre initie aux questions d’approximation d’une fonction continuedonn´eepardespolynoˆmes.Cestunevasteth´eorieque nous n’esquisserons ici que superficiellement. Par rapport `a la norme uniforme, nous e´ tudions l’interpolation de Lagrange, qui est analogue a` l’approximation de Taylor. Dans les deuxcasdesph´enome`nesdenon-convergencesontpossibleset doiventˆetreconnus`atitredavertissement. Fortheureusement,lethe´or`emedeWeierstrassassurequetoute fonction continue f : [ a, b ] R peuteˆtreuniformementapproch´ee pardespolynˆomes P n , de sorte que k f P k 0 pour n → ∞ . Nous e´ nonc¸ ons ici la formulation constructive due a` Bernstein. Algorithmiquement,lanormequadratiquesav`ereplusavantageuse: elleprovientdunproduitscalaireetpermetdescalculstr`esefcaces. Nousmentionnonsicilaricheth´eoriedespolynoˆmesorthogonaux. 2/23
Sommaire
1
2
Approximation polynomiale et norme uniforme InterpolationdeLagrange,diffe´rencesdivis´ees Majoration de l’erreur, phe´ nome` ne de Runge Th´eor`emedeWeierstrass,polynoˆmesdeBernstein
Polynoˆ mes orthogonaux et norme quadratique Approximations uniforme, en moyenne, et quadratique Produit scalaire, orthonormalisation selon Gram–Schmidt Meilleure approximation pour la norme quadratique
3/23
Retour sur l’interpolation de Lagrange Th ´ ` (interpolation de Lagrange) eoreme ´ Etant donne´ s des points distincts x 0 , . . . , x n R et des valeurs arbitraires y 0 , . . . , y n R ,ilexisteununiquepolynˆome P R [ X ] dedegr´e n v´eriant P ( x k ) = y k pour tout k = 0 , . . . , n , `a savoir n X x j P = X y k Y . k =0 j 6 = k x k x j On l’appelle le polynoˆ me interpolateur de L d ´ agrange onne par x 0 , . . . , x n et y 0 , . . . , y n , ou passant par ( x 0 , y 0 ) , . . . , ( x n , y n ) . Cer´esultatestvalablesurtoutcorps:mˆfoule,meˆm eme rm e preuve. Calcul pratique. Noussouhaitonsunem´ethodedecalculefcace. ´ Approximation. Etant donne´ s n + 1 points distincts x 0 , . . . , x n [ a, b ] , on peut approcher toute fonction f : [ a, b ] R par l’unique polynome ˆ P dedegr´e n donne´par x 0 , . . . , x n et y k = f ( x k ) pour k = 0 , . . . , n . Par construction on a P ( x ) = f ( x ) pour tout x ∈ { x 0 , . . . , x n } . Pour x [ a, b ] nous souhaitons majorer l’e´ cart | P ( x ) f ( x ) | . § 1.1 4/23
§.1
Diff´erencesdivis´´´ ees : enonce
1
Le polynoˆ me interpolateur de f en x 0 , . . . , x n peuts´ecrirecomme
P = a 0 + a 1 ( X x 0 ) + . . . + a n ( X x 0 ) ∙ ∙ ∙ ( X x n 1 ) .
Cette´ecriturepermetdel´evaluerefcacementa`laHorner: P ( x ) = a 0 + ( x x 0 ) a 1 + . . . ( x x n 2 ) a n 1 + ( x x n 1 ) a n . . . .
Ceci ne ne´ cessite que n soustractions, n additions, n multiplications. Mais comment calculer efficacement les coefficients a 0 , a 1 , . . . , a n ? On observe que a 0 = f ( x 0 ) et a 1 = f ( xx 11 ) fx ( 0 x 0 ) . Par re´ currence ond´enitles diffe´ rences divise´ es par f [ x i ] := f ( x i ) puis . . . , x i + k 1 ] f [ . . , x i + k ] := f [ x i +1 , . . . , x i x + ik + ] k f [ xx ii , x i , . .
The´ore`me Nous avons a k = f [ x 0 , . . . , x k ] pour tout k = 0 , . . . , n .
/532
§1.D1fif´renecesidvis´ees:algortimhe
e´ tape 2
etape 0 etape 1 ´ ´ ff (( x 0 )) &f [ x f ( xx 21 ) &f [ x 01 ,,xx 12 ]] →& f [ x 0 , x 1 , x 2 ]
. . .
e´ tape n
x . n 2 ) &f . . fff ((( xx nn ) 1 ) &&ff [[ xx [ x nnn 23 ,, 1 ,xxx nnn ] 21 ]] && ff [ x [ x nn 3 , 2 ,xx nn 2 , 1 ,xx nn ] 1 ] &f [ x 0 , . . . , x n ]
Algorithme 1 calcul des diffe´ rences divise´ es Entr´ee: les points x 0 , . . . , x n et les valeurs y 0 , . . . , y n ou` y k = f ( x k ) Sortie: les coefficients a 0 , . . . , a n comme spe´ cifie´ s ci-dessus pour k de 0 `a n faire a k y k fin pour pour i de 1 `a n faire pour k de n `a i faire a k ax kk ax kk 1 i fin pour fin pour retourner a 0 , . . . , a n
re´ sultat a 0 a 1 a 2
a n 2 a n 1 a n
/632
§1.
Diff´erencesdivis´ees:d´emonstration On va prouver la formule a k = f [ x 0 , . . . , x k ] par re´ currence sur k . L´enonce´estvraiaurang k = 0 car a 0 = f ( x 0 ) = f [ x 0 ] . Supposons l’e´ nonce´ vrai au rang k 1 et prouvons-le au rang k . Soit P k 1 lepolynˆomeinterpolateurde f en x 0 , . . . , x k 1 et soit Q k 1 le polynoˆ me interpolateur de f en x 1 , . . . , x k . Alors P ( X x 0 ) Q k 1 ( X x k ) P k 1 k = x k x 0 verifie P k ( x 0 ) = f ( x 0 ) , . . ., P k ( x k ) = f ( x k ) . C’est donc le polynoˆ me ´ interpolateur de f en x 0 , . . . , x k .Onend´eduitque
1
k = d m P k = dom Q k 1 dom P k 1 a o x k x 0 f [ x 1 , . . . , x k x ] f [ xx 0 , . . . , x k 1 ] f [ x 0 , . . . , x k ] . = = k 0
Ceciprouvelaformulesouhait´ee. Remarque. Puisque P k est unique et dom P k = f [ x 0 , . . . , x k ] , cette valeur est inde´ pendante de l’ordre des points x 0 , . . . , x k .
7/23
§1.
Interpolation et approximation : exemple On conside` re la fonction f : [ 1 , +1] R donn´eepar f ( x ) = 1+1 x 2 . La graphique trace f (noir)ainsiquetroispolynˆomesinterpolateurs:
2
P 2 (rouge) interpole en 1 , 0 , +1 , 1 − − P 4 (vert) interpole en 1 , 2 , 0 , + 21 , +1 , P 8 (bleu) interpole en 1 , 34 , 12 , 14 , 0 , + 14 , + 21 , + 43 , +1 . Si P 2 est encore loin, P 4 approche f de´ja`assezbiensur [ 1 , +1] . Les graphes de f et P 8 semblentcoı¨ncider(pourcettere´solution). ` A noter toutefois que l’erreur explose en dehors de [ 1 , +1] .
/832
§.1
Interpolation et approximation : exemple Pourmieuxvisualiserl´ecartentre f et P 8 il est beaucoup plus informatifdafcherladiff´erence f P 8 pour pouvoir « zoomer » :
2
Graphiquement on voit que | f P 8 | ≤ 0 . 0025 sur [ 1 , +1] . Onremarquequelerreurestlaplusgrandeprochedesextr´emite´s. Dans la suite nous allons prouver et quantifier ces observations.
9/23
´ Ecart entre une fonction et son polynoˆ me interpolateur Th´eor`eme Soit f : [ a, b ] R une fonction n + 1 foisd´erivable. Soient x 0 , . . . , x n [ a, b ] des points distincts de cet intervalle. Soit P lepolynˆomeinterpolateurdonne´parles x k et y k = f ( x k ) . Pour tout x [ a, b ] il existe ξ [ a, b ] (qui de´ pend de x ) tel que : f ( n +1) ( ξ ) Y n ( x x k ) . f ( x ) P ( x ) = ( n + 1)! k =0 Ainsi l’erreur | f ( x ) P ( x ) | de´ pend d’une majoration de | f ( n +1) | mais aussi de la disposition des points x j parrapport`a x . Par exemple, si les points x 0 , . . . , x n sont ´equidistants , le terme | Q nk =0 ( x x k ) | est plus grand pre` s du bord de I qu’au centre de I . Un choix judicieux des points x 0 , . . . , x n , plus dense aux extre´ mites, ´ donnera une meilleure approximation : points de Tchebychev . J.-P. Demailly, Analysenum´eriqueet´equationsdiffe´rentielles , EDP Sciences, Grenoble 2006 (3e e´ dition), chapitre 2 § 1.2 10/23
D´emonstrationduth´eor`eme Pour x ∈ { x 0 , . . . , x n } le´galit´eestvraie,inde´pendammentde ξ . f ( x ) P ( x ) f ( n +1) ( ξ ) n =( n + 1)! k Y ( x x k ) . =0 Nous fixons x / ∈ { x 0 , . . . , x n } et posons C := Q f k ( n x =0 )( xP ( xx k )) . Conside´ rons la fonction : n g ( t ) = f ( t ) P ( t ) C Y ( t x k ) . k =0 Elle s’annule pour t ∈ { x 0 , . . . , x n , x } , donc en au moins n + 2 points. Par conse´ quent g 0 s’annule en au moins n + 1 points de [ a, b ] . Ensuite g 00 s’annule en au moins n points de [ a, b ] , etc. . . Finalement g ( n +1) s’annule au moins une fois dans [ a, b ] . Or, g ( n +1) ( t ) = f ( n +1) ( t ) C ( n + 1)! On conclut qu’il existe ξ [ a, b ] tel que C = f ( ( n n + + 1 1 ) )(! ξ ) . § 1.2 11/23
Soyez le premier à déposer un commentaire !

17/1000 caractères maximum.