Precedente | Indice | Successivo |
Parte prima - Interpolazione
Scopo: | calcolo dei coefficienti del polinomio interpolante n punti assegnati, rappresentato nella forma di Newton. |
Specifiche: |
subroutine conwt(x, y, n, ifail) integer n, ifail real x(n), y(n) |
Descrizione: |
Backgroud del problema
Dati n punti xi e n valori corrispondenti yi, esiste un unico polinomio interpolante tali punti. La sua rappresentazione però non è unica, ma dipende dalla base scelta nello spazio vettoriale dei polinomi di grado £ n-1. Una rappresentazione particolarmente conveniente da un punto di vista computazionale è la seguente: pn-1(x) = an + an-1(x-xn) + an-2(x-xn)(x-xn-1) + ... + a1 (x-xn)...(x-x2), detta formula di Newton. Indicati, infatti, i coefficienti ai con y[xi,..., xi+k], essi si possono ottenere mediante la seguente formula ricorsiva: ![]() Descrizione dell'algoritmo L'algoritmo, dopo il controllo dell'assenza di ascisse uguali, implementa, con uno schema iterativo, la formula per il calcolo delle differenze divise, memorizzando le stesse nel vettore contenente le ordinate dei punti di interpolazione. Raccomandazioni sull'uso Il numero di punti d'interpolazione deve essere positivo e minore di nove, inoltre le ascisse di tali punti devono essere distinte. Nel caso in cui il numero di punti è maggiore di nove, si suggerisce la risoluzione del problema utilizzando le subroutine cospl, pmq1, pmq2. I coefficienti sono memorizzati nel vettore delle ordinate dei punti d'interpolazione, quindi, se s'intende riutilizzare tale vettore è necessario eseguirne prima una copia. |
Bibliografia: | [1], [2] |
Parametri di I/O: |
input
x - vettore di reali, ascisse dei punti d'interpolazione output
y - vettore di reali, coefficienti del polinomio |
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 calcola n(n-1)/2 differenze divise, ognuna delle quali richiede 2 somme e 1 prodotto, la complessità asintotica è O(3/2 n2) |
Memoria richiesta: | in memoria sono allocati due array di reali in singola precisione, di dimensione n, quindi, la complessità asintotica è O(2n). |
Accuratezza fornita: | funzione della precisione del sistema aritmetico. |
Esempio di programma chiamante: |
Program conwtd c Programma dimostrativo della subroutine conwt external conwt integer dim parameter (dim=10) integer n,ifail real x(dim),y(dim),a(dim) character*12 fin,fout print* print*,'*** PROGRAMMA DIMOSTRATIVO DELLA subROUTINE CONWT ***' print* write(*,10)'Numero di punti di interpolazione (max ',dim,')= ' read(*,*)n print*,'Nome del file di input= ' read(*,'(A)')fin open(11,FILE=fin,STATUS='OLD') do 1 i=1,n read(11,*)x(i) 1 continue read(11,*) do 2 i=1,n read(11,*)y(i) 2 continue close(11) call conwt(x,y,n,a,ifail) if (ifail .eq. 11) stop 'Errore! numero di punti non valido' if (ifail .eq. 12) stop 'Errore! ascisse coincidenti' print*,'Nome del file di output= ' read(*,'(A)')fout open(12,FILE=fout) write(12,'(E14.7)')(a(i),i=1,n) close(12) print*,'Coefficienti del polinomio interpolante =' write(*,'(E14.7)')(a(i),i=1,n) 10 format (1X,A,I3,A) End |
Precedente | Indice | Successivo |