| Universite catholique de Louvain Analyse numerique 1a Approximation, interpolation, integration. MATH2171 2003-2004 Alphonse Magnus, Institut de Mathematique Pure et Appliquee, Universite Catholique de Louvain, Chemin du Cyclotron,2, B-1348 Louvain-la-Neuve (Belgium) magnus@anma.ucl.ac.be , http://www.math.ucl.ac.be/~magnus/ Table des matieres. Preface. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 Bibliographie . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 Analyse numerique et theorie de l'approximation. . . . . . . . . . 9 1. Qu'est ce que l'analyse numerique? . . . . . . . . . . . . . . . 9 1.1. Analyse numerique et analyse . . . . . . . . . . . . . . . . . 9 1.2. Analyse numerique et calcul . . . . . . . . . . . . . . . . .. 9 2. Theorie de l'approximation. . . . . . . . . . . . . . . . . . . 10 2.1. Les trois niveaux d'une theorie de l'approximation. . . . . . 10 3. Quelques approximations de fonctions utilisees dans les calculatrices et les ordinateurs 11 3.1. Calculatrices scientifiques: le systeme CORDIC . . . . . . . 11 3.2. Approximations polynomiales et rationnelles . . . . . . . . . 12 3.3. AGM, etc . . . . . . . . . . . . . . . . . . . . . . . . . .. 13 3.4. Approximations et nombres irrationnels . . . . . . . . . . .. 13 3.5. Approximations les plus simples: bien commencer . . . . . . . 14 CHAPITRE 1. Theoremes generaux d'existence et d'unicite de meilleure approximation. 15 1. Distances et normes. . . . . . . . . . . . . . . . . . . . . .. 15 1.1. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 1.2. Exercices et exemples . . . . . . . . . . . . . . . . . . . . 15 1.3. Remarques . . . . . . . . . . . . . . . . . . . . . . . . . . 15 1.4. Normes . . . . . . . . . . . . . . . . . . . . . . . . . . .. 16 1.5. Exemples, exercices . . . . . . . . . . . . . . . . . . . . . 16 1.6. Exercices, exemples . . . . . . . . . . . . . . . . . . . . . 17 1.7. Formes et applications lineaires continues sur des espaces vectoriels normes de fonctions 17 2. Existence d'une meilleure approximation. . . . . . . . . . .. . 18 2.1. Theoreme d'existence de meilleure approximation dans un sous-espace de dimension finie 18 2.2. Contre-exemple . . . . . . . . . . . . . . . . . . . . . . . .19 2.3. Remarque . . . . . . . . . . . . . . . . . . . . . . . . . . .19 3. Unicite de la meilleure approximation. . . . . . . . . . . . . .19 3.1. Definition. Convexite . . . . . . . . . . . . . . . . . . . . 19 3.2. Proposition . . . . . . . . . . . . . . . . . . . . . . . . . 19 3.3. Definition . . . . . . . . . . . . . . . . . . . . . . . . . .19 3.4. Une condition su#sante d'unicite. Theoreme . . . . . . . . . .20 3.5. Exercice . . . . . . . . . . . . . . . . . . . . . . . . . . .20 4. Continuite du projecteur de meilleure approximation. . . . . . .20 4.1. Theoreme de continuite . . . . . . . . . . . . . . . . . . . .20 4.2. Forte unicite . . . . . . . . . . . . . . . . . . . . . . . . 21 5. Dualite. . . . . . . . . . . . . . . . . . . . . . . . . . . . .21 6. Exemples et exercices. . . . . . . . . . . . . . . . . . . . . .21 6.1. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 6.2. Moyenne et mediane . . . . . . . . . . . . . . . . . . . . . .22 6.3. Principaux sousespaces de fonctions utilises en approximation22 6.4. Centre et rayon de Tchebycheff d'une partie P de X . . . . . 22 6.5. Largeurs de Kolmogorov . . . . . . . . . . . . . . . . . . . .22 6.6. Coapproximation . . . . . . . . . . . . . . . . . . . . . . . 23 CHAPITRE 2. Approximation au sens de Tchebycheff. . . . . . . . .. 24 1. Theoreme d'equioscillation de Tchebycheff. . . . . . . . . . .. 24 1.1. Theoreme d'equioscillation de Tchebycheff (1853) . . . . . .. 24 1.2. Preuve de la condition necessaire: p optimal dans P n => (3) .25 1.3. Preuve de la condition suffisante (3) => p optimal dans P n . 26 1.4. Exemple . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 1.5. Theoreme d'unicite de la meilleure approximation polynomiale au sens de Tchebycheff 26 2. Proprietes de la meilleure approximation. . . . . . . . . . . . 27 2.1. Symetrie. Theoreme . . . . . . . . . . . . . . . . . . . . . .27 2.2. Theoreme (de La Vallee Poussin) . . . . . . . . . . . . . . . 27 2.3. Unicite forte . . . . . . . . . . . . . . . . . . . . . . . . 28 2.4. Signes alternes . . . . . . . . . . . . . . . . . . . . . . . 28 2.5. Algorithme d'echange . . . . . . . . . . . . . . . . . . . . .29 2.6. Meilleure approximation au sens L infty sur un compact quelconque 30 3. Polynomes de Tchebycheff. . . . . . . . . . . . . . . . . . . .31 3.1. Meilleure approximation d'un polynome de degre n dans P n-1. 31 3.2. Definition . . . . . . . . . . . . . . . . . . . . . . . . . .31 3.3. Premieres proprietes . . . . . . . . . . . . . . . . . . . . .31 3.4. Premiers echantillons . . . . . . . . . . . . . . . . . . . . 33 3.5. Exercice . . . . . . . . . . . . . . . . . . . . . . . . . . .35 3.6. Relation de recurrence . . . . . . . . . . . . . . . . . . . .35 3.7. Polynome de moindre norme sur un intervalle, sous contrainte p(0) = 1 . . . 36 3.8. Meilleure approximation d'un polynome de degre n dans P n onctions rationnelles de moindre et plus grande deviation . . . . .36 3.11. Proprietes extremales des polynomes de Tchebycheff . . . . .37 3.12. Autres proprietes des T n . . . . . . . . . . . . . . . . . .39 3.13. Equation di#erentielle lineaire . . . . . . . . . . . . . . .42 3.14. Proposition . . . . . . . . . . . . . . . . . . . . . . . . .42 3.15. Polynomes de Tchebycheff et problemes de SturmLiouville . .43 3.16. Coe#cients, derivees et primitives . . . . . . . . . . . . . 43 3.17. Primitives iterees de T n (x) /sqrt(1-x2) et formule de Rodrigues 44 3.18. Orthogonalite et base duale de P N *. . . . . . . . . . . . 45 4. Bonne approximation; series de polynomes de Tchebycheff, relation avec series de Fourier. 48 4.1. Cascade de meilleures approximations et developpements dans la base des polynomes de Tchebycheff 48 4.2. Serie de Fourier d'une fonction continue periodique . . . . . 49 4.3. Series de polynomes de Tchebycheff . . . . . . . . . . . . . 51 4.4. Vitesse de decroissance des coefficients et bornes de norme de fonction d'erreur 54 4.5. Theoreme de Weierstrass . . . . . . . . . . . . . . . . . . . 55 4.6. Calcul des coefficients de Tchebycheff et autres algorithmes .56 5. Approximation par fonction rationnelle. . . . . . . . . . . . . 60 6. Lecture. Tchebycheff et de La Vallee Poussin . . . . . . . . . .61 CHAPITRE 3. Approximation en moyenne. . . . . . . . . . . . . . . .67 1. Produit scalaire, orthogonalite, espace prehilbertien. . . . . .67 1.1. Produits scalaires sur P n . . . . . . . . . . . . . . . . . .67 1.2. Espace prehilbertien . . . . . . . . . . . . . . . . . . . . .70 2. Meilleure approximation dans un espace prehilbertien. . . . . . 70 2.1. Base d'un espace de dimension finie, matrice de Gram . . . . .70 2.2. Meilleure approximation = projection orthogonale . . . . . . .71 2.3. Methode d'orthogonalisation de GramSchmidt . . . . . . . . . 73 2.4. Hauteurs, volumes et determinants de Gram . . . . . . . . . . 73 2.5. Factorisation de Cholesky . . . . . . . . . . . . . . . . . . 74 3. Polynomes orthogonaux. . . . . . . . . . . . . . . . . . . . . 75 3.1. Construction d'une base orthogonale de P n . . . . . . . . . .75 3.2. Relation de recurrence . . . . . . . . . . . . . . . . . . . .79 3.3. Quelques algorithmes utilisant la recurrence . . . . . . . . .81 3.4. Zeros des polynomes orthogonaux . . . . . . . . . . . . . . .85 3.5. Zeros de polynomes orthogonaux et valeurs propres de matrices tridiagonales symetriques 86 3.6. Formules d'integration de Gauss. Premiere approche . . . . . .88 3.7. Formule d'integration de Gauss et fractions continues . . . . 90 3.8. Formule de Christo#elDarboux . . . . . . . . . . . . . . . . 92 3.9. Orthogonalite et operateurs (formellement) hermitiens . . . . 92 3.10. Polynomes orthogonaux classiques . . . . . . . . . . . . . .94 3.11. Orthogonalite et derivees n emes : formule de Rodrigues . . .95 3.12. Usages et varietes de polynomes orthogonaux . . . . . . . . 96 3.13. Harmoniques spheriques et fonctions de Legendre . . . . . . .99 3.14. Polynomes d'Hermite et mecanique quantique . . . . . . . . 102 3.15. Orthogonalite et equioscillation . . . . . . . . . . . . . 103 3.16. Noyaux reproduisants, polynomes noyaux . . . . . . . . . . 104 4. Moindres carres, regression. . . . . . . . . . . . . . . . . . 106 5. Approximation en norme # # 1 . . . . . . . . . . . . . . . . . 110 6. Series de Fourier en analyse numerique. . . . . . . . . . . . 111 6.1. Comportement des coe#cients . . . . . . . . . . . . . . . . 113 6.2. Transformee de Fourier discrete . . . . . . . . . . . . . . 115 6.3. Tranformee de Fourier rapide (Fast Fourier Transform FFT) . 116 6.4. Analyse en ondelettes . . . . . . . . . . . . . . . . . . . .118 7. Convergence, espace de Hilbert . . . . . . . . . . . . . . . . 119 7.1. Suites totales et maximales . . . . . . . . . . . . . . . . .119 7.2. Theoreme. . . . . . . . . . . . . . . . . . . . . . . . . . .121 7.3. Exemples de suites totales dans C [a, b] et L 2 ([a, b], µ). 122 7.4. Theoreme d'approximation de Weierstrass. . . . . . . . . . . 122 7.5. Theoreme de StoneWeierstrass . . . . . . . . . . . . . . . .125 7.6. Intervalles non bornes, probleme des moments. . . . . . . . .127 7.7. Arcs de Bezier en typographie informatique . . . . . . . . . 128 CHAPITRE 4. Interpolation et applications. . . . . . . . . . . . .131 1. Interpolation. . . . . . . . . . . . . . . . . . . . . . . . . 131 1.1. Interpolation polynomiale classique . . . . . . . . . . . . .132 1.2. Interpolation: cadre general . . . . . . . . . . . . . . . . 134 1.3. Interpolation polynomiale classique en formulation de Newton, differences divisees. 138 1.4. Extrapolation a la limite de Richardson . . . . . . . . . . .140 1.5. Reste de l'interpolation polynomiale classique . . . . . . . 143 1.6. Interpolation d'HermiteFejer . . . . . . . . . . . . . . . .145 2. Formules d'integration basees sur l'interpolation. . . . . . . 146 2.1. Reste de la formule de quadrature de Gauss . . . . . . . . . 146 2.2. Formules de quadratures de Gauss avec points imposes . . . . 147 2.3. Points de Tchebycheff: regle de ClenshawCurtis . . . . . . .148 2.4. Regles adaptatives d'integration . . . . . . . . . . . . . . 148 3. Representation du reste: theoreme de Peano. . . . . . . . . . .149 3.1. Theoreme (Peano) . . . . . . . . . . . . . . . . . . . . . . 149 CHAPITRE 5. Di#erences finies. . . . . . . . . . . . . . . . . . .152 1. Les operateurs du calcul aux di#erences. . . . . . . . . . . . 152 2. Interpolation. . . . . . . . . . . . . . . . . . . . . . . . . 154 3. Derivation. . . . . . . . . . . . . . . . . . . . . . . . . . .156 4. Integration. . . . . . . . . . . . . . . . . . . . . . . . . . 156 4.1. Formules de NewtonCotes . . . . . . . . . . . . . . . . . . 157 5. Noyaux de Peano de regles d'integration. . . . . . . . . . . . 158 5.1. Formule du trapeze . . . . . . . . . . . . . . . . . . . . . 158 5.2. Formule de Simpson . . . . . . . . . . . . . . . . . . . . . 158 5.3. Noyaux de Peano de formules composees . . . . . . . . . . . .159 5.4. La formule de Simpson avant Simpson . . . . . . . . . . . . .159 6. Formule d'Euler-Maclaurin. . . . . . . . . . . . . . . . . . . 160 6.1. Identites des nombres et polynomes de Bernoulli . . . . . . 162 6.2. Schema d'integration de Romberg. . . . . . . . . . . . . . . 166 6.3. Formule d'Euler-Maclaurin en tant que formule sommatoire . . 166 CHAPITRE 6. Appendices: alphabets grec, cyrillique, petit dico, index. . . . . . . . . . . . . . 170 1. Alphabets . . . . . . . . . . . . . . . . . . . . . . . . . . 170 2. Petit dico mathematical English # francais mathematique. . . 171 Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 172 Preface. 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 specifique. La discipline put se developper sous l'impulsion de mathematiciens avises, tels P. Henrici [Hen] et E. Stiefel [Sti]. Le present cours fut cree par Jean Meinguet, Professeur a l'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 differentielles et fonctionnelles), d'algebre lineaire numerique (theorie des matrices) et d'algorithmique numerique: ECTS MATH 2171 Analyse numerique I a : [22,5-30] 4 A. Magnus approximation, interpolation, integration MATH 2172 Analyse numerique Ib : [22,5-30] 4 P. Van Dooren resolution numerique des equations MATH 2180 Analyse numerique II [45-0] Q1+Q2 4.5 A. Magnus INMA 2380 Theorie des matrices [30-22,5] Q2 5 P. Van Dooren MATH 2830 Seminaire d'analyse numerique [30] Q1 2 Y. Genin, A. Magnus, P. Van Dooren INMA 2111 Analyse de complexite [30-15] Q2 4 V. Blondel, E. Huens d'algorithmes (Bisannuel) INMA 2710 Algorithmique numerique [3015] Q1 4 P. Van Dooren 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 polynomes et par des polynomes trigonometriques, selon la norme du maximum (chap. 2) et en moyenne (chap. 3). Avec l'interpolation (chap. 4) et le calcul aux differences finies (chap. 5), on dispose des outils permettant de traiter tous les problemes de l'analyse numerique classique, en particulier l'integration numerique. | |
|
