Algorithmes de calcul formel et numérique PDF

livre-algorithmes EXo7.pdf

On retient les choses suivantes : • On affecte une valeur à une variable par le signe égal a. Page 9. ALGORITHMES ET MATHÉMATIQUES. 1. PREMIERS PAS AVEC Python

Cours de mathématiques - Exo7

Le triangle de Pascal est un algorithme pour calculer ces coefficients ( invariant par la translation de vecteur Ti oùi est le premier vecteur de ...

Exercices de mathématiques

Expliquer pourquoi les algorithmes 1 et 3 ne donneront pas le résultat attendu. Page 22. Ministère de l'Education Nationale de l'Enseignement Supérieur et de

Cours darithmétique

parant les olympiades internationales de mathématiques. Le plan complet de ce cours est : 2.3 Algorithme d'Euclide étendu et théor`eme de Bézout .

Maths vocab in English

math vs. maths : les deux sont corrects toutefois math relève de À titre d'exemple : en français 1 234 567

Analyse Numérique

cision de l'arithmétique mathématique et peut si on n'y prend garde

Algorithmes de calcul formel et numérique

Ce texte regroupe donc des résultats mathématiques qui ont doute une version actualisée du système utilisé sur les TI 89 92

Algèbre - Cours de première année

Voici la définition mathématique de la continuité d'une fonction f : I ? Le triangle de Pascal est un algorithme pour calculer ces coefficients.

Analyse Numérique

2 déc. 2014 f (x) grand ; (c) de l'algorithme utilisé dont les qualités dépendent de la méthode mathématique dont il découle

Algorithmes de calcul formel et numérique

B. Parisse

Institut Fourier

UMR 5582 du CNRS

Université de Grenoble

2 Giac/Xcas est un logiciel libre de calcul formel dont une caractéristique est de nécessiter peu de ressources sans sacrifier les performances (en particulier sur les calculs polynomiaux). Ce document décrit une partie des algorithmes de calcul for- mel et numérique qui y sont impleémentés, l"objectif à long terme est de couvrir l"essentiel des algorithmes implémentés. Ce n"est pas le manuel d"utilisation de Xcas, ni un manuel de programmation ou d"exercices illustrés avec Xcas (voir le menu Aide, Manuels : Référence calcul formel, Programmation, Exercices, Amu- sements...). Ce texte regroupe donc des résultats mathématiques qui ont été ou sont utilisés dans Giac (ou sont susceptibles de l"être), ils sont en général accompagnés de preuves et souvent d"illustrations avec Xcas.

Pour plus d"informations sur Giac/Xcas, cf. :

N.B. : La version HTML de ce document comporte des champs de saisie inter- actifs, ceux-ci apparaissent comme des commandes "mortes" dans la version PDF (elles sont exécutées une fois pour toutes par la version non interactive degiac). La version HTML est optimisée pour le navigateur Firefox. Elle est générée avec hevea.inria.frde Luc Maranget, ou le fork de Yannick Chevallier pour le support mathjax, ainsi qu"une version modifiée deitex2MMLde Jacques Distler pour la conversion en MathML. Si vous avez une machine très puissante, vous pou- vez exécuter toutes les commandes interactives en cliquant sur le bouton Exécuter. En-dessous de ce bouton se trouve la console de l"interpréteur du logiciel de calcul formel.

Table des matières

1 Plan et index

2 Trousse de survie Xcas

2.1 Utilisation comme super-calculatrice

2.2 Calcul exact

2.2.1 Arithmétique

2.2.2 Algèbre linéaire exacte

2.3 Calcul scientifique

2.3.1 Analyse numérique

2.3.2 Algèbre linéaire numérique

3 Calculer sur ordinateur

3.1 Représentation des entiers

3.2 Les réels

3.2.1 Virgule fixe et flottante.

3.2.2 Les flottants au formatdouble. . . . . . . . . . . . . .29

3.2.3 Opérations sur les flottants

3.2.4 Erreurs

3.2.5 Erreur absolue, relative, arrondi propagation des erreurs.

3.3 L"arithmétique d"intervalle.

3.4 Calcul exact et approché, types, évaluation.

3.5 Forme normale et reconnaissance du 0.

3.6 Valeur générique des variables et hypothèses

3.7 Structures de données

3.7.1 Maple, Mathematica, ...

3.7.2 Giac/Xcas

3.7.3 Calculatrices formelles HP48/49

3.7.4 Calculatrices formelles TI92/89/Voyage 200

3.8 Algorithmes et complexité.

3.8.1 Algorithmes modulaires ou p-adiques

3.8.2 Algorithmesdéterministes.Algorithmesprobabilistes:Las

Vegas et Monte-Carlo

3.9 Entiers et polynômes.

3.9.1 Petits et grands entiers

3.9.2 Opérations arithmétiques de base

3.9.3 Opérations de base sur les petits entiers.

3.9.4 Opérations de base sur les grands entiers

3.10 Euclide

52
3

4TABLE DES MATIÈRES

3.10.1 Division euclidienne.

3.10.2 Anneau euclidien

3.10.3 Le PGCD

3.10.4 L"identité de Bézout

3.10.5 Nombres premiers entre eux

3.10.6 Les restes chinois

3.10.7 Nombres premiers, factorisation

3.10.8 Remarque : la divisibilité est une relation d"ordre partiel

3.10.9 Prolongement : idéaux

3.11 Quelques algorithmes d"arithmétique de base.

3.11.1 Calcul de la racine carrée entière

3.11.2 Bezout sur les entiers et les fractions continues

3.11.3 La puissance rapide itérative

3.11.4 Application de la puissance rapide : trouver un g

´nérateur

deFp=Z=p. . . . . . . . . . . . . . . . . . . . . . .66

3.11.5 Application de la puissance rapide : cryptographie RSA

3.12 Algorithmes rapides sur les polynômes en une variable.

3.12.1 Inverse moduloxl. . . . . . . . . . . . . . . . . . . . .70

3.12.2 Division euclidienne.

3.12.3 Euclide

3.13 Pour en savoir plus.

3.14 Exercices sur types, calcul exact et approché, algorithmes de bases

4 Les générateurs de nombres pseudo-aléatoires.

4.1 Selon la loi uniforme

4.1.1 Les générateurs congruentiels à 1 cran.

4.1.2 Récurrence àkéléments. . . . . . . . . . . . . . . . . . 82

4.1.3 Mersenne twister.

4.2 Selon plusieurs lois classiques

5 Le PGCD de polynômes.

5.1 Le sous-résultant.

5.2 Le pgcd en une variable.

5.2.1 Le pgcd heuristique.

5.2.2 Le pgcd modulaire

5.3 Le pgcd à plusieurs variables.

5.3.1 Le pgcd heuristique.

5.3.2 Le pgcd modulaire multivariables.

5.3.3 EZGCD.

5.4 Quel algorithme choisir?

103

5.5 Pour en savoir plus.

103

6 Le résultant

105

6.1 Définition

105

6.2 Applications

106

6.2.1 Systèmes polynomiaux

107

6.2.2 Identité de Bézout dansZ[X].. . . . . . . . . . . . . . . 107

6.3 Résultant et degrés

108

TABLE DES MATIÈRES5

6.4 Lien avec l"algorithme du sous-résultant (calcul de PGCD)

109

6.5 Calcul efficace du résultant

111

7 Localisation des racines

113

7.1 Majoration

113

7.2 Les suites de Sturm.

113

7.3 Autres algorithmes

114

8 Exercices (PGCD, résultant, ...)

119

8.1 Instructions

119

8.1.1 Entiers

119

8.1.2 Polynômes

119

8.1.3 Calculs modulon. . . . . . . . . . . . . . . . . . . . . .120

8.2 Exercices PGCD

121

8.3 Exercice (Bézout modulaire)

122

8.4 Exercices (résultant)

123

8.5 Décalage entier entre racines.

124

8.6 Exemple de correction de géométrie et résultant

126
127

9.1 Ordre et réduction

127

9.2 Idéaux

128

9.3 Introduction

128

9.4 Checking a reconstructed Groebner basis

129

9.5 Speeding up by learning from previous primes

130

9.6 Giac/Xcas implementation and experimentation

131

9.7 Conclusion

134

9.8 Représentation rationnelle univariée (rur).

135

10 Courbes paramétriques et polaires

139

10.1 Introduction

139

10.2 Représentation graphique

144

10.3 Paramétrage

146

10.4 Étude analytique d"une courbe en paramétrique

146

10.4.1 Rappel sur les graphes de fonction

146

10.4.2 Domaine et périodicité

149

10.4.3 Branches infinies

150

10.4.4 Étude locale

151

10.5 Plan d"étude d"une courbe

159

10.6 Courbes en polaires

160

10.7 Coniques

168

10.7.1 Ellipse

169

10.7.2 Parabole

172

10.7.3 Hyperbole

174

10.7.4 Paramétrisation rationnelle

175

11 Propriétés métriques des courbes.

179

11.1 Longueur d"arc

179

11.2 Courbure, repère de Frenet, accélération normale et tangentielle.

181

6TABLE DES MATIÈRES

12 Représentation des courbes implicites.

189

13 Formes différentielles et intégrales curvilignes

191

13.1 Forme différentielle

191

13.2 Intégrale curviligne

193

13.3 Forme différentielle exacte

194

13.4 Intégrale curviligne et intégrales doubles.

196

14 Équations et systèmes différentiels.

199

14.1 Introduction et représentation graphique.

199

14.2 Existence et unicité

203

14.3 Quelques méthodes de résolution explicite.

206

14.3.1 Équations à variables séparables

206

14.3.2 Équations linéaires

206

14.3.3 Équations linéaires à coefficients constants

207

14.3.4 Systèmesdifférentielslinéairesàcoefficientsconstantsd"ordre

1. 210

14.3.5 Systèmes et équations

211

14.3.6 Allure des courbes en dimension 2.

212

14.3.7 Systèmes d"ordre plus grand que 1

214

14.3.8 Intégrales premières.

215

14.3.9 Le modèle proie-prédateur

217

14.3.10Quelques autres méthodes

218

14.4 Comportement asymptotique des solutions

218

14.4.1 Équations linéaires à coefficients constants d"ordre 1 et 2

218

14.4.2 Forçage périodique

219

14.4.3 Équation autonome sans second membre

220

14.4.4 Systèmes linéaires

221

14.4.5 Forçage près d"un point d"équilibre de système.

222

14.5 Résolution numérique

224

14.5.1 Méthodes à un pas

224

14.5.2 Méthodes de Runge-Kutta (explicites)

226

15 Introduction au calcul variationnel

229

16 Corps finis.

235

16.1 Rappels

235

16.2 Représentation des corps non premiers.

235

16.2.1 Cas général.

235

16.2.2 Corps de petit cardinal, cas de la caractéristique 2

236

16.3 Exercices

237

16.4 Rappels de quelques complexités de base

quotesdbs_dbs46.pdfusesText_46

[PDF] Algorithmes de calcul formel et numérique

Algorithmes de calcul formel et numérique

B. Parisse

Institut Fourier

UMR 5582 du CNRS

Université de Grenoble

Pour plus d"informations sur Giac/Xcas, cf. :

Table des matières

1 Plan et index

2 Trousse de survie Xcas

2.1 Utilisation comme super-calculatrice

2.2 Calcul exact

2.2.1 Arithmétique

2.2.2 Algèbre linéaire exacte

2.3 Calcul scientifique

2.3.1 Analyse numérique

2.3.2 Algèbre linéaire numérique

3 Calculer sur ordinateur

3.1 Représentation des entiers

3.2 Les réels

3.2.1 Virgule fixe et flottante.

3.2.2 Les flottants au formatdouble. . . . . . . . . . . . . .29

3.2.3 Opérations sur les flottants

3.2.4 Erreurs

3.2.5 Erreur absolue, relative, arrondi propagation des erreurs.

3.3 L"arithmétique d"intervalle.

3.4 Calcul exact et approché, types, évaluation.

3.5 Forme normale et reconnaissance du 0.

3.6 Valeur générique des variables et hypothèses

3.7 Structures de données

3.7.1 Maple, Mathematica, ...

3.7.2 Giac/Xcas

3.7.3 Calculatrices formelles HP48/49

3.7.4 Calculatrices formelles TI92/89/Voyage 200

3.8 Algorithmes et complexité.

3.8.1 Algorithmes modulaires ou p-adiques

3.8.2 Algorithmesdéterministes.Algorithmesprobabilistes:Las

Vegas et Monte-Carlo

3.9 Entiers et polynômes.

3.9.1 Petits et grands entiers

3.9.2 Opérations arithmétiques de base

3.9.3 Opérations de base sur les petits entiers.

3.9.4 Opérations de base sur les grands entiers

3.10 Euclide

4TABLE DES MATIÈRES

3.10.1 Division euclidienne.

3.10.2 Anneau euclidien

3.10.3 Le PGCD

3.10.4 L"identité de Bézout

3.10.5 Nombres premiers entre eux

3.10.6 Les restes chinois

3.10.7 Nombres premiers, factorisation

3.10.8 Remarque : la divisibilité est une relation d"ordre partiel

3.10.9 Prolongement : idéaux

3.11 Quelques algorithmes d"arithmétique de base.

3.11.1 Calcul de la racine carrée entière

3.11.2 Bezout sur les entiers et les fractions continues

3.11.3 La puissance rapide itérative

3.11.4 Application de la puissance rapide : trouver un g

´nérateur

3.11.5 Application de la puissance rapide : cryptographie RSA

3.12 Algorithmes rapides sur les polynômes en une variable.

3.12.1 Inverse moduloxl. . . . . . . . . . . . . . . . . . . . .70

3.12.2 Division euclidienne.

3.12.3 Euclide

3.13 Pour en savoir plus.

3.14 Exercices sur types, calcul exact et approché, algorithmes de bases

4 Les générateurs de nombres pseudo-aléatoires.

4.1 Selon la loi uniforme

4.1.1 Les générateurs congruentiels à 1 cran.

4.1.2 Récurrence àkéléments. . . . . . . . . . . . . . . . . . 82

4.1.3 Mersenne twister.

4.2 Selon plusieurs lois classiques

5 Le PGCD de polynômes.

5.1 Le sous-résultant.

5.2 Le pgcd en une variable.

5.2.1 Le pgcd heuristique.

5.2.2 Le pgcd modulaire

5.3 Le pgcd à plusieurs variables.

5.3.1 Le pgcd heuristique.