Répondre

yoshi · 25-06-2024 10:18:34

Bonjour,

Méthode de Heron.
Vitesse de convergence

Google a écrit :

La méthode de Héron est un cas particulier de la méthode de Newton pour la détermination de solution d'une équation de la forme $f(x)=0$ avec $f(x)=x^2−a$. Sa vitesse de convergence est très rapide : la convergence de la suite sous-jacente est quadratique donc le nombre de décimales exactes double à chaque tour de boucle.

Voir encore :
https://fr.wikipedia.org/wiki/M%C3%A9th … H%C3%A9ron
https://mathrais.fr/methode-heron/ (video très simple et claire)

ou

Grand oral
Étude de la convergence de la méthode de Héron.
Question :
Pourquoi la méthode de Héron permet d’obtenir rapidement une approximation de la racine carrée d’un nombre positif A ?
(...)
La suite ici :
https://pedagogie.ac-reunion.fr/fileadm … _Heron.pdf

Et ;-)
N-B : Pour débuter avec Latex (rien de bien compliqué), voir Code Latex

@+

[EDIT] On trouve beaucoup de choses sur Bibmath... ^_^
Méthode de Newton-Raphson, et approximation de racine de 2 par la méthode d'Héron d'Alexandrie :
https://www.bibmath.net/dico/index.php? … _meth.html

Bal3s · 24-06-2024 21:43:45

Merci beaucoup pour vos réponses!

Je me dis que je pourrait alors comparer la suite donnée par la méthode de Newton et de Héron à ce que j'obtiendrai avec une dichotomie par exemple?
Je ne sais pas si c'est possible , étant donné que la dichotomie ne répond pas au même fonctionnement qu'une suite...
Peut être en comparant le nombre d'itération nécessaire pour obtenir une certaine précision/erreur absolue?
Je sais que cette erreur absolue est de (b-a)/(2^(n+1)) pour la dichotomie mais je n'en ai pas la moindre idée en ce qui concerne la méthode de Héron

ps: je m'excuse pour ce qui est de ma piètre connaissance en ce qui est du LATEX et qui rend ceci quelque peu horrible à lire

yoshi · 23-06-2024 20:06:54

RE,

Je me suis beaucoup penché sur la méthode de Heron d'Alexandrie pour le calcul ultra rapide de la racine carrée d'un entier.
Je connaissais déjà la méthode de calcul par dichotomie, et celle - sans nom - apprise au Lycée en 4e dans les années 60...
J'ai donc implémenté ces 3 méthodes en langage Python.
Voici le script Python pour la méthode de Heron :

#!/usr/bin/env python

# coding: utf-8 -*-

from time import time

from decimal import Decimal as D,getcontext

from math import sqrt

def rac(n,prc):

    getcontext().prec=prc+2

    E=int(sqrt(n))

    u=D(E)         # Pour ne pas être trop loin de la racine cherchée

    q=D(E-1)

    epsilon=D(1)/D((10**prc))

    i=0

    while abs(q)>D(2)*epsilon:

        u=(u**2+D(n))/(u*D(2))

        q=abs(D(n)/u-u)

        i+=1   

    return u,i

debut=time()

radicande = 5   # nombre dont vous recherchez la racine carrée

precision = 2000 # Précision souhaitée

u,i=rac(radicande,precision)

print ("Racine cherchée :")

print (u)

print("\nNombre d'Itérations :", i)

print("Effectuées en :",time()-debut,"s")

Et j'obtiens en lançant le script :

Racine cherchée :
2.236067977499789696409173668731276235440618359611525724270897245410520925637804899414414408378782274969508176150773783504253267724447073863586360121533452708866778173191879165811276645322639856580535761350417533785003423392414064442086432539097252592627228876299517402440681611775908909498492371390729728898482088641542689894099131693577019748678884425089754132956183176921499977424801530434115035957668332512498815178139408000562420855243542235556106306342820234093331982933959746352271201341749614202635904737885504389687061135660045757139956595566956917564578221952500060539231234005009286764875529722056766253666074485853505262330678494633422242317637277026632407680104443315825733505893098136226343198686471946989970180818952426445962034522141192232912598196325811104170495807048120403455994943506855551855572512388641655010262436312571024449618789424682903404474716115455723201737676590460918529575603577984398054155380779064393639723028756062999482213852177348592453515121046345555040707227872421534778752911212121184331789335191038008011118179004590618846249647104244248308880129406811314695953279447898998931691577460792461807500679877124204847380502773608291559913962448914943560683462529064408327944642680888989746046308353537875042061374757606883401879088192559117973574464190248537871146194090191913688035110397638436041281058110378698951852014697045642021763892890884446377826385893792440046028875405398460156061705223615090385775410042193684987254271850375215557693316723004778269866662446210678464272486385274578213410067985645305271124180595972849455195451310172309750871496529436282902540012047780324155464489988706177998190033606562243886409639287753517266295971438227956307956149523015444235016538917278640913041979397111356282139367457681174922067562108887818873671671627622623379877111539509682982890683018259081401003895509723261508452834587893607346396117236678366571982607921440289119008995584241522495712918323216741189975720139403788197728015288723418668345418382867300274314
Nombre d'Itérations : 11
Effectuées en : 0.1520085334777832 s

Pourquoi l'exemple avec $\sqrt 5$ ?
Il y a bien longtemps, un copain libraire m'avait remonter une demande d'un de ses clients qui souhaitait avoir une valeur décimale de $\left( \phi =\dfrac{1+\sqrt 5}{2}\right)$. Grâce à ma calculette, j'en avais proposé 18.
Réponse : il en a déjà 30... et il en voudrait le maximum possible.
Alors j'avais dû écrire en BASIC sur mon ordi d'alors (le constructeur venait de sortir unr version de sa bécane fonctionnant non plus avec des cassettes mais avec des disquettes) la seule méthode que je connaissais alors (celle apprise en 4e). mais pour cela j'avais dû réécrire les 4 opérations...
Ca fonctionnait : 1 h pour 100 décimales (vitesse d'horloge de la machine : 4,77 MHz, RAM 128 Ko)

Puis au hasard d'une question sur Bibmath il y a quelques années, j'avais découvert qu'on pouvait utiliser le procédé pour le calcul de la racine cubique (et je l'ai aussi implémenté en Python)...
Le sujet est ici : https://www.bibmath.net/forums/viewtopi … 519#p90519

N-B : ces calculs avec autant de décimales sont rendus possibles que par l'importation du module decimal qui contient la classe Decimal (qui fait appel de façon totalement transparente pour l'utilisateur lambda aux fractions continues - paraît qu'on dit maintenant fractions continuées) .
Je n'ai besoin d'importer en fait que cette classe et je ,'ai besoin que de choisir un radicande et le nombre de décimales souhaité.

Si tu es intéressé, je peux expliquer en détail le fonctionnement de mon script Python, ou autre...

@+

Roro · 23-06-2024 17:28:03

Bonjour,

Si tu as un peu commencé à travailler tu as dû te rendre compte que les deux méthodes que tu évoques sont exactement les mêmes !

En effet, si tu appliques la méthode de Newton pour trouver l'endroit où la fonction $f:x\longmapsto a-x²$ s'annule, tu vas construire la suite $(v_n)_n$ définie par récurrence par
$$v_{n+1} = v_n-\frac{f(v_n)}{f'(v_n)} = v_n + \frac{a-v_n²}{2v_n} = \frac{1}{2}(v_n + \frac{a}{v_n}).$$

C'est donc exactement la même chose que d'utiliser la suite $(u_n)_n$ que tu proposes...

En fait, la méthode de Héron (celle qui consiste à utiliser la suite comme celle que tu introduis pour $(u_n)_n$) est un cas particulier de la méthode de Newton...

Roro.

Bal3s · 23-06-2024 16:39:55

Bonjour, je suis en train de rédiger mon grand oral sur le thème suivant "Déterminer la valeur décimale d’une racine carrée?"
Je fais face à un problème: j'aimerai comparer les méthodes que je propose mais je ne sais pas trop comment m'y prendre.
Voici les 2 méthodes principales utilisées pour déterminer la racine d'un réel quelconque a:
- Utilisation d'une fonction auxiliaire ( f:x → a-x²) de laquelle je détermine les racines à l'aide de la méthode de Newton (tracé de tangentes successives)
-Utilisation d'une suite Un+1=(Un+(a/Un))/2 donc je démontre la convergence vers racine de a

Merci d'avance pour vos éventuelles réponses

Forum de mathématiques - Bibm@th.net

Répondre

Résumé de la discussion (messages les plus récents en premier)

Grand oral

Pied de page des forums