Polyana Num

Anne 2013-2014

Analyse Numrique

Cours de Tako Takahashi

Polycopi rdig par Michel Pierre et Antoine Henrot

Cours lectif CE33

Semestre S7 : 2013-2014

Tako Takahashi

Ecole des Mines de Nancy - Campus Artem - 54 042 Nancy Cedex

Tel : 03 83 68 45 95 - email: [email protected]

IECL - Dp. Gnie Industriel et Maths Appliques

Table des matires

1 Les erreurs en Analyse Numrique 9

1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

1.2 Arithmtique machine . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

1.2.1 Reprsentation machine des nombres rels . . . . . . . . . . . . . 10

1.2.2 Perte de chires signicatifs . . . . . . . . . . . . . . . . . . . . . 10

1.3 Notions de conditionnement et stabilit . . . . . . . . . . . . . . . . . . 12

1.3.1 Conditionnement . . . . . . . . . . . . . . . . . . . . . . . . . . 12

1.3.2 Stabilit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

1.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

1.5 Exercices du chapitre 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

2 Rsolution d'quations non linaires 17

2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

2.2 Cas des fonctions d'une variable . . . . . . . . . . . . . . . . . . . . . . . 17

2.2.1 Prliminaires : sparation des zros . . . . . . . . . . . . . . . . . 17

2.2.2 Quelques algorithmes classiques . . . . . . . . . . . . . . . . . . . 18

2.2.2.1 Mthode de dichotomie (ou bisection) . . . . . . . . . . 18

2.2.2.2 Mthode de la scante . . . . . . . . . . . . . . . . . . . 19

2.2.2.3 Critre d'arrt . . . . . . . . . . . . . . . . . . . . . . . 19

2.2.2.4 Mthode de Newton . . . . . . . . . . . . . . . . . . . . 20

2.2.2.5 Mthode de point xe . . . . . . . . . . . . . . . . . . . 20

2.2.3 Convergence des algorithmes . . . . . . . . . . . . . . . . . . . . 22

2.2.3.1 Mthodes de point xe . . . . . . . . . . . . . . . . . . 22

2.2.3.2 Mthode de Newton . . . . . . . . . . . . . . . . . . . . 24


2.2.4 Comparaison des algorithmes . . . . . . . . . . . . . . . . . . . . 28

2.2.4.1 Mthode de dichotomie . . . . . . . . . . . . . . . . . . 28

2.2.4.2 Mthode de Newton . . . . . . . . . . . . . . . . . . . . 29


2.2.4.4 Mthode du point xe . . . . . . . . . . . . . . . . . . . 29

2.2.5 Acclration de la convergence . . . . . . . . . . . . . . . . . . . 30

2.2.5.1 Mthode de relaxation . . . . . . . . . . . . . . . . . . . 30

2.2.5.2 Mthode du 2 d'Aitken . . . . . . . . . . . . . . . . . 31

2.3 Fonctions valeurs complexes . . . . . . . . . . . . . . . . . . . . . . . . 34

2.3.1 Cas des quations polynmiales . . . . . . . . . . . . . . . . . . . 34

2.3.1.1 Localisation des zros . . . . . . . . . . . . . . . . . . . 34

3

4 TABLE DES MATIRES

2.3.1.2 Evaluation d'un polynme : algorithme de Hrner . . . 35

2.3.1.3 Dtermination de tous les zros . . . . . . . . . . . . . . 37

2.3.1.4 Mthode de Bairstow . . . . . . . . . . . . . . . . . . . 38

2.3.1.5 Mthode de Mller . . . . . . . . . . . . . . . . . . . . 39

2.4 Systme d'quations non linaires . . . . . . . . . . . . . . . . . . . . . . 40

2.4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40

2.4.2 La mthode de Newton-Raphson . . . . . . . . . . . . . . . . . . 41

2.4.3 La mthode de Broyden . . . . . . . . . . . . . . . . . . . . . . . 42


3 Interpolation et approximation polynmiale 45

3.1 Interpolation de Lagrange . . . . . . . . . . . . . . . . . . . . . . . . . . 45

3.1.1 Le polynme d'interpolation . . . . . . . . . . . . . . . . . . . . . 45

3.1.2 Proprits des dirences divises . . . . . . . . . . . . . . . . . . 47

3.1.3 Erreur dans l'interpolation de Lagrange . . . . . . . . . . . . . . 50

3.1.3.1 Analyse du thorme 3.3 . . . . . . . . . . . . . . . . . 51

3.2 Approximation polynmiale uniforme . . . . . . . . . . . . . . . . . . . . 52

3.3 Approximation au sens des moindres carrs . . . . . . . . . . . . . . . . 56

3.3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56

3.3.2 Mthode classique des moindres carrs . . . . . . . . . . . . . . . 57

3.3.3 Polynmes orthogonaux . . . . . . . . . . . . . . . . . . . . . . . 60

3.3.4 Exemples classiques de polynmes orthogonaux . . . . . . . . . . 62

3.3.5 Polynmes trigonomtriques . . . . . . . . . . . . . . . . . . . . . 64

3.3.6 La transforme de Fourier rapide . . . . . . . . . . . . . . . . . . 67

3.4 Approximation par des fonctions polynmiales par morceaux . . . . . . 67

3.4.1 Approximation linaire par morceaux . . . . . . . . . . . . . . . 68

3.4.2 Approximation cubique . . . . . . . . . . . . . . . . . . . . . . . 68

3.4.3 Fonctions splines . . . . . . . . . . . . . . . . . . . . . . . . . . . 69


4 Drivation et intgration numrique 73

4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73

4.2 Drivation numrique . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74

4.2.1 Drive premire . . . . . . . . . . . . . . . . . . . . . . . . . . . 74

4.2.1.1 Formules deux points . . . . . . . . . . . . . . . . . . 74

4.2.1.2 Formules trois points . . . . . . . . . . . . . . . . . . 75

4.2.1.3 Erreur . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75

4.2.2 Drives d'ordre suprieur . . . . . . . . . . . . . . . . . . . . . . 76

4.3 Intgration numrique : mthodes composites . . . . . . . . . . . . . . . 76

4.3.1 Principe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76

4.3.2 Mthode des rectangles . . . . . . . . . . . . . . . . . . . . . . . 76

4.3.3 Mthode des trapzes . . . . . . . . . . . . . . . . . . . . . . . . 77

4.3.4 Mthode de Simpson . . . . . . . . . . . . . . . . . . . . . . . . . 78

4.3.5 Mthode du trapze corrige . . . . . . . . . . . . . . . . . . . . 78

4.4 Analyse de l'erreur dans les mthodes d'intgration . . . . . . . . . . . . 79

4.4.1 Thorie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79

TABLE DES MATIRES 5

4.4.2 Application aux mthodes usuelles . . . . . . . . . . . . . . . . . 80

4.4.2.1 Mthode des rectangles ( gauche ou droite) . . . . . 80

4.4.2.2 Formule du point milieu . . . . . . . . . . . . . . . . . . 80

4.4.2.3 Mthode des trapzes . . . . . . . . . . . . . . . . . . . 81

4.4.2.4 Mthode de Simpson . . . . . . . . . . . . . . . . . . . 81

4.4.2.5 Mthode des trapzes corrigs . . . . . . . . . . . . . . 82

4.4.3 Exemple d'application . . . . . . . . . . . . . . . . . . . . . . . . 82

4.5 Mthodes d'intgration numrique de Gauss . . . . . . . . . . . . . . . . 82

4.5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82

4.5.2 Ide de base des mthodes de Gauss . . . . . . . . . . . . . . . . 83

4.5.3 Mise en oeuvre de la mthode . . . . . . . . . . . . . . . . . . . . 84

4.5.3.1 Mthode de Legendre-Gauss . . . . . . . . . . . . . . . 85

4.5.3.2 Mthode de Gauss-Chebyshev . . . . . . . . . . . . . . 86

4.5.3.3 Mthodes de Laguerre et Hermite . . . . . . . . . . . . 86

4.6 Mthodes d'extrapolation la limite . . . . . . . . . . . . . . . . . . . . 86

4.6.1 Extrapolation la limite de Richardson . . . . . . . . . . . . . . 87

4.6.2 Mthode de Romberg . . . . . . . . . . . . . . . . . . . . . . . . 89


5 Rsolution numrique d'quations direntielles 93

5.1 Quelques remarques sur (5.1) . . . . . . . . . . . . . . . . . . . . . . . . 93

5.1.1 Quelques soucis d'ordre thorique . . . . . . . . . . . . . . . . . . 94

5.1.2 Rgularit de la solution . . . . . . . . . . . . . . . . . . . . . . . 96

5.2 Mthodes de rsolution un pas . . . . . . . . . . . . . . . . . . . . . . 97

5.2.1 La mthode d'Euler . . . . . . . . . . . . . . . . . . . . . . . . . 97

5.2.1.1 Estimation de l'erreur de discrtisation . . . . . . . . . 99

5.2.1.2 Inuence des erreurs d'arrondis . . . . . . . . . . . . . . 101

5.2.2 Mthode d'Euler implicite . . . . . . . . . . . . . . . . . . . . . . 103

5.3 Les mthodes de Runge-Kutta . . . . . . . . . . . . . . . . . . . . . . . 103

5.4 Contrle du pas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107

5.5 Mthodes pas multiples . . . . . . . . . . . . . . . . . . . . . . . . . . 109

5.5.1 Mthodes d'Adams-Bashforth r + 1 pas . . . . . . . . . . . . . 109

5.5.2 Mthodes d'Adams-Moulton r + 1 pas . . . . . . . . . . . . . . 111

5.5.3 Mthode de prdicteur-correcteur . . . . . . . . . . . . . . . . . . 112

5.6 Comparaison des mthodes . . . . . . . . . . . . . . . . . . . . . . . . . 112

5.7 Applications des problmes aux limites . . . . . . . . . . . . . . . . . . 113

5.8 Schma de Newmark pour les problmes d'ordre 2 . . . . . . . . . . . . 114


6 Rsolution de systmes linaires 117

6.1 Quelques remarques gnrales . . . . . . . . . . . . . . . . . . . . . . . . 117

6.1.1 Origines des problmes . . . . . . . . . . . . . . . . . . . . . . . . 117

6.1.2 Mthodes utilises . . . . . . . . . . . . . . . . . . . . . . . . . . 117

6.1.3 Structure de la matrice . . . . . . . . . . . . . . . . . . . . . . . 118

6.1.3.1 Cas d'une matrice diagonale . . . . . . . . . . . . . . . 118

6.1.3.2 Matrice triangulaire suprieure (ou infrieure) . . . . . 118

6 TABLE DES MATIRES

6.1.3.3 Autres cas . . . . . . . . . . . . . . . . . . . . . . . . . 119

6.1.3.4 Matrices symtriques . . . . . . . . . . . . . . . . . . . 120

6.1.4 Stockage des matrices . . . . . . . . . . . . . . . . . . . . . . . . 120

6.2 Mthodes directes de rsolution de AX = b . . . . . . . . . . . . . . . . 123

6.2.1 Mthode d'limination de Gauss . . . . . . . . . . . . . . . . . . 123

6.2.1.1 Calcul du nombre d'oprations lmentaires . . . . . . . 126

6.2.2 Drivs de la mthode de Gauss . . . . . . . . . . . . . . . . . . 126

6.2.2.1 Factorisation LU . . . . . . . . . . . . . . . . . . . . . . 127

6.2.2.2 Algorithme de Crout . . . . . . . . . . . . . . . . . . . 128

6.2.2.3 Cas particulier des matrices tridiagonales . . . . . . . . 129

6.2.2.4 Mthode de Gauss-Jordan . . . . . . . . . . . . . . . . 130

6.2.3 Factorisation de Cholesky . . . . . . . . . . . . . . . . . . . . . . 131

6.2.4 Autres mthodes directes . . . . . . . . . . . . . . . . . . . . . . 134

6.3 Analyse du conditionnement d'un systme linaire . . . . . . . . . . . . 134

6.3.1 Quelques prliminaires sur les normes matricielles . . . . . . . . 134

6.3.1.1 Norme sur l'espace vectoriel des matrices . . . . . . . . 135

6.3.2 Analyse du conditionnement . . . . . . . . . . . . . . . . . . . . 137

6.3.2.1 Proprits de cond (A) . . . . . . . . . . . . . . . . . . . 138

6.3.3 Exemple de systme linaire mal conditionn . . . . . . . . . . . 139

6.3.4 Prconditionnement . . . . . . . . . . . . . . . . . . . . . . . . . 140

6.4 Mthodes itratives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 140

6.4.1 Description des mthodes de Jacobi, Gauss-Seidel, relaxation . . 140

6.4.2 Itrations par blocs . . . . . . . . . . . . . . . . . . . . . . . . . . 141

6.4.3 Etude de la convergence des mthodes itratives . . . . . . . . . 142

6.4.3.1 Vitesse de convergence . . . . . . . . . . . . . . . . . . 143

6.4.3.2 Application aux mthodes de Jacobi-Gauss-Seidel-Relaxation144

6.4.4 Application la mthode des dirences nies . . . . . . . . . . 147

6.5 La mthode du gradient conjugu . . . . . . . . . . . . . . . . . . . . . . 151

6.5.1 Gradient conjugu avec prconditionnement . . . . . . . . . . . . 154


7 Calcul de valeurs propres et vecteurs propres 155

7.1 Rappels . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 155

7.2 Origine des problmes de valeurs propres . . . . . . . . . . . . . . . . . . 157

7.2.1 Vibration d'une corde . . . . . . . . . . . . . . . . . . . . . . . . 157

7.2.2 Vibration d'une membrane . . . . . . . . . . . . . . . . . . . . . 159

7.2.3 Problmes de valeurs propres gnraliss . . . . . . . . . . . . . . 160

7.2.4 Systme mcanique . . . . . . . . . . . . . . . . . . . . . . . . . . 160

7.2.5 Autres exemples . . . . . . . . . . . . . . . . . . . . . . . . . . . 161

7.3 Mthode de la puissance itre et de la puissance inverse . . . . . . . . . 161

7.3.1 Mthode de la puissance itre . . . . . . . . . . . . . . . . . . . 161

7.3.2 Mthode de la puissance inverse . . . . . . . . . . . . . . . . . . 163

7.4 Mthode de Jacobi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 164

7.5 Mthode de Givens-Householder . . . . . . . . . . . . . . . . . . . . . . 168

7.5.1 Principe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 168

7.5.2 Description de la mthode de Givens . . . . . . . . . . . . . . . . 168

TABLE DES MATIRES 7

7.5.3 Mise sous forme Hessenberg d'une matrice . . . . . . . . . . . . . 171

7.6 La mthode QR . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 172

7.6.1 Algorithme QR de recherche de valeurs propres . . . . . . . . . . 174


8 TABLE DES MATIRES

Chapitre 1

Les erreurs en Analyse

Numrique

1.1 Introduction

Dans le titre de ce chapitre, le mot erreur n'est pas pris au sens de faute (raisonnement

faux dans la mthode, instruction fausse dans le programme). Il ne concerne que des

erreurs invitables. On peut les classer en trois catgories :

Les erreurs sur les donnes. Elles peuvent tre dues l'imprcision des mesures

physiques ou au fait que les donnes proviennent elle mme d'un calcul approch.

Elles sont imposes, en quelque sorte, de l'extrieur et nous ne pouvons agir sur elles.

Nanmoins, la manire dont elles se propagent au cours des calculs est davantage

du ressort du calculateur. L'analyse de cette propagation sera voque au cours de

ce chapitre. Elle est lie aux notions de conditionnement et de stabilit (voir section

1.3).

Les erreurs d'arrondi. Ce sont les erreurs dues au fait que la machine (dans ce

cours, ce terme dsignera indiremment la calculette de poche ou l'ordinateur) ne

peut reprsenter les nombres rels qu'avec un nombre ni de chires. A chaque opra-

tion mathmatique lmentaire, il pourra y avoir une perte de chires signicatifs. Le

calculateur doit donc tre vigilant quand le nombre d'oprations est trs important.

Cela va faire l'objet du prochain paragraphe.

Les erreurs d'approximation ou de discrtisation. Ce sont les erreurs qu'on

commet, par exemple, lorsqu'on calcule une intgrale l'aide d'une somme nie, une

drive l'aide de dirences nies ou bien la somme d'une srie innie l'aide d'un

nombre ni de ses termes (on parle alors quelquefois d'erreur de troncature). Une

situation qu'on rencontrera souvent galement consiste approcher une fonction,

solution d'une certaine quation fonctionnelle ou aux drives partielles, par une

combinaison linaire nie de fonctions lmentaires. Ce type d'erreurs est bien sr

fortement li la mthode employe. Un des buts de l'analyse numrique consiste

justement valuer ces erreurs de discrtisation pour chaque algorithme mis en place.

C'est donc un souci qui nous accompagnera tout au long de ce cours.

9

10 CHAPITRE 1. LES ERREURS EN ANALYSE NUMRIQUE

1.2 Arithmtique machine

1.2.1 Reprsentation machine des nombres rels

Le systme de reprsentation machine des nombres rels le plus utilis en calcul scien-

tique est celui de la reprsentation en virgule ottante normalise. Un nombre x 6= 0s'crit

x mbp

o b est la base de numration (entier suprieur ou gal 2), m la mantisse (ensemblede chires de la base b) et p l'exposant (entier relatif). Dire que la reprsentation estnormalise, c'est supposer

b1 m < 1:Par exemple, le nombre 395.2134 en base 10 s'crit +:3952134 10+3 ou, plus souvent,+:3952134 E+3. Les bases b = 2 ou les puissances de 2 sont frquemment utilises parles constructeurs d'ordinateurs. Cela signie, par exemple que tous les calculs internes

sont faits en base 2 et seul le rsultat ach est traduit en base 10.

La mantisse m est donc un nombre qui commence toujours par 0: : : : et qui s'critavec un nombre maximum N de chires signicatifs (impos par le choix de la tailledes emplacements mmoires allous au type rel). Signalons la possibilit oertes sur la

plupart des ordinateurs (mais pas sur les calculatrices !) de travailler en double prcision,

c'est--dire essentiellement avec une mantisse comportant 2N chires signicatifs. Cettepossibilit est videmment coteuse en temps de calcul et ne doit surtout pas tre

utilise systmatiquement. Elle est intressante, en particulier, quand on n'est pas trs

sr de la stabilit d'un algorithme, pour pouvoir comparer des rsultats obtenus en

simple prcision et en double prcision.

L'exposant p est lui aussi limit par la machine avec laquelle on travaille. Si p esthors des limites permises (i.e. trop grand en valeur absolue), le nombre x ne sera pasreprsentable en machine : elle achera alors un message du type exponent overow

quand le nombre est trop grand, ou elle achera 0 s'il est trop petit, voir Exercice 1.1.

On appelle quelquefois capacit le plus grand nombre que peut crire la machine et

pas le plus petit nombre. En gnral, le pas est l'inverse de la capacit.

La dirence entre la valeur exacte d'un nombre x et la valeur x de sa reprsentationest appele erreur d'arrondi. Elle est majore par

12bNbp, soit en valeur relative :x xx

bNbp2x bNbp2bp1 = b1N2 :Cette erreur est systmatiquement prsente dans tout calcul arithmtique sur nombre

rel eectu par un ordinateur. Elle fait que l'arithmtique numrique n'a pas la pr-

cision de l'arithmtique mathmatique et peut, si on n'y prend garde, conduire des

rsultats inexacts, voire aberrants, comme le montrent les exemples suivants et les

exercices.

1.2.2 Perte de chires signicatifs

Pour faciliter la comprhension, nous nous placerons dans l'environnement rassurant

de la base 10, les phnomnes tant du mme type dans toute base.

Exemple 1.1 Supposons que dans un calcul apparaisse la quantit x = 3:1415(o = 3:141592653589793 : : :). Si on travaille avec 8 chires signicatifs (comme

1.2. ARITHMTIQUE MACHINE 11

beaucoup de calculettes), le nombre sera reprsent par : = 0:31415927 101 envirgule ottante normalise. On aura donc

x = 0:31415927 101 0:31415 101 = 0:0000927 101 = 0:927 104

On constate que x ne contient en fait que 3 chires signicatifs et non 8, soit une pertesche de 5 chires signicatifs. Ce genre de phnomnes peut surgir tout moment

d'un calcul. Nous verrons de nombreux exemples d'algorithmes conduisant faire la

dirence de 2 nombres proches.

Exemple 1.2 : Soit calculer le quotient

A =XN

XD=

3; 1415104( 3; 1515) 0; 927En travaillant avec 8 chires signicatifs, on a :

XD = 104(0; 927:104) 0; 927 = 0; 0 = 3; 1415927 A = ERREUR = 3; 14159265 A = 0; 18530::: = 3; 141592653 e A = 0; 197134::: = 3; 141592654 c A = 0; 201427::: = 3; 1415926535 e A = 0; 1992548::: = 3; 1415926536 c A = 0; 1996844::: = 3; 14159265358 e A = 0; 1995984::: = 3; 14159265359 c A = 0; 19964143::: = 3; 141592653589 A = 0; 19963713::: = 3; 1415926535897 e A = 0; 199640143::: = 3; 1415926535898 c A = 0; 1996405743::: = 3; 14159265358979 A = 0; 1996405312 = 3; 1415927653589793 A = 0; 1996405439:::On constate que pour obtenir p chires signicatifs pour A, il faut reprsenter l'aidede p+ 8 chires signicatifs.

Dans le tableau ci dessus, le symbole ] signale des reprsentations avec le mme nombrede chires, tous tant identiques sauf le dernier.

Exemple 1.3 : L'addition numrique n'est pas associative : en virgule ottante nchires signicatifs, (a+ b) + c peut tre dirent de a + (b+ c). C'est le cas avec lechoix suivant o les calculs sont faits avec 8 chires signicatifs.

a : = 0; 23371258:104

b : = 0; 33678429:102

c : = 0; 33677811:102

a+ b = 0; 00000023(371258):102 + 0; 33678429:102 = 0; 33678452:102:

On remarque que, dans cette addition, les 6 derniers chires de a sont perdus. Ainsi :

(a+ b) + c = 0; 33678452:102 0; 33677811:102= 0; 00000641:102 = 0; 641:103:

Par ailleurs :

b+ c = 0; 33678429:102 0; 33677811:102= 0; 00000618:102 = 0; 618:103


a+ (b+ c) = 0; 02337125 (8) :103 + 0; 61800000:103 = 0; 64137126:103:

Essayons d'analyser le phnomne ci-dessus. Si vf (a+ b) dsigne le rsultat de l'addi-tion a+ b, on a :

vf (a+ b) = (a+ b) (1 + "1)

o "1 dsigne l'erreur relative commise dans le calcul : celle-ci dpend de la prcision dela machine. On sait qu'elle est majore par

12

1nsoit ici 5:108. Posons = vf (a+ b).On a alors

vf ((a+ b) + c) = vf ( + c) = ( + c) (1 + "2) j"2j 5:108= [(a+ b) (1 + "1) + c] (1 + "2)

= a+ b+ c+ (a+ b) "1 (1 + "2) + (a+ b+ c) "2:

Ainsi :

vf ((a+ b) + c) (a+ b+ c)a+ b+ c

=a+ b

a+ b+ c"1 (1 + "2) + "2:

De la mme faon :

vf (a+ (b+ c)) (a+ b+ c)a+ b+ c

=b+ c

a+ b+ c"3 (1 + "4) + "4:

On voit que les erreurs "1 (1 + "2), "3 (1 + "4), environ gales 5:108sont soumises

des coecients amplicateurs

a+ b

a+ b+ c' 5:104; b+ c

a+ b+ c' 0; 9:

Ceci explique pourquoi le second calcul est plus prcis que le premier.

Remarque 1.1 Dans les calculs o interviennent des nombres d'ordres de grandeur dif-

frents, il est en gnral prfrable d'eectuer les oprations en groupant ceux d'ordres

de grandeur similaires pour viter les pertes de chires signicatifs.

1.3 Notions de conditionnement et stabilit

Ces deux notions, toujours prsentes en analyse numrique, sont relatives la propa-

gation plus ou moins importante des erreurs d'arrondi dans un calcul donn. Nous les

tudions ici pour le calcul d'une fonction.

x 2 R 7! f(x) 2 R:

1.3.1 Conditionnement

Le conditionnement dcrit la sensibilit de la valeur d'une fonction une petite variation

de son argument, c'est--dire :

f (x) f (x)f (x)en fonction de

x xx

lorsque x x est petit. Pour une fonction susamment rgulire, on a videmment :f (x) f (x)f (x) x xx ' xf 0 (x)f (x)

:D'o on tire :

1.3. NOTIONS DE CONDITIONNEMENT ET STABILIT 13

Dnition 1.1 On appelle conditionnement d'une fonction numrique f de classe C1

en un point x, le nombre

cond(f)x :=

xf 0 (x)f (x) :Exemple 1.4 : f (x) =

px xf 0 (x)f (x)

= 12 :Ceci correspond un bon conditionnement, puisque l'erreur relative sur f sera au plusmoiti d'une erreur relative sur x.

Exemple 1.5 : f (x) = a x xf 0 (x)f (x) = xa x

:Ici, le conditionnement est trs mauvais si x est voisin de a. Ceci correspond auxexemples 1.1, 1.2, 1.3.

1.3.2 Stabilit

La stabilit dcrit la sensibilit d'un algorithme numrique pour le calcul d'une fonction

f (x).

Exemple 1.6 :

f (x) =px+ 1px:Le conditionnement de cette fonction est gal :xf 0 (x)f (x)

=xp

xpx+ 12px (x+ 1)

1px+ 1px

= 12r

x

x+ 1

Cette dernire expression tant proche de

12 pour x grand. Donc, si x est grand, leconditionnement de f est bon. Cependant, dans un calcul 6 chires signicatifs, ona :

f (12345) =p12346

p12345 = 111; 113 111; 108 = 0; 500000:102:Or un calcul prcis donne : f (12345) = 0; 4500032::::102: On a donc une erreur de10% ce qui est important et peu en accord avec le bon conditionnement de f . Ceci estd l'algorithme utilis dans ce calcul que l'on peut expliciter comme suit :

x0 : = 12345

x1 : = x0 + 1

x2 : =px1

x3 : =px0

x4 : = x2 x3Il y a quatre fonctions intervenir et, priori, mme si le conditionnement de f est bon,il se peut que le conditionnement d'une ou plusieurs fonctions utilises dans l'algorithme

soit suprieur celui de f . C'est ce qui se produit ici pour la fonction x3 7! x4 = x2x3(x2 tant suppos xe) dont le conditionnement est grand lorsque x3 est voisin de x2comme on l'a vu prcdemment.


En conclusion, le choix d'un bon algorithme numrique est essentiel. Par exemple, ci-

dessus, un meilleur algorithme est obtenu en utilisant :

f (x) =px+ 1px = 1p

x+ 1 +px:

Dans ce cas, toujours avec 6 chires signicatifs :

f(12345) =1p

12346 +p12345

=1

222; 221= 0; 450002:102

ce qui donne une erreur relative de 0; 0003%. Dans la mme optique, l'exemple suivantpeut aussi tre mdit.

Exemple d'instabilit : Calcul de e12 l'aide de sa srie de Taylor

ex =NXn=0

xn

n!(= SN ) pour N grand.

Voici les valeurs successives de cette somme en fonction de N pour x = 12. Le calculest fait avec 10 chires signicatifs.

N SN N SN N SN2 11; 0::: 19 1629; 87::: 36 0; 001432:::3 61; 0::: 20 996; 45::: 37 0; 000472:::4 227; 0::: 21 579; 34::: 38 0; 0001454:::5 637; 0::: 22 321; 11::: 39 0; 000049726:::6 1436; 6::: 23 170; 04::: 40 0; 000010319:::7 2710; 6::: 24 86; 20::: 41 0; 000007694:::8 4398; 88::: 25 41; 91::: 42 0; 000002422:::9 6265; 34::: 26 19; 58::: 43 0; 000003928:::10 7953; 62::: 27 8; 80::: 44 0; 000003508:::11 9109; 137::: 28 3; 8130::: 45 0; 000003623:::12 9504; 78::: 29 1; 5937::: 46 0; 000003592:::13 9109; 13::: 30 0; 6435::: 47 0; 000003600:::14 8072; 94::: 31 0; 2513::: 48 0; 000003598:::15 6654; 55::: 32 0; 0950::: 49 0; 000003599:::16 5127; 44::: 33 0; 0348::: 50 0; 000003598:::17 3709; 05::: 34 0; 01238:::18 2528; 47::: 35 0; 004283:::La valeur de e12 est en fait de 0; 0000061442::: . La formule ex = 1ex donne lieu uncalcul plus stable, mme si ex est calcul comme ci-dessus.

1.4 Conclusion

An de limiter la propagation des erreurs d'arrondi, il faut essayer d'anticiper en utili-

sant des algorithmes dont la stabilit est optimise par un choix d'oprations interm-

diaires bon conditionnement.

Les phnomnes souligns dans ce chapitre ne pouvant tre, en tout tat de cause,

compltement limins, on peut essayer d'valuer l'erreur totale laquelle un algorithme

est susceptible de donner lieu :

a/ en faisant un calcul en double prcision et en confrontant le rsultat au mme calcul

fait en simple prcision. C'est ce que nous avons fait dans l'exemple 1.2. Cependant,

1.5. EXERCICES DU CHAPITRE 1 15

cette technique est trs coteuse en temps machine puisqu'elle peut multiplier le temps

de calcul par un facteur 8.

b/ en faisant une analyse mathmatique de l'erreur : ce peut tre une analyse rtrograde

de l'erreur comme celle utilise plus haut pour comparer (a+ b) + c et a+ (b+ c). Desmthodes statistiques peuvent tre galement utilises. Nous renvoyons la littrature

spcialise pour ces questions le plus souvent dlicates.

1.5 Exercices du chapitre 1

Exercice 1.1 En crivant un petit programme, trouver la capacit et le pas de votre

calculatrice de poche ou de l'ordinateur.

Exercice 1.2 Calculer les racines de l'quation x2 + 111; 11x + 1; 2121 = 0 dans une

arithmtique 5 chires signicatifs (base 10) en utilisant les formules x = b+pb24ac2a ,

puis x = 2cb+pb24ac , et analyser les rsultats.

Exercice 1.3 Estimer l'erreur faite dans le calcul de (cosx) e10x2

autour de x = 2quand l'erreur sur x est d'ordre 106:

Exercice 1.4 Trouver une mthode pour calculer :

sin (+ x) sin

lorsque x est voisin de 0, la prcision permise par le nombre de chires signicatifsutiliss.

Exercice 1.5 Calculer, en arrondissant quatre chires signicatifs chaque calcul in-

termdiaire, la somme des nombres suivants d'abord dans le sens croissant puis dans le

sens dcroissant. Comparer les rsultats.

0; 1580 0; 2653 0; 2581:101 0; 4288:101 0; 6266:102 0; 7555:102

0; 7889:103 0; 7767:103 0; 8999:104:

Exercice 1.6 Les valeurs 1, 16 ,162 , ...,

16n sont thoriquement gnres par la suite

x0 = 1, x1 =16 , xn+1 =

37

6xn xn1 pour tout n 1:Calculer les valeurs successives avec 4 dcimales puis avec 8 dcimales et comparer...On constate une dirence trs importante ds la 5me tape. Expliquer !

Chapitre 2

Rsolution d'quations non

linaires

2.1 Introduction

Le but de ce chapitre est de dcrire les algorithmes les plus frquemment utiliss pour

rsoudre des quations non linaires du type :

f (x) = 0

o

1. x est une variable relle, f une fonction valeurs relles

2. x est une variable complexe, f une fonction valeurs complexes

3. x est un vecteur de Rn, f une fonction de Rn dans Rn.Le premier point sera le plus dtaill : la convergence des algorithmes est analyse. On

prsentera galement des techniques d'acclration de convergence. Pour les fonctions

complexes, on insistera sur le cas des polynmes. Pour les fonctions de Rn dans Rn onprsentera rapidement les algorithmes qui seront en fait inspirs de la dimension 1.

2.2 Cas des fonctions d'une variable

2.2.1 Prliminaires : sparation des zros

Exemple 2.1 : rsoudre x 0; 2 sinx 0; 5 = 0, x rel.Exemple 2.2 : rsoudre cosx = ex, x rel.

Le premier travail consiste en une analyse mathmatique minimale pour sparer les

zros, c'est--dire dterminer des intervalles [ai; bi] dans lesquels l'quation considrea une solution et une seule.

La mthode la plus simple est d'utiliser qu'une fonction continue strictement monotone

sur un intervalle [ai; bi] et telle que f (ai) f (bi) 0 a un zro et un seul dans l'intervalle[ai; bi]. Par exemple :

f1 (x) = x 0; 2 sinx 0; 5f 01 (x) = 1 0; 2 cosx 0 pour tout x :Donc f1 est strictement croissante sur R. Comme f1 (0) = 0; 5 < 0 ; f1 () = 0; 5 >0; f1 a un unique zro dans [0; ]:

17

18 CHAPITRE 2. RSOLUTION D'QUATIONS NON LINAIRES

Un calcul similaire pour l'exemple 2.2 conduit une impasse si on pose f2 (x) :=cosx ex puisque la drive f 02 (x) = sinx + ex est du mme type. Cette situationest bien sr beaucoup plus frquente. On peut alors :

A/ choisir plus judicieusement la fonction auxiliaire f2. Ici, on peut par exemple poserf2 (x) := e

x cosx 1: Les zros de f2 sont exactement les solutions de (2.2). D'autrepart :

f 02 (x) = ex (cosx sinx) =

p2ex cos

x

4

:

Ainsi f2 est strictement monotons sur les intervalles du type4 + k

2 ;

4 + (k + 1)

2

, k entier. L'tude des signes successifs de f

4 + k

2

permet

alors de localiser les zros ventuels.

B/ On peut procder par tatonnements en s'aidant au maximum d'informations compl-

mentaires disponibles. Ainsi, dans l'exemple 2.2, le trac des reprsentations graphiques

des fonctions x 7! cosx et x 7! ex est particulirement suggestif.Dans la suite, nous nous placerons le plus souvent dans le cas o f : [a; b] ! R admetun unique zro dans l'intervalle [a; b] :

2.2.2 Quelques algorithmes classiques

2.2.2.1 Mthode de dichotomie (ou bisection)

Reprenons l'exemple 2.1. Nous avons vu que si f(x) = x 0:2 sinx 0:5, f (0) 0 ; d'o un zro dans (0; ). Si on calcule la valeur de f en

2

, on constate

que f2

= 2 0; 7 > 0. Donc ce zro est en fait dans

0; 2

. On peut alors calculer

f

4

= 0; 14 > 0, qui montre qu'il est dans

0; 4

.

Il est clair qu'une rptition de ce procd donne un encadrement de plus en plus prcis

du zro cherch et fournit donc un algorithme de calcul de ce zro.

Algorithme 2.1 : Soit f : [a0; b0]! R continue et telle que f (a0) f (b0) 0:2664Pour n = 0; 1; 2; :::; N; faire

m := (an+bn)2Si f (an) f (m) 0; an+1 := an; bn+1 := mSinon an+1 := m; bn+1 := bn:

On a : an+1 bn+1 = 12 (an bn), soit par rcurrence an bn = 12n (a0 b0). Il enrsulte que cette mthode est toujours convergente puisque an bn tend vers 0 quandn tend vers l'inni. On peut choisir le temps d'arrt N pour que :

1

2N(a0 b0) < " = prcision choisie.

On obtient alors un encadrement de la solution cherche la prcision voulue. Bien que

cette situation soit trs allchante, on verra qu'en fait cette mthode converge plutt

lentement compare celles qui suivent.

Remarque 2.1 Dans l'exemple 2.1, on a f (0) = 0; 5 ; f () = 2; 64. Ceci laisseimmdiatement penser que le zro cherch doit tre plus prs de 0 que de . Le plusecace n'est donc pas de tester la valeur de f en le milieu de [0; ] mais plutt en unpoint plus voisin de 0 tenant compte de cette dirence de poids entre f (0) et f ().Ceci conduit aux algorithmes dits de fausse position qui convergent gnralement plus

vite. Nous ne les expliciterons pas ici.

Remarque 2.2 La mthode ci-dessus converge mme si f a plusieurs zros dans l'in-tervalle [a0; b0] :

2.2. CAS DES FONCTIONS D'UNE VARIABLE 19

2.2.2.2 Mthode de la scante

Soit f admettant un zro dans l'intervalle [x1; x0] : Pour obtenir une premire approxi-mation de ce zro, l'ide est de remplacer f par son interpol linaire sur [x1; x0], soitpar

Y (x) = f (x0) + (x x0) f (x0) f (x1)x0 x1 ;

l'unique fonction linaire dont les valeurs concident avec celles de f en x1 et x0.L'approximation x1 est alors obtenue en rsolvant :

Y (x1) = 0

soit

x1 = x0 f (x0) x0 x1f (x0) f (x1) :

Gomtriquement (cf Figure 2.1), ceci revient remplacer la courbe d'quation y =

xn1

xn

xn+1

A

B

Figure 2.1 Mthode de la scante

f (x) par la scante AB et xn+1 est l'intersection de AB avec la droite (Ox) :

Comme le montre le dessin, xn+1 semble plus voisin du zro cherch que xn1 ou xn.Pour trouver une meilleure approximation, il sut de rpter le procd l'aide des

points (xn; xn+1). En continuant, on obtient l' :

Algorithme 2.2 : x0 et x1 tant donns,24 Pour n = 0; 1; 2; :::xn+1 = xn f (xn) xn xn1

f (xn) f (xn1) :

2.2.2.3 Critre d'arrt

Cet algorithme n'est videmment pas complet tant qu'on n'a pas prcis un critre

d'arrt. Nous verrons plus loin que, gnralement, xn converge vers la solution x1cherche ce qui signie que pour n grand, xn est voisin de x1. Sans plus d'informations,


il est dicile de savoir ce que signie numriquement n grand, et c'est l une dicultfrquente en analyse numrique.

Un critre d'arrt souvent utilis consiste choisir a priori une tolrance " et terminerl'algorithme lorsque

jxn+1 xnj " : (2.1)Ce n'est pas compltement satisfaisant ; pour s'en convaincre, on peut penser la suite :

xn = 1 +1

2+ :::+

1

n

qui vrie limn!1 jxn+1 xnj = 0 bien que tendant vers l'inni.Puisqu'on veut rsoudre f(x) = 0, un autre critre d'arrt possible consiste s'arrterlorsque

jf (xn)j < " : (2.2)Un numricien particulirement scrupuleux pourra dcider de ne s'arrter que lorsque

les deux critres d'arrts (2.1) et (2.2) sont simultanment vris.

Dans le cas de l'algorithme de la scante ci-dessus, on peut aussi utiliser :

jf (xn) f (xn1)j < " :ce critre d'arrt a l'avantage d'viter une possible division par 0.

Enn, pour viter l'ordinateur de tourner sans s'arrter lorsqu'il n'y a pas convergence,

il est videmment indispensable de toujours mettre un critre limitant le nombre

total d'itrations.

2.2.2.4 Mthode de Newton

Ici, au lieu d'assimiler la courbe y = f (x) une scante, on l'assimile la tangenteen un point (xn; f (x0)) soit, la droite d'quation :

Y = f (xn) + f0 (xn) (x xn) :Son intersection avec l'axe des abscisses fournit une approximation de la solution x1.A nouveau, on renouvelle le procd jusqu' obtenir une approximation susante, d'o

l' :

Algorithme 2.3 : x0 tant donn"Pour n = 0; 1; 2; :::

xn+1 = xn f(xn)f 0(xn) :

Remarque 2.3 Cet algorithme est initi l'aide d'un seul point. Il peut tre vu comme

une modication de l'algorithme prcdent o le quotient

xnxn1f(xn)f(xn1) a t remplacpar

1f 0(xn). Nous verrons plus loin qu'il donne lieu une convergence beaucoup plus

rapide.

2.2.2.5 Mthode de point xe

Elle consiste d'abord remplacer l'quation

() f (x) = 0par une quation

() g (x) = x


xn

xn+1

f(xn)

Figure 2.2 Mthode de Newton

ayant mmes solutions. On est ainsi ramen la recherche des points xes de l'applica-

tion g. Le remplacement de () par () est toujours possible en posant, par exemple,g (x) = f (x) + x. Ce n'est videmment pas forcment le meilleur choix !

Exemple 2.3 : Pour l'quation

x2 x 2 = 0

on peut prendre

g (x) = x2 2g (x) =

p2 + x

g (x) = 1 +2

x

g (x) = x x2 x 2

mpour tout paramtre m 6= 0:

l'quation tant sous la forme (), on a alors l'algorithme suivant :Algorithme 2.4 : On choisit x0Pour n = 0; 1; 2; :::xn+1 = g (xn) :

Cette mthode est justie par la :

Proposition 2.1 Soit g : [a; b] ! [a; b] continue et x0 2 [a; b] : Si xn converge versx1, alors

x1 = g (x1) :

La dmonstration est immdiate en passant la limite dans l'galit xn+1 = g (xn) eten utilisant la continuit de g au point x1.Une dicult majeure dans l'algorithme 2.4 est qu'il peut arriver qu'on ne puisse cal-

culer g (xn). Il sut de penser ce qui se passe lorsque g (x) = px !


x0 x1x2

y=x

Figure 2.3 Mthode de point xe pour g(x) =px+ 2

Remarque 2.4 Il peut tre intressant de construire graphiquement les valeurs suc-

cessives de xn dans certains cas : prenons g (x) =p2 + x comme dans l'exemple 2.3 :

On utilise la premire bissectrice pour reporter les valeurs successives de xn. On peutse convaincre l'aide de ce type de construction que certains points xes ne sont jamais

atteints par l'algorithme 2.4 (cf Figure 2.4 ci aprs) :

Exemple 2.4 : g (x) = x2 Si x0 est choisi gauche de 1, la suite xn converge vers lepoint xe 0.Si x0 est choisi droite de 1, la suite xn tend versl'inni.A moins de choisir exactement x0 = 1, on voit que la suite ne converge jamais vers 1 :c'est un point xe instable. On y reviendra dans le paragraphe suivant.

Cet exemple met par ailleurs en vidence l'inuence du choix de x0 sur le comportementde xn.

2.2.3 Convergence des algorithmes

2.2.3.1 Mthodes de point xe

Commenons par traiter le cas du point xe qui est fondamental d'un point de vue

thorique.

Thorme 2.1 Soit g : [a; b]! [a; b] drivable et telle que

jg0 (x)j K 8x 2 [a; b] avec 0 K < 1 (2.3)

Alors, pour tout x0 2 [a; b], la suite dnie par

xn+1 = g (xn) 8n 2 N

converge vers l'unique point xe de g:


Figure 2.4 Mthode de point xe pour g(x) = x2

Dmonstration : Notons d'abord que la suite est dnie pout tout n puisque

8x 2 [a; b] g (x) 2 [a; b] :

La fonction g a un point xe et un seul dans l'intervalle [a; b], car la fonction h (x) =g (x) x vrie :(i) h est continue sur [a; b]

(ii) h0 (x) = g0 (x) 1 k 1 < 0, donc h est strictement monotone(iii) h (a) = g (a) a 0 puisque g (a) 2 [a; b](iv) h (b) = g (b) b 0 puisque g (b) 2 [a; b] :Soit x1 ce point xe, on a :

xn+1 x1 = g (xn) g (x1) = g0 (n) (xn x1)

o n 2 [a; b], d'aprs le thorme des accroissements nis. Ainsi, en utilisant (2.3), ona :

jxn+1 x1j K jxn x1j ; (2.4)et par rcurrence,

jxn x1j Kn jx0 x1j 8n:Puisque 0 K < 1; ceci prouve que limn!1 jxn x1j = 0.Remarque 2.5 Quand une suite xn converge vers x1 selon la relation (2.4), on ditque la convergence est au moins linaire. Plus gnralement, on dnit :

Dnition 2.1 Soit xn une suite convergeant vers x1. S'il existe un nombre p et uneconstante C 6= 0 tels que

limn!1

jxn+1 x1jjxn x1jp = C;

on dit que la convergence est d'ordre p ; C est la constante d'erreur asymptotique.


S'il existe une constante C et un rel positif p tel que

jxn+1 x1j C jxn x1jp

pour tout n assez grand, on dit que la convergence est au moins d'ordre p.

Remarque 2.6 La convergence vers 0 de anbn dans l'algorithme 2.1 (la dichotomie)est linaire.

Remarque 2.7 Il est clair qu'une convergence est d'autant plus rapide que son ordre

est grand. En eet, si jxn x1j est petit, jxn x1j2 est encore plus petit !...La notion de vitesse de convergence est videmment essentielle en analyse numrique :

an de diminuer le temps de calcul (et donc le cot !), toutes choses tant gales par

ailleurs, on choisira toujours l'algorithme convergeant le plus rapidement. Cependant,

il est bien rare que "toutes les choses soient gales par ailleurs". Voir le paragraphe

suivant ce propos.


Revenons un instant la mthode du point xe. D'aprs la formule de Taylor l'ordre

2, on a, en supposant g susamment rgulire :

xn+1 x1 = g(xn) g(x1) = (xn x1)g0 (x1) + 12(xn x1)2g00 (n)

o n 2 [xn; x1]. Pour n grand, on a donc

xn+1 x1 ' (xn x1)g0 (x1)

et la vitesse de convergence sera d'autant plus grande que g0 (x1) est plus petit. Le casle plus favorable est celui o g0 (x1) = 0:Si M2 est majorant de g

00 (x) sur [a; b], on a alors :

jxn+1 x1j M22jxn x1j2 :

La convergence est alors au moins d'ordre 2 !

Si on revient l'algorithme 2.3 de Newton, on voit qu'il s'agit en fait d'un algorithme

de point xe pour la fonction g (x) = x f(x)f 0(x) . La drive de g est donne par :

g0 (x) = 1 f0 (x)

f 0 (x)+f (x) f 00 (x)f 02 (x)

=f (x) f 00 (x)f 02 (x)

:

Si f 0 (x1) 6= 0, on a alors, puisque f (x1) = 0 :

g0 (x1) = 0:

Ceci montre que la mthode de Newton converge de faon quadratique...si elle converge !

Pour s'assurer de sa convergence, on peut essayer d'appliquer g le thorme 2.1. Ilest clair que l'hypothse (2.3) est vrie sur un voisinage susamment petit de x1(puisque g0 (x1) = 0 et on suppose g0 continue). L'hypothse plus dicile vrier estque g envoie un voisinage [a; b] de x1 dans lui-mme. On a en fait le rsultat suivant :


Thorme 2.2 Soit f deux fois continument direntiable sur un intervalle ouvert decentre x1 vriant :

f (x1) = 0; f 0 (x1) 6= 0:Alors, si x0 est choisi assez prs de x1, la mthode de Newton :

xn+1 = xn f (xn)f 0 (xn)

8n 0

produit une suite xn convergeant au moins quadratiquement vers x1.

Avant de dmontrer ceci, faisons quelques remarques :

Remarque 2.8 Toute l'ambiguit dans ce rsultat provient de si x0 est choisi assezprs de x1 : en eet, dans la pratique, il n'y a gnralement aucun moyen de savoirdans quelle mesure x0 est assez voisin de x1.

C'est un des inconvnients de la mthode de Newton : une initialisation faite au hasard

conduit souvent une divergence. Ceci est suggr par la Figure 2.5.

x0x1

x2x0x1

Figure 2.5 Divergence dans la mthode de Newton

Remarque 2.9 L'hypothse f 0 (x1) 6= 0 est naturelle : tant donn le calcul duquotient

f(xn)f 0(xn), des valeurs petites de f 0 (xn) conduisent une perte de prcision.Si f 0 (x1) = 0, il se peut cependant que la mthode converge, mais en gnral laconvergence sera au plus linaire.

Exemple : f (x) = x2

xn+1 = xn f (xn)f 0 (xn)

=1

2xn ;

ici xn converge linairement vers 0.

Remarque 2.10 An de lever l'incertitude de l'initialisation dans la mthode de New-

ton, on peut utiliser des thormes plus globaux comme celui assurant la convergence

ds que x0 2 [a; b] si f : [a; b]! R est deux fois continuement direntiable et :i) f (a) f (b) 0ii) f 0 (x1) 6= 0 8x 2 [a; b]iii) f 00(x) 0 ( 0) 8x 2 [a; b]iv)

jf(a)jjf 0(a)j < b a; jf(b)jjf 0(b)j < b a:


Dmonstration du thorme 2.2 :

Nous allons montrer qu'il existe " > 0 tel que la fonction

g (x) = x f (x)f 0 (x)

satisfasse les hypothses du thorme 2.1 dans l'intervalle [x1 "; x1 + "] :On a :

g0 (x) =f (x) f 00 (x)f 02 (x)

Puisque f 0 (x1) 6= 0, il existe "1 tel que :8x 2 [x1 "1; x1 + "1] ; f 0 (x) 6= 0:Il en rsulte que g0 est continue sur cet intervalle. Puisque g0 (x1) = 0, il existe "2 "1tel que :

8x 2 [x1 "2; x1 + "2] ; jg0 (x)j 12< 1:

Par ailleurs, d'aprs le thorme des accroissements nis :

jg (x) g (x1)j jx x1j max2[x;x1]

jg0 ()j 12jx x1j ; si jx x1j "2:

puisque g (x1) = x1, ceci prouve que g envoie [x1 "2; x1 + "2] dans lui-mme(jx x1j "2 =) jg (x) x1j "2).D'aprs le thorme 2.1 appliqu g avec a = x1 "2, b = x1 + "2, la suite dniepar

x0 2 [x1 "2; x1 + "2]xn+1 = g (xn) = xn f (xn)

f 0 (xn)

converge vers x1. Les considrations faites prcdemment montrent que la convergenceest quadratique, le seul point vrier tant le comportement de la drive seconde de

g. Or, on vrie que

g00 (x1) =f 00 (x1)f 0 (x1)

:

Si f est deux fois continument drivable, g00 est borne sur un voisinage de x1 et onpeut directement appliquer les remarques prcdentes.


L'algorithme 2.2 correspondant est dni par :

xn+1 := xn f (xn) xn xn1f (xn) f (xn1) =

xn1f (xn) xnf(xn1)f (xn) f (xn1)soit encore

xn+1 x1 = (xn1 x1) f (xn) (xn x1) f(xn1)f (xn) f (xn1)et, en utilisant f (x1) = 0

xn+1 x1 = (xn x1) (xn1 x1)hf(xn)f(x1)

xnx1 f(xn1)f(x1)

xn1x1

if (xn) f (xn1) :


Utilisant les notations standard des dirences divises (cf chapitre suivant), soit :

f [x] : = f (x)

f [x; y] : =f (y) f (x)

y x =f [y] f [x]

y xf [a; x; y] : =

f [x; y] f [a; x]y a , etc...,

la formule ci-dessus s'crit :

xn+1 x1 = (xn x1) (xn1 x1) f [xn1; x1; xn]f [xn1; xn]

: (2.5)

D'aprs le thorme des accroissements nis

f [xn1; xn] = f 0 (n) o n 2 [xn1; xn] : (2.6)

Nous verrons de mme au chapitre suivant que :

f [xn1; x1; xn] =1

2f 00 (n) o n 2 plus petit intervalle contenant xn1; xn; x1:(2.7)

Si on suppose que xn prend ses valeurs dans un intervalle J sur lequel :

8x 2 J jf 00 (x)j M; jf 0 (x)j m > 0; (2.8)

d'aprs (2.5), (2.6), (2.7) et en posant :

en := jxn x1j ;

on a :

en+1 = cnenen1; cn 12

M

m(2.9)

(et limn!1 cn = 12f 00(x1)f 0(x1)d'aprs ce qui suit). Si f est deux fois continument drivable

sur un intervalle [x1 ; x1 + ] et si f 0 (x1) 6= 0, on montre, comme dans le cas dela mthode de Newton qu'il existe J = [x1 "; x1 + "] (0 < " ) et M; m > 0tel que (2.8) soit vri. Quitte resteindre encore ", en utilisant (2.9), on montreque si x0 2 J , alors xn appartient J pour tout n, ceci par rcurrence. Dans ce cas,l'estimation (2.9) est valable pour tout n. On dduit de cette estimation que en tendvers 0 et que la convergence est surlinaire.En eet, remarquons d'abord qu'on peut se "ramener" au cas C = 1 dans (2.9) enposant "n = Cen. Multipliant alors (2.9) par C, on a

"n+1 (Cen) (Cen1) = "n"n1: (2.10)

Soit alors p la racine positive de p2 p 1 = 0, soit p = (1+p5)

2 = 1; 618::: (le nombred'or !) et K = max

"0; p

p"1. Montrons par rcurrence que

"n Kpn : (2.11)

Ceci est vrai pour n = 0; 1 d'aprs le choix de K. Si c'est vrai jusqu'au rang n, d'aprs(2.10), on a :

"n+1 KpnKpn1 = Kpn1(1+p) = Kpn+1 ; d'aprs le choix de p ;


donc (2.10) est vrai pour tout n.Ainsi, si on choisit K < 1 (c'est--dire x0 et x1 susamment voisins de x1), "n et doncen tendent vers 0 quand n tend vers l'inni, d'aprs (2.11).Cette mme relation (2.11) suggre que la convergence est au moins d'ordre p. On lemontre (cf. Dnition 2.1), en remarquant que (2.10) implique :

"n+1"pn

"1pn "n1 =

"n"pn1

1pcar p (1 p) = 1:

Ainsi

"n"pn1reste infrieur la suite Yn dnie par

Y1 ="1"p0;

Yn+1 = Y1pn

qui, comme on le vrie aisment converge vers 1 puisque j1 pj < 1:Donc, pour n assez grand

"n+1 Yn"pn (1 + ") "pn:Ceci prouve que la convergence est au moins d'ordre p = 1; 618::: .

Thorme 2.3 Soit f deux fois continument direntiable sur un intervalle ouvert decentre x1 vriant :

f (x1) = 0; f 0 (x1) 6= 0:Alors, si x0; x1 sont choisis assez prs de x1, l'algorithme de la scante dni par :

xn+1 = xn f (xn) xn xn1f (xn) f (xn1) 8n 1

converge vers x1 et la convergence est au moins d'ordre p = 1; 618::: .

2.2.4 Comparaison des algorithmes

Pour comparer les algorithmes, il est important de tenir compte de la prsence ou non

des facteurs suivants :

assurance de la convergence

vitesse de la convergence

stabilit de l'algorithme - prcision des rsultats

ecacit des calculs (ex : nombre de fonctions calculer chaque itration).

2.2.4.1 Mthode de dichotomie

Avantages :

la convergence est assure

on a un encadrement de la solution

un seul calcul de fonction chaque itration.

Inconvnients :

vitesse de convergence linaire, donc lente

sensible aux erreurs d'arrondi ; exemple : la fonction f (x) = ex 1x x22 s'annulethoriquement en x = 0 seulement. Numriquement, elle change de signe un grandnombre de fois autour de x = 0.



Avantages :

converge rapidement quand elle converge (ce qui compense largement le dernier in-

convnient)

relativement stable et peu sensible aux erreurs d'arrondis si f 0 (x1) n'est pas troppetit.

Inconvnients :

peut diverger ou converger vers un autre zro que celui cherch si la donne initiale

est mal choisie

ncessite le calcul de la drive d'une fonction, ce qui est numriquement dicile si

on ne la connait pas explicitement

chaque tape ncessite deux valuations de fonctions.


Avantages :

ncessite une seule valuation de fonction chaque tape

convergence relativement rapide, bien que moins que celle de Newton.

Inconvnients :

comme la mthode de Newton, peut diverger si les donnes initiales sont mal choisies

le calcul de f (xn) f (xn1) peut produire des erreurs de chute.

2.2.4.4 Mthode du point xe

Inconvnients :

convergence souvent dicile raliser en pratique

certains points xes -dits instables- ne peuvent tre atteints

convergence lente de type linaire, en gnral.

Conclusion : cette dernire mthode a surtout un intert thorique : son analyse math-

matique est relativement aise et nous a permis d'en dduire celle de la mthode de

Newton qui en est en fait un cas particulier. En pratique, elle est souvent utilise dans de

tels cas particuliers. Nous verrons plusieurs reprises dans la suite qu'elle joue un rle

considrable pour adapter des algorithmes linaires des situations non linaires. Elle

est donc fondamentale en tant que concept. D'autre part, couple avec des techniques

d'acclration de la convergence (cf. paragraphe suivant), elle peut tre intressante.

La mthode de Newton a gnralement la faveur des utilisateurs : elle est eectivement

trs rapide et est certainement conseiller lorsque le calcul de f 0 est ais et lorsque desremarques simples permettent de choisir coup sr la donne initiale dans le domaine

de convergence. Pour cela, elle peut tre, par exemple, prcde d'une application de

quelques itrations de la mthode de dichotomie.

Si on veut une mthode d'application plus universelle, la mthode de la scante est

plutt conseiller puisqu'elle ncessite seulement la connaissance de f . Elle est rela-tivement rapide et ne ncessite qu'une valuation de fonction chaque itration. Ce

dernier point peut mme la faire considrer comme plus rapide que la mthode de

Newton. En eet, si on pose :

un := x2n;

le passage de un un+1 ncessite le mme travail qu'une itration de la mthode deNewton. Mais on a :

jun+1 x1j C jx2n+1 x1jp C jun x1jp2

:


Vue ainsi, la mthode est d'ordre p2 = 2; 618::: ! Ce genre de considrations n'est pas ngliger dans une valuation globale du temps de calcul.

Terminons par un exemple :

Rsolution de x 0; 2 sinx 0; 5 = 0 l'aide des quatre algorithmes direntsDichotomie

x1 = 0; 5x0 = 1; 0

Scante

x1 = 0; 5x0 = 1; 0

Newton

x0 = 1Point xe

x0 = 1x = 0; 2 sinx+ 0; 5

1 0; 75 0; 5 0; 5 0; 502 0; 625 0; 61212248 0; 61629718 0; 5958853 0; 5625 0; 61549349 0; 61546820 0; 6122484 0; 59375 0; 61546816 0; 61546816 0; 6149415 0; 609375 0; 615382196 0; 6171875 0; 615454127 0; 6132812 0; 615465878 0; 6152343 0; 615467799 0; 6162109 0; 6154681010 0; 6157226 0; 6154681511 0; 615478512 0; 615356413 0; 615417414 0; 615447915 0; 615453216 0; 6154708817 0; 6154670718 0; 6154689719 0; 61546802520 0; 615468502

Cet exemple conrme les remarques gnrales. La mthode de Newton est la plus rapide.

Ici, la mthode de la scante l'est presque autant. Les deux autres sont de type linaire :

celle du point xe est plus rapide ce qui est cohrent avec le fait que son taux de

convergence est

maxx ddx (0; 2 sinx+ 0; 5)

= 0; 2 au lieu de 0; 5 pour la premire.2.2.5 Acclration de la convergence

D'une manire gnrale, tant donne une suite xn convergeant vers x1, acclrer saconvergence consisite la remplacer par une suite bxn convergeant plus vite vers x1,c'est--dire vriant :

limn!1

bxn x1xn x1 = 0:

Par exemple, si xn converge linairement, on cherchera construire bxn convergeantquadratiquement.

2.2.5.1 Mthode de relaxation

Elle est base sur une ide trs simple. Considrons une mthode de point xe xn+1 =g(xn) qui ne converge pas ou trs lentement vers un point xe x

. L'quation qu'on

cherche rsoudre x = g(x) peut galement s'crire

x+ x = g(x) + x (2.12)


et ce pour tout rel. L'criture de l'quation sous la forme (2.12) suggre d'utiliserune nouvelle mthode de point xe :

xn+1 =g(xn) + xn

+ 1:= G(xn): (2.13)

Maintenant, d'aprs le Thorme 2.1, cette mthode (2.13) va converger (en choisissant

d'initialiser assez prs de la solution) ds que

jG0(x)j =g0(x) + + 1

< 1et ce d'autant plus rapidement que

g0(x) + + 1 est petit. Comme on est parfaitementlibre de choisir le paramtre (qui s'appelle ici paramtre de relaxation), l'ideest de le prendre le plus proche possible de g0(x). Bien sr, la valeur exacte deg0(x) n'est en gnral pas connue, mais par encadrement on peut en avoir des valeursaproches convenables, qu'on peut d'ailleurs ractualiser ventuellement au cours des

itrations. En conclusion cette mthode est trs simple d'utilisation et peut rendre de

prcieux services.

2.2.5.2 Mthode du 2 d'Aitken

An d'illustrer la mthode, commenons par considrer une suite xn convergeant versx1 et telle que :

xn+1 x1 = k (xn x1) o 0 < k < 1:Les nombres k et x1 peuvent tre exprims en fonction des valeurs de la suite xn l'aide des deux quations :

xn+1 x1 = k (xn x1) ;xn+2 x1 = k (xn+1 x1) :On obtient par dirence :

xn+2 xn+1 = k (xn+1 xn) ;et en substituant dans la premire quation mise sous la forme

x1 = xn +xn+1 xn

1 kon a :

x1 = xn (xn+1 xn)2

xn+2 + xn 2xn+1 :

En utilisant les notations des dirences nies, soit

xn = xn+1 xn2xn = xn+1 xn = (xn+2 xn+1) (xn+1 xn) ;ceci s'crit encore :

x1 = xn (xn)2

2xn:

La mthode tire son nom de cette formule. Elle montre ici que la limite x1 cherchepeut tre exactement connue l'aide de xn+2; xn+1; et xn ; n quelconque.


L'ide d'Aitken est de gnraliser cette remarque aux suites convergeant linairement

c'est--dire telles que :

xn+1 x1 = kn (xn x1)avec

limn!1 kn = k 2 [0; 1[ :

Pour une telle suite, le coecient kn est "presque" constant si n est grand et on peutalors faire le calcul prcdent pour se convaincre que :

bxn = xn (xn)22xn

doit tre trs voisin de x1. On a en eet :

Thorme 2.4 Soit une suite xn vriant pour tout entier n, xn 6= x1 et xn+1x1 =(k + "n) (xn x1) avec 0 jkj < 1 et limn!1 "n = 0. Alors la suite dnie par :

bxn := xn (xn)22xn

vrie :

limn!1

bxn x1xn x1 = 0:

Dmonstration : Posons en = xn x1. On a :

2xn = en+2 2en+1 + en = en [(k + "n+1) (k + "n) 2 (k + "n) + 1]= en

h(k 1)2 + n

io n = k ("n+1 + "n) + "n+1"n 2"n:

Puisque n tend vers 0 et en 6= 0; 2xn est dirent de 0 pour n grand et bxn est doncbien dni au moins pour n assez grand. D'autre part

bxn x1 = en "1 (k 1 + "n)2(k 1)2 + n

#:

Mais l'expression entre crochets tend vers 0 quand n tend vers l'inni ce qui prouve lersultat.

Application : Algorithme de Steensen Soit xn dnie par :

xn+1 = g (xn) 8n 0

o g et x0 vrient les hypothses du thorme 2.1. On sait qu'alors xn converge aumoins linairement vers x1. On peut acclrer cette convergence en utilisant la mthodede 2 d'Aitken. Il est alors plus ecace de repartir avec la nouvelle valeur bxn chaquenouvelle itration. Ceci donne l'algorithme suivant dit de Steensen.

Algorithme 2.5 : x0 donn2664Pour n = 0; 1; 2; :::

yn := g (xn) ; zn := g (yn)

xn+1 := xn (yn xn)2

zn 2yn + xn


Remarque 2.11 Cet algorithme est nouveau un algorithme de point xe

xn+1 = (xn) avec

(x) = x (g (x) x)2

g (g (x)) 2g (x) + x:

On peut montrer que si g0 (x1) 6= 0, alors 0 (x1) = 0: On sait qu'alors l'algorithmeassoci converge de faon quadratique. Ainsi, par rapport l'algorithme associ g : on acclre la convergence quand elle a lieu

on a un procd convergeant, mme si jg0 (x1)j 1.Exemple 2.5 : Nous avons vu que si g (x) = x2, la suite dnie par

xn+1 = x2n

converge si jx0j < 1 vers le point xe 0. Le point xe 1 n'est jamais atteint (saufdans le cas irraliste o x0 est exactement gal 1). Ceci est cohrent avec le fait queg0 (1) = 2 > 1.Calculons la fonction dans ce cas :

(x) = xx2 x2

x4 2x2 + x = xx2 (x 1)2

x (x 1) (x2 + x 1)

(x) =xx2 + x 1 x (x 1)

x2 + x+ 1=

x3

x2 + x 1 =x3

(x r1) (x r2)

o r1;2 =1p5

2.

Puisque (x) x3 pour x voisin de 0, si x0 est choisi assez petit, la suite xn secomportera sensiblement comme :

Yn+1 = Y3n ;

d'o convergence d'ordre 3 vers 0.Si x0 est choisi voisin de 1, puisque

0 (1) = 0 et 00 (1) 6= 0, la suite associe converge de faon quadratique vers 1. Ici, il y a donc un gain considrable par rapport g.

Remarque 2.12 Il faut noter que, si l'algorithme 2.5 converge plus vite que celui

associ g, chaque itration comporte deux valuations de la fonction : on y met leprix. Ainsi, une comparaison plus juste consiste mettre sur le mme plan la suite xndnie par l'algorithme 2.5 et la suite Yn dnie par :

Yn+1 = g (g (Yn)) ; Y0 = 1

o chaque itration comporte aussi deux valuations de g. Dans l'exemple prcdent,on a Yn+1 = Y

4n , qui, au voisinage de 0, est d'ordre 4 et donc meilleure que celle donnepar qui est d'ordre 3. Bien sr, on a dans ce cas g0 (x1) = 0 !

Remarque 2.13 D'une manire gnrale, il est illusoire d'esprer obtenir des m-

thodes convergeant plus rapidement sans alourdir le travail chaque itration, soit

en augmentant le nombre d'valuation de fonctions, soit en valuant plus de drives.

Signalons par exemple l'algorithme de Richmond d'ordre 3 pour rsoudre f (x) = xdonn par :

xn+1 = xn 2f (xn) f0 (xn)

f 0 (xn)2 f (xn) f 00 (xn)

:

Cet algorithme parfois utilis converge bien sr rapidement, mais ncessite l'valuation

de f; f 0; f 00 chaque tape.


Thoriquement, il est presque toujours possible d'imaginer des mthodes d'ordre aussi

lev qu'on veut. Du point de vue pratique, elles sont le plus souvent irralistes. D'autre

part, il faut se convaincre qu'une mthode d'ordre 2 est dj trs rapide et qu'en gnral,il est pratiquement dicile de faire mieux. On peut se reporter l'exemple trait

prcdemment : en 4 itrations, la mthode de Newton donne le rsultat avec 8 chiressignicatifs ! Un numricien raisonnable s'en contentera.

2.3 Fonctions valeurs complexes

2.3.1 Cas des quations polynmiales

Bien que les quations polynmiales (ou algbriques) puissent tre rsolues l'aide des

mthodes dcrites plus haut, elles mritent une attention particulire dans la mesure

o elles interviennent trs frquemment dans les applications. Nous verrons, d'une part,

comment proter de la structure polynmiale dans certaines des mthodes gnrales,

d'autre part, nous dcrirons de nouveaux algorithmes permettant de trouver les racines

relles ou complexes d'un polynme.

Rappelons d'abord le thorme fondamental de l'algbre :

Thorme 2.5 (D'Alembert) Tout polynme de degr n admet exactement n zrosrels ou complexes (avec la convention habituelle que des zros de multiplicit r sont

compts r fois).

2.3.1.1 Localisation des zros

La localisation des zros d'un polynme est un problme dicile. On peut utiliser des

techniques d'analyse complexe (indice ou Thorme de Rouch). Des renseignements

peuvent galement tre obtenus sur les zros rels l'aide de la rgle des signes de

Descartes :

Proposition 2.2 Soit le nombre de zros strictement positifs d'un polynme.Soit le nombre de changements de signe des coecients.Alors :

(2.14) est pair (2.15)Exemple 2.6 : Soit P (x) = x4 + 4x2 x 1: = 1 donc 1 comme est pair, on a ncessairement = 1:Par consquent P a une racine positive et une seule.

Les racines ngatives peuvent tre examines aussi puisqu'elles sont les racines positives

de P (x) :P (x) = x4 + 4x2 + x 1Par le mme raisonnement, P a une racine ngative et une seule.Conclusion : P a une racine positive

une racine ngative

deux racines complexes conjugues.

Plusieurs thormes permettent aussi de localiser les zros d'un polynme. Citons en

par exemple un :

Thorme 2.6 Soit P (x) = a0 + a1x+ :::anxn; an 6= 0: Soit r := 1 + max

0kn1

akan :Alors tout zro x0 de P vrie jx0j r:

2.3. FONCTIONS VALEURS COMPLEXES 35

2.3.1.2 Evaluation d'un polynme : algorithme de Hrner

L'valuation d'un polynme en un point peut se faire en calculant chacun des produitsak

ket en faisant leur somme. Cette technique est gnralement peu utilise cause

des erreure de chute qu'elle engendre et cause du nombre trop important d'oprations

lmentaires qu'elle met en jeu, surtout quand le degr est lev.

Voici par exemple ce que donne une valuation du polynme :

P (x) = (1 x)6 = 1 6x+ 15x2 20x3 + 15x4 6x5 + x6

l'aide de sa forme dveloppe. Le calcul a t fait sur un ordinateur CDC 6500

travaillant avec 14 chires signicatifs. Les points ont t relevs par des segments dedroite l'aide d'un traceur.

Figure 2.6 Photo tire du livre Elementary Numerical Analysis par S.D.

Conte et Carl de Boor.

Remarque 2.14 Imaginer ce que la mthode de dichotomie couple avec un tel calcul

de la fonction P peut donner comme rsultat !

On prfre gnralement utiliser l'algorithme de Hrner qui repose sur la factorisation

suivante du polynme :

P (x) = anxn + an1xn1 + :::+ a2x2 + a1x+ a0;

soit :

P (x) = a0 + x (a1 + x (a2 + x (a3 + :::+ x (an2 + xan1 + xan)) : : :))


d'o :

Algorithme 2.6 : valuation de P ()2664bn := ande i = n 1 0bi := ai + bi+1P () := b0:

Comme sous-produit intressant, on obtient le polynme P1 (x) tel que :

P (x) = (x )P1 (x) + b0; (2.16)c'est--dire le quotient de la division de P (x) par (x ). Il est donn par :

P1 (x) = bnxn1 + bn1xn2 + :::+ b2x+ b1:

En eet, le quotient de xk dans (x )P1 (x) + b0 est gal :bk bk+1 = ak pour k = 1; : : : ; n 1 ;

bn = an pour k = n

b0 = a0 pour k = 0

Si on drive la formule (2.16), on obtient

P 0 (x) = P1 (x) + (x )P 01 (x) :En particulier :

P 0 () = P1 () : (2.17)

On peut donc utiliser les bi prcdents pour valuer la drive de P au mme point ,toujours l'aide de l'algorithme de Hrner.

Algorithme 2.7 : valuation de P 0 ()2664cn := bnde i = n 1 1ci := bi + ci+1P 0 () := c1:

Ainsi, l'algorithme de Newton prend la forme suivante pour un polynme P (x) =a0 + a1x+ :::+ anx

n:

Algorithme 2.8 : Rsolution de P (x) = 0 par la mthode de Newton partir d'unevaleur approche x0 d'un zro rel.2666666664

Pour m = 0; 1; ::: := xmbn := an ; cn := an ;Pour i = n 1 1

bi := ai + bi+1 ; ci := bi + ci+1 ;b0 := a0 + b1 ;

xm+1 := xm b0c1 :

Remarque 2.15 Comme dans le cas gnral, il faut s'attendre des dicults lorsque

P 0 (x1) = 0, c'est--dire lorsque le zro cherch est multiple.


Remarque 2.16 La formule (2.16) montre, puisque P (x1) = 0, que :

P (x) = (x x1)P1 (x)o une approximation de P1 (x) est obtenue l'aide des derniers coecients bi calculs.Pour calculer une autre racine de P , on peut utiliser ce polynme P1 de degr moindreet lui appliquer la mme mthode (P1 est appel polynme rduit).

Evidemment, les coecients de ce polynme ne sont connus que de faon approche ce

qui entachera d'erreur tous les calculs subsquents. On constate, d'une manire gnrale,

que ces erreurs sont moins importantes lorsqu'on calcule les zros dans l'ordre croissant

de leur valeur absolue.

2.3.1.3 Dtermination de tous les zros

Pour pallier les inconvnients prcits, Maehly a propos une mthode qui s'avre ef-

cace au niveau de la prcision des rsultats : supposons avoir dj calcul les r zros

1; 2; :::; r. Le polynme rduit est alors :

Pr (x) =P (x)

(x 1) (x 2) ::: (x r) :

La mthode de Newton applique Pr, soit

xi+1 := xi Pr (xi)P 0r (xi)

peut tre mise en oeuvre l'aide de la formule :

xi+1 := xi P (xi)P 0 (xi)

Prk=1

P (xi)(xik)

qui se dmontre aisment. L'avantage de cette mthode est qu'elle converge quadrati-

quement vers j+1 mme si les k; k = 1; :::; r, ne sont pas des zros de P . Elle n'estdonc pas sensible aux erreurs prcdentes sur les k; k = 1; :::; r:

Remarque 2.17 Les coecients d'un polynme sont souvent connus seulement de

manire approche (cf. remarque prcdente). Il est donc important de connatre la

sensibilit d'une racine une variation des coecients (cf. notion de conditionnement

dnie au chapitre prcdent).

En bref, on peut dire que :

une racine multiple est toujours mal conditionne

une racine simple peut l'tre aussi, et ce pour des polynmes apparemment anodins.

Exemple 2.7 (d Wilkinson - voir l'analyse du conditionnement dans "Introduction

to Numerical Analysis" par J. Stoer, R. Burlisch) :

P (x) = (x 1) (x 2) ::: (x 20) =20Xi=0

aix20i:

P est un polynme dont toutes les racines sont relles et bien spares. Cependant, onpeut montrer que, pour une variation de " du coecient a5, la 16me racine subit uneperturbation de

" 3; 7 1014 !ce qui veut dire qu'un calcul 14 chires dcimaux signicatifs ne donnera aucun chiresignicatif sur 16.


Intressons-nous maintenant aux zros complexes d'un polynme P . Il est clair que siP a ses coecients rels et si la donne initiale x0 est relle, l'algorithme de Newton nepourra converger vers un zro non rel, mme si x0 est proche de ce zro dans le champcomplexe, ceci puisque tous les xn sont ncessairement rels. Si on veut obtenir un zrocomplexe, il faut alors a priori utiliser l'arithmtique complexe. Si on veut l'viter, on

peut prfrer l'algorithme suivant qui permet de trouver les zros complexes tout en

travaillant en nombres rels.

2.3.1.4 Mthode de Bairstow

Elle part de l'observation que trouver deux zros ; complexes conjugus de P (x)revient trouver un polynme de degr 2, x2 rx s admettant ; comme zros ettel que

P (x) =x2 rx sQ (x) :Pour r et s xs, on peut toujours crire la division euclidienne de P par x2 rx ssous la forme

P (x) =x2 rx sQ (x) +A (x r) +B (2.18)o degQ = degP 2 et A et B sont des constantes dtermines de faon unique.Ceci tant vrai pour tout r et s, on dnit ainsi des fonctions A (r; s) et B (r; s), et leproblme pos revient dterminer r et s solutions de

A (r; s) = 0B (r; s) = 0:(2.19)

Il s'agit d'un systme non linaire de deux quations deux inconnues. Nous verrons

dans le paragraphe suivant que la mthode de Newton que nous avons vue pour une

quation une variable se gnralise au cas de plusieurs variables. Ainsi, appliquant

cette mthode au systme (2.19), on est conduit l'itration :

r0; s0 choisis ("assez prs" de la solution)ri+1si+1

: =

risi

"

@[email protected]

@[email protected]

@[email protected]

@[email protected]

#1r=ri; s=si

A (ri; si)B (ri; si)

;

o []1 signie qu'on prend l'inverse de la matrice et donc qu'on rsout un systme

linaire 2 2. On a doncri+1si+1

:=

risi

ABsBAs

ArBsBrAsArBABrArBsBrAs

!r=ri; s=si

: (2.20)

(Ici on a pos Ar [email protected]@r ; As =

@[email protected] ; :::). Le calcul de A;B;Ar; As; Br; Bs est men de lafaon suivante.

Posons :

P (x) = anxn + an1xn1 + :::+ a1x+ a0:

Q (x) = bnxn2 + bn1xn3 + :::+ b3x+ b2:

Identiant les coecients des puissances de x dans (2.18), on obtient8>>>>>>>>>>>>>:

bn := anbn1 := an1 + rbnbn2 := an2 + rbn1 + sbn.

.

.

.

.

.

.

.

.b2 := a2 + rb3 + sb4A := a1 + rb2 + sb3B := a0 + rA+ sb2:

(2.21)


Pour obtenir les drives de A et B, on direncie le systme (2.21) par rapport r ets. On remarque que les ai sont indpendants de r et s et donc drives nulles. Posantalors :

8k = 2; :::; n Ck = (bk)r ; C1 = Ar; C0 = Br8k = 2; :::; n dk = (bk)s ; d1 = As; d0 = Bson obtient :8>>>>>>>>>>>>>>>>>>>>>>>:

Cn := 0 dn := 0Cn1 := bn dn1 := 0Cn2 := bn1 + rCn1 dn2 := bnCn3 := bn2 + rCn2 + sCn1 dn3 := bn1 + rdn1

dn4 := bn2 + rdn2 + sdn1::::::::::::::::::::::::::::::::::::::::::::: :::::::::::::::::::::::::::::::::::::::::::::C2 := b3 + rC3 + sC4 d2 := b4 + rd4 + sd3C1 := b2 + rC2 + sC3 d1 := b3 + rd3 + sd2C0 := A+ rC1 + sC2 d0 := b2 + rd2 + sd1

9>>>>>>>>>>>>=>>>>>>>>>>>>;On constate qu'en fait les deux algorithmes ci-dessus sont identiques et qu'en particulier

d0 = C1 (= Bs = Ar) et As = d1 = C2: D'o :

Algorithme 2.9 (Bairstow) : les coecients a0; :::; an sont donns. On choisit unevaleur initiale (r0; s0)266666666666664

De i = 0 ... (test d'arrt)bn := an; bn1 := an1 + ribn; Cn1 := bn; Cn2 := bn1 + rCn124 de k = n 2 1bk := ak + ribk+1 + sibk+2Ck1 := bk + riCk + siCk+1

b0 := a0 + rib1 + sib2

ri+1 := ri b1C1 b0C2C21 C0C2

si+1 := si C1b0 b1C0C21 C0C2

:

2.3.1.5 Mthode de Mller

Nous terminons ce paragraphe par un dernier algorithme qui permet de calculer tous

les zros rels ou complexes d'une quation algbrique ou mme d'une quation non

linaire plus gnrale inconnue relle et complexe. C'est en fait une gnralisation

de la mthode de la scante : au lieu d'interpoler la fonction f donne l'aide d'unefonction linaire sur [xi1; xi], on l'interpole l'aide du polynme de degr 2 prenantles valeurs f (xi2) ; f (xi1) ; f (xi) respectivement aux points xi2; xi1; xi:On verra au chapitre suivant que ce polynme est donn par :

q (x) = f (xi) + (x xi) f [xi; xi1] + (x xi) (x xi1) f [xi; xi1; xi2]o f [:] reprsente les dirences divises introduites prcdemment, qui sont dniespar rcurrence et que nous tudierons plus amplement au chapitre 3.

Dans l'algorithme, le point xi+1 est alors obtenu comme l'un des zros de q (x). Cecalcul peut tre conduit explicitement puisqu'il s'agit d'une quation du second degr.

Auparavant, rcrivons q (x) en utilisant :

(x xi) (x xi1) = (x xi)2 + (x xi) (xi xi1) ;


soit

q (x) = f (xi) + Ci (x xi) + f [xi; xi1; xi2] (x xi)2

avec

Ci = f [xi; xi1] + (xi xi1) f [xi; xi1; xi2] :Ainsi

xi+1 := xi +2f (xi)

Ci fC2i 4f (xi) f [xi; xi1; xi2]g12

o on choisit entre + et de faon rendre le dnominateur le plus grand possibleen module (noter qu'on obtiendra des nombres complexes non rels ds que C2i 4f (xi) f [xi; xi1; xi2], d'o la ncessit de travailler en arithmtique complexe pourobtenir les zros complexes).

On obtient l'algorithme suivant :

Algorithme 2.10 (Mller) : on choisit x0; x1; x2266666666666666666666666664

h1 := x1 x0; h2 := x2 x1f [x1; x0] :=

f(x1)f(x0)h1

; f [x2; x1] :=f(x2)f(x1)

h22666666666664

Pour i = 2; 3; :::f [xi; xi1; xi2] := (f [xi; xi1] f [xi1; xi2]) = (hi+1 + hi)Ci := f [xi; xi1] + hif [xi; xi1; xi2]

hi+1 := 2f (xi) =Ci

C2i 4f (xi) f [xi; xi1; xi2]

12

et on choisit le signe pour que le dnominateur de jhi+1j soit le plus grand possiblexi+1 := xi + hi+1on calcule f (xi+1)f [xi+1; xi] := (f (xi+1) f (xi)) =hi+1:Arrt lorsque jxi+1 xij < " jxi+1jou

jf (xi+1)j < "ou

lorsque le nombre maximum d'itrations prx est atteint.

Remarque 2.18 Il faut noter que chaque itration de cet algorithme ne ncessite

qu'une seule valuation de f (qu'on peut faire l'aide de l'algorithme de Hrner si fest un polynme). On obtient pourtant une mthode d'ordre 1; 84::: = q o q est laplus grande racine de q3 q2 q 1 = 0. Ceci s'obtient comme dans la mthode de lascante en montrant que si ei = jxi x1j, alors ei+1 Ceiei1ei2: Cette mthode servle trs ecace dans la pratique et relativement prcise.

2.4 Systme d'quations non linaires

2.4.1 Introduction

Reprenons les mthodes tudies au paragraphe 2.2. Il est clair que la mthode de

dichotomie n'a aucun sens en dimension N 2. En revanche, les trois autres mthodespeuvent s'adapter au cas d'une fonction F : RN ! RN . Passons rapidement sur lesmthodes de point xe qui ncessitent que le systme d'quations rsoudre soit crit

sous la forme 8>>>>>:x1 = g1(x1; x2; : : : ; xN )x2 = g2(x1; x2; : : : ; xN ).

.

.

.

.

.

xN = gN (x1; x2; : : : ; xN ) :

(2.22)

2.4. SYSTME D'QUATIONS NON LINAIRES 41

Il est assez rare que la mthode de point xe crite partir du systme (2.22) converge,

les conditions de convergence tant plus diciles raliser qu'en dimension un. Il faut

en eet que pour une certaine norme matricielle (voir chapitre 6), la norme de la matrice

Jacobienne de F soit strictement infrieure 1 au point recherch. On peut bien srenvisager des mthodes d'acclration de convergence comme au paragraphe 2.2.5. Nous

faisons le choix de prsenter plutot ici les mthodes gnralisant la mthode de Newton

et celle de la scante.

2.4.2 La mthode de Newton-Raphson

Considrons un systme d'quations s'crivant F (X) = 0 ou encore, de faon dveloppe8>>>>>:f1(x1; x2; : : : ; xN ) = 0f2(x1; x2; : : : ; xN ) = 0.

.

.

.

.

.

fN (x1; x2; : : : ; xN ) = 0 :

(2.23)

La gnralisation naturelle de la formule de Newton unidimensionnelle

xn+1 = xn (f 0(xn))1f(xn)fait intervenir la matrice Jacobienne de F :

F 0(Xn) =

[email protected]@[email protected]

@[email protected]

: : : @[email protected]

.

.

.

.

.

.

.

.

.

.

.

@[email protected]

@[email protected]

: : : @[email protected]

1CA (2.24)toutes les drives partielles tant values au point Xn. La mthode de Newton-Raphson s'crit donc formellement

Xn+1 = Xn [F 0(Xn)]1F (Xn) : (2.25)Le second membre de (2.25) est parfaitement dni car on eectue le produit d'une

matrice NN par un vecteur de RN . Dans la pratique, on ne calcule pas explicitementl'inverse de la matrice Jacobienne, ce qui s'avrerait trop coteux, et on prfre crire

l'algorithme sous la forme suivante :

Algorithme 2.11 (Newton-Raphson)2664X0 donn ;pour n = 0; 1; : : : ; test d'arrt , faire

Rsolution du systme linaire F 0(Xn)n = F (Xn)Xn+1 = Xn + n

Remarque 2.19 Encore plus qu'en dimension 1, le choix de l'initialisation est crucial

et le risque de divergence, si on ne dmarre pas proximit de la solution cherche, est

grand.

Remarque 2.20 La convergence est l aussi d'ordre 2, donc trs rapide (quand il y a

convergence !)

Remarque 2.21 Dans le cas des systmes de grande dimension, la mthode de Newton-

Raphson s'avre assez coteuse puisqu'il faut valuer chaque itration N2 +N fonc-tions (les N2 drives partielles de la matrice Jacobienne, plus les N fonctions coordon-nes). De plus, il y a un systme linaire N N (dont la matrice est en gnral pleine)


rsoudre. Pour pallier le premier inconvnient, il est frquent qu'on ne recalcule pas

la matrice Jacobienne chaque itration, mais seulement de temps en temps. Bien sr,

ce moment-l, la convergence n'est plus quadratique, mais en temps de calcul il arrive

qu'on y gagne beaucoup, en particulier quand les drives de F sont trs coteuses calculer.

2.4.3 La mthode de Broyden

La mthode de Broyden s'inspire directement de la remarque 2.21 ci-dessus en poussant

mme la logique un peu plus loin. Puisqu'il est coteux (voire mme dans certains cas

impossible) de calculer la matrice Jacobienne de F , on va se contenter d'en dterminerune valeur approche chaque itration Bn. De plus la suite de matrices Bn se calculerasimplement par rcurrence.

On peut considrer que la mthode de la scante, en dimension un, est base un peu

sur le mme principe. En eet elle revient approcher

f 0(xn) parf(xn) f(xn1)

xn xn1 :

En dimension N , on va simplement imposer la suite de matrices Bn de vrier lamme relation :

Bn(Xn Xn1) = F (Xn) F (Xn1) : (2.26)Bien sr, la relation (2.26) ne dnit pas la matrice Bn. Elle n'impose que sa valeur dansune direction. Broyden a fait le choix simple de considrer qu'on pouvait passer de Bn Bn+1 en rajoutant simplement une matrice de rang 1. Ainsi, sa formule d'actualisations'crit,

Bn+1 = Bn +(Fn BnXn)(Xn)T

kXnk2 (2.27)

o on a not Xn = Xn+1Xn et Fn = F (Xn+1)F (Xn). On vrie immdiatementque la suite de matrice Bn dnie par (2.27) satisfait bien (2.26). La mthode deBroyden s'crit donc :

Algorithme 2.12 (Broyden)266666664

X0 et B0 donns; pour n = 0; 1; : : : ; test d'arrt, faire

Rsolution du systme linaire Bnn = F (Xn)Xn+1 = Xn + n ; Fn = F (Xn+1) F (Xn)

Bn+1 = Bn +(Fn Bnn)(n)T

knk2Remarque 2.22 On peut prendre comme matrice initiale B0 = Id, il faut videmmentattendre un certain temps avant d'avoir une approximation raisonnable de la matrice

Jacobienne.

Remarque 2.23 On peut dmontrer qu'en gnral, comme pour la mthode de la

scante, la convergence est superlinaire. La suite de matrices Bn ne converge pasforcment vers la matrice Jacobienne de F .

2.5 Exercices du chapitre 2

Exercice 2.1 Etudier la convergence des mthodes de point xe suivantes (on cherche

approcher

p2). Appliquer des mthodes d'acclration de la convergence pour rendre

2.5. EXERCICES DU CHAPITRE 2 43

ces algorithmes convergents quand ils ne convergent pas ou plus rapides quand ils

convergent.

xn+1 =2xn

xn+1 =12 (xn +

2xn

)

xn+1 = 2xn 2xnxn+1 =

13 (2xn +

2xn

)

Exercice 2.2 Pour les fonctions suivantes, trouver un algorithme de point xe (autre

que la mthode de Newton !) qui converge vers le plus petit zro positif de

1. x3 x 1 = 02. x tanx = 03. ex cosx = 0.Exercice 2.3 Trouver les racines des polynmes suivants

x4 56; 101x3 + 785; 6561x2 72; 7856x+ 0; 078

x7 28x6 + 322x5 1960x4 + 6769x3 Ax2 + 13068x 5040avec A = 13132, puis A = 13133:

Exercice 2.4 En utilisant la formule de Taylor, imaginer un algorithme modiant la

mthode de Newton et assurant une convergence quadratique dans le cas d'une racine

multiple de f .

Exercice 2.5 En appliquant le Thorme de Rouch (voirs cours d'analyse complexe)

et la rgle de Descartes, localiser au mieux les zros des polynmes

x6 6x4 + 2x3 + x 1 x5 2x4 + 8x3 3x2 + 1 :

Chapitre 3

Interpolation et approximation

polynmiale

Dans ce chapitre, on dispose d'une fonction f , connue par exemple uniquement parses valeurs en certains points, et on cherche remplacer ou approcher f par unefonction plus simple, le plus souvent par un polynme. Nous verrons dans ce contexte,

l'interpolation qui consiste rechercher un polynme qui passe exactement par les points

donns, l'interpolation par morceaux, en particulier les fonctions splines o l'expression

du polynme est dirente sur chaque sous-intervalle, l'approximation uniforme ou

l'approximation au sens des moindres carrs ou on cherche approcher au mieux la

fonction, soit pour la norme uniforme (ou norme innie), soit pour la norme euclidienne.

Cette dernire approche conduira naturellement aux fonctions trigonomtriques et aux

sries de Fourier, et on prsentera la Transforme de Fourier Rapide ou F.F.T.

3.1 Interpolation de Lagrange

3.1.1 Le polynme d'interpolation

Soit f : [a; b] ! R connue en n+1 points distincts x0; x1; :::xn de l'intervalle [a; b]. Ils'agit de construire un polynme P de degr infrieur ou gal n tel que

8i = 0; 1; :::n P (xi) = f(xi) (3.1)

Thorme 3.1 Il existe un et un seul polynme de degr infrieur ou gal n solutionde (3.1). Le polynme s'crit

Pn(x) =nXi=0

f(xi)Li(x) (3.2)

o

Li(x) =Y

k=0 k 6=i

(x xk)(xi xk) : (3.3)

Remarque 3.1 Le polynme Pn est appel polynme d'interpolation de Lagrange dela fonction f aux points x0; x1; :::xn:Les polynmes Li(x) sont appels polynmes de base de Lagrange associs ces points.

45

46 CHAPITRE 3. INTERPOLATION ET APPROXIMATION POLYNMIALE

Dmonstration du Thorme 3.1 :

Existence : On vrie directement que le polynme donn par (3.2) est solution de (3.1)

(on utilise le fait que Li(xj) = ij).Unicit : Soit Q un autre polynme solution. Alors 8i = 0; 1; :::n Q(xi) P (xi) = 0:Ainsi QP est un polynme de degr infrieur ou gal n s'annulant en n+1 points.Il est donc identiquement nul.

Exemple 3.1 : Interpolation linaire. On applique (3.2) avec n = 1 pour trouver

P1(x) = f(x0)(x x1)(x0 x1) + f(x1)

(x x0)(x1 x0) :

Ceci s'crit encore

P1(x) = f(x0) +f(x1) f(x0)

x1 x0 (x x0) : (3.4)

Remarque 3.2 L'criture (3.2) du polynme d'interpolation est intressante au point

de vue thorique, mais peu du point de vue numrique : elle a un caractre peu algo-

rithmique. De plus, son valuation requiert trop d'oprations lmentaires.

On lui prfre la formule de Newton qui consiste crire le polynme d'interpolation

Pn aux points x0; x1; :::xn sous une forme gnralisant (3.4) soit :

Pn(x) = an0 + a

n1 (x x0) + :::+ ann (x x0) (x x1) ::: (x xn1) :Notons d'abord que tout polynme de degr infrieur ou gal n peut se mettre souscette forme ds que les xi sont tous distincts. L'avantage de cette criture est que lapartie tronque

an0 + an1 (x x0) + an2 (x x0) (x x1) + :::+ an1n (x x0) (x x1) ::: (x xn2)n'est pas autre chose que Pn1(x) : en eet, il s'agit d'un polynme de degr infrieurou gal n 1 tel que :

8i = 0; 1; :::n 1 Valeur en xi = Pn(xi) = f(xi):Donc, connaissant Pn1, il sut de calculer ann pour connatre Pn (a

nn est aussi le

coecient de xn dans Pn crit sous forme usuelle). Les ain sont donns par la formule

de Newton :

Thorme 3.2 (Formule d'interpolation de Newton) Le polynme d'interpolation

de Lagrange de la fonction f aux points distincts x0; x1; :::xn est donn par :

Pn(x) =

nXi=0

f [x0; x1; :::xi]

i1Yk=0

(x xk) (3.5)

o f [:] dsigne les dirences divises de f dnies par :

i = 0; :::; n f [xi] = f(xi) (3.6)

f [x0; x1; :::; xk] :=f [x1; :::; xk] f [x0; :::; xk1]

xk x0 : (3.7)

Remarque 3.3 Par convention

Qi1k=0(x xk) := 1 si i < 1.Dmonstration : On la fait par rcurrence sur le nombre de points xi. La formule (3.5) est vraie pour n = 1 (cf. (3.4)).

3.1. INTERPOLATION DE LAGRANGE 47

Supposons la vraie pour n points. On a alors :

Pn(x) = Pn1(x)+annn1Yk=0

(xxk) =n1Xi=0

f [x0; x1; :::; xi]n2Yk=0

(xxk)+annn1Yk=0

(xxk):

Reste calculer ann. Considrons

Q(x) =x x0xn x0Qn1(x) +

xn xxn x0Pn1(x)

o Qn1(x) =Pn

i=1 f [x1; :::; xi]Qn1

k=1(xxk) est le polynme d'interpolation de f auxn points x1; x2; :::; xn: On vrie immdiatement que :

8i = 0; 1; :::; n Q(xi) = f(xi):

Puisque degQ n; Q Pn: Cette nouvelle expression de Pn nous permet d'armerque le coecient de xn de Pn est donn par

ann =1

xn x0 f [x1; :::; xn]1

xn x0 f [x0; x1; :::; xn] :

3.1.2 Proprits des dirences divises

i) f [x0; x1; :::; xn] est invariant par des permutations sur les xi : en eet, permuter lesxi ne change pas le polynme d'interpolation et donc ne change pas le coecient duterme de plus haut degr.

ii) si f = Q est un polynme de degr q

Q [x0; x1; :::; xn] =

0 si q < ncoecient du terme de plus haut degr de Q si q = n:

En eet, si q n, l'interpol de Q n'est autre que Q lui-mme.iii) table des dirences divises : permet de calculer de faon inductive les dirences

divises d'une fonction selon le shma suivant :

x0 f [x0]f [x0; x1]

x1 f [x1] f [x0; x1; x2]f [x1; x2] f [x0; x1; x2; x3]

x2 f [x2] f [x1; x2; x3].

.

.

f [x2; x3]x3 f [x3].

.

.

.

.

.

.

.

.

.

.

.

.

.

. f [xn1; xn]xn f [xn]

Les coecients de la formule de Newton sont donns par les premiers lments de

chaque colonne (diagonale (1)).

iv) valuation de Pn(x) : Nous avons vu au paragraphe prcdent que l'algorithme deHrner permet l'valuation d'un polynme en un point de faon plus rapide et plus

stable que la forme dveloppe usuelle. La mme remarque vaut ici pour la formule de

Newton.

48 CHAPITRE 3. INTERPOLATION ET APPROXIMATION POLYNMIALE

Pour mettre en oeuvre l'algorithme de Hrner, il est plus agrable d'utiliser la formule

de Newton aux points xn; xn1; :::; x1; x0 soit

Pn(x) =nXi=0

f [xi; :::; xn]nY

k=i+1

(x xk):

Algorithme 3.1 : Evaluation de Pn(x) : on suppose les valeurs f(xi) mises e

Polyana Num

Text of Polyana Num

Transmissions Num eriques { L3

France Num - entreprises.gouv.fr

Médias sociaux identité num

An Num Chap11

Metro num 2013_ca_beauvaisis_a_castaing

Leur Cod Num

Modelisation Num S9

Cours analyse-num source1

20120708 el watan num spe

Cours d’électronique numérique · Cours d’électronique numérique Cours d’électronique numérique Aurélie Gensbittel Enseignante-Chercheuse Bertrand Granado Enseignant-Chercheur

Planète Num

Réseau ICÉRAMM - Huma-Num

LA TRIBUNE D'HUMA-NUM - Huma-Num : l'infrastructure des ... · de préparer les changements futurs pour le monde SHS tant Huma-Num#Actu LA TRIBUNE D'HUMA-NUM Huma-Num. La nouvelle

Espace Infusion -Culture Num. (2011)

Cultiver son identité num

Floyd Num Ch13

Num 1020 CnC manual

Advanced Web Num 1

Imagier num metier

Ateliers num eriques - RESEAU FEMTOreseau-femto.cnrs.fr/IMG/pdf/Houches_scilab.pdf · 2016-03-29 · Ateliers num eriques L’objet de ces s eances de travaux pratiques num eriques

Copro-Parasitologie Pratique Doc Num

TD méthod num

Gazette num 10

Baromètre France Num

Num ro 2 printemps

e2 Proj Num Thermometre Rapport

Î~ NUM ÉROD EC PEN - COURS D'ATI RIBUTION - Freejcautran.free.fr/.../legislatives/1981/lettre_du_depute.pdf · 2016-12-18 · NUM ÉRO 5 OU 29 MAI 198' 1 LA .. _ ,# Î~ NUM ÉROD

bas el num

20120704 num special elwatan

Rapport Fondation Num final

Documents

Polyana Num

Text of Polyana Num