ENS Ydé. Mr NJEUTCHA P.

Jeudi, 13 avril 2023.

CHAP 2 : GENERALITES SUR LES METHODES ITERATIVES ET

RESOLUTION NUMERIQUE DES EQUATIONS NON-
LINEAIRES

GRANDS TITRES A RETROUVER LE LONG DU CHAPITRE :

 METHODES ITERATIVES.
 Tps SUR MATLAB.
 INTERPOLATION LINEAIRE.

INTRODUCTION :
L’objet essentiel de ce chapitre est l’approximation d’une fonction réelle c’est-à-
dire la résolution approchée du problème suivant :
Etant donnée une équation non linéaire à une seule variable définie par f(x) = 0 (E).
La valeur de la variable x vérifiant cette égalité est appelée solution ou racine de
l’équation notée xo ; Dans nombre de cas, nous devons recourir aux méthodes
numériques car la solution ne peut pas être déterminée analytiquement. Ainsi,
résoudre une telle équation revient à définir une succession d’éléments (solutions
intermédiaires) qui converge vers la solution désirée telle que Lim Xk = x*. On ne
X->inf.
parle pas de solution exacte car souvent elle n’existe pas. Cependant, X->inf on cherche
une solution qui soient approchée de la solution exacte avec une certaine précision.
Il existe plusieurs techniques permettant de résoudre (E). Ces méthodes se
différentient par leurs principes et leurs vitesses de convergence. Nous introduirons
donc les méthodes qui suivent :
 Méthodes dichotomique(dissection)
 Méthodes du point-fixe
 Méthode newtonienne (des tangentes)
 Méthode de la sécante
Nous les présenterons dans l’ordre de complexité croissante des algorithmes.
Dans le cas de la dichotomie, la seule information utilisée est le signe de la fonction
f aux extrémités de son intervalle, tandis que pour les autres algorithmes, on prend
aussi en compte les valeurs de la fonction et ou de ses dérivées.

INFO L1 1 ANALYSE NUMERIQUE

 ENS Ydé. Mr NJEUTCHA P.

I. METHODES ITERATIVES
Définitions :
Méthode itérative de résolution de f(x)=0 : f définie sur [a ; b] € |R, c’est une
méthode consistant à construire une suite (Xk)k€|N sensée converger vers x solutions
(Xk étant l’itérée calculée à partir de X0, X1, X2,…,Xn).
Méthode itérative convergente : méthode dont, si pout tout choix X0 € |R, on a
Lim Xk = x
X->inf.

I.1 méthode de dichotomie :

Cette méthode repose sur les hypothèses suivantes :
 Il existe une solution sure [a ; b] ;
 La fonction f est monotone sur [a ; b] ;
Sous ces deux hypothèses, l’inégalité suivante est vérifiée : f(a)*f(b)<0.

I.1.1 Principe de la méthode de dichotomie :

La figure ci-contre illustre le principe de la dichotomie.
 On calcule c par l’expression :
Si f(c)=0, alors x = c, on arrête la recherche.
 Mettre à jour [a ; b] tel que :
-
-Si f(a)*f(c)<0, ; X0 € [a; c], b=c
alors
- Si f(b)*f(c)<0, alors X0 € [c ; b], a=c ;
 On recommence le calcul de c itérativement
Jusqu’à ce que |b-a|< ε, ε = précision.

I.1.2 Condition d’arrêt :

Le nombre d’itérations dépend de la précision ε voulue ainsi que

l’intervalle initial [a ; b]. N>= ln((b-a) / ε) /ln2.
 Avantages de la méthode :
- Elle converge toujours ;
- Pour ε donné, on connait le nombre d’itérations nécessaire qui est
ln((b-a) / ε) /ln2.
INFO L1 2 ANALYSE NUMERIQUE
 ENS Ydé. Mr NJEUTCHA P.

- Mise en œuvre simple (car ne dépend que du signe de f(x)).

 Inconvénients de la méthode :
- Convergence lente (seulement linéaire ou à l’ordre 1).
- On ne tient compte que du signe de f(x) donc on perd beaucoup
d’informations.
- S’il y a plusieurs racines, on en obtient qu’une et on ne sait pas
laquelle ;
- On doit trouver a et b telle que a différent de b.

Application : Rechercher la solution de E(x) = 0, E(x) = x3 – 4x -8,95,

dans [2,3] avec ε = 10-2 ;

I.2 méthode du point fixe :

Il faut réécrire l’équation f(x) = 0 sous la forme x = g(x), avec la
condition de convergence |g’(x)|<1.
I.2.1 Principe de la méthode du point-fixe :
* Le principe ici correspond à la recherche du point d’intersection
entre les deux fonctions : y = g(x) et y = x.
* On choisit initialement un point X0 qui sera la première estimée de
la solution.
* On calcule g(X0). Cette dernière valeur sera considérée comme
nde
étant la 2 estimée de la solution. À son tour, cette solution sera injectée dans la
fonction g(x) et ordre suit jusqu’à satisfaction d’un critère d’arrêt.
I.2.2 Critère d’arrêt :

| X1 - X0| < ε

I.2.3 Avantages et inconvénients :

 Avantage :
Mise en œuvre facile.
 Inconvénient :
- Convergence souvent difficile à réaliser en pratique ;
- La convergence est lente, de type linéaire en général.
INFO L1 3 ANALYSE NUMERIQUE
 ENS Ydé. Mr NJEUTCHA P.

Application : Rechercher la solution de E(x) = 0, E(x) = -x4/5 + x -2, avec

X0= 8 ; ε = 10-4

I.3 méthode de Newton (des tangentes) :

I.3.1 Principe de la méthode de newton :
On suppose que f est continue et dérivable sur I € IR
On choisit X0 et on définit une suite récurrente de façon qui suit : Xn+1 est
l’abscisse de l’intersection entre la droite (D) : y = 0 et (𐊅) : y = f’(Xn) (x – Xn) + f(Xn)
où (𐊅) correspond à la tangente en Xn de f. On obtient Xn+1 =Xn - f(Xn)/f’(Xn).
Sous certaines conditions, la suite a une limite Ф telle que f(Ф) = 0 et est un point
fixe de la fonction 𐌸(x) = x – f(x)/f’(x).
Ex : Partant de f(x) = x2 – a, on a Xn+1 = Xn – (Xn2 - a)/ 2Xn ;
Soit Xn+1 = 1/2(Xn+ a/Xn ) ;
Cette suite converge vers √a avec X0=1, on obtient √2 à 4 itérations, à 10-8 près.
I.3.2 Etude de la convergence
On suppose que f est continue et dérivable sur I € IR jusqu’à l’ordre 3.
𐌸(x) = x – f(x)/f’(x)
𐌸’(x) = f’’(x) f(x)/[f’(x)]2

𐌸’’(x) = f’’(x) /f’(x) + f’’(x) f(x)/ [f’(x)]2 – 2 f’’(x) f(x)/[f’(x)]3.

 Si f’(Ф) et f’’(Ф) diffèrent de 0, on a :
𐌸’(Ф) = 0 et 𐌸’’(Ф) ≠ 0. Dans ces conditions, la méthode est de 2nd ordre, on
parle de convergence quadratique dans la zone de convergence.
 Si f(Ф) ≠ 0 et f’(Ф) = 0, il y’a un point d’inflexion. La méthode est d’ordre > 2.
 Si f’(Ф) = 0, il y’a une racine multiple, la convergence est linéaire.
La présence d’une racine multiple ralentit la convergence.

CONDITION SUFFISANTE DE CONVERGENCE :

Si Ф est une racine et si f et f’ sont continues sur [inf(Ф, X0 ) ;sup(Ф, X0)], alors,
il y’a convergence monotone.

INFO L1 4 ANALYSE NUMERIQUE

 ENS Ydé. Mr NJEUTCHA P.

I.3.3 Avantages et inconvénients :

 Avantage :
Théorème : S’il y’a convergence, alors celle-ci est rapide (en générale,
quadratique, linéaire si Ф est multiple).
Elle nécessite un seul point de départ.
 Inconvénient :
- F doit être continue, dérivable et il faut calculer la dérivée.
- La convergence n’est pas assurée dans tous les cas.
Ex : f(x) = 3√x ; √x si x>0

f(x) = 0 si x=0
-√-x si x<0

I.3.4 Critère d’arrêt :

 On s’arrête si |Xn – Xn-1| < ε0 où est l’erreur absolue tolérée.
 On s’arrête aussi si |Xn – Xn-1| < εr|Xn| εr où est l’erreur relative tolérée.
Remarque : On n’est pas assurée d’avoir une racine avec cette précision.

I.3.5 Contrôle :
Il suffit de vérifier que f(x) = 0 ou change de signe dans [Xn–εa ; Xn+εa].
Dans la pratique, on se contente d’examiner les signes de f(Xn-1) et f(Xn),
éventuellement celui de f(Xn+ε0).
Deplus on limite apriori le nombre d’itérations et on s’arrête si f’(xn)=0 ou si f(xn) et
f’(xn) n’est / ne sont pas définie(s).

I.4 méthode des sécantes :

Cette méthode est une alternative à celle des tangentes, lorsque l’on ne connait
pas la dérivée de la fonction f.
A l’itération k de la méthode de newton, on approche f(xk) par (f(xk) – f(xk-1))/(xk-xk-1).
En effet, d’après la formule de Taylor-Lagrange, Өk € ]Xk-1;Xk[, vérifiant la relation :
f’(xk) = (f(xk) – f(xk-1))/( xk - xk-1 ) + ( xk - xk-1 )*f’’(Өk ) /2!.
Si la suite converge, alors ( xk - xk-1 )*f’’(Өk ) /2! → 0 quand k→∞, ce qui justifie
l’approximation précédente.

INFO L1 5 ANALYSE NUMERIQUE

 ENS Ydé. Mr NJEUTCHA P.

Cette méthode est une méthode à 2 pas : Le calcul de Xk+1, nécessite de

connaitre Xk-1 et Xk. Il faut donc 2 valeurs d’initialisation ( X-1,X0) pour définir par
la suite les valeurs de Xk.

I.4.1 Convergence de méthode :

Soit f une fonction de classe C2 sur un voisinage d’une racine simple Ө de f.
Soit X-1 et X0 donnés dans ce voisinage, telles que f(X-1) ≠ f(X0). La suite (Xk)k€ IN
définie par la méthode de la sécante Xk+1 = Xk – (Xk - Xk-1)f(Xk) / (f(Xk)-f(Xk-1)) Ɐ k€ IN,
est localement convergente d’ordre (1+√5)/2 ~ 1,648.

II. INTERPOLATION :
L’interpolation est un outil mathématique permettant de construire des
fonctions à partir de la donnée d’un nombre finie de valeurs.
1. Interpolation de Lagrange :
 Définition :
Soit n € IN* et (xi ; yi) 0<i<n € IR2 et xi≠xi+1 . Le polynome d’interpolation de
LAGRANGE associé au n+1 points noté Pn est donné par :

Théorème : Le polynôme d’interpolation de LAGRANGE associé au n+1 points

(xi ; yi) est l’unique polynôme de degré au +n vérifiant :
Pn(x) = yi Ɐ i =0, …, n (8)
REMARQUE : Il est possible d’obtenir l’existence et l’unicité du polynôme
d’interpolation de Lagrange sans passer par sa construction. Alors pour cela, on
définit Ф : IR[x] IRn+1, Ф(P) = (P(X0), …, P(Xn)). L’existence et l’unicité du
polynôme Pn est équivalente à la bijectivité de Ф.
Or celle-ci est une application linéaire de dimension n+1 et est donc bijective ssi
elle est injective et surjective. Pour vérifier l’injectivité de Ф il est nécessaire et
suffisant de vérifier que son noyau est réduit au vecteur nul (Ker Ф = {0E})

INFO L1 6 ANALYSE NUMERIQUE

ENS Ydé. Mr NJEUTCHA P.

Exemple : Ecrire la fonction de LAGRANGE (polynôme interpolant) associé aux

n+1 points, i € [l 0 ; n l], au point p € IR
But : Calculer le polynôme Pn(t) définie par (6)
Données : X : vecteur / tableau de IRn+1 (il a n+1 composantes).
X(i) = Xi-1, Ɐ i=1,…,n+1 , X(i) ≠ X(j), i ≠ j de meme que pour Y.
t : est un reel
résultat : Y=Pn(t).

INFO L1 7 ANALYSE NUMERIQUE