Sul calcolo approssimato della radice di indice k di un numero a

Mettiamo subito in evidenza che < 1 0 < 1 + x < 2, pertanto operativa-

√

mente è necessario portarsi in queste condizioni: volendo calcolare 3 = 1.732

√ √ ≈

non si scriverà 3 = 1 + 2 1 + 2/2 = 2, bensı̀

√ √ √

p · − ≈ −

3 = 4 3/4 = 2 0.75 = 2 1 0.25 2(1 0.25/2) = 1.75

√

Detti ora ξ = a ed una (piccola) perturbazione della soluzione ξ, utiliz-

k

zando ancora una volta la (1) si ha: →0

n

kn k k k k ≈

x = (ξ(1 + )) = ξ (1 + ) = a(1 + ) a(1 + k )

n n n n

e pertanto kn

≈ −

(x /a 1)/k

n

Come vedremo dagli esempi, solitamente il valore di primo tentativo x è suffi-

0

cientemente accurato, ossia è sufficientemente piccolo, da consentire di rag-

0

giungere una precisione di 6 cifre significative in sole 2 o 3 iterazioni di Newton.

1 1

Il metodo che ci apprestiamo ora a descrivere è ispirato da un report di K.

Turkowski per il calcolo della radice cubica. Brevemente, si parte dall’osserva-

zione che √ √

√ k k

p

kp

k a = 2 b = 2 b

e pertanto la radice k−esima di qualsiasi numero è in relazione semplice con

kp

quella di un numero 2 più piccolo: in altre parole, calcolare la radice k−esima

1 ≤ b < 2.

di qualsiasi numero può ricondursi a calcolare quella di un numero k−1

2

I passi per il calcolo della radice k−esima sono dunque i seguenti:

• si porta fuori radice un’eventuale potenza k−esima di 10; questo passaggio

non è richiesto in una implementazione su calcolatore

• ≥

se 1 + x 2, si porta fuori radice la minima potenza k−esima di 2 che

consente di applicare la (1). La scelta della base 2 è giustificata dal fatto

che è relativamente semplice calcolarne le potenze anche a mente; inoltre,

come si vedrà in seguito, per come i numeri vengono rappresentati interna-

mente al calcolatore, è immediato eliminarne le potenze con un’operazione

di resto modulo k

• si utilizza la (1) per approssimare la radice

• volendo, si migliora l’approssimazione con l’algoritmo di Newton

• si esegue il prodotto dei termini trovati

Vediamo alcuni esempi pratici. Approssimiamo a 6 cifre significative per mo-

strare l’accuratezza del valore di primo tentativo di x ; nella pratica non si va

0

oltre le 2 o 3 cifre. √

3 100 = 4.64159. Si ha:

1. si desideri approssimare

√ √

r 100 2

3 3

3 6

x = 100 = 2 = 2 1.5625

0 64

0.5625

≈ ·

4 1+ = 4 1.1875 = 4.75

3

3 −

ove = (1.1875 /1.5625 1)/3 = 2.39%. Volendo migliorare la soluzione

0 −

con il metodo di Newton, si ha 1/k = 0.333 e (k 1)/k = 0.667 e

1.5625

· ·

x = 4 0.667 1.1875 + 0.333 = 4 1.16104 = 4.64415

1 2

1.1875

1.5625

· ·

x = 4 0.667 1.16175 + 0.333 = 4 1.1604 = 4.64159

2 2

1.16175

√

3 343000 = 70. Si ha:

2. si desideri approssimare

√ √

r 343 3

3 3

3 9 ·

x = 343000 = 10 2 = 10 2 0.669922

0 512

0.330078

≈ − ·

80 1 = 80 0.889974 = 71.1979

3

1 K. Turkowski, Computing the Cube Root, Apple Computer Technical Report #KT-32,

1998 2

3 −

ove = (0.889974 /0.669922 1)/3 = 1.74%. Volendo migliorare la

0 −

soluzione con il metodo di Newton, si ha ancora 1/k = 0.333 e (k 1)/k =

0.667 e

0.669922 ·

· = 80 0.875265 = 70.0212

x = 80 0.667 0.889974 + 0.333

1 2

0.889974

0.669922

· ·

x = 80 0.667 0.875265 + 0.333 = 80 0.875000 = 70

2 2

0.875265

√

3. si desideri approssimare π = 1.77245. Si ha:

√

√ r π

2

x = π = 2 = 2 0.785398

0 4

0.214602

≈ − ·

2 1 = 2 0.892699 = 1.7854

2

2 −

ove = (0.892699 /0.785398 1)/2 = 0.73%. Volendo migliorare la

0 −

soluzione con il metodo di Newton, si ha 1/k = (k 1)/k = 0.5 e

0.785398 ·

· = 2 0.886250 = 1.77250

x = 2 0.5 0.892688 + 0.5

1 0.892688

0.785398

· ·

x = 2 0.5 0.88625 + 0.5 = 2 0.886227 = 1.77245

2 0.88625

√

5

4. si desideri approssimare 55 = 2.22881. Si ha:

√

√ r 55 5

5 5 5 = 2

x = 55 = 2 1.71875

0 32

0.71875

≈ ·

2 1+ = 2 1.14375 = 2.2875

5

5 −

ove = (1.14375 /1.71875 1)/5 = 2.77%. Volendo migliorare la so-

0 −

luzione con il metodo di Newton, si ha 1/k = 0.2 e (k 1)/k = 0.8

e

1.71875

· ·

x = 2 0.8 1.14375 + 0.2 = 2 1.11587 = 2.23174

1 4

1.14375

1.71875 ·

· = 2 1.11441 = 2.22881

x = 2 0.8 1.11587 + 0.2

2 4

1.11587

Vediamo infine una semplice implementazione al calcolatore in linguaggio

C: il programma seguente approssima e calcola la radice k−esima con il meto-

do descritto. La funzione è più lenta rispetto alla inclusa in

kthroot() pow()

quest’ultima tuttavia non è universale nel senso che viene implemen-

#math.h;

tata in modo diverso dai vari compilatori, e talvolta ottimizzata per sfruttare le

particolarità dell’architettura di destinazione.

3