Accélération de convergence (exposants de Lyapunov)

[martini_bird]

Salut à tous !

Dans le genre « je me détends », j'ai tenté un petit programme pour calculer des exposants de Lyapunov. Tout ça tourne bien en quelques lignes, seul hic : dès qu'on veut avoir un minimum de précision, c'est loooong !

Là, je me souviens qu'il existe des techniques d'accélération de convergence pour les suites/séries : Richardson, Aitken, Mac-Laurin, transformation d'Euler etc. Mais dans le cas qui m'intéresse, c'est de maigre utilité.

Je m'explique : il s'agit de calculer la limite des moyennes de Césaro d'une suite , où la suite des points est donnée par une relation de récurrence . *

Si par conséquent vous avez des idées ou des techniques de sioux à me proposer, je suis preneur !

Merci d'avance.

* Avec et , on retombe bien sur l'exposant de Lyapunov associé à la suite logistique .
-----

[martini_bird]

Salut,

je vous donne le résultat de 11 heures de calcul pour vous motiver.

A comparer avec wikipedia (la première image, qui je ne sais trop pourquoi est à l'envers) : je suppose que l'illustration sur wiki a été obtenue en laissant de côté la valeur exact de l'exposant lorsqu'il est positif (zone coloriée en noir).

Bref, c'est looong, mais c'est beau (qui a dit non ?! ).

Cordialement.

[Gwyddon]

Coucou,

Mon message inutile du jour : en effet c'est très beau mais je ne peux pas t'aider

[Calvert]

Petite question: tu as codé dans quel langage?

Je ne sais pas comment accélérer ta convergence, mais pense aux pauvres astrophysiciens en évolution stellaire qui calculent plutôt pendant des mois...

Mais effectivement, c'est très beau!

[A voir en vidéo sur Futura]

[martini_bird]

Salut,

c'est fait en python, mais on pourrait le faire avec n'importe quel langage qui connait les additions et sait afficher un point avec une couleur donnée (autrement dit tous ).

Merci pour les encouragements : puisque visiblement il n'y a guère moyen d'être plus rapide, je suis en train de modifier le programme pour découper les calculs en plusieurs sessions.

Cordialement.

PS : si le code intéresse des gens, il suffit de m'envoyer un mp.

[Calvert]

Peut-être devrais-tu essayer un langage compilé (python ne l'est pas, sauf erreur de ma part). Mon expérience me fait dire que c'est plus rapide que les langages interprétés.

En tout cas, entre Matlab et C++, un gain de temps d'un facteur 10 est envisageable suivant les cas.

[martini_bird]

C'est pas bête : je vais essayer en c++ à l'occasion.

Merci !

[invite4ef352d8]

si Python est un language performant. je pense pas qu'on gagne grand chose a essayer d'autres language (par pas grand chose j'entend moins d'un facteur 2 quoi)

[Gwyddon]

Oui mais comme le dit Calvert, c'est un langage interprété. Un langage compilé est bien plus rapide, quel que soit le langage d'ailleurs

C++, OCaml, C, etc...

EDIT : au passage c'est très lisible le python ? Si oui, je peux tenter de traduire ton code en Ocaml, pour voir

[invite8ef897e4]

Bonjour,

c'est tres beau en effet, mais je suis decu d'apprendre que Python ne se compile pas
Je voulais me mettre a Python, c'est sexy en ce moment

[Gwyddon]

Bonjour,

c'est tres beau en effet, mais je suis decu d'apprendre que Python ne se compile pas
Je voulais me mettre a Python, c'est sexy en ce moment

Plus sexy que le C++ qui a envahi la physique des particules ?

[invite8ef897e4]

[mode=HS]

Plus sexy que le C++ qui a envahi la physique des particules ?

Ah ben moi j'ai ete eleve au C++ puis Java, et je n'ai pas particulierement a m'en plaindre Mais c'est vrai que Python semble devenir populaire parmi les "vrais" informaticiens. Enfin, moi j'ai decouvert Python par l'intermediaire d'un informaticien qui a ete mis a l'honneur au labo pour ses performances dans un concours international (de programmation) et j'ai voulu en savoir plus, parce que notre celebrite locale utilise ce langage. Et j'ai decouvert qu'il est tres elegant, alors j'ai commence (doucement) a jouer un peu avec. mais je ne m'etais jamais pose la question de la compilation... Il n'est peut-etre pas fait pour ca. Apres tout, awk n'est pas compilable, et m'offre de grand service (bon ok, la comparaison est un peu deplacee).
[/mode]

Je n'arrive pas a savoir si l'image produite par martini_bird presente une meilleure resolution que celle sur wikipedia (je ne parle pas de l'image elle-meme bien entendu, mais du contenu !) Peut-etre que l'inage de wiki a une plus grande precision au niveau du calcul, mais que la representation est moins bien choisie (echelle de couleurs moins riche)

image sur wiki
http://upload.wikimedia.org/wikipedi..._fractal_1.png

[martini_bird]

Peut-etre que l'inage de wiki a une plus grande precision au niveau du calcul, mais que la representation est moins bien choisie (echelle de couleurs moins riche)

Tout à fait : les contours sont plus nets sur l'image de wikipedia (le nombre d'itérations doit être plus élevé, ou des astuces que je ne connais pas ont été utilisées). En revanche les exposants positifs (la zone noire) sont tous traités de la même façon, et le dégradé bleu/blanc pour les exposants négatifs ne fait intervenir "qu'une" échelle de 256 couleurs.

J'ai pris cette image comme référence pour tester mon programme, histoire de ne pas prendre des vessies pour des lanternes...

Cordialement.

[Bobby]

Salut martini,

peut-être as-tu déjà essayé l'extension psyco ? En gros elle fait une pseudo-compilation en C de ton programme python et ça accélère sensiblement son excécution. Pour l'utiliser il y a juste à insérer ces deux lignes en début de programme :

try: import psyco; psyco.full()
except: pass

Il faut bien évidemment l'avoir installée bien sûr. En moyenne il semblerait que le temps d'exécution soit divisé par 4. En ce qui me concerne j'ai eu droit à un facteur 10 sur une génération de nombres premiers. C'est assez impressionant.

[martini_bird]

Salut,

merci pour l'astuce, sur quelques essais je gagne un facteur 3.

Merci !

[martini_bird]

Salut,

avec l'astuce de Bobby, et en intégrant dans le programme des tests d'arrêt plus pertinent, j'ai obtenu l'image suivante en 1h07. Merci !

Je devrais pouvoir faire mieux, car j'ai segmenté les calculs de manière à augmenter la précision pour les régions « délicates ».

Cordialement.