Analyse Numérique 1 - Cours

Analyse numérique 1 1 Chapter 1 Notions d’erreurs 1.1 Les quantités On a deux quantités l’une exacte et l’autre approchée p Exemple 1 La quantité exacte: 5, 3/7, 3; e; ; log(5); sin(3); cos(5); : tan(1)::::::...

Analyse numérique 1 1 Chapter 1 Notions d’erreurs 1.1 Les quantités On a deux quantités l’une exacte et l’autre approchée p Exemple 1 La quantité exacte: 5, 3/7, 3; e; ; log(5); sin(3); cos(5); : tan(1):::::: p Exemple 2 La quantité approximative où valeur approchée: 5 ' 2:236::::; ' 3:141:::; ln(2=3) ' 0:405::::: Dé…nition 1 Soient x un nombre donné et x une valeur approchée de ce nombre. 1- si x >x, x est dite valeur approchée par excée. 2- si x 1 : la suite diverge ( est un point …xe répulsif).Plus précisément, si d: g 0 ( ) > 1, la suite diverge de facon monotone. e: g 0 ( ) < 1 la suite diverge de facon oscillante (spirale). Remarque 10 Si on touve des di¢ cultés pour déterminer la foction g; on écrit la fonction sous la forme g(x) = x + f (x) et on choisit le parametre qui véri…t l’inéquation jg 0 (x)j < 1 Accélération de la convergence Lemme 1 On suppose que g 0 (tel que x = g(x)) existe.Plus g 0 ( ) est petite , plus la convergence est rapide. Accélération: soit 6= 1 on ajoute x au deux cotés on obtient: x + x = x + g(x) alors x + g(x) x= = h(x) 1+ la constante est choisie de maniére a ce que h0 (xn ) = 0 18 pour chaque itération ce qui conduit à + g 0 (xn ) = h0 (xn ) = 0 ) = g 0 (xn ) 1+ alors la converge, de la suite xn + g(xn ) xn+1 = ; = g 0 (xn ) 1+ sera plus rapide que la suite xn+1 = g(xn ) Exemple 26 On considére l’équation: x f (x) = 0; f (x) = x e l’équation admet une solution unique dans l’intervalle I = [0:5; 1] et g(x) = e x satisfait les conditions du point …xe alors g 0 (x) = e x alors la converge, de la suite: (xn + 1)e( xn ) xn+1 = ; = g 0 (xn ) = e( xn ) 1 + e( xn ) sera plus rapide que la suite xn+1 = e( xn ) Algorithme d’accélération 1-calculer x0 ; x1 ; :::; xn par la méthode lente x0 2 [a; b] xn+1 = g(xn ); n = 0; 1; 2::: où N est choisi selon chaque cas 2- On pose = g 0 (xn ) 3- On cherche les approximations x0 2 [a; b] xn+1 = h(xn ); n = 0; 1; 2::::::: 19 2.4.4 Majoration d’erreur Critère d’arret 1 pour la méthode du point …xe Soit la racine exacte de (2.1) et xn est la racine approximative, alors on a jxn j k n jb aj si on calcule la racine approchée avec m décimales exactes on a jxn j K n jb aj " = 0:5 10 m alors ln("=(b a)) n (2.3) ln(K) Critère d’arret 2 pour la méthode du point …xe Théoréme 10 4- On a une majoration de l’erreur commise à l’itération n,pour tout n 2 IN on a Kn jxn j jx1 x0 j 1 K Soit la racine exacte de (2.1) et xn est la racine approximative, alors on a jxn j = jxn xn+1 + xn+1 j jxn xn+1 j + jxn+1 j) jxn+1 xn j + jxn+1 j jg(xn ) g(xn 1 )j + jg(xn ) g( )j K jxn xn 1 j + K jxn j (1 K) jxn j K jxn xn 1 j K 2 jxn 1 xn 2 j K 3 jxn 2 xn 3 j K n jx1 x0 j jxn xn 1 j = jg(xn 1 ) g(xn 2 )j K jxn 1 xn 2 j = K jg(xn 2 ) g(xn 3 )j K 2 jxn 2 xn 3 j :::::: K n 1 jx1 x0 j donc Kn ) jxn j jx1 x0 j 1 K 20 alors si on calcule la racine approchée avec une précision " on a K jxn j jxn xn 1 j " 1 K Kn jx1 x0 j " 1 K alors on arrete les itérations lorsque 1 k jxn xn 1 j " (2.4) k ou (1 K) n ln( ")= ln(K) jx1 x0 j Proof. Unicité du point …xe : Supposons que g admet un autre point …xe 1 di¤erent de alors on a : jg( ) g( 1 )j= j 1j Kj 1 j ou encore (1 K) j 1j = 0 mais comme k < 1, alors = 1 Algorithme 4 Méthode du point …xe étape 1: entré: g(x); x0 ; " étape 2: la suite de recurrence :xn+1 = g(xn ) étape3: si jxn+1 xn j < " aller à l’étape 4 si non aller à l’étape 2 étape 4: sortie: a¢ her = xn+1 aller à l’étape 5 étape 5: …n 2.4.5 Méthode de Newton-Raphson (ou Newton ou des tangantes) En prenant la fonction g dé…nie par :g(x) = x ff0(x) (x) on obtient le procédé de Newton-Raphson donné par : ( xn+1 = xn ff0(x n) (xn ) pour n 0 (2.5) x0 donné avec f 0 (xn ) 6= 0 Théoréme 11 Soit une fonction de classe C 2 sur [a; b] satisfaisant les con- ditions suivantes : 1- f (a):f (b) < 0 21  2- 8x 2 [a; b]; f 0 (x) 6= 0 ( f est strictement monotonne) 3-8x 2 [a; b]; f 00 (x) 6= 0 ( f est convexe ou concave) Alors en choisissant x0 2 [a; b] tel que f 00 (x0 )f (x0 ) > 0, les itérations de Newton-Raphson (2.5) convergent vers l’unique solution de f (x) = 0 dans [a; b]: Théoréme 12 (théorème equivalant) Soit une fonction f de classe C 2 sur [a; b] satisfaisant les conditions suivantes : 1- f (a):f (b) < 0 2- 8x 2 [a; b]; f 0 (x) 6= 0 ( f est strictement monotonne) 3-8x 2 [a; b]; f 00 (x) 6= 0 ( f est convexe ou concave) 4- ff0(a) (a) b a , ff0(b)(b) b a Alors la méthode de Newton-Raphson (2.5) converge vers l’unique solution l de f (x) = 0 dans [a; b]et ceci pour n’importe quel choix de x0 2 [a; b]. Exemple 27 Considérons l’équation f (x) = x3 x2 + x 1 = 0; x 2 I = [0; 2] On a f est dé…nie ,continue et dérivable sur I , 1- f (0) = 1 < 0, f (2) = 8 4 + 2 1 = 5 > 0; donc f (0)f (2) < 0. 2-8x 2 I = [0; 2] , f 0 (x) = 3x2 2x + 1 = 0 ) = 4 12 < 0 ) 0 00 f (x) 6= 0; f (x) > 0 3-8x 2 I = [0; 2] , f "(x) = 6x 2 6= 0 4-f (0)f 00 (0) > 0 alors l’algoritme de Newton-Raphson (2.5) convergent vers l’unique solu- tion de f (x) = 0 dans I=[0; 2]: 2.4.6 Méthode de Newton modi…eé f (x) En prenant la fonction g dé…nie par : g(x) = x f 0 (x0 ) on obtient la méthode de Newton modi…ée comme suit f (xn ) xn+1 = xn (2.6) f 0 (x0 ) pour n 0 on montre alors que cette méthode est d’ordre 1. Autres modi…c- ations de la méthode de Newton peuvent etre obtenues en prenant f 0 (x (n) )) pour des valeurs intérmédaires. Remarque 11 Si l’equation f (x) = 0 admet une racine de multiplicité p alors on utilise la méthode de Newton modi…ée f (xn ) xn+1 = xn p ; pour n 0 , x0 donné (2.7) f 0 (xn ) 22 Exemple 28 soit f (x) = (x 1)3 exp(x); I = [0; 2] , = 1 est une racine d’ordre 3, soit 1 g(x) = f 3 (x) 1 alors g 0 (x) = 13 f 3 1 (x)f 0 (x); donc la méthode de Newton pour la foction g est g(xn ) xn+1 = xn g 0 (xn ) 1 f 3 (xn ) = xn 1 1 1 3 f 3(xn )f 0 (xn ) f (xn ) = xn 3 0 f (xn ) 2.4.7 Critére d’arret pour la méthode du Newton Soit la racine exacte de (2.1) , alors on a jxn j ' jxn xn+1 j (2.8) alors si on calcule la racine approchée avec m décimales exactes on a m jxn xn+1 j " = 0:5 10 Remarque 12 Le meme citére d’arret pour la méthode de la sécante, jxn xn+1 j " Algorithme 5 Méthode du point …xe étape 1: entré: g(x); x0 ; " étape 2: la suite de recurrence :xn+1 = xn ff0(x n) (xn ) étape3: si jxn+1 xn j < " aller à l’étape 4 si non aller à l’étape 2 étape 4: sortie: a¢ her = xn+1 aller à l’étape 5 étape 5: …n 2.5 Ordre d’une méthode numérique 0 00 Dé…nition 14 On dit que la méthode est d’ordre p si g ( ) = g ( ) = ::: = g (p 1) ( ) = 0 et g (p) ( ) 6= 0 ou est une racine de l’équation f (x) = 0, c’est-à-dire est une racine multiplicité p. 23 Dé…nition 15 On dit qu’une suite (xn ) construite par une méthode numérique converge vers avec un ordrep 1 si jxn+1 j 9C > 0 : p C; 8n n0 jxn j où n0 0 est un entier. Dans ce cas, on dit que la méthode est d’ordre p. Remarquer que si p est égal à 1, il est nécessaire que C < 1 dans (??)pour que (xn ) converge vers. On appelle alors la constante C facteur de convergence de la méthode. Théoréme 13 Si la racine 2 I et g 2 C p (I), p 1, et si g (i) ( ) = 0 pour i = 1; p 1 et g (p) ( ) 6= 0, alors la méthode de point …xe associée à la fonction d’itération g est d’ordre p et xn+1 g( )(p) lim p = (2.9) n!1 (xn ) (p)! Proof. Un développement de Taylor de g en x = donne: 00 0 g ( ) 2 g (p 1) ( ) p 1 '(p) ( n ) g(xn ) = g( ) + (xn )g ( ) + (xn ) + ::: + (xn ) + (xn 2! (p 1)! (p)! n entre et xn ainsi on a xn+1 g (p) ( n ) g( )(p) lim p = lim = n!1 (xn ) n!1 (p)! (p)! g( )(p) C= (p)! est le facteur de convergence asymptotique. Remarque 13 On peut dé…nir le taux de convergence asymptotique par R = log(jg 0 ( )j). x Exemple 29 soit f (x) = x e = 0; I=[0,1]; alors la racine 6= 0 la méthode du point …xe xn xn+1 = g(xn ) = e ; n 0 g 0 (x) = e x et g 0 ( ) 6= 0 donc la méthode est d’ordre 1. 24 Conclusion 1 Les méthodes numériques sont de la forme suivante: xn+1 = xx f (xn )=q(xn ) 1- si f (b) f (a) q(xn ) = b a on obtient la méthode de la cordre. 2- si f (xn ) f (xn 1 ) q(xn ) = xn xn 1 on obtien la méthode de la sécante et si a est …xé on a xn 1 = a si b est …xé on a xn 1 = b 3- si q(xn ) = f 0 (xn ) on obtient la méthode de Neuton -Raphson 4- si q(xn ) = f 0 (x0 ) on obtient la méthode de Newton -Raphson modi…ée 5- si f 0 (xn ) q(xn ) = p on obtient la méthode de Newton -Raphson la racine f (x) = 0 et de multi- plicité p 25 Bibliography A. Doneddu, Topologie. Fonctions réelles d’une variable réelle. tome 4. M. Sibony et J.-Cl.Mardon, Approximations et équations di¤érentielles, Troisiéme tirage, octobre 1988, ISBN 2 7056 2, HERMANN, France. Daldoul Mabrouk, une introduction à l’analyse numérique. M. Hazi, Itroduction aux espaces normés A. Doneddu, Espaces euclidiens et hermitiens. Géometries. J. Genet et G. Pupion, Analyse modérne. Derradji Salah, Analyse Numérique 1 A. Doneddu, Structures fondamentales, tome 1. Abdelha…d Mostefai, Cours de topologie. Al…o Quarteroni, Riccardo Sacco, Fausto Saleri, Méthodes numèriques.copyright Springer-Verlag Italia, Milano 2004 B. Demidovitch et L.Maron. Eléments de Calcul Numèriques.Traduction francaise. Editions Mir. 1979. Endre Suli and David Mayers. An Introduction to Numerical Analysis. Jeand-Pierre Demailly , Analyse Numériques des Equations Di¤érentielles. O¢ ce des publications universitaires :01-1994. ISBN 2.7061.0421.X. Jeand-Pierre Nougier,Méthodes de calcul numèrique.Systémes d’équations.Volume1. copyright HERMES Science Europe Ltd, Paris, 2001. 26  M. Crouzeix, A. L. Mignot. Analyse Numérique des Equations Di¤éren- tielles, Mason, Paris 1984. M. Sibony et J.-Cl.Mardon, Approximations et équations di¤érentielles, Troisiéme tirage, octobre 1988, ISBN 2 7056 2, HERMANN, France. Phillips and Taylor, Theory and Applications of Numerical Analysis, Academic Press, INC. Lodon, 1973. Richard L. Burden, J. Douglas Faires, Numerical Analysis, Fourth Edition.PWS-KENT Publishing Company.Boston. 1989. L. Halpern, MACS1, Cours d’Analyse numérique, 24 septembre 2010 Patrick Lascaux , Ramond Thédor, Analyse numérique matricielle ap- pliquée à l’art de l’ingénieur, Méthodes directes. M. Sibony et J.-Cl.Mardon, Systémes linéaires et non linéaires.HERMANN, France. M. Ranger, Chapitre II. Normes matricielles. Conditionnement. Guillaume Legendre. Méthodes numériques,Introduction à l’analyse numérique et au, calcul scienti que,Cours 2009/2010 Dauphine uni- versité Paris. Jean- Pierre Nougier, Méthode de calcul numérique volume1, systèmes d’équations, Anathony Ralston, Philip Rabinowitz, A …rst cours in numerical analysis P.G.Ciarlet, introduction à l’analyse numérique matricielle et à l’optimisation Pascal Viot, Méthode d’analyse numériquecours DEA ,12 novembre 2010. L. Halpern, MACS1, Cours d’Analyse numérique, 24 septembre 2010 M. Ranger, Chapitre II. Normes matricielles. Conditionnement. Franck Jedrzejewski, Introduction aux méthodes numériques Deuxième édition. Tahar abbes Miloud, méthodes numériques 27  Markasch Asch,Approximation numérique des équations di¤érentielle or- dinaires et partielles, préparation de l’agrégation de mathématique-2009. Abdesslam Boutayeb Mohamed Derouich, 2010/2011, Section SMA-SMI /S2 Franck Jedrzejewski, Introduction aux méthodes numériques. Deuxième édition Chapitre 2.pdf ,. Equations non linéaires. 28