Algoritmo per il calcolo della radice n-esima

La radice  n-esima di di un numero reale positivo A,  ${\displaystyle {\sqrt[{n}]{A}}}$ , e' la soluzione reale positiva  della equazione

${\displaystyle x^{n}=A}$

(per un numero n>1 intero ci sono  n soluzioni nel campo complesso, tuttavia una sola e' reale e positiva se ${\displaystyle A>0}$.

Questa voce - adattata dall' originale in inglese di wikipedia - e' su  un metodo numerico per il calcolo di questa radice  che converge velocemente. I passi dell' algoritmo sono:

1. Si prova a stimare un valore iniziale di partenza  ${\displaystyle x_{0}}$
2. Si pone ${\displaystyle x_{k+1}={\frac {1}{n}}\left[{(n-1)x_{k}+{\frac {A}{x_{k}^{n-1}}}}\right]}$. Questo equivale a  ${\displaystyle \Delta x_{k}={\frac {1}{n}}\left[{\frac {A}{x_{k}^{n-1}}}-x_{k}\right];x_{k+1}=x_{k}+\Delta x_{k}}$.
3. Si ripete lo step 2 fino a che si raggiunge la precisione desiderata, cioe'  ${\displaystyle |\Delta x_{k}|<\epsilon }$ .

Un caso speciale e' il calcolo numerico della radice quadrata ponendo n=2:

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

${\displaystyle 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 e' un  metodo per trovare numericamente lo zero di una funzione f(x). Lo schema generale e': 

1. Partire da una stima iniziale ${\displaystyle x_{0}}$ 
2. ${\displaystyle x_{k+1}=x_{k}-{\frac {f(x_{k})}{f'(x_{k})}}}$ 
3. Ripetere lo step 2 fino a che si raggiunga la precisione desiderata.

Il calcolo numerico della radice n-esima si puo' concepire come la ricerca di uno zero della funzione:

${\displaystyle f(x)=x^{n}-A}$ 

La cui derivata e':

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

In questo modo si costruisce l' iterazione: 

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

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

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

${\displaystyle ={\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 puo' verificare una veloce convergenza:

Foglio di calcolo esemplificativo. Il numero di cui si vuole calcolare la radice e' 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

Voci correlate

• Metodi per il calcolo della radice quadrata
• Metodo_delle_tangenti

 

Analisi numerica 

Riferimenti bibliografici

• Kendall E. Atkinson, An introduction to numerical analysis, Wiley, 1989..