1 Il nest guère difficile de trouver la solution de léquation linéaire a*x - b = 0 où a et b...

1

Il n’est guère difficile de trouver la solution de l’équation linéaire a*x - b = 0 où a et b sont connus et x est l’inconnue. On écrit a*x = b et chaque membre de l’expression est divisé par a:

a*x = b a\a*x = a\b x = a\b (division à gauche, mldivide(a, b) en Matlab)

x*a = b x*a/a = b/a x = b/a (division à droite, , mrdivide(a, b) en Matlab)

19

4

7

*

111

211

2113

19

42

72113

3

2

1

321

321

321

x

x

x

xxx

xxx

xxx

44.3

34.2

22.13

19

4

7

111

211

2113

\3

2

1

x

x

x

Que faire avec un système non-linéaire comme celui-ci:

Des méthodes adaptées doivent être mises en œuvre.

4)(

7)sin(11)log(32121

21

xxabsx

xx

Equations Non Linéaires Equations linéaires, non-linéaires

2

Trouver les « zéros » de fonctions non linéaires, les valeurs réelles telles que f()=0

Avantage: l’algorithme n’utilise que des évaluations

de la fonction f

Equations Non Linéaires Méthode de la bissection (dichotomie)

3

Cette méthode s’applique à des équations du type pour lesquelles on peut calculer ou estimer la dérivée de f : f’(x).

Soit x1 une valeur initiale approchée de la racine inconnue: = x1 + h, on aet comme

on en tire l’estimation de h la quantité à ajouter à x1 pour s’approcher de et générer une valeur x2 = x1 + h :

On en déduit la méthode:

Equations Non Linéaires Méthode de Newton

4

xn xn+1

f(x)

xn+2 x

Equations Non Linéaires Méthode de Newton, interprétation géométrique

5

x1 x2

x3

La méthode ne converge pas toujours vers la solution. Dans l’exemple ci-contre il existe un changement de concavité qui amène à une oscillation des termes xn

Equations Non Linéaires Méthode de Newton, convergence, arrêt

f(x)

x

6

|f ’(x)| >> 1 (à gauche) critère trop restrictif: alors que l’erreur est faible, les itérations se poursuivent puisque le résidu est grand.

|f ’(x)| << 1 (à droite) critère trop faible: ici le résidu est faible et conduit à l’arrêt des itérations alors que l’erreur est grande.

On utilisera donc préférentiellement le contrôle sur l’incrément.

résidu

résidu

Equations Non Linéaires Méthode de Newton: contrôle sur le résidu

e(k) = erreur = |x(k) - |résidu = f(x(k))

7

La méthode Newton peut s’appliquer à la résolution d’un système de plusieurs équations non linéaires :

A partir d’un couple de valeurs approchées (x1, y1) d’une solution (, ) du système, on peut déterminer deux accroissements h et k à donner à x1 et y1 de manière à ce que :

En développant en 1er ordre,il vient :

Equations Non Linéaires Méthode de Newton: systèmes d’équations non linéaires

8

Les quantités h et k s’obtiennent donc, en résolvant le système linéaire suivant :

Sous forme matricielle, en posant J la matrice Jacobienne:

),(

),(

11

11

),( 11 yxg

yxf

k

hJ

yx

),(

),(\

11

11

),(1

1

2

2

11 yxg

yxfJ

y

x

y

xyx

Généralisation:

),(

),(\

),(1

1

nn

nn

yxn

n

n

n

yxg

yxfJ

y

x

y

xnn

On peut noter de façon condensée (vectorielle): )(\1 nnnn

ufJuuu

J(x1, y1) =

Equations Non Linéaires Méthode de Newton: systèmes d’équations non linéaires

9

R R

On veut : f(x+h)=f(x) + h.f’(x) = 0 h = - f(x) / f’(x)

À partir de x1, on calcule x2=x1+h1, puis x3, …

Rn Rn

0

);;(

);;(

);;(

)(

3

2

1

zyxf

zyxf

zyxf

z

y

x

FXF

Equations Non Linéaires Méthode de Newton: résumé

Equations Non Linéaires fzero, poignée de fonction

La fonction fzero résout les équations non-linéaires du type : mafonction(x) = 0. Elle possède 2 entrées: a) une poignée* de la fonction dont on recherche le zéro et b) une valeur x0 initiale supposée proche du zéro de la fonction. Sa sortie est la valeur x= qui annule mafonction. >> fzero('cos', 2) % ou écrire: fzero(@cos, 2)ans = 1.5708

On peut évidemment affecter la sortie à une nouvelle variable:>> un_zero_de_cos = fzero(@cos, 2) % ceci résout: cos(x)=0un_zero_de_cos = 1.5708

Essayons avec ma fonction >> u=fzero(@mafonction, 2)u = 1>> u=fzero(@mafonction, -10)u = -1.0000 % ces 2 dernières commandes résolvent: x.^2-1 = 0

* Une poignée est un type de variable désignant les fonctions. Elle est construite en ajoutant un ‘@’ davant le nom de la fonction, ou en la créant comme une fonction anonyme.

function y=mafonction(x)y=x.^2-1;end

Equations Non Linéaires fzero, fonctions paramétrées

Les choses peuvent se compliquer si la fonction cible est paramétrée, et possède donc plus d’une entrée comme dans la version ci-contre:

function y=mafonction(p, x)y = x.*cos(x)+p;end

Une façon d’utiliser fzero (qui n’accepte que des fonction à une seule entrée) est de créer une fonction anonyme en fixant d’abord la valeur du paramètre:>> p = 5;>> mafonction2 = @(x) mafonction(p, x); % mafonction2 possède une seule entrée>> ezplot(mafonction2, [-10, 2])>> grid>> fzero(mafonction2, -5)ans = -5.3125>> fzero(mafonction2, 0)ans = 3.0217

-10 -8 -6 -4 -2 0 2

0

5

10

x

mafonction(p,x)

Equations Non Linéaires fzero, options, optimset

En réalité, fzero peut posséder 2 ou 3 entrées:>> x = fzero(fun, x0, options)où options est une entrée qui va permettre, par exemple d’indiquer avec quelle tolérance la recherche du zéro doit être réalisée.

Pour connaitre les options disponibles avec fzero, on utilise la commande optimset. On voit que par défaut, fzero recherche le zéro d’une fonction jusqu’à une tolérance égale à eps(1).

>> options = optimset(@fzero)options = Display: 'notify' MaxFunEvals: [] MaxIter: [] TolFun: [] TolX: 2.2204e-016

…

Pour changer la valeur de l’option ‘param’, il faut utiliser la syntaxe suivante pour optimset:options = optimset(old_options, ‘param', new_value)Ainsi, pour changer le critère d’arrêt, on écrira:>> new_opt = optimset(options, 'tolx', 1e-6)On pourra par la suite exécuter fzero avec les nouvelles options qu’on lui passera:>> x = fzero(fun, x0, new_opt )

new_opt = Display: 'notify' MaxFunEvals: [] MaxIter: [] TolFun: [] TolX: 1.0000e-006 …

Equations Non Linéaires Exercice: erreur de la méthode de dichotomie

En observant que l’erreur est bornée:

Etablir

le nombre d’itérations minimal qui garantisse:où est une tolérance donnée.

14

On considère le dioxyde de carbone (CO2), pour lequel a=0.401 Pa.m6 et b=42.7 10-6 m3. Donner le volume occupé par N=1000 molécules de CO2 à la température T=300 K et à la pression p=3.5 107 Pa et avec une tolérance de 10-9. On donne k=1.38 10-23 Joule.K-1.

Equations Non Linéaires Exercice: Volume d’un gaz réel

Equations Non Linéaires Exercice: matrice jacobienne

Soit la fonction F de R2 R2:

Calculer l’expression de sa matrice jacobienne JF (X). En déduire JF([1; 2]).

La fonction jacobimatrice ci-contre évalue numériquement la matrice jacobienne d’une fonction fun. Etudier chaque ligne de cette fonction. Appliquer la à la fonction F définie au-dessus et vérifier le résultat obtenu pour JF([1; 2]).Pourquoi a t’il été ajouté « eps » dans la définition de dx ?

function [J, y0]=jacobimatrice(fun, x0)% Jacobimatrice calcule la matrice jacobienne J de la% fonction fun évaluée au point x0.% y0 = fun(x0). % fun est une poignée de fonction.% Exemple pour une fonction R^3 ==> R^2:% >> f=@(x) [x(1)*x(2)^2+x(3); x(1)*x(3)^2-x(2)];% >> x0 = [1, 2, 3];% [J, y0]=jacobimatrice(f, x0)% J =% 4 4 1% 9 -1 6% y0 =% 7% 7y0 = fun(x0);n = length(x0); m = length(y0);J = zeros(m, n);dx = x0/1000 + eps; for k=1:n x0p=x0; x0m=x0; x0p(k)=x0p(k)+dx(k); x0m(k)=x0m(k)-dx(k); J(:,k)=(fun(x0p)-fun(x0m))/2/dx(k); endend

16

Copier, tester et débugger la fonction NEWTON donnée ici. Elle fait appel à la fonction jacobimatrice étudiée plus haut dans ce chapitre.

Equations Non Linéaires Exercice: écrire une fonction newtonfunction [x, niter]=newton(f, x0, tolx, maxiter)% trouve la solution par la méthode de Newton% d’un système d’équations non-linéaires pouvant % se mettre sous la forme% f(x)=0 où f est une fonction de R^n dans R^n % X = valeur telle que f(X) = 0 à TOLX prés % NITER = nombre d'itérations effectuées %% F = poignée de la fonction % X0 = valeur initiale des itérations % TOLX = tolérance sur l'incrément: % si norm(x(k+1)-x(k))< tolx alors arrêt% MAXITER = nombre maximal d'itérations à effectuer %% exemple dans R^1:% f=@(x) sin(2*x) -1 + x;% [x, niter]=newton(f, 0.5, 1e-8, 100)% x = % 0.3523% niter =% 4%% exemple dans R^3% f=@(x)[x(1)+x(2)^2+x(3);x(1)+x(3)^2-x(2); sum(x)];% x0 = [1; 2; 3];% [x, niter]=newton(f, x0, 1e-8, 100)% x =% -3.0000% 1.0000% 2.0000% niter =% 6

x0=x0(:);continuer=true;niter=0; while continuer xold=x; J=jacobimatrice(f, xold); x=xold-J\f(xold); niter=niter+1; if niter>maxiter, continuer=false; end if norm(x-xold)<tolx, continuer=false; end end end

x0=x0(:);continuer=true;niter=0; while continuer xold=x; J=jacobimatrice(f, xold); x=xold-J\f(xold); niter=niter+1; if niter>maxiter, continuer=false; end if norm(x-xold)<tolx, continuer=false; end end end

Equations Non Linéaires Exercice: modifier une fonction newtonfunction [x, niter]=newton(f, x0, tolx, maxiter)% trouve la solution par la méthode de Newton% d’un système d’équations non-linéaires pouvant % se mettre sous la forme% f(x)=0 où f est une fonction de R^n dans R^n % X = valeur telle que f(X) = 0 à TOLX prés % NITER = nombre d'itérations effectuées %% F = poignée de la fonction % X0 = valeur initiale des itérations % TOLX = tolérance sur l'incrément: % si norm(x(k+1)-x(k))< tolx alors arrêt% MAXITER = nombre maximal d'itérations à effectuer %% exemple dans R^1:% f=@(x) sin(2*x) -1 + x;% [x, niter]=newton(f, 0.5, 1e-8, 100)% x = % 0.3523% niter =% 4%% exemple dans R^3% f=@(x)[x(1)+x(2)^2+x(3);x(1)+x(3)^2-x(2); sum(x)];% x0 = [1; 2; 3];% [x, niter]=newton(f, x0, 1e-8, 100)% x =% -3.0000% 1.0000% 2.0000% niter =% 6

Suite du fichier

• Modifier la fonction newton ci-contre de façon à ce quelle renvoie le vecteur x =[x0, x1, ..., xn] des itérations successives et où x0 est la valeur initiale et xn est la solution à tolx prés.• newton peut-elle résoudre x^3-1=0 ? (voir http://fr.wikipedia.org/wiki/Fractale_de_Newton)

18

Objectif: résoudre le système ci-contre, avec la méthode de Newton. On prendra tolx=10-12

Soit f1(x, y) = x2 – 2xy – 2 = 0f2(x, y) = x + y2 + 1 = 0

Selon la valeur initiale donnée à l’algorithme itératif, la convergence vers la solution peut échouer. De même, on ne sait pas si il existe zéro, une ou plusieurs solutions. Une approche graphique est possible pour les systèmes à 2 variables.

a) Représenter la surface z(x,y)=f12(x,y) +f2

2(x,y) en utilisant les fonctions meshgrid et surf. Pourquoi est-il plus efficace de représenter z=log10(f1

2(x,y) +f22(x,y)) ? En

déduire une estimation de la ou des solutions.

b) Appliquer la méthode de Newton avec cette ou ces estimations comme valeur(s) initiale(s).

1yx

2xy2x2

2

{

Equations Non Linéaires Exercice: Recherche d’une valeur initiale

19

a) Résoudre le système ci-dessous, avec la méthode de Newton. On prendra tolx=10-6.2x1 - x2 = exp(-x1)-x1 + 2x2 = exp(-x2)

b) Trouver la matrice X telle que X * X * X =

Sol: X =

43

21

161.1290.1

860.0129.0

Equations Non Linéaires Exercice: applications pour la fonction newton.m