Calcolo della radice quadrata

Da Wikipedia, l'enciclopedia libera.

Voce principale: Radice quadrata.

Questa voce è dedicata ai molti metodi che sono stati utilizzati per calcolare radici quadrate di numeri reali positivi, o per meglio dire, per calcolare le radici quadrate principali di numeri razionali.

Indice

1 Note storiche
2 Metodo babilonese
3 Approssimazione Bakhshali
- 3.1 Esempio di approssimazione Bakhshali
4 Calcolo della radice quadrata di un intero: algoritmo di Bombelli
- 4.1 Calcolo della radice quadrata con qualsivoglia precisione
5 Radici quadrate usando il metodo iterativo di Newton
6 Approssimazione semplice
- 6.1 Costruzione
7 Metodo delle equazioni quadratiche
- 7.1 Esempio di uso del metodo dell'equazione quadratica
8 Voci correlate

[modifica] Note storiche

I primi ad occuparsi del problema dell'estrazione di radice quadrata di un numero sono stati i babilonesi. Essi, tra i primi ad utilizzare un sistema di numerazione posizionale, avevano elaborato un procedimento per l'estrazione di radice quadrata che spesso viene attribuito a matematici posteriori, come Archita (428 - 365 a.C.) oppure ad Erone di Alessandria (vissuto tra il I° e II° sec. d.C.) oppure a Newton.

I babilonesi avevano ricavato un valore di $\sqrt {2}$ pari a 1,414222 con un errore di 0,000008 dal valore vero. Di Erone di Alessandria, matematico e scienziato greco, si hanno poche notizie biografiche. Si occupò di meccanica, matematica e fisica. A lui si deve la formula (detta appunto formula di Erone) mediante la quale calcolare l'area di un triangolo qualsiasi, noti i suoi lati. Studiò metodi approssimati per risolvere problemi di misurazione, sia in geometria che in geodesia ed inventò un metodo per approssimare le radici quadrate e cubiche di numeri che non siano quadrati o cubi perfetti. E proprio del metodo di approssimazione delle radici quadrate di cui vogliamo occuparci.

[modifica] Metodo babilonese

Un algoritmo per approssimare $\sqrt z$ comunemente usato è conosciuto come metodo babilonese ed è basato sul metodo di Newton. Questo metodo funziona nel modo seguente:

Poni n=1 e inizia con un valore arbitrario positivo $x n$ (quanto più esso è prossimo alla radice, tanto migliore è la convergenza dell'algoritmo)
sostituisci $x n$ con la media di $x n$ e $z / x n$
aumenta n e vai al punto 2

Questo è un algoritmo a convergenza quadratica, il che vuol dire che il numero di cifre corrette $r$ grossolanamente raddoppia ad ogni passo.

Questo algoritmo può essere rappresentato dalla relazione di ricorrenza

$x_{n+1} = 0,5 \left(x_n + \frac{z}{x_n}\right)$

dalla quale si ricava $\lim_{n \to \infty} x_n = \sqrt z$ .

Ad esempio, poiché la radice quadrata di 2 deve essere compresa tra 1 e 2, stimiamo che sia circa 1,5. Applicando ripetutamente la formula otteniamo i seguenti valori:

$x_0 \,=\, 1,5$

$x_1 = \frac{1,5 + 2/1,5}{2} = 1,416667$

$x_2 = \frac{1,416667 + 2/1,416667}{2} = 1,414216$

$x_3 = \frac{1,414216 + 2/1,414216}{2} = 1,414214$

$x_4 = \frac{1,414214 + 2/1,414214}{2} = 1,414214$

$\cdots$ ;

in tal modo al quarto passaggio si ha il valore della radice quadrata di 2 corretto alla sesta cifra decimale.

Questo algoritmo funziona ugualmente bene per i numeri p-adici, ma non può essere usato per identificare radici quadrate reali con indice di radice p-esimo. Riferendosi a questo metodo è facile per esempio costruire una sequenza di numeri razionali che converge a $+ 3$ nei reali, ma a $- 3$ nei 2-adici.

[modifica] Approssimazione Bakhshali

Il metodo Bakhshali è un metodo matematico per trovare un'approssimazione della radice quadrata di un numero che fu descritto in un antico manoscritto col nome di Manoscritto Bakhshali perché fu scoperto nel 1881 vicino al villaggio di Bakhshali (o Bakhshalai) nella frazione Yusufzai del distretto di Peshawar (ora parte del Pakistan). Il testo era scritto nel linguaggio Sarada su corteccia di betulla.

L'approssimazione Bakhshali della radice quadrata si ottiene applicando due volte l'approssimazione semplice.

Con le notazioni precedenti introduciamo $P \,:=\, \frac{d}{2 N} ~~\mbox{e}~~ A := N + P$

$\sqrt{N^2 + d} \approx A - \frac{P^2}{2 A}$

Sviluppando l'equazione diventa:

$\sqrt{N^2 + d} \approx N + \frac{d}{2\,N} - \frac{d^2}{8\,N^3 + 4\,N\,d}$

[modifica] Esempio di approssimazione Bakhshali

Trova $\sqrt{9.2345}$

Usiamo $\, N=3 ~~\mbox{e}~~ d = 9,2345 - 3^2 = 0,2345$

$\sqrt{3^2 + d} \approx 3 + \frac{d}{6} - \frac{d^2}{216 + 12\,d}$

$\sqrt{3^2 + 0,2345} \approx 3 + \frac{0,2345}{6} - \frac{0,2345^2}{216 + 12 \cdot 0,2345}$

$\sqrt{3^2 + 0,2345} \approx 3 + 0,039083 - \frac{0,055}{216 + 2,814}$

$\sqrt{3^2 + 0,2345} \approx 3 + 0,039083 - 0,000251$

$\sqrt{3^2 + 0,2345} \approx 3,038832$

[modifica] Calcolo della radice quadrata di un intero: algoritmo di Bombelli

Questo algoritmo si applica alla notazione decimale (e più in generale ad una scrittura posizionale in una qualsiasi base b) di numeri interi e fornisce la parte intera della radice e l'eventuale resto.

Per tale calcolo si inizia distinguendo nella scrittura in base 10 del radicando gruppi di due cifre, consecutive partendo dal gruppo formato dalla cifra delle unità e da quella delle decine; il gruppo delle cifre di maggior peso può ridursi ad una cifra (come nell'esempio che segue). Risulta comodo scrivere il risultato in costruzione al di sopra di questa scrittura collocando ciascuna cifra del risultato sopra un corrispondente gruppo di cifre del radicando: infatti il numero L di cifre decimali del risultato è uguale al numero dei gruppi di cifre del radicando.

Si opera con tre variabili intere correnti: il risultato in costruzione x, un resto r e una cifra d da accodare alla precedente scrittura di x. Inizialmente x ed r sono poste a 0 e si procede a ripetere L volte il seguente blocco di istruzioni.

Modifica la scrittura del resto r accodandole il gruppo di cifre più significativo (quelle più a sinistra) non ancora usato.
Trova la più grande cifra $d$ tale che $y : = d (20 x + d)$ non superi $c$ . Accoda questa nuova cifra alla scrittura del risultato x.
Sottrai $y$ da $r$ e ottieni così il nuovo resto.

Esempio: Trova la radice quadrata di 1522759.

           1  2 3  4 
       |  01 52 27 59                              1    prima cifra della soluzione
x         01                   1(20*0+1)=1        +1 
          00 52                                    22   seconda cifra della soluzione
2x        00 44                2(20*1+2)=44       + 2 
             08 27                                 243  terza cifra della soluzione
24x          07 29             3(20*12+3)=729     +  3 
                98 59                              2464 quarta cifra della soluzione
246x            98 56          4(20*123+4)=9856       4
                00 03          L'algoritmo termina: la parte intera è 1234 ed il resto 3

Per adattare l'algoritmo ad una base b diversa da 10, basta sostituire la precedente definizione della y con la $y : = d (2 b x + d)$ . Usando la base binaria, l'algoritmo si semplifica molto, perché nel passo 2, per trovare la più grande cifra binaria $d$ tale che $y = d (2 b x + d) < = c$ , si deve provare solo con $d = 1$ , cioè stabilire se 100₂x + 1 <= c. Se la disuguaglianza è verificata, allora la nuova cifra del risultato è 1, altrimenti 0.

Stima asintotica del tempo impiegato dall'algoritmo

Per trovare ogni cifra del risultato (in base binaria) sono necessarie le seguenti operazioni:

moltiplicare $x$ per 100₂ e aggiungere 1 (equivale ad accodare 01 alla scrittura binaria);
un confronto, cioè verificare se la disuguaglianza è soddisfatta;
una differenza tra numeri che hanno al massimo un numero di cifre pari a quello del risultato.

Quindi per trovare la parte intera della radice di un intero $n$ , è necessario un tempo $O(\log_2^2(n))$ .

Implementazione con una function nel linguaggio C++

int intsqrt(int a, int* pr)
// Dato l'intero positivo a, calcola la parte intera della 
// sua radice quadrata principale e il relativo resto; 
// pone il resto in *pr e ritorna la radice
{
int x,r,dp1,L,g[10],j,y,yn;
// separa coppie di cifre e calcola numero delle cifre della radice
L=0; while(a>0) { g[L++]=a%100; a /= 100; }  
// corsa per individuare le successive cifre della radice
x=r=0; 
for(j=L-1;j>=0;j--) { 
  y=0;  // determina cifra
  for(dp1=1;dp1<10;dp1++) { yn=dp1*(20*x+dp1); if(yn<=r) y=yn; else break; } 
  x=x*10+dp1-1; r -= y;
  } 
*pr=r;
return(x);
}

[modifica] Calcolo della radice quadrata con qualsivoglia precisione

Il precedente algoritmo può essere adattato per ottenere la radice di un numero dato da una scrittura decimale (o posizionale in qualsiasi base) con qualsivoglia precisione. Si voglia ad esempio la radice del numero a = 152.3469 con p=4 cifre decimali. Innanzitutto si considera il numero intero A = a * 100^p+1 = 1523469000000; quindi con l'algoritmo precedente si trova la radice di A trovando la parte intera 1234288 e il resto 2134056. Dividendo la parte intera per 10^p+1, cioè per la radice del precedente fattore moltiplicativo, si ottiene 12.34288 come valore per difetto. Si può quindi concludere che il valore cercato è 12.3429 e che costituisce un arrotondamento per eccesso.

Si trova però che questi calcoli su numeri interi sono più onerosi di calcoli approssimati basati su considerazioni geometriche sulla funzione radice quadrata, come gli altri qui presentati. I calcoli sugli interi peraltro sono stati utilizzati per verificare la precisione di calcoli di ispirazione geometrica.

[modifica] Radici quadrate usando il metodo iterativo di Newton

Il metodo di Newton trova una singola radice di una funzione $f (x)$ a partire dalla conoscenza di un'approssimazione sufficientemente precisa della radice. Esso si basa sull'iterazione espressa da:

$x_{n+1} = x_n - {f(x_n) \over f^\prime(x_n)}$ .

Per trovare la radice quadrata di un numero z si utilizzano ampiamente due funzioni $f (x)$ e $g (x)$

(Vedi anche: metodo di Newton, Integer square root.)

[modifica] Primo metodo

Il primo metodo ricerca la radice quadrata di z mediante la

$f(x) = x^2 - z \,$

Nota che sono radici della funzione $f (x)$ sia $\sqrt{z}$ che $- \sqrt{z}$ , ovvero che $f( \sqrt{z} ) = f( -\sqrt{z} ) = 0$ .

La derivata prima della funzione è $f^\prime(x) = 2 x$

Allora l'iterazione per $x n + 1$ è ottenuta come:

$x_0 = 1 \,\,\,$ e

$x_{n+1}\,\!$	$= x_n - {f(x_n) \over f^\prime(x_n)}$
	$= x_n - {(x_n^2 - z) \over 2 x_n}$
	$= x_n - \frac {x_n}{2} + \frac {z}{2 \,\,\, x_n}$
	$= \frac {x_n}{2} + \frac {z}{2 \,\,\, x_n}$ .

[modifica] Secondo metodo

Il secondo metodo ricerca il reciproco della radice quadrata di z mediante la funzione

$g(x) = \frac{1}{x^{2}} - z$ ,

funzione avente come radici $\frac{1}{\sqrt{z}}$ e $\frac{-1}{\sqrt{z}}$ .

La derivata prima di questa funzione è $g^\prime(x) = -2 x^{-3}$ .

Quindi l'iterazione alla Newton per $x n + 1$ è ottenuta come:

$\,x_0 = 0,5\qquad$ e

$x_{n+1} \,\!$	$= x_n - {g(x_n) \over g^\prime(x_n)}$
	$= x_n - {x_n^{-2} - z \over -2 x_n^{-3}}$
	$= x_n - (-1/2) {x_n^3} (x^{-2} - z)$
	$= x_n + (1/2) (x_n - z x_n^3)$
	$= \frac{ 3 x_n - z x_n^3 }{2}$
	$= 1,5 \, x_n - 0,5 \, z x_n^3 = 0,5 \, x_n \,\, ( 3 - z x_n^2 )$ .

[modifica] Esempio

Usiamo entrambi i metodi per trovare $\sqrt{7} = 2.6457513 ...$ .

$z = 7 \,$ poiché stiamo cercando la radice quadrata di 7

$f(x)\,$		$g(x)\,$
$x_0\,$	$1\,$	$x_0\,$	$0,5\,$
$x_1\,$	$\frac{1}{2} + \frac{7}{2 \times 1} = 4$	$x_1\,$	$0.5 \times 0,5 \,\, ( 3 - 7 (0,5)^2 ) = 0,312$	$\frac{1}{x_1}= 3,2\,$
$x_2\,$	$\frac{4}{2} + \frac{7}{2 \times 4} = 2,875$	$x_2\,$	$0,5 \times 0,312 \,\, ( 3 - 7 (0,312)^2 ) = 0,362$	$\frac{1}{x_2}= 2,762\,$
$x_3\,$	$\frac{2,875}{2} + \frac{7}{2 \times 2,875} = 2,654$	$x_3\,$	$0.5 \times 0,362 \,\, ( 3 - 7 (0,362)^2 ) = 0.376$	$\frac{1}{x_3}= 2,652\,$
$x_4\,$	$\frac{2,654}{2} + \frac{7}{2 \times 2,654} = 2,645$	$x_4\,$	$0,5 \times 0,376 \,\, ( 3 - 7 (0,376)^2 ) = 0,378$	$\frac{1}{x_4}= 2,645\,$
$\sqrt{7} \approx 2,645$		$\sqrt{7} \approx 2,645$

[modifica] Confronto

L'iterazione per $f (x)$ implica una divisione che è più onerosa, in termini di tempi di calcolo, di una moltiplicazione tra interi. L'iterazione per $g (x)$ non implica divisioni ed è quindi raccomandata per z intero grande.

Questa iterazione usando g implica soltanto un elevamento al quadrato e due moltiplicazioni, in alternativa ad una divisione nel caso di f. Nella implementazione pratica di estrazione di radici quadrate di interi grandi, il calcolo iterativo che richiede g è più veloce per interi grandi z, poiché la divisione è al massimo $O (M (n))$ , che è un fattore costante del tempo di moltiplicazione. Il termine costante è quasi sempre 3 o più, in quanto una singola divisione con la maggior parte dei dispositivi di calcolo è più veloce di tre moltiplicazioni.

[modifica] Approssimazione semplice

Questo metodo di approssimazione, come dice il nome, è piuttosto semplice, ma può essere altresì altamente impreciso. L'entità dell'imprecisione per questa approssimazione è dipendente dal valore dell'espressione $d / 2 N$ : quanto più grande è il suo valore, tanto maggiore è l'imprecisione del risultato approssimato.

[modifica] Costruzione

Siano N > 0 e d > 0, allora

$N^2 \quad < \quad N^2 + d \quad < \quad N^2 + 2\,d + \frac{d^2}{N^2}$

$N^2 \quad < \quad N^2 + d \quad < \quad N^2 + 2\left( N \right) \left( \frac{d}{N} \right) + \left( \frac{d}{N} \right)^2$

$N^2 \quad < \quad N^2 + d \quad < \quad \left( N + \frac{d}{N} \right)^2$

$N \quad < \quad \sqrt{N^2 + d } \quad < \quad N + \frac{d}{N}$ .

Dunque il valore di $\sqrt{N^2 + d}$ deve stare tra $(N)$ e $( N + \frac{d}{N})$ . Si considera quindi l'approssimazione

$\sqrt{N^2 + d} \, \approx \, \mbox{media} \left( N , N + \frac{d}{N} \right) = \frac{1}{2} \left( N + N + \frac{d}{N} \right)$

ovvero

$\sqrt{N^2 + d} \, \approx \, N + \frac{d}{2\,N}$

Esempio:

Per approssimare la radice di 39, si sostituisce 39 con la somma di un quadrato noto e del valore d pari alla differenza (in questo caso

39 = 36 + 3

$\sqrt{39} = \sqrt{36 + 3} \, \approx \, 6 + \frac{3}{12} \, \approx \, 6,25$

che approssima discretamente il valore effettivo di 6,244997.

[modifica] Metodo delle equazioni quadratiche

La soluzione al problema della ricerca di un valore iniziale ottimale per trovare $\sqrt{r}$ dove 1 < r < 100 può essere risolto in questo modo:

Per radici quadrate di valori maggiori di 100, si usa la seguente identità:

$\sqrt{105,3} = \sqrt{1,053} \times 10$

Per radici quadrate di valori minori di 1, si usa la seguente identità

$\sqrt{0,1053} = \sqrt{10,53} \,\div\, 10$

Usando l'equazione $\sqrt{r} \,=\, N + \frac{1}{X}$ dove $X > 1$ e $N \in \{1,2,3,4,5,6,7,8,9\}$

$\sqrt{r} \,=\, N + \frac{1}{X}$

$r \,=\, { \left( N + \frac{1}{X} \right ) }^2$

$r \,=\, N^2 + \frac{2\,N}{X} + \frac{1}{X^2}$

$0 \,=\, \left( N^2 - r \right) + \frac{2\,N}{X} + \frac{1}{X^2}$

$\left( N^2 - r \right) + \frac{2\,N}{X} + \frac{1}{X^2} \,=\, 0$

$\left( N^2 - r \right) \, X^2 + \left( 2\,N \right) X + 1 \,=\, 0$

Risolvere $X$ utilizzando la formula dell'equazione quadratica, scegliendo la soluzione che soddisfa la condizione $X > 1$ .

La soluzione finale è:

$\sqrt{r} \,=\, N + \frac{1}{X}$

L'ovvio problema è che non possiamo valutare le soluzioni dell'equazione quadratica senza l'uso della funzione radice quadrata. Tuttavia possiamo fare in modo che il serpente morda la propria coda.

$\left( N^2 - r \right) \, X^2 + \left( 2\,N \right) X + 1 \,=\, 0$

Sia $r \, = \, N^2 + d$