[FAQ] fr.sci.maths - partie 3/3
medtib@alussinan.org (Mehdi Tibouchi)
Archive-Name: fr/maths/maths-faq-3
Last modified: 2006-11-11
Version 2.12
#####################################################
# #
# FAQ fr.sci.maths (partie 3/3) #
# #
#####################################################
fr.sci.maths est un groupe de discussion destiné à recueillir les
discussions en français concernant les mathématiques.
Ce document rassemble les questions qui ont été fréquemment posées dans
ce forum.
Remarque sur la notation : le signe de multiplication utilisé ici est
l'astérisque *, comme souvent en informatique.
La version texte de ce document a été divisée en trois parties, afin de
faciliter sa difusion sur les forums francophones.
On trouvera, dans cette partie, les chapitres V à VII inclus.
Pour les chapitres I et II, se referer au document intitulé :
"[FAQ] fr.sci.maths - partie 1/3".
Pour les chapitre III et IV, se referer au document intitulé :
"[FAQ] fr.sci.maths - partie 2/3".
Table des matières :
I Contradictions.
1. Est-ce que 0,9999... = 1 ?
2. J'ai réussi à montrer que 2=1.
3. Zéro puissance zéro égal un (0^0 = 1).
II Démonstrations.
1. Le petit théorème de Fermat.
2. ab et a+b premiers entre eux.
3. Irrationalité de la racine carrée de 2.
4. Irrationalité de la racine d'un nombre premier.
5. Irrationalité de e.
6. Transcendance de e.
7. Somme des puissances des premiers entiers.
8. Les nombres et les polynômes de Bernoulli.
9. Par combien de zéros le nombre 1998! se termine-t-il ?
10. Expression par radicaux des racines d'un polynôme de degré n.
-+- Début de la deuxième partie -+-
III Géométrie.
1. Problème de la chèvre.
2. Problème (dit) de Napoléon.
IV Énigmes.
1. Pièces et balance, traduit par Vincent Lefèvre.
2. Les âges du capitaine.
3. Quel est le nombre qui continue cette suite : 2, 12, 1112,...
4. Probabilité que 2 personnes soient nées le même jour.
5. Somme et produit de deux entiers.
6. Les deux échelles.
7. La cuve de vin.
-+- Début de la troisième partie -+-
V Questions fondamentales.
1. Les nombres premiers.
2. Pi.
3. Le grand théorème de Fermat.
4. La conjecture de Syracuse.
5. Les cardinaux des ensembles infinis - Partie I.
6. Les cardinaux des ensembles infinis - Partie II.
7. Qu'est-ce que le nombre e ?
VI Mathématiques et Ordinateur.
1. Logiciels de mathématiques.
2. L'algorithme de CORDIC sur les calculatrices.
VII Conclusion.
1. Références.
2. Remerciements.
========================================================================
Changements intervenus depuis la version précédente :
- Mises à jour ou suppression des liens morts.
- Rééquilibrage des trois parties pour tenir dans la limite de 64ko.
- Révision du paragraphe I.3.
- Suppression du paragraphe VI.1 de Frédéric Bastok (double-emploi
avec le document posté chaque quinzaine).
- Réécriture du paragraphe VI.2 (maintenant VI.1), qui était dépassé
et étrangement structuré.
- Autres détails cosmétiques.
Les changements sont précédés du caractère : |
========================================================================
V Questions fondamentales.
========================
1. Les nombres premiers.
---------------------
Définition :
- Un nombre premier est un entier possédant exactement 2 diviseurs.
(ces deux diviseurs sont donc 1 et lui-même).
A noter que la définition de nombre premier exclut 1. Admettre 1 comme
nombre premier rendrait faux l'important "Théorème fondamental de
l'arithmétique" qui dit qu'il existe une unique manière d'écrire un
nombre entier supérieur à 1 comme produit de nombres premiers (sans
prendre en compte l'ordre de la multiplication).
a) En existe-t-il une infinité ?
Oui. En voici une démonstration par l'absurde. Noter qu'après le
Théorème de Pythagore, c'est sûrement le résultat mathématique pour
lequel on connaît le plus de démonstrations différentes.
Supposons qu'il n'en existe qu'un nombre fini n, qui seraient
p_1, p_2,..., p_n. Le produit p_1*...*p_n est divisible par chacun
de ces premiers p_1,..., p_n. Cela signifie que p_1*...*p_n+1 n'est
divisible par aucun d'entre eux. Donc le plus petit diviseur
(excepté 1) de ce nombre, qui est forcément un nombre premier, n'est
ni p_1, ni p_2,..., ni p_n. Notre liste ne peut donc pas être
complète, il doit donc exister une infinité de nombres premiers.
b) Quel est le plus grand que l'on connaisse ?
| Actuellement (attention, les records tombent vite!), le plus grand
| nombre premier connu est 2^32582657 - 1 qui a été découvert en 2006
| dans le cadre du projet GIMPS. Il a 9808358 chiffres décimaux. Ce
| nombre est le quarante-quatrième nombre de Mersenne connu.
| (Source : http://www.utm.edu/research/primes/largest.html)
c) Polynôme donnant l'ensemble des nombre premiers.
Il existe un polynôme à coefficients entiers à 26 variables tel que
l'ensemble des nombres premiers coïncide avec l'ensemble des valeurs
**positives** prises par P(a,b,c,...x,y,z) lorsque les 26 variables
a,b,c,...,x,y,z parcourent N.
Ce polynôme s'écrit:
P(a,b,...,y,z) = (k+2) * {1 - [wz+h+j-q]^2 - [(gk+2g+k+1)(h+j)+h-z]^2
- [2n+p+q+z-e]^2 - [16((k+1)^3)(k+2)((n+1)^2) + 1 - f^2]^2
- [(e^3)(e+2)((a+1)^2) +1 -o^2]^2 - [(a^2-1)(y^2)+1-x^2]^2
- [16(r^2)(y^4)(a^2-1) +1 -u^2]^2 - [((a+(u^2)
(u^2-a))^2-1)(n+4dy)^2+1-(x+cu)^2]^2 - [n+l+v-y]^2
- [(a^2-1)l^2+1-m^2]^2 - [ai+k+1-l-i]^2
- [p+l(a-n-1)+b(2an+2a-n^2-2n-2)-m]^2 -[q+y(a-p-1)
+ s(2ap+2a-p^2- 2p-2)-x]^2-[z+pl(a-p)+t(2ap-p^2-1)-pm]^2}
Rendre P(a,...,z) positif revient à annuler simultanément chacun des
crochets dans le " long " facteur {1 - [...]^2 - ... - [...]^2}.
Ce facteur se réduit alors à 1, tandis que les conditions ainsi
imposées à k font que le facteur " court ", à savoir (k+2),
est premier.
On peut lire dans " l'Abrégé d'Histoire des Mathématiques "
de Jean Dieudonné (pages 232 et suivantes) l'existence d'un polynôme
à 21 variables ayant la même forme et les mêmes propriétés que le
polynôme déjà cité.
Pour ceux qui voudraient s'initier à ce genre de mathématiques,
On peut lire:
-- l'article "Diophantine Decision Problems",
de la regrettée Julia Robinson, pages 76 à 116
du livre "Studies in Number Theory", volume 6 des MAA Studies
in Mathematics, édité (au sens scientifique du terme)
par W.J. LeVeque.
-- "Little book of big primes" de Paulo Ribenboim.
-- "book of prime numbers records"
Annexe: Dans le même ordre d'idée il existe un polynôme dont
les valeurs positives donnent les nombres de Fibonacci :
f(x,y) = 2 x(y^4) + (x^2)(y^3) - 2(x^3)(y^2) - (y^5) - y(x^4) + 2 y
d) Nombres de Mersenne et nombres premiers.
Au sujet du projet GIMPS (Great Internet Mersenne Prime Search), ce
projet consiste à chercher le plus grand nombre premier sous la
forme d'un nombre de Mersenne (Les nombres de Mersenne sont les
nombres premiers du type 2^p - 1 où p est lui-même premier).
Le 38ième nombre de Mersenne a été trouvé le 1er juin 1999 par
l'équipe de Nayan Hajratwala, George Woltman et Scott Kurowski. il
s'agit de 2^6972593 - 1. Ce nombre compte 2,098,960 décimales.
Trouverez vous le 39ième nombre de Mersenne ?
Vous pouvez vous aussi participer à ce grand projet en faisant
tourner sur votre machine (quelle que soit la plateforme) le
programme qui a été développé pour ce projet. C'est un programme que
vous pouvez faire tourner en tâche de fond et qui utilise les cycles
CPU non utilisés (donc cela ne ralentira pas votre ordinateur).
C'est un projet de recherche à plusieurs qui utilise les résultats
fournis par les 4200 participants pour déterminer quels nombres
restent à tester,... C'est un projet qui se fait en collaboration,
celui qui a la chance de trouver un nombre de Mersenne inscrit
définitivement son nom dans l'histoire des maths... (et gagne aussi
10 000 $ je crois, mais j'espère que vous ne ferez pas ça pour
l'argent).
Plus de renseignements sur: http://www.mersenne.org/prime.htm
ou en français (miroir officiel) sur:
http://www.mersenne.org/french_prime.htm
2. Pi.
---
a) Algorithmes de calculs de décimales.
C'est Archimede (en 225 avant JC) qui calcula le premier algorithme
sur les décimales de Pi.
| On trouve sur Internet de nombreux recueils de formules et méthodes
| permettant de calculer des décimales. Par exemple :
| http://www.peripheria.net/calcul/
| ou encore le site très complet de Boris Gourévitch :
| http://www.pi314.net/
b) l'algorithme de Bailey, Borwein et Plouffe ?
C'est pour calculer pi en base 16 (il y a une version en base 10,
mais beaucoup plus lente). L'intérêt, c'est qu'on peut calculer un
chiffre sans devoir déterminer tous les précédents.
| Voir par exemple les pages web précédentes, ou encore :
| http://fr.wikipedia.org/wiki/Formule_BBP
| http://www.joyofpi.com
J.P. Delahaye a écrit un très beau livre sur le sujet:
"Le Fascinant nombre Pi" aux éditions Belin - Pour la science.
3. Le grand théorème de Fermat.
----------------------------
a) Enoncé.
Le " grand " ou " dernier " théorème de Fermat dit ceci:
alors qu'il existe des carrés qui sont somme de deux carrés
(par exemple 5² = 3² + 4², 13² = 12² + 5²), il n'existe aucun cube
(non nul) qui soit somme de deux cubes (non nuls).
De même, il n'existe aucune puissance quatrième qui soit somme de
deux puissances quatrièmes (non nulles), etc.
En général, pour n > 2, il n'existe aucun triplet (x, y, z)
d'entiers non nuls, tels que x^n + y^n = z^n.
C'est à dire, traduit en langage mathématique :
pour n > 2 l'équation x^n + y^n = z^n n'a pas de solution entière
non triviale.
b) Histoire liée au théorème.
Contrairement au petit théorème, il s'agit d'un résultat extrêmement
difficile, dont Fermat n'a pas publié de démonstration, et qu'il n'a
probablement pas démontré. Fermat n'a même jamais affirmé
publiquement l'avoir démontré. Il écrivit dans une marge du livre II
des Oeuvres de Diophante:
" j'ai découvert une démonstration merveilleuse, mais je n'ai pas
la place de la mettre dans la marge ".
Le livre et cette annotation ont été publiés après sa mort, par son
fils.
En dépit de la simplicité de son énoncé, ce théorème est tellement
difficile à prouver que les plus grands mathématiciens s'y sont
cassé les dents pendant 358 ans exactement, d'après le livre de
Simon Singh. On notera cependant, que :
-> Euler (1707-1783) le démontre pour n = 3 et ses multiples
-> Legendre (1752-1833) pour n = 5
-> Kummer (1810-1893) pour tout n tel que 2<n<100
| En 1995, une démonstration est enfin publiée:
celle d'Andew Wiles (1953-).
c) Références.
Voici une page bien documentée sur le sujet (Warning in english!)
http://www.best.com/~cgd/home/flt/flt01.htm
Simon Singh a écrit un très beau livre :
_Le dernier Théorème de Fermat_ aux éditions JC Lattès,
à partir d'un documentaire qu'il devait réaliser sur le sujet
pour la BBC. C'est principalement un roman.
Dans un genre plus mathématiques, on pourra consulter avec profit le
livre de Yves Hellegouarch :
_Invitation aux mathématiques de Fermat-Wiles_ aux éditions Masson,
très bien fait, mais demandant un niveau licence ou maîtrise de
mathématiques, pour en comprendre toutes les finesses.
4. La conjecture de Syracuse.
--------------------------
a) Présentation de la conjecture.
Le problème de la conjecture de Syracuse, également connue sous les
noms de problème de Collatz, Kakutani, ou Ulam, se présente de
manière très simple.
On se donne une entier naturel n plus grand que 1. S'il est pair,
on le divise par deux, s'il est impair, on le multiplie par 3 et on
lui ajoute 1 (ce qui revient à lui appliquer la fonction x |-> 3x+1).
On >conjecture< que l'on finit toujours par trouver la valeur 1 au
fil des calculs, valeur à partir de laquelle on restera bloqué dans
le cycle 1-4-2-1-...
Cependant, le fait que l'on retrouve toujours 1 n'a pas été démontré
et même si on est presque sûr que cela est vrai, quel que soit
l'entier n choisi au départ, il n'est pas exclu qu'il existe un
entier n ne vérifiant pas cette propriété, d'où le nom de :
>conjecture< de Syracuse.
Depuis plusieurs dizaines d'années, ce problème est activement
étudié par les mathématiciens, mais n'a pas encore été résolu.
Les recherches ont cependant bien avancé, comme nous allons le voir
plus loin.
b) Une métaphore éclairante.
Comment souvent, les mathématiciens, en travaillant sur ce problème,
ont senti que certaines idées étaient récurrentes etont introduit un
vocabulaire adapté pour décrire les phénomènes étudiées.
Imaginons que l'on vérifie la propriété pour n=15. On obtient :
46, 23, 70, 35, 106, 53, 160, 80, 40, 20, 10, 5, 16, 8, 4, 2, 1.
On appelle cette suite finie d'entiers le VOL, ou la TRAJECTOIRE de
15. Il faut imaginer une représentation de cette suite sur un
graphique, l'axe des abscisses figurant l'indice de chaque entier
dans la suite, l'axe des ordonnées indiquant l'entier correspondant.
On appelle ETAPE, un nombre de cette suite finie. Ici, par exemple,
80 est une étape du vol de 15.
Si la conjecture est vraie, on remarque que la suite atteint une
étape maximale, appelé ALTITUDE MAXIMALE du vol. Ici, l'altitude
maximale était 160.
On définit également la DUREE de chaque vol comme le nombre d'étapes
à franchir avant d'arriver pour la première fois au chiffre 1, et la
durée de VOL EN ALTITUDE comme la durée entre le moment où le
vol commence, et celui où il repasse sous sa valeur initiale.
c) Des avancées intéressantes.
A partir de là, il est plus facile de comprendre les dernières
avancées dans la résolution du problème. Il a été ainsi démontré que
chacune des propositions suivantes était équivalente à l'énoncé de
la conjecture de Syracuse elle-même :
(1) Tout vol a une durée finie
C'est en gros l'énoncé de la conjecture en elle-même.
(2) Tout vol est de durée en altitude finie
En effet, si ceci est vrai, alors on conclut sur notre problème par
récurrence. Pour n=2 on finit par retomber sous 2, c'est à dire à 1.
Supposons que n et tous les entiers plus petits quelui vérifient la
conjecture. Démontrons que c'est alors le cas de n+1 :
Le vol n+1 a une durée en altitude finie, donc, au cours des
calculs, on arrive à n, ou à un entier inférieur, que l'on note i.
Mais i vérifie la conjecture, donc il aboutit au cycle 4-2-1. Ainsi
n+1 aboutit-il aussi à ce cycle. Réciproquement, si la conjecture
est vraie, la propriété (2) est bien entendue vraie.
(3) Tout vol a un nombre fini d'étapes paires (resp. impaires)
On considère le vol n. Après un certain nombre d'étapes, on atteint
un dernier nombre pair. On le divise par deux, et on obtient un
impair. Mais, si on applique x -> 3x+1 à cet impair, on obtiendra un
pair, ce qui contredit le fait qu'on ait dépassé les dernier pair,
sauf si le nombre impair que l'on vient de trouver est 1.
Alors on s'arrête dans les calculs, et n vérifie la conjecture, qui
de ce fait est vraie.
(4) Tout vol a un nombre fini d'étapes paires (resp. impaires) en
altitude
Démonstration analogue.
Les mathématiciens désespèrent quant au fait de démontrer
directement la conjecture elle-même, et pensent qu'il est moins
difficile de montrer que l'une de ces propriétés, équivalentes au
problème, est vraie.
On sait par ailleurs montrer que la propriété est vraie pour un très
grand nombre d'entiers. On considère par exemple n = 4*k + 1.
En effectuant les calculs, on trouve qu'il devient 12*k+4, 6*k+2,
3*k+1, ce dernier entier étant plus petit que n.
Pour n = 4*k, on descend sous n dès la première étape du calcul. De
même que pour 4k + 2.
Il suffirait donc de pouvoir montrer que 4k+3 a lui aussi une durée
de vol en altitude finie pour conclure que la conjecture est vraie !
On peut affiner ce type de démonstration. En travaillant avec les
entiers du type 65536*k + i (avec i compris entre 0 et 65535), tous
les cas aboutissent sauf 1729 cas, donc il ne reste que 2,6% des
nombres à étudier.
Des développements plus récents ont montré que pour n assez grand,
il existait une constante alpha telle que au moins n^alpha des
entiers inférieurs à n possèdent la propriété de Syracuse.
En 1995, J. Lagarias et D. Applegate démontrèrent ce résultat pour
la constante alpha=0,81. Mais leurs calculs furent menés avec des
ordinateurs et sont invérifiables à la main.
d) Les records établis
Les records enregistrés au fur et à mesure des recherches ont été
soigneusement consignés.
C'est à T. Oliveira e Silva que l'on doit les records les plus
récents et les plus significatifs. Les records suivants proviennent
de sa page web :
Le plus grand nombre testé est : 77 * 2^50 = 86694292826882048.
La conjecture a été vérifiée par deux fois avec des ordinateurs
jusqu'à n = 2^51 = 2251799813685248.
Le record de l'altitude maximale est tenu par le vol
82450591202377887, qui atteint l'entier :
875612750096198197075499421245450.
D'autres records, datant de 1998 et sans doute améliorés depuis :
Celui de vol de durée record en vol est celui du vol
100759293214567, de durée 1820 (c'est assez faible, on aurait pu
croire que des entiers résisteraient plus).
Enfin celui de durée en altitude record est le vol 70665924117439,
dont la durée en altitude est de 1177 étapes.
e) Données heuristiques et indécidabilité du problème
Si l'on étudie la façon dont les entiers évoluent en terme de parité
au cours d'un calcul de Syracuse, on peut avoir une idée de son
temps de vol.. Ainsi, si l'on obtient souvent des nombres pairs,
ils vont être divisés par deux, et on arrivera plus rapidement à 1
(en admettant qu'on arrive toujours à 1).
En tenant compte du fait qu'un nombre impair donne un nombre pair et
que ce dernier va être divisé par deux ensuite, et qu'il y a dans
l'ensemble des entiers naturels autant de pairs que d'impairs, on
estime, au moyen d'un calcul probabiliste, qu'un entier donné est en
moyenne multiplié par 3/4 lorsqu'on effectue une étape du calcul.
Ceci tend à confirmer la conjecture. Expérimentalement, ce résultat
de 3/4 est très bien confirmé, et le modèle statistique semble
performant.
Cependant, certains mathématiciens sont arrivés à se poser la
question de l'indécidabilité du problème. Ils ont proposé quelques
extensions du problème : autoriser les entiers négatifs, ou
remplacer 3x+1 quand x est impair par qx+1 avec q un entier impair
donné. Pour certaines valeurs de q>3, la conjecture n'est pas vraie.
Mais c'est J. Conway qui a semé le doute. Plutôt que de ce demander
si un entier donné, au cours du calcul, était pair ou impair, c'est
à dire avait 0 ou 1 pour reste par la division euclidienne par 2,
il s'intéresse au reste par la division euclidienne par un entier p
et propose alors p formules à employer pour effectuer les calculs
selon ce que ce reste soit 0, 1, 2, .., ou p-1. Il a montré que si
alors on étendait la conjecture de Syracuse, on arrivait à un
problème indécidable.
Finalement, on a vu que beaucoup de résultats tendent à nous faire
penser qu'il est >presque< impossible que la conjecture soit fausse.
Cependant, il est arrivé dans l'histoire que les mathématiciens
aient une telle intuition très forte en faveur d'une conjecture et
qu'elle soit en fait fausse. Les résultats de J. Conway montrant que
des problèmes très similaires sont indécidables incitent donc à la
prudence !
f) Bibliographie
"La conjecture de Syracuse", par Jean-Paul Delahaye
in: _Pour La Science_ N°247 de mai 1998.
Et sur le web :
| "The 3x+1 problem and its generalizations" par Jeff Lagarias :
| http://www.cecm.sfu.ca/organics/papers/lagarias/
5. Les cardinaux des ensembles infinis - Partie I.
-----------------------------------------------
a) Avertissement
Le sujet est vaste et peut intéresser des gens de niveaux divers
(à partir du lycée et bien au-delà). C'est pourquoi cet article est
découpé en 2 parties. La première s'adresse au niveau pré-bac, la
seconde est accessible à partir du DEUG, environ.
Dans la première partie, l'accent est mis sur la "vulgarisation",
parfois au détriment de la rigueur : pour éviter des complications
techniques, certaines démonstrations sont "un peu fausses", tout en
donnant l'idée principale de la méthode. Chaque fois que c'est le
cas, c'est signalé, et on peut se reporter à la seconde partie pour
trouver une démonstration (à priori) rigoureuse.
La seconde partie complète la première, avec des outils plus abstraits
et plus puissants. Elle s'efforce à la rigueur, mais elle peut
comporter des erreurs ou imprécisions.
Merci enfin à David Madore (David.Madore@ens.fr), spécialiste du
sujet, d'avoir corrigé et complété une première mouture de cet article.
Merci également à tous les lecteurs de fr.sci.maths qui m'ont indiqué
des corrections diverses.
Rappel : N : ensemble des entiers naturels = {0,1,2,3,...}
Z : ensemble des entiers relatifs (signés) = {...,-1,0,1,...}
Q : ensemble des nombres rationnels (fractions)
R : ensemble des nombres réels
C : ensemble des nombres complexes
L'étoile signifie que l'ensemble est privé de 0 (N*={1,2,3,...}).
Voici d'abord les résultats essentiels, qui seront suivis par quelques
explications :
_ N, Z, Q ont autant d'éléments
_ R, C ont autant d'éléments
_ Les 3 premiers ont moins d'éléments que les 2 derniers.
La notion de cardinal étend la notion de nombre aux infinités, de
façon à ce que l'on puisse comparer les ensembles infinis.
Voici comment.
b) Cardinal d'un ensemble fini
Pour un ensemble fini, le cardinal est une notion intuitive, c'est
simplement le nombre d'éléments de l'ensemble. Il appartient à N.
Ex : Card {1,2,3} = 3 = Card {6,15,28}
(*) Opérations sur les cardinaux (finis) :
--------------------------------------
(1) Si A et B sont deux ensembles finis *disjoints* alors
Card (A Û B) = Card A + Card B
où Û désigne l'union disjointe.
Ex : A = {1,2,3} Card A = 3
B = {8,9} Card B = 2
A Û B = {1,2,3,8,9} Card(A Û B) = 5 = 3+2.
(2) Si A et B sont deux ensembles finis, alors
Card (A × B) = (Card A) . (Card B)
où A × B désigne le produit cartésien des ensembles A et B.
Ex : A = {1,2,3} Card A = 3
B = {a,b} Card B = 2
A × B = { (1,a), (1,b), (2,a), (2,b), (3,a), (3,b) }
Card (A × B) = 6 = 3x2.
(3) Si A est un ensemble fini on note P(A) l'ensemble des parties de A,
c'est a dire l'ensemble des sous-ensembles de A.
alors Card P(A) = 2^(Card A)
En effet : pour constituer une partie B de A, il y a un choix à
faire pour chaque élément de A : soit on le met dans B,
soit on ne l'y met pas (2 possibilités).
S'il y a n éléments dans A, cela donne 2^n possibilités
pour B, soit 2^n parties différentes.
Ex : A = {1,2,3} Card A = 3
P(A) = { Ø, {1}, {2}, {3}, {1,2}, {2,3}, {1,3}, {1,2,3} }
Card P(A) = 8 = 2^3
Ce sont ces propriétés (1), (2), (3) qu'on va vouloir généraliser aux
ensembles infinis.
-----
Pour un ensemble infini, l'intuition ne s'applique plus : il faut
recourir à des définitions formelles. C'est Cantor qui, le premier,
a fourni un système cohérent permettant de traiter les ensembles
infinis.
c) Définition rigoureuse d'un ensemble infini :
Une bijection f entre 2 ensembles E et F est une application qui fait
correspondre à chaque élément de E un unique élément de F
et inversement.
S'il existe une bijection entre E et F, on dit que E et F sont
équipotents et on note : E ~ F.
Un ensemble est dit fini s'il est en bijection avec un ensemble
A_n = {1, 2, 3, ..., n} avec n un entier naturel (et A_0 = Ø).
Alors Card(E) = n, et on retrouve la notion intuitive.
Un ensemble E qui ne peut pas être mis en bijection avec un tel ensemble
A_n est dit infini.
Ex : N est un ensemble infini.
d) Cardinal d'un ensemble infini :
On étend la notion de cardinal aux ensembles infinis de la façon
suivante (schématiquement ; pour plus de rigueur voir partie II) :
1. Si 2 ensembles sont équipotents (en bijection), on dit qu'ils ont
le même cardinal.
2. On dit que Card E <= Card F si E a même cardinal qu'une partie de F.
En particulier, si un ensemble infini E est inclus dans un ensemble
(infini) F alors Card E <= Card F (inégalité large).
Ex. (règle 1) :
Card Z = Card N car il existe (au moins) une bijection de N
dans Z, qu'on peut expliciter :
g : n --> n/2 si n est pair
n --> -(n+1)/2 si n est impair
ce qui donne 0 --> 0
1 --> -1
2 --> 1
3 --> -2
...
Ex. (règle 2) : Card N <= Card Z <= Card Q <= Card R <= Card C.
e) Quelques résultats sur les ensembles dénombrables
On a vu Card N = Card Z. Établissons quelques autres résultats :
(*) Card N = Card (N^2)
On peut en effet compter les éléments de N^2 = { (a,b) | a,b dans N }.
Une bijection possible de N^2 dans N est le "comptage en diagonale" :
(0,0) --> 0
(1,0) --> 1
(0,1) --> 2
(2,0) --> 3
(1,1) --> 4
(0,2) --> 5
...
(on compte les points de N^2 selon les diagonales bas-droite ->
haut gauche, en s'éloignant de l'origine).
On peut même expliciter la bijection :
(p,q) --> (p+q).(p+q+1)/2 + q
De même, on a Card (Z^2) = Card Z.
(*) Card (Z) = Card Q
Essentiellement, une fraction p/q est un couple d'entiers relatifs
(p,q). Cette égalité n'est donc pas particulièrement surprenante
quand on a admis Card (Z^2) = Card Z.
Formellement, la démonstration est un peu technique : elle est
donc donnée dans la deuxième partie.
On a donc : Card N = Card Z = Card Q.
Ce cardinal est noté aleph_0.
(aleph est la première lettre de l'alphabet hébreu).
Tous les ensembles infinis qui ont le même cardinal que N sont dits
dénombrables.
Au sens large, "dénombrable" signifie aussi "fini ou dénombrable".
Enfin, un ensemble qui n'est ni fini ni dénombrable est dit...
indénombrable.
f) Quelques résultats sur les ensembles indénombrables
Plaçons nous maintenant dans les réels.
(*) Card [0,1] = Card [0,2] = Card [a,b] = ...
Il est facile de trouver une bijection de [0,1] dans [0,2] :
k : x --> 2x par exemple.
De même, on peut toujours trouver une bijection entre 2 intervalles
de R, ouverts ou fermés.
Tous les intervalles de R ont donc le même cardinal.
(*) Card (a,b) = Card R
(a,b) désigne l'intervalle, sans se préoccuper de l'inclusion ou non
des bornes.
La fonction tangente, par exemple, fournit une bijection
de ]-pi/2,pi/2[ dans R.
En appliquant ce qui précède, tout intervalle de R a le même
cardinal que R.
(*) Card ([0,1[^2) = Card [0,1[
En effet on peut expliciter une bijection de [0,1[^2 dans [0,1[ :
Soit (a,b) dans [0,1[^2. Écrivons leur développement décimal :
a = 0, a1 a2 a3 a4 ...
b = 0, b1 b2 b3 b4 ...
formons alors c = 0, a1 b1 a2 b2 a3 b3 a4 b4 ...
N'est-il pas alors clair que la fonction l : (a,b) --> c
est une bijection de [0,1[^2 dans [0,1[ ?
[en fait, pas tout a fait : il y a une lacune, expliquée dans la
seconde partie, mais ça ne change pas le résultat]
Grâce à ce qui précède on déduit que :
Card R = Card [0,1[ = Card ([0,1]^2) = Card R^2.
On peut démontrer la même chose avec n'importe quel exposant à la
place de 2.
(*) Card C = Card R
En effet, les fonctions partie réelle et partie imaginaire d'un
complexe fournissent une bijection évidente de C dans R^2.
Avec ce qui précède on a donc Card C = Card R^2 = Card R.
g) Rapport dénombrable/indénombrable
On va maintenant voir que R n'est pas dénombrable.
Pour simplifier, on va montrer que [0,1[ n'est pas dénombrable ;
ce qui implique, bien sûr, que R ne l'est pas.
Supposons le contraire : on peut alors énumérer [0,1[, c'est-à-dire
qu'il existe une suite (u_n), n dans N, qui contient tous les réels
de [0,1[.
Écrivons le développement décimal (par exemple) des premiers termes
de (u_n) en notant u_n,i le i-ème chiffre après la virgule de u_n :
u_1 = 0, u_1,1 u_1,2 u_1,3 u_1,4 ...
u_2 = 0, u_2,1 u_2,2 u_2,3 u_2,4 ...
...
u_n = 0, u_n,1 u_n,2 u_n,3 u_n,4 ...
...
On forme maintenant le nombre v s'écrivant :
v = 0, u_1,1 u_2,2 u_3,3 u_4,4 ... u_i,i ...
(on prend les chiffres de la diagonale principale ci-dessus)
On forme enfin le nombre w en remplaçant chaque chiffre de v par
son prédécesseur (et 0 par 8) :
w = 0, w_1 w_2 w_3 w_4 ...
avec :
w_i = 8 si u_i,i = 0
w_i = u_i,i - 1 sinon
Alors le nombre w, qui est bien défini, n'est pas dans la liste des
valeurs parcourues par (u_n). En effet :
w_1 (le premier chiffre de w après la virgule) est différent de
u_1,1 (le premier chiffre de u_1 après la virgule) donc w <> u_1.
w_2 <> u_2,2 donc w <> u_2
...
w_n <> u_n,n donc w <> u_n pour tout n.
On a donc construit un réel de [0,1[ qui n'est pas dans (u_n) :
contradiction avec l'hypothèse.
Une telle suite u_n parcourant tous les réels de [0,1[ n'existe
donc pas, donc [0,1[ est indénombrable.
La technique qui nous a permis de le montrer est classique, et connue
sous le nom de "Procédé diagonal de Cantor".
h) Conclusion :
Tout ceci nous permet d'écrire :
Card N = Card Z = Card Q < Card R = Card C.
Pour d'autres développements, et des justifications plus rigoureuses,
voir la partie II.
6. Les cardinaux des ensembles infinis - Partie II.
------------------------------------------------
a) Autre définition rigoureuse d'un ensemble infini :
Une définition équivalente (moyennant l'axiome du choix) à celle
de la première partie est :
Un ensemble E est dit infini si on peut trouver une bijection entre
lui-même et une de ses parties (strictes) F, ie :
F inclus dans E, F <> E, F ~ E.
Ex : N est en bijection avec N*, par la fonction f : n --> n+1
ainsi, N est infini
b) Cardinal d'un ensemble infini :
La façon parfaitement rigoureuse de définir le cardinal pour un
ensemble infini s'appuie sur le théorème de Cantor-Bernstein :
Thm : Soient A et B deux ensembles (finis ou infinis).
Si A s'injecte dans B et B s'injecte dans A, alors
A et B sont équipotents.
(la démonstration est facile dans le cas fini, un peu moins dans le
cas général).
Ce théorème justifie les écritures :
Card(A) = Card(B) si A et B sont équipotents
Card(A) <= Card(B) si A s'injecte dans B
En effet, on peut alors appliquer la règle d'antisymétrie :
si n <= m et m <= n alors n = m.
Écrire cette règle avec les cardinaux infinis est une simple
ré-écriture du théorème de Cantor-Bernstein.
D'autre part, on a l'équivalence (moyennant l'axiome du choix) :
- A s'injecte dans B
- B se surjecte sur A
et en notant Card(B) >= Card(A) si B se surjecte sur A,
on reste cohérent en manipulant les cardinaux.
Pour la culture (merci à David Madore) :
Si A et B sont deux ensembles quelconques, alors soit A s'injecte
dans B (ie Card(A) <= Card(B)), soit B s'injecte dans A
(ie Card(B) <= Card(A)).
En d'autres termes : les cardinaux forment une classe "totalement
ordonnée".
c) Quelques précisions sur les ensembles dénombrables
(*) Card (Z^2) = Card Q
On a une injection évidente f : Q --> Z^2 :
f(p/q) = (p,q)
avec p,q premiers entre eux et q>0
[on peut rajouter f(0)=(0,1) pour être parfaitement rigoureux]
Évidemment, ce n'est pas une bijection : (4,6) par exemple n'a pas
d'antécédent, puisque f(4/6) = (2,3).
On a donc Card Q <= Card(Z^2).
D'autre part, on a vu dans la première partie : Card (Z^2) = Card Z.
Or Z s'injecte trivialement dans Q : Card Z <= Card Q.
De ces deux inégalités on déduit Card (Z^2) = Card Q, alors qu'il
serait fastidieux d'exhiber une bijection explicite entre Q et Z^2.
d) Quelques précisions sur les ensembles indénombrables
(*) Card ([0,1[^2) = Card [0,1[
En fait, l'application l donnée dans la partie I n'est pas vraiment
une bijection, mais seulement une injection. Cela est dû à l'existence
de deux écritures décimales distinctes pour les décimaux : l'une
avec un nombre fini de chiffre (ex : 1,23), l'autre avec un nombre
infini de chiffres (ex : 1,2299999...) [Voir la FAQ 0,999...=1].
En conséquence, le nombre 0,50595959... par exemple n'a pas
d'antécédent puisque:
l(0,555... , 0,099...) = l(0,555.. , 0,1) = 0,51505050...
Cependant, ça suffit : l nous fournit une injection de [0,1[^2 dans
[0,1[, et l'injection réciproque est triviale. En appliquant le
théorème de Cantor-Bernstein on peut donc conclure en toute rigueur
que Card([0,1[) = Card([0,1[^2).
La généralisation à Card R = Card (R^2), se fait toujours comme
indiqué dans la première partie.
e) Rapport dénombrable/indénombrable
Voici une démonstration plus indirecte du fait que R est indénombrable,
mais qui a l'avantage de préciser le rapport entre les 2,
à savoir R ~ P(N), l'ensemble des parties de N.
(*) Soit E un ensemble. P(E) n'est jamais équipotent à E.
En voici une (jolie) démonstration par l'absurde.
Supposons qu'il existe une bijection h : E --> P(E)
Pour tout x dans E, h(x) est un sous-ensemble de E.
Notons F = { x dans E | x n'est pas dans h(x) }.
Par construction, F est une partie de E, donc F est dans P(E).
Comme h est une bijection, F a un antécédent dans E, ie :
il existe y dans E tel que h(y) = F = {x dans E | x n'est pas dans h(x)}
Alors :
- si y est dans F, par définition de F, y n'est pas dans h(y)=F.
Absurde.
- si y n'est pas dans F, par définition de F, y est dans h(y)=F.
Absurde aussi.
C'est donc l'hypothèse d'existence de la bijection h qui est fausse.
Cqfd.
(*) Card P(N) = Card R
On constitue donc l'application p : P(N) --> R de la façon suivante.
Soit E dans P(N). E est donc un sous-ensemble (fini ou infini) de N.
On forme un nombre d écrit en base 2 de la façon suivante :
d = 0, d0 d1 d2 d3 d4 d5...
où dn = 1 si n est dans E, 0 sinon
On a alors d dans [0,1], de façon claire (d=0 si E=@, d=1 si E=N).
[On peut définir p de façon plus concise :
p(E) = \somme_{n dans E} 2^-(n+1)]
La fonction p : E --> p(E)=d est alors une surjection de P(N) dans R.
[Tout réel r de [0,1] est atteint, et pour connaître son antécédent,
il suffit d'écrire le développement binaire de r.
En revanche, p n'est pas une bijection, en raison de l'existence de
2 développements binaires, comme pour les développements décimaux.]
D'autre part, si on fabrique l'application q comme p, mais en
considérant que cette fois d est écrit en base 3 (ou 10, ou n>2),
alors l'application q est une injection de P(N) dans R.
[Tous les réels ne sont pas atteints, mais chaque réel atteint a un
antécédent unique.]
P(N) se surjecte et s'injecte à la fois dans R, donc P(N) ~ R :
Card P(N) = Card R
Par généralisation du cas fini, on écrit :
Card R = Card P(N) = 2^(Card N) = 2^(aleph_0)
(*) Card N < Card R
En effet, puisque N est inclus (donc s'injecte) dans R,Card N <= Card R.
De plus, on vient de montrer que Card R = Card P(N), et que P(N)
n'est pas équipotent à N. Donc Card N < Card R.
f) Hypothèse du Continu...
On définit aleph_1 comme étant le plus petit cardinal strictement
supérieur à aleph_0 (pour une définition plus rigoureuse de aleph_1,
voir l'article de David Madore :
http://www.eleves.ens.fr:8080/home/madore/w/ordinals/ordinals.html)
Le fait de savoir si Card R = aleph_1 est indécidable d'après la
construction de R seule, c'est à dire qu'on peut arbitrairement
décider que oui ou non.
Habituellement, on fait l'hypothèse que c'est bien le cas
(hypothèse du Continu) : aleph_1 = Card R.
En termes plus simples, l'hypothèse du Continu dit que :
toute partie de R est soit au plus dénombrable, soit équipotente à R.
En termes intuitifs (!) : il n'existe pas d'ensemble "strictement
plus gros" que N mais "strictement plus petit" que R.
g) Opérations sur les cardinaux
Toutes les opérations valables avec les cardinaux finis, sont
extensibles aux cardinaux infinis, mais l'intérêt est moindre :
Si A ou B est infini :
Card (A Û B) = Card A + Card B = Max (Card A , Card B)
Card (A × B) = Card A . Card B = Max (Card A , Card B)
Card (P(A)) = 2^Card(A)
L'hypothèse du Continu "dit" ainsi que aleph_1 = 2^aleph_0.
h) Références
-- Initiation à la théorie des ensembles, J. Breuer
Dunod, 1961
-- Théorie axiomatique des ensembles, Jean-Louis Krivine,
Presses Universitaires de France, 1972 (niveau maîtrise)
voir aussi :
-- Théorie des ensembles, Jean-Louis Krivine, Vuibert, 1998
7. Qu'est-ce que le nombre e ?
---------------------------
a. le point de vue Néperien.
On pose ln(e) = 1.
Il suffit d'expliquer comment on définit naturellement la fonction
logarithme, et tu comprendras pourquoi e est e.
La fonction ln se définit (à une constante près) par la propriété :
ln(xy)=ln(x)+ln(y).
En dérivant cette relation, on vérifie que :
y ln'(xy))= ln'(x). Donc : ln'(y) = ln'(1)/y.
On définit donc la fonction ln comme étant LA SEULE FONCTION dérivable
telle que :
1 ln(xy)=ln(x)+ln(y)
2. ln'(1) = 1.
Puis on définit e par : ln(e)=1.
L'intérêt de cette définition de la fonction ln : on a de jolis
développements en série entière, la fonction exp, inverse de la fonction
ln vérifie : y'=y et y(0)=1 (c'est un théorème).
Tiens, d'ailleurs, on peut aussi décider de définir d'abord la fonction
exp. Les théorèmes deviennent des définitions et les définitions
deviennent des théorèmes :
b. Le point de vue de Cauchy:
exp est la solution de l'équation différentielle y'=y,
vérifiant : exp(0) = 1.
Suivant ce point de vue, on définit e=exp(1) et on définit ln comme
étant la fonction inverse de la fonction exp (de sorte que ln(e)=1).
On a alors le théorème :
1. ln(xy)=ln(x)+ln(y)
2. ln'(1) = 1.
c. Le point de vue Théologique e^(i\pi) + 1 = 0.
Il suffit de définir la fonction puissance.
Si a est un réel positif, on définit a^n pour tout entier naturel n,
puis a^(1/p) pour tout entier naturel p (c'est le nombre b tel que
b^p=a. Ce nombre existe car l'application b->b^p est un bijection)
donc a^q pour tout nombre rationnel positif q, puis a^x pour tout réel
positif x (par passage à la limite).
On s'aperçoit que la fonction que l'on définit ainsi admet un
prolongement analytique : z dans C -> a^z dans C, on démontre qu'il
existe une infinité de réels positifs tel que e^(i\pi) + 1 = 0
et on définit e comme le plus petit réel positif tel que :
e^(i\pi) + 1 = 0
Ensuite, on peut définir la fonction exponentielle par exp(x)=e^x, et
les définitions du second point de vue deviennent des théorèmes (alors
qu'en utilisant la définition du second point de vue (convenablement
étendue aux nombres complexes), l'équation e^(i\pi) + 1 = 0 est un
théorème).
========================================================================
VI Mathématiques et Ordinateurs.
=============================
1. Logiciels de Mathématiques.
---------------------------
| Il existe une multitude de programmes informatiques pouvant être
| utiles aux mathématiques de multiples façons. On peut distinguer
| plusieurs types d'applications.
|
| a) Les logiciels de calcul formel.
|
| Ces programmes permettent de manipuler des expressions symboliques
| et de calculer avec (par exemple dériver des fonctions, factoriser
| des polynômes, calculer des développement en série entière, etc.).
|
| Les plus connus sont sans doute les logiciels commerciaux Maple,
| de Maplesoft, et Mathematica, de Wolfram Research. Il existe
| également des systèmes libres de calcul formel généralistes, tels
| que Yacas (léger et facile), Maxima (puissant et complet) ou encore
| Axiom (efficace pour manipuler des structures algébriques
| abstraites).
|
| Certains programmes de calcul symbolique sont plus spécialisés dans
| certains domaines, comme PARI/GP pour la théorie des nombres, GAP
| pour la théorie des groupes ou Macaulay pour l'algèbre commutative.
|
| Une liste assez complète de ce qui existe est disponible ici :
| http://en.wikipedia.org/wiki/List_of_computer_algebra_systems
|
| b) Les logiciels d'analyse numérique.
|
| À l'opposée, on trouve des logiciels permettant d'effectuer des
| calculs approchés sur des quantités importantes de données
| numériques (résoudre de grands systèmes linéaires, effectuer des
| transformées de Fourier rapides, résoudre numériquement des
| équations aux dérivées partielles, etc.).
|
| On peut citer notamment le logiciel commercial MATLAB, référence du
| domaine, et ses concurrents libres GNU Octave et Scilab, à la
| syntaxe et aux fonctionnalités très similaires. Tous les trois
| manipulent en premier lieu des matrices.
|
| L'écriture de simulations numériques s'effectue par ailleurs souvent
| dans des langages de programmation classiques (C, FORTRAN, Python...)
| assistés de bibliothèques spécialisées, telles que LAPACK en FORTRAN
| ou SciPy en Python. Un répertoire de nombreux ensembles de routines
| est disponible à l'adresse :
| http://gams.nist.gov/
|
| c) Les logiciels de statistiques.
|
| On s'éloigne un peu des mathématiques à proprement parler, mais on
| peut mentionner notamment GNU R, un langage de programmation et un
| environnement logiciel très puissant et libre dans le domaine de
| l'analyse statistique.
|
| d) Les logiciels de tracé de graphes.
|
| Certains programmes sont spécialisés dans la représentation
| graphique (courbes, surfaces, nuages de points, etc.) de fonctions
| ou de données numériques. Citons par exemple gnuplot, descartes ou
| encore ploticus.
|
| e) Les logiciels de géométrie plane.
|
| Il existe des programmes permettant de réaliser et raisonner sur
| des figures de géométrie euclidienne plane : on peut placer des
| points et construire des droites les reliant, des parallèles et des
| perpendiculaires, des coniques, des lieux de points, et ainsi de
| suite.
|
| Le plus connu du public francophone est sans doute Cabri Géomètre,
| mais il existe de nombreux concurrents, notamment libres, tels que
| Dr. Geo, Kig, GeoGebra ou encore GeoProof (ce dernier étant doté de
| fonctionnalités de démonstration automatique).
|
| f) Les assistants de preuve.
|
| Certains programmes permettent, dans un système formel donné, de
| vérifier la correction d'une démonstation, et dans une certaine
| mesure de produire automatiquement la preuve de certains énoncés.
| Les techniques ainsi mises en oeuvre sont parfois appliquées à la
| démonstrations de certains algorithmes, ou à la certification de
| preuves de résultats mathématiques non-triviaux (récemment, on a
| ainsi pu voir certifiée en Coq une démonstration du théorème des
| quatre couleurs, grâce aux travaux de B. Werner et G. Gonthier).
|
| On peut citer dans le domaine des programmes tels que Coq, PhoX
| ou encore Isabelle.
|
| g) La mise en page mathématique.
|
| La réalisation de documents imprimés comportant un nombre important
| de formules mathématiques et autres diagrammes est à peu de choses
| près l'apanage d'un seul logiciel : LaTeX, éventuellement complété
| de divers paquets d'extension (comme amsmath pour des
| fonctionnalités mathématiques supplémentaires ou xy pour les
| diagrammes) et de programmes externes pour des tâches particulières
| (comme BibTeX pour la gestion des bibliographies ou METAPOST pour
| la réalisation de figures).
|
| LaTeX n'est pas un éditeur « WYSIWYG », au sens où l'utilisateurs
| ne manipule pas directement une prévisualisation du document
| imprimé, mais un fichier texte dans lequel il indique des
| instructions de mise en forme, ce qui rend particulièrement commode
| l'insértion des expressions mathématiques. Il existe cependant des
| surcouches graphiques telles que LyX permettant aux utilisateurs
| rebutés par le texte pur de profiter de la puissance de LaTeX via
| un éditeur plus visuel. Dans la même veine, on peut mentionner le
| traitement de texte scientifique GNU TeXmacs, qui s'inspire des
| principes de séparation de la structure et du contenu qui prévalent
| en TeX/LaTeX.
|
| En ce qui concerne la mise à disposition de textes mathématiques en
| ligne sur le web, elle se fait encore très fréquemment via LaTeX, en
| proposant aux visiteurs de télécharger des documents imprimables PS
| ou PDF, ou bien en insérant les formules mathématiques composées par
| LaTeX sous forme d'images dans la page HTML (statiquement grâce à
| des programmes comme LaTeX2HTML, ou de manière dynamique comme le
| fait WikiTeX). La norme MathML, publiée depuis 1999 et dont le
| support commence à apparaître dans les navigateurs web, doit
| permettre de remédier à cette situation. MathML n'est toutefois
| pas du tout un langage conçu pour qu'un être humain écrive avec,
| et donc la réalisation de documents XHTML contenant du MathML passe
| par des traitements de texte comme TeXmacs, OpenOffice.org ou
| l'éditeur intégré au navigateur Amaya. Il existe aussi des outils,
| comme itex2mml, pour convertir des expressions mathématiques LaTeX
| en MathML.
2. L'agorithme de CORDIC sur les calculatrices.
--------------------------------------------
Un des algorithmes les plus courants sur calculatrice scientifique
est l'algorithme CORDIC (pour "COordinate Rotation DIgital Computer")
dont la référence classique est : Jack E. Volder,
"The CORDIC Trigonometric Computing Technique," IRE Transactions
on Electronic Computers, Vol. EC-8, pp.330-334, 1959. J. Volder y
décrit des algorithmes pour l'évaluation rapide des fonctions sinus
et cosinus au moyen d'une série de rotations du système de coordonnées
(méthodes qu'on retrouvera lors de l'évaluation de la tangente)
Dans une calculatrice typique un nombre 'flottant' occupe 8 octets
de mémoire et se décompose en :
- une mantisse constituée de 13 chiffres codés indépendamment sur
4 chiffres binaires (on parle de Binaire Code Decimal ou BCD)
- un exposant (puissance de 10) éventuellement signé
- le signe du nombre (et de l'exposant s'il n'est pas signé)
Les algorithmes mathématiques sont généralement implémentés à un
plus bas niveau utilisant une représentation fixe en BCD (sur 16
chiffres soit 8 octets dans notre exemple).
Une multiplication (division) par 10^n peut donc être remplacée par
un décalage de 4*n chiffres binaires. Sur calculatrice on tente
d'éviter les opérations 'lourdes' que sont la multiplication et la
division.
Toutes les fonctions 'standard' peuvent se ramener (entre autres)
aux quatre fonctions suivantes : ln, exp, tan, arctan
Soit à évaluer une de ces fonctions f au point x, le principe des
algorithmes CORDIC est d'effectuer une série de transformations
simples (addition/soustraction et décalage) réduisant la valeur de
x à une valeur très faible en même temps qu'élaborant le résultat.
Chacune de ces transformations nécessite une valeur précalculée
de f (ou de son inverse). Le résultat est obtenu par une simple
interpolation linéaire (ou un développement en série si davantage
de chiffres sont requis).
Pour les 4 fonctions précédentes les tableaux L et A suffiront
(pour obtenir plus de 12 chiffres de précision) :
L= [ln(2), ln(1.1), ln(1.01), ..., ln(1.000001)]
A= [atan(1), atan(0.1), atan(0.01), ..., atan(0.0001)]
(pour tanh et argtanh il faudrait en plus AH= [atanh(1),...] )
On procède en deux étapes :
1. Ramener la valeur à évaluer dans l'intervalle où la méthode est
applicable en utilisant (par exemple) les transformations :
(ln(10), Pi/2, Pi sont également précalculées et Pi/4= atan(1))
- ln sur [1, 10[ (1) ln(x)= ln(x*10^(-n))+n*ln(10)
- exp sur [0, ln(10)[ (2) exp(x)= exp(x-n*ln(10))*10^n
- arctan sur [0, 1[ si x<0 atan(x)= -atan(-x) puis
si x>1 atan(x)= Pi/2-atan(1/x)
- tan sur [0, Pi/4[ (3) tan(x)= tan(x modulo Pi) puis
si x>Pi/2 tan(x)= -tan(Pi-x) puis
(4) si x>Pi/4 tan(x)= 1/tan(Pi/2-x)
En réalité les algorithmes restent valides pour des valeurs plus
grandes que ce qui est précisé mais perdent alors en efficacité.
2. Appliquer l'algorithme en itérant sur l'indice k de l'élément
précalculé (on commence toujours par le plus grand terme).
(L'erreur commise dans chaque cas est inférieure à 10^(-12))
- ln : Représentons x par le produit suivant :
x= (1+1)^n0*(1+1/10)^n1*...*(1+1/10^6)^n6*(1+eps.)
avec n0 entier positif maximal puis n1 maximal, etc..
de sorte que ln(x)= n0*ln(1+1)+n1*ln(1+1/10)+... +ln(1+eps.)
k= 0; y= 0; p= 1; //p est le produit partiel plus haut
TantQue (k <= 6)
TantQue (x >= p+p*10^(-k))
y= y+L[k]; //ou L[k]= log(1+10^(-k))
p= p+p*10^(-k);
FinTant;
k= k+1; //à la fin on a :
FinTant; // x/p= (1+eps.) donc eps.= x/p-1
Rendre y+(x/p-1); //le terme suivant est -(x/p-1)^2/2
//réponse exacte : y+ln(x/p)
- exp : On écrira cette fois :
exp(x)= (1+1)^n0*(1+1/10)^n1*...*(1+1/10^6)^n6*(1+eps.)
k= 0; y= 1; //y est le produit partiel précédent
TantQue (k <= 6)
TantQue (x >= L[k])
x= x-L[k];
y= y+y*10^(-k);
FinTant;
k= k+1; //à la fin on a :
FinTant; //exp(x)=(1+eps.) donc eps.= exp(x)-1
Rendre y+y*x; //le terme suivant est +y*x^2/2!
//réponse exacte : y*exp(x)
- arctan : (pour argtanh voir note (5))
On utilise une représentation de type
atan(x)= n0*A[0]+n1*A[1]+...+n4*A[4]+eps.
obtenue en répétant la formule :
atan(x/y)= atan(x'/y')+atan(10^(-k))
avec x'= x-y*10^(-k) et y'= y+x*10^(-k) qui donne :
k= 0; y= 1; r= 0;
TantQue (k <= 4)
TantQue (x < y*10^(-k))
k= k+1;
FinTant;
xp= x-y*10^(-k);
y= y+x*10^(-k);
x= xp;
r= r+A[k]; //où A[k]= atan(10^(-k))
FinTant; //à ce stade : atan(x/y)= eps.
Rendre r+(x/y); //le terme suivant est -(x/y)^3/3
//réponse exacte : r+atan(x/y)
- tan : Cette fois si on a : (pour tanh voir note (6))
x= n0*A[0]+n1*A[1]+...+n4*A[4]+eps.
et si tan(s)=n/d alors tan(s+atan(10^(-k)))=n'/d'
avec n'= n+d*10^(-k) et d'= d-n*10^(-k)
k= 0; n= 0; d= 1; //tan(somme partielle)= n/d= 0
TantQue (k <= 4)
TantQue (x >= A[k])
x= x-A[k]; //reste de la somme partielle
np= n+d*10^(-k);// n'
d= d-n*10^(-k); // d'
n= np;
FinTant;
k= k+1;
FinTant; //à ce stade x= eps.
Rendre (n+x*d)/(d-x*n); //pour plus de précision remplacer
//x par x+x^3/3
//exact : (n+d*tan(x))/(d-n*tan(x))
(pour sinus et cosinus voir la note (7))
Ce qui précède ne correspond qu'à une implémentation parmi d'autres
et on aurait pu préférer une table de racines carrées de (1+1/10^k)
par exemple (avec l'avantage de traiter les racines carrées!).
Les implémentations sur ordinateurs utilisent plutôt la base 2
(car travaillant en binaire plutôt qu'en BCD) ce qui conduit à
remplacer tous les 10^n par 2^n (et... à précalculer davantage
de termes).
On aurait également pu calculer moins de termes en utilisant un
développement en série du second ordre ou davantage car les
multiplications sont devenues très rapides (méthode encore bien
plus utile pour obtenir davantage de chiffres de précision et...
que ne permettent pas les méthodes qui suivent).
Mais l'efficacité de la multiplication autorise également l'essor
de techniques concurrentes comme les approximations polynômiales
apparentées aux polynômes de Chebyshev (Tschebyscheff).
On y construit des polynômes (au moyen de l'algorithme de Remez par
exemple) de telle sorte que l'erreur maximale commise en remplacant
la fonction par son polynôme sur un intervalle fixé soit la plus
petite possible. Un précurseur de ces méthodes est Hastings, C, Jr.
dans "Approximations for Digital Computers", Princeton University
Press, 1955.
Notes :
(1) à ce stade la représentation flottante est utilisée donc il
suffit de calculer le logarithme de la mantisse et d'ajouter
l'exposant que multiplie ln(10).
(2) n est la partie entière de x divise par ln(10) qu'on pourra
additionner directement à l'exposant.
(3) le calcul de la tangente n'a pas de sens si |x| > 10^13
(4) il vaut mieux ne faire cela que pour des valeurs proches
de Pi/2 afin d'éviter la division.
(5) l'implémentation de argtanh est presque identique pourvu de
commencer avec k= 1 puis de remplacer A[k] par AH[k] et
y= y+x*10^(-k) par y= y-x*10^(-k).
(6) l'implémentation de tanh s'en déduit en commençant avec k= 1,
en remplaçant A[k] par AH[k], d=d-n*10^(-k) par d=d+n*10^(-k)
et (n+x*d)/(d-x*n) par (n+x*d)/(d+x*n).
(7) si on ajoute p= 1; à la ligne d'initialisation ainsi que
p= p+p*10^(-2*k); à la boucle la plus interne et enfin
p= p+p*x*x; tout à la fin alors le sinus est donné par
(n+x*d)/sqrt(p) et le cosinus par (d-x*n)/sqrt(p)
(Les formules moins efficaces sin(x)= tan(x)/sqrt(1+tan(x)^2)
et cos(x)= 1/sqrt(1+tan(x)^2) sont plus souvent utilisées).
========================================================================
VIII Références et remerciements.
===========================
1. Références.
-----------
a) Livres
On ne saurait trop répéter que les livres dépendent du niveau en
mathématiques du lecteur. Ainsi si vous êtes en terminale ne vous lancez
pas immédiatement dans la démonstration du dernier théorème de Fermat
par Andrew Wiles. Une approche des courbes elliptiques peut être
préférable, avant toute autre lecture. :o)
Sur l'histoire des mathématiques:
-- « Une histoire des mathématiques (Routes et dédales) »
de A. Dahan-Dalmedico et J. Peifer aux éditions Point-Science.
-- « Histoire universelle des chiffres »
de G. Iffrah aux éditions Seghers.
-- « Mathématique au fil des âges (épistémologie et histoire) »
collectif du groupe I.R.E.M. aux éditions Gauthier-Villar.
-- « Eléments d'histoire des mathématiques »
de N. Bourbaki aux éditions Hermann.
-- « Abrégé d'histoire des mathématiques 1700 - 1900 »
sous la direction de J. Dieudonné.
-- « Les grands courants de la pensée mathématique »
sous la direction de F. Le Lionnais, aux éditions PUF.
b) News et autres FAQs
Dans le "Big-8" :
-- sci.math FAQ à l'adresse
http://www.faqs.org/faqs/sci-math-faq/
-- sci.math.num-analysis FAQ à l'adresse
| http://www.mathcom.com/corpdir/techinfo.mdir/scifaq/
c) Web
L'Encyclopédie Électronique des Suites Entières de N. J. A. Sloane
http://www.research.att.com/~njas/sequences/indexfr.html
La base de données MacTutor History of Mathematics archive, développée
et gérée par John O'Connor et Edmund Robertson à l'Université de
St-Andrews (Ecosse) http://www-groups.dcs.st-and.ac.uk/~history/
La page Web des nombres premiers,
| http://primes.utm.edu/
|
| La base de donnée de prépublications ArXiV :
| http://arxiv.org/archive/math
|
| Les mathématiques sur la Wikipédia francophone :
| http://fr.wikipedia.org/wiki/Portail:Math%C3%A9matiques
2. Remerciements.
-------------
Une version html de ce texte est disponible à l'adresse
<http://faq.maths.free.fr/>
que Kristen Le Liboux et Régis Décamps entretiennent.
Nous tenions à remercier tous ceux qui ont participé volontairement,
par la rédaction de paragraphes entiers, ou involontairement, par leurs
contributions sur le forum, à cette FAQ.
En particulier,
Silvain Abadie, Guillaume Allègre, Frederic Bastok, Hubert Bayet,
Dominique Bernardi, Yann Chevalier, Jérôme Collet, Sébastien Dauby,
Daniel Dubuisson, Raphaël Giromini, Vincent Lefevre, Stéphane Ménart,
Jean-Pierre Minisini, Christian Radoux, Guillaume Réocreux, Fréderic
Schutz et Mehdi Tibouchi.
| D'émormes mercis à Guillaume Allègre, pour avoir entretenu sur son
| site la proto-faq du forum, à Frédéric Schutz, pour avoir rédigé la
| première version de la FAQ, ainsi qu'à Raphaël Giromini, qui en était
| le précédent mainteneur.
De chaleureux remerceiments pour leurs relectures et leurs corrections :
Emmanuel Bresson, Petrut Constantine, Jean-Paul Delahaye, Paul Jobling,
Kristen Le Liboux et Olivier Miakinen.
| Pour toute remarque concernant cette FAQ, ou pour y incorporer de
| nouveaux paragraphes, s'adresser à son mainteneur Mehdi Tibouchi
| (medtib@alussinan.org).
=======================================================================
Les autres parties de cette FAQ se trouve dans les documents intitulés :
[FAQ] fr.sci.maths - partie 1/3
[FAQ] fr.sci.maths - partie 2/3
Ces documents sont disponibles sur fr.sci.maths ou à l'adresse :
http://www.usenet-fr.net/fur/maths/maths-faq.html
http://www.usenet-fr.net/fur/maths/maths-faq-2.html
.
Traduit en HTML par faq2html.pl le Wed Nov 3 05:42:13 2010 pour le site Web Usenet-FR.
