Calcolo per l’Astronomia a.a. 2014/2015 

Lauro Moscardini lauro.moscardini@unibo.it 

Tel. 051‐2095726 Sito web:  

apps.difa.unibo.it/files/people/lauro.moscardini/calcolo_14‐15 

Programma del corso  

•  Integrazione di funzioni • Metodi di interpolazione di daA 

•  Generazione di numeri casuali e metodi Monte Carlo 

•  Equazioni differenziali ordinarie •  Equazioni differenziali parziali 

Interpolazione di daA 

•  Newton divided‐differences (polinomi di Newton) •  Interpolazione polinomiale di Lagrange •  Interpolazione con spline 

Interpolazione di daA: introduzione 

•  L’interpolazione consiste nel processo uQle a sAmare valori intermedi posizionaQ tra daQ definiA in modo preciso •  Se i daQ a disposizione sono (n+1), esiste un unico polinomio di grado n che passa che tuT i punQ 

reUa  parabola  cubica 

Interpolazione di daA: introduzione 

•  L’interpolazione polinomiale e’ appunto il processo di determinare l’unico polinomio di grado n che ‘fiUa’ gli (n+1) punA •  Il polinomio di ordine n puo’ essere definito in modi diversi, per esempio:   Polinomi di Newton   Polinomi di Lagrange 

QuesQ due metodi sono costruiQ in modo ideale per essere implementaQ numericamente! 

Newton divided differences •  Interpolazione lineare f1: e’ la forma piu’ semplice di interpolazione: conneUe due daQ con una reUa e la usa per sQmare il valore in punQ intermedi.  

€

f1 x( ) − f x0( )x − x0

=f x1( ) − f x0( )

x1 − x0

€

f1 x( ) = f x0( ) +f x1( ) − f x0( )

x1 − x0x − x0( )

Dalla similitudine dei due triangoli: 

Interpolazione  al prim’ordine 

Rapporto di differenze finite: derivata prima 

   

Formula per l’interpolazione lineare 

Newton divided differences •  Interpolazione quadraAca f2: Avendo a disposizione 3 punQ, e’ possibile introdurre un po’ di curvatura per fiUare meglio i daQ.  E’ posibile usare un polinomio al secondo ordine: 

€

f2 x( ) = b0 + b1 x − x0( ) + b2 x − x0( ) x − x1( )

€

f2 x( ) = a0 + a1x + a2x2 = ax 2 + bx + c

€

a0 = b0 − b1x0 + b2x0x1a1 = b1 − b2x0 − b2x1a2 = b2

Corrispondenza tra i coefficienQ: 

‘di solito’ si usa: 

Newton divided differences •  Interpolazione quadraAca f2: Come calcolare i coefficienQ? 

€

x = x0 ⇒ b0 = f x0( )

x = x1⇒ b1 =f x1( ) − f x0( )

x1 − x0

x = x2 ⇒ b2 =

f x2( ) − f x1( )x2 − x1

−f x1( ) − f x0( )

x1 − x0x2 − x0

Rapporto di differenze finite: Derivata seconda 

 

} Interpol. lineare } Interpol. quadraAca 

Newton divided differences •  Formula generale per il polinomio di ordine n fn passante per (n+1) punQ: 

€

fn x( ) = b0 + b1 x − x0( ) + b2 x − x0( ) x − x1( ) + ..+ bn x − x0( ) x − x1( ).. x − xn−1( )

Le parentesi quadre rappresentano sQme della funzione per i rapporQ alle differenze finite 

dove i coefficienQ valgono: 

€

b0 = f x0[ ]b1 = f x1,x0[ ]b2 = f x2,x1,x0[ ]...bn = f xn ,xn−1,..,x1,x0[ ]

€

f xn,xn−1,...,x1,x0[ ] =

f xn,xn−1,...,x1[ ] − f xn−1,...,x1,x0[ ]xn − x0( )

Differenze divise di ordine n 

Newton divided differences •  Formula generale per il polinomio di ordine n fn passante per (n+1) punQ: sosQtuendo 

€

fn x( ) = f x0( ) + x − x0( ) f x1,x0[ ] + x − x0( ) x − x1( ) f x2,x1,x0[ ]+..+ x − x0( ) x − x1( ).. x − xn−1( ) f xn ,xn−1,...,x0[ ]

CommenA: •  i punQ non devono necessariamente essere equispaziaQ •  i valori di x non devono essere necessariamente in ordine crescente o decrescente 

Newton divided differences: •  Errore per i polinomi interpolanA di Newton: •  La formula dei polinomi di Newton e’ simile alla formula dell’espansione di Taylor, in cui si aggiungono via via derivate agli ordini piu’ alQ della funzione. •  Un errore di troncamento puo’ essere definito come nel caso dell’approssimazione con la serie di Taylor: 

€

Rn =f (n+1) ξ( )n +1( )!

x − x0( ) x − x1( ).. x − xn( )

€

Rn =f (n+1) ξ( )n +1( )!

xi+1 − xi( )n−1

dove ξ e’ un punto appartenente all’intervallo coperto dai daQ 

InfaT, per la serie di Taylor l’errore di troncamento e’: 

Problema: il calcolo dell’errore richiederebbe la conoscenza della funzione soUostante e delle sue derivate, pertanto non e’ possibile! 

Newton divided differences: •  Errore per i polinomi interpolanA di Newton: •  Un modo alternaQvo che non richiede la conoscenza a priori della funzione soUostante e’: 

€

Rn = f x,xn ,xn−1,..,x0[ ] x − x0( ) x − x1( ).. x − xn( )

Differenza divisa all’ordine (n+1) 

Per la sua sQma, serve un punto in piu’, xn+1: 

Questa relazione e’ equivalente a: 

 

€

Rn ≅ f xn+1,xn ,xn−1,..,x0[ ] x − x0( ) x − x1( ).. x − xn( )

€

Rn = fn+1 x( ) − fn x( )fn+1 x( ) = fn x( ) + Rn

(sQma successiva) – (sQma aUuale)  

L’incremento aggiunto al caso all’ordine n per calcolare il caso all’ordine (n+1) e’ uguale all’errore per il caso all’ordine n 

Interpolazione polinomiale di Lagrange Si traUa di una riformulazione dei polinomi di Newton, molto piu’ concisa 

€

fn x( ) = Li x( ) f xi( )i= 0

n

∑

€

Li x( ) =∏ j= 0i≠ j

n x − x j

xi − x jdove 

Esempi per n=1 e n=2: 

€

f1 x( ) =x − x1x0 − x1

f x0( ) +x − x0x1 − x0

f x1( )

€

f2 x( ) =x − x1( ) x − x2( )x0 − x1( ) x0 − x2( )

f x0( ) +x − x0( ) x − x2( )x1 − x0( ) x1 − x2( )

f x1( ) +x − x0( ) x − x1( )x2 − x0( ) x2 − x1( )

f x2( )

Interpolazione polinomiale di Lagrange 

•  nella formula, ogni termine Li(x) sara’ uguale a 1 per x=xi  e nullo nella posizione di tuT gli altri punQ •  Pertanto ogni prodoUo Li(x) fi(x) assumera’ il valore di fi(x) nella posizione del punto xi •  l’errore di troncamento e’ lo stesso che si ha con i polinomi di Newton 

CommenA generali 

•  il metodo di Newton e’ preferibile per calcoli esploratori (cioe’ quando n non e’ conosciuto a priori) •  il metodo di Newton ha vantaggi dovuQ alla sua similitudine con la serie di Taylor •  la sQma dell’errore con i polinomi di Newton puo’ essere facilmente implementata perche’ uQlizza le differenze finite •  il metodo di Lagrange e’ preferibile quando soltanto un’interpolazione e’ richiesta (cioe’  quando l’ordine n e’ conosciuto a priori) •  il metodo di Lagrange e’ piu’ facile dal punto di vista computazionale 

CoefficienA dei polinomi 

•  i metodi di Newton e di Lagrange non forniscono direUamente i coefficienQ nella forma convenzionale 

€

fn x( ) = a0 + a1x + a2x2 + ...+ anx

n

•  per calcolarli, bisogna risolvere il sistema lineare algebrico di (n+1) equazioni in (n+1) incognite. Pero’ il sistema e’ notoriamente ‘mal‐condizionato’ e facilmente influenzato da errori di arrotondamento. Quindi e’ meglio tenere l’ordine n basso o usare i metodi di Newton e di Lagrange per l’interpolazione.  

Interpolazione inversa 

Due possibili soluzioni: •  scambiare x con f(x) e applicare l’interpolazione di Newton/Lagrange. •  applicare la normale interpolazione e trovare il valore di x che soddisfa il dato valore di f(x)  problema di ricerca di una radice (zero) 

f(x)  variabile dipendente x  variabile indipendente 

Extrapolazione 

•  E’ il processo di calcolare f(x) per un valore di x al di fuori dall’intervallo coperto dai valori di x •  Se il valore di x extrapolato non e’ vicino ai punQ a disposizione, l’errore commesso puo’ essere molto grande. Conseguentemente la massima cautela e’ richiesta durante l’extrapolazione.