Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter
[Astuce] Approximation de racines carrées
Information importante Le message original n'ayant ete modifie dans les delais, il a ete remplace par ce sujet bien plus interessant... Les premiers messages ont etes supprimes
Ce sujet pouvant etre interessant, il pourra eventuellement remplacer le sujet original en cas de non-modification de celui-ci.Envoyé par Blustuff
Bon d'accord.
Vous connaissez la méthode de Newton ? Elle permet de résoudre des équations en trouvant des racines approchées. Graphiquement, vous tracez la courbe de votre fonction, et à un premier point quelconque de la fonction, que vous savez suffisement proche de la solution, vous tracez la tangente. Vous prenez l'intersection entre la tangente et l'axe des abscisses, et ca vous donne une seconde approximation.
De cette nouvelle approximation, vous réitérez l'algorithme, en retracant la tangente en ce point, et en prenant l'approximation suivante à l'intersection de la tangente et de l'axe.
Cette méthode ne marche pas toujours, et converge mal, voir pas du tout si la dérivée première est très proche de 0, ou si la dérivée seconde est trop grande.
Pour les racines carrées, elle converge très bien. Si on essaie de se représenter la fonction :
x² = a
qui a deux solutions racine de a, et -racine de a, et qu'on prend comme première approximation a, on s'apercoit en tracant les tangentes successives, quon se rapproche toujours de a, en décroissant vers a.
si on appelle u_n les différentes approximations succesives, avec u_0 = a, l'équation de la tangeante à la fonction
f(x) = x² - a
en b est :
t(x) = f'(b)(x - b) + f(b)
et son intersection avec l'axe des abscisses :
t(x) = 0
eq à f'(b)(x - b) + f(b) = 0
eq à x - b = -f(b)/f'(b)
eq à x = b - f(b)/f'(b)
eq à x = b - (b² - a) / (2*b)
Soit de manière plus facilement calculable pour le processeur :
x = b - b/2 + a/2b
x = (b - a/b) / 2
On a donc la suite :
u_0 = a
u_(n+1) = (u_n - a / u_n) / 2
Donc, une soustraction, une division, et un décalage de bit par étape.
Remarques :
1) J'ai simplifié la méthode de Newton, on est pas obligé de tracer la tangente au même point que celui où on en trouve le coefficient directeur.
2) La méthode converge très vite, à chaque étape, on a deux fois plus de chiffres de précision. Si à une étape, on à 10 chiffres de précision, on en aura vingt à la suivante. Dans notre cas, c'est peut utile pour des racines entières... Sauf... Si on cherche des racines de nombre 64 bits... Mais la méthode marche très bien pour les nombres à virgule flottante aussi, avec la même formule, ce n'est juste pas les mêmes opérations.
3) On peut s'arretter quand on veut à cette méthode. Une manière simple pour les entiers, consiste à arrêter l'algorithme quand [u_n] = [u_(n+1] (où [.] désigne partie entière)
4) désolé si c'est brouillon, mais je dois aller en cooooouuurs, j'espère ne pas vous avoir autant endormi, que ce que je vais dormir ces prochaines heures.
Verdict : bluffé : c'est fou ce que ce sujet c'est rendu interressant !
Merci aus bons utilisateurs du forum, et sans jouer lesinspecteurs de traveaux finis,
chapeau à Blustuff pour ce cours de maths accéléré !
Je connaissais pas cette méthode, mais je l'aime bien aussi, ça me fait beaucoup penser à la méthode de Newton sur les recherche de racines d'une fonction par dichotomie.
Juste pour enrichir ce poste je signale qu'il y a aussi une méthode toute simple avec des divisions. Et ça peut se faire à la main sur un bout de papier, ça ressemble énormément aux divisions qu'on a tous eu l'habitude de faire à l'école étant gamins. Et comme pour les divisions, les chiffres après la virgule ne sont pas des problèmes. Les résultat sont exactement ceux d'une calculette.
@+
Normal, les calculettes effectuent les racines carrées par les méthodes de la divisions. Il faut jouer avec le reste de la division à chaque fois mais je ne sais plus trop comment ca fonctionne, mais si je me souvient bien n'importe quelle racine peut-être calculée à partir de cette méthode.
Tu peux l'exposer Morgatte ?
Voilà j'ai retrouvé comment on fait pour calculer une racine carrée à l'aide de somme et de division. En fait il s'agit de décomposer le resultat en une somme qu'on pourra obtenir par récursivité. ( j'm'explique)
Selon la formule :
x^2=a
2 x^2= x^2 + a
x = (x2 + a)/(2x)
x = (x + a/x)/2
Nous arrivons à la formule suivante :
x(i+1) = 1/2 ( xi + a / xi )
Nous devons donc calculer chaque résultat à partir du résultat précédent et nous pouvons commencer par n'importe quelle valeur de xi ( sauf 0 )
Exemple du calcul de la racine carrée de 2 :
x^2 = 2 =>> a = 2
i = 1 ==> 1/2 ( 1 + 2/1 ) = 1.5
i = 2 ==> 1/2 ( 1.5 + 2/1.5 ) = 1.416666667
i = 3 ==> 1/2 ( 1.416666667 + 2/1.416666667 ) = 1.414215686
i = 4 ==> 1/2 ( 1.414215686 + 2/1.414215686 ) = 1.414213562
que donne la calculette pour racine carrée de deux : 1.414213562. Nous obtenons donc la même réponse ( en fait parce que la calculette obtient le résultat par la même méthode
Bon amusement
Surtout parce que 1.414213562 est la meilleur approximation à 10 chiffre de sqrt(2). ;-)( en fait parce que la calculette obtient le résultat par la même méthode
Ah ben non, ma méthode est encore différente des deux vôtres. Comme quoi.
La tienne c'est encore un rapprochement du résultat par itérations successive.
Celle que je connais trouve exactement chaque chiffre de la racine à chaque nouvelle boucle. Exactement comme pour une division, on trouve le chiffre suivant. Y a pas d'approximation.
Mais je croix que sans papier ça va être difficile à expliquer. (Je peux pas disposer les chiffres comme je le voudrais).
Je vais essayer et je vous rappelle si je m'en souviens encore. C'est loin j'avoue.
Je ne pense pas qu'une vaut mieux qu'une autre, toutes doivent se valoir plus ou moins, vu que tout dépend de la précision voulue.
@+
lol non Morgatte, si tu trouves un chiffre par itération, je te rappelle que la Methode de Newton trouve deux fois plus de chiffres à chaque ittération. Donc elle est bien meilleure. Alucard, certes tu as la même formule que celle donnée par la Methode de Newton, mais ta suite je ne sais même pas pourquoi elle converge. La méthode de Newton donne la convergence de la suite pour racine carrée, parce que la dérivée de racine carrée est supérieure à 0, et ne change pas de signe. Ton calcul n'est pas une démonstration, où il en manque la moitié.
hum, pour moi ca parrait complet, je suis un peu ennuyé là :s Pourrais tu expliquer ce qui cloche dans mon explication ou dans le raisonnement parce que là je ne vois pas trop. :s
Ce qui cloche, c'est qu'il n'y a aucune raison que ta suite converge vers racine de a. Enfin du moins il faudrait l'expliciter.
Malheureusement je n'ai pas plus d'explications a donner que ca, il faudrait que je demande au prof qui m'a appris cette technique pour avoir plus d'explication.
Tout ce que je sais c'est que c'est une facon facile de trouver les racines carrée d'un nombre quelconque avec quelques circuits logique assez basiques.
Mais donner plus de renseignement il faudrait que je m'attarde un peu plus sur le probleme. Il y a peut-etre une astuce ou un raisonnement que je n'ai pas compris ou que j'ai passé pensant qu'il n'etait pas important.
J'vais voir pour améliorer ca
Mais il semble que les deux méthodes soient identiques, juste que j'ai tapé ce que j'avais dans mon cours sans vraiment chercher plus loin.
soit X un nombre dont on souhaite extraire la racine
soit A et B tel que A*B=X
pour trouver la racine de X il faut que A=B
mettons que B>A
cherchez pas à comprendre mais (A+B)/2>=sqr(A*B) et (A+B)/2<B
on trouve ainsi une nouvelle valeur B' qui est<B et >sqr(X)
suffit de calculer A' dans A*B=X ou A=X/B
A' sera<sqr(X)et>A
A augmente et B diminue en tandant tous deux vers la racine de X; ainsi de suite jusqu'à A=B ou B'=B
B'=((X/B)+B)/2
suis pas prof de math donc je sais pas si j'ai été ne serait-ce que clair pâle ou moyen
La première inégalité que tu poses, c'est le fait que la moyenne aithmétique est toujours plus petite que la moyenne géométrique. La seconde est facile à vérifier grace à la condiont B > A.
Les deux suites A et B sont respectivement croissantes et décrossantes, sont respectivement inférieures et supérieures à la racine. Ca ne suffit pas pour qu'elles convergent vers la racine. Je cherche, je cherche... Et il reste à trouver la vitesse de convergence également...
Les suites A_n et B_n sont respectivement majorée et croissante, et minorée et décroissante, donc Convergente. Pour n tendant vers l'infini on à B_n = B_(n+1) = (A_n + B_n) / 2. Donc A_n = B_n. Les deux suites converges vers L. Or A_n <= Racine de X <= B_n donc L <= X <= L Donc X = L. Les deux suites tendent vers racine de X.
Si on essaie de ne faire qu'avec une seule suite, B_n :
B_n+1 = (A_n + B_n) / 2 = (X/B_n + B_n) / 2
On a exactement la même formule de récurence que pour la méthode de Newton. Donc les calculs et la vitesse de convergence sont strictement les mêmes.
ben, c'est pas ça qu'j'ai dit?
avec mes mots à moi...
Vous avez un bloqueur de publicités installé.
Le Club Developpez.com n'affiche que des publicités IT, discrètes et non intrusives.
Afin que nous puissions continuer à vous fournir gratuitement du contenu de qualité, merci de nous soutenir en désactivant votre bloqueur de publicités sur Developpez.com.
Répondre avec citation
Partager