Mathématiques - L'algorithme philosophal...

L'algorithme philosophal...
(Cliquez-ici pour accéder à la version originale de cette discussion avec couleurs et images)

Posted by: HaK

Salut à tous,

Quel est le but de ce post ? Trouver une technique de calcul manuel permettant d'obtenir le résultat de x^y (dsl je ne maîtrise pas encore TEX) pour tout x et y réel. Je m'explique tous le monde connait les algorithmes d'extractions de racine carré j'en donne deux pour exemple :

Citation:

1. Un algorithme fabuleux au " compte goutte ".
Cette méthode SIMPLISSIME est d’une beauté fulgurante ! j’en suis fou.
Mais la convergence est décevante puisque chaque itération ne donne qu’un seul chiffre.
Cependant il suffit de connaître les nombres impairs pour la mettre en œuvre.

Sur un exemple (qui en dit long).

Soit à trouver la racine de A=2137.
On écrit ce nombre par tranche de deux (en partant de la virgule) 21 37 , 00 00
Du premier groupe, on ôte les premiers nombres impairs :
21-1-3-5-7=5.
Nous avons effectués quatre soustractions, le premier chiffre est donc un 4.
On recommence avec 537 (le reste des premières soustractions suivit du deuxième groupe)
Cette fois, on soustrait à 537 les impairs à partir de 81 (obtenu en ajoutant 1 au dernier impair utilisé multiplié par 10 et augmenté d’une unité - " on ‘colle’ un 1 à 8 ")
537-81-83-85-87-89-91=21
La racine approchée est donc 46 (puisqu’il y a 6 soustractions)
On peut continuer :
2100-921-923=256
La valeur approchée devient 46,2

On continue ?
25600-9241-9243=6816
Une valeur approchée est donc 46,22

Citation:

2. La méthode de Héron d’Alexandrie. (premier siècle de notre ère)
Description
Cette méthode repose sur la connaissance d’une première valeur approchée de la racine de A notée a.
Il s’agit ensuite de calculer la moyenne arithmétique entre a et A/a (puisque ce sont deux valeurs approchées du nombre cherché).
On obtient alors : (1/2)(a+(A/a)) , il ne reste plus qu’à itérer le processus.

En notations " lycéennes " :
On construit la suite définie par son premier terme, et la relation de récurrence : X0= a et Xn+1=(1/2)(Xn+(a/Xn)) (n en indice) .

Cette méthode est très simple, puisqu’il s’agit à chaque étape, d’évaluer la moyenne arithmétique de deux approximations de la racine carrée de A.
En effet si est une valeur approchée par excès, alors est une valeur approchée par défaut (et réciproquement).
étant la moyenne arithmétique de ces deux valeurs approchées.

Extrait de http://membres.lycos.fr/ericmer/

Donc mon idée consiste à s'appuyer sur ces technique pour en trouver des plus générale. Alors qu'en pensez vous est-ce fou , impossible, possible ou déjà fait !

Posted by: Non inscrit

dejà fait !!!

si tu veux x^y, ecrit le x sous forme x = 1+b et calcule (1+b)^y = 1 +y*b + .... plus tu pousses loin la somme, plus tu approches le resultat...

Posted by: HaK

Tu pourrais expliciter un peu s'il te plait

Posted by: HaK

Personne ne peut détailler ?

Posted by: cesar

Citation:

Posté par Non inscrit

dejà fait !!!

si tu veux x^y, ecrit le x sous forme x = 1+b et calcule (1+b)^y = 1 +y*b + .... plus tu pousses loin la somme, plus tu approches le resultat...

je crois comprendre:

il s'agit d'un developpement en serie entiere ...

(1+b)^y = 1+y*b/1!+ y(y-1)*b*b/2! +.....y(y-1)(y-2)....(y-n+1)*b^n/n!.....

je garantirai pas, mais cela ressemble...

Posted by: HaK

Le developpement en série entière correspont à un developpement limité ? On en a eut quelque notions en Physique mais je ne suis pas très au point, je débute ma PCSI...

Posted by: cesar

Citation:

Posté par HaK

Le developpement en série entière correspont à un developpement limité ? On en a eut quelque notions en Physique mais je ne suis pas très au point, je débute ma PCSI...

quand on fait un DL de taylor , ou bien un developpement en serie entiere d'une fonction f(x), on tombe sur les mêmes termes : c'est à cause de l'unicité de la decomposition sur une base (ici, la base est : 1, x, x*x, x*x*x, x*x*x*x,....

Posted by: Chimerade

Citation:

Posté par HaK

On construit la suite définie par son premier terme, et la relation de récurrence : X0= a et Xn+1=(1/2)(Xn+(a/Xn)) (n en indice) .

Petite erreur, mais tout le monde avait compris ! Il faut lire :
$\Large X_0= a$ et $\Large X_{n+1}=(\frac{1}{2})\times (X_n+\frac{A}{X_n})$

Citation:

Posté par HaK

En effet si est une valeur approchée par excès, alors est une valeur approchée par défaut (et réciproquement).

Je conteste cette phrase : qu'X(0) soit une valeur approchée par excès ou par défaut importe peu, X(1) et tous les X suivants seront approchés par excès. En effet :

$\Large X_{n+1}-\sqrt{A} = (\frac{1}{2})\times (X_n+\frac{A}{X_n})-\sqrt{A}$
$\Large X_{n+1}-\sqrt{A} = (\frac{1}{2})\times (X_n+\frac{A}{X_n}-2\sqrt{A})$
$\Large X_{n+1}-\sqrt{A} = (\frac{1}{2X_n})\times (X_n^2+A-2X_n\sqrt{A})$
$\Large X_{n+1}-\sqrt{A} = (\frac{1}{2X_n})\times (X_n-\sqrt{A})^2$

On note également l'évolution de l'erreur relative à chaque étape :

$\Large \frac{X_{n+1}-\sqrt{A}}{\sqrt{A}} = (\frac{1}{2X_n\sqrt{A}})\times (X_n-\sqrt{A})^2$
$\Large \frac{X_{n+1}-\sqrt{A}}{\sqrt{A}} = (\frac{\sqrt{A}}{2X_n(\sqrt{A})^2})\times (X_n-\sqrt{A})^2$
$\Large \frac{X_{n+1}-\sqrt{A}}{\sqrt{A}} = (\frac{\sqrt{A}}{2X_n})\times (\frac{X_n-\sqrt{A}}{\sqrt{A}})^2$
Et $\Large X_n$ tendant vers $\Large \sqrt{A}$ on peut écrire :

$\Large \frac{X_{n+1}-\sqrt{A}}{\sqrt{A}} \approx (\frac{1}{2})\times (\frac{X_n-\sqrt{A}}{\sqrt{A}})^2$

Ceci peut s'interpréter en disant que le nombre de chiffres exacts fait plus que doubler à chaque étape. De tels algorithmes sont très précieux pour les informaticiens...

Posted by: HaK

Merci de la correction chimerade, comme tu l'as dit ce genre d'algorithme est utile pour les informaticiens, mais ce qui m'interresse plus est de trouver une methode abordable d'aproximation de a^b à la main. On peut donc utiliser les séries de Taylor (je vais essayer de bouquiner dessus...), mais n'existe t-il pas un moyen de modifier l'algorithme que tu as corrigé pour le généraliser à notre sujet ?

Posted by: Chimerade

Citation:

Posté par HaK

Merci de la correction chimerade, comme tu l'as dit ce genre d'algorithme est utile pour les informaticiens, mais ce qui m'interresse plus est de trouver une methode abordable d'aproximation de a^b à la main. On peut donc utiliser les séries de Taylor (je vais essayer de bouquiner dessus...), mais n'existe t-il pas un moyen de modifier l'algorithme que tu as corrigé pour le généraliser à notre sujet ?

Je me souviens l'avoir cherché (il ya longtemps !) cet algorithme en me limitant aux exposants du type $\Large \frac{1}{n}$ , mais il me semble que je n'étais pas parvenu à trouver un algorithme similaire, ce qui ne signifie évidemment pas qu'il n'en existe pas ! Je doute en tous cas de l'applicabilité spécifiquement de cette méthode pour un exposant entier, a fortiori quelconque.

Bonne recherche !