Algoritmo per calcolare la radice quadrata
Per calcolare un valore approssimato della radice quadrata di un numero posso utilizzare un algoritmo iterativo. E' un buon esempio per capire lo scopo del calcolo numerico.
Con questo algoritmo si può stimare la radice quadrata di qualsiasi numero.
La precisione dipende dal numero delle iterazioni.
Un esempio pratico
Ad esempio, voglio calcolare la radice quadrata di 2.
$$ n=2 $$
Inizializzazione
Assegno alla radice il valore iniziale 1.
$$ r = 1 $$
E' una scelta arbitraria. Può anche essere un numero diverso.
Nota. La scelta del valore iniziale influisce sulla rapidità dell'algoritmo a convergere su una buona stima. Ad esempio, usando r=n/10 come valore iniziale spesso si riducono le iterazioni.
Quindi applico la formula
$$ r_i = \frac{ r + \frac{n}{r} }{2} $$
in modo iterato fino a ottenere una stima accettabile della radice quadrata.
Iterazione 1
La prima iterazione utilizza il valore iniziale r=1 ed è la stima meno affidabile
$$ r_1 = \frac{ r + \frac{n}{r} }{2} $$
$$ r_1 = \frac{ 1 + \frac{2}{1} }{2} $$
$$ r_1 = 1.5 $$
Iterazione 2
Nella seconda iterazione utilizzo il valore trovato nell'iterazione precedente r=r1=1.5
$$ r_2 = \frac{ r_1 + \frac{n}{r_1} }{2} $$
$$ r_2 = \frac{ 1.5 + \frac{2}{1.5} }{2} $$
$$ r_2 = 1.41666666667 $$
Il nuovo valore della radice è già una buona approssimazione della radice quadrata di due.
Le prime due cifre decimali (1.41) sono esatte
Nota. In effetti la radice quadrata di 2 è$$ \sqrt{2} = 1.414213562373095 $$
Ripetendo il calcolo più volte, usando di volta in volta l'ultimo valore della radice, la stima della √2 migliora in modo quadratico.
Iterazione 3
Nella terza iterazione utilizzo come radice r=1.41666666667
$$ r_3 = \frac{ r_2 + \frac{n}{r_2} }{2} = 1.4142156862745097 $$
La terza iterazione produce una stima migliore in quanto le prime quattro cifre decimali (1.4142) della √2 sono esatte
Iterazione 4
Nella quarta iterazione utilizzo come radice r=1.4142156862745097
$$ r_4 = \frac{ r_3 + \frac{n}{r_3} }{2} = 1.4142135623746899 $$
Ora la stima ha le prime otto cifre decimali esatte (1.41421356).
E via dicendo
Nota. La stima della radice √2 migliora in modo quadratico. Nella seconda iterazione le prime 2 cifre decimali sono esatte. Nella terza iterazione le prime 4 cifre decimali sono esatte. Nella quarta iterazione le prime 8 cifre decimali sono esatte. E via dicendo.
Esempio 2
Per calcolare una buona stima della radice quadrata di 441 sono necessarie 9 iterazioni
| iterazione | radice |
|---|---|
| 1 | 221.0 |
| 2 | 111.49773755656109 |
| 3 | 57.72648738142165 |
| 4 | 32.68298069537334 |
| 5 | 23.088121019325943 |
| 6 | 21.094426250358378 |
| 7 | 21.000211342955026 |
| 8 | 21.000000001063462 |
| 9 | 21.0 |
E' un esempio pratico di applicazione del calcolo numerico.
Chiaramente, a ogni iterazione i calcoli sono svolti da un computer.
E così via.
