Analisi  Numerica     26/10/2011  

  1  

Interpolazione  Polinomiale:  Sia  data  la  𝑓: 𝑎, 𝑏 → ℝ  assegnata  e  in  particolare  siano  noti  𝑓 𝑥! , 𝑓! 𝑥! , 𝑓′′(𝑥!)  e  si  vuole  determinare  il  polinomio  quadratico  di  Taylor  di  approssimazione  della  𝑓 𝑥 𝑖𝑛  𝑥!.  Prendiamo  il  polinomio  in  una  base  con  centro  𝑥!  (ricordo  che  nella  lezione  precedente  il  centro  della  base  era  indicato  con  c):  

𝑝 𝑥 = 𝑎! + 𝑎! 𝑥 − 𝑥! + 𝑎! 𝑥 − 𝑥! !  Valuto  il  polinomio  per  x=𝑥!:  

𝑝 𝑥! = 𝑎! + 𝑎! 𝑥! − 𝑥! + 𝑎! 𝑥! − 𝑥! ! ⇒ 𝑓 𝑥! = 𝑎!  𝑝′ 𝑥! = 𝑎! + 2𝑎! 𝑥! − 𝑥! ! ⇒ 𝑓′ 𝑥! = 𝑎!  

𝑝′′ 𝑥! = 2𝑎! ⇒𝑓′′ 𝑥!2

= 𝑎!  A  partire  da  queste  3  informazioni  posso  costruire  un  polinomio  che  approssimi  il  meglio  possibile  la  mia  funzione  f(x).  Il  problema  di  interpolazione  vuol  dire  ricostruire  una  funzione  a  partire  da  informazioni  puntuali  di  questa  funzione.    Siano  dati  n+1  punti  (𝑥! , 𝑦!)  con  i=0,1,…,n  con  𝑥!  distinti.  Si  vuole  determinare  un  polinomio  p(x)  tale  che  𝑝(𝑥!) = 𝑦!  𝑐𝑜𝑛  𝑖 = 0,1,… , 𝑛.    (GRAFICO  FATTO  BENE  SUGLI  APPUNTI)    Vorrei  ricondurre  un  determinato  fenomeno  del  quale  mi  è  sconosciuto  l’andamento  (funzione),  conoscendo  solo  delle  informazioni  puntuali  di  questo  fenomeno,  ovviamente  più  dati  conosco  di  questo  fenomeno  meglio  riuscirò  a  ricondurmi  ad  una  rappresentazione  matematica  dello  stesso.  Il  risultato  che  riesco  ad  ottenere  in  questo  modo  prende  il  nome  di  polinomio  di  interpolazione.    Esempio  su  un  grafico  in  2  dimensioni  (x,y):  Data  una    𝑓: 𝑎, 𝑏 → ℝ        𝑥! → 𝑓(𝑥!)  la  miglior  approssimazione  che  mi  aspetto  dovrebbe  risultare  circa  così:    (GRAFICO  FATTO  BENE  SUGLI  APPUNTI)    Esempio  in  3  dimensioni:  Rilevati  alcuni  campioni,  posso  ricostruire  una  funzione  polinomiale  che  rappresenta  un  determinato  punto  atmosferico.  Per  ottenere  informazioni  riguardo  a  come  la  pioggia  cada  in  una  determinata  area,  potrei  determinare  un’area  in  cui  posizionare  dei  barili  per  la  raccolta  della  pioggia  stessa,  questi  rappresenterebbero  un  campione  (o  per  meglio  dire  un  punto),  potendo  rappresentare  l’informazione  in  3  dimensioni  ottengo  una  valutazione  di  un  polinomio  con  punti   𝑥! , 𝑦! , 𝑧! .    (GRAFICO  DA  FARE)    Dato  un  insieme  di  punti  

     

𝑥! = 0𝑥! = 1𝑥! = 0

 

 Posso  costruire  un  polinomio  di  secondo  grado  che  potrebbe  rappresentare  il  problema,  il  polinomio  sarà  sicuramente  nella  forma  𝑝 𝑥 = 𝑎! + 𝑎!𝑥 + 𝑎!𝑥!,  alla  quale  posso  applicare  le  mie  condizioni  del  problema.  

x   0   1   2  y   0   1   0  

Analisi  Numerica     26/10/2011  

  2  

𝑝 𝑥! = 𝑦! ⇒ 𝑎! + 𝑎!𝑥! + 𝑎!𝑥!! = 𝑦!𝑝 𝑥! = 𝑦! ⇒ 𝑎! + 𝑎!𝑥! + 𝑎!𝑥!! = 𝑦!𝑝 𝑥! = 𝑦! ⇒ 𝑎! + 𝑎!𝑥! + 𝑎!𝑥!! = 𝑦!

 

 Risolvo  il  sistema  per  trovare  i  coefficienti,  sostituendo  i  valori  forniti  dal  problema:    

𝑎! + 𝑎!0 + 𝑎!0! = 0𝑎! + 𝑎!1 + 𝑎!1! = 1𝑎! + 𝑎!2 + 𝑎!2! = 0

 

 𝑎! = 0𝑎! = 2𝑎! = −1

 

Pertanto  il  mio  polinomio  interpolante  è  𝑝 𝑥 = 2𝑥 − 𝑥!    Vado  a  verificare  che  il  polinomio  ottenuto  approssimi  per  bene  la  mia  funzione  di  partenza,  mi  basta  sostituire  i  miei  valori  di  x  al  polinomio  appena  ottenuto  e  controllare  che  la  corrispondenza  x,y  venga  rispettata.  

𝑝 0 = 0𝑝 1 = 1𝑝 2 = 0

 

Il  polinomio  che  meglio  approssima  i  punti  (x,y)  assegnati  è  la  seguente  parabola:  

 Perché  abbiamo  scelto  di  rappresentare  il  mio  problema  proprio  con  un  polinomio  di  secondo  grado?  Teorema:  Dati  n+1  punti   𝑥! , 𝑦! !!!,!,…,!  con  𝑥!  distinti  ∃! 𝑝(𝑥) ∈ ℙ!  che  verifica  le  condizioni:  𝑝 𝑥! = 𝑦!  𝑖 =0,1,… , 𝑛  Dimostrazione:  Dato  un  polinomio  nella  forma  𝑝 𝑥 = 𝑎! + 𝑎!𝑥! + 𝑎!𝑥! +⋯+ 𝑎!𝑥! ∈ ℙ!  impongo  le  mie  “condizioni  di  interpolazione”:  1°  condizione      𝑎! + 𝑎!𝑥!! + 𝑎!𝑥!! +⋯+ 𝑎!𝑥!! = 𝑦!  2°  condizione      𝑎! + 𝑎!𝑥!! + 𝑎!𝑥!! +⋯+ 𝑎!𝑥!! = 𝑦!  i-­‐esima  condizione      𝑎! + 𝑎!𝑥!! + 𝑎!𝑥!! +⋯+ 𝑎!𝑥!! = 𝑦!    Siccome  𝑎!, 𝑎!,… , 𝑎!  sono  incognite  e  le  x  sono  invece  informazioni  puntuali  posso  ricondurmi  ad  un  sistema  lineare  dove  𝑎!, 𝑎!,… , 𝑎!  sono  incognite  che  compaiono  unicamente  al  primo  grado,  nella  forma:  

𝑉 ∙ 𝑎 = 𝑦  • dove  V  è  la  matrice  dei  coefficienti  di  a;  • a  è  il  vettore  delle  incognite;  • y  è  il  vettore  delle  osservazioni  

𝑉 ∙ 𝑎 = 𝑦 ⇒

1 𝑥! 𝑥!! ⋯ 𝑥!!

1 𝑥! 𝑥!! … 𝑥!!

⋮1

⋮𝑥!

⋮ ⋯ ⋮𝑥!! … 𝑥!!

∙

𝑎!𝑎!⋮𝑎!

=

𝑦!𝑦!⋮𝑦!

 

Analisi  Numerica     26/10/2011  

  3  

V  prende  il  nome  di  matrice  di  Vandermonde,  caratterizzata  dall’avere  nella  prima  colonna  tutti  1  (ovvero  i  nostri  punti  elevati  alla  0),  tutti  i  punti  elevati  ad  1,2,…,n  nelle  successive  linee.  Il  determinante  della  matrice  V  è:  

(𝑥! − 𝑥!) ≠ 0!

!,!!!!!!

 

Se  i  punti  presi  sono  distinti  il  determinante  è  ≠ 0    Se  vogliamo  risolvere  un  problema  di  interpolazione  si  presentano  problemi  relativi  alla  soluzione  del  sistema  lineare,  in  particolar  modo  riguardanti  la  matrice  V.  E’  possibile  dimostrare  che  la  matrice  V  è  mal  condizionata,  pertanto  non  adatta  ad  essere  risolta  con  il  calcolatore.  Esempio:  

     

𝑝 𝑥 = 𝑎! + 𝑎!𝑥! + 𝑎!𝑥! ⇒𝑎! + 𝑎!0 + 𝑎!0! = 0𝑎! + 𝑎!1 + 𝑎!1! = 1𝑎! + 𝑎!2 + 𝑎!2! = 2

⟹𝑎! = 0

𝑎! + 𝑎! = 12𝑎! + 4𝑎! = 2

⇒𝑎! = 0

𝑎! = 1 − 𝑎!−2𝑎! + 2 + 4𝑎! = 2

⇒  

𝑎! = 0𝑎! = 1𝑎! = 0

 posso  quindi  scrivere  il  mio  polinomio  𝑝 𝑥 = 𝑥.  

 𝑝 𝑥  esiste  ed  è  unico  in  ℙ!,  anche  se  io  sono  partito  cercando  il  polinomio  di  grado  2,  ho  scoperto  che  per  approssimare  i  miei  punti  “basta”  un  polinomio  di  grado  1,  ovvero  una  retta.    Interpolazione  polinomiale  nella  forma  di  Newton:  Dati  dei  punti  (𝑥! , 𝑦!)!!!,!,…,!  il  polinomio  nella  forma  di  Newton  è  espresso  come:  𝑝 𝑥 = 𝑎! + 𝑎! 𝑥 − 𝑥! + 𝑎! 𝑥 − 𝑥! 𝑥 − 𝑥! +⋯+ 𝑎! 𝑥 − 𝑥! 𝑥 − 𝑥! … (𝑥 − 𝑥!!!)    La  base  di  Newton  prende  il  nome  di  base  con  n  centri  ed  è  espressa  come:  

{1, 𝑥 − 𝑥! , 𝑥 − 𝑥! 𝑥 − 𝑥! ,… , 𝑥 − 𝑥! 𝑥 − 𝑥! … 𝑥 − 𝑥!!! }  Il  sistema  di  interpolazione  risultante  sarà  (ovvero  la  valutazione  di  un  polinomio  nella  forma  di  Newton  sarà  scomposta  nel  sistema):  𝑝 𝑥! = 𝑦!𝑝 𝑥! = 𝑦!

⋮𝑝 𝑥! = 𝑦!

𝑎! = 𝑦!𝑎! + 𝑎! 𝑥! − 𝑥! = 𝑦!

⋮𝑎! + 𝑎! 𝑥! − 𝑥! + 𝑎! 𝑥! − 𝑥! 𝑥! − 𝑥! +⋯+ 𝑎! 𝑥! − 𝑥! 𝑥! − 𝑥! … 𝑥! − 𝑥!!! = 𝑦!

   

 La  forma  compatta  della  forma  di  Newton  è  espressa  come:  

𝑁 ∙ 𝑎 = 𝑦  • dove  N  è  la  matrice  dei  coefficienti  (di  Newton)  di  a;  • a  è  il  vettore  delle  incognite;  • y  è  il  vettore  delle  osservazioni    

𝑁 ∙ 𝑎 = 𝑦  ⟹

1 0 0 ⋯ 01 𝑥! − 𝑥! 0 … 0⋮1

⋮𝑥! − 𝑥!

⋮ ⋯ ⋮𝑥! − 𝑥! … 𝑥! − 𝑥!!!

∙

𝑎!𝑎!⋮𝑎!

=

𝑦!𝑦!⋮𝑦!

 

 Il  determinante  della  matrice  N  (che  è  una  matrice  triangolare):  

𝑥! − 𝑥!

!

!,!!!!!!

 

x   0   1   2  y   0   1   2  

Analisi  Numerica     26/10/2011  

  4  

Differenza  divisa:  Sia  f  una  funzione  continua  su  di  un  intervallo  [a,b]  e  {𝑥!}!!!,!,…,!  con  n+1  punti  distinti  nell’intervallo  [a,b].  Si  definisce  differenza  divisa  di  ordine  n  (e  si  usa  la  notazione  𝑓[𝑥!, 𝑥!,… , 𝑥!])  il  coefficiente  di  𝑥!  del  polinomio  𝑝 ∈ ℙ!che  soddisfa  la  condizione  di  interpolazione  (in  una  qualsiasi  forma)  𝑝 𝑥! = 𝑓 𝑥!  per  i=0,1,…,n.  Risultato:    Il  polinomio  di  interpolazione  di  Newton  dei  punti  (𝑥! , 𝑓(𝑥!))  con  i=0,1,…,n  ha  come  coefficienti:  

𝑎! = 𝑓 𝑥!  𝑎! = 𝑓 𝑥!, 𝑥!  

𝑎! = 𝑓 𝑥!, 𝑥!, 𝑥!  …  

𝑎! = 𝑓 𝑥!, 𝑥!, 𝑥!,… , 𝑥!    Come  calcolo  le  differenze  divise?  Formula  ricorrente  per  le  differenze  divise:  

𝑓 𝑥! , 𝑥!!!,… , 𝑥!!!!! =𝑓 𝑥! , 𝑥!!!,… , 𝑥!!!!! − 𝑓[𝑥! , 𝑥!!!,… , 𝑥!!!]

𝑥!!!!! − 𝑥  

Esempio:  (𝑥!, 𝑓 𝑥! )  

(DISEGNO  FATTO  BENE  SUGLI  APPUNTI)  𝑓 𝑥! = 𝑓 𝑥! ⇒ 𝑦 = 𝑓(𝑥!) ∙ 𝑥!  

 𝑥! 𝑓 𝑥! = 𝑓[𝑥!] 𝑓[𝑥!, 𝑥!]𝑥! 𝑓 𝑥! = 𝑓[𝑥! 𝑓[𝑥!, 𝑥!]⋮𝑥!

⋮𝑓(𝑥!)

⋮𝑓[𝑥!!!, 𝑥!]

 

 Come  è  possibile  vedere  i  punti  ottenuti  dalla  differenza  divisa,  sono  esattamente  espressi  nella  forma  di  Newton.