approximation de la solution de f(x)=0 avec Newton

Utilisation à l'épreuve de modélisation de l'agrégation de mathématiques

Modérateur : xcasadmin

Répondre
Denizou
Messages : 61
Inscription : mer. juin 13, 2012 7:23 am

approximation de la solution de f(x)=0 avec Newton

Message par Denizou » ven. févr. 15, 2013 5:10 pm

Bonjour,
j'ai écrit une procédure permettant de cherche la solution de f(x)=0 avec la méthode de Newton. Pour montrer que la méthode est quadratique, je calcule la précision obtenue à chaque étape. La solution a étant approchée avec fsolve.

Bizarrement,après 7/8 itérations j'obtiens 0 mais ensuite la suite est constante à a + 3.10^(-61) environ (7 itérations pour f(x)=x-exp(-x))

j'ai alors modifié la méthode de résolution, me disant que Xcas avait du procéder de même au calcul de a, ce qui expliquait ma solution "exacte" mais pas ma suite constante. J'ai testé les 5 méthodes.

1ère surprise : la solution "exacte" était obtenue par la méthode dichotomique et non celle de Newton comme je le pensais naïvement.
2nde surprise : Je ne peux pas obtenir plus de 60/80 décimales, c'est d'ailleurs l'ordre de grandeur de la différence entre chaque solution (j'imagine qu'il y a un lien !)

Merci

parisse
Messages : 5734
Inscription : mar. déc. 20, 2005 4:02 pm
Contact :

Re: approximation de la solution de f(x)=0 avec Newton

Message par parisse » ven. févr. 15, 2013 8:13 pm

Cela vient de la valeur de epsilon (config du cas), en effet fsolve se base là-dessus pour arrêter la suite récurrente (la méthode par défaut c'est Newton, avec préfacteur au début pour s'approcher de la racine). Donc avec un epsilon à 1e-12 par exemple, on a 2 itérées distantes de moins de 1e-12, par exemple à 1e-15, ce qui entraine que la 2ème est à environ 1e-30 de la racine, et juste après le test, xcas fait encore au moins une itération avec préfacteur 1, d'où la précision à 60 chiffres environ.
Si vous changez la valeur de epsilon à 1e-50 par exemple, vous aurez 200 chiffres sans problèmes. Mais le mieux c'est sans doute d'utiliser la fonction newton directement et de spécifier epsilon et le nombre max d'itérations (fixé à 20 par défaut).

Denizou
Messages : 61
Inscription : mer. juin 13, 2012 7:23 am

Re: approximation de la solution de f(x)=0 avec Newton

Message par Denizou » ven. févr. 15, 2013 10:16 pm

Merci pour la réponse
Je comprends bien pourquoi la suite devient constante.
Mais comment se fait-il que pour f(x)=x-exp(-x) ou f(x)=x-cos(x) j'obtienne exactement autour de 7ème itération la valeur renvoyée par la méthode bisection_solver ?

parisse
Messages : 5734
Inscription : mar. déc. 20, 2005 4:02 pm
Contact :

Re: approximation de la solution de f(x)=0 avec Newton

Message par parisse » sam. févr. 16, 2013 7:04 am

Probablement parce que bisection_solver utilise la librairie flottante GSL, et fait donc le calcul avec des flottants hardware indépendamment de Digits et de epsilon. Si vous calculez la différence avec un flottant multiprécision, ce dernier est converti en flottant hardware et la différence est nulle, mais en précision 14 chiffres.

Denizou
Messages : 61
Inscription : mer. juin 13, 2012 7:23 am

Re: approximation de la solution de f(x)=0 avec Newton

Message par Denizou » sam. févr. 16, 2013 9:09 am

parisse a écrit :Probablement parce que bisection_solver utilise la librairie flottante GSL, et fait donc le calcul avec des flottants hardware indépendamment de Digits et de epsilon. Si vous calculez la différence avec un flottant multiprécision, ce dernier est converti en flottant hardware et la différence est nulle, mais en précision 14 chiffres.
Justement non ! La différence est nulle quelle que soit le nombre de Digits... Ceci dit, cela n'arrive pas tout le temps. Pour f(x)=x^2-2 le phénomène ne se produit pas. Mais pour les deux fonctions testées au dessus, j'obtiens exactement la valeur calculée par fsolve.

parisse
Messages : 5734
Inscription : mar. déc. 20, 2005 4:02 pm
Contact :

Re: approximation de la solution de f(x)=0 avec Newton

Message par parisse » sam. févr. 16, 2013 10:05 am

Je me suis mal expliqué. Le résultat de fsolve avec bisection_solver est un flottant hardware quelle que soit la précision. Quand vous faites la différence avec le résultat de votre méthode de Newton, ce résultat multi-précision est converti en flottant hardware et donc la différence est nulle quelle que soit la précision.

Denizou
Messages : 61
Inscription : mer. juin 13, 2012 7:23 am

Re: approximation de la solution de f(x)=0 avec Newton

Message par Denizou » sam. févr. 16, 2013 3:42 pm

parisse a écrit :Je me suis mal expliqué. Le résultat de fsolve avec bisection_solver est un flottant hardware quelle que soit la précision. Quand vous faites la différence avec le résultat de votre méthode de Newton, ce résultat multi-précision est converti en flottant hardware et donc la différence est nulle quelle que soit la précision.
Je pense au contraire que vous avez été très clair mais que ce sont mes connaissances qui sont insuffisantes : auriez vous l'amabilité de m'expliquer (ou de me donner un lien) ce qu'est un flottant hardware.
Ceci dit (j'insiste !), pourquoi puis-je obtenir une différence nulle avec certaines fonctions mais pas avec toutes ? S'il c'était lié à l'écriture de la solution, ce ne serait pas le cas ?

Merci de vos réponses

frederic han
Messages : 1137
Inscription : dim. mai 20, 2007 7:09 am
Localisation : Paris
Contact :

Re: approximation de la solution de f(x)=0 avec Newton

Message par frederic han » sam. févr. 16, 2013 6:16 pm

Bonjour,

Les flottants hardware sont de precision fixe (en general 13 chiffres), ils utilisent une taille constante en memoire meme si Digits est <13. Ce sont les plus rapides.

Il y a aussi une librairie qui permet a giac de travailler en precision arbitraire pour certaines operations, mais pas pour toutes. Typiquement rand(0..1)() travaillera en flottants hardware quelquesoit le nombre de digits. Giac appelle certaines librairies qui ne supportent pas la precision arbitraire. Je pense que c'est le cas de gsl. Par exemple l'algebre lineaire non plus ne fera pas la precision arbitraire:
Ex:
en digits grand:
A:=[[1/3.0,1],[1,2]]
A*A sera bien en grande precision
mais
egv(A) se limitera a 13 chiffres car il utilise surement une autre librairie.

Frederic

parisse
Messages : 5734
Inscription : mar. déc. 20, 2005 4:02 pm
Contact :

Re: approximation de la solution de f(x)=0 avec Newton

Message par parisse » sam. févr. 16, 2013 6:46 pm

Oui, egv est en précision hardware, et utilise mon propre code si la taille de la matrice est < à la valeur de la variable d'environement GIAC_LAPACK (par defaut 400) et utilise lapack sinon (avec l'implémentation atlas sur les binaires fournis). J'ai toujours en projet de faire un egv en multi-précision, qui utiliserait la précision hardware comme départ, mais pas eu le temps de le faire jusqu'à présent.

Denizou
Messages : 61
Inscription : mer. juin 13, 2012 7:23 am

Re: approximation de la solution de f(x)=0 avec Newton

Message par Denizou » sam. févr. 16, 2013 7:35 pm

frederic han a écrit :Bonjour,

Les flottants hardware sont de precision fixe (en general 13 chiffres), ils utilisent une taille constante en memoire meme si Digits est <13. Ce sont les plus rapides.

Il y a aussi une librairie qui permet a giac de travailler en precision arbitraire pour certaines operations, mais pas pour toutes. Typiquement rand(0..1)() travaillera en flottants hardware quelquesoit le nombre de digits. Giac appelle certaines librairies qui ne supportent pas la precision arbitraire. Je pense que c'est le cas de gsl. Par exemple l'algebre lineaire non plus ne fera pas la precision arbitraire:
Ex:
en digits grand:
A:=[[1/3.0,1],[1,2]]
A*A sera bien en grande precision
mais
egv(A) se limitera a 13 chiffres car il utilise surement une autre librairie.

Frederic
Si j'ai bien compris :

1) Quelle que soit la méthode utilisée par fsolve, du fait de la valeur d'epsilon par défaut, je vais être plus précis que la valeur calculée, et ma suite va apparaître constante (du moins avec une quinzaine de chiffres significatifs). Pour "éloigner" ce phénomène, il me suffit de diminuer la valeur d'epsilon.
2) Une des méthodes utilisées (bisection_solver) par fsolve, utilise des flottants hardware, c'est à dire de précision fixe. Pour obtenir plus de décimales, l'algorithme fait appel à une librairie pour pouvoir travailler à la précision demandée.
3) Le résultat de cette méthode est à nouveau un flottant hardware, c'est à dire de précision fixe.

Ce que je ne comprends toujours pas :

1) Si j'obtiens Delta = 0,000000000000000... à un moment de mon itération pourquoi ensuite ce n'est plus le cas ?
2) Pourquoi selon les fonctions et en utilisant les mêmes algorithmes de résolution, n'obtiens-je pas toujours 0 ?

Merci de votre aide

Répondre