Chapitre 2 Équations non linéaire
Pour une fonction f donnée, on veut résoudre (trouver x)
f(x) = 0
• Pour certains cas c’est facile (les polynômes de degré 4 par exemple). Mais on à rien
pour les polynômes degrés supérieurs. Et rien pour une fonction quelconque.
• On voudrait une méthode systématique, on cherche plutôt une méthode s’appuyant le
moins possible sur des particularités de la fonction.
Définition Un point x pour lequel la fonction f « touche » l’axe des x (f(x) = 0) est appelé
racine de la fonction f.
Dans ce chapitre on cherchera à construire des méthodes permettant de trouver les
racines d’une fonction quelconque.
U. Laval Dept. Math & Stat MAT-2910
1
Chapitre 2
Méthode de la bissection.
1. Choisir un intervalle de départ contenant un changement de signe de la fonction.
2. Approximer la racine par le point milieu de l’intervalle.
3. Déterminer le sous intervalle contenant la racine et retour à 2.
Après n passages dans l’étape 2 on aura une approximation xn de la racine.
Est-ce que ça marche tout le temps (n’importe quel f)? NON
a a x2
x2 x1 b x1 b
• La fonction doit couper l’axe: on doit avoir un changement de signe de f.
• S’appuie sur une connaissance « graphique » de la fonction, il faut trouver un intervalle
de départ contenant un changement de signe. On peut « rater » des racines très proches
les unes des autres.
U. Laval Dept. Math & Stat MAT-2910
2
Chapitre 2
Erreur d’approximation?
Si xn est l’approximation de la racine r à la nième étape de la bissection,
r
a xn b
• À chaque étape, r et xn se trouvent dans l’intervalle: l’erreur absolue est moins grande
que la moitié de la longueur de l’intervalle.
• À chaque étape on divise l’intervalle en 2 pour la prochaine étape.
Conclusion pour f une fonction ayant une racine en r. Notons xn la suite d’approximation
obtenue par la méthode de la bissection. On dira que la suite est convergente vers r
(notée xn r) avec
Où L est la longueur de l’intervalle initial.
Remarque pour un intervalle de départ donné, pour garantir une erreur absolue inférieure
à e donnée, il suffit que
U. Laval Dept. Math & Stat MAT-2910
3
Chapitre 2
La dernière question est celle de l’arrêt de la méthode, pour cela introduisons du
vocabulaire.
Méthode itérative: méthode dans laquelle on applique de manière répétitive (en boucle)
une méthode plus simple.
Itération: une application de la méthode contenue dans la boucle d’une méthode
itérative.
La bissection est une méthode itérative. Une itération consistant à calculer le point milieu
et à déterminer le prochain sous-intervalle (contenant la racine).
Une méthode itérative produit une suite d’approximation.
Une méthode itérative est convergente si la suite d’approximation converge.
La méthode itérative est divergente si la suite d’approximation diverge.
La méthode itérative est non-convergente si la suite d’approximation ne converge pas,
mais ne diverge pas (pensez à xn = (-1)n).
La bissection est une méthode toujours convergente: fermée. Ce n’est pas le cas de toute
les méthodes. Certaines méthodes ne convergeront que dans certaines conditions de
départ et divergeront autrement.
U. Laval Dept. Math & Stat MAT-2910
4
Chapitre 2
Quand est-ce qu’on arrive? Une méthode itérative donne à chaque itération une
approximation. Dans un monde idéal on arrêterait lorsque
|xn − r| = 0
Les erreurs de troncature, de représentation, le trop grand nombre d’itérations, etc. font
en sorte que cette condition n’est presque jamais réalisable.
Critère d’arrêt: condition vérifiée à chaque itération permettant l’arrêt de la méthode:
• critère de convergence une condition indiquant la convergence de la suite. Indicateur
définissant une solution acceptable (succès).
• critère de divergence/non-convergence une condition indiquant l’instabilité ou
l’impossibilité d’atteindre la convergence. Indicateur définissant un échec de la méthode.
Tolérance Valeur choisie pour l’évaluation d’un critère d’arrêt.
En général on utilisera plus d’un critère à la fois. Les valeurs de tolérances étant basées sur les
qualités attendues pour la solution: rapidité de calcul, nombre de C.S. estimé, etc.
Les critères les plus fréquemment utilisés
U. Laval Dept. Math & Stat MAT-2910
5
Chapitre 2
Une méthode inconnue, produit le résultat:
Iter. xi f(xi) |xi - xi-1| |xi - xi-1|/|xi|
0 9.9900000000E-01 9.9800100000E-01 ---- ----
1 9.9800100000E-01 9.9600599600E-01 9.9900000000E-04 1.0010010010E-03
2 9.9600599600E-01 9.9202794407E-01 1.9950039990E-03 2.0030040050E-03
3 9.9202794407E-01 9.8411944182E-01 3.9780519311E-03 4.0100200351E-03
4 9.8411944182E-01 9.6849107576E-01 7.9085022543E-03 8.0361203308E-03
…
11 1.2886052215E-01 1.6605034170E-02 2.3011095604E-01 1.7857366414E+00
12 1.6605034170E-02 2.7572715978E-04 1.1225548798E-01 6.7603286351E+00
13 2.7572715978E-04 7.6025466639E-08 1.6329307010E-02 5.9222700524E+01
14 7.6025466639E-08 5.7798715777E-15 2.7565113431E-04 3.6257736584E+03
15 5.7798715777E-15 3.3406915455E-29 7.6025460859E-08 1.3153486170E+07
16 3.3406915455E-29 1.1160220002E-57 5.7798715777E-15 1.7301422472E+14
La méthode converge! La méthode diverge!
Attention: il est clair que la méthode converge vers 0 une racine de f. Le critère d’arrêt à
droite est mal choisi (division par zéro) et renvoie un faux négatif.
U. Laval Dept. Math & Stat MAT-2910
6
Chapitre 2
La bissection peut être lente (beaucoup d’itérations == propagation d’erreur), exige une
connaissance a priori de la position des racines et n’est pas toujours applicable.
On construit une méthode plus rapide et plus générale en s’appuyant sur la notion de
point fixe et sur les résultats théoriques s’y rattachant.
Définition Soit g une fonction réelle. Un point x tel que g(x) = x est appelé point fixe de g.
Remarques
• Si x est un point fixe de g alors c’est une racine de f(x) = x-g(x). La recherche d’un point
fixe est similaire à la recherche d’une racine.
• Tous les points fixes de g-(x) = x – f(x) et g+(x) = x + f(x) sont des racines de f(x).
• On peut « fabriquer » de nombreuses fonctions dont un point fixe correspond à une
racine spécifique d’une fonction donnée.
Méthode du point fixe
• x0 donné
• xn+1 = g(xn) n=1,2,…
Facile, semble générale. Mais est-ce que ça marche vraiment?
U. Laval Dept. Math & Stat MAT-2910
7
Chapitre 2
Supposons g suffisamment différentiable avec un point fixe g(r) = r
• soit l’erreur d’approximation: en = xn – r.
• En se basant le théorème de Taylor (en petit):
• Si et les termes d’ordres supérieurs sont négligeables, on peut écrire
• Si , en+1 tend vers zéro et la méthode converge vers r.
• Si , en+1 ne peut pas décroitre et la méthode ne peut pas converger vers r.
• Si , le signe de l’erreur alternera, on aura donc des approximations
qui seront alternativement supérieures (en+1 > 0) et inférieures (en+1 < 0) à r.
On appelle taux de convergence d’une méthode de point fixe la valeur de . Il sert à
comparer des méthodes, plus le taux est petit (mais dans ]0,1[) plus la convergence sera
rapide.
U. Laval Dept. Math & Stat MAT-2910
8
Chapitre 2
Et si ? Indéterminé, dépendra de la fonction et du point de départ!
Convergence de la
méthode: on
s’approche du point
fixe
Divergence de la
méthode: on s’éloigne
du point fixe
U. Laval Dept. Math & Stat MAT-2910
9
Chapitre 2
Jusqu’ici:
Bissection: on approxime la racine par une suite de points milieux d’intervalles emboités
contenant la racine et dont la longueur est divisée par deux à chaque étape.
• terme d’erreur connu
• méthode simple mais qui ne fonctionne que si la fonction coupe l’axe des x.
Méthode du point fixe: on remplace la recherche d’une racine de f par la recherche de
point fixe d’une fonction g fabriquée uniquement dans ce but.
Si g est suffisamment dérivable et
• Si , la méthode converge vers r.
• Si , la méthode ne peut pas converger vers r.
• Si la convergence dépendra du point de x0 et de la nature de g
Le comportement de la méthode (conv./div.) dépend de x0, car le dev. de Taylor sous-
entend que l’on est « proche » de r.
U. Laval Dept. Math & Stat MAT-2910
10
Chapitre 2
Et si ? On reprend Taylor mais on garde la dérivée 2eme (négligeant les termes sup.)
On pourrait faire une analyse similaire à la précédente. À retenir : la convergence dépendra
explicitement du point de départ (e0 = x0-r).
Définition La méthode du point fixe converge à l’ordre p si il y a une constante C telle que
Remarques
• Une convergence d’ordre 1 est linéaire, d’ordre 2 est quadratique, d’ordre 3 cubique, etc.
• la méthode converge à l’ordre 1 (linéaire).
• Si la méthode converge et que alors la convergence est au moins d’ordre 2
(quadratique). Elle est quadratique si la dérivée 2eme est non nulle.
• La convergence cubique!? La dérivée 1ere et 2eme sont nulles en r, on recommence
l’exercice mais avec la dérivée 3eme (la convergence dépend de g(3)(r) et e0)
U. Laval Dept. Math & Stat MAT-2910
11
Chapitre 2
Remarques
•On ne connait pas r. Si xn est proche de r on aura
• On pourra mesurer l’ordre (ou valider un algorithme) en estimant l’ordre à partir des
approximations d’erreur!
• Convergence linéaire:
• Convergence quadratique:
Pourquoi on aime la convergence quadratique?
|x0-r| = 0.1 pour une convergence linéaire: |x3-r| C1| x2-r | C12| x1-r | C13| x0-r |=0.1C13
|x0-r| = 0.1 pour une convergence quadratique:
|x3-r| C2| x2-r |2 C2 (C2| x1-r |2)2 C2 (C2 (C2| x0-r |2)2)2=1x10-8C27
Stratégie: si on peut, on choisit des g qui nous donne une convergence quadratique
U. Laval Dept. Math & Stat MAT-2910
12
Chapitre 2
Une méthode inconnue produit ce tableau:
Iter. x_i f(x_i) E_i |E_i+1|/|E_i| |E_i+1|/|E_i|2
0 1.0000000000E+000 -2.000000E+001
1 7.6666666667E+000 4.296296E+002 6.666667E+000
2 5.2302037387E+000 1.220724E+002 2.436463E+000 3.654694E-001 5.482042E-002
3 3.7426969187E+000 3.142688E+001 1.487507E+000 6.105190E-001 2.505759E-001
4 2.9948535683E+000 5.861285E+000 7.478434E-001 5.027495E-001 3.379813E-001
5 2.7770222259E+000 4.159856E-001 2.178313E-001 2.912794E-001 3.894925E-001
6 2.7590418664E+000 2.687565E-003 1.798036E-002 8.254257E-002 3.789288E-001
7 2.7589241814E+000 1.146346E-007 1.176850E-004 6.545199E-003 3.640193E-001
8 2.7589241764E+000 0.000000E+000 5.020130E-009 4.265734E-005 3.624704E-001
Conclusion: La méthode converge vers 2.7589241 une racine de la fonction f. La
convergence est quadratique, car:
U. Laval Dept. Math & Stat MAT-2910
13
Chapitre 2
Une méthode inconnue d’ordre 2 produit les résultats suivants
Iter. xi f(xi) Ei |Ei+1|/|Ei| |Ei+1|/|Ei|2
0 3.9000000000E+00 -6.877662E-05
1 3.9256775621E+00 -2.154734E-05 2.567756E-02
2 3.9446108896E+00 -6.771760E-06 1.893333E-02 7.373491E-01 2.871570E+01
3 3.9586457814E+00 -2.132483E-06 1.403489E-02 7.412797E-01 3.915211E+01
4 3.9690856434E+00 -6.724478E-07 1.043986E-02 7.438506E-01 5.300009E+01
….
12 3.9969307913E+00 -6.697819E-11 1.024287E-03 7.494759E-01 5.483954E+02
13 3.9976986055E+00 -2.118759E-11 7.678142E-04 7.496086E-01 7.318348E+02
14 3.9982742415E+00 -6.702768E-12 5.756360E-04 7.497074E-01 9.764178E+02
15 3.9987058425E+00 -2.120533E-12 4.316010E-04 7.497811E-01 1.302526E+03
16 3.9990294725E+00 -6.708871E-13 3.236300E-04 7.498361E-01 1.737336E+03
Conclusion: Attention la méthode est en difficulté! On converge vers 4. une racine de la
fonction f. Mais la convergence est linéaire, car:
U. Laval Dept. Math & Stat MAT-2910
14
Chapitre 2
Le comportement de la méthode dépend de x0, comment choisir x0 garantissant la
convergence?
Définition: le bassin d’attraction d’un point fixe r de g est l’ensemble des points x0 pour
lesquels la méthode converge vers r.
Idéalement, on choisit un point de départ dans ce bassin. Mais comment définir le bassin?
On voudrait une relation entre le bassin et la dérivée de g. On peut caractériser les points
fixes.
Un point fixe est attractif si
un point fixe est répulsif si
un point fixe est indéterminé si
Pour une fonction g dont la dérivée est continue près de r
• si r est un point fixe attractif alors on garanti un bassin d’attraction contenant plus que r
• si r est un point fixe répulsif alors on ne peut rien dire sur le bassin d’attraction. Il peut
être un singleton.
• si r est un point fixe indéterminé, on ne peut rien dire.
Pas très satisfaisant…
U. Laval Dept. Math & Stat MAT-2910
15
Chapitre 2
Complexité du bassin d’attraction.
Ici un exemple en dimension 2.
En noir les points du bassin.
En couleur: les points répulsifs
avec gradation en fonction de
leur « vitesse de divergence »
[Link]
U. Laval Dept. Math & Stat MAT-2910
16
Chapitre 2
Un résultat existe dans des conditions particulières, c’est le théorème de point fixe:
Théorème Soit une fonction continue g(x) de[a,b] dans [a,b] et telle que
pour tout x ∈]a,b[
alors :
• Il existe un unique point fixe r de la fonction g(x) dans l’intervalle [a,b].
• L’algorithme des points fixes xn+1=g(xn) converge vers r et ce, quelle que soit la valeur de x0
dans [a,b].
C’est le mieux que nous avons concernant le bassin d’attraction. Cependant les conditions
d’application sont assez restrictives.
Dans la réalité on choisira un point de départ en se basant sur
• Le respect de la réalité décrite et des dimensions des variables (km, °C, $, etc.)
• Une estimation du point fixe visé ou du bassin d’attraction.
Puisqu’on ne connait pas exactement la nature du point fixe, son bassin d’attraction, ou le
comportement de la méthode, il est essentiel d’avoir
• de bon critère de convergence/divergence.
• de comprendre et savoir analyser les résultats obtenus.
U. Laval Dept. Math & Stat MAT-2910
17
Chapitre 2
