Sqrt

Molto spesso capita di dover calcolare la radice quadrata di un certo numero. Consideriamo ad esempio la radice quadrata di 2. Questa in matematica è scritta come \(\sqrt{2}\), ed è definita come quel numero che moltiplicato per se stesso diventa proprio \(2\). In formula

In generale la radice quadrata di un numero \(x\) è scritta come \(\sqrt{x}\) e soddisfa la formula

A questo punto ci possiamo chiedere: ma come possiamo calcolare, in pratica, questa radice quadrata? Nella maggior parte delle situazioni non siamo noi ad implementare l'algoritmo per il calcolo di \(\sqrt{x}\). Ci basta utilizzare la libreria di riferimento del linguaggio. Ad esempio in python possiamo procedere utilizzando il modulo math e la funzione sqrt.

>>> import math
>>> math.sqrt(2)
1.4142135623730951
>>> math.sqrt(9)
3.0
>>> math.sqrt(12345678901)
111111.11061005555

In questo progetto andiamo a vedere un possibile algoritmo per implementare tale funzione. L'obiettivo è di svelare la magia e di mostrare come possiamo farlo anche noi.

Come si calcola \(\sqrt{x}\)?

Il nostro obiettivo è, fissato un \(x\), trovare il numero \(r\) tale che

dove sia \(r\) che \(x\) si muovono nel contesto dei numeri reali \(\mathbb{R}\). L'idea sarà quella di implementare un algoritmo iterativo che si avvicina alla soluzione per approssimazione. Si parte da una stima qualsiasi del risultato che vogliamo ottenere, anche pessima, e si applica una regola per migliorare la stima con cui lavoriamo e portarla sempre più vicina al risultato preciso.

A livello computazionale abbiamo una successione di valori converge al valore desiderato

Nello specifico osserviamo che cercare la radice di \(x\) significa cercare lo zero della funzione

Per cercare gli zeri esiste un metodo generale, dovuto a due matematici: Newton e Raphson, che si chiama appunto metodo di Newton-Raphson. In questo specifico contesto, data la forma della funzione \(f(r)\), il metodo si riduce alla seguente formula.

Dove \(r_n\) è la nostra stima iniziale, mentre \(r_{n+1}\) è la stima migliorata dal metodo dopo una iterazione.

Prima di lasciarti al codice però dobbiamo affrontare un'ultima questione. Dato che il metodo si basa su una successione di valori sempre più vicini al valore desiderato, la domanda delle domande è: e quando mi fermo? Abbiamo bisogno di un criterio di terminazione.

Un possibile criterio è analizzare la vicinanza tra il valore calcolato al quadrato e il target \(x\) e assicurarsi che questa distanza sia più piccola di un parametro di precisione \(\epsilon\)

Il tuo obiettivo in questo progetto sarà implementare l'algoritmo per il calcolo di \(\sqrt{x}\) utilizzando queste formule e il linguaggio di programmazione che preferisci.