246
6 R´ esolution des ´ equations et des syst` emes non lin´ eaires
6.7.2 M´ ethodes de Newton modifi´ ees
Plusieurs modifications de la m´ ethode de Newton ont ´ et´ e propos´ ees pour r´ eduire son coˆ ut quand on est assez proche de x
∗ .
1. Mise `
a jour cyclique de la matrice jacobienne
Une alternative efficace ` a la m´ ethode (6.42) consiste ` a garder la matrice jacobienne (ou plus pr´ ecis´ ement sa factorisation) inchang´ ee pendant un certain
nombre p ≥ 2 d’´ etapes. En g´ en´ eral, la d´ et´ erioration de la vitesse de convergence s’accompagne d’un gain en efficacit´ e de calcul.
On a impl´ ement´ e dans le Programme 53 la m´ ethode de Newton dans le
cas o` u la factorisation LU de la matrice Jacobienne est mise ` a jour toutes les
p it´ erations. Les programmes utilis´ es pour r´ esoudre les syst` emes triangulaires
ont ´ et´ e d´ ecrits au Chapitre 3.
Ici, et dans les programmes qui suivent, x0 d´ esigne le vecteur initial, F
et J les expressions fonctionnelles de F et de sa matrice jacobienne J F . Les
param` etres tol et nmax repr´ esentent la tol´ erance pour le crit` ere d’arrˆ et et le
nombre maximum d’it´ erations. En sortie, le vecteur x contient l’approximation
du z´ ero de F, et iter le nombre d’it´ erations effectu´ ees.
Programme 53 - newtonsys : M´ ethode de Newton pour les syst` emes d’´ equations non lin´ eaires
function [x,iter]=newtonsys(F,J,x0,tol,nmax,p)
%NEWTONSYS M´ ethode de Newton pour les syst` emes non lin´ eaires
% [X, ITER] = NEWTONSYS(F, J, X0, TOL, NMAX, P) tente de r´ esoudre
% le syst` eme non lin´ eaire F(X)=0 avec la m´ ethode de Newton.
% F et J sont des chaˆ ınes contenant les expressions des ´ equations
% non lin´ eaires et de la matrice jacobienne. X0 est la donn´ ee initiale
% TOL est la tol´ erance de la m´ ethode. NMAX est le nombre maximum
% d’it´ erations. P est le nombre de pas cons´ ecutifs durant lesquels la
% jacobienne est fix´ ee. 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; Fxn=zeros(n,1); x=x0; err=tol+1;
for i=1:n
for j=1:n
Jxn(i,j)=eval(J((i-1)*n+j,:));
end
end
[L,U,P]=lu(Jxn);
step=0;
while err>tol
if step == p
step = 0;
6 R´ esolution des ´ equations et des syst` emes non lin´ eaires
6.7.2 M´ ethodes de Newton modifi´ ees
Plusieurs modifications de la m´ ethode de Newton ont ´ et´ e propos´ ees pour r´ eduire son coˆ ut quand on est assez proche de x
∗ .
1. Mise `
a jour cyclique de la matrice jacobienne
Une alternative efficace ` a la m´ ethode (6.42) consiste ` a garder la matrice jacobienne (ou plus pr´ ecis´ ement sa factorisation) inchang´ ee pendant un certain
nombre p ≥ 2 d’´ etapes. En g´ en´ eral, la d´ et´ erioration de la vitesse de convergence s’accompagne d’un gain en efficacit´ e de calcul.
On a impl´ ement´ e dans le Programme 53 la m´ ethode de Newton dans le
cas o` u la factorisation LU de la matrice Jacobienne est mise ` a jour toutes les
p it´ erations. Les programmes utilis´ es pour r´ esoudre les syst` emes triangulaires
ont ´ et´ e d´ ecrits au Chapitre 3.
Ici, et dans les programmes qui suivent, x0 d´ esigne le vecteur initial, F
et J les expressions fonctionnelles de F et de sa matrice jacobienne J F . Les
param` etres tol et nmax repr´ esentent la tol´ erance pour le crit` ere d’arrˆ et et le
nombre maximum d’it´ erations. En sortie, le vecteur x contient l’approximation
du z´ ero de F, et iter le nombre d’it´ erations effectu´ ees.
Programme 53 - newtonsys : M´ ethode de Newton pour les syst` emes d’´ equations non lin´ eaires
function [x,iter]=newtonsys(F,J,x0,tol,nmax,p)
%NEWTONSYS M´ ethode de Newton pour les syst` emes non lin´ eaires
% [X, ITER] = NEWTONSYS(F, J, X0, TOL, NMAX, P) tente de r´ esoudre
% le syst` eme non lin´ eaire F(X)=0 avec la m´ ethode de Newton.
% F et J sont des chaˆ ınes contenant les expressions des ´ equations
% non lin´ eaires et de la matrice jacobienne. X0 est la donn´ ee initiale
% TOL est la tol´ erance de la m´ ethode. NMAX est le nombre maximum
% d’it´ erations. P est le nombre de pas cons´ ecutifs durant lesquels la
% jacobienne est fix´ ee. 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; Fxn=zeros(n,1); x=x0; err=tol+1;
for i=1:n
for j=1:n
Jxn(i,j)=eval(J((i-1)*n+j,:));
end
end
[L,U,P]=lu(Jxn);
step=0;
while err>tol
if step == p
step = 0;