ESIAL 1ere annee

Description

Niveau: Secondaire, Lycée, Première
Mathematiques Numeriques et Analyse de Donnees ESIAL 1ere annee Notes de cours redigees par B. Pinc¸on et J.-F. Scheid 2007-2008

• norme ieee


• interpolation de lagrange-hermite par morceaux


• valeurs caracteristiques des flottants ieee


• systeme de van-der-monde


• erreur d'interpolation


• formalisation de la methode de gauss en decomposition sur la matrice

Informations

• Publié par: profil-mazor-2012
• Nombre de lectures: 20
• Langue: Français

Extrait

Math´ematiques Num´eriques
et
Analyse de Donn´ees
`ereESIAL 1 ann´ee
Notes de cours r´edig´ees par B. Pinc¸on et J.-F. Scheid
2007-2008Table des mati`eres
1 Arithm´etique flottante 5
1.1 Repr´esentation d’un nombre en virgule flottante. . . . . . . . . . . . . . . . . . . . . . . . 5
1.1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.1.2 D´efinition formelle d’un syst`eme fini de repr´esentation en virgule flottante . . . . . 5
1.1.3 Approximation d’un nombre r´eel par un nombre flottant . . . . . . . . . . . . . . . 7
1.1.4 Erreur entre un r´eel et son repr´esentant flottant : le epsilon machine . . . . . . . . 8
1.2 La norme IEEE 754 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.2.2 Valeurs caract´eristiques des flottants IEEE . . . . . . . . . . . . . . . . . . . . . . 9
1.2.3 Remarques sur le codage des flottants IEEE . . . . . . . . . . . . . . . . . . . . . . 10
1.2.4 L’arithm´etique avec les nombres sp´eciaux . . . . . . . . . . . . . . . . . . . . . . . 10
1.3 Quelques cons´equences sur les calculs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.3.2 La soustraction de deux nombres proches . . . . . . . . . . . . . . . . . . . . . . . 12
1.3.3 Calculs d’erreurs classiques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
1.3.4 Notions sur le conditionnement d’un probl`eme . . . . . . . . . . . . . . . . . . . . 15
1.3.5 Stabilit´e d’un algorithme : un exemple simple . . . . . . . . . . . . . . . . . . . . . 17
1.4 Recettes et rem`edes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
1.4.1 G´eneralit´es . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
1.4.2 Probl`emes d’overflow . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
1.4.3 Quelques algorithmes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2 R´esolution de syst`emes lin´eaires 25
2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
2.2 La m´ethode de Gauss (rappels) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
2.3 L’interpr´etation matricielle de la m´ethode de Gauss . . . . . . . . . . . . . . . . . . . . . 27
2.3.1 Quelques notations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
k ⊤2.3.2 Action d’une matrice de la forme M =I +z(e ) . . . . . . . . . . . . . . . . . . 28
2.3.3 Th´eor`eme 1 : La d´ecomposition A =LU . . . . . . . . . . . . . . . . . . . . . . . . 29
2.3.4 Quelques autres r´esultats th´eoriques . . . . . . . . . . . . . . . . . . . . . . . . . . 31
2.3.5 Utilisation d’une d´ecomposition pour r´esoudre un syst`eme lin´eaire . . . . . . . . . 31
2.3.6 Couˆt de la m´ethode de Gauss/LU . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
2.3.7 Aquoisertlaformalisation delam´ethodedeGaussend´ecomposition surlamatrice? 33
2.4 Deux autres d´ecompositions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
⊤2.4.1 La d´ecomposition A =LDL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
⊤2.4.2 La d´ecomposition de Cholesky A=CC . . . . . . . . . . . . . . . . . . . . . . . 35
2.5 C’est fini? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
3 Interpolation polynomiale 37
3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
3.2 Base canonique - Syst`eme de Van-der-Monde . . . . . . . . . . . . . . . . . . . . . . . . . 38
3.3 Polynˆome de Lagrange . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
3.4 Base de Newton - Diff´erences divis´ees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
1`2 TABLE DES MATIERES
3.5 Calcul des diff´erences divis´ees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
3.5.1 Evaluation du polynˆome - Sch´ema d’Horner . . . . . . . . . . . . . . . . . . . . . . 43
3.6 Erreur d’interpolation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
3.7 Probl`eme de convergence de l’interpolation . . . . . . . . . . . . . . . . . . . . . . . . . . 44
3.7.1 Points d’interpolation ´equidistants . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
3.7.2 Abscisses de Tchebichev . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
3.8 Interpolation de Lagrange-Hermite . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
3.9 Interpolation polynomiale par morceaux . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
3.9.1 Interpolation de Lagrange par morceaux . . . . . . . . . . . . . . . . . . . . . . . . 48
3.9.2 Interpolation de Lagrange-Hermite par morceaux . . . . . . . . . . . . . . . . . . . 49
3.10 Splines cubiques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
3.10.1 Calcul num´erique des splines cubiques (conditions naturelles) . . . . . . . . . . . . 50
3.10.2 Propri´et´es et estimations d’erreurs des splines cubiques . . . . . . . . . . . . . . . 51
3.10.3 Splines param´etriques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
3.11 Courbes de B´ezier . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
3.11.1 Construction g´eom´etrique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
3.11.2 Calcul num´erique des courbes de B´ezier . . . . . . . . . . . . . . . . . . . . . . . . 54
4 Probl`emes de moindres carr´es 55
4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
4.1.1 Exemple : un probl`eme de lissage de points . . . . . . . . . . . . . . . . . . . . . . 55
4.1.2 Matrices de changement de base . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
´4.2 Ecriture de E comme une forme quadratique . . . . . . . . . . . . . . . . . . . . . . . . . 58
4.3 R´esolution du probl`eme par recherche du z´ero de la d´eriv´ee . . . . . . . . . . . . . . . . . 60
4.3.1 Rappels ou compl´ements de calcul diff´erentiel . . . . . . . . . . . . . . . . . . . . . 60
4.3.2 Application des r´esultats pr´ec´edents sur notre fonction E . . . . . . . . . . . . . . 63
4.4 R´esolution du probl`eme par orthogonalisation . . . . . . . . . . . . . . . . . . . . . . . . . 64
4.4.1 Projection orthogonale sur un sous-espace vectoriel . . . . . . . . . . . . . . . . . . 64
4.4.2 Application : un premier algorithme bas´e sur cette id´ee . . . . . . . . . . . . . . . 65
4.4.3 Interpr´etation matricielle de l’algorithme 1 . . . . . . . . . . . . . . . . . . . . . . 67
4.4.4 Algorithme 2 : la d´ecomposition A=QR par les transformations de Householder . 67
5 Introduction a` l’analyse de donn´ees : Analyse en composantes principales. 69
5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
5.2 Quelques rappels de statistiques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
5.3 Quelques rappels sur les valeurs et vecteurs propres . . . . . . . . . . . . . . . . . . . . . . 71
5.4 Variables centr´ees r´eduites . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
5.5 Repr´esentation des individus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
5.5.1 Inertie par rapport `a un point . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
5.5.2 Inertie par rapport `a une droite . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
5.5.3 Minimisation de l’inertie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
5.5.4 Axes principaux . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
5.5.5 Matrice de variance-covariance, matrice de corr´elation . . . . . . . . . . . . . . . . 77
5.5.6 Repr´esentation graphique des individus . . . . . . . . . . . . . . . . . . . . . . . . 79
5.6 Composantes principales . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
5.7 Repr´esentation des variables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81
6 Introduction a` l’analyse de donn´ees : Classification non hi´erarchique. 83
6.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
6.2 Consid´erations g´en´erales sur le probl`eme (6.1) . . . . . . . . . . . . . . . . . . . . . . . . . 84
6.3 Quelques algorithmes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
6.3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
6.3.2 Choix de la partition initiale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86
6.3.3 Algorithme des H-means . . . . . . . . . . . . . . . . . . . . . . . . . . . . .