6.7 R´ esolution des syst` emes d’´ equations non lin´ eaires
251
Propri´ et´ e 6.9 Si les hypoth` eses du Th´ eor` eme 6.2 sont satisfaites et s’il existe
deux constantes positives ε et γ telles que
(0)
− x
∗
≤ ε, Q 0 − J F (x
∗ ) ≤ γ,
alors la suite de vecteurs x
(k) construite par la m´ ethode Broyden est bien
d´ efinie et converge superlin´ eairement vers x
∗ , c’est-` a-dire
(k)
− x
∗
≤ c k x
(k−1)
− x
∗
,
(6.53)
o` u les constantes c k sont telles que lim
k→∞
c k = 0.
En faisant des hypoth` eses suppl´ ementaires, il est possible de montrer que la
suite Q k converge vers J F (x
∗ ). Cette propri´ et´ e n’est pas toujours satisfaite
par l’algorithme pr´ ec´ edent comme le montre l’Exemple 6.13.
Il existe de nombreuses variantes de la m´ ethode de Broyden moins coˆ uteuses en calculs, mais elles sont en g´ en´ eral moins stables (voir [DS83], Chapitre 8).
Le Programme 54 propose une impl´ ementation de la m´ ethode de Broyden (6.48)-(6.52). On a not´ e Q l’approximation initiale Q 0 dans (6.52).
Programme 54 - broyden : M´ ethode de Broyden pour les syst` emes d’´ equations
non lin´ eaires
function [x,iter]=broyden(F,Q,x0,tol,nmax)
%BROYDEN M´ ethode de Broyden pour les syst` emes non lin´ eaires
% [X, ITER] = BROYDEN(F, Q, X0, TOL, NMAX) tente de r´ esoudre
% le syst` eme non lin´ eaire F(X)=0 avec la m´ ethode de Broyden.
% F est une chaˆ ıne contenant l’expression des ´ equations
% non lin´ eaires. Q est une approximation initiale de la jocobienne.
% X0 est la donn´ ee initiale. TOL est la tol´ erance de la m´ ethode.
% NMAX est le nombre maximum d’it´ erations. ITER est l’it´ eration
% `
a laquelle la solution X a ´ et´ e calcul´ ee.
[n,m]=size(F);
if n ˜= m, error(’Seulement pour les syst` emes carr´ es’); end
iter=0; err=1+tol; fk=zeros(n,1); fk1=fk; x=x0;
for i=1:n
fk(i)=eval(F(i,:)); end
while iter < nmax & err > tol
s=-Q \ fk;
x=s+x;
err=norm(s,inf);
if err > tol
for i=1:n, fk1(i)=eval(F(i,:)); end
Q=Q+1/(s’*s)*fk1*s’;
end
iter=iter+1;