Archive

Archives de l'auteur

Comment calcule une calculatrice ?

16/05/2010 Valvino Aucun commentaire

Naïvement, je pensais qu’une calculatrice (ou tout logiciel de calcul scientifique) utilisait les développements en série pour calculer les fonctions usuelles : trigonométriques (sinus, cosinus, tangente), exponentielle, logarithme, etc. En fait, il n’en est rien et on utilise des astuces bien précises qui diminuent fortement la complexité des calculs.

Par exemple, on utilise l’algorithme CORDIC (COordinate Rotation DIgital Computer) inventé en 1959 par Jack E. Volder. Détaillons-le sommairement.

On se donne un angle en radian \alpha (que l’on suppose compris entre 0 et \pi/2, on peut toujours s’y ramener par des formules trigonométriques du genre \sin(x+\pi/2)=\cos(x), etc…). On va calculer par itération un vecteur v_n qui représente un point sur le cercle unité. Pour cela, on lui fait subir des rotations d’angles \gamma_n choisis judicieusement, par exemple tels que \tan \gamma_n= 2^{-n}. L’avantage est qu’en binaire la multiplication par 2^{-n} revient à un simple décalage de virgule. Le vecteur v_n, d’angle correspondant \alpha_n, convergera alors vers la valeur exacte v, d’angle correspondant \alpha.

On a donc une relation de récurrence du type

\displaystyle v_{n+1}=\begin{pmatrix} \cos \gamma_{n} & -\sin \gamma_{n} \\ \sin \gamma_{n} & \cos \gamma _{n}\end{pmatrix}v_n

d’où en factorisant par \cos \gamma_n

\displaystyle v_{n+1}=\cos(\arctan(2^{-n}))\begin{pmatrix} 1 & -\sigma_{n} 2^{-n} \\ \sigma_{n} 2^{-n} & 1 \end{pmatrix}v_n

où \sigma_n = \pm 1 (sens de la rotation). On le calcule en regardant le signe de l’angle actuel \alpha_{n+1}=\alpha_n-\sigma_n \arctan2^{-n}.

Il suffit alors d’avoir en mémoire les différentes valeurs de \arctan2^{-n} (on peut même utiliser l’approximation \arctan2^{-n} \sim 2^{-n} pour n un peu grand) pour se retrouver avec un algorithme qui n’utilise que des additions, des décalages de virgules et une seule multiplication finale par

\displaystyle\prod_{n=0}^{N-1} \cos(\arctan(2^{-n})) = \prod_{n=0}^{N-1} \frac{1}{\sqrt{1 + 2^{-2n}}},

valeurs que l’on peut aussi stocker à l’avance. Malin, non?

On peut généraliser ce genre de procédés. Pour plus d’informations : http://en.wikipedia.org/wiki/CORDIC

Categories: Maths faciles Tags: , , , , , ,

Sujets polémiques en mathématiques

26/03/2010 Valvino 21 commentaires

Même si les mathématiques ont l’air d’une science exacte, où la Vérité est figée à tout jamais, il existe quelques sujets qui poussent aux débats sans fin. J’en connais quelques uns :

  • l’entier 1 est-il premier ?
  • doit-on considérer les ensembles finis comme dénombrables ?
  • pour ou contre l’axiome du choix ?
  • qui a inventé le calcul différentiel? Newton ou Leibniz ?
  • les statistiques font-elles parties des mathématiques ?
  • est-ce que la façon d’aborder les mathématiques de Bourbaki est LA bonne façon de procéder ?

En connaissez-vous d’autres ?

Voici quelques propositions des commentaires :

  • Dans Bourbaki, un espace quasi-compact est un espace topologique vérifiant la propriété de Borel-Lebesgue. Un espace compact est un espace quasi-compact séparé. Par contre, dans les textes mathématiques écrits en anglais, un espace est compact n’est pas nécessairement séparé. Quid ?
  • La définition de \pi est erronée, et l’erreur s’est perpétuée depuis l’antiquité.
  • Une forme sesquilinéaire est-elle linéaire à gauche ou à droite?
  • Dans les coordonnées sphériques, que désignent \theta, \varphi, r et \rho?
  • Combien vaut 0^0 ?
  • Est-ce que les notions d’ « application » et de « fonction » sont identiques ?
  • L’espace topologique vide est-il connexe ?
  • Quelle est la dimension de Krull de l’anneau nul ?
  • La suite (n)_{n\in\mathbb N} « converge-t-elle » ou « diverge-t-elle » vers l’infini ?
  • …
Categories: Réflexions Tags: , ,

Preuve topologique de l’infinitude des nombres premiers

03/02/2010 Valvino 6 commentaires

Voilà un titre qui en jette un maximum! J’ai lu dans l’excellent livre Raisonnements divins (chez Springer) une démonstration étonnante du fait qu’il existe une infinité de nombres premiers. Elle est d’un niveau élevé car elle fait appel à des notions de topologie générale, mais elle est assez élémentaire pour qui connait cette théorie. Je la livre donc ici.

On définit une topologie sur \mathbb Z en disant que les ouverts sont le vide et les O \subset \mathbb Z vérifiant que pour tout entier a\in O, il existe un entier b>0 tel que a+b\mathbb Z\subset O. Il est clair que la réunion quelconque d’ouverts est un ouvert. De plus, si O_1,O_2 sont des ouverts, ou bien l’intersection est vide et O_1 \cap O_2 est un ouvert, ou bien pour a \in O_1 \cap O_2, on a a+b_1b_2\mathbb Z \subset O_1 \cap O_2, avec  des entiers b_1,b_2>0 tels que a+b_1\mathbb Z\subset O_1 et a+b_2\mathbb Z\subset O_2. Finalement,  O_1 \cap O_2 est un ouvert. On a donc bien une topologie sur \mathbb Z.

On remarque d’une part que tout ouvert non vide est infini (car par définition il contient un ensemble infini), et d’autre part que tout ensemble du type a+b\mathbb Z, avec a,b des entiers (b>0), est un fermé. En effet, on a

\displaystyle a+b\mathbb Z=\mathbb Z-\left(\bigcup_{k=1}^{b-1} [a+k+b\mathbb Z]\right),

c’est donc le complémentaire d’un ouvert.

Comme tout entier différent de 1 et -1 admet un diviseur premier, on a

\displaystyle \mathbb Z-\{-1,1\}=\bigcup_p 0+p\mathbb Z

où la réunion se fait sur tous les nombres premiers p. S’ils étaient en nombre fini, \bigcup_p 0+p\mathbb Z serait fermé comme réunion finie d’ensembles fermés. Par passage au complémentaire, \{-1,1\} serait ouvert, ce qui est absurde car c’est un ensemble fini non vide. Il existe donc une infinité de nombres premiers.

Joli, non?

Categories: Maths difficiles Tags: , , ,

Le théorème de Wielandt

26/01/2010 Valvino Aucun commentaire

La fonction gamma \Gamma prolonge la notion de factorielle sur l’ensemble des nombres complexes privés des entiers négatifs ou nul. Il s’agit là d’une fonction holomorphe, sauf aux entiers négatifs ou nul où elle admet des pôles. C’est donc une fonction méromorphe sur les nombres complexes.

On dispose de plusieurs caractérisations de cette fonction. Citons le théorème de Bohr-Mollerup :

Soit une fonction f:]0,+\infty[ \to ]0,+\infty[ telle que

  1. f(1)=1;
  2. f(x+1)=xf(x) pour tout x>0;
  3. f est log-convexe, c’est-à-dire que \log(f) est une fonction convexe.

Alors f(x)=\Gamma(x) pour tout x>0.

On dispose d’une autre caractérisation, il s’agit du théorème de Wielandt :

Soit f une fonction holomorphe sur \mathrm{Re}(z)>0 telle que

  1. f(1)=1;
  2. f(z+1)=zf(z) pour tout \mathrm{Re}(z)>0;
  3. f est bornée dans la bande 1 \leq \mathrm{Re}(z) \leq 2.

Alors f(z)=\Gamma(z) pour tout \mathrm{Re}(z)>0.

Je me propose de faire une esquisse de la démonstration.

On remarque tout d’abord que l’on peut étendre f sur l’ensemble des nombres complexes privés des entiers négatifs ou nul par 2. en suivant la même méthode que pour la fonction gamma. Ensuite, on remarque avec 1. que les résidus aux pôles sont les mêmes que ceux de la fonction gamma. Ainsi, la fonction g=f-\Gamma est une fonction entière.

Ensuite, on remarque que g est bornée sur la bande 0 \leq \mathrm{Re}(z) \leq 1. Pour cela, il suffit de remarquer que c’est le cas sur la bande 1 \leq \mathrm{Re}(z) \leq 2, en faisant une majoration explicite sur la formule définissant \Gamma. On utilise ensuite 2. pour se ramener à la bande 0 \leq \mathrm{Re}(z) \leq 1, le problème en 0 étant effaçable par 1.

Enfin, on pose h(z)=g(z)g(1-z).  Par ce qui précède, c’est une fonction entière bornée dans la bande 0 \leq \mathrm{Re}(z) \leq 1. De plus, h(z+1)=-h(z), ce qui montre que h est une fonction bornée sur l’ensemble des nombres complexes. Par le théorème de Liouville, elle est constante. Comme h(1)=0, on a h=0, c’est-à-dire g=0. Finalement, f=\Gamma.

Categories: Maths difficiles Tags: , , , ,

Le théorème de Jordan

13/12/2009 Valvino un commentaire

Prenez une feuille de papier, et un stylo. Tracez une ligne, avec pour conditions

  1. ne pas lever le stylo;
  2. ne pas repasser par dessus la ligne;
  3. refermer la ligne sur elle-même à la fin.
Une ligne respectant les conditions.

Une ligne respectant les conditions.

Le théorème de Jordan vous dit alors que vous avez découpé votre feuille en deux parties d’un seul bloc, avec une partie finie et l’autre infinie (si on considère que le papier pourrait être aussi grand que l’on veut). Et là bien sûr vous vous dites qu’il ne faut pas sortir de Polytechnique pour établir des résultats aussi évidents… Hé bien, en dépit de son apparente simplicité, ce théorème est très difficile à démontrer. Tout réside dans le fait qu’il existe des lignes dans le plan très vicieuses…

Commençons par énoncer rigoureusement le théorème. Tout d’abord, on définit une courbe (c’est-à-dire une ligne) comme une fonction f qui part de l’intervalle [0,1] et qui va dans le plan. D’une certaine manière, [0,1] peut être vu comme le temps (0 le début du tracé, 1 la fin) et f(t) le point tracé exactement à l’instant t. On exige que cette fonction soit continue (la condition de ne pas lever le stylo), ainsi la courbe est « en un seul morceau ». De plus, on veut que la courbe se referme sur elle-même à la fin, donc on exige f(0)=f(1). Enfin, il ne faut pas que la courbe repasse sur elle-même, on veut donc que f(t_1) \neq f(t_2) à deux instants t_1 et t_2 qui ne sont pas exactement 0 et 1. On a donc une condition d’injectivité de la courbe (la courbe doit être injective sur [0,1[ et ]0,1]). Les courbes ainsi définies portent le doux nom de courbes de Jordan.

Comment formaliser le concept d’être « d’un seul bloc »? On dit qu’une partie du plan est connexe (c’est-à-dire d’un seul bloc) si on peut toujours passer d’un point de cette partie à un autre par une courbe continue.

La partie A est connexe, alors que B ne l'est pas.

La partie A est connexe, alors que B ne l'est pas.

Rappelons que le complémentaire d’une partie du plan est tout simplement la partie du plan constituée des points qui ne sont pas dans la première. Deux parties du plan sont dites disjointes si elles n’ont pas de points en commun. Enfin, une partie du plan est dite bornée quand on peut l’inclure dans un disque de rayon fini.

On peut alors énoncer correctement le théorème de Jordan :

Le complémentaire d’une courbe de Jordan est constitué de deux parties connexes qui sont disjointes. L’une est bornée, et l’autre non.

Pourquoi ce théorème est-il si difficile à démontrer? Tout simplement parce qu’il existe des courbes de Jordan très vicieuses. Comme exemple, prenons une courbe de Jordan de type fractale appelée flocon de von Koch. Sans rentrer dans les détails, c’est une courbe obtenue en itérant une infinité de fois le procédé décrit dans l’animation suivante :

Les premières étapes de la construction du flocon de von Koch.

Les premières étapes de la construction du flocon de von Koch.

Le problème de ce genre de courbe est qu’il est difficile de savoir si deux points peuvent être reliés par une courbe continue qui ne passe pas par dessus le flocon à cause des innombrables radicelles que forme la courbe. C’est ce qui fait la difficulté de ce théorème!

Pour plus d’informations, vous pouvez consulter le très bon article wikipédia sur le sujet.

Categories: Vulgarisation Tags: , , , , , , ,