calcul de la racine carrée par la méthode de Newton

Version imprimable

31/10/2006, 10h23
annoussa

calcul de la racine carrée par la méthode de Newton
salut!!!
je suis en train d'écrire une fonction qui calcule la racine carrée d'un réel positif a par la methode de newton.
la racine carrée d'un reel>0 est egale à la limite de la suite (Xn) n>0
X indice(n+1)= 1/2 *( x indice n + a / x indice n)
X0 est arbitraire
Code:

1 2 3 4 5 6 7 8 9 entrer(a); entrer (X0); n <-0 tant que ??? x(n+1)<- 1/2 *( x indice n + a / x indice n) n<-n+1 fin tant que
et apres on fait une boucle mais quelle est la condition d'arrêt!!!!!
et quand on retourne la racine carrée de a!!!!!
merci de me conseiller!!
31/10/2006, 10h28
Matthieu Brucher

Tu peux utiliser la précision pour faire ton calcul.
31/10/2006, 10h30
®om

Vu que tu sais que ta suite converge (en tout cas en mathématiques, car en représentation flottante ça doit être plus dur à prouver), tu peux comparer l'écart entre Xn et Xn+1 (divisé par Xn pour prendre en compte l'ordre de grandeur). Donc tu t'arrêtes lorsque (|Xn+1 - Xn| / |Xn|) < ε... Il faut maintenant déterminer ton ε:)
31/10/2006, 10h47
nletteron

J'allais le dire. Ta suite est convergente donc

| x(n+1) - x(n) | < epsilon

Epsilon est une valeur très petite. A toi de voir quelle est le meilleur rapport qualité du résultat, temps de l'algorithme.

je ce bout de code ici (Delphi)

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
 
// distance de deux points
Function Distance(x1, y1, x2, y2 : integer): integer;
// Calcul de l'hypothénuse a := sqrt(dx*dx+dy*dy)
// en utilisant la formule de Newton pour le calcul de la racine carrée
// 12 itérations suffisent :  sqrt(a) -->  Xo = (1+a)/2  et  Xn+1 = (xn+a/xn)/2
// C'est 3 fois plus rapide que  j := trunc(sqrt(sqr(dx)+sqr(dy)))
var
  i : Integer;
  a, r0, r1 : Integer;
begin
  r0 := x2-x1;      
  r1 := y2-y1;
  a := r0*r0 + r1*r1;
  r1 := (1+a) DIV 2;
  FOR i := 1 TO 12 DO
  begin
    r0 := r1;
    IF r0 > 0 then r1 := (r0+(a div r0)) div 2;
  end;
  Result:= r1;
end;

31/10/2006, 15h47
random

à la vitesse ou l'itération converge 12 itérations c'est déja énorme
surtout si on choisit inteligemment l'amorce

étant donnée qu'un entier est sur 32 Bits

est-ce qu'il ne serait pas possible de choisir le nombre d'itération
en fonction de la grosseur du chiffre initial?

exemple
Code:

1 2 3 4 5 6 7 8 si Chiffre initiale < 16777215 (24bits) Nombre d'iteration=8 else si Chiffre initiale < 65535 (16bits) Nombre d'iteration=6 else si Chiffre initiale < 255 (8bits) Nombre d'iteration=4 else Nombre d'iteration=12
où quelque chose du genre?

j'ai trouvé que (à l'aide de mon cpu)

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
 
    Racine de:  | Nombre d'iteration
=====================================
            8   |    2
           24   |    3
           48   |    4
          120   |    5
          360   |    6
        1 088   |    7
        3 135   |    8
        9 999   |    9
       31 328   |    10
      103 040   |    11
      342 224   |    12
    1 151 328   |    13
    3 920 399   |    14
   13 571 855   |    15
   47 416 995   |    16
  166 642 280   |    17
  590 733 024   |    18
2 105 524 995   |    19

donc pour une réponse valide avec 12 iterations
le nombre doit être inférieur à 1 151 328

je me demande quand le nombre d'iteration devient
plus couteux (en cycle CPU) que de faire

trunc(sqrt(NombreAuCarre))

31/10/2006, 19h44
j.p.mignot

Si on considère la suite
x(n+1) = 1/2 *( x indice n + a / x indice n)
elle décroît dès l'indice 2 avec Xn > sqrt(a); Elle converge vers sqrt(a).
Si maintenant on considère la 2eme suite Yn = a/ Xn,
elle croit avec Yn < sqrt (a) aussi dès n >=2. Elle converge aussi vers sqrt(a).
{ La suite X peut croître entre X0 et X1 si X0 < sqrt(a) }

donc en tout cas dès l'index 2 on a.
Yn= a/Xn < sqrt(a) < Xn

Pour assurer un nombre d'itérations donnant sqrt(a) <= Xn < sqrt(a) + Epsilon,
il suffit de satisfaire Xn - a/Xn < Epsilon ( Condition suffisante, pas obligatoirement nécessairement )
02/11/2006, 11h10
random

oui si on choisit une amorce au hasard le nombre d'itérations est plus important
mais on peut choisir l'amorce de la façon suivante
10^(nombredechiffresdelapartieentièredunombre/2)
2 105 524 995 est ainsi parfaitement traité en 7 itérations avec epsilon = 10^-12