Algoritmi

L'algoritmo della Secante

Algoritmo della Secante per il calcolo degli zeri di una funzione.

Il metodo che qui si propone, detto metodo della secante, tende a risolvere e eliminare la difficoltà del calcolo della derivata prima necessaria nell'applicazione del metodo di Newton senza rinunciare del tutto al miglioramento della velocità convergenza che tale metodo introduce.

L'ipotesi assicura che esiste almeno un punto z in cui é f(z)=0; inoltre la funzione è strettamente monotona nell'intervallo [a,b] per cui comunque si scelgano, in esso, due punti distinti x₀ e x₁ sarà sempre vero che f(x₁)-f(x₀) è diverso da zero. 

Si consideri, allora la secante passante per i due punti curva, di ascissa x₀ e x₁, che hanno coordinate P₀(x₀ ,f( x₀))  e  P₁(x₁ ,f( x₁)).
La retta passante per il punto P₀ e P₁ ha equazione  y-f( x₁) = m(x-f( x₁)) dove per semplicità si è posto m=[f( x₁)-f( x₀)]/( x₁- x₀)
L'intersezione della retta  secante P₀P₁ con l'asse x può considerarsi una buona approssimazione della soluzione z; pertanto posto y=0 nella precedente equazione si ha, in analogia a quanto ottenuto nel metodo di Newton,   x₂ = x₁ - f(x₁)/m

dove sostituendo 1/m= (x₁ - x₀)  / ( f(x₁) - f(x₀) ) si ottiene, infine, 
x₂ = x₁ - f(x₁) (x₁ - x₀)  / ( f(x₁) - f(x₀) )

Poichè la retta  secante P₀P₁ può considerarsi una buona approssimazione della retta t, tangente in P₁ alla curva di equazione y=f(x) quando P₁ --> P₀ si può notare che il metodo qui ottenuto non è altro che il metodo di Newton nel quale alla derivata prima f'(x₁) si è sostituita una espressione approssimata e cioè il rapporto incrementale m=[f( x₁)-f( x₀)]/( x₁- x₀)
Per questo, il metodo della secante ha una convergenza di ordine quasi quadratico (si può dimostrare che è di ordine 1/2+/2 = 1,618)
Pertanto, il procedimento consente di ridurre  l'ampiezza dell'errore, ad ogni iterazione, in maniera che si possa assumere e₂ =  k e₁^1,618. La convergenza non è esattamente come nel metodo di Newton, ma il metodo presenta il grande vantaggio di non richiedere il calcolo della derivata prima.

É stato precedentemente accennato alla velocità di convergenza del metodo della secante che è di ordine 1,618; il metodo di Steffensen consente di accelerare la convergenza del metodo della secante portandola alla stessa velocità del metodo di Newton senza un aggravio eccessivo in termini di costo del calcolo.

Facendo riferimento alla formula della secante
x₂ = x₁ - f(x₁) (x₁ - x₀)  / ( f(x₁) - f(x₀) )
si assuma che nell'intorno di x₀ sia lecito porre f(x₁) = (x₁ - x₀) da cui x₀ = x₁ -f(x₁) . In tal caso la formula della secante precedentemente scritta, assume la forma seguente che prende il nome di formula di Steffensen:
x₂ = x₁ - f(x₁)² / ( f(x₁) - f(x₁ -f(x₁))
Più frequentemente la stessa formula viene usata sotto la forma seguente:
x₂ = x₁ - f(x₁)² / (  f(x₁ + f(x₁)) - f(x₁) )
che è giustificata dal fatto che nella prima forma il denominatore è semplicemente l'incremento della funzione nell'intorno sinistro di x₁ mentre nella seconda forma, l'incremento della funzione viene calcolato nell'intorno destro dello stesso punto. 

Le formule appena scritte partono con un solo punto x₁, come la formula di Newton, ma richiedono, ad ogni iterazione, il calcolo sia dell'incremento h= f(x₁) che della   f(x₁ + f(x₁)) = f(x₁+h).
La dimostrazione che la convergenza delle formule precedenti è quadratica la si ottiene facilmente quando si riscriva la formula di Steffensen con le posizioni precedenti:
x₂ = x₁ - f(x₁) h / (  f(x₁ + h) - f(x₁) )  = x₁ - f(x₁)/ m 
dove è stato posto m =  (  f(x₁ + h) - f(x₁) )/h ; sviluppando  f(x₁ + h)   in serie di Taylor intorno a x₁ si ottiene
f(x₁+ h)= f(x₁)+f'(x₁)h+ f"(x₁)h² /2+O(h²)
da cui si deduce:
(f(x₁+ h)- f(x₁))/h=f'(x₁)+ f"(x₁)h /2+O(h²)
si ha, cioè
m=f'(x₁)[1+ f"(x₁)h /2f'(x₁)+O(h²)] = f'(x₁)/[1- f"(x₁)h /2f'(x₁)+O(h²)].
Sostituendo, infine, nella   
x₂ = x₁ - f(x₁)/ m=x₁ - f(x₁)/f'(x₁)*[1- f"(x₁)h /2f'(x₁)+O(h²)] 
da cui, ricordando che h= f(x₁) , si può scrivere 
x₂ = x₁- f(x₁)/f'(x₁)+ f"(x₁)h² /2f'(x₁)²+O(h³) . 
Qui  si riconosce l'espressione dell'errore della formula di Newton. Pertanto la formula di Steffensen ha la stessa convergenza della formula di Newton.      

Di seguito è riportato il codice in fortran 90 che impllementa l'algoritmo della secante per il calcolo degli zeri di una funzione.

!Programma in fortran 90 per il calcolo
!degli zeri di una funzione con il metodo
!della secante
      program main
      real :: a = 1.0, b = -1.0
      integer :: m = 8
      interface
      function f(x)
      real, intent(in) :: x
      end function
      end interface

      call secant(f,a,b,m)
      end program main

      subroutine secant(f,a,b,m)
      real, intent(in) :: a,b
      integer, intent(in) :: m
      real :: fa, fb, temp
      integer :: n
      interface
      function f(x)
      real, intent(in) :: x
      end function f
      end interface

      fa = f(a)
      fb = f(b)
      if (abs(fa) >  abs(fb)) then
         temp = a
         a = b
         b = temp
         temp = fa
         fa = fb
         fb = temp
      end if
      print *,"    n        x(n)         f(x(n))"
      print *," 1 ", b, fb
      print *," 0 ", a, fa	
      do n = 2,m
         if (abs(fa) >  abs(fb)) then
            temp = a
            a = b
            b = temp
            temp = fa
            fa = fb
            fb = temp
         end if
         temp = (b - a)/(fb - fa)
  	 b = a
	 fb = fa
         a = a - fa*temp
         fa = f(a)
         print *,n,a,fa
      end do   
      end subroutine secant

      real function f(x)
      real, intent(in) :: x
      f = x**5 + x**3 + 3.0
      end function

• » Invia tramite EMAIL
• » Versione per la STAMPA
• » Le vostre opinioni