Recherche de zéros: Méthode du point fixe

[Rockleader]

Bonjour, je pense avoir désormais assimilé toutes les notions de mon cours, à l'exception de celle ci.

Pourriez vous m'expliquer ce qu'est la méthode de point fixe ?


Par exemple j'ai un exo qui m'a fait montrer que

l'équation x^3+x=1000 possédait une unique solution noté r dans [9;10]

Je suis censé utiliser la méthode de point fixe pour trouver une approximation de r. En indication, Il faut pour cela mettre l'équation sous la forme g(x)=x


Merci à vous

[Doraki]

Tu n'as aucune idée pour trouver une fonction g telle que g(x)=x <=> x^3+x = 1000 ?

[Rockleader]

Tu n'as aucune idée pour trouver une fonction g telle que g(x)=x x^3+x = 1000 ?

Ce n'est pas tellement que je n'ai pas d'idée c'est que je n'ai pas compris ce qu'il faut faire, à partir de là peut être que le comment le faire me semblera plus clair maiss pour le moment non désolé je n'en ai aucune idée.

[Doraki]

Est-ce que tu sais ce qu'est "la méthode du point fixe" ?

[Rockleader]

Ben non justement =)

C'est pour ça que je voulais avoir un exemple sur cet exo avant mon partiel ;)

ça doit pas être bien compliqué à comprendre. Il me semble que cela à un rapport avec des dérivés successives mais je n'ai pas trouvé d'exemples clair ni sur le net, ni dans mon cours vu que j'ai été absent le jour où on a abordé ça ;)

[Sylviel]

Il y a plusieurs idées qui tourne autour des méthodes de point fixe. Mais fondamentalement je te laisse montrer la chose suivante :
soit une fonction f de R dans R, strictement contractante (i.e. k-lipschtiz avec k<1).
1) Montrer qu'elle admet un unique point fixe.
2) montrer que la suite récurrente x_{n+1}=f(x_n) converge vers le point fixe.

Et vàlà la méthode de point fixe ^^

[Doraki]

La méthode du point fixe c'est de calculer un point fixe en itérant une fonction contractante :

Soit I un intervalle de R, f une fonction de I dans I, u0 un élément de I,
on suppose f contractante (il existe u tel que 0 < k < 1 et pour tout x,y de I, |f(x)-f(y)| <= k|x-y|)
Alors f a un unique point fixe, et la suite définie par u(n+1) = f(un) converge vers ce point fixe.

Donc ici le premier truc à faire c'est chercher une fonction g telle que g(x) = x <=> l'équation de départ est vérifiée.

[Cliffe]

Voila l'algo :

Code: Tout sélectionner

Choisir g; Choisir x0;
x := x0; n := 0;
[U][B]Tant que[/B][/U] le test d'arrêt n'est pas satisfait [U][B]faire[/B][/U]
    x := g(x); n := n + 1;
   mettre à jour le critère d'arrêt.
[U][B]Fait[/B][/U]
[U][B]retourner[/B][/U] n, x;


Exemple de critères d'arrêt :
- précision :
- nombre max d'ittérations atteint :
- on diverge :

[Rockleader]

La méthode de point fixe revient donc à trouver une fonction assimilable à la suite qui converge vers notre point fixe r ?


dire point fixe unique c'est pas un peu un pléonasme ? Parce que un point fixe est forcement unique non ? M'enfin ça c'est une autres question =)


En ce qui concerne l'application directe je ne vois toujours pas comment faire ! J'ai bien entendu les hypothèses de départs qu'il faut prendre pour utiliser la méthode, mais je ne saurais toujours pas l'utiliser !

[Doraki]

La méthode de point fixe revient donc à trouver une fonction assimilable à la suite qui converge vers notre point fixe r ?

La méthode du point fixe est une méthode pour calculer le point fixe d'une fonction.
Toi dans ton exo tu veux calculer la solution d'une équation (x^3+x=1000)

Donc tu dois chercher une fonction g telle que être un point fixe de g soit la même chose que être solutio de l'équation.
Ensuite tu essayes d'appliquer la méthode à g et si ça marche tu obtiens son point fixe, donc la solution de l'équation.

Parce que un point fixe est forcement unique non ?

non, la fonction x -> x a plein de points fixes.

[Rockleader]

Si je dois chercher une fonction g; pourquoi me dit on d'emblée de prendre g(x)=x

Qui plus est, si j'en crois tes dires, g(x)=x admet une infinité de point fixe et non pas un seul comme la solution de l'équation que l'on cherche.


Pourriez vous me donner la solution sur cet exemple ? Ou sur un autre exemple de votre choix si vous préférez, dans l’immédiat je cherche à visualiser comment ça se passe pour être capable d'appliquer ça dans mon partiel cet aprèm si jamais ça tombe.

[Doraki]

On t'a jamais dit de prendre d'emblée g(x) = x o_O

on t'a dit (je recopie) de mettre l'équation sous la forme g(x) = x où g est une certaine fonction de ton choix. C'est-à-dire (je me répète) de trouver une fonction g telle que l'équation équivaut à g(x)=x.

Si tu prends g(x) = x ça ne marche pas puisque x^3+x = 1000 n'est pas équivalent à x = x

Si tu prends g(x) = x²-cos(x) ça ne marche pas non plus puisque x^3+x = 1000 n'est pas équivalent à x²-cos(x) = x

[Rockleader]

Ok je comprends un peu mieux alors !!!


Mais comment déterminer cette fonction g du coup.


On pourrait en faire beaucoup sans trouver par exemple

G(1)=1^3+1 - 1000 = -998 ce qui est différent de 1 On sait donc ici que x^3 +x -1000 n'est pas la fonction que l'on recherche.

Mais ça ne me dit toujours pas comment j'arrive à trouver celle que je cherche ;)

Désolé si je suis long à la détente^^

[Doraki]

G(1)=1^3+1 - 1000 = -998 ce qui est différent de 1 On sait donc ici que x^3 +x -1000 n'est pas la fonction que l'on recherche.

Tu dis n'importe quoi.
on veut avoir x^3+x=1000 g(x) = x, donc en x=1 ça donne 2=1000 g(1) = 1. Or 2 n'est pas 1000 donc il ne faut pas prendre g(1)=1. C'est tout ce qu'on peut dire à propos de g(1)

g(x) = x^3+x-1000 ne marche pas puisque x^3+x=1000 n'est pas équivalent à x^3+x-1000 = x.

Mais ça ne me dit toujours pas comment j'arrive à trouver celle que je cherche

admire :

x^3+x = 1000
x = 1000-x^3 (j'ai soustrait x^3 des deux cotés)
1000-x^3 = x
donc on peut (il y a d'autres solutions) commencer par prendre g(x) = 1000-x^3.

[Rockleader]

Désolé, je n'ai pas [...] en fait je vois pas comment excuser un tel manque de logique, j'aurais du le voir ça parait évident vu sous cet angle. Je cherchais quelque chose de plus compliqué que ça à faire et je me suis perdu en route.

Si j'ai bien compris pour conclure tout ça, le point fixe r que l'on recherche ce sera bien le x tel que
x = 1000 -x^3 avec x compris entre 9 et 10.

A partir de ce moment pour le trouver c'est en tatonant par petit intervalle jusqu'à ce que l'on obtienne la précision recherchée je suppose ?

[Doraki]

Ben là il faudrait vérifier qu'on ait une chance pour d'avoir g contractante autour du point fixe.

Comme g est C1, g est contractante sur un segment <=> |g'| < 1 sur le segment.
Donc une fois qu'on a choisi g, le 2ème truc à faire est de voir si |g'(r)| < 1 ou pas.

Ici on ne connait pas la valeur de r, on sais juste qu'il est dans [9;10], donc il faut calculer g' sur cet intervalle.

[Rockleader]

Mince, je croyais que pour être contractante il suffisait que sur l'intervalle |g| < 1

Mais d'après ce que tu écris il faut vérifier que |g'| < 1



Dans tous les cas merci, vous m'avez enlever une sacré épine du pied en m'expliquant cette notion !

[Doraki]

Si jamais tu trouves que |g'(r)| > 1, alors comme g est bijective (ici sur R, mais en général au moins autour de r) tu peux remplacer g par sa fonction réciproque g-1
en effet on a g(x) = x <=> g-1(g(x)) = g-1(x) <=> x = g-1(x) <=> l'équation de départ est vérifiée,

et g-1'(r) * g'(r) = 1 (on dérive g-1(g(x)) = x en x=r)
Donc si |g'(r)| > 1 on obtient |g-1'(r)| < 1.

Ensuite si tu as une fonction telle que |g'| < 1 sur [9;10] alors [9;10] sera obligatoirement stable par g et g y est contractante donc t'as fini.