Radice quadrata – Metodo babilonese

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…

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 …

Passo	$x_A$	$\displaystyle x_B = \frac{n}{x_A}$	$\displaystyle x_M = \frac{x_A+x_B}{2}$
1	128,00000000	2,00000000	65,00000000
2	65,00000000	3,93846154	34,46923077
3	34,46923077	7,42691364	20,94807220
4	20,94807220	12,22069494	16,58438357
5	16,58438357	15,43620834	16,01029596
6	16,01029596	15,98971067	16,00000331

Osserva l’immagine

A ogni iterazione

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

A ogni passo

Nei primi 2 passi $x_A$ e $x_B$ 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_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

n=256

Passo	$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}$	%
1	128,00000000	2,00000000	65,00000000	63,00000000	0,96923077	96,923077 %
2	65,00000000	3,93846154	34,46923077	30,53076923	0,88573979	88,573979 %
3	34,46923077	7,42691364	20,94807220	13,52115857	0,64546076	64,546076 %
4	20,94807220	12,22069494	16,58438357	4,36368863	0,26312034	26,312034 %
5	16,58438357	15,43620834	16,01029596	0,57408762	0,03585740	3,585740 %
6	16,01029596	15,98971067	16,00000331	0,01029265	0,00064329	0,064329 %

Le 6 colonne precedenti si possono ridurre a 2!

	Approssimazione	Errore assoluto
$\displaystyle x_1 = \frac{n}{2}$	128,00000000
$\displaystyle x_2 = \frac{x_1 + \frac{n}{x_1}}{2}$	65,00000000	63,00000000
$\displaystyle x_3 = \frac{x_2 + \frac{n}{x_2}}{2}$	34,46923077	30,53076923
$\displaystyle x_4 = \frac{x_3 + \frac{n}{x_3}}{2}$	20,94807220	13,52115857
$\displaystyle x_5 = \frac{x_4 + \frac{n}{x_4}}{2}$	16,58438357	4,36368863
$\displaystyle x_6 = \frac{x_5 + \frac{n}{x_5}}{2}$	16,01029596	0,57408762
…	…	…
$\displaystyle x_{i+1} = \frac{x_i + \frac{n}{x_i}}{2}$	…	…