19
PROGRAMMATION SCIENTIFIQUE EN C PRO-1027

PROGRAMMATION SCIENTIFIQUE EN C PRO-1027. Résolution de système déquations non- linéaires (racines déquations) u Méthode de Newton-Raphson u Convergence

Embed Size (px)

Citation preview

Page 1: PROGRAMMATION SCIENTIFIQUE EN C PRO-1027. Résolution de système déquations non- linéaires (racines déquations) u Méthode de Newton-Raphson u Convergence

PROGRAMMATION SCIENTIFIQUE EN C

PRO-1027

Page 2: PROGRAMMATION SCIENTIFIQUE EN C PRO-1027. Résolution de système déquations non- linéaires (racines déquations) u Méthode de Newton-Raphson u Convergence

Résolution de système d’équations non-linéaires (racines d’équations)

Méthode de Newton-Raphson Convergence de la méthode Méthode de la sécante Travail pratique 2 b)

Page 3: PROGRAMMATION SCIENTIFIQUE EN C PRO-1027. Résolution de système déquations non- linéaires (racines déquations) u Méthode de Newton-Raphson u Convergence

Méthodes de Newton-Raphson

Cette méthode converge plus rapidement que la méthode de bissection

La méthode de Newton est basée sur l’utilisation de la portion linéaire de la série de Taylor

01

01 )()(

xxx

xdx

dfxfxf

Page 4: PROGRAMMATION SCIENTIFIQUE EN C PRO-1027. Résolution de système déquations non- linéaires (racines déquations) u Méthode de Newton-Raphson u Convergence

Méthodes de Newton-Raphson

Nous avons une racine quand f(x) = 0, alors

)('

)(

)('

/

)(

)()()(0

0

001

0

001

0101

xf

xfxx

dx

dfxf

dxdf

xfxx

xxdx

dfxfxf

Page 5: PROGRAMMATION SCIENTIFIQUE EN C PRO-1027. Résolution de système déquations non- linéaires (racines déquations) u Méthode de Newton-Raphson u Convergence

Méthodes de Newton-Raphson

Nous pouvons alors estimer une nouvelle valeur de la racine (x1) à partir d’une estimation initiale x0.

Nous pouvons alors raffiner l’estimation de la valeur de la racine (x1) de façon itérative

)('

)(1

i

iii xf

xfxx

Page 6: PROGRAMMATION SCIENTIFIQUE EN C PRO-1027. Résolution de système déquations non- linéaires (racines déquations) u Méthode de Newton-Raphson u Convergence

Méthodes de Newton-Raphson

Si f(x) est linéaire nous obtenons la solution au premier essai

Si f(x) est non linéaire, la série de Taylor est seulement valide pour de petits x

Les termes non linéaires tronqués de la série de Taylor influence la précision de la solution

Page 7: PROGRAMMATION SCIENTIFIQUE EN C PRO-1027. Résolution de système déquations non- linéaires (racines déquations) u Méthode de Newton-Raphson u Convergence

Méthodes de Newton-Raphson

À partir d’une estimation initiale d’une racine x0 nous calculons une nouvelle estimation x1 et ce itérativement jusqu’à l’obtention de la solution

La nouvelle estimation xi+1 est toujours estimée à partir de la dernière estimation xi.

Page 8: PROGRAMMATION SCIENTIFIQUE EN C PRO-1027. Résolution de système déquations non- linéaires (racines déquations) u Méthode de Newton-Raphson u Convergence

Méthodes de Newton-Raphson

ii

i

ii

ii xx

xf

xx

xfxf

11

)()(0)('

Page 9: PROGRAMMATION SCIENTIFIQUE EN C PRO-1027. Résolution de système déquations non- linéaires (racines déquations) u Méthode de Newton-Raphson u Convergence

Méthode de Newton-Raphson

Algorithme de NewtonNEWTON_RAPHSON(float x0, int nbiterMAX, float delta, float eps)

v = f(x0)

nbiter = 0

imprimer nbiter,x0,v

deltax1x0 = MAXFLOAT

TANT QUE nbiter<nbiterMAX ET deltax1x0 > delta ET |v| > eps FAIRE

x1 = x0-v/f’(x0)

v = f(x1)

imprimer nbiter, x1,v

deltax1x0 = x1- x0

x0 = x1

nbiter = nbiter + 1

FIN TANT QUE

Page 10: PROGRAMMATION SCIENTIFIQUE EN C PRO-1027. Résolution de système déquations non- linéaires (racines déquations) u Méthode de Newton-Raphson u Convergence

Convergence de la méthode

Dans certains cas l’algorithme de Newton ne converge pas

f ’(xi) -> 0

Page 11: PROGRAMMATION SCIENTIFIQUE EN C PRO-1027. Résolution de système déquations non- linéaires (racines déquations) u Méthode de Newton-Raphson u Convergence

Convergence de la méthode

Dans certains cas l’algorithme de Newton ne converge pas

f (xi) / f’(xi) = -f (xi+1) / f’(xi+1)

Page 12: PROGRAMMATION SCIENTIFIQUE EN C PRO-1027. Résolution de système déquations non- linéaires (racines déquations) u Méthode de Newton-Raphson u Convergence

Convergence de la méthode

Dans certains cas l’algorithme de Newton ne converge pas

f (xi) / f’(xi) = -f (xi+1) / f’(xi+1)

Page 13: PROGRAMMATION SCIENTIFIQUE EN C PRO-1027. Résolution de système déquations non- linéaires (racines déquations) u Méthode de Newton-Raphson u Convergence

Convergence de la méthode

Dans certains cas l’algorithme de Newton ne converge pas (ou converge lentement)

f’(xi) >>> f(xi)

Page 14: PROGRAMMATION SCIENTIFIQUE EN C PRO-1027. Résolution de système déquations non- linéaires (racines déquations) u Méthode de Newton-Raphson u Convergence

Méthode de la sécante

La seule différence avec la méthode de Newton-Raphson réside dans le calcul numérique de la dérivée f’(x)

Une nouvelle estimation de la racine xi+1 est déduite à partir des valeurs de la fonction f(xi) et f(xi-1) et des estimations précédentes des racines xi et xi-1.

Page 15: PROGRAMMATION SCIENTIFIQUE EN C PRO-1027. Résolution de système déquations non- linéaires (racines déquations) u Méthode de Newton-Raphson u Convergence

Méthode de la sécante

La valeur de la pente f’(x) est alors donnée par

1

1)()()('

ii

iii xx

xfxfxf

)()(

)(1

11

ii

iiiii xfxf

xxxfxx

La nouvelle estimation de la racine est donnée par

Page 16: PROGRAMMATION SCIENTIFIQUE EN C PRO-1027. Résolution de système déquations non- linéaires (racines déquations) u Méthode de Newton-Raphson u Convergence

Méthode de la sécante

Page 17: PROGRAMMATION SCIENTIFIQUE EN C PRO-1027. Résolution de système déquations non- linéaires (racines déquations) u Méthode de Newton-Raphson u Convergence

Méthode de la sécante

Algorithme de la sécante

SECANTE(float x0, float x1, int nbiterMAX, float delta, float eps)

u = f(x0)

v = f(x1)

nbiter = 0

imprimer nbiter,x0,u

nbiter++

imprimer nbiter,x1,v

deltax1x0 = MAXFLOAT

TANT QUE nbiter<nbiterMAX ET deltax1x0 > delta ET |v| > eps FAIRE

SI |u| < |v| ALORS

Permuter x0 et x1 , u et v

FIN SI

Page 18: PROGRAMMATION SCIENTIFIQUE EN C PRO-1027. Résolution de système déquations non- linéaires (racines déquations) u Méthode de Newton-Raphson u Convergence

Méthode de la sécante

Algorithme de la sécanteTANT QUE nbiter<nbiterMAX ET deltax1x0 > delta ET |v| > eps FAIRE

SI |u| < |v| ALORS /* POUR ÉVITER LA DIVERGENCE */

Permuter x0 et x1 , u et v

FIN SI

s = (x1-x0)/(v-u) /* = 1/f ’(x1) */

x0 = x1

u = v

x1 = x0-v*s

v = f(x1)

imprimer nbiter, x1,v

deltax1x0 = x1- x0

nbiter = nbiter + 1

FIN TANT QUE

Page 19: PROGRAMMATION SCIENTIFIQUE EN C PRO-1027. Résolution de système déquations non- linéaires (racines déquations) u Méthode de Newton-Raphson u Convergence

Travail pratique 2 b

Utilisation des méthodes de Newton et de la sécante