---

Chapitre 3 
Résolution des équations non-linéaires

3.1  Fonctions à une variable, exposé des méthodes
3.1.1  Méthode de Dichotomie (Bisection)
3.1.2  Méthode de Regula Falsi (fausse position)
3.1.3  Méthode de la sécante
3.1.4  Méthode de Newton
3.1.5  Récapitulatif
3.2  Systèmes d'équations non linéaires
3.3  Zéros de polynômes

---

L'objectif de ce chapitre est de comparer différentes méthodes de résolution d'équations non linéaires du type :

f(x) = 0

(3.1)

dans le cas où une solution analytique ne peut pas être obtenue. Après l'exposé des méthodes applicables aux fonctions à une variable, nous aborderons le cas des systèmes d'équations non linéaires puis le cas particulier des racines d'un polynôme. La particularité de ces méthodes est qu'elles ne permettent de déterminer qu'une seule racine. Il faut alors rechercher les autres racines possibles par itération.

3.1  Fonctions à une variable, exposé des méthodes

3.1.1  Méthode de Dichotomie (Bisection)

Cette méthode repose sur le constat que si le produit f(a).f(b) < 0 est négatif, alors la fonction f s'annule au moins une fois sur l'intervalle [a,b]. Les différentes étapes de la méthode peuvent être résumées comme suit :

1. Choisir un intervalle [x₀ = a,x₁ = b] tel que f(a).f(b) < 0.
2. Calculer la valeur de la fonction en x₂ = (a+b)/2
3. On choisit un nouvel intervalle [x₀,x₂] ou [x₂,x₁] en respectant la condition du 1. On est alors assuré de toujours encadrer la racine.
4. Répéter les étapes 2 et 3 jusqu'à l'obtention de la précision désirée, c'est à dire jusqu'à ce que f(x₂) < e, e étant la précision désirée.

Après k itérations, la précision sur la racine s, vaut :

|xk-s| <

b-a 2^k^+1

(3.2)

Il est donc possible d'estimer à l'avance le nombre d'itérations nécessaires pour approcher s avec une précision donnée. Si on désire une tolérance t sur la racine, alors l'inégalité précédente donne le nombre d'itération minimal n qui doit vérifier

b-a 2^n^+1

< t

(3.3)

On en déduit le minorant de n

n >	log(b-a)-log2t log2

(3.4)

Si on choisit le logarithme de base 2 (bits de précision) l'inégalité précédente se simplifie

n > log2(b-a)-1-log2t

(3.5)

Il faut donc une itération supplémentaire par bit de précision. On remarquera que l'ordre de convergence vaut p = 1 et qu'il est indépendant de la fonction.

Figure 3.1: Méthode de dichotomie

Exemple 32 Les points successifs pour les premiers pas d'itération apparaissent sur la figure 3.1 pour la fonction

f(x) = e^-2x-cosx-3

avec a = -2 et b = 2.

3.1.2  Méthode de Regula Falsi (fausse position)

La première étape de la méthode est identique à celle de la précédente. Au lieu d'utiliser le point médian, on utilise le point d'intersection avec l'axe des abscisses de la droite (x⁽⁰⁾ = a,y⁽⁰⁾ = f(a)),(x⁽¹⁾ = b,y⁽¹⁾ = f(b)). Ce point est donné par l'équation suivante qui se vérifie très simplement :

x^(2) = x^(0)-y^(0)

x^(1)-x^(0) y^(1)-y^(0)

(3.6)

Les étapes 3 et 4 sont alors identiques à celles de la méthode de dichotomie

Figure 3.2: Méthode de Régula-Falsi

La figure 3.2 montre l'évolution des points au cours des itérations. On démontre que si f^¢(s) et f^¢¢(s) sont différents de 0, l'ordre de convergence de cette méthode vaut aussi 1.

3.1.3  Méthode de la sécante

Cette méthode est une variante de la méthode de Regula Falsi. La condition de l'étape 1 n'a plus à être satisfaite : la racine n'est pas nécessairement dans l'intervalle [x^(k),x^(k+1)]. Comme il ne subsiste aucune indication sur le choix initial de l'intervalle [x⁽⁰⁾,x⁽¹⁾], on effectue un choix arbitraire de cet intervalle et on surveille alors la décroissance de la norme de y^(k) = f(x^(k)).

x^(k+1) = x^(k)-y^(k-1)

x^(k)-x^(k^-1) y^(k)-y^(k^-1)

(k = 1,2,...)

(3.7)

L'ordre de convergence vaut p = [(1+Ö5)/2] = 1.618.

Figure 3.3: Méthode de la sécante

La figure 3.3 montre l'évolution des points en prenant comme intervalle initial, l'intervalle [-1,1] qui ne contient pas la racine. On pourra vérifier que la méthode diverge si on choisit par exemple l'intervalle [1,2].

3.1.4  Méthode de Newton

Dans ce cas, on suppose que la fonction est continûment dérivable et que sa dérivée peut être calculée facilement. La méthode consiste alors à approcher la fonction au point de coordonnées (x^(k),y^(k)) par sa tangente :

y = f(x^(k))+(x-x^(k))f^¢(x^(k))

(3.8)

On obtient alors x^(k+1), point d'intersection avec l'axe des abscisses :

x^(k+1) = x^(k)-

f(x^(k)) f^¢(x^(k))

(k = 0,1,2,...)

(3.9)

Figure 3.4: Méthode de Newton

La figure 3.4 montre l'évolution des points au cours des itérations si on prend comme point de départ le point x₀ = -2.

Remarque 33 Bien que plus rapide, la méthode de Newton échoue dans plusieurs cas. Quelques exemples sont rassemblés sur la figure ci-dessous

Figure 3.5: Cas où la méthode de Newton échoue

3.1.5  Récapitulatif

méthode	Rapidité	nombre de points	f(a)f(b) < 0	f Î C^2
dichotomie	non	2	oui	non
Newton	oui	1	non	oui
Sécante	moyen	2	non	non

3.2  Systèmes d'équations non linéaires

La méthode de newton peut être généralisée à la résolution des systèmes d'équations non-linéaires de la forme : 

fi(u) = fi(x1,x2,...,xn) = 0

(i = 1,2,...,n)

(3.10)

A titre d'exemple, considérons le système d'équations à deux inconnues suivant

ì í î

f(x,y) = 0  g(x,y) = 0

(3.11)

On définit le Jacobien du système par la matrice aux dérivées partielles :

F(x,y) = 

é
ê
ê
ê
ê
ê
ê
ê
ê
ë

¶f ¶x	¶f ¶y
¶g ¶x	¶g ¶y

ù
ú
ú
ú
ú
ú
ú
ú
ú
û

= 

é
ê
ë

fx	fy
gx	gy

ù
ú
û

(3.12)

En posant u = [x,y]^T, la suite des points u^(k) est obtenue par généralisation de l'équation de Newton pour une fonction à une variable. Elle prend la forme :

u^(k+1) = u^(k)-F^-^1(u^(k))F(u^(k))     (k = 0,1,2,...)

(3.13)

avec F^T = [f,g].

La forme explicite de l'équation 3.13 dans ce cas simple est

x^(k+1)

= 

x^(k)+

g.fy-f.gy fxgy-fygx

ê ê ê

(x^(k),y^(k))

(3.14)

y^(k+1)

= 

x^(k)+

f.gx-g.fx fxgy-fygx

ê ê ê

(x^(k),y^(k))

(3.15)

Dans le cas général de l'équation 3.10, l'équation 3.13 reste vraie en définissant :

u =

é ê ê ê ê ë

x1 x2 :  xn

ù ú ú ú ú û

F =

é ê ê ê ê ë

f1 f2 :  fn

ù ú ú ú ú û

et 

F = 

é
ê
ê
ê
ê
ê
ê
ê
ê
ê
ê
ê
ê
ê
ê
ê
ê
ë

¶f1 ¶x1	¶f1 ¶x2	...	¶f1 ¶xn
¶f2 ¶x1	:	...	¶f2 ¶xn
:	:	...	:
¶fn ¶x1	¶fn ¶x2	...	¶fn ¶xn

ù
ú
ú
ú
ú
ú
ú
ú
ú
ú
ú
ú
ú
ú
ú
ú
ú
û

3.3  Zéros de polynômes

La méthode de Newton est aussi bien adaptée au problème de résolution d'équations de type polynomial. Nous nous restreindrons au cas de polynômes à coefficients réels mais la méthode est encore valable dans le cas complexe.

Comme nous l'avons vu, la méthode de newton nécessite, à chaque itération, le calcul de la fonction et de la dérivée au point x^(k). Le calcul peut être réalisé de la manière suivante avec un coût en temps de calcul réduit. Considérons pour cela le polynôme de degré n dont on veut la valeur de la dérivée au point p = x^(k). Le polynôme de départ étant donné par

Pn(x) = a0x^n+a1x^n^-^1+a2x^n^-^2+....+an-1x+an

(3.16)

La division euclidienne de P(x) par (x-p) donne comme quotient le polynôme P_n-1(x) de degré (n-1) et le reste constant R₀

Pn(x) = (x-p)Pn-1(x)+R0

(3.17)

avec

Pn-1(x) = b0x^n^-1+b1x^n^-2+....+bn-2x+bn-1

(3.18)

On vérifie que le calcul des b_k et de R₀ peut se faire simplement par l'algorithme suivant

b0	=	a0	(3.19)
bk	=	ak+p.bk-1     (k = 0,1,2,...)	(3.20)
R0	=	bn	(3.21)

D'autre part la dérivation de P_n(x) donne

Pn(x) = Pn-1(x)+(x-p)Pn-1^¢(x)

(3.22)

On en déduit donc que

Pn^¢(p) = Pn-1(p)

(3.23)

Pour avoir la valeur de la dérivée de P_n(x) au point p, il suffit donc de calculer la valeur de P_n-1(x) au point p. Pour cela il suffit de considérer la division euclidienne de P_n-1(x) par (x-p) qui donne le quotient P_n-2(x) et le reste R₁

Pn-1(x)	=	(x-p)Pn-2(x)+R1
Pn-2(x)	=	c0x^n^-2+c1x^n^-2+....+cn-3x+cn-2	(3.24)

D'après l'équation 3.24, on remarque que

Pn^¢(p) = Pn-1(p) = R1

(3.25)

Il suffit donc de calculer R₁ pour avoir la dérivée de P_n. Le calcul de R₁ se fait par le calcul des c_k en utilisant le même algorithme que pour les b_k

c0	=	b0	(3.26)
ck	=	bk+p.ck-1                    (k = 1,2,...n-1)	(3.27)
R1	=	cn-1 = Pn^¢(p)	(3.28)

                    Il suffira donc maintenant d'inclure cet algorithme de calcul de la dérivée dans l'algorithme de Newton.

---

Commentaires sur ce polycopié smam@iup.univ-evry.fr

---

---

Said Mammar

Lundi 22 Novembre 1999