Algoritmi

Interpolazione Polinomiale

L'interpolazione polinomiale con la formula di lagrange

L'interpolazione polinomiale costituisce un'alternativa dell'interpolazione lineare: mentre per questo metodo si usa una sequenza di funzioni lineari, si tratta ora di servirsi di un polinomio di un opportuno grado più alto.

In generale, se abbiamo n punti dati, esiste esattamente un polinomio di grado n−1 che passa attraverso tutti i punti dati. L'errore di interpolazione è proporzionale alla distanza fra i punti dati alla potenza n . Inoltre questo interpolante, essendo un polinomio è illimitatamente differenziabile. Quindi l'interpolazione polinomiale, in linea di principio risolve tutti i problemi di interpolazione lineare.

Tuttavia questo metodo presenta alcuni svantaggi. Il calcolo che porta ai coefficienti del polinomio d'interpolazione è molto "costoso" (in termini di tempo di esecuzione richiesto al calcolatore e in termini di complessità delle elaborazioni). Inoltre, l'interpolazione polinomiale per il complesso dei valori dalla variabile indipendente non si rivela molto esatta; questo accade, in particolare, nei punti astremi (vedi fenomeno di Runge ). Questi svantaggi possono essere evitati usando i metodi dell'interpolazione spline.

C====================================================================
C Programma per in calcolo del Polinomio interpolatore 
C su piu' punti utilizzando la FORMULA DI LAGRANGE
C====================================================================
C
      PROGRAM pollag
      IMPLICIT NONE
C====================
C Parte dichiarativa
C====================
      INTEGER n, m, maxn, maxpt
      INTEGER i, is, k
      PARAMETER (maxn=50, maxpt=300)
      REAL*8 x(0:maxn), y(0:maxn), xs(0:maxpt), ys(0:maxpt)
      REAL*8 f, a, b, h
      CHARACTER*20 nomefilein, nomefileout
C====================
C Parte esecutiva
C====================
C
C Ingresso dati
C
      print *, 'Formula di LAGRANGE'
      print *
      print *, '1 = Lettura nodi da file'
      print *, '2 = Nodi equidistanti'
      print *
      print *, 'Inserire la scelta'
      read *, is
      if (is.eq.1) then
         print *, ' Inserisci il numero di nodi (n+1)'
         read *, n
         n = n-1
         print *, 'Dammi il nome del file di ingresso contenente i nodi'
	 read*, nomefilein
         open (unit=9,file=nomefilein)	 
         do i = 0, n
            read (9,*) x(i)
         end do	 
	 close (9)
      else
         print *, 'Dammi gli estremi a e b dell''intervallo '
	 print *, 'da discretizzare'
         read*, a, b
         print *, ' Inserisci il numero di intervalli n'
         read *, n 
	 h = (b-a)/dble(n)
	 x(0) = a
	 do i = 1, n
            x(i) = x(0) + h * i
         end do	 
      end if
      print *, '1 = Lettura valori da interpolare da file'
      print *, '2 = Valori equidistanti'
      print *
      print *, 'Inserire la scelta'
      read *, is
      if (is.eq.1) then
         print *, ' Inserisci il numero di punti (m+1) per valutare'
         print *, ' l''approssimazione del polinomio interpolatore'
         read *, m
         m = m-1
         print *, 'Dammi il nome del file contenente i valori'
	 read*, nomefilein
         open (unit=9,file=nomefilein)	 
         do i = 0, m
            read (9,*) xs(i)
         end do	 
	 close (9)
      else
         print *, 'Stesso intervallo: 1=SI 2=NO'
         read *, is
	 if (is.eq.2) then
           print *, 'Dammi gli estremi a e b dell''intervallo '
	   print *, 'da discretizzare'
           read*, a, b
	 else
	   a = x(0)
	   b = x(n)
	 end if
         print *, ' Inserisci il numero di intervalli m'
         read *, m
	 h = (b-a)/dble(m)
	 xs(0) = a
	 do i = 1, m
            xs(i) = xs(0) + h * i
         end do	 
      end if
      print *, 'Dammi il nome del file in uscita'
      read*, nomefileout
      open (unit=10,file=nomefileout)
C
C Calcolo della funzione sui nodi
C   
      do i = 0, n
         y(i) = f(x(i))
      end do
C 
C Ciclo esterno per i punti su cui valutare il polinomio
C interpolatore
C
      do k = 0, m
C
C Esecuzione della valutazione con Formula di Lagrange
C
        CALL lagrange (x, y, xs(k), ys(k), n)  
      end do
C
C Uscita dati e risultati
C
      write(*,*)
      write(*,*) ' Scrittura dei nodi e valori'
      do i = 0, n
        write (*,*) i, x(i), y(i)
      end do
      write(*,*)
      write(*,*) ' Scrittura dei punti interpolati'
      do k = 0, m
        write (*,*) k, xs(k), ys(k)
        write (10,'(2g20.15)') xs(k), ys(k)
      end do
      stop
      end


C====================================================================
C Subroutine per la valutazione del polinomio di interpolazione
C in un punto con la FORMULA DI LAGRANGE 
C====================================================================
      SUBROUTINE lagrange (x, y, xs, ys, n)  
      IMPLICIT NONE
C
C Variabili INGRESSO:
C     x       vettore contenente i nodi (0:n)
C     y       vettore contenente i valori della funzione nei nodi (0:n)
C     xs      valore di cui effettuare la valutazione
C     n       il numero dei nodi e'  (n+1)
C
C Variabili USCITA:
C     ys      approssimazione calcolata

C
C====================
C Parte dichiarativa
C====================
      INTEGER n
      INTEGER k, i, r, j
      REAL*8 x(0:*), y(0:*), L(0:n)
      REAL*8 xs, ys  
C====================
C Parte esecutiva
C====================
      
      do i = 0, n
         L(i) = 1.0d0
         do j = 0, i-1
            L(i) = L(i)*(xs-x(j))/(x(i)-x(j))
	 end do
	 do j = i+1, n
            L(i) = L(i)*(xs-x(j))/(x(i)-x(j))
	 end do
      end do
      ys = 0.0d0
      do i = 0, n
         ys = ys + y(i)*L(i)
      end do
      return
      end

C====================================================================
C Funzione assegnata
C====================================================================
      real*8 function f(x)
      implicit none
      real*8 x
      f=dsqrt(x)
      return
      end

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