Metodo babilonese

L’algoritmo è noto come metodo babilonese oppure di Archita, di Erone, …

Sia n, con n > 4, il numero in ingresso e x la sua radice quadrata allora 2 < x < n

Prima approssimazione: x_1=\frac{n}{2}

2 < x < x_1 < n

Seconda approssimazione: x_2=\frac{n}{x_1}

x_1 \cdot x_2 = n

2=x_2 < x < x_1 < n

Terza approssimazione: x_3=\frac{x_1+x_2}{2}

x_2 < x_3 < x_1

Ripeti i calcoli con x_4=x_3, la media calcolata nel passaggio precedente

x_4=x_3

\displaystyle x_5=\frac{n}{x_4}

\displaystyle x_6=\frac{x_4+x_5}{2}

Ripeti …

Esempio

n=256

Osserva

  • In prima colonna, x_A: un’approssimazione della radice che nella prima riga è n/2 e successivamente sarà il valore in ultima colonna della riga precedente
  • In seconda colonna, x_B: la divisione tra …
  • In terza colonna, x_M: la media aritmetica tra …
x_A \displaystyle x_B=\frac{n}{x_A} \displaystyle x_M=\frac{x_A+x_B}{2}
128,00000000 2,00000000 65,00000000
65,00000000 3,93846154 34,46923077
34,46923077 7,42691364 20,94807220
20,94807220 12,22069494 16,58438357
16,58438357 15,43620834 16,01029596
16,01029596 15,98971067 16,00000331

Perché funziona?

Osserva lo schema a destra (n > 4)

  • x_Ax_B convergono verso x
  • x_M è sempre in mezzo…

A ogni iterazione

  • 2 \ll x_B < x < x_M < x_A \ll n
  • x_A si allontana da n e si avvicina da destra a x
  • x_B si allontana da 2 e si avvicina da sinistra a x
  • x_M si trova tra x_Bx_A

Se rappresenti graficamente i valori dell’esempio precedente

Funziona sempre?

L’algoritmo funziona per qualsiasi valore di n (positivo…) e per qualsiasi approssimazione iniziale (positiva…)

A ogni passo

  • n=x_A\cdot x_B
  • se x_A > \sqrt{n} allora x_B < \sqrt{n}
  • se x_A <  \sqrt{n} allora x_B > \sqrt{n}
  • x_M sarà compreso tra x_A e x_B e sempre più vicino a \sqrt{n}

Nei primi passi x_A e x_B potrebbero scambiarsi di posto ma poi tutto continuerà come prima.

Quante iterazioni?

Per decidere quando fermare l’iterazione si può stabilire un valore soglia ε e fermare l’iterazione quando l’errore è minore di ε

Si può scegliere tra

  • Errore assoluto, E_a=|x_A-x_M|, distanza tra due soluzioni successive
  • Errore relativo: \displaystyle E_r=\frac{|x_A-x_M|}{x_M}, errore in rapporto all’ultima approssimazione
    Si usa se l’ordine di grandezza dei numeri in gioco è molto alto o molto basso

Esempio

n=256

x_A \displaystyle x_B=\frac{n}{x_A} \displaystyle x_M=\frac{x_A+x_B}{2} E_a=|x_A-x_M| \displaystyle E_r=\frac{|x_A-x_M|}{x_M}
128,00000000 2,00000000 65,00000000 63,00000000 0,96923077 96,923077 %
65,00000000 3,93846154 34,46923077 30,53076923 0,88573979 88,573979 %
34,46923077 7,42691364 20,94807220 13,52115857 0,64546076 64,546076 %
20,94807220 12,22069494 16,58438357 4,36368863 0,26312034 26,312034 %
16,58438357 15,43620834 16,01029596 0,57408762 0,03585740 3,585740 %
16,01029596 15,98971067 16,00000331 0,01029265 0,00064329 0,064329 %

Le 6 colonne precedenti si possono ridurre a 2

  • Prima approssimazione: x_1=\frac{n}{2}
  • Approssimazioni successive: x_{i+1}=\frac{x_i+\frac{n}{x_i}}{2}
  • Scegli quale criterio utilizzare per fermare l’iterazione

Esempio

n=256

x_i E_i
1 128,00000000
2 65,00000000 63,00000000
3 34,46923077 30,53076923
4 20,94807220 13,52115857
5 16,58438357 4,36368863
6 16,01029596 0,57408762
7 16,00000331 0,01029265

Wikipedia: Metodi per il calcolo della radice quadrata