Mat 367 Méthodes numériques PDF 1. calcul approché représentation

de cours exercices corrigés. Éric DOR. &. Économétrie. Cours et exercices entre le vecteur Xt et la variable univariée Yt. ... DUt = 1 si t ? ti.

Analyse Numérique

2.3.1.2 Evaluation d'un polynôme : algorithme de Hörner . . . 35 Exercice 2.5 En appliquant le Théorème de Rouché (voirs cours d'analyse complexe).

livre-algorithmes EXo7.pdf

Voici ce que l'on fait pour calculer Sn avec n = 10. • On affecte d'abord la valeur 0 à la variable somme cela correspond à l'initialisation S0 = 0.

algorithmique.pdf

Il s'agit d'afficher la valeur d'une variable. Syntaxe : « afficher a ». Syntaxe des instructions. Algorithme papier algobox. Calculatrice TI. Calculatrice

Algèbre - Cours de première année

activement par vous-même des exercices sans regarder les solutions. Le triangle de Pascal est un algorithme pour calculer ces coefficients.

ANALYSE MATRICIELLE ET ALGÈBRE LINÉAIRE APPLIQUÉE

Ces deux références proposent un cours complété d'exercices avec vectorielle Vect(x) si et seulement si

Modélisation et simulation des systèmes de production: une

7 mai 2013 Un article (en cours de transformation) est souvent appelé une ''pièce" dans la production. La description complète du processus de ...

Mat 367 Méthodes numériques

1. calcul approché représentation des données (flottants

METHODES NUMERIQUES

Ci-apr`es on propose un autre algorithme qui exploite le théor`eme de Vi`ete et qui évite le Considérons les deux matrices A et C et le vecteur b.

Notes de cours

les étudiants (ce dernier fixant le programme de l'examen) ou tout au moins pas de manière aussi Analyse numérique – Algorithme et étude mathématique.

Mat 367, Méthodes numériques

Bernard.Parisse@ujf-grenoble.fr

2016
La version HTML de ce document comporte des champs de saisie interactifs, ceux-ci apparaissent comme

des commandes "mortes" dans la version PDF. La version HTML est optimisée pour le navigateur Firefox. Vous

pouvez exécuter toutes les commandes interactives en cliquant sur le bouton Exécuter (attention cela peut prendre

un certain temps!), le champ suivant est la console de l"interpréteur du logiciel de calcul formel.

on verra sur de nombreuses commandes qu"il est fort utile de disposer d"un logiciel capable de faire du calcul

formel!

Table des matières

1 Présentation du module6

2 Représentation des nombres et autres données, calcul exact/approché

2.1 Représentation des entiers

2.2 Les réels

2.2.1 Virgule fixe et flottante.

2.2.2 Les flottants au formatdouble. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .9

2.2.3 Opérations sur les flottants

2.2.4 Erreurs

2.2.5 Erreur absolue, relative, arrondi propagation des erreurs.

2.3 L"arithmétique d"intervalle.

2.4 Types composés.

3 Algèbre linéaire15

3.1 Le pivot de Gauss

3.1.1 L"algorithme

3.1.2 Efficacité de l"algorithme

3.1.3 Erreurs d"arrondis du pivot de Gauss

3.2 Applications de Gauss

3.2.1 Base d"un sous-espace

3.2.2 Déterminant

3.2.3 Réduction sous forme échelonnée (rref)

3.2.4 Inverse

3.2.5 Noyau

18 1

3.3 La méthode de factorisationLU. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .18

3.3.1 Interprétation matricielle du pivot de Gauss

3.3.2 FactorisationPA=LU. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .19

3.3.3 Applications

3.4 La factorisation de Cholesky

3.5 Conditionnement

3.5.1 Rappel sur les normes matricielles

3.5.2 Nombre de condition

3.6 Quelques méthodes alternatives au pivot

3.6.1 FactorisationQR. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .24

3.6.2 Jacobi, Gauss-Seidel, relaxation

3.6.3 Le gradient conjugué

4 Approximation polynomiale

4.1 Polynôme de Lagrange

4.1.1 Existence et unicité

4.1.2 Majoration de l"erreur d"interpolation.

4.1.3 Calcul efficace du polynôme de Lagrange.

4.1.4 Sensibilité aux erreurs sur les données.

4.2 Interpolation aux points de Tchebyshev

4.3 Interpolation de Hermite

4.4 Polynômes de Bernstein et courbes de Bézier

4.5 Polynômes orthogonaux.

4.6 Les splines

4.7 Autres approximations polynomiales.

5 Intégration numérique44

5.1 Les rectangles et les trapèzes

5.2 Ordre d"une méthode

5.3 Simpson

5.4 Newton-Cotes

5.5 Calcul des poidswi. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .52

5.6 En résumé

5.7 Accélération de Richardson-Romberg

5.8 Cas des fonctions périodiques.

5.9 Quadratures gaussiennes.

5.9.1 Description

5.9.2 Calcul des poids

5.9.3 Erreur d"une quadrature gaussienne

5.10 Méthode adaptative.

5.11 Accélération de Richardson-Romberg

5.12 Méthodes probabilistes.

60
2

6 Suites itératives et applications63

6.1 Le point fixe dansR. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .63

6.2 Le point fixe dansRn. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .65

6.3 La méthode de Newton dansR.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66

6.4 La méthode de Newton dansRn.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69

6.5 Calcul approché des racines complexes simples

7 Réduction approchée des endomorphismes

7.1 Méthode de la puissance

7.2 Itérations inverses

7.3 Elimination des valeurs propres trouvées

7.4 Décomposition de Schur

8 Equations différentielles (résolution numérique)

8.1 Méthodes à un pas

8.2 Méthodes de Runge-Kutta (explicites)

9 Quelques références81

A Développement de Taylor, séries entières, fonctions usuelles 84

A.1 La fonction exponentielle

A.2 Séries entières.

A.3 Série alternée

A.4 La fonction logarithme

A.5 Autres applications

89
A.5.1 Exemple : la fonction d"erreur (error fonction,erf). . . . . . . . . . . . . . . . . . . . 89 A.5.2 Recherche de solutions d"équations différentielles 90
A.5.3 Exemple : fonctions de Bessel d"ordre entier 90
A.6 Développements asymptotiques et séries divergentes 91

B La moyenne arithmético-géométrique.

B.1 Définition et convergence

B.2 Lien avec les intégrales elliptiques

B.3 Application : calcul efficace du logarithme.

99
3 Index arrondi, 6 atan, 79

Bézier, courbes de,

35
base, 4 BCD, 7

Bernstein, polynômes de,

35
bit, 7 cholesky, 18 complexe, 12 constante de Lebesgue, 32
contractante, 57
convexe, 62
cos, 77
dénormalisé, 7 determinant, 15 différences divisées, 30
divisées, différences, 30
division euclidienne, 4 double, 7

Durand-Kerner, Weierstrass,

64
erreur, 8 9 14 erreur absolue, 9 erreur relative, 10

Euler, méthode d",

Euler, Mac Laurin,

49
54
exp, 76
exposant, 7 expression, 12 factorisation, 64
factorisation de Schur, 67
flottant, 7 fonction, 12

Gauss,

Gauss-Seidel,

25
gaussienne, quadrature, 50
gradient conjugué, 27

Hermite, interpolation de,

34 integration,40

interpolation, 27
28
intervalle, arithmétique, 11 inverse, 15 itérations inverses, 67

Jacobi,

25
ker, 16

Lagrange,

27
lagrange, 28

Lebesgue, constante de,

Legendre,

36
liste, 12 ln, 79
LU, 16

Mac Laurin, Euler,

49
54
mantisse, 6 7 matrice, 12

Monte-Carlo,

Newton,

61
63

Newton-Cotes,

46
normalisé, 6 noyau, 16 ordre, 42
orthogonaux, polynômes, 36

Péano, noyau de,

44
pivot, 13 point fixe, 58
point milieu, 41
polynômes orthogonaux, 36
polynome, 12 puissance, 65
QR, 22
68
quadrature, 40
quadrature gaussienne, 50
racine, 64
4 rectangle,41 reduction, 15

Richardson-Romberg,

48
54

Romberg,

48
54
rref, 15

Runge, phénomène de,

Runge-Kutta,

Schur (factorisation),

67
sequence, 12 serie alternee, 79
serie entiere, 77

Simpson,

45
sin, 77
splines, 39
symbole, 12

Taylor,

Tchebyshev,

32
trapeze, 41
vecteur, 12 5

1 Présentation du module

Les thèmes abordés seront :

calcul approché, représentation des données (flottants, v ecteurs,matrices), erreurs (normes, de calcul, d"ar -

rondi...). 2. Pi votde Gauss, f actorisationLU, conditionnement, Cholesk y,f actorisationQR. 3. Interpolation polynômiale (év aluation,interpolation de Lagrange, Hermite, Bézier) 4.

Intégration numérique

5. Méthode du point fix e,de Ne wton,méthodes itérati vesen algèbre linéaire 6. Méthode de la puissance, v aleurspropres et v ecteurspropres. 7.

Résolution d"équations dif férentielles.

L"évaluation se fait sur :

1/2 : un DS à mi-semestre et certains compte-rendus de TP (à rédiger seul ou en binome),

1/2 : l"e xamenfinal

Les calculatrices et les netbooks de taille d"écran plus petits que 13 pouces sont autorisées au DS et à l"examen

final (prêt possible de netbooks pour le semestre).

2 Représentation des nombres et autres données, calcul exact/approché

Mot-clefs :

Types de base : entier machine, entier long, flottant machine et multiprécision (Base 2, base 10).

Erreur relative, erreur absolue, erreur d"arrondi, +/-, */ Algorithme de Horner. Types composés : complexes, poly-

nomes (représentation dense/creuse), symboles, listes (vecteurs, matrices), expressions, fonctions.

Les principaux ensembles de nombres en mathématiques sont les entiers positifsNet relatifsZ, les rationnelsQ,

les réelsRet les complexesC. Sur ordinateur, on peut représenter ces nombres de manière exacte dans certains

cas, approchée dans d"autres.

2.1 Représentation des entiers

Proposition 1

Di visioneuclidienne de deux entiers : siaetbsont deux entiers,a0;b >0, il existe un unique couple(q;r)tel que a=bq+r; r2[0;b[ Preuve : On prend pourqle plus grand entier tel queabq0.

Exemple :iquorem(23,7)

[3;2]

La division euclidienne permet d"écrire un nombre entier, en utilisant une basebet des caractères pour représenter

les entiers entre 0 etb1. Nous écrivons les nombres entiers enbaseb= 10avec comme caractères les chiffres de

0 à 9. Les ordinateurs utilisent des circuits binaires pour stocker les informations, il est donc naturel d"y travailler

en base 2 en utilisant comme caractères 0 et 1 ou en base 16 en utilisant comme caractères les chiffres de 0 à 9 et

les lettres de A à F. En général, pour trouver l"écriture d"un nombre en baseb(par exempleb= 2), on effectue des

divisions euclidienne successives parbdu nombre puis de ses quotients successifs jusqu"à ce que le quotient soit

0 et on accolle les restes obtenus (premier reste à droite, dernier reste à gauche). Inversement, pour retrouver un

entierdà partir de son écrituredn:::d0, on traduit les divisions euclidiennes successives en d= (:::((dnb+dn1)b+dn2):::+d1)b+d0 =dnbn+dn1bn1+:::+d0 Par exemple, vingt-cinq s"écrit en base 160x19car 25 divisé par 16 donne quotient 1, reste 9 convert(25,base,16) [9;1]

En base 2, on trouverait0b11001car25 = 24+ 23+ 1.

quotesdbs_dbs46.pdfusesText_46

[PDF] Mat 367 Méthodes numériques 1. calcul approché représentation

Mat 367, Méthodes numériques

Bernard.Parisse@ujf-grenoble.fr

Table des matières

1 Présentation du module6

2 Représentation des nombres et autres données, calcul exact/approché

2.1 Représentation des entiers

2.2 Les réels

2.2.1 Virgule fixe et flottante.

2.2.2 Les flottants au formatdouble. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .9

2.2.3 Opérations sur les flottants

2.2.4 Erreurs

2.2.5 Erreur absolue, relative, arrondi propagation des erreurs.

2.3 L"arithmétique d"intervalle.

2.4 Types composés.

3 Algèbre linéaire15

3.1 Le pivot de Gauss

3.1.1 L"algorithme

3.1.2 Efficacité de l"algorithme

3.1.3 Erreurs d"arrondis du pivot de Gauss

3.2 Applications de Gauss

3.2.1 Base d"un sous-espace

3.2.2 Déterminant

3.2.3 Réduction sous forme échelonnée (rref)

3.2.4 Inverse

3.2.5 Noyau

3.3 La méthode de factorisationLU. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .18

3.3.1 Interprétation matricielle du pivot de Gauss

3.3.2 FactorisationPA=LU. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .19

3.3.3 Applications

3.4 La factorisation de Cholesky

3.5 Conditionnement

3.5.1 Rappel sur les normes matricielles

3.5.2 Nombre de condition

3.6 Quelques méthodes alternatives au pivot

3.6.1 FactorisationQR. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .24

3.6.2 Jacobi, Gauss-Seidel, relaxation

3.6.3 Le gradient conjugué

4 Approximation polynomiale

4.1 Polynôme de Lagrange

4.1.1 Existence et unicité

4.1.2 Majoration de l"erreur d"interpolation.

4.1.3 Calcul efficace du polynôme de Lagrange.

4.1.4 Sensibilité aux erreurs sur les données.

4.2 Interpolation aux points de Tchebyshev

4.3 Interpolation de Hermite

4.4 Polynômes de Bernstein et courbes de Bézier

4.5 Polynômes orthogonaux.

4.6 Les splines

4.7 Autres approximations polynomiales.

5 Intégration numérique44

5.1 Les rectangles et les trapèzes

5.2 Ordre d"une méthode

5.3 Simpson

5.4 Newton-Cotes

5.5 Calcul des poidswi. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .52

5.6 En résumé

5.7 Accélération de Richardson-Romberg

5.8 Cas des fonctions périodiques.

5.9 Quadratures gaussiennes.

5.9.1 Description

5.9.2 Calcul des poids

5.9.3 Erreur d"une quadrature gaussienne

5.10 Méthode adaptative.

5.11 Accélération de Richardson-Romberg

5.12 Méthodes probabilistes.

6 Suites itératives et applications63

6.1 Le point fixe dansR. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .63

6.2 Le point fixe dansRn. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .65

6.3 La méthode de Newton dansR.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66

6.4 La méthode de Newton dansRn.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69

6.5 Calcul approché des racines complexes simples

7 Réduction approchée des endomorphismes

7.1 Méthode de la puissance

7.2 Itérations inverses

7.3 Elimination des valeurs propres trouvées

7.4 Décomposition de Schur

8 Equations différentielles (résolution numérique)

8.1 Méthodes à un pas

8.2 Méthodes de Runge-Kutta (explicites)