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}
    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_1=x_3, la media calcolata nel passaggio precedente
    • x_1=x_3
    • x_2=\frac{n}{x_1}
    • x_3=\frac{x_1+x_2}{2}

Esempio: n=256

x_1 x_2=\frac{n}{x_1} x_3=\frac{x_1+x_2}{2}
128,000000… 2,000000… 65,000000…
65,000000… 3,938461… 34,469230…
34,469230… 7,426913… 20,948072…
20,948072… 12,220694… 16,584383…
16,584383… 15,436208… 16,010295…

Si può esprimere in modo più compatto…

  • Prima approssimazione: x_1=\frac{n}{2}
  • Approssimazioni successive: x_{i+1}=\frac{x_i+\frac{n}{x_i}}{2}

Esempio: n=256

x_1=\frac{n}{2} 128,000000…
x_2=\frac{x_1+\frac{n}{x_1}}{2} 65,000000…
x_3=\frac{x_2+\frac{n}{x_2}}{2} 34,469230…
x_4=\frac{x_3+\frac{n}{x_3}}{2} 20,948072…
x_5=\frac{x_4+\frac{n}{x_4}}{2} 16,584383…
x_6=\frac{x_5+\frac{n}{x_5}}{2} 16,010295…

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

Nell’esempio precedente


In realtà l’algoritmo funziona per qualsiasi valore di n (positivo…) e per qualsiasi approssimazione iniziale (positiva…)

A ogni passo

  • n=x_1\cdot x_2
  • se x_1 > \sqrt{n} allora x_2 < \sqrt{n}
  • se x_1 < \sqrt{n} allora x_2 > \sqrt{n}
  • x_3 sarà compreso tra x_1x_2 e sempre più vicino a \sqrt{n}

Nei primi passi x_1x_2 potrebbero scambiarsi di posto ma poi tutto continuerà come prima.


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_1-x_3|, distanza tra due soluzioni successive
  • Errore relativo: E_r=\frac{|x_1-x_3|}{x_3}, errore in rapporto all’ultima approssimazione
    Si usa se l’ordine di grandezza dei numeri in gioco è molto alto o molto basso

Esempio precedente

x_i E_a E_r
128,000000…
65,000000… 63,000000… 0,9692…
34,469230… 30,530769… 0,8857…
20,948072… 13,521158… 0,6454…
16,584383… 4,363688… 0,2631…
16,010295… 0,574087… 0,0358… (3,58 %)


Codifica: Python



Wikipedia: Metodi per il calcolo della radice quadrata

Notice: This work is licensed under a BY-NC-SA. Permalink: Metodo babilonese

Comments are closed.