Calcolo Numerico            

Relazione sull’interpolazione polinomiale attraverso il  Metodo di Newton ‐ Differenze divise 

          Sergio Porcu  

INTERPOLAZIONE POLINOMIALE 

 

Metodo di Newton ‐ Differenze divise 

 

 

 

L’interpolazione polinomiale è un metodo di calcolo mediante il quale, data una funzione y = ƒ(x) e 

dati  i  valori  numerici  che  tale  funzione  assume  per  x  a  determinati  valori  x1,  x2,  ...,  xn,  si  può 

determinare con buona approssimazione il valore numerico di ƒ(x) per x = x0 con x1<x0<xn e x0 ≠ xi 

(i = 2, 3,  ..., xn).  Il metodo di Newton riconduce  l’interpolazione a un calcolo di differenze, che si 

conducono alla formula di Taylor. 

Il polinomio interpolatore Pn(x) ha la seguente struttura (più avanti vedremo come costruirla): 

 

Pn(x) = a0 + a1⋅(x ‐ x0) + a2⋅(x ‐ x0)⋅(x ‐ x1) + ... + an⋅(x ‐ x0)⋅(x ‐ x1)⋅...⋅(x ‐ xn‐1) 

 

dove  i valori ai  rappresentano  le differenze divise,  rapporti  incrementali  che  si definiscono  sugli 

n+1 punti (x0, x1, ..., xn) 

 

   ƒ(x0)                                                           i = 0  

   ai = ƒ[x0, ..., xi] =  ‐ 

   (ƒ[x1, ..., xi] ‐ ƒ[x0, ..., xi‐1])/( xi ‐ x0)      i > 0 

 

Se si considera il caso generale di n+1 punti (x0, ..., xn), la differenza divisa di ordine n risulta 

 

ƒ[x0, ..., xn] = (ƒ[x1, ...,xn] ‐ ƒ[x0, ..., xn‐1] )/(xn ‐ x0) 

 

La  differenza  divisa  risulta  indipendente  rispetto  alle  permutazioni  in  quanto  dipende 

esclusivamente dai punti e non dall’ordine in cui questi si trovano. 

I  valori  delle  differenze  divise  associate  agli  n+1  punti  xi  ed  i  coefficienti  del  polinomio 

interpolatore  si  ottengono mediante  la  costruzione di un’opportuna  tabella  contenente  i  valori 

degli stessi punti xi e delle funzioni ƒ[x0, ..., xn]: 

 

ordine 0    ordine 1       ordine 2     ...     ordine n 

xi   yi=ƒ(xi) 

x0   ƒ(x0) 

  x1  ƒ(x1)       ƒ[x0, x1] 

  x2  ƒ(x2)      ƒ[x1, x2]    ƒ[x0, x1, x2] 

   .      .            .               .       . 

   .      .            .               .       . 

  xn  ƒ(xn)      ƒ[xn‐1, xn]            ƒ[xn‐2, ..., xn]    ...  ƒ[x0, ..., xn] 

 

Dalla tabella, che richiede n2 somme algebriche e n2/2 divisioni, si estrapolano gli elementi della 

diagonale;  questi  rappresentano  i  coefficienti  del  polinomio  interpolatore,  che  avrà,  come 

abbiamo visto prima, la seguente forma: 

 

Pn(x) = a0 + a1⋅(x ‐ x0) + a2⋅(x ‐ x0)⋅(x ‐ x1) + ... + an⋅(x ‐ x0)⋅(x ‐ x1)⋅...⋅(x ‐ xn‐1) 

 

con a0 = ƒ(x0), a1 = ƒ[x0, x1], a2 = ƒ[x0, x1, x2], ..., an = ƒ[x0, x1, ..., xn]. La costruzione di tale polinomio 

richiede invece n moltiplicazioni e 2n somme. 

 

Nelle  pagine  a  seguire  verranno  presentati  l’algoritmo  risolutivo  del  metodo  delle  differenze 

divise, tradotto in linguaggio C, ed alcuni esempi di interpolazione attraverso il metodo di Newton, 

ciascuno dei quali sarà corredato dalle schermate di visualizzazione dell’algoritmo sopra riportato 

e da opportuni grafici di confronto tra funzione reale e polinomio interpolante. 

 

 

 

 

 

 

/******************************************************************************* Il programma effettua l'interpolazione polinomiale di una serie di numeri inseriti da tastiera   attraverso il Metodo di Newton delle Differenze Divise. L'algoritmo visualizza in uscita i risultati del processo di calcolo, quali tabella degli ordini ed elementi della diagonale principale utilizzati come coefficienti del polinomio interpolatore, ed il polinomio stesso. 

    Autore:    ‐ Sergio Porcu *******************************************************************************/  #include<stdio.h> #include<iostream.h> #include<math.h> #include<conio.h> #define N 10  main() {   /* Dichiarazione delle variabili */   float x[N];    /* Vettore contenente i valori delle x dei punti */   float y[N];    /* Vettore contenente i valori delle y dei punti */   float f[N];    /* Vettore contenente i valori delle funzioni */   float app[N];    /* Vettore di appoggio contenente i valore delle funzioni */   float diagon[N];  /* Vettore contenente i valori della diagonale principale */   int cont,i,j;    /* Contatori */   int num;    /* Numero di punti da interpolare */   int salto,passo;  /* Variabili di comodo */    /* Inizializzazione delle variabili */   num=0;   clrscr();    /* Inserimento dei valori dei punti da interpolare */   puts("\t\tInterpolazione dei punti con il metodo delle ");         puts("\t\t    differenze divise (metodo di Newton)\n");   printf("Quanti punti vuoi interpolare? : ");   cin>>num;   passo=(num‐1);   for(cont=0;cont<num;cont++)  /* Ciclo di inserimento */   {     printf("Inserisci il valore x del %d° punto : ",cont+1);     cin>>x[cont];     printf("Inserisci il valore y del %d° punto : ",cont+1);     cin>>y[cont];   }    /* Inizializzazione del vettore contenete i valori delle funzioni */   for(cont=0;cont<num;cont++) 

  {     f[cont]=y[cont];   }    /* Inizio elaborazione dati */   clrscr();   printf("Scansione dei risultati elaborati dal calcolatore : \n");   printf("Colonna delle differenze divise di ordine 0\n");   for(i=0;i<num;i++)   {     cout<<f[i];     printf("\n");   }   for(i=0;i<num;i++)  /* Scansione dei punti */   {       /* Memorizzazione degli elementi della diagonale */      diagon[i]=f[i];     salto=i+1;     for(j=i+1;j<num;j++)  /* Ciclo di calcolo */     {       if(j==i+1) 

printf("Colonna delle differenze divise di ordine         %d\n",i+1); if(x[j]!=x[j‐salto])  /* Controllo di eventuali errori di inserimento */ 

             {           app[j]=(f[j]‐f[j‐1])/(x[j]‐x[j‐salto]);              }              else              {                    clrscr();                    printf("Errore di inserimento dati:\n");                    printf("i punti inseriti non appartengono ad una funzione ");                  printf("continua!\a");                    return ‐1;                   }       }     for(j=i+1;j<num;j++)     {       f[j]=app[j];       cout<<f[j];       printf("\n");     }   }   /* Fine elaborazione dati */    /* Visualizzazione finale dei dati */   printf("\n");   printf("I valori della diagonale sono : \n"); 

  for(i=0;i<num;i++)   {     cout<<diagon[i];     printf("\n");   }   printf("\n");   printf("P%d(x)=",(num‐1));   cout<<diagon[0];   for(i=1;i<num;i++)   {        if(diagon[i]>=0)              printf("+");     cout<<diagon[i];     for(j=1;j<=num‐passo;j++)     {       printf("(x");       if(x[j‐1]>=0)         printf("‐");       else         printf("+");       cout<<abs(x[j‐1]);              printf(")");     }     passo‐‐;   }     return 0; }                    

ESEMPIO 1 Funzione reale y = 3cos(x) + ex  Interpolazione dei punti con il metodo delle differenze divise (metodo di Newton)  Quanti punti vuoi interpolare? : 5 Inserisci il valore x del 1° punto : ‐3 Inserisci il valore y del 1° punto : ‐2.92 Inserisci il valore x del 2° punto : 0 Inserisci il valore y del 2° punto : 4 Inserisci il valore x del 3° punto : 2 Inserisci il valore y del 3° punto : 6.1406 Inserisci il valore x del 4° punto : 4 Inserisci il valore y del 4° punto : 52.6372 Inserisci il valore x del 5° punto : 9 Inserisci il valore y del 5° punto : 8100.35  Scansione dei risultati elaborati dal calcolatore : Colonna delle differenze divise di ordine 0 ‐2.92 4 6.1406 52.6372 8100.35 Colonna delle differenze divise di ordine 1 2.30667 1.0703 23.2483 1609.54 Colonna delle differenze divise di ordine 2 ‐0.247273 5.5445 226.613 Colonna delle differenze divise di ordine 3 0.827396 24.5632 Colonna delle differenze divise di ordine 4 1.97799  I valori della diagonale sono : ‐2.92 2.30667 ‐0.247273 0.827396 1.97799  P4(x)=‐2.92+2.30667(x+3)‐0.247273(x+3)(x‐0)+0.827396(x+3)(x‐0)(x‐2)+1.97799(x+3)(x‐0)(x‐2)(x‐4) 

Esempio 1 ‐ y = 3cos(x) + e^x 

                           

ESEMPIO 2 Funzione reale y = ln(x) + 1/x   Interpolazione dei punti con il metodo delle differenze divise (metodo di Newton)  Quanti punti vuoi interpolare? : 5 Inserisci il valore x del 1° punto : 1 Inserisci il valore y del 1° punto : 1 Inserisci il valore x del 2° punto : 3 Inserisci il valore y del 2° punto : 1.432 Inserisci il valore x del 3° punto : 5 Inserisci il valore y del 3° punto : 1.809 Inserisci il valore x del 4° punto : 7 Inserisci il valore y del 4° punto : 2.089 Inserisci il valore x del 5° punto : 9 Inserisci il valore y del 5° punto : 2.308  Scansione dei risultati elaborati dal calcolatore : Colonna delle differenze divise di ordine 0 1 1.432 1.809 2.089 2.308 Colonna delle differenze divise di ordine 1 0.216 0.1885 0.14 0.1095 Colonna delle differenze divise di ordine 2 ‐0.00687501 ‐0.012125 ‐0.00762498 Colonna delle differenze divise di ordine 3 ‐0.000874999 0.000750003 Colonna delle differenze divise di ordine 4 0.000203125  I valori della diagonale sono : 1 0.216 ‐0.00687501 ‐0.000874999 0.000203125  P4(x)=1+0.216(x‐1)‐0.00687501(x‐1)(x‐3)‐0.000874999(x‐1)(x‐3)(x‐5)+ 0.000203125(x‐1)(x‐3)(x‐5)(x‐7) 

Esempio 2 ‐ y = ln(x) + 1/x 

                           

ESEMPIO 3 Funzione reale y = 2sen(x) + ln1/(x+1)  Interpolazione dei punti con il metodo delle differenze divise (metodo di Newton)  Quanti punti vuoi interpolare? : 5 Inserisci il valore x del 1° punto : 0 Inserisci il valore y del 1° punto : 0 Inserisci il valore x del 2° punto : 2 Inserisci il valore y del 2° punto : 0.72 Inserisci il valore x del 3° punto : 5 Inserisci il valore y del 3° punto : ‐3.710 Inserisci il valore x del 4° punto : 6 Inserisci il valore y del 4° punto : ‐2.505 Inserisci il valore x del 5° punto : 9 Inserisci il valore y del 5° punto : ‐1.478  Scansione dei risultati elaborati dal calcolatore : Colonna delle differenze divise di ordine 0 0 0.72 ‐3.71 ‐2.505 ‐1.478 Colonna delle differenze divise di ordine 1 0.36 ‐1.47667 1.205 0.342333 Colonna delle differenze divise di ordine 2 ‐0.367333 0.670417 ‐0.215667 Colonna delle differenze divise di ordine 3 0.172958 ‐0.126583 Colonna delle differenze divise di ordine 4 ‐0.0332824  I valori della diagonale sono : 0 0.36 ‐0.367333 0.172958 ‐0.0332824  P4(x)=0+0.36(x‐0)‐0.367333(x‐0)(x‐2)+0.172958(x‐0)(x‐2)(x‐5)‐0.0332824(x‐0)(x‐2)(x‐5)(x‐6) 

Esempio 3 ‐ y = 2sen(x) + ln1/(x+1) 

                           

ESEMPIO 4 Funzione reale y = sen(x) + cos(x) + x2  Interpolazione dei punti con il metodo delle differenze divise (metodo di Newton)  Quanti punti vuoi interpolare? : 5 Inserisci il valore x del 1° punto : ‐3 Inserisci il valore y del 1° punto : 7.869 Inserisci il valore x del 2° punto : ‐1 Inserisci il valore y del 2° punto : 0.7 Inserisci il valore x del 3° punto : 2 Inserisci il valore y del 3° punto : 4.493 Inserisci il valore x del 4° punto : 5 Inserisci il valore y del 4° punto : 24.325 Inserisci il valore x del 5° punto : 7 Inserisci il valore y del 5° punto : 50.411  Scansione dei risultati elaborati dal calcolatore : Colonna delle differenze divise di ordine 0 7.869 0.7 4.493 24.325 50.411 Colonna delle differenze divise di ordine 1 ‐3.5845 1.26433 6.61067 13.043 Colonna delle differenze divise di ordine 2 0.969767 0.891056 1.28647 Colonna delle differenze divise di ordine 3 ‐0.00983889 0.0494264 Colonna delle differenze divise di ordine 4 0.00592652  I valori della diagonale sono : 7.869 ‐3.5845 0.969767 ‐0.00983889 0.00592652  P4(x)=7.869‐3.5845(x+3)+0.969767(x+3)(x+1)‐0.00983889(x+3)(x+1)(x‐2)+ 0.00592652(x+3)(x+1)(x‐2)(x‐5) 

Esempio 4 ‐ y = sen(x) + cos(x) + x^2