Algoritmo per il calcolo della radice quadrata

Per calcolare la radice quadrata di un numero

$x$

usando un algoritmo in stile matematico, si può utilizzare il metodo di Newton-Raphson, che è un metodo iterativo per trovare successivamente approssimazioni della radice quadrata.

L’algoritmo di Newton-Raphson per calcolare

$\sqrt{x}$

può essere scritto come:

$$x_{n+1} = \frac{1}{2} \left( x_n + \frac{x}{x_n} \right)$$

Dove:

• 
  $x_n$ 

  è l’approssimazione corrente della radice quadrata,

• 
  $x_{n+1}$ 

  è la prossima approssimazione.

Passaggi dell’algoritmo:

1. Inizializzare un valore iniziale
   $x_0$ 

   , ad esempio $x_0 = \frac{x}{2}$ 

   .

2. Ripetere il calcolo:
   $$x_{n+1} = \frac{1}{2} \left( x_n + \frac{x}{x_n} \right)$$ 

   fino a quando la differenza tra $x_{n+1}$ 

   e $x_n$ 

   non è abbastanza piccola (convergenza).

Pseudocodice:

funzione radice_quadrata(x)
    x_n = x / 2  // Inizializza il valore iniziale
    tolleranza = 0.0001  // Definisci la tolleranza
    mentre |x_n * x_n - x| > tolleranza
        x_n = 0.5 * (x_n + x / x_n)  // Calcola la nuova approssimazione
    fine mentre
    ritorna x_n
fine funzione

• La funzione viene eseguita fino a quando la differenza tra
  $x_n^2$ 

  e $x$ 

  è inferiore alla tolleranza specificata, garantendo così che l’approssimazione della radice quadrata sia abbastanza precisa.

Metodo algoritmo babilonese

L’algoritmo babilonese (noto anche come Metodo di Herone) è un metodo molto antico per calcolare la radice quadrata di un numero. È un caso particolare del metodo di Newton-Raphson e si basa su un’iterazione simile, ma con una formula semplificata.

Formula dell’algoritmo babilonese:

L’algoritmo babilonese per calcolare la radice quadrata di un numero

$x$

è dato dalla seguente formula iterativa:

$$x_{n+1} = \frac{1}{2} \left( x_n + \frac{x}{x_n} \right)$$

Dove:

• 
  $x_n$ 

  è l’approssimazione corrente della radice quadrata,

• 
  $x_{n+1}$ 

  è la prossima approssimazione.

Scegliere il valore iniziale $x_0$ nell’algoritmo babilonese è una parte importante del processo. L’algoritmo è un metodo iterativo, quindi la qualità della stima iniziale può influenzare la rapidità con cui l’algoritmo converge al risultato finale. Vediamo come scegliere $x_0$ in modo efficace.

Come scegliere il valore iniziale $x_0$?

1. Scelta basata sul numero stesso: Una scelta comune per il valore iniziale $x_0$ è utilizzare una stima approssimativa. Un’opzione semplice è scegliere $x_0$ come metà del numero di cui vuoi calcolare la radice quadrata. Ad esempio, se vuoi calcolare la radice quadrata di 16, puoi scegliere:

   $$x_0 = \frac{x}{2} = \frac{16}{2} = 8$$Questo è un buon punto di partenza e consente una rapida convergenza per molti numeri.

2. Scelta basata su una stima più informata: Se hai un’idea del range in cui si trova la radice quadrata del numero, puoi scegliere un valore iniziale più preciso. Ad esempio, se stai cercando la radice quadrata di 100, sapere che la risposta è 10 ti permette di scegliere un valore iniziale vicino a 10. Se invece stai cercando la radice quadrata di 2, potresti scegliere $x_0 = 1$ come valore iniziale.
3. Scelta di $x_0$ casuale: Se non hai un’idea precisa di dove si trovi la radice quadrata, una scelta casuale può funzionare bene. In genere, un valore iniziale che è una stima relativamente buona del numero sarà sufficiente per ottenere una rapida convergenza.

Esempi:

1. Radice quadrata di 16:

   $$x_0 = \frac{16}{2} = 8$$Iterando con l’algoritmo babilonese:

   $$x_1 = \frac{1}{2} \left( 8 + \frac{16}{8} \right) = \frac{1}{2} \left( 8 + 2 \right) = 5$$ $$x_2 = \frac{1}{2} \left( 5 + \frac{16}{5} \right) = \frac{1}{2} \left( 5 + 3.2 \right) = 4.1$$ $$x_3 = \frac{1}{2} \left( 4.1 + \frac{16}{4.1} \right) \approx \frac{1}{2} \left( 4.1 + 3.902 \right) = 4.001$$E così via, con l’approssimazione che migliora ad ogni passo.

2. Radice quadrata di 100:

   $$x_0 = \frac{100}{2} = 50$$Iterando con l’algoritmo:

   $$x_1 = \frac{1}{2} \left( 50 + \frac{100}{50} \right) = 26$$ $$x_2 = \frac{1}{2} \left( 26 + \frac{100}{26} \right) \approx 15.192$$ $$x_3 = \frac{1}{2} \left( 15.192 + \frac{100}{15.192} \right) \approx 10.001$$Dopo pochi passaggi, otteniamo una buona approssimazione di 10.

Riepilogo della scelta di $x_0$:

• Valore iniziale approssimato: Una buona scelta di $x_0$ è metà del numero $x$, ovvero $x_0 = \frac{x}{2}$. Questo vale per molti numeri e garantisce una rapida convergenza.
• Valore iniziale più preciso: Se conosci un intervallo in cui si trova la radice quadrata, scegli $x_0$ vicino al risultato. Ad esempio, se cerchi $\sqrt{100}$, sai che la risposta è 10, quindi scegli $x_0 \approx 10$.
• Valore iniziale casuale: In mancanza di una stima iniziale, scegli un valore ragionevole (come 1 o metà di $x$).

In generale, la scelta di $x_0$ non è critica per l’algoritmo, poiché converge rapidamente in ogni caso. La tolleranza definisce quando fermarsi, e di solito una stima iniziale non molto precisa può comunque portare a una buona soluzione.

Passaggi dell’algoritmo:

1. Inizializzazione: Inizia con una stima iniziale
   $x_0$ 

   (ad esempio, $x_0 = \frac{x}{2}$ 

   ).

2. Iterazione: Ripeti il calcolo:
   $$x_{n+1} = \frac{1}{2} \left( x_n + \frac{x}{x_n} \right)$$ 

   fino a che la differenza tra le iterazioni successive non è abbastanza piccola.

Pseudocodice:

funzione radice_babilonese(x)
    x_n = x / 2  // Inizializza con un valore di partenza
    tolleranza = 0.0001  // Definisci la tolleranza
    mentre |x_n^2 - x| > tolleranza
        x_n = 0.5 * (x_n + x / x_n)  // Calcola la nuova approssimazione
    fine mentre
    ritorna x_n
fine funzione

Dettagli:

• Il valore di partenza
  $x_0$ 

  può essere scelto arbitrariamente, ma di solito si usa $x_0 = \frac{x}{2}$ 

  o un altro valore che è una stima approssimativa della radice.

• L’algoritmo continua a iterare finché la differenza tra l’approssimazione e il valore reale è inferiore a una tolleranza prefissata, garantendo che l’approssimazione sia sufficientemente precisa.

Esempio in LaTeX:

Se volessi scrivere il metodo babilonese in LaTeX, puoi usare la seguente sintassi:

\documentclass{article}
\usepackage{amsmath}

\begin{document}

L'algoritmo babilonese per calcolare la radice quadrata di un numero \(x\) è dato dalla formula iterativa:

\[
x_{n+1} = \frac{1}{2} \left( x_n + \frac{x}{x_n} \right)
\]

Iniziamo con una stima iniziale \( x_0 = \frac{x}{2} \), e iteriamo fino a che la differenza tra le iterazioni successive non è sufficientemente piccola:

\[
x_{n+1} = \frac{1}{2} \left( x_n + \frac{x}{x_n} \right)
\]

\end{document}