Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Algorithme de Risch
Résumé
L’algorithme de Risch, dû à , est un algorithme destiné aux systèmes de calcul formel, permettant de calculer des primitives, c'est-à-dire de déterminer une fonction, connaissant sa dérivée. L’algorithme transforme ce problème en un problème d'algèbre (ou plus précisément d'). Il est basé sur la forme de la fonction à intégrer et sur des méthodes pour intégrer les fonctions rationnelles, les radicaux, les logarithmes, et les exponentielles. Risch, qui développa l'algorithme en 1968, l'a appelé une procédure de décision, parce qu'il est capable de déterminer si une fonction admet une primitive exprimable à l'aide des fonctions élémentaires (et, si c'est le cas, de la déterminer explicitement). L’algorithme de Risch est résumé (en plus de cent pages) dans Algorithms for Computer Algebra, de , Stephen Czapor et George Labahn. L'algorithme de Risch–Norman, plus rapide mais moins général, fut développé en 1976.
L'algorithme de Risch a pour but d'intégrer des fonctions élémentaires, c'est-à-dire des fonctions obtenues par composition d'exponentielles, de logarithmes, de radicaux, des fonctions trigonométriques, et des quatre opérations arithmétiques (+ − × ÷). Laplace résolut ce problème pour le cas des fonctions rationnelles, en montrant que la primitive d'une telle fonction est somme d'une fraction rationnelle et de multiples de logarithmes de fractions rationnelles. L'algorithme suggéré par Laplace est généralement décrit dans les manuels de calcul intégral ; en tant que programme informatique, il fut finalement implémenté dans les années 1960.
Entre 1833 et 1841, Liouville formula rigoureusement le problème que résout l'algorithme de Risch. Il montra (par des méthodes analytiques) que s'il existe une solution élémentaire g à l'équation g ′ = f, alors il y a des constantes αi et des fonctions élémentaires ui et v telles que la solution soit de la forme
(c'est le théorème de Liouville-Rosenlicht). Risch développa une méthode permettant de ne considérer qu'un ensemble fini de fonctions élémentaires ayant la forme donnée par Liouville.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.