Universite catholique de Louvain Analyse numerique Approximation , interpolation , integration . INMA2171 2009 -2010 Alphonse Magnus, Institut de Mathematique Pure et Appliquee, Universite Catholique de Louvain, Chemin du Cyclotron,2, B -1348 Louvain-la-Neuve (Belgium ) (0)(10)473157 , alphonse.magnus@uclouvain.be , http://perso.uclouvain.be/alphonse.magnus/ et toujours: http://www.penombre.org/ INMA2171 2009-10 – 0 – Table – Table des m atieres. Preface. ..................................................7 Analyse numerique et theorie de l'approximation. ........ 11 1. Qu'est ce que l'analyse numerique? ................... 11 1.1. Analyse numerique et analyse ....................... 11 1.2. Analyse numerique et calcul ........................ 11 2. Theorie de l'approximation. .......................... 12 2.1. Les trois niveaux d'une theorie de l'approximation. .12 3. Quelques approximations de fonctions utilisees dans les calculatrices et les ordinateurs 13 3.1. Calculatrices scientifiques: le systeme CORDIC ..... 13 3.2. Approximations polynomiales et rationnelles ........ 14 3.3. AGM, etc ........................................... 15 3.4. Approximations et nombres irrationnels ............. 15 3.5. Approximations les plus simples: bien commencer .... 17 CHAPITRE 1. Theoremes generaux d'existence et d'unicite de meilleure approximation. 18 1. Distances et normes. ................................. 18 1.2. Exercices et exemples ...............................18 1.3. Remarques .......................................... 18 1.4. Normes ............................................. 19 1.5. Exemples, exercices ................................ 19 1.6. Exercices, exemples ................................ 20 1.7. Formes et applications lineaires continues sur des espaces vectoriels normes de fonctions 20 2. Existence d'une meilleure approximation. ........... . 21 2.1. Theoreme d'existence de meilleure approximation dans un sous-espace de dimension finie 21 2.2. Contre-exemple ..................................... 22 2.3. Remarque ........................................... 22 3. Unicite de la meilleure approximation. ............... 22 3.1. Definition. Convexite .............................. 22 3.2. Proposition ........................................ 22 3.3. Definition ......................................... 23 3.4. Une condition suffisante d'unicite. Theoreme ....... 23 3.5. Exercice ........................................... 23 4. Continuite du projecteur de meilleure approximation. ..23 4.1. Theoreme de continuite ............................. 23 4.2. Forte unicite ...................................... 24 5. Dualite. ............................................. 24 6. Exemples et exercices. ............................... 24 6.2. Moyenne et mediane ................................. 25 6.3. Principaux sous-espaces de fonctions utilises en approximation . . . . . . . . . . . . . . . . 25 6.4. Centre et rayon de Tchebycheff d'une partie P de X ..26 6.5. Largeurs de Kolmogorov ............................. 26 6.6. Coapproximation .................................... 26 CHAPITRE 2. Approximation au sens de Tchebycheff. ....... 27 1. Theoreme d'equioscillation de Tchebycheff. ........... 27 1.1. Theoreme d'equioscillation de Tchebycheff (1853) ... 27 1.2. Preuve de la condition necessaire: p^optimal dans Pn 28 1.3. Preuve de la condition suffisante (3) -> p^optimal dans Pn .................. .. 29 1.4. Exemple ....................................... .... 29 1.5. Theoreme d'unicite de la meilleure approximation polynomiale au sens de Tchebycheff 29 2. Proprietes de la meilleure approximation. ............ 30 2.1. Symetrie. Theoreme ................................. 30 2.2. Theoreme (de La Vallee Poussin) .................... 30 2.3. Unicite forte ...................................... 31 2.4. Signes alternes .................................... 31 2.5. Algorithme d'echange ............................... 32 2.6. Meilleure approximation au sens sur un compact quelconque ............ 33 3. Polyn^omes de Tchebycheff. ........................... 34 3.1. Meilleure approximation d'un polyn^ome de degre n dans Pn-1 . .............. 34 3.2. Definition ......................................... 34 3.3. Premieres proprietes ............................... 34 3.4. Premiers echantillons .............................. 36 3.5. Exercice ........................................... 38 3.6. Relation de recurrence ......................... ... 38 3.7. Polyn^ome de moindre norme sur un intervalle, sous contrainte p(0) = 1 ...... .. 39 3.8. Meilleure approximation d'un polyn^ome de degre n dans Pn-2 .. .............. 39 3.9. Meilleure approximation de fonction rationnelle .... 39 3.10. Fonctions rationnelles de moindre et plus grande deviation . . . . . . . . . . . . . . . . . . . 39 3.11. Proprietes extremales des polyn^omes de Tchebycheff 40 3.12. Autres proprietes des Tn .......................... 43 3.13. Equation differentielle lineaire .................. 46 3.14. Proposition ....................................... 46 3.15. Polyn^omes de Tchebycheff et problemes de Sturm-Liouville . . . . . . . . . . . . . . . . . . 47 3.16. Coecients, derivees et primitives ........................................... 48 Tn (x) 3.17. Primitives iterees de et formule de Rodrigues ....................... 49 2 p1 - x INMA2171 2009-10 – 0 – Table – 4 3.18. Orthogonalite et base duale de P N . .......................................... 50 4. Bonne approximation; series de polyn^omes de Tchebyche , relation avec series de Fourier. 53 4.1. Bonne base et bonne approximation ........................................... 53 4.2. Cascade de meilleures approximations et developpements dans la base des polyn^omes de Tchebyc 54 4.3. Serie de Fourier d'une fonction continue periodique ............................ 55 4.4. Series de polyn^omes de Tchebycheff ........................................... 56 4.5. Vitesse de decroissance des coecients et bornes de norme de fonction d'erreur 59 4.6. Theoreme de Weierstrass ...................................................... 61 4.7. Calcul des coecients de Tchebycheff et autres algorithmes . . . . . . . . . . . . . . . . . . . 62 4.8. Algorithmes en representation de Tchebycheff ................................. 65 5. Approximation par fonction rationnelle. ......................................... 66 6. Lecture. Tchebycheff et de La Vallee Poussin ................................... 67 CHAPITRE 3. Approximation en moyenne quadratique. ............................. 72 1. Produit scalaire, orthogonalite, espace prehilbertien. ............................ 72 1.1. Produits scalaires sur Pn ..................................................... 72 1.2. Espace prehilbertien .......................................................... 75 2. Meilleure approximation dans un espace prehilbertien. .......................... 75 2.1. Base d'un espace de dimension nie, matrice de Gram ......................... 75 2.2. Meilleure approximation = projection orthogonale ............................ 76 2.3. Methode d'orthogonalisation de Gram-Schmidt ................................ 79 2.4. Hauteurs, volumes et determinants de Gram .................................. 80 2.5. Factorisation de Cholesky ..................................................... 81 3. Polyn^omes orthogonaux. ........................................................ 82 3.1. Construction d'une base orthogonale de Pn ................................... 83 3.2. Relation de recurrence ........................................................ 86 3.3. Quelques algorithmes utilisant la recurrence ................................... 87 3.4. Zeros des polyn^omes orthogonaux ............................................. 91 3.5. Zeros de polyn^omes orthogonaux et valeurs propres de matrices tridiagonales symetriques 92 3.6. Formules d'integration de Gauss. Premiere approche .......................... 94 3.7. Formule d'integration de Gauss et fractions continues ......................... 97 3.8. Formule de Christo el-Darboux ............................................... 98 3.9. Orthogonalite et operateurs (formellement) hermitiens . . . . . . . . . . . . . . . . . . . . . . . . 99 3.10. Polyn^omes orthogonaux classiques ........................................... 100 3.11. Usages et varietes de polyn^omes orthogonaux ................................ 104 3.12. Harmoniques spheriques et fonctions de Legendre ............................ 107 3.13. Polyn^omes d'Hermite et mecanique quantique ................................110 3.14. Orthogonalite et equioscillation .............................................. 111 4. Moindres carres, regression. .....................................................112 5. Approximation en norme kk1 . ................................................. 116 6. Series de Fourier en analyse numerique. ......................................... 117 6.1. Comportement des coecients ................................................ 119 6.2. Transformee de Fourier discrete ............................................... 121 6.3. Tranformee de Fourier rapide (Fast Fourier Transform FFT) . . . . . . . . . . . . . . . . . . 122 INMA2171 2009-10 – 0 – Table – 6.4. Analyse en ondelettes ......................................................... 125 7. Convergence, espace de Hilbert ................................................. 128 7.1. Suites totales et maximales ................................................... 128 7.2. Theoreme. .................................................................... 129 7.3. Exemples de suites totales dans C [a, b] et L2 ([a, b];). .........................130 7.4. Theoreme d'approximation de Weierstrass. ................................... 130 7.5. Theoreme de Stone-Weierstrass ............................................... 134 7.6. Noyaux reproduisants, polyn^omes noyaux, representants de Riesz . . . . . . . . . . . . . . 136 7.7. Intervalles non bornes, probleme des moments. ................................ 138 7.8. Arcs de Bezier en typographie informatique ................................... 139 CHAPITRE 4. Interpolation et applications. .........................................142 1. Interpolation. ...................................................................142 1.1. Interpolation polynomiale classique ........................................... 143 1.2. Interpolation: cadre general ...................................................145 1.3. Interpolation polynomiale classique en formulation de New ton, di erences divisees. 149 1.4. Extrapolation a la limite de Richardson ....................................... 151 1.5. Formulation de New ton en general ............................................ 151 1.6. Di erences divisees et derivees ................................................ 153 1.7. Reste de l'interpolation polynomiale classique ................................. 156 1.8. Interpolation d'Hermite-Fejer ................................................. 157 2. Formules d'integration basees sur l'interpolation. ................................158 2.1. Reste de la formule de quadrature de Gauss ...................................158 2.2. Formules de quadratures de Gauss avec points imposes ........................ 159 2.3. Points de Tchebyche : regle de Clenshaw -Curtis .............................. 160 2.4. Regles adaptatives d'integration ...............................................161 3. Representation du reste: theoreme de Peano. ................................... 161 3.1. Theoreme (Peano) ............................................................ 162 CHAPITRE 5. Di erences nies. .................................................... 164 1. Les operateurs du calcul aux di erences. ........................................ 164 2. Interpolation. ...................................................................167 3. Derivation. ..................................................................... 168 4. Integration. .....................................................................169 4.1. Formules de New ton-Cotes .................................................... 169 5. Noyaux de Peano de regles d'integration. ....................................... 170 5.1. Formule du trapeze ........................................................... 170 5.2. Formule de Simpson .......................................................... 171 5.3. Noyaux de Peano de formules composees ...................................... 171 5.4. La formule de Simpson avant Simpson ....................................... 172 6. Formule d'Euler-Maclaurin. .................................................... 173 6.1. Identites des nombres et polyn^omes de Bernoulli .............................. 175 6.2. Schema d'integration de Romberg. ............................................ 178 6.3. Formule d'Euler-Maclaurin en tant que formule sommatoire . . . . . . . . . . . . . . . . . . . 179 CHAPITRE 6. Recapitulation. ...................................................... 183 INMA2171 2009-10 – 0 – Table – CHAPITRE 7. Appendices: alphabets grec, cyrillique, petit dico, index. . . . . . . . . . . . . . 184 1. Alphabets ...................................................................... 184 2. Petit dico mathematical English . francais mathematique. .....................185 Index ................................................................................. 186 INMA2171 2009-10 – 0 – Bib – Prefac e. L'analyse numerique a longtemps ete incorporee au cours d'analyse generale, dont elle representait le versant applique et constructif. Le fort developpement des moyens de calcul automatique a rendu necessaire l'apparition d'un enseignement speci que. La discipline put se developper sous l'impulsion de mathematiciens avises, tels P. Henrici [H en ] et E. Stiefel [S ti]. Le present cours fut cree par Jean M einguet, Professeur al'Universite. On trouvera ici l'essentiel de la partie “ approximation, interpolation, integration” de son enseignement. D'autres cours reprennent les themes de resolution numeriques des equations (y compris di erentielles et fonctionnelles), d'algebre lineaire numerique (theorie des matrices) et d'algorithmique numerique. Le Professeur Meinguet est egalement a l'origine de l'enseignement de la programmation  et de l'informatique dans notre universite, mais cela est une autre histoire. . . Les grands principes de la theorie de l'approximation sont d'abord deduits de concepts d'analyse fonctionnelle (chap. 1). Ces resultats sont alors appliques a des situations plus concretes: on examine en detail l'approximation par des polyn^omes et par des polyn^omes trigonometriques, selon la norme du maximum (chap. 2) et en moyenne quadratique (chap. 3). Avec l'interpolation (chap. 4) et le calcul aux di erences nies (chap. 5), on dispose des outils permettant de traiter tous les problemes de l'analyse numerique classique, en particulier l'integration numerique.