Dichotomie

Systèmes d'équations non linéaires 2
1. Dichotomie 2
2. Point #xe 3
3. Méthodes de Newton et et de la sécante 5
1
Systèmes d'équations non linéaires
On considère un intervalle I ⊂ R (borné ou non) et une fonction f : I → R.
On cherche à résoudre
x ∈ I, f (x) = 0
1. Dichotomie
1.1. Description. Soit f : [a, b] → R une fonction continue telle que
f (a) f (b) < 0
Alors en vertu du théorème des valeurs intermédiaire, il existe x0 ∈ [a, b] tel que
f (x0) = 0. Soit c =
a+b
2
, alors si f (c) = 0, c est solution, sinon f (a) f (c) < 0
ou bien f (c) f (b) < 0 dans le premier cas, on pose b = c dans le deuxième cas, on
pose a = c. Dans les deux cas on obtient à nouveau f (a) f (b) < 0. On peut alors
réitérer le processus, jusqu'à ce que l'une des conditions suivantes soit
réalisée :
(1) |b − a| < #
(2) |f (c)| < δ
Si l'un des deux tests d'arret est positif, on estime que l'on a convergé vers une
solution approchée de l'équation f (x) = 0.
1.2. Algorithme. L'algorithme s'écrit (il s'agit ici un code scilab):
Algorithm 1.1. [k,E]=Dichotomie(f, a,b,#,K)
//Résolution de f (z) = 0 par dichotomie
//entrée a < b intervalle initial
// # pour le test d'arret |f (c)| < #
// K pour limiter le nombre d'itérations.
//Sortie : k, nombre d'itérations
// X=(ci, 0 ≤ i ≤ k), les itérés
// E=(|f (ci)| , 0 ≤ i ≤ k)
if f(a)*f(b)>0 then return end
c=(a+b)*0.5;fc=f(c);
C=c;E=abs(fc);
k=1;
while abs(fc)>eps# & k<K do
k=k+1;
if f(a)*fc<0 then
b=c;
else
a=c;
end
c=(a+b)*0.5;fc=f(c);
E=[E,abs(fc)]
end
return k,C,E;
2
2. POINT FIXE 3
endfunction
1.3. Convergence.
Theorem. Soient [a0, b0] , [a1, b1] , ..., [an, bn] , ... les intervalles engendrés
par l'algorithme de dichotomie, alors les suites an et bn
sont adjacente et leur limite commune est un zéro de f. Soit
r = limn→∞ cn avec cn =
an+bn
2
, alors
|r − cn| ≤ 2
−(n+1) |b0 − a0|
Example 1.2. Si [a, b] = [0, 1], pour obtenir une précision |x
∗ − xn| < 10−6
, il
faut 19 itérations, quelle que soit la fonction f.
2. Point #xe
L'équation f (x) = 0 est supposée mise sous la forme F (x) = x
2.1. Description.
Definition 2.1. On dit que x est un point #xe de F si et seulement si F (x) = x
la méthode de point #xe consiste à considérer la suite
x0 ∈ R
xn+1 = F (xn)
Dans quelles conditions la suite est-elle convergente ? C'est ce à quoi nous allons
essayer de répondre dans le paragraphe sur la convergence. Auparavent :
2.2. L'algorithme. Voici le code scilab de l'algorithme de point #xe pour
la résolution de F (x) = x:
function [k,x,E]=PointFixe(F,x,eps,K)
//resolution de F(x)=x par la méthode du point fixe
//x valeur initiale puis solution
//eps réel positif : la precision on arete lorsque |F(x)-x|<eps
// K entier : nombre max d'itérations
//E vecteur réel : historique de l'erreur |F(x)-x|
//k entier : nombre d'itérations
k=1;y=F(x);dx=abs(y-x);E=dx;
while dx>eps & k<K do
x=y;
y=f(x);
dx=abs(y-x);
E=[E,dx]
k=k+1
end
return k,x,E
endfunction
2. POINT FIXE 4
2.3. Conditions de convergence.
Theorem 2.2. Soit I un intervalle fermé, borné de R et F : I → R
véri#ant
(1) F (I) ⊂ I
(2) F continue sur I
(3) F monotone sur I
alors F admet un point #xe x
∗ ∈ I
Definition 2.3. Soit I = [a, b] 6= ∅ et f : I → R. L'application f
est dite contractante sur I si :
il existe un réel λ ∈ [0, 1[ tel que pour tout x, y ∈ I :
|F (x) − F (y)| 6 λ |x − y|
Proposition 2.4. Soit I = [a, b] 6= ∅ et soit F une application de
classe C
1
sur I véri#ant
sup
I
|F
0
| < 1
Alors F est contractante sur I.
Le théorème suivant donne des conditions su#santes pour que F admette un
point #xe x
∗
et pour que la suite xn converge vers x
∗
.
Theorem 2.5. Soit I un intervalle fermé de R et F : I → R une
application contractante sur I, telle que F (I) ⊂ I
alors
(1) F admet un unique point #xe x
∗ ∈ I et
(2) pour tout x0 ∈ I, la suite xn+1 = F (xn) converge vers
x
∗
.
Proposition 2.6. Soit I = [a, b], soit F une application de classe
C
1
sur I admettant un point #xe x
∗ ∈ I, et véri#ant |F
0
(x
∗
)| < 1.
Alors on peut trouver un intervalle Iδ = [x
∗ − δ, x∗ + δ] tel que
F (I) ⊂ I et F est contractante sur Iδ.
Corollary 2.7. Si F admet un point #xe x
∗
, si F est de classe C
1 au voisinage
de x
∗
, si |F
0
(x
∗
)| < 1, alors il existe un voisinage V de x
∗
tel que pour tout x0 ∈ V ,
la suite xn+1 = F (xn) converge vers x
∗
.
2.4. Ordre de convergence d'une suite réelle.
Definition 2.8. soit (un) une suite réelle convergent vers u. Si
l'erreur en = u − un véri#e
|en+1| = O (|en|
α
)
on dit que l'ordre de convergence de la suite est (au moins) α.
Si α = 1 la convergence est linéaire,
si 1 < α < 2 la convergence est dite super-linéaire,
si α = 2 la convergence est dite quadratique,
Proposition 2.9. Pour que l'ordre de convergence soit α il su#t
que limn→∞
|en+1|
|en|
α existe et soit #nie.
3. MÉTHODES DE NEWTON ET ET DE LA SÉCANTE 5
Figure 1. Méthode de point #xe, di#érents cas de #gure
Proposition 2.10. Pour F assez régulière, si la suite xn+1 =
F (xn) converge vers x
∗
, alors son ordre de convergence est q, le
plus petit entier tel que F
(q)
(x
∗
) 6= 0
3. Méthodes de Newton et et de la sécante
3.1. Description. La méthode de Newton pour résoudre les équations non
linéaires
f (x) = 0
est un cas particulier de la méthode de point #xe.
On considère l'équation et on suppose donc f de classe C
2 au voisinage de la
solution x
∗
. Si l'on dispose d'une approximation xn pas trop éloignée de x
∗
, alors
on peut écrire en posant x
∗ = xn + h (h est l'erreur) et en utilisant la formule de
Taylor :
0 = f (x
∗
) = f (xn) + hf0
(xn) + O
h
2
#
(1)
' f (xn) + hf0
(xn)
Ce faisant, on a linéarisé le problème au voisinage de xn.
Linéariser la fonction f au voisinage du point x consiste à remplacer
la fonction h 7→ f (x + h) par sa partie linéaire : h 7→ f (x) +
hf0
(x).
On a donc approximativement h ' −
f(xn)
f
0(xn)
, à condition que f
0
(xn) 6= 0. On
peut donc corriger l'approximation courante en écrivant x
∗ ' xn+1 avec
xn+1 = xn −
f (xn)
f
0 (xn)
On réitère le processus, et on obtient la méthode de Newton
3. MÉTHODES DE NEWTON ET ET DE LA SÉCANTE 6
Figure 2. Algorithmes de Newton et de la sécante (ou Quasi-Newton)
(a) Newton
(b) quasi-Newton (sécante)
Si l'on ne dispose pas de la dérivée ou si celle-ci coûte trop cher à calculer, on
peut l'approcher par
f
0
(xn) '
f (xn) − f (xn−1)
xn − xn−1
on obtient alors la méthode de la sécante, qui est une méthode de quasi-Newton.
xn+1 = xn − f (xn)
(xn − xn−1)
f (xn) − f (xn−1)
3.2. Algorithmes (codes scilab).
Algorithm 3.1. [k,X,E]=Newton(f,df,x0,#,K)
#Méthode de Newton pour la résolution de f(x)=0
#Entree : f, df la fonction et sa dérivée.
# x0 ∈ R approximation initiale
# # > 0 le test d'arret est |f (x)| < #
# K nombre max d'iterations
#Sortie : k nombre d'iterations,
# X∈ Rk, la suite des itérés xn
# E∈ Rk, la suite des f (xn)
x=x0;k=1;fx=f(x);dfx=df(x);
X=x0;E=abs(fx);
while abs(fx)>eps & k<K do

Dichotomie

Transféré par

Droits d'auteur :

Formats disponibles

Dichotomie

Transféré par

Informations du document

Description originale:

Titre original

Copyright

Formats disponibles

Partager ce document

Partager ou intégrer le document

Options de partage

Avez-vous trouvé ce document utile ?

Ce contenu est-il inapproprié ?

Droits d'auteur :

Formats disponibles

Dichotomie

Transféré par

Droits d'auteur :

Formats disponibles

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

Vous aimerez peut-être aussi