Precedente Indice Successivo



Nwt


Scopo: valutazione del polinomio interpolante n punti assegnati, rappresentato nella forma di Newton.
Specifiche: subroutine nwt(p, a, n, x, m, y, ifail)
Integer n, m, ifail
real p(n), a(n), x(m), y(m)
Descrizione: Backgroud del problema

Dati n punti distinti xi e n valori corrispondenti yi esiste un unico polinomio di grado n-1 tale che: Pn-1(xi) = yi, i = 1,..., n La rappresentazione di Newton di tale polinomio è la seguente:

pn-1(x) = an + an-1(x-xn) + ... + a1(x-xn)(x-xn-1)...(x-x2)

Descrizione dell'algoritmo

L'algoritmo implementa, con uno schema iterativo, la formula di Newton nella forma innestata (metodo di Horner):

pn-1(x) = an+ (x - xn)[an-1 + (x - xn-1)[...[a2 + (x - x2)a1]...]]

Raccomandazioni sull'uso

Il numero di punti di interpolazione deve essere positivo e le ascisse di tali punti devono essere distinte.

Bibliografia: [1], [2]
Parametri di I/O: input

p - vettore di reali, ascisse dei punti di interpolazione
a - vettore di reali, coefficienti del polinomio
n - intero, numero dei punti/coefficienti
x - vettore di reali, punti in cui valutare il polinomio.
m - intero, numero di punti di valutazione

output

y - vettore di reali, valori del polinomio
ifail - intero, indicatore d'errore
Indicatori d'errore: Errori gestiti dalla subroutine:
ifail = 0 nessun errore.
ifail = 11 il numero dei punti è o non positivo, o maggiore di 9.
ifail = 12 sono state immesse almeno due ascisse uguali.
Routines ausiliarie: nessuna.
Tempo d'esecuzione: l'algoritmo esegue, per ognuna delle m valutazioni, (n-1) cicli contenenti 2 somme e 1 prodotto, quindi la complessità asintotica è O(m+3n)
Memoria richiesta: in memoria sono allocati due array di reali in singola precisione di dimensione n e 2 di dimensione m quindi la complessità asintotica è O(2n+2m).
Accuratezza fornita: funzione della precisione del sistema aritmetico.
Esempio di programma chiamante: 
      program nwtd

      external nwt
      integer dim,lung
      parameter (dim=9,lung=100)
      
      integer n,ifail
      real p(dim),a(dim),x(lung),y(lung)
      character*12 fin1,fin2,fin3,fout
      print*
      print*,'*** PROGRAMMA DIMOSTRATIVO DELLA SUBROUTINE NWTN ***'
      print*
      write(*,10)'Numero di punti di interpolazione (max',dim,')= '
      read(*,*)n
      print*,'Nome del file di input (punti di interpolazione)= '
      read(*,'(A)')fin1
      open(11,FILE=fin1,STATUS='OLD')
      do 1 i=1,n
           read(11,*)p(i)
    1 continue
      close(11)
      
      print*,'Nome del file di input (coefficienti del polinomio)= '
      read(*,'(A)')fin2
      open(12,FILE=fin2,STATUS='OLD')
      do 2 i=1,n
           read(12,*)a(i)
    2 continue
      close(12)
      
      write(*,10)'Numero di ascisse (max ',lung,')= '
      read(*,*)m
      print*,'Nome del file di input (ascisse)= '
      read(*,'(A)')fin3
      open(13,FILE=fin3,STATUS='OLD')
      do 3 i=1,m
           read(13,*)x(i)
    3 continue
      close(13)
      
      call nwt(p,a,n,x,m,y,ifail)
      if (ifail .eq. 11) stop 'Errore! numero di punti non valido'
      print*,'Nome del file di output= '
      read(*,'(A)')fout
      open(14,FILE=fout)
      write(14,20)(y(i),i=1,m)
      close(14)
      
      print*,'Valori del polinomio: '
      write(*,20)(y(i),i=1,m)
   10 format (1X,A,I3,A)
   20 format (1X,E14.7)
      End


Precedente Indice Successivo