Ingénierienumériqueetsimulation

Mr.ESSADDOUKIMostafa http://www.developpement-informatique.com1

Résolutionnumériquedeséquations

I. Méthode de Bissection 1. Introduction

L’équation 0)( =xf , avec )(xf une fonction continue, a au moins une racine entre !x et ux si 0)()( <uxfxf !

Puisque la racine est entre !x et ux , on peut trouver le point milieu mx entre !x et ux . Cela nous donne deux nouveaux intervalles

Ü !x et mx , et

Ü mx et ux .

2. Algorithme Les étapes pour appliquer la méthode de bissection pour trouver la racine de l'équation 0)( =xf sont :

1. Choisir !x et ux telleque 0)()( <uxfxf ! ,ouend'autrestermes, )(xf changedesigneentre !x et

ux .2. Estimezlaracine mx del’équation 0)( =xf commepointmilieuentre !x et ux :

xx

m = xu! +

2

3. Vérifiezmaintenantcequisuita) si 0)()( <mxfxf ! ,alorslaracineestentre !x et mx ;donc !! xx = et mu xx = .b) si 0)()( >mxfxf ! ,alorslaracineestentre mx et ux ;donc mxx =! et uu xx = .c) si 0)()( =mxfxf ! ;laracineest mx .Arrêtezl'algorithmesicelaestvrai.

4. Trouvezlanouvelleestimationdelaracine

xx

m = xu! +

2

Trouvezl'erreurd'approximationrelative

∈amnewx

= x - x

x 100mnew

mold

Avec new

mx =racineestiméeàpartirdel'itérationactuelle old

mx =racineestiméeàpartirdel'itérationprécédente5. Comparerl'erreurd'approximationrelative ∈a aveclatoléranced'erreurrelativepré-spécifiée ∈s .

si ∈a , alors retournez à l’étape 3, sinon arrêtez l’algorithme. Il faut également vérifier si lenombred'itérationsest supérieuraunombremaximald'itérationsautorisé. Si c’est le cas, il fautterminerl'algorithmeetinformerl'utilisateur.

Ingénierienumériqueetsimulation

Mr.ESSADDOUKIMostafa http://www.developpement-informatique.com2

II. Regula Falsi (False Position Method) 1. Introduction

0)( =xf (1)

( )Uxf

Uxrx

( )Lxf

LxO

( )xf

x

Exact root

Figure 1 Regula Falsi

L'équation non linéaire ci-dessus peut être considérée comme la valeur de x telle que l'équation (1) est satisfaite. Dans la méthode de la bissection, nous identifions les valeurs appropriées de Lx (valeur limite inférieure) et

Ux (valeur limite supérieure), de sorte que

0)()( <UL xfxf . (2)

La prochaine racine prédite / améliorée rx peut être calculée en tant que point médian entre Lx et Ux comme :

2

ULr

xxx

+= (3)

La méthode de bissection peut ne pas être efficace car elle ne prend pas en compte que )( Lxf beaucoup plus près de la racine de la fonction )(xf par rapport à )( Uxf . En d'autres termes, la racine prédite suivante rxserait plus proche (dans l'exemple tel qu'illustré à la figure 1), que le point intermédiaire entre Lx et Ux . La méthode de Regula Falsi utilise cette observation mathématiquement en dessinant une sécante de la valeur de la fonction dans Lx à la valeur de la fonction à Ux , et estime la racine comme où elle traverse l'axe des abscisses.

Sur la base de deux triangles similaires, montrés à la figure 1, on obtient

Ur

U

Lr

L

xxxf

xxxf

−

−=

−

− )(0)(0 (4)

de l’équation (4), on obtient ( ) ( ) ( ) ( )LUrULr xfxxxfxx −=−

( ) ( ) ( ) ( ){ }ULrULLU xfxfxxfxxfx −=− L'équation ci-dessus peut être résolue pour obtenir la racine prédite suivante comme

( ) ( )( ) ( )UL

ULLUr xfxf

xfxxfxx

−

−= (5)

2. Algorithme Les étapes pour appliquer la méthode de regula falsi pour trouver la racine de l'équation 0)( =xf sont :

Ingénierienumériqueetsimulation

Mr.ESSADDOUKIMostafa http://www.developpement-informatique.com3

1. Choisir Lx et Ux telleque ( ) ( ) 0<UL xfxf ,ouend'autrestermes, )(xf changedesigneentre Lx et

Ux .2. Estimezlaracine rx del’équation 0)( =xf commepointmilieuentre !x et ux :

( ) ( )( ) ( )UL

ULLUr xfxf

xfxxfxx

−

−=

3. Vérifiezmaintenantcequisuitd) si ( ) ( ) 0<rL xfxf ,alorslaracineestentre !x et mx ;donc LL xx = et rU xx = .e) If ( ) ( ) 0>rL xfxf ,alorslaracineestentre mx et ux ;donc rL xx = et UU xx = .f) If ( ) ( ) 0=rL xfxf ;laracineest rx .Arrêtezl'algorithmesicelaestvrai.

4. Trouvezlanouvelleestimationdelaracine

( ) ( )( ) ( )UL

ULLUr xfxf

xfxxfxx

−

−=

Trouvezl'erreurd'approximationrelative

100×−

=∈ newr

oldr

newr

a xxx

Avec new

rx =racineestiméeàpartirdel'itérationactuelle old

rx =racineestiméeàpartirdel'itérationprécédente5. Comparerl'erreurd'approximationrelative ∈a aveclatoléranced'erreurrelativepré-spécifiée ∈s .

si ∈a , alors retournez à l’étape 3, sinon arrêtez l’algorithme. Il faut également vérifier si lenombred'itérationsest supérieuraunombremaximald'itérationsautorisé. Si c’est le cas, il fautterminerl'algorithmeetinformerl'utilisateur.

Notez que les algorithmes de Regula Falsi et de bissection sont assez similaires. La seule différence est la formule utilisée pour calculer la nouvelle estimation de la racine comme indiqué aux étapes 2 et 4

Ingénierienumériqueetsimulation

Mr.ESSADDOUKIMostafa http://www.developpement-informatique.com4

III. Newton-Raphson Method 1. Introduction

La méthode de Newton-Raphson est basée sur le principe selon lequel, si la conjecture initiale de la racine 0)( =xf est à ix , alors si l'on trace la tangente à la courbe )( ixf , le point 1+ix où la tangente croise l'axe des

abscisses est une estimation améliorée de la racine

En utilisant la définition de la pente d'une fonction, à ixx =

f x

x x

i

i i

' ( ))

= tan

= f(xi

∅

−

− +

0

1

( )

1

0

+−

−

ii

i

xxxf = ,

Qui donne

xf xi

i+1 = x -

f(xi

i )' ( )

(1)

2. Algorithme Les étapes pour appliquer la méthode de Newton-Raphson pour trouver la racine de l'équation 0)( =xf sont :

1. Évaluez ( )xf ʹ symboliquement2. Utilisezuneestimationinitialedelaracine ix ,pourestimerlanouvellevaleurdelaracine 1+ix ,

comme

( )( )i

iii xf

xf = xxʹ

−+1

3. Trouvezl'erreurd'approximationrelative a∈

∈ +

+a

i

i

xx

= - x

x 100i1

1

4. Comparerl'erreurd'approximationrelative ∈a aveclatoléranced'erreurrelativepré-spécifiée∈s .si ∈a ,alorsretournezàl’étape2,sinonarrêtezl’algorithme.Ilfautégalementvérifiersilenombred'itérationsestsupérieuraunombremaximald'itérationsautorisé.Sic’estlecas,ilfautterminerl'algorithmeetinformerl'utilisateur.

f(x)

f(xi)

f(xi+1)

xi+2

xi+1

xix

θ

[xi,f(xi)]

Ingénierienumériqueetsimulation

Mr.ESSADDOUKIMostafa http://www.developpement-informatique.com5

IV. Sécante Method 1. Introduction

La méthode de Newton-Raphson pour résoudre une équation non linéaire xf xi

i+1 = x -

f(xi

i )' ( ) est donnée par la formule

itérative

xf xi

i+1 = x -

f(xi

i )' ( )

(1)

L'un des inconvénients de la méthode Newton-Raphson est que vous devez évaluer la dérivée de la fonction. Cependant, il peut encore être un processus laborieux, et même intraitable si la fonction est dérivée dans le cadre d'un schéma numérique. Pour surmonter ces inconvénients, la dérivée de la fonction x

f xii

+1 = x - f(x

ii )

' ( )est approximative comme

ʹ =−

−−

−f x

f x f xx xii i

i i( )

( ) ( )11

(2)

La substitution de l'équation (2) dans l'équation (1) donne :

x xf x x xf x f xi i

i i i

i i+

−

−

= −−

−1

1

1

( )( )( ) ( )

(3)

Cette méthode nécessite maintenant deux racine initiales, mais contrairement à la méthode de la bissection, les deux racines initiales n'ont pas besoin de vérifier le changement de signe. La méthode sécante est une méthode ouverte et peut ou non converger. Cependant, lorsque la méthode sécante converge, elle convertira généralement plus rapidement que la méthode de bissection. Cependant, comme la dérivée est approximée dans l'équation (2), elle converge généralement plus lentement que la méthode Newton-Raphson.

2. Algorithme Lesétapespourappliquerlaméthodedesécantepourtrouverlaracinedel'équation 0)( =xf sont:

1. Calculez l'estimation suivante de la racine à partir de deux racines initiales

x xf x x xf x f xi i

i i i

i i+

−

−

= −−

−1

1

1

( )( )( ) ( )

2. Trouvezl'erreurd'approximationrelative a∈ as

∈ +

+a

i

i

xx

= - x

x 100i1

1

3. Comparerl'erreurd'approximationrelative ∈a aveclatoléranced'erreurrelativepré-spécifiée∈s .si ∈a ,alorsretournezàl’étape1,sinonarrêtezl’algorithme.Ilfautégalementvérifiersilenombred'itérationsestsupérieuraunombremaximald'itérationsautorisé.Sic’estlecas,ilfautterminerl'algorithmeetinformerl'utilisateur.