Esercizio 6

Esiste il metodo di Newton per calcolare uno zero di una funzione in un intervallo dato. Per esempio se abbiamo $f(x)$ in [a,b] e sappiamo che sia $f(a)f(b)<0$ implica che esiste almeno un punto $x_0$ in cui la nostra funzione è uguale a zero. Il procedimento di Newton si basa sul fatto che se ci spostiamo da un punto iniziale $x$ in un punto $x+h$ prossimo al nostro zero della funzione $x_0$ ($x+h \sim x_0$) si ha

$$\begin{eqnarray*} f(x+h)=f(x)+f'(x)\cdot h \sim 0 \end{eqnarray*}$$

ossia da $x$ posso scegliere $h$ e aggiornare il mio nuovo $x$ come

$$\begin{eqnarray*} h = -f(x)/f'(x) \\ x = x + h \end{eqnarray*}$$

in questo modo iterativamante ci muoviamo verso il valore $x_0$. L'algoritmo di Newton è molto efficiente per calcolare la radice di un numero. Se infatti vogliamo calcolare la radice di un numero $y_0$ possiamo considerare la funzione

$$\begin{eqnarray*} f(x)= x^2 -y_0 \end{eqnarray*}$$

che si annulla esattamente quando il valore di $x^2$ eguaglia $y_0$, ossia quando $x$ diviena la radice di $y_0$.

Esercizio: scrivere una funzione che implementi il metodo di Newton e calcolare la radice di un numero positivo. Un esempio di soluzione può essere

def newton(f,df,a,b,y,tol):
    ''' newton(f,df,a,b,y,tol) 
        find the square root of y in the interval a,b starting from (a+b)/2 
    '''
    maxcount=100000 # maximun number of step
    count=0
    x=(a+b)/2.0 # starting point
    while (f(x,y)>tol) and (count<maxcount):
        h=-f(x,y)/df(x)
        x = x + h
        count = count + 1
    return x

def f(x,y0):
    ''' f(x) = x*x '''
    return x*x - y0 

def df(x):
    ''' df(x) = 2*x '''
    return 2.0*x

if __name__ == '__main__':
   import math
   tolerance = 0.0001
   y0=input('sqrt of = ')
   print "math ",y0,math.sqrt(y0),"computed",newton(f,df,0,y0,y0,tolerance)