Commentaires des différentes méthodes

hello, ma proposition est de répertorié dans ce topic les critiques et commentaires des différents méthodes utilisées dans les exercices de calcul num. par exemple comme Magali l'a fait précédemment pour les méthodes de convergences du pt fixe et de newton:
la méthode du point fixe est vraiment nulle (puisqu il faut toujours tester des coefficients au hasard) et que si on veut trouver une racine, il vaut mieux utiliser Newton sans hésitations (converge toujours et plus rapide...).

enfin voila je pense que ce genre de commentaires peut être utiles afin que l'on puisse déterminer quelles méthodes est la meilleure pour un type d'exercice.

merci d'avance d'y prêter attention.
GAB

Bon en regardant dans mes notes du cours théorique, voila ce que j'en retire en ce qui concerne la comparaison entre point fixe et Newton. C'est dit en toute généralité, et ça peut sembler bizarre par rapport a ce qu'on a vu aux TPs mais bon voila ^^

L'avantage de la méthode du point fixe par rapport à celle de Newton est qu'il ne faut pas, sauf cas particulier, calculer de dérivée. En effet il peut être difficile pour certaines fonctions de calculer la dérivée (dixit le cours théorique, je sais que les fonctions vues aux TPs étaient tout à fait dérivable)

Il y a parfois un problème lors de l'utilisation de cette méthode, qui implique de devoir utiliser un K. Ce K n'est pas, comme j'ai pu le lire dans un autre post, choisi au hasard!! Je vais essayer d'illustrer ce problème en reprenant l'exemple qui a été donné au cours théorique.

% Méthode du point fixe
% Exemple vu au cours théorique

clear
clc
F = inline ('4*sin(x)+x-1'); % fonction donnée
x = -5 : 0.01 : 5 ;
f = F(x);
plot(x,f)
grid on

% en zoomant sur le plot on peut observer 3 zéros :
% en a peu près 0.201 , 3.983 et 4.917

%appliquons maintenant la méthode du point fixe

g = inline ('1-4*sin(x)');
%en effet si F(x)=4*sin(x)+x-1=0, alors g(x)=x=1-4*sin(x)
x0=0.201;
for n=1:60
xn=g(x0);
x0=xn;
end
x0 % affiche la dernière valeur de l'approximation

% ça converge vers 4.917, un autre des zéros, et pas vers 0.201 !!!
% PROBLEME!!!

gprime = inline ('-4*cos(x)');
display ('La dérivée de g au voisinage du zéro vaut')
gprime(0.201)

% il faut que la dérivée de g, gprime, soit < 1 en valeur absolue autour du
% zéro recherché, autrement dit |gprime(xO)| < 1
% pour cela on doit introduire un K !

Vous pouvez vérifiez en copiant tout ca dans l'éditeur de matlab et en faisant tourner le programme.

Il faut donc trouver une valeur de K!
Pour ce faire, on repart de l'algorithme de base du point fixe.

Si F(x) = 0 est la solution recherchée,
x = x + F(x) a les mêmes annulations, avec g(x) = x + F(x)
ou encore

x = x + K.F(x) , avec K différent de zéro

g(x) devient x + K.F(x)

comme dit plus haut, le problème vient du fait que |g'(x)|>1 autour du zéro recherché.
il faut que |g'(x)|< 1

on dérive notre nouveau g(x)

g'(x)= 1 + K.F'(x)
il faut donc que |1+K.F'(x)|<1 autour du zéro recherché

et c'est comme ça qu'on détermine K !

toujours dans le cours théorique, le prof dit qu'on peut trouver un K qui convient en résolvant 1+K.F'(x)=0 autour du zéro recherché (ici 0.201)
c-a-d 1+K(4cos(0.201)+1)=0
ce qui donne K = -1/(4cos(0.201)+1) = -0.2

% méthode du point fixe
% détermination de K

clc
clear

% il faut que |g'(x)|<1 autour du zéro recherché, ici 0.201
% le K déterminé vaut -0.2
% on vérifie si désormais |g'(x)| < 1

gprime = inline ('1-0.2*(4*cos(x)+1)');
gprime (0.201)

% ok c'est bon !
% g(x) devient donc x + K.F(x)

g = inline ('x-0.2*(4*sin(x)+x-1)');
x0=0.201;
for n=1:60
xn=g(x0);
x0=xn;
end
x0 % affiche la dernière valeur de l'approximation, qui est désormais la bonne !!

et voila on y est finalement arrivé ! Et on a pas choisi K "au hasard". Désolé j'espère que j'ai embrouillé personne, moi j'ai eu du mal a comprendre mais en s'acharnant un peu on y arrive ^^. Je voulais juste montrer que K était pas déterminé au hasard et que bref valait mieux pas dire ça à l'examen ....

Pour finir de comparer point fixe et newton,

Point fixe: pas de calcul de dérivée nécessaire en principe (seul vague avantage de la méthode), mais bon parfois il faut quand même pour pouvoir déterminer un K quand ça marche pas (je vais plus m'étendre la dessus )

Newton: faut calculer une dérivée, mais converge de manière quadratique donc bcp plus rapide que pt fixe SAUF si on recherche une racine multiple. Dans ce cas l'algorithme converge de façon linéaire (comme pour le point fixe), mais on peut corriger l'algorithme avec un facteur M.

x(n+1) = x(n) - M. F(x(n)) / F'(x(n)) , avec M = 2 si racine double ou M = 3 si racine triple.

Pour les racines multiples , je crois que la dichotomie est la meilleure solution.

Et pour la comparaison point fixe/ Newton, rien à ajouter.

Par contre pour comparer les Euler et Heun, a part dire que Euler explicite est beaucoup plus simple mais qu'il y a des problèmes de stabilité dans certains cas qui n'existent pas pour l'implicite qui est toujours stable... je ne vois pas comment caractériser la précision de ces méthodes ... je suppose que plus les pas sont petits plus c'est précis mais c'est un peu vague comme réponse...

moi dans mes notes j'ai que euler explicite devient très 'instable' pour une valeur de pas trop petite. C'est la seule raison pour laquelle je pense qu'on pourrait préférer l'implicite à l'explicite.

Maintenant en ce qui concerne Heun (aka Runge-Kutta à deux paramètres), ben c'est une sorte de mix explicite-implicite, sauf que pour la partie implicite on n'utilise pas newton mais 'une grossière estimation de y(n)'. C'est peut-être ça qui le rend éventuellement plus rapide que l'implicite, vu qu'on utilise pas de dérivée

à confimer

Pour Heun, j'en sais strictement rien...mais c'est peut être ça !

Par contre pour Euler explicite, c'est l'inverse je pense... La méthode peut être instable mais pour des pas trop grands. La manière de la rendre stable c'est de diminuer le pas mais parfois il faut trop le diminuer, les calculs prennent trop de temps et la méthode n'est alors plus efficace.
Et comme tu dis, quand explicite est instable, alors on préfère implicite.

Thomas a écrit:

% il faut que la dérivée de g, gprime, soit < 1 en valeur absolue autour du
% zéro recherché, autrement dit |gprime(xO)| < 1
% pour cela on doit introduire un K !

[/quote]


NOTE De COURS
Pour améliorer la situation et augmenter la vitesse de convergence de l’algorithme, il suffit de choisir une fonction d’itération dont la dérivée est nulle, ou presque, au point solution. Rechercher une solution de f(x) = 0 est équivalent à rechercher une solution de x = x + f(x) ou encore de x = x + L. f(x), pour autant que L soit non nul. Cette façon de réorganiser le calcul nous permet de choisir une fonction d’itération dont le module de la dérivée sera quasiment nul au voisinage de la solution. En effet, nous avons g’(x) = 1 + L. f’(x) et si nous choisissons L = -1/f’(r).......

je pense que le K que t' a introduit c' est pour augmenter la vitesse, quand on n' a un truc qui diverge il faut changer de g(x) et réessayer je sait pas si je me trompe quelqu'un peut confirmer ou infirmer ?

Merci

non , si t'as bien suivi mon raisonnement, voire que t'as rentré les algorithmes que j'ai mis en 'citation', tu verras que le K que j'ai rentré c'est juste pour que la méthode fonctionne correctement. Et en effet, si tu as bien lu, tu verras que j'ai déterminé le K en égalant l'équation avec zéro (K ou L peut importe).
J'avoue que c'est pas over clair, mais j'ai vérifié mes calculs avec matlab et ça fonctionne (encore heureux vu que c'est tiré de mes notes du cours théorique ...)

Pour les problèmes aux conditions limites, je sais qu'on ne peut pas utiliser la méthode du "système tridiagonal" si le problème au conditions limites en question est non linéaire. Mais si le système est linéaire (y, y' et y'' dans des termes séparés), quel est le critère de choix?