1

ANA NUM L2 2iE hms

Chapitre 2 Chapitre 2 Chapitre 2 Chapitre 2 MMMMthodes thodes thodes thodes numriquenumriquenumriquenumriques s s s de rsolution de lquation de rsolution de lquation de rsolution de lquation de rsolution de lquation

I.I.I.I. Position du problmePosition du problmePosition du problmePosition du problme

Soit " # $ % $ une fonction relle ou ventuellement " # ) % ). On cherche une ou plusieurs solutions de lquation :

", 0 1 Une solution de lquation 1 est un rel tel que " 0 En gnral, il nya pas de formule unique pour rsoudre lquation 1 et les mthodes de rsolution varient selon la structure de ". Par exemple :

1 si " est linaire, on peut trouver une solution de lquation 1 en appliquant des rgles de base dalgbre ou de trigonomtrie

2 si " est polynomiale a. Polynme du second degr

Lquation 1 devient : ", a x + b x + c 0 avec a 0. Les racines exactes de sont donnes par la formule :;:?@AB@ b-4ac > 0. b. Polynme de degr n 3 Lquation 1 scrit ", G + H, + I, + J,K + L 0 . Il ny a pas toujours de formules connues pour trouver une solution exacte de 1. QuestionQuestionQuestionQuestion : comment rsoudre lquation1 lorsquil nexiste pas de formule pour

Dterminer une solution exacte du problme ?

1 On peut utiliser une mthode graphiquemthode graphiquemthode graphiquemthode graphique Cependant, la rsolution graphique peut tre parfois longue et fastidieuse car elle ncessite lanalyse complte de la fonction. 2 on peut utiliser une mthode analytique fonde sur des approximationsmthode analytique fonde sur des approximationsmthode analytique fonde sur des approximationsmthode analytique fonde sur des approximations

successives en construisant une suite de solutions approches qui converge vers une solution exacte de 1. Ce type de mthodes appeles mthodes itratives sont trs faciles implmenter sur un ordinateur

2

ANA NUM L2 2iE hms

II.II.II.II. MMMMthodes itratives de type point fixethodes itratives de type point fixethodes itratives de type point fixethodes itratives de type point fixe

1.1.1.1. Principes de basePrincipes de basePrincipes de basePrincipes de base Etape 0Etape 0Etape 0Etape 0

Hypothse 1Hypothse 1Hypothse 1Hypothse 1 : : : : on suppose que " est continue sur un intervalle I de $. Etape 1Etape 1Etape 1Etape 1 On dtermine un intervalle [a, b] V I dans lequel lquation 1 admet une solution. Un tel intervalle peut tre trouver laide dune reprsentation graphique ou en utilisant le thorme des valeurs intermdiaires TVI. Thorme des valeurs intermdiaires rappelThorme des valeurs intermdiaires rappelThorme des valeurs intermdiaires rappelThorme des valeurs intermdiaires rappel

Soit " une fonction continue sur un intervalle I de $. Soient a et b deux points de I tels que "J. "I Y 0. Alors, il existe au moins un point [ \ [a, b] tel que " sannule en y.

Hypothse 2Hypothse 2Hypothse 2Hypothse 2 : On suppose que lintervalle [a, b] trouv contient une seule racine

de " note . Etape Etape Etape Etape 2222 On transforme ", 0 en une quation de type gx x o g est une fonction sur [a, b]. Lquation 2 est une quation de type point fixe. Il y a plusieurs mthodes pour dterminer g en fonction de " exemples : gx x - ",; gx x - _`a , b 0 ;

Hypothse Hypothse Hypothse Hypothse 3333 : On suppose que g [a, b] [a, b]. Etape Etape Etape Etape 3333 On choisit un point initial ,d \ [a, b] est une approximation grossire de la solution . On construit alors une suite :

,e f,d,B f,e g ,hie f,h j 0, 1, , j 2

3

ANA NUM L2 2iE hms

Une telle suite est galement appele un processus itratif. Daprs lhypothse 3, ,hn est une suite dlments de [a, b]. Puisque g est continue voir tape 2, alors s limhkil ,hie limhkilg,h gm , on dit cd "m 0. Daprs lhypothse 1, s . On dit quune solution de lquation 1 est un point fixe de g car elle vrifie g . QuestionsQuestionsQuestionsQuestions : Quelles sont les conditions de convergence de la suite ,hn ?

Comment estimer la propagation de lerreur commise chaque itration ?

2.2.2.2. Conditions de convergence dConditions de convergence dConditions de convergence dConditions de convergence dun processus un processus un processus un processus itratifitratifitratifitratif Dfinition 1Dfinition 1Dfinition 1Dfinition 1 Un processus itratif dfini par n ,d Gojj ,hie g,h, j 0,1, pest dit convergent pour un ,d 1donn si et seulement si la suite ,d, ,e, , ,h est convergente. Une condition ncessaire et suffisante de convergence dun processus itratif est donne par le thorme suivant :

Thorme 1 Thorme du point fixeThorme 1 Thorme du point fixeThorme 1 Thorme du point fixeThorme 1 Thorme du point fixe Soit g une fonction dfinie sur un intervalle [a, b]. On suppose que : a On suppose que g est continment drivable et que g[a, b] [a, b] b g est contractantecontractantecontractantecontractante sur [a, b] Alors, r ,d \ [J, I], la suite rcurrente dfinie par ,hie g,h converge vers lunique solution de lquation x gx. \ [J, I]. Dfinition 2Dfinition 2Dfinition 2Dfinition 2 Soit g : [a, b] k [a, b]. g est contractante si et seulement il existe une constante positive K telle que : 0000 t K Y 1K Y 1K Y 1K Y 1 et

|gx gy| t K|x - y|, r ,, [ \ [J, I] ou de faon quivalente :

max`\[@,;] |gx,| t y Y 1 On peut noncer une rgle de choix de la fonction g dans un algorithme itratif.

4

ANA NUM L2 2iE hms

Rgle de choix de gRgle de choix de gRgle de choix de gRgle de choix de g On remplace lquation 1 par gx x. On estime gx sur un intervalle [a, b] contenant une seule solution de 1. Soit M max`\[@,;]|g,| 1. Si M > 1, on limine g. 2. Si M > 1, la mthode converge et la fonction g peut tre retenue RcapitulatifRcapitulatifRcapitulatifRcapitulatif : Principe de convergence: Principe de convergence: Principe de convergence: Principe de convergence dun algorithme itratifdun algorithme itratifdun algorithme itratifdun algorithme itratif Soit " une fonction continue sur un intervalle [a, b] de $. On suppose que [a, b] est tel que lquation "x 0 1 admette une unique solution note . On remplace 1 par gx x avec g telle que : g [a, b] [a, b] g est continue et drivable sur [a, b] Max`\[@,;] |gx,| t y Y 1 Sous ces conditions, le processus itratif ,hn dfini par ,hie g,h converge vers lunique solution .de 1. En dautres termes, lalgorithme utilis permet de trouver une solution de 1. RemarqueRemarqueRemarqueRemarque :::: lintervalle [a, b] est souvent difficile dterminer. Sil est plus facile de dterminer g, on peut utiliser la proposition suivante : Proposition 1Proposition 1Proposition 1Proposition 1 ---- Convergence locale Convergence locale Convergence locale Convergence locale Soit vrifiant de g avec g continue. Si | g | Y 1 alors il existe un intervalle [a, b] contenant tel que : r ,d \ [J, I], on puisse construire une suite rcurrente ,hn dfinie par ,hie g,h qui converge . 4444----Exemple dapplication Exemple dapplication Exemple dapplication Exemple dapplication Exemple 1Exemple 1Exemple 1Exemple 1 Rsoudre lquation ", ,K + , { 1 0 E 1. Recherche de lintervalle [a, b] et de la valeur initiale ,0

5

ANA NUM L2 2iE hms

Pour , 0 , "0 0K + 0 { 1 {1 Pour , 1 , "1 1K + 1 { 1 1 Comme "0. "1 Y 0 , le thorme des valeurs intermdiaire assure lexistence dau moins une solution E dans [0, 1]. Cette solution est unique car " est continue et strictement croissante sur [0, 1] Des calculs supplmentaires montrent que la solution de E est plus proche de 1. On prend ,d 1 2. Choix de la fonction g ", 0 | ,B + 1 , { 1 0 ou de faon quivalente , eei` ge, Alors ge vrifie les proprits suivantes g est continue et drivable sur [0, 1] r , \ [0, 1], g1x \[0, 1] | gex | t B|`|ei`>> Y 1 , r , \ [0, 1] Posons ,hie ge,h , r j \ }, alors daprs le thorme du point fixe thorme 1, la suite ,hn converge vers lunique solution .de E. 3. Approximations successives de la solution exacte .de E.

,d 1 ,e 0.5, ,B 0.8, ,K 0.610, ,? 0.729 , , 0.653, , 0.701 La solution exacte de E 10-6 prs est 0.682 328. La convergence est obtenue partir de la 30me itration.

6

ANA NUM L2 2iE hms

RemarquesRemarquesRemarquesRemarques

a Choix de g Lalgorithme aurait-il converg si la fonction g choisit tait g2 x 1-x3 ? Non, car g2 x ne vrifie pas toutes les conditions du thorme du point fixe. En effet, g2 x nest pas contractante sur [KK , 1]: | g2 x | 3 x > 1, r , KK \ [KK , 1]

b Choix de ,d Pour ,d 0.5, la convergence est plus rapide Pour ,e 2, la convergence est plus lente : il faut beaucoup plus ditrations pour

atteindre . Pourquoi ?

III III III III Aspects numriques des mthodes dapproximations successivesAspects numriques des mthodes dapproximations successivesAspects numriques des mthodes dapproximations successivesAspects numriques des mthodes dapproximations successives Les questions analyses dans les sections prcdentes ont essentiellement dordre mathmatique. Du point de vue du calcul numrique, lanalyse de lexemple 1 soulve les questions suivantes. Le : a Un ordinateur effectue un nombre fini ditrations. Comment calculer le nombre

ditrations maximales effectuer. Ou plus prcisment, pour une prcision > 0 est assez petit, comment arrter les itrations ds que la solution recherche est atteinte prs. ?

b Comment se propage lerreur h ,h { au cours des itrations ?

7

ANA NUM L2 2iE hms

1.1.1.1. Nombre ditrations ncessaire lapproximation de Nombre ditrations ncessaire lapproximation de Nombre ditrations ncessaire lapproximation de Nombre ditrations ncessaire lapproximation de prprprprssss Thorme 2Thorme 2Thorme 2Thorme 2 Si on a : g [a, b] [a, b] Max`\[@,;] |fx,| t y Y 1 Alors, tant donn ,d, la suite des erreurs h ,h { vrifie :

|h | t yh| d | Pour une prcision > 0, le nombre ditrations n qui vrifient |h | t est tel que j avec

{ | | La preuve du thorme est laisse en exercice. RemarqueRemarqueRemarqueRemarque : Plus ,d est choisi proche de la solution , plus petit sera le nombre ditrations permettant destimer prs.

2.2.2.2. Vitesse de Convergence et ordre de convergence dune mthodeVitesse de Convergence et ordre de convergence dune mthodeVitesse de Convergence et ordre de convergence dune mthodeVitesse de Convergence et ordre de convergence dune mthode Un algorithme dont les termes derreurs augmentent chaque nouvelle itration ne peut pas converger. Pour quun algorithme converge, la vitesse de propagation des erreurs doit diminuer. La qualit dune mthode itrative doit donc tre caractrise par sa vitesse de convergence. Comment estimer cette vitesse ? DfinitionDfinitionDfinitionDfinition 3333 La mthode itrative dfinie par ,hie f,h est dite dordre p si

hieh hkil avec > 0 En utilisant la formule de Taylor et sous rverse dexistence des drives successives de g, une mthode itrative de type point fixe est dordre p si et seulement si

8

ANA NUM L2 2iE hms

g g gp-1 0 et gp 0 Alors si :

a hie gxh:lordre de convergence de la mthode est 1. On dit que la convergence est linaire

b hie eB g"hB lordre de convergence de la mthode est 2. On dit que la convergence est quadratique

Comportement des termes derreurs absolues |en| k |gx| est le coefficient de rduction asymptotique de lerreur

RemarqueRemarqueRemarqueRemarque : lordre de convergence dpend de la mthode utilise mais aussi de lordre de multiplicit de la solution de lquation 1. IV IV IV IV Mthode de NewtonMthode de NewtonMthode de NewtonMthode de Newton But de la mthodeBut de la mthodeBut de la mthodeBut de la mthode : trouver une solution de lquation ", 0 1 On note la solution de lquation 1.

1111 Principe de la mthode Principe de la mthode Principe de la mthode Principe de la mthode On suppose que " est continment drivable i.e. est de classe C1 On construit une suite ,hn telle que ,hie, 0 soit le point dintersection de la

tangente la courbe de " au point ,h, ",h avec laxe horizontal Ox.

9

ANA NUM L2 2iE hms

Puisque lquation de la tangente " au point ,h, ",h est : [ ",h + , { ,h",h

On a 0 ",h + ,hie { ,h",h

On calcule alors les termes de la suite en utilisant la formule

,hie ,h { ",h",h r j 0, 1, 2, . RemarquesRemarquesRemarquesRemarques :::: 1. Si "x,h 0 pour n donn, alors on choisit une nouvelle valeur initiale ,d.

2. Choix de ,d Etant donn un intervalle [ a, b ] contenant lunique solution de lquation 1, on choisira une valeur initiale ,d proche de lextrmit ou ""xx > 0. Par exemple si "J"xxJ > 0, on prendra ,d J sinon si "I"xxI > 0, on prendra ,d I 3. La mthode de Newton est une mthode itrative de type point fixe. Posons g, , { _`_x`, alors

g, , , { ",", , ", 0

Mthode de Newton

10

ANA NUM L2 2iE hms

3.3.3.3. Algorithme Algorithme Algorithme Algorithme de de de de la mthode de Newtonla mthode de Newtonla mthode de Newtonla mthode de Newton Newton ", "x, ,d, , % ce programme permet de calculer une solution de lquation %tant donn ,d, " une fonction continue admettant 1 drive continue " INPUT: ", " , une approximation initiale ,d, > 0 la prcision dsire, N le nombre maximum ditrations OUTPUT : valeur approche de ou afficher chec Pour n 1, 2, . N-1 Calculer ",h Si "x,h 0 alors afficher chec . Fin Sinon calculer ,hie ,h { _`_x` Si |,hie { ,h| t |,h| alors afficher ,hie. Fin Fin Afficher la mthode a chou aprs N itrations . Fin Newton

3.3.3.3. Convergence dune mthode de NewtonConvergence dune mthode de NewtonConvergence dune mthode de NewtonConvergence dune mthode de Newton La mthode de Newton est une mthode de type point fixe o la fonction g, , { _`_x`.

Lorsque la drive seconde "" de " existe. Si "x on a : gx, 1 { "x,B { ","","x,

","","x,

De plus, si "x 0, alors " 0 gx 0. La mthode de Newton est au moins dordre 2 cf. page 8. Proposition Proposition Proposition Proposition 2222 Si "x 0 est un zro simple de " alors la mthode Newton est convergente et La vitesse de convergence de la mthode est au moins dordre 2

11

ANA NUM L2 2iE hms

Thorme 3Thorme 3Thorme 3Thorme 3 2222 Si " est trois fois drivable et si "x 0 et "xx 0 alors pour ,d suffisamment proche de , la mthode de Newton est du second ordre. On a gxx __"_ 0 et les termes derreurs absolues vrifient :

hie "xx

2"x hB Si gxx 0, lordre de convergence de la mthode Newton est > 2. RemarqueRemarqueRemarqueRemarque : : : : Lorsque " est drivable, la mthode de Newton converge plus rapidement que les mthodes itratives de type point fixe dfinies par g, , { ", . Le dmontrer 4444. Exemples dapplication de la mthode de Newton. Exemples dapplication de la mthode de Newton. Exemples dapplication de la mthode de Newton. Exemples dapplication de la mthode de Newton ExeExeExeExemple mple mple mple 2 R2 R2 R2 Racine carre dun rel positif c et application c2acine carre dun rel positif c et application c2acine carre dun rel positif c et application c2acine carre dun rel positif c et application c2 On cherche , H avec H > 0. Ce qui revient rsoudre ", , { H 0. " est continument drivable et on a "x, 2,. On considre la suite telle que

,hie ,h { ",h",h

,h { ,h { H2,h ,hie e B ,h + H,h

Pour H 2, 1 devient ", , { 2 0. Soit la solution recherche. , 1, "1 1 { 2 {1 , 2, "2 2 { 2 2

La solution \ [1, 2]. tant plus proche de , 1, on prend ,d 1. a Puisque la drive de " ne sannule pas sur [1, 2], on a "x 0 . Daprs la proposition 2, la mthode de Newton converge quadratiquement. On a :

12

ANA NUM L2 2iE hms

j ,h ,hie 0 1.000 000 1.500 000 1 1.500 000 1.466 667 2 1.466 667 1.414 216 3 1.414 216 1.414 214 4 1.414 214 1.414 214 ,? 1.414 214 est la solution exacte 10-6 prs. Exemple Exemple Exemple Exemple 3 Equation transcendante3 Equation transcendante3 Equation transcendante3 Equation transcendante Trouver une solution positive de 2 sin x x On doit rsoudre lquation : ", , { 2 sin, 0. On a : ", 1 { 2 cos,. Soit la solution recherche.

, 2, "2 2 { sin2 0.181 405 , 1.5, "1.5 1.5 { sin1.5 { 0.494 990 , 1, "1 1 { sin1 { 0.682 942

", 0 admet une solution positive \ [1, 2]. De plus , "x 0 car"x ne sannule pas sur [1, 2]. La mthode converge. Les calculs ci-dessus montrent que est beaucoup plus proche de 2. On prend ,d 2 . On construit la suite ,hn dfinie par la relation de rcurrence

,hie ,h { ,h { 2 sin,h 1 { 2 cos,h 2 mj,h { ,hcos,h1 { 2 cos,h

hD Le calcul numrique donne les rsultats suivants :

13

ANA NUM L2 2iE hms

j ,h h D ,hie 0 2.00 000 3.48 318 1.83 229 1.90 100 1 1.90 100 3.12 468 1 .64 846 1.89 551 2 1.89 551 3.10 497 1.63 808 1.89 549 3 1.89 549 3.10 497 1.63 808 1.89 549

La solution exacte est ,? 1.89 549 10-5 prs. Exemple Exemple Exemple Exemple 4 Equation algbrique4 Equation algbrique4 Equation algbrique4 Equation algbrique Rsoudre lquation ", ,K + , { 1 0 avec la mthode Newton Comme dans lexemple 1, la solution \ [0, 1.]. Comme ", 3,B + 1, la mthode de Newton converge. On prend ,d 2 et n construit la suite ,hn dfinie par la relation de rcurrence ,hie ,h { ",h",h On obtient ,hie ,h { `i `:eK `>ie **

j ,h ,hie 0 1 0.750 000 1 0.750 000 0.686 047 2 0.686 047 0.682 340 3 0.682 340 0.682 328 La solution exacte est ,? 0.682 328 On retrouve le mme rsultat que dans lexemple 1 convergence pour N 30 avec beaucoup moins ditrations N 4. Cet exemple montre que la mthode de Newton converge plus rapidement que la procdure utilise dans lexemple 1.

5. 5. 5. 5. ProbProbProbProblme de conditionnement de la mthode de Newtolme de conditionnement de la mthode de Newtolme de conditionnement de la mthode de Newtolme de conditionnement de la mthode de Newtonnnn Lorsque |",| est trs petit au voisinage de la solution exacte de ", 0. Ce cas pourrait se prsenter, par exemple, lorsque est zro dordre multiple de " , le terme

14

ANA NUM L2 2iE hms

_`_` explose _`_` k + et la mthode de Newton diverge. Dans ce cas, on dit que le problme est mal conditionn. Comment rsoudre un problme de conditionnement de la mthode de Newton lorsque est zro dordre multiple de " ? Proposition 3Proposition 3Proposition 3Proposition 3 Lorsque est un zro dordre m de ", alors la mthode modifie de Newton dfinie par

,hie ,h { ",h",h r j 0, 1, 2, est convergente. Cette mthode est dordre 2 V Mthode de la scante V Mthode de la scante V Mthode de la scante V Mthode de la scante ButButButBut : Trouver une solution de ", 0 PrincipePrincipePrincipePrincipe : conserver lefficacit de la mthode de Newton tout en vitant des calculs de

drive Daprs ce qui prcde, la mthode de Newton est une mthode trs efficace. Cependant lestimation de ",h chaque itration peut tre coteux en calculs, do lide de remplacer ",h par :

",h ",h { ",h:e ,h { ,h:e

SSSSccccaaaannnntttteeee

15

ANA NUM L2 2iE hms

Mthode de la scante ou de la corde Daprs *, deux valeurs initiales ,d et ,e sont ncessaires pour contruire une suit ,hn dfinie par

,hie ,h { ",h ,h { ,h:e ",h { ",h:e r j 0, 1, 2, Exemple 7Exemple 7Exemple 7Exemple 7 Trouver une solution positive de lquation ", , { 2 sin, 0 On a , 2, "2 2 { sin2 0.181 405 , 1.5, "1.5 1.5 { sin1.5 { 0.494 990 , 1, "1 1 { sin1 { 0.682 942 ", 0 admet une solution positive dans [1, 2]. Les calculs ci-dessus montrent que cette solution est beaucoup plus proche de 2. On prend ,d 2 et ,e 1.9 On considre la suite dfinie par la relation de rcurrence

,hie ,h { ,h { 2 sin,h,h { ,h:e ,h { 2 sin,h { ,h:e { 2 sin,h:e

,h { ,h { 2 sin,h hD Le calcul numrique donne les rsultats suivants :

j ,h:e ,h h D ,hie { ,h 1 2.000 000 1.900 000 -0.000 740 -0. 174 005 -0.004 253 2 1.900 000 1. 895 747 -0.000 002 -0.000 002 -0.000 253 3 1. 895 747 1.895 495 0 0

Comme dans lexemple 3, la mthode de la scante converge au bout de 3 itrations.

16

ANA NUM L2 2iE hms

La solution exacte est ,? 1.89 550 10-5 prs. RemarquesRemarquesRemarquesRemarques :::: Choix de ,d Etant donn un intervalle [ a, b ] contenant lunique solution de lquation 1, on choisira une valeur initiale ,d proche de lextrmit ou ""xx Y 0. Par exemple si "J"xxJ Y 0, on prendra ,d J sinon si "I"xxI Y 0, on prendra ,d I ExerciExerciExerciExercicccceeee : crire la: crire la: crire la: crire lalgorithme lgorithme lgorithme lgorithme de lade lade lade la mthode de la mthode de la mthode de la mthode de la scantescantescantescante.... VIVIVIVI ConclusionConclusionConclusionConclusion En rsum, les mthodes itratives de calcul de solutions de lquation ", 0 "continue et ou drivable commence par une approximation de la valeur initiale ,d de la solution exacte et la gnration dune suite laide dun processus itratif formule de rcurrence. Les mthodes de type point fixe permettent de rsoudre lquation ", 0 quand celle-ci peut scrire sous la forme x gx de sorte que la solution exacte est un point fixe de la fonction g f . Ainsi la mthode de Newton est telle que f, , { _`_` . La mthode de Newton converge ds lors que la valeur initiale ,d a t bien choisie. Cette convergence est quadratique ds lors que st racine simple de " ie "x 0 et linaire lorsque est racine multiple de ". Pour dterminer lordre de convergence dune mthode on utilise la formule de Taylor de g en que La mthode de la scante est une variante de la mthode de Newton dans laquelle on remplace "x, par une diffrence de type _`:_`: . Dautres mthodes itratives comme la mthode de la bissection galement appele dichotomie ou la mthode de la fausse position convergent toujours mais leur vitesse de convergence est faible voir TD.