Résolution numérique des équations

non linéaires
[email protected]
Yassine Hachaïchi
Smart Electricity & ICT ; ENICarthage
 Résolution numérique des équations non
linéaires
Position du problème Le problème est de calculer les zéros d’une
fonction continue f, c’est-à-dire les x points tels que f(x) = 0.
Exemples :
𝑥 2 − 2 = 0 on a 𝑥 = ± 2 ≈ ± 1,41 · · ·
𝑒 −𝑥 − 𝑥 = 0 on peut justifier l’existence d’un zéro par 𝑓(0) =
1
1 > 0 et 𝑓 1 = − 1 < 0.
𝑒
 Algorithme de la Dichotomie
• Informellement, on construit deux suites 𝑢𝑛 𝑛 et 𝑣𝑛 𝑛 , telles
que
lim 𝑢𝑛 = lim 𝑣𝑛 = 𝑐 𝑒𝑡 ∀𝑛 ∈ 𝑁; 𝑢𝑛 ≤ 𝑐 ≤ 𝑣𝑛 .
𝑛→∞ 𝑛→∞
• Cette méthode repose sur le théorème des valeurs intermédiaires :
Théorème (TVI) Soit f continue sur [a; b] telle que
𝑓(𝑎)𝑓(𝑏) < 0, 𝑎𝑙𝑜𝑟𝑠 ∃𝑐 ∈]𝑎; 𝑏[; 𝑓(𝑐) = 0
Précondition : Soit une fonction f continue, telle qu’il existe
𝑎 < 𝑏 𝑎𝑣𝑒𝑐 𝑓(𝑎)𝑓(𝑏) < 0, on sait par le TVI qu’il existe au
moins un zéro de f dans l’intervalle ]a; b[.
On construit les suites 𝑢𝑛 𝑛 , 𝑣𝑛 𝑛 et 𝑥𝑛 𝑛 comme suit.
𝑢0 = 𝑎; 𝑣0 = 𝑏
𝑢𝑛 +𝑣𝑛
et pour tout 𝑛 ∈ 𝑁 on pose 𝑥𝑛 = ;
2
Si 𝑓(𝑥𝑛 ) = 0 on a notre valeur et on arrête.
Sinon si 𝑓(𝑥𝑛 )𝑓(𝑢𝑛 ) < 0 alors 𝑢𝑛+1 = 𝑢𝑛 𝑒𝑡 𝑣𝑛+1 = 𝑥𝑛
Sinon 𝑢𝑛+1 = 𝑥𝑛 𝑒𝑡 𝑣𝑛+1 = 𝑣𝑛 .
Pour 𝑥𝑛 , on peut s ’arrêter une
étape avant !!
𝒏 ≥ 𝟑 × 𝐥𝐨𝐠 𝟐 𝟏𝟎 ≈ 𝟗. 𝟗𝟔𝟔
 Méthodes du point fixe
On dit que 𝛼 est un point fixe d’une fonction f si f(𝛼) = 𝛼.
Si f est continue, une méthode consiste en la construction d’un
suite convergente 𝑢𝑛+1 = 𝑓(𝑢𝑛 ), celle si converge vers un point
fixe de f.
Réduction de problème : Chercher un zéro d’une fonction
continue g, peut se réduire à la recherche d’un point fixe d’une
fonction continue f, par exemple :
𝑔 𝑥 = 0 ⇐⇒ 𝑓 𝑥 = 𝑥 + 𝜆 𝑥 𝑔 𝑥 = 𝑥; 𝑝𝑜𝑢𝑟 𝜆 𝑥 ≠ 0
Par exemple
3 3
1
𝑥 − 𝑥 − 1 = 0 ⇐⇒ 𝑥 − 1 = 𝑥 ⇐⇒ 2 = 𝑥
𝑥 − 1
On va commencer par donner des préconditions afin de garantir
l’existence d’un point fixe d’une fonction continue, ensuite les
conditions de convergence d’une méthode vers ce point fixe.
Théorème Soit f continue de [a; b] dans R.
Si 𝑓([𝑎; 𝑏]) ⊂ [𝑎; 𝑏] alors f admet un point fixe.
Preuve : 𝑓(𝑎) ∈ [𝑎; 𝑏] alors 𝑓(𝑎) − 𝑎 ≥ 0.
𝑓(𝑏) ∈ [𝑎; 𝑏] alors 𝑓(𝑏) − 𝑏 ≤ 0.
En utilisant le TVI pour 𝑓(𝑥) − 𝑥, on a
∃𝑐 ∈ [𝑎; 𝑏]; 𝑓(𝑐) − 𝑐 = 0.
Théorème Soit 𝑓 ∶ [𝑎; 𝑏] → 𝑅 une fonction continue. On
suppose que les hypothèses suivantes soient satisfaites :
H1. L'image de [a; b] par f est un sous-ensemble de [a; b] (c.-a-d.
𝒇([𝒂; 𝒃]) ⊆ [𝒂; 𝒃]) ;
H2. il existe K < 1 tel que
∀𝒙; 𝒚 ∈]𝒂; 𝒃[; |𝒇(𝒙) − 𝒇(𝒚)| ≤ 𝑲|𝒙 − 𝒚|
on dit que f est contractante.
Il existe alors un unique 𝛼 ∈ [𝑎; 𝑏] tel que 𝑓(𝛼) = 𝛼 , appelé
point fixe de f, et la suite (𝑢𝑛 ) définie par :
𝑢0 ∈]𝑎; 𝑏[ 𝑒𝑡 𝑢𝑘+1 = 𝑓(𝑢𝑘 ) converge vers 𝛼.
 Estimation du nombre d’itérations en fonction
de l'erreur tolérée
Pour chercher 𝛼 ∈ [𝑎; 𝑏] tel que 𝑓(𝛼) = 𝛼 à 𝜀 près par une
méthode de point fixe, il suffit que
𝑲𝒏 |𝒖𝟎 − 𝜶 | ≤ 𝑲𝒏 |𝒃 − 𝒂| ≤ 𝜺.
𝒂+𝒃 𝑲𝒏 𝒃 − 𝒂
Si 𝒖𝟎 = , 𝑲𝒏 𝒖𝟎 − 𝜶 ≤ ≤ 𝜺.
𝟐 𝟐
𝑎+𝑏
Pour une incertitude de 𝜀, et en prenant 𝑢0 = , on pose
2
𝟐𝜺
𝒍𝒐𝒈
𝒃−𝒂
𝑵𝜺 = 𝑬 + 𝟏
𝐥𝐨𝐠 𝑲
 Exemple.
1
Soit la fonction 𝑓 𝑥 = 𝑥 − (𝑥 2 − 2).
5
Montrez que la suite 𝑥0 ∈ [1; 2] 𝑒𝑡 𝑥𝑛+1 = 𝑓(𝑥𝑛 ) converge vers 2.
′ 2
f est clairement de classe C . 𝑓 𝑥 = 1 − 𝑥, alors pour 1 ≤ 𝑥 ≤
1
5
1 ′ 3
2, 𝑜𝑛 𝑎 0 ≤ ≤ 𝑓 𝑥 ≤ < 1.
5 5
6
f est croissante, alors pour 1 ≤ 𝑥 ≤ 2, on a 1 < 𝑓 1 = ≤ 𝑓 𝑥 ≤
5
8
𝑓 2 = < 2. On peut appliquer le théorème :
5
3 1
𝑥0 = 𝑒𝑡 𝑥𝑛+1 = 𝑥𝑛 − (𝑥𝑛2
− 2) converge vers l’unique point fixe de
2 5
f dans [1; 2].
1 2
𝑙− 𝑙 − 2 = 𝑙 ⇐⇒ 𝑙 2 − 2 = 0 ⇐⇒ 𝑙 = ± 2.
5
 ? 𝑁 ; 𝑢𝑁 = 2 ± 10−3
𝑛
3
𝑢𝑛 − 2 < 𝑏 − 𝑎 < 10−3
5
𝑛
5
103 <
3
0,0013060694016=0.6^(13)
Théorème (de convergence locale) Soit 𝑓 ∶ 𝐼 → 𝑅 telle que f
est de classe 𝐶 1 sur un ouvert I et ∃𝛼 ∈ 𝐼; 𝑓(𝛼) = 𝛼.
1. Si |𝑓′(𝛼)| < 1 alors il existe un voisinage 𝛼 ∈ 𝑉 ⊂ 𝐼 tel
que : ∀𝑥0 ∈ 𝑉 ; 𝑥𝑛+1 = 𝑓(𝑥𝑛 ); converge vers 𝛼
On dit que 𝛼 est un point fixe attractif.
2. Si |𝑓′(𝛼)| > 1 alors ∀𝑥0 ∈ 𝐼 ; 𝑥𝑛+1 = 𝑓(𝑥𝑛 ); diverge.
Sauf si 𝒙𝒏 = 𝜶 pour 𝒏 ∈ 𝑵. On dit que 𝛼 est un point fixe
répulsif.
3. Si 𝑓 ′ 𝛼 = 1 on ne peut rien décider.
Preuve :
1. Si 𝑓 ′ 𝛼 = 𝑙 < 1 alors il existe
𝑙+1
𝜀 > 0 ∶ ∀𝑥 ∈ 𝛼 − 𝜀, 𝛼 + 𝜀 ; 𝑓′ 𝑥 < < 1
2
puisque f′ est continue. Or par le théorème des accroissements finis :
𝑙+1
𝑥−𝛼 ≤𝜀 → 𝑓 𝑥 −𝑓 𝛼 ≤ 𝑥 − 𝛼 ≤ 𝑥 − 𝛼 ≤ 𝜀 alors
2
𝑓 𝑥 ∈ 𝛼 − 𝜀, 𝛼 + 𝜀
On peut alors appliquer le théorème du point fixe sur l’intervalle 𝛼 − 𝜀, 𝛼 + 𝜀 .
2. Si 𝑓 ′ 𝛼 = 𝑙 > 1 alors
𝑙 + 1
𝑓 𝑥𝑛 − 𝑓 𝛼 ≥ 𝑥𝑛 − 𝛼 > 𝑥𝑛 − 𝛼 > 𝜀
2
on déborde à chaque fois de l’intervalle
Cas convergents
Cas divergents
Définition (Application contractante) Soient (𝑋, 𝑑) un espace métrique et
𝑓 ∶ 𝑋 → 𝑋 une application. On dit que f est contractante s’il existe une
constante 0 < 𝑘 < 1 telle que
∀𝑥, 𝑦 ∈ 𝑋, 𝑑 𝑓 𝑥 , 𝑓 𝑦 ≤ 𝑘 𝑑(𝑥, 𝑦).
Théorème (Théorème du point fixe de Picard-Banach) Soient (𝑋, 𝑑) un
espace métrique complet et 𝑓 ∶ 𝑋 → 𝑋 une application k-contractante.
Alors
1. f admet un unique point fixe 𝑎 ∈ 𝑋,
2. pour tout 𝑥0 ∈ 𝑋, la suite des itérées de 𝑥0 par f, définie par 𝑥𝑛 ∶= 𝑓 𝑛 𝑥0
pour tout 𝑛 ∈ 𝑁, converge vers a,
𝑘𝑛
3. ∀𝑛 ∈ 𝑁, 𝑑 𝑥𝑛 , 𝑎 ≤ 𝑑 𝑥1 , 𝑥0 .
1−𝑘
Algorithme de Newton
L’algorithme de Newton est une méthode de point fixe pour rechercher le zéro d’une
1 𝑓 𝑥𝑛
fonction de classe 𝐶 tel que : 𝑥𝑛+1 = 𝑥𝑛 − ′
𝑓 𝑥𝑛
L’idée est de chercher 𝜆(𝑥) telle que : 𝑔(𝑥) = 𝑥 + 𝜆(𝑥)𝑓(𝑥) soit nulle en 𝛼 tel
que f(𝛼) = 0.
𝑔′(𝑥) = 1 + 𝜆′(𝑥)𝑓(𝑥) + 𝜆(𝑥)𝑓′(𝑥), en posant 𝑔′(𝛼) = 0, on a λ(𝛼)f′(𝛼) = −1.
On peut montrer que 𝑥𝑛+1 est le point d’intersection de la tangente à la courbe de f
au point 𝑥𝑛 (d’équation [𝑦 = 𝑓′(𝑥𝑛 )(𝑥 − 𝑥𝑛 ) + 𝑓(𝑥𝑛 )]) et l’axe des abscisse
(Ox)
(c’est-à-dire la racine de l’équation [0 = 𝑓′(𝑥𝑛 )(𝑥𝑛+1 − 𝑥𝑛 ) + 𝑓(𝑥𝑛 )]).
𝑓 𝑥
On pose alors 𝑥𝑛+1 = 𝑔(𝑥𝑛 ) avec 𝑔 𝑥 = 𝑥 − . En cas de convergence,
𝑓′ 𝑥
𝑓 𝑙 𝑓 𝑙
𝑔 𝑙 =𝑙 − = 𝑙 ⇐⇒ = 0 ⇐⇒ 𝑓 𝑙 = 0
𝑓′ 𝑙 𝑓′ 𝑙
Newton • [𝒚 = 𝒇′(𝒙𝒏 )(𝒙 − 𝒙𝒏 ) + 𝒇(𝒙𝒏 )]
• [𝟎 = 𝒇′(𝒙𝒏 )(𝒙𝒏+𝟏 − 𝒙𝒏 ) + 𝒇(𝒙𝒏 )]
Théorème (Newton locale) Soit 𝑓 ∶ [𝑎; 𝑏] → 𝑅 une fonction
de classe 𝐶 1 . On suppose que ∃𝛼 ∈]𝑎; 𝑏[; 𝑓(𝛼) =
0 𝑒𝑡 𝑓′(𝛼) ≠ 0 (racine simple). Alors il existe un voisinage V
de tel que la suite 𝑥𝑛 définie par :
𝒇 𝒙𝒏
𝒙𝟎 ∈ 𝑽 ; 𝒙𝒏+𝟏 = 𝒙𝒏 − ′ converge vers 𝛼.
𝒇 𝒙𝒏
𝑓 𝑥
Preuve : Soit 𝑔 𝑥 = 𝑥 − , on a alors : 𝑓 𝛼 = 0 ⇒
𝑓′ 𝑥
g 𝛼 =𝛼
𝑓′ 𝑥 2 −𝑓 𝑥 𝑓′′ 𝑥 𝑓 𝑥 𝑓′′ 𝑥
𝑔′(𝑥) = 1 − = , d’où g’ 𝛼 = 0.
𝑓′ 𝑥 2 𝑓′ 𝑥 2
Par le théorème du point fixe, il existe un voisinage V de tel
que ∀𝑥0 ∈ 𝑉; 𝑥𝑛+1 = 𝑔(𝑥𝑛 ) converge vers 𝛼.
Théorème (Newton globale) Soit 𝑓 ∶ [𝑎; 𝑏] → 𝑅 une fonction de classe 𝐶 2 . On
suppose que les hypothèses suivantes soient satisfaites :
H1. 𝑓(𝑎) · 𝑓(𝑏) < 0 ;
H2. 𝑓′(𝑥) ≠ 0; ∀𝑥 ∈]𝑎; 𝑏[.
H3. 𝑓′′(𝑥) ≠ 0; ∀𝑥 ∈]𝑎; 𝑏[.
Alors la suite 𝑥𝑛 définie par :
𝑓 𝑥𝑛
𝑥0 ∈ 𝑉 𝑡𝑒𝑙 𝑞𝑢𝑒 𝑓 𝑥0 𝑓 ′′ 𝑥0 > 0 ; 𝑥𝑛+1 = 𝑥𝑛 − ′ converge vers l’unique
𝑓 𝑥𝑛
𝛼 ∈ 𝑎, 𝑏 ; 𝑓 𝛼 = 0.

La démonstration peut être faite pour le cas (H2); 𝑓′(𝑥) > 0 et (H3); 𝑓′′(𝑥) > 0.
On montre dans ce cas que 𝑥𝑛 est décroissante minorée par 𝛼.
Ordre d'une méthode
Soit 𝑥𝑛 une suite qui converge vers 𝛼 (une méthode). On dit que est
d’ordre (au moins) 𝑝 > 0 ⇐⇒
𝑥𝑛+1 − 𝛼
𝑥𝑛 − 𝛼 𝑝
est bornée.
Cet indicateur nous donne un comparaison entre les méthodes. Plus
l’ordre p est grand, plus la méthode converge rapidement vers le point
fixe. Algorithmiquement, pour une incertitude fixée 𝜀 , le nombre
d’itérations N𝜀 est plus petit.
La dichotomie et la fausse position sont d’ordre 1.
Théorème Soit g de classe 𝐶 𝑝 au voisinage de la limite 𝛼 = 𝑔(𝛼). Si
𝑔 𝑘 (𝛼) = 0, 𝑝𝑜𝑢𝑟 𝑘 = 1; · · · ; 𝑝 − 1 et 𝑔 𝑝 (𝛼) ≠ 0, alors la suite
𝑥𝑛+1 = 𝑔(𝑥𝑛 ) est d'ordre exactement p.
Preuve : Soit le développement limité de g au voisinage de 𝛼 :
𝑔 𝑘 𝛼 𝑔 𝑝 𝛼
𝑝−1
𝑔 𝑥 = 𝑔 𝛼 + Σ𝑘=1 𝑥−𝛼 𝑘+ 𝑥 − 𝛼 𝑝 + 𝑜( 𝑥 − 𝛼 𝑝 )
𝑘! 𝑝!
𝑔𝑝 𝛼
⇐⇒ 𝑔(𝑥) − 𝑔(𝛼) = 𝑥 − 𝛼 𝑝 + 𝑜( 𝑥 − 𝛼 𝑝 )
𝑝!
On a alors
𝑔𝑝 𝛼 𝑝 𝑝
𝑥𝑛+1 − 𝛼 = 𝑔(𝑥𝑛 ) − 𝑔(𝛼) = 𝑥𝑛 − 𝛼 + 𝑜 𝑥𝑛 − 𝛼 ⇐⇒
𝑝!
𝑥𝑛+1 −𝛼 𝑔𝑝 𝛼
→ ≠0
𝑥𝑛 −𝛼 𝑝 𝑝!
Proposition Soit 𝑓 ∶ [𝑎; 𝑏] → 𝑅 une fonction de classe 𝐶 1 .
On suppose que ∃𝛼 ∈]𝑎; 𝑏[; 𝑓(𝛼) = 0 𝑒𝑡 𝑓′(𝛼) ≠ 0
(racine simple). , alors la méthode de Newton est d'ordre au
moins 2.
Il suffit de voir la preuve de la méthode de Newton où on a
𝛼 = 𝑔(𝛼) et 𝑔′ (𝛼) = 0

Soit a > 0 un réel, écrire l’algorithme de Newton pour

approcher 𝑎. Prenez a = 3 et effectuez les 4 premières
itérations. Comparez avec 3
Systèmes d'équations à plusieurs variables
On peut aussi utiliser la méthode de Newton pour résoudre un système
de n équations (non linéaires) à n inconnues 𝑥 = (𝑥1 , … , 𝑥𝑛 ), ce qui
revient à trouver un zéro d'une fonction F de ℝ𝑛 dans ℝ𝑛 , qui devra être
différentiable et dont la différentielle est inversible.
Il faut multiplier par l'inverse de la matrice jacobienne J𝐹 (𝑥𝑘 ) au lieu de
diviser par 𝑓 ′ (𝑥𝑘 ). Évidemment, pour économiser du temps de calcul,
on ne calculera pas l'inverse de la jacobienne, mais on résoudra le
système d'équations linéaires suivant
J𝐹 𝑥𝑘 𝑥𝑘+1 − 𝑥𝑘 = −𝐹 𝑥𝑘