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.