programme : calcul de la racine carrée d'un nombre (methode de newton)

[invitebd1ce6b7]

bonsoir a tous,
j'ai ecris un programme qui calcule la racine carrée d'un nombre lu au clavier par
la methode de newton : (ak+1 =0.5*(ak+x/ak) <- la k ieme approximation de la
racine carrée de x (sachant que a0 = 1.0)
on arrete le calcul quand la difference entre ak+1 et ak est inferieure à epsilon fixé.
mon programme marche mais du moment ou je choisis de grands nombres l'approximation
n'est plus top
en plus je sais pas comment choisir le epsilon ( la condition du tant que : ak+1 - ak < epsilon)
voici mon programme :

WITH Ada.text_io;
WITH Ada.float_text_io;
USE Ada.text_io;
use Ada.float_text_io;


--spécification:
--R0: ecrire un programme qui calcule la racine carrée d'un nombre lu au clavier, par la méthode de Newton
--Tests: on testera le programme sur les valeurs suivantes: 4,9,16,0,34,13.9


--R1+Analyse informelle:
--1)demander a l'utilisateur de taper un nombre strictement positif
--2)lire le nombre pour lequel on souhaite calculer la racine
--3)calculer la racine en utilisant la methode de newton


--R2:
--1)je sais faire (on utilisera une boucle repeter jusqu'à pour imposer à l'utilisateur de taper un nombre strictement positif
--2)je sais faire
--3)on utilisera une boucle tant que car on ne sais pas si on doit executer l'instruction au moins une fois


PROCEDURE racine IS
--un programme qui calcule la racine carrée d'un nombre lu au clavier, par la méthode de Newton
--declarations des variables
x : FLOAT; --le nombre pour lequel on souhaite calculer la racine carrée
Un : FLOAT; --le terme courant de la suite qui permet d'approximer la racine carrée de x
n : INTEGER; --le rang courant de la suite de Newton
BEGIN
--demander a l'utilisateur de taper un nombre strictement positif
LOOP
PUT("veuillez taper un nombre strictement positif pour lequel vous souhaiter calculer la racine carrée : ");
GET(x);
EXIT WHEN (x>0.0);
END LOOP;
--x>0
--initialisation des variables
Un:=1.0;
n:=0;
--on fait le calcule pour simplifier Un+1 - Un comme ci-dessous en utilisant pour Un+1 la formule de newton
WHILE ((0.5*((x/Un)-Un))>0.00001) LOOP
Un:=0.5*(Un+x/Un);
n:=n+1;
END LOOP;
--(0.5*((x/Un)-Un))<0.00001
--afficher le resultat
PUT("la racine carrée de ");
PUT(x);
PUT(" est : ");
PUT(Un);
END racine;

merci enormement d'avance pour votre aide
-----

[WizardOfLinn]

C'est un peu dommage de calculer deux fois le terme de la suite pour chaque boucle. Ce n'est pas un bug, mais une petite maladresse.

Pour limiter la propagation des erreurs d'arrondis lors du calcul de la racine de grands nombres, je suggérerais de commencer par mettre le nombre sous la forme x = 4^m*y (par exemple), avec 1<=y<4
Calculer Racine(x) revient alors calculer 2^m*Racine(y), où y est compris entre 1 et 4.

Le "bon" choix du epsilon dépend de la précision de la représentation des nombres en virgule flottante et l'algorithme peut être instable si le epsilon est choisi trop petit. Les flottants codés sur 4 octets (par exemple) ont 6 chiffres significatifs.

[Jack]

en plus je sais pas comment choisir le epsilon ( la condition du tant que : ak+1 - ak < epsilon)

Encore faut-il que ak+1 soit supérieur à ak pour que cette condition soit correcte. Si dans ta boucle la différence devenait négative, tu en sortirais prématurément.
Mais tout ça aurait pu être déduit en affichant la suite des valeurs de ak au cours de la boucle pendant la mise au point du programme.
La bonne condition est donc : |ak+1 - ak| < epsilon

[invitebd1ce6b7]

merci beaucoup pour la reponse mais je comprends pas tres bien le role du m ni
pourquoi on calcule racine (y) pour en deduire racine x ? et pourquoi le choix de 4^m*y ??

[A voir en vidéo sur Futura]

[invitebd1ce6b7]

merci beaucoup pour la reponse ! oui je vois aussi l'utilité de la valeur absolue !
mais j'ai encore du mal à choisir epsilon (j'arrive pas à le mettre en code )!!

[WizardOfLinn]

En fait, pour que le epsilon soit indépendant du résultat, la condition est |(ak+1 - ak)/ak|, erreur relative. Ainsi, le choix du epsilon ne dépend plus que de la précision des flottants utilisés. Prendre 10^-5 ou 10^-6 s'il s'agit de flottant simple précision, par exemple.
Sinon, la méthode que j'ai proposée permet d'accélérer la convergence et de gérer différemment la précision, même si c'est plus compliqué. Au lieu de calculer directement la racine d'un grand nombre, le problème se réduit à calculer la racine d'un nombre entre 1 et 4. Et le choix de 4^m n'est pas le seul possible, on peut utiliser d'autres factorisations dont la racine carré est connue de façon exacte, sans erreur d'arrondi.

Mais déjà, avec ton programme, en exprimant la condition en erreur relative, ça devrait mieux marcher.