Metodo babilonese

di
Radici e zeri

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

n > 4

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

Segui i passi

Osserva…
\displaystyle x_1 = \frac{n}{2}Un’approssimazione ragionevole
2\ < \ x_* \ < \ x_1 \ < \ n
\displaystyle x_2 = \frac{n}{x_1}Un’altra approssimazione ragionevole
x_1 \cdot x_2 = n
2\ = \ x_2 \ < \ x_* \ < \ x_1 \ < \ n
\displaystyle x_3 = \frac{x_1 + x_2}{2}Ancora un’approssimazione ragionevole
2\ = \ x_2 \ < \ x_* \ < \ x_3 \ < \ x_1 \ < \ n
\displaystyle x_4 = \frac{n}{x_3}Ripete il 2° passo
\displaystyle x_5 = \frac{x_3+x_4}{2}Ripete il 3° passo
…Continua…

Riorganizza i passi precedenti

  • Considera n=256
  • 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 …
Passox_A\displaystyle x_B = \frac{n}{x_A}\displaystyle x_M = \frac{x_A+x_B}{2}
1128,000000002,0000000065,00000000
265,000000003,9384615434,46923077
334,469230777,4269136420,94807220
420,9480722012,2206949416,58438357
516,5843835715,4362083416,01029596
616,0102959615,9897106716,00000331

Perché funziona?

Osserva l’immagine

  • x_A e x_B convergono verso x_*
  • x_M è sempre in mezzo…

A ogni iterazione

  • 2\ < \ x_B \ < \ x_* \ < \ x_M \ < \ x_A \ < \ 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_B e x_A

n > 0

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 2 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}
    Distanza tra due soluzioni successive, in rapporto con l’ultima approssimazione (diventa una percentuale)
    Si usa se l’ordine di grandezza dei numeri in gioco è molto alto o molto basso

Esempio

n=256

Passox_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}%
1128,000000002,0000000065,0000000063,000000000,9692307796,923077 %
265,000000003,9384615434,4692307730,530769230,8857397988,573979 %
334,469230777,4269136420,9480722013,521158570,6454607664,546076 %
420,9480722012,2206949416,584383574,363688630,2631203426,312034 %
516,5843835715,4362083416,010295960,574087620,035857403,585740 %
616,0102959615,9897106716,000003310,010292650,000643290,064329 %

Conclusione…

Le 6 colonne precedenti si possono ridurre a 2, o addirittura a 1!

  • La prima approssimazione è \displaystyle x_1 = \frac{n}{2}
  • Le approssimazioni successive diventano \displaystyle x_{i+1} = \frac{x_i + \frac{n}{x_i}}{2}
  • Scegli il criterio per fermare l’iterazione (per esempio errore assoluto)
PassoApprossimazioneErrore
1\displaystyle \frac{256}{2}= 128,00000000
2\displaystyle \frac{128 + \frac{256}{128}}{2}= 65,0000000063,00000000
3\displaystyle \frac{65 + \frac{256}{65}}{2}= 34,4692307730,53076923
4…= 20,9480722013,52115857
5…= 16,584383574,36368863
6…= 16,010295960,57408762
…………