Retour à l'index du GREYC

Séminaire Algorithmique

Site du CNRS

Séminaire Algorithmique

Le séminaire a lieu le mardi à 11 h 45 (sauf modification exceptionnelle), au campus Côte de Nacre, bâtiment Sciences 3, salle S3 351, 3ème étage.

Résumé du séminaire du Mardi 23 Octobre 2007

Approximation polynomiale de fonctions continues et nombres flottants

par Sylvain Chevillard (LIP - ENS Lyon)

Pour calculer des valeurs approchées numériques des fonctions mathématiques usuelles, on remplace généralement la fonction par une autre, très proche et plus facile à calculer. Ainsi, l'élaboration d'un algorithme numérique pour évaluer une fonction suit généralement les étapes suivantes :

  1. on détermine sur quel intervalle on souhaitera évaluer la fonction ;
  2. on détermine avec quelle précision on souhaite connaître les valeurs de la fonction ;
  3. on cherche un approximant fournissant la précision requise sur l'intervalle choisi.
  4. on cherche un bon algorithme pour évaluer l'approximant.

Pour la troisième étape, on choisit généralement un polynôme (notamment parce que l'étape d'évaluation a été très bien étudiée dans le cas où l'approximant est un polynôme et on sait la traiter de manière satisfaisante).

Les coefficients du polynôme doivent être stockés dans la mémoire de l'ordinateur et doivent donc être représentables sous forme de nombres flottants. Nous nous intéressons au problème de la recherche d'un très bon polynôme (voire du meilleur) à coefficients représentables en machine, pour approcher une fonction continue. En utilisant la théorie des réseaux de points (et l'algorithme LLL de A. Lenstra, H. Lenstra et L. Lovasz) et la programmation linéaire, nous proposons un algorithme permettant d'obtenir un tel polynôme.

GREYC
Campus Côte de Nacre, boulevard du Maréchal Juin
BP 5186
14032 Caen Cedex
FAX : +33 (0)2 31 56 73 30
http://www.greyc.fr