Soutenance mémoire
Résoudre ou ne pas résoudre
Face à une intégrale, une somme, une équation différentielle, on a souvent le réflexe de calculer , de résoudre, afin d’arriver à une expression en termes de fonctions connues de la solution ou de l’objet dénoté par la formule. Les formes explicites sont précieuses, et des algorithmes puissants existent pour les trouver. Tout utilisateur du calcul formel a vu son logiciel favori calculer comme par magie une intégrale peu commode. Sans doute a-t-il aussi été confronté un jour à une réponse « explicite » en termes de fonctions G de Meijer, ou d’autres fonctions spéciales ésotériques. Car il en va des calculs sur ordinateur comme de ceux à la main : afin d’augmenter le pouvoir d’expression des « formules », on est conduit à introduire peu à peu de nouvelles fonctions. Définies comme solutions « canoniques » de telle ou telle équation remarquable, elles s’accompagnent de règles de calcul qui permettent de travailler avec les expressions les faisant intervenir. Le support d’une large gamme de fonctions spéciales est un enjeu conséquent pour un système de calcul formel lorsqu’il est la clé pour représenter sur l’ordinateur les fonctions (et les nombres [30]) que l’on souhaite manipuler. Une approche un peu différente consiste à se donner les moyens de calculer avec ces fonctions même quand elles ne sont pas représentables explicitement. La nuance avec l’adjonction de fonctions spéciales très générales n’est souvent qu’une question de langage. Mais celui des équations est parfois fort naturel du point de vue algorithmique, par exemple s’il s’agit de manipuler les nombres algébriques à travers leurs polynômes annulateurs. Il sous-entend en tout cas un point de vue moins orienté vers les règles de calcul ad hoc, et plus vers le traitement uniforme d’une classe d’objets bien définie. La détection des cas particuliers où existent des expressions plus explicites et la recherche de ces dernières est dévolue à une phase de résolution clairement séparée.
On pourrait faire remonter l’étude des fonctions D-finies à la seconde moitié du dix neuvième siècle. Une bonne partie des résultats mathématiques auxquels nous ferons appel datent en effet des travaux de Cauchy, Riemann, Fuchs, Frobenius et d’autres mathématiciens sur les équations différentielles linéaires à coefficients analytiques. Mais c’est le début des années 1980 qui voit se dégager le concept de série D-finie, d’abord en combinatoire, avec un article de Stanley [222] récapitulant les propriétés de base qui en font une classe d’objets remarquables. Des travaux de Zeilberger naissent ensuite, vers 1990, les premiers algorithmes de calcul formel majeurs utilisant véritablement les récurrences et équations différentielles linéaires comme structure de données. Plusieurs implémentations indépendantes de son algorithme de sommation hypergéométrique apparaissent rapidement. Peu après, la première version du module Maple gfun [214] propose une boîte à outils complète de calcul avec comme objets de base ces équations. D’autres outils du même genre suivent [147, 165]. À l’extrême, on peut envisager de remplacer complètement la définition « explicite » dans un système de calcul formel des fonctions qui s’y prêtent par une description « D-finie ».
Et l’évaluation numérique ?
Les travaux mentionnés dans la section précédente ont en commun de traiter les séries D-finies comme des séries formelles plutôt que comme des fonctions analytiques. On attend pourtant d’un logiciel de calcul formel qu’il soit capable de tracer les graphes des fonctions qu’on y manipule, ou encore de les évaluer à précision arbitraire. Lorsque l’on traite les fonctions élémentaires et fonctions spéciales une à une, chacune vient habituellement avec non seulement les règles algébriques nécessaires aux manipulations symboliques, mais aussi du code d’évaluation numérique. Afin de manipuler les fonctions D-finies dans l’optique de la section précédente, il est souhaitable, de même, que l’évaluation numérique fasse partie des opérations disponibles en utilisant les équations différentielles comme structure de donnée. Ce que les systèmes existants offrent en général de plus proche est un intégrateur numérique générique d’équations différentielles. Ces intégrateurs sont assez éloignés des caractéristiques des routines d’évaluation numérique des fonctions usuelles : ils ne donnent des résultats corrects que sur un voisinage limité du point où sont fournies les conditions initiales, n’offrent le plus souvent aucune garantie, ciblent la petite précision plutôt que la précision arbitraire, et finalement ne tirent que très peu parti des propriétés fortes des fonctions D-finies. Plus généralement, les opérations de nature analytique — « majorer, minorer, approcher », suivant les mots de Dieudonné [76, p. 15] — sur les fonctions D-finies sont comparativement peu développées, que ce soit en théorie ou en pratique. Comme travaux allant explicitement dans cette direction, je ne connais guère que ceux de van der Hoeven [235, 236, 239] sur l’évaluation à grande précision des fonctions D-finies, qui s’inscrivent dans un programme plus général d’analyse complexe effective [240, 243], et ceux de Gerhold, Kauers et Pillwein [109, 141, 143] sur la preuve d’inégalités. Quelques développements plus anciens, notamment une série d’articles des frères Chudnovsky [54, 57] précurseurs de ceux de van der Hoeven déjà cités, répondaient déjà aux mêmes questions du point de vue du calcul formel. En revanche, toute une littérature qui va des mathématiques pures à l’arithmétique d’intervalles en passant par l’analyse numérique (et les méthodes de Lánczos ou de Clenshaw mentionnées plus haut) fourmille d’idées qui mériteraient d’être revisitées pour nos besoins.
Cette thèse contribue à munir la structure de données « fonction D-finie » d’opérations « analytiques », à commencer par l’évaluation numérique. Le leitmotiv est de proposer des solutions, par ordre approximatif d’importance :
Automatiques. Je m’efforce de donner des algorithmes généraux , plutôt que des méthodes qui demandent des ajustements manuels pour s’appliquer efficacement à un problème donné. Ces algorithmes sont autant que possible accompagnés d’implémentations, qui elles-mêmes fonctionnent pour toute la classe des fonctions D-finies et à précision arbitraire.
Garanties. À l’image des tables mentionnées plus haut, les outils développés visent à pouvoir servir de référence et se doivent donc de fournir des valeurs numériques fiables. Tous les résultats ou presque s’accompagnent donc de bornes d’erreur rigoureuses.
Rapides. L’arrivée de machines de bureau puissantes et d’implémentations extrêmement rapides d’algorithmes avancés en arithmétique multiprécision et en calcul formel renforce l’importance pratique de la complexité des algorithmes. En ce qui concerne l’évaluation ou l’approximation de fonctions, la taille de l’expression à évaluer est en règle générale plus petite que celle du résultat. On vise alors une complexité quasi-optimale, linéaire en la taille de la sortie à des facteurs logarithmiques près.
Presque tous les algorithmes en jeu sont naturellement symboliques-numériques. On appelle ainsi les procédés mêlant calculs exacts et approchés, qu’il s’agisse de passer par des calculs numériques pour obtenir plus rapidement un résultat symbolique, ou inversement de résoudre numériquement un problème mal conditionné grâce à un prétraitement ou des étapes exactes. Les résultats « analytiques » que nous nous proposons de calculer ne se limitent pas aux valeurs numériques. En particulier, des approximants polynomiaux, ou encore diverses sortes de bornes, sont tout à la fois des intermédiaires pour le calcul de valeurs numériques et des résultats que l’on peut mettre sous une forme intelligible et renvoyer à l’utilisateur. Or, parmi les utilisateurs potentiels d’un outil d’évaluation numérique garanti, se trouvent les développeurs de bibliothèques numériques. Les outils de calcul formel auxquels font appel les algorithmes d’évaluation à la fois automatiques et relativement généraux rejoignent parfois ceux dont eux auraient besoin. Un second axe se dessine : commencer ainsi à développer, toujours concernant la classe des fonctions D-finies, des outils de calcul formel « pour l’arithmétique des ordinateurs », complémentaires d’outils spécialisés comme Sollya [52].
NumGfun
Le logiciel présenté ici, NumGfun, est une extension à gfun dédiée à l’évaluation des suites ou fonctions définies par les équations traitées, et plus généralement à leur manipulation « analytique ». Il offre, entre autres, un moteur de prolongement analytique numérique garanti de solutions d’équations différentielles linéaires à coefficients polynomiaux, et des fonctions de calcul de bornes symboliques sur les valeurs de suites récurrentes.
Distribution. NumGfun a évolué à partir d’une première version (presque entièrement réécrite entre-temps) qui date de mon stage de M2. Celle utilisée pour l’instant dans ce document est une version de développement qui doit déboucher prochainement sur la version stable accompagnant la forme finale de cette thèse. Après quelques versions indépendantes à ses débuts, NumGfun est désormais un sous-module de gfun. Il est distribué avec lui au sein de la bibliothèque Algolib [205], sous les conditions de la GNU Lesser General Public Licence, version 2.1 [99].
Travaux apparentés. Les algorithmes mis en œuvre dans NumGfun trouvent en majorité leur origine dans les travaux des frères Chudnovsky [53, 54, 55, 56, 57] ainsi que de van der Hoeven [234, 235, 236, 237]. Le plus important est peut-être la méthode d’évaluation numérique baptisée bit burst [57]. Elle appartient à la famille des algorithmes de sommation de séries D-finies par scindage binaire, que l’on peut faire remonter à une note de Schroeppel et Salamin [15, §178], et généralise par ailleurs des algorithmes proposés auparavant par Brent [37] pour des fonctions élémentaires particulières. Je renvoie à Bernstein [24, §12.7] et van der Hoeven [239, §1] pour plus de contexte et d’histoire. Plusieurs algorithmes mieux connus (notamment grâce aux descriptions et implémentations de Haible et Papanikolaou [122] ainsi que de Gourdon et Sebah [115]) peuvent se voir comme des cas particuliers de l’algorithme bit burst. Contrairement à eux, l’algorithme général n’avait apparemment jamais été utilisé en pratique avant ce travail. Une explication possible est que dans la description de Chudnovsky et Chudnovsky, le contrôle des erreurs ne fait pas partie de l’algorithme. Il s’agit donc d’une méthode pouvant être spécialisée pour calculer n’importe quelle fonction D-finie donnée, moyennant des bornes d’erreur calculées séparément. La version de van der Hoeven [235] corrige cette faiblesse et fournit ainsi un véritable algorithme général d’évaluation à grande précision pour toute la classe des fonctions D-finies. Toutes ces techniques s’étendent au calcul de limites et « conditions initiales généralisées » aux singularités de l’équation différentielle qui définit la fonction. Le cas des points singuliers réguliers est abordé dans plusieurs articles de Chudnovsky et Chudnovsky [53, 54, 57] puis traité de façon plus explicite par van der Hoeven [236], qui résout aussi par la suite celui (non implémenté dans NumGfun) des points singuliers irréguliers [239]. Sur le plan des implémentations, des bibliothèques généralistes comme CLN [121] ou MPFR [183] utilisent des routines à base de scindage binaire pour évaluer certaines fonctions élémentaires et fonctions spéciales. La sommation par scindage binaire de séries à convergence rapide est aussi l’algorithme de prédilection des logiciels dédiés au calcul à très grande précision de constantes remarquables sur des machines de bureau, dont les détenteurs récents du record de calcul de π [17, 262]. Enfin, la variété déjà impressionnante de fonctions spéciales disponibles nativement dans les systèmes de calcul formel n’est pas toujours suffisante dans les applications. Plusieurs articles récents sont consacrés à l’évaluation de classes de fonctions spéciales « un peu moins communes » qui recoupent celle couverte par NumGfun [4, 89]. Les fonctionnalités de calcul de bornes symboliques offertes par NumGfun sont uniques en leur genre. L’outil existant le plus proche est sans doute le logiciel ACETAF de Eble et Neher [82], dont l’idée est, grossièrement, de borner les coefficients de Taylor par une application en arithmétique d’intervalles de la formule intégrale de Cauchy. L’algorithme utilisé dans NumGfun emprunte à des techniques d’asymptotique automatique [93, 94] ainsi qu’à des algorithmes proposés par van der Hoeven pour l’analyse effective [235, 237, 240].
|
Table des matières
Introduction
1 Des tables et des programmes
2 Résoudre ou ne pas résoudre
3 Et l’évaluation numérique ?
4 Organisation du manuscrit et contributions
1 NumGfun
1.1 Présentation
1.2 Une session avec NumGfun
1.2.1 gfun
1.2.2 NumGfun
1.2.3 Évaluation numérique
1.2.4 Prolongement analytique numérique
1.2.5 Évaluation numérique, suite
1.2.6 Points singuliers réguliers
1.2.7 Bornes symboliques
1.3 Architecture
1.4 Développements à venir
2 Le DDMF
2.1 Motivation
2.2 Algorithmes de calcul formel
2.3 Présentation en ligne et interactivité
2.4 Futur
3 Préliminaires : équations différentielles et récurrences linéaires
3.1 Notations et conventions
3.1.1 Structures algébriques usuelles
3.1.2 Autres notations
3.2 Généralités sur les récurrences et équations différentielles linéaires
3.2.1 Récurrences
3.2.2 Équations différentielles à coefficients séries
3.3 D-finitude
3.3.1 Définitions
3.3.2 Équations différentielles et récurrences
3.3.3 Propriétés de clôture
3.3.4 Intermède : (in)décidabilité
3.4 Asymptotique
3.4.1 Généralités
3.4.2 Le théorème de Perron-Kreuser
3.4.3 Développements asymptotiques de suites P-récursives
4 Points singuliers réguliers
4.1 Introduction
4.2 Solutions au voisinage d’un point singulier
4.2.1 Étude analytique locale
4.2.2 Points singuliers réguliers et points singuliers irréguliers
4.2.3 Étude formelle
4.3 La méthode de Frobenius
4.3.1 Le cas générique
4.3.2 Indices exceptionnels
4.3.3 Base de solutions construite par la méthode de Frobenius
4.3.4 Récurrences sur les coefficients
4.4 La méthode de Poole et la base canonique
4.4.1 Introduction
4.4.2 Formulation compacte
4.4.3 Base canonique de solutions en un point singulier régulier
4.4.4 Jeux d’écriture
4.5 La méthode originale de Heffter
5 Majorants pour les suites P-récursives
5.1 Introduction
5.1.1 Problématique
5.1.2 Quelques exemples
5.1.3 Esquisse de l’algorithme et plan du chapitre
5.2 Paramètres de croissance factorielle et exponentielle
5.2.1 Singularités dominantes
5.2.2 Croissance générique des solutions
5.2.3 Fonction génératrice normalisée
5.3 Contrôle du comportement sous-exponentiel
5.3.1 La méthode des séries majorantes
5.3.2 Séries majorantes pour les fractions rationnelles
5.3.3 Séries majorantes pour les fonctions D-finies normalisées
5.3.4 Variante : majorants avec partie polynomiale
5.3.5 Variante : points ordinaires
5.4 Bornes sur les suites P-récursives générales
5.4.1 Algorithme
5.4.2 Formules explicites
5.5 Implémentation
5.6 Remarques finales
5.6.1 Bornes fines sans formule explicite
5.6.2 Limitations
Conclusion
Télécharger le rapport complet
