Méthode de Müller

[evariste_G]

Bonjour.

J'ai créé un tableur afin de me donner les termes consécutifs de la suite engendrée par la méthode de Müller pour obtenir la valeur de la solution de l'équation $e^{-x}-\sqrt{x}=0$.

Le fichier est ici : http://agnus.dei.free.fr/muller.ods (format open office)

Le problème est que la suite diverge, ce qui n'est pas normal ... et j'ai beau regarder partout, je ne vois pas l'erreur ... Quelqu'un aurait-il une idée ?

[kojak]

bonjour,

T'as pas plus simple comme méthode

[evariste_G]

:D Cette méthode est compliquée, mais en théorie ultra performante ... Et puis, même s'il existe d'autres techniques, je suis du genre obstiné et comme je n'arrive pas à comprendre où est mon erreur, ça commence à m'agacer ...

[MB]

Tu as tenté avec un logiciel de calcul numérique ? (car là c'est un peu indigeste à vérifier les formules)

[OG]

:D Cette méthode est compliquée, mais en théorie ultra performante ... Et puis, même s'il existe d'autres techniques, je suis du genre obstiné et comme je n'arrive pas à comprendre où est mon erreur, ça commence à m'agacer ...

ultra performante ? l'ordre est un peu moins que 2 : 1.84 et des brouettes.
Par contre l'intérêt est d'obtenir des racines complexes même si on part avec une initialisation réelle.

O.G.

[evariste_G]

:D Cette méthode est compliquée, mais en théorie ultra performante ... Et puis, même s'il existe d'autres techniques, je suis du genre obstiné et comme je n'arrive pas à comprendre où est mon erreur, ça commence à m'agacer ...

ultra performante ? l'ordre est un peu moins que 2 : 1.84 et des brouettes.
Par contre l'intérêt est d'obtenir des racines complexes même si on part avec une initialisation réelle.

J'ai un peu exagéré oui :D disons que je n'ai pas eu beaucoup de choses sur cette méthode. J'avais cru voir des choses sur les racines complexes oui, mais dans la pratique, j'avoue que ce n'est pas évident (avec un tableur) d'arriver à ses fins ...

Je n'ai pas de logiciel de calculs formels ... donc je ne peux rien proposer d'autre qu'un tableur ...

[OG]

il y a toujours Scilab pour le numérique ou maxima pour le formel.

Comme la méthode est d'ordre presque 2, avec Scilab on fait 4, 5 itérations pas plus. L'idéal serait d'observer avec Maple ou Maxima en précisant 20, 30
chiffres après la virgule.

Pour l'ordre j'ai lu cela dans Quarteroni, Sacco et Saleri. Ils donnent la référence à Hildebrandt 1987. Je n'ai pas d'idée sur la preuve. Peut-être que cela ressemble à celle pour la méthode de la sécante (en plus compliquée)?

Il y a aussi la méthode de Dekker-Brent (un peu moins compliquée que Muller).

O.G.

[evariste_G]

Merci. Je regarderai ça un jour, quand j'aurai plus de temps, sur Matlab (quand je l'aurai téléchargé et dompté un minimum ...).

[OG]

Re

j'ai programmé la méthode sous Scilab, vite fait :

Code : Tout sélectionner

function [s]=muller(f,a,b,c,N)
  x0=a
  x1=b
  x2=c
  for i=1:N
    f1=(f(x2)-f(x1))/(x2-x1)
    f2=(f(x2)-f(x0))/(x2-x0)
    f3=(f(x0)-f(x1))/(x0-x1)
    w=f1+f2-f3
    xx=x2-2*f(x2)/max(w+(w^2-4*f(x2)*(f2-f3)/(x2-x1))^.5,w-(w^2-4*f(x2)*(f2-f3)/(x2-x1))^.5)
    x0=x1
    x1=x2
    x2=xx
  end
  s=x2
endfunction

Avec les mêmes données ça diverge.
Par contre si je prends $f(x)=x^3-5$ j'obtiens le résultat attendu et avec $\exp(x)-.5$ aussi.
Je n'ai pas vu de conditions pour que cela converge (il doit y en avoir), visiblement tu es tombé sur le bon exemple !

O.G.

[OG]

je continue... Comme c'est une méthode à 3 points qui consistent à calculer pour le $k+1$ point la racine du polynôme (degré 2) qui passe par les 3 points. Pour approfondir ton exemple il faudrait se farcir le tracé du dit polynôme pour $n=1$, observer, etc ...

O.G.

[OG]

je continue (tout seul), je suis aussi du genre obstiné. Ce midi je me suis dit que le pb venait peut-être du max. En effet il faut maximiser le dénominateur mais en valeur absolue pas un simple max. Je testerai quand j'aurai le temps.
Avis aux amateurs !

O.G.

[OG]

Histoire de conclure, mon intuition du midi était juste, hier soir je me suis fait avoir comme un débutant.

Je confirme donc : il faut choisir celui de plus grande valeur absolue (et dans le cas où il y a des complexes de plus grand module). Et là, of course, pour la fonction de evariste_G, ça marche : muller(f,0.3,0.4,.5,3) me donne 0.4263028 . Comme d'habitude on peut optimiser le programme (c'est du --vite fait-- Scilab pas du OpenOffice.org)

Code : Tout sélectionner

unction [s]=muller(f,a,b,c,N)
  x0=a
  x1=b
  x2=c
  for i=1:N
    f1=(f(x2)-f(x1))/(x2-x1)
    f2=(f(x2)-f(x0))/(x2-x0)
    f3=(f(x0)-f(x1))/(x0-x1)
    w=f1+f2-f3
    v1=w+(w^2-4*f(x2)*(f2-f3)/(x2-x1))^.5
    v2=w-(w^2-4*f(x2)*(f2-f3)/(x2-x1))^.5
    v3=max(abs(v1),abs(v2))
    v4=(w>=0)*v3-(w<0)*v3
    xx=x2-2*f(x2)/v4
    x0=x1
    x1=x2
    x2=xx
  end
  s=x2
endfunction

Bonne soirée
O.G.

[evariste_G]

Bien sûr ! Je suis bête de ne pas y avoir pensé, surtout que je me suis dit, quand j'ai vu cette méthode : "Mais comment est-ce possible avec les complexes de calculer le max alors qu'il n'y a pas de relation d'ordre ?" J'aurais dû y penser ! Merci

[OG]

un dernier message pour le plaisir.

De rien mais je me suis fait avoir aussi.
Pour l'ordre de convergence, je n'ai pas le livre en question sous les yeux. Le plus difficile doit être de montrer que ça converge pour $f$ très régulière
+ zéro simple à coup de epsilon et Taylor-Truc.

Pour l'ordre il suffit d'écrire l'erreur d'interpolation pour le polynôme de Lagrange et on doit obtenir que cet ordre de convergence est racine de $x^3-x^2-x-1$ (et en montrant aussi que cet ordre est $\geq 1.1$ pour ne pas tomber sur la racine 1.003 !)

O.G.

[Framboise]

Bonjour,

Pour info:
Numerical Mathematics 2d ed.
By Alfio Quarteroni, Riccardo Sacco, Fausto Saleri

http://www.amazon.com/Numerical-Mathema ... 3540346589

page 269 Müller method.
pae 271:
Program 54 - mulldefl : Muller’s method with refinement

Les programmes ne sont plus dispo à l'adresse donnée dans le livre:
http://www1.mate.polimi.it/˜calnum/programs.html

Auteur:
http://iacs.epfl.ch/cmcs/AQ/public.htm