Abid abdellah.
-
Charif al idrissi.- Système non linéaire f ( x ) = 0 Informatique
1 Introduction :
Nous nous intéresserons dans ce cours à l’approximation des zéros d’une fonction réelle non linéaire d’une variable
réelle.
Toutes les méthodes que nous allons présenter sont itératives et consistent en la construction d’une suite ( xn )n∈N telle
que lim xn converge vers l’un des zéros de la fonction
1.1 Vitesse de convergence d’une suite :
Définition :
Soit ( xn )n∈N une suite convergente vers α. On appelle ordre de convergence de la suite ( xn ) le réel fini ou infini r > 0
défini par :
| x n +1 − α |
r = sup{s ∈ R+ tel que lim < ∞}
n→+∞ | xn − α|s
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 :
| x n +1 − α |
lim =k≤1
n→+∞ | xn − α|
— Si 0 < k < 1 on dit que la suite ( xn ) est à convergence linéaire.
— Si k = 0 on dit que la suite ( xn ) est à convergence super-linéaire.
— Si k = 1 on dit que la suite ( xn ) est à convergence logarithmique .
Définition :
Soit ( xn )n∈N une suite qui converge vers une limite α. On dit que la convergence de ( xn )n∈N vers α est d’ordre r ≥ 1
lorsqu’il existe une suite (en )n∈N qui converge vers 0, majore l’erreur commise : ∀n ∈ N, | xn − α| ≤ en et vérifie :
e n +1
lim = µ tel que 0 < µ < ∞
n→+∞ ern
.
1.2 Critères d’arrêt :
En cas de convergence le suite ( xn )n∈N construite par une méthode itérative converge vers c. Pour l’utilisation pra-
tique d’une telle méthode il faut introduire un critère d’arrêt pour interrompre le processus itératif lorsque l’approxima-
tion de c par xn est jugée satisfaisante .Pour cela, plusieurs choix sont possibles :
— imposer un nombre maximal d’itérations.
— imposer une tolérance e > 0 sur l’incrément :| xn+1 − xn | < e.
— imposer une tolérance e > 0 sur le résidu :| f ( xn )| < e.
2 Méthode de la dichotomie :
2.1 Principe :
Soit f : [ a, b] −→ R continue telle que f ( a) f (b) ≤ 0
Page 1
Abid abdellah. -
Charif al idrissi.- Système non linéaire f ( x ) = 0 Informatique
a+b
On calcule l’image du milieu de l’intervalle m = 2 , certainement on aura l’une des conditions vérifiées, soit
f ( a) f (m) ≤ 0 ou f (m) f (b) ≤ 0
Dans notre cas, c’est f ( a) f (m) ≤ 0, c-à-dire la solution qu’on cherche appartient à l’intervalle [ a, m]
On recommence la même procédure avec le nouvel intervalle
En gros, nous sommes entrain de construire par récurrence sur n trois suites ( an ), (bn ) et (mn ) telles que a0 = a, b0 = b
et telles que pour tout n ≥ 0,
— mn = an + 2
bn
— Si f (mn ) f (bn ) ≤ 0 alors an+1 = mn et bn+1 = bn .
— Si f (mn ) f ( an ) ≤ 0 alors an+1 = an et bn+1 = mn .
2.2 Etude de la convergence :
Theorème :
Soit f : [ a, b] −→ R vérifiant f ( a) f (b) ≤ 0 et soit α ∈ [ a, b] l’unique solution de l’équation f ( x ) = 0. Si l’algorithme
de dichotomie arrive jusqu’à l’étape n alors on a l’estimation :
b−a
|α − mn | ≤
2n +1
Par conséquent, la suite (mn ) converge vers α.
Ce théorème valide notre algorithme et pour assurer sa terminaison, on peut choisir une valeur e > 0, et on retourne
(mn ) dès que |α − mn | < e
Page 2
Abid abdellah. -
Charif al idrissi.- Système non linéaire f ( x ) = 0 Informatique
Remarque : La méthode de dichotomie est d’ordre 1.
En effet, on pose en = b2−na . D’après le théorème précédent, On a ∀n ∈ N, | xn − α| ≤ en ,et en converge vers 0, ainsi que
e
lim ne+n 1 = 12
n→+∞
2.3 Implémentation :
3 Méthode de Newton :
3.1 Principe :
Soit f : [ a, b] −→ R une fonction de classe C 2
Etant donné un point x0 , x1 est l’abscisse du point d’intersection de la tangente de f en xn avec l’axe des abscisses.
alors on recommence l’opération avec la tangente au point d’abscisse x1 .
Page 3
Abid abdellah. -
Charif al idrissi.- Système non linéaire f ( x ) = 0 Informatique
Ce processus conduit à la définition d’une suite récurrente :
(
x0 ∈ [ a, b]
f ( xn )
x n +1 = x n − f 0 ( xn )
En effet la tangente au point d’abscisse xn a pour équation :y = f 0 ( xn )( x − xn ) + f ( xn ). Donc le point (xn+1 ,0) appartenant
à la tangente et à l’axe des abscisses vérifie 0 = f 0 ( xn )( xn+1 − xn ) + f ( xn ).
3.2 Implémentation :
3.3 Etude de la convergence :
Proposition :
Soit f de classe C 2 définie au voisinage d’un point α pour lequel f (α) = 0 et f 0 (α) 6= 0. Alors il existe un voisinage V
de α pour lequel, quel que soit x0 ∈ V la suite ( xn )n∈N converge vers α. En outre, la convergence est quadratique.
Démonstration :
Supposons que f 0 (α) > 0, alors f est strictement croissante au voisinage de α, donc il existe une intervalle [ a, b] tel
que : f ( a) < f (α) = 0 < f (b)
f (x)
Posons φ( x ) = x − f 0 ( x) . φ est de classe C 1 et f ( x ) = 0 ⇔ φ( x ) = x.
f (x) f ( x )− f (α)f (α)− f ( x )−(α− x ) f 0 ( x )
Alors φ( x ) − α = x − α − f 0 (x)
= x−α− f 0 (x)
= f 0 (x)
de Taylor-Lagrange | f (α) − f ( x ) − (α − x ) f 0 ( x )| ≤ M22 (α −
Selon l’inégalité x )2
Donc |φ( x ) − α| M2
≤ 2 fM0 (2x) (α − x )2 ≤ 2m 1
( α − x )2 ≤ K ( α − x )2
Choisissons η > 0 assez petit pour que Kη < 1 et [α − η, α + η ] ⊂ [ a, b] Alors x0 ∈ [α − η, α + η ] ⇒ ∀n ∈ Nxn ∈
[α − η, α + η ]
n
De plus, | xn+1 − α| ≤ K (α − xn )2 et par récurrence on peut montrer que | xn − α| ≤ K1 (K |α − x0 |)2
Puisque K | x0 − c| ≤ Kη < 1 ceci montre que limxn = α
n e
En posant en = K1 (K |α − x0 |)2 on a donc lim ne+2 1 = K > 0 d’où la convergence est quadratique
n→+∞ n
Page 4
Abid abdellah. -
Charif al idrissi.- Système non linéaire f ( x ) = 0 Informatique
4 Exercice :
4.1 Exercice 1 : Méthode de la sécante
Une autre solution si on ne souhaite pas à avoir à se préoccuper du calcul de la dérivée dans la méthode de Newton,
consiste à remplacer cette dernière par la pente de la corde reliant les points d’abscisses xn−1 et xn−2 .
Autrement dit, la relation :
f ( xn )
x n +1 = x n −
f 0 ( xn )
sera remplacée par :
x n − x n −1
x n +1 = x n − f ( xn )
f ( x n ) − f ( x n −1 )
Q1) Écrire une fonction sécante(a,b, f ,eps) qui prends en argument a et b les extrémité de l’intervalle [ a, b], f une
fonction et eps la tolérance initialisé à 1e−8 , et qui renvoie la racine de f situé a l’intervalle [a,b].
Q2) Trouver une valeur approximative de π
1. préciser l’intervalle d’étude.
2. donner la fonction f à utilser.
3. tracer la courbe de f et le point (π,0)
4.2 Exercice 2 : Méthode de la fausse position (Regula Falsi)
Soit f : [ a, b] −→ R continue telle que f ( a) f (b) ≤ 0
Le principe de cette méthode est le même que celui de la dichotomie sauf qu’à la place de calculer le milieu, on
calcule l’abscisse m du point d’intersection de la corde reliant les points de coordonnées ( a, f ( a)) et (b, f (b)) avec l’axe
des abscisses.
certainement on aura l’une des conditions vérifiées, soit f ( a) f (m) ≤ 0 ou f (m) f (b) ≤ 0
Page 5
Abid abdellah. -
Charif al idrissi.- Système non linéaire f ( x ) = 0 Informatique
Dans notre cas, c’est f ( a) f (m) ≤ 0 , c-à-dire la solution qu’on cherche appartient à lintervalle [a,m]
On recommence la même procédure avec le nouvel intervalle
f (b)− f ( a)
la corde en question a pour équation : y = b− a ( x − a) + f ( a) donc l’abscisse m du point d’intersection avec l’axe
des abscisses vérifie :
f (b) − f ( a) a f (b) − b f ( a)
0= (m − a) + f ( a) ⇔ m =
b−a f (b) − f ( a)
En gros, nous sommes entrain de construire par récurrence sur n trois suites ( an ) , (bn ) et (mn ) telles que a0 = a,b0 = b
et telles que pour tout n ≥ 0 ,
an f (bn )−bn f ( an )
1. mn = f (bn )− f ( an )
2. Si f (mn ) f (bn ) ≤ 0 alors an+1 = mn et bn+1 = bn .
3. Si f (mn ) f ( an ) ≤ 0 alors bn+1 = mn et an+1 = an .
Q1) Écrire une fonction Regula Falsi(a,b,f,eps) qui prends en argument a et b les extrémité de l’intervalle [a,b], f une
fonction et eps la tolérance initialisé à 1e−8 , et qui renvoie la racine de f situé à l’intervalle [a,b].
√
Q2) Trouver une valeur approximative de − 3 4
1. préciser l’intervalle d’étude.
2. donner la fonction f à utiliser.
√
3. tracer la courbe de f et le point (− 3 4,0)
Q3) Modifie les deux fonction dichotomie et regula falsi en renvoyant aussi le nombre d’itération. comparer les deux
méthodes ( en terme de nombre d’itération).
Page 6
