Résolution numérique de l'équation f ( x ) = 0

Résolution numérique de l'équation f ( x ) = 0


Ce document, destiné à des étudiants de L3, explique quelques méthodes permettant de trouver numériquement les zéros de fonctions d'une variable réelle.

I Introduction

II Méthode de dichotomie

III Méthode de point fixe

IV Méthode de Newton

V Méthode de Lagrange

VI Bibliographie

VII Exercices

Vous trouverez ici le fichier pdf doczero.pdf

I Introduction

I-1 Préambule

L'étude générale des fonctions à variables réelles nécessite de temps à autre la résolution d'équations de type f(x) = 0. Autrement dit, nous sommes amenés à trouver les zéros de fonctions non linéaires, c'est-à-dire les valeurs réelles alpha telles que
ou, ce qui est équivalent, à résoudre une équation de type

I-2 Exemple motivant: équation d'état d'un gaz

Résolution numérique de l'équation f ( x ) = 0I Introduction → I-2 Exemple motivant: équation d'état d'un gaz
On veut déterminer le volume V occupé par un gaz de température T et de pression p. L'équation d'état (c'est-à-dire l'équation qui lie p, V et T) est :
a et b sont deux coefficients dépendants de la nature du gaz, N le nombre de molécules contenues dans le volume V et k la constante de Boltzmann. Il faut donc résoudre une équation non linéaire d'inconnue V. Ceci revient à trouver les zéros de la fonction :

Dans le cas le plus général, il s'agit de résoudre une équation non linéaire dont on n'est pas capable de trouver une solution exacte. Dans ce cas, on dispose de quelques méthodes numériques exécutables sur des logiciels comme Matlab, Maple, Octave, Scilab pour approximer la solution exacte. Ces méthodes numériques sont toutes basées sur la construction d'une suite convergeant vers un réel alpha vérifiant .
Dans ce document, nous allons traiter quatre méthodes: la méthode de dichotomie, de point fixe, de Newton et de Lagrange. Pour le faire, nous avons besoin de quelques rappels d'analyse.

I-3 Rappels d'analyse


Une équation de type f(x) = 0 peut être écrite d'une manière équivalente sous la forme de g(x) = x. La fonction g est une fonction dépendante de f non unique comme le montre l'exemple suivant :
Exemple
Si la fonction g peut être
ou

Les instructions Matlab suivantes permettent de tracer les représentations graphiques de ces fonctions, y compris celle de la droite y = x:
Code Matlab
x = 0:0.001:1;
f = inline('sin(2*x)-1 + x');
g1 = inline('1-sin(2*x)');
g2 = inline('1/2*(asin(1-x))');
h = inline('x');
plot(x, f(x), '--.b',  x, g1(x), '-.b', x, g2(x), '--b', x, h(x),'b');
legend('f', 'y=1-sin(2x)', 'y=1/2*(Arcsin(1-x))', 'y=x');
grid on;
ylabel('y(x)');
xlabel('x');

On voit bien que f admet un unique zéro et que les graphes des fonctions
se coupent en .

I-3-1 Point fixe

I-3-2 Multiplicité d'une racine, fonction contractante

I-3-3 Théorème de point fixe

I-3-4 Fonctions convexes

I-3-5 Vitesse de convergence d'une suite

I-3-1 Point fixe

Définition

Un réel est dit point fixe d'une fonction si

I-3-2 Multiplicité d'une racine, fonction contractante

Résolution numérique de l'équation f ( x ) = 0I IntroductionI-3 Rappels d'analyse → I-3-2 Multiplicité d'une racine, fonction contractante

Définition

Soit p un entier et f une fonction p fois dérivable.
  1. On dit que alpha est un zéro de f de multiplicité p si
  2. Un zéro de multiplicité 1 (respectivement 2) est appelé un zéro simple (respectivement double ).

Définition

Soit . Une fonction est dite fonction contractante de rapport k si

Remarque

  1. Soit . Si
    alors g est contractante sur .
  2. Une fonction contractante est continue.

I-3-3 Théorème de point fixe


Théorème

Soit une fonction contractante de rapport k. Alors g admet un unique point fixe . De plus, pour tout choix de la suite définie par converge vers l quand .

Démonstration
Etape 1: Existence de l et convergence de la suite Remarquons d'abord que ce qui implique que la suite (xn) est bien définie. Soit x0 dans et . Nous allons montrer:
  1. est de Cauchy (donc convergente, car est complet)
  2. quand où l est un point fixe de g.

Par hypothèse, on sait que
Par récurrence sur n, on obtient:
Soit et on a donc:
La suite (xn) est donc de Cauchy dans qui est complet et par conséquent (xn) converge vers une limite l quand . Comme la fonction g est contractante, elle est continue, et donc quand . En passant à la limite dans l'égalité: on en déduit que l = g(l), c'est à dire que l est un point fixe de g.
Etape 2: Unicité
Soient l1 et l2 deux points fixes de g, donc alors ; comme k<1, ceci est impossible sauf si l1 = l2.

Remarque

Si g est une application vérifiant
alors la suite définie par converge vers l'unique point fixe l de g sur pour tout choix de . De plus en faisant tendre p vers l'infini dans et en gardant n, on obtient:

I-3-4 Fonctions convexes

Définition [fonction convexe]

Soit I un intervalle de . Une fonction est dite convexe sur I si
Si l'inégalité est stricte, f est dite strictement convexe .

Proposition

Si convexe, alors la fonction
est croissante sur .

Proposition

Si est deux fois dérivable, alors:

Définition

On dit que est concave sur I si (-f) est convexe sur I.

I-3-5 Vitesse de convergence d'une suite

Résolution numérique de l'équation f ( x ) = 0I IntroductionI-3 Rappels d'analyse → I-3-5 Vitesse de convergence d'une suite

Définition

Soit une suite convergente vers alpha. On appelle ordre de convergence de la suite (xn) le réel fini ou infini r>0 défini par:
  1. Si r = 2, on dit que la convergence de (xn) est quadratique .
  2. Si r = 3, on dit que la convergence de (xn) est cubique .
  3. Supposons que l'ordre de convergence de la suite (xn) est r = 1 et que:
    1. Si 0 < k < 1 on dit que la suite (xn) est à convergence linéaire .
    2. Si k = 0 on dit que la suite (xn) est à convergence super-linéaire .
    3. Si k = 1 on dit que la suite (xn) est à convergence logarithmique .

Exemple
Soit . Soit la suite récurrente définie par
avec
La suite (xn) converge vers et son ordre de convergence est égal à 2. En effet:
et

I-4 Critère d'arrêt pour la résolution numérique de f(x) = 0

Résolution numérique de l'équation f ( x ) = 0I Introduction → I-4 Critère d'arrêt pour la résolution numérique de f(x) = 0

Une fois construite la suite (xn) convergeant vers l vérifiant g(l) = l, quand peut-on arrêter les itérations de l'algorithme numérique si l'on désire déterminer une valeur approchée de l avec une tolérance varepsilon fixée à l'avance. Un bon critère d'arrêt est le contrôle de l'incrément :
  1. On constate la convergence : les résultats numériques se stabilisent.
  2. On s'arrête à l'itération n0 si on peut montrer théoriquement que:

Exemple
Soit f(x) = x3-4x+1. On vérifie que f admet 3 racines réelles et en posant
Un simple calcul donne les valeurs suivantes:

x0 
 -2  0  2

x1 
 -2.125  0.25  1.875

x2 
 -2.114975450  0.254098301  1.860978520

x3 
 -2.114907545  0.254101688  1.860805877

x4 
 -2.114907541  0.254101688   1.860805853

x5 
 -2.114907541  0.254101688   1.860805853

x6 
       

x7 
       

x8 
       

On constate que les valeurs numériques se stabilisent et on a alors les valeurs approchées de l1, l2 et l3 à environ près.

II Méthode de dichotomie

II-1 Principe

Considérons une fonction f continue sur un intervalle . On suppose que f admet une et une seule racine alpha dans et que f(a) f(b) < 0. On note
le milieu de l'intervalle.
  1. Si f(c) = 0, c'est la racine de f et le problème est résolu.
  2. Si nous regardons le signe de f(a) f(c).
    1. Si f(a) f(c)<0, alors
    2. Si f(c) f(b)<0, alors

On recommence le processus en prenant l'intervalle au lieu de dans le premier cas, et l'intervalle au lieu de dans le second cas. De cette manière, on construit par récurrence sur n trois suites (an), (bn) et (cn) telles que et telles que pour tout ,
  1. Si f(cn) f(bn)<0 alors et .
  2. Si f(cn) f(an)<0 alors et .
L'algorithme ci-dessus s'appelle l'algorithme de dichotomie .

II-2 Etude de la convergence

Théorème

Soit f une fonction continue sur vérifiant f(a) f(b)<0 et soit l'unique solution de l'équation f(x) = 0. Si l'algorithme de dichotomie arrive jusqu'à l'étape n alors on a l'estimation:
Par conséquent, la suite (cn) converge vers alpha. C'est aussi vrai si .

Démonstration
Il suffit de remarquer qu'à chaque itération, on divise l'intervalle par deux.

II-3 Test d'arrêt


Pour que la valeur de cn de la suite à la n-ième itération soit une valeur approchée de alpha à près, il suffit que n vérifie:
On a alors:
ce qui permet de calculer à l'avance le nombre maximal d'itérations assurant la précision varepsilon.