Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Chapitre 1 13 Algorithmique algébrique par Daouda Niang Diatta Résumé Ce chapitre est un chapitre d'introduction faire des opérations C exactes sur un ordinateur en précision in nie ne peut se faire sans précaution Les limites imposées par la machine prin

Algorithmique algébrique par Daouda Niang Diatta Résumé Ce chapitre est un chapitre d'introduction faire des opérations C exactes sur un ordinateur en précision in nie ne peut se faire sans précaution Les limites imposées par la machine principalement la taille de la mémoire disponible et la vitesse d'exécution des programmes se font rapidement sentir On ne peut donc aborder l'algorithmique algébrique sans avoir au moins un minimum de repères informatiques notamment la notion de complexité des algorithmes C'est le sujet que nous allons brièvement développer ici Calcul formel quelques généralités Le calcul formel a commencé à se développer vers les années lorsque les ordinateurs devinrent assez puissants pour envisager des calculs polynomiaux des dérivations itérées de grosses fonctions ou bien des calculs de primitives pratiquement inaccessibles à la main Ce genre de calcul est évidemment purement mécanique et il semble naturel qu'un ordinateur puisse réaliser ce travail automatiquement On obtenait alors la valeur formelle d'une fonction dérivée ou d'une primitive et non pas simplement une valeur approchée en un point particulier On pouvait donc manipuler des formules avec un ordinateur Avec la puissance accrue des machines et le développement de nouveaux algorithmes de nombreux systèmes formels seront développés depuis capable de mener des calculs de plus en plus gros sur des objets de plus en plus abstraits Calcul formel et calcul numérique La première caractéristique de tels systèmes est de pouvoir faire tout calcul exactement et donc d'appréhender les objets pour ce qu'ils sont ainsi le rationnel ne peut être en aucun cas remplacé dans un système formel par un nombre décimal du genre qui est un autre rationnel qui ne lui est pas égal C On doit impérativement faire travailler la machine en précision in nie Tout calcul sera exécuté sans aucun recours à des calculs approchés Ceci présente avantage et inconvénient D'une part il n'y a aucune erreur dans l'évaluation d'une formule et en cela on est débarrassé du problème auquel on est constamment confronté en analyse numérique les erreurs d'approximation et incertitudes numériques Mais d'un autre coté il faut être prêt à gérer des nombres de plus en plus gros qui prendront pour être stockés de plus en plus de place mémoire et sur lesquels les opérations seront de plus en plus longues à être exécutées Prenons un exemple simple pour illustrer les divers problèmes qui se posent en calcul numérique et formel Si nous cherchons la valeur du polynôme x ? x en Un bon système numérique nous donne ce qui est manifestement faux mais reste cependant un nombre simple facile à manipuler et proche du résultat exact Quant à un système formel il calcule la valeur exacte qui est une fraction dont le numérateur aussi bien que le dénominateur ont B chi res chacun en base L'exactitude autant que la rapidité ont donc chacun un prix On peut résumer les deux approches dans le tableau ci-dessous C D Calcul numérique approximation en virgule ottante des nombres erreur d'approximation calculs rapides encombrement mémoire réduit Calcul formel