Algoritmo per il calcolo della radice n-esima

La radice $n$-esima, ${\sqrt[{n}]{A}},$ di un numero reale $A$ non negativo, è la soluzione reale non negativa dell'equazione

$x^{n}=A.$

In questa voce è descritto un metodo numerico, che converge velocemente, per il calcolo di questa radice. I passi dell'algoritmo sono:

1. si prova a stimare un valore iniziale di partenza $x_{0};$
2. si pone $x_{k+1}={\frac {1}{n}}\left({(n-1)x_{k}+{\frac {A}{x_{k}^{n-1}}}}\right),$ che equivale a $x_{k+1}=x_{k}+\Delta x_{k},$ con $\Delta x_{k}={\frac {1}{n}}\left({\frac {A}{x_{k}^{n-1}}}-x_{k}\right);$
3. si ripete il secondo passo fino a che si raggiunge la precisione desiderata, cioè $|\Delta x_{k}|<\varepsilon .$

Un caso speciale è il calcolo numerico della radice quadrata, cioè il caso $n=2$:

$x_{k+1}={\frac {1}{2}}\left(x_{k}+{\frac {A}{x_{k}}}\right).$

La derivazione dell'algoritmo si basa sul metodo numerico di Newton-Raphson.

Derivazione dal metodo di Newton-Raphson

Il metodo delle tangenti o di Newton-Raphson è un metodo per trovare numericamente lo zero di una funzione$f(x).$ Lo schema generale è:

1. partire da una stima iniziale $x_{0};$
2. $x_{k+1}=x_{k}-{\frac {f(x_{k})}{f'(x_{k})}};$
3. ripetere il secondo passo fino a che si raggiunga la precisione desiderata.

Il calcolo numerico della radice $n$-esima si può concepire come la ricerca di uno zero della funzione $f(x)=x^{n}-A,$ la cui derivata è:

$f^{\prime }(x)=nx^{n-1}.$

In questo modo si costruisce l'iterazione:

$x_{k+1}=x_{k}-{\frac {f(x_{k})}{f'(x_{k})}}$

$=x_{k}-{\frac {x_{k}^{n}-A}{nx_{k}^{n-1}}}$

$=x_{k}-{\frac {x_{k}}{n}}+{\frac {A}{nx_{k}^{n-1}}}$

$={\frac {1}{n}}\left({(n-1)x_{k}+{\frac {A}{x_{k}^{n-1}}}}\right).$

Esempio numerico

Si vuole calcolare la radice quarta di

6901827461

Si imposta un primo valore, ad esempio 1000. Utilizzando un foglio di calcolo si può verificare una veloce convergenza:

Foglio di calcolo esemplificativo. Il numero di cui si vuole calcolare la radice è nella casella A1=

6901827461

e l'esponente $n=4$ della radice nella casella A2.

Si pone la stima iniziale, 1000, nella casella B2.

I valori vengono generati inserendo nella casella B3: (($A$2–1)*B2+$A$1/B2^($A$2–1))/$A$2

6901827461	stima	valore calcolato	differenza
4	1000	1E+12	-9,93098E+11
	751,7254569	3,19328E+11	-3,12426E+11
	567,8559656	1,03981E+11	-97078880593
	435,3149815	35909921459	-29008093998
	347,4029409	14565787245	-7663959784
	301,7054079	8285760564	-1383933103
	289,1072856	6986121665	-84294203,78
	288,235197	6902208103	-380642,2278
	288,2312231	6901827469	-7,871785164
	288,231223	6901827461	0

Bibliografia

• Kendall E. Atkinson, An introduction to numerical analysis, 2nd, New York, Wiley, 1989, ISBN 0-471-62489-6.

Voci correlate

• Metodi per il calcolo della radice quadrata
• Metodo delle tangenti