2015 cn3 approssimazione print
DESCRIPTION
Lesson about numeric calculusTRANSCRIPT
![Page 1: 2015 Cn3 Approssimazione Print](https://reader034.vdocumenti.com/reader034/viewer/2022042717/563db789550346aa9a8bfa8f/html5/thumbnails/1.jpg)
LEZIONI DI ANALISI MATEMATICA II
APPROSSIMAZIONE DI DATI E DI FUNZIONI
Letizia SCUDERI
Dipartimento di Scienze Matematiche, Politecnico di [email protected]
A.A. 2015/2016
![Page 2: 2015 Cn3 Approssimazione Print](https://reader034.vdocumenti.com/reader034/viewer/2022042717/563db789550346aa9a8bfa8f/html5/thumbnails/2.jpg)
Approssimazione di dati e di funzioni
Approssimare una funzione f significa sostituirla con una funzione fche le sia “vicina” in qualche senso e abbia una forma piu semplice(per esempio, polinomiale) su cui si possa facilmente operare.
Un’applicazione di tale operazione si ha, per esempio,nell’integrazione numerica:
f ≈ f =⇒
∫ b
a
f (x) dx ≈
∫ b
a
f (x) dx
![Page 3: 2015 Cn3 Approssimazione Print](https://reader034.vdocumenti.com/reader034/viewer/2022042717/563db789550346aa9a8bfa8f/html5/thumbnails/3.jpg)
Approssimare un insieme di dati (xi , yi ) (ove, per esempio,yi = f (xi ) e f non e nota esplicitamente) significa determinare unafunzione f che abbia un andamento analogo a quello della funzioneche ha generato i suddetti dati.
Un’applicazione di tale operazione si ha, per esempio, nellastatistica, nella finanza, nella fisica e ogni qual volta si vuolecostruire un modello che descriva il fenomeno in questione e cipermetta di fare previsioni attendibili in punti x diversi da xi .
![Page 4: 2015 Cn3 Approssimazione Print](https://reader034.vdocumenti.com/reader034/viewer/2022042717/563db789550346aa9a8bfa8f/html5/thumbnails/4.jpg)
Nell’approssimazione di una funzione (o di un fenomeno) foccorre:
1 individuare una classe di funzioni approssimanti che sia idoneaa descrivere la suddetta funzione (o fenomeno);
2 adottare un criterio per la scelta di un suo particolareelemento f ;
3 valutare la bonta di f , ovvero la “distanza” di f da f .
Supponendo che la funzione da approssimare f appartenga allospazio lineare delle funzioni continue in [a, b] (f ∈ C [a, b]) oppuredotate di derivata k-esima continua in [a, b] (f ∈ C k [a, b]), lafunzione approssimante generalmente viene scelta in uno deiseguenti sottospazi lineari:
![Page 5: 2015 Cn3 Approssimazione Print](https://reader034.vdocumenti.com/reader034/viewer/2022042717/563db789550346aa9a8bfa8f/html5/thumbnails/5.jpg)
polinomi algebrici di grado n:
f (x) ≡ pn(x) =n∑
k=0
akxk
per l’approssimazione di funzioni continue su intervalli chiusi elimitati;
polinomi trigonometrici di grado n e frequenza ω:
f (x) ≡ tn(x) = a0 +
n∑
k=1
[ak cos(kωx) + bk sin(kωx)]
per l’approssimazione di funzioni continue e periodiche conperiodo 2π/ω su intervalli chiusi e limitati;somme esponenziali di ordine n:
f (x) ≡ en(x) =
n∑
k=0
akekx (f (x) ≡ en(x) =
n∑
k=0
ake−kx )
per l’approssimazione di funzioni con un comportamento ditipo esponenziale, male approssimabile con dei polinomi;
![Page 6: 2015 Cn3 Approssimazione Print](https://reader034.vdocumenti.com/reader034/viewer/2022042717/563db789550346aa9a8bfa8f/html5/thumbnails/6.jpg)
funzioni spline di ordine n, ovvero funzioni polinomiali a trattidotate di derivata continua fino all’ordine n− 1, perl’approssimazione di quelle funzioni che generalmente perraggiungere la tolleranza desiderata richiedono polinomi digrado elevato o eccessivamente oscillanti.
Osserviamo che ciascun elemento dei suddetti sottospazi si esprimecome una combinazione lineare di funzioni, che definiscono unabase per il sottospazio in questione, mediante i parametri akoppure ak , bk .ESEMPIO
Le funzioni che definiscono una base per il sottospazio lineare deipolinomi algebrici di grado n sono:
ϕ0(x) = 1, ϕ1(x) = x , . . . , ϕn(x) = xn
Il suddetto sottospazio ha dunque dimensione finita n + 1.
![Page 7: 2015 Cn3 Approssimazione Print](https://reader034.vdocumenti.com/reader034/viewer/2022042717/563db789550346aa9a8bfa8f/html5/thumbnails/7.jpg)
Per individuare una particolare funzione approssimante nelsottospazio prescelto, adotteremo uno dei seguenti criteri:
criterio dell’interpolazione (per l’approssimazione di unafunzione)
0 1 2 3 4 5 6−1.5
−1
−0.5
0
0.5
1
1.5
funzioneinterpolante
![Page 8: 2015 Cn3 Approssimazione Print](https://reader034.vdocumenti.com/reader034/viewer/2022042717/563db789550346aa9a8bfa8f/html5/thumbnails/8.jpg)
criterio dei minimi quadrati (per l’approssimazione di uninsieme di dati sperimentali)
0 0.2 0.4 0.6 0.8 1 1.2 1.4 1.6 1.8 20
0.5
1
1.5
2
2.5
3
3.5
4
4.5
5
![Page 9: 2015 Cn3 Approssimazione Print](https://reader034.vdocumenti.com/reader034/viewer/2022042717/563db789550346aa9a8bfa8f/html5/thumbnails/9.jpg)
Nel caso dell’approssimazione di una funzione f , per giudicare labonta dell’approssimante prescelta f , consideriamo la seguentenorma:
||f − f ||∞ := maxa≤x≤b
|f (x)− f (x)|
Quando si vuole approssimare una funzione f con una tolleranzapiccola a piacere occorre individuare una successione di sottospaziFn di dimensione finita n + 1 per la quale, scelta in ogni Fn lafunzione fn(x), risulti:
limn→∞
||f − fn|| = 0
ove|| · ||
denota una qualsiasi norma di funzione. Quando cio si verifica, sidice che fn converge in norma a f ; nel caso della norma infinito sidice che fn converge uniformemente a f .
![Page 10: 2015 Cn3 Approssimazione Print](https://reader034.vdocumenti.com/reader034/viewer/2022042717/563db789550346aa9a8bfa8f/html5/thumbnails/10.jpg)
Com’e noto una funzione puo essere approssimata in un datointervallo dal suo polinomio di Taylor di grado opportuno n. Taleprocedura e pero costosa perche richiede la conoscenza di f e dellesue derivate fino a un dato ordine n. Inoltre, il polinomio di Taylorpuo non approssimare accuratamente f quando ci si discosta dalpunto iniziale x0. In figura si puo notare come f (x) = 1/x sidiscosti dal suo polinomio di Taylor di grado 10 e di punto inizialex0 = 1, man mano che ci si allontana da x0.
1 1.2 1.4 1.6 1.8 2 2.2 2.4 2.6 2.8 30.2
0.4
0.6
0.8
1
1.2
1.4
1.6
1.8
2
1/xTf
10,1(x)
![Page 11: 2015 Cn3 Approssimazione Print](https://reader034.vdocumenti.com/reader034/viewer/2022042717/563db789550346aa9a8bfa8f/html5/thumbnails/11.jpg)
Per altre funzioni cio ovviamente non si verifica: per esempio lafunzione esponenziale puo essere approssimata in ogni punto realemediante il suo polinomio di Taylor di punto iniziale x0 = 0, purcheil grado n sia sufficientemente grande.
1 2 3 4 5 6 7 8 9 100
0.5
1
1.5
2
2.5x 10
4
ex
Tf4,0
(x)Tf
8,0(x)
Tf12,0
(x)Tf
16,0(x)
![Page 12: 2015 Cn3 Approssimazione Print](https://reader034.vdocumenti.com/reader034/viewer/2022042717/563db789550346aa9a8bfa8f/html5/thumbnails/12.jpg)
Interpolazione polinomiale
Consideriamo n + 1 dati (xi , yi ), i = 1, . . . , n + 1 (con yi = f (xi )eventualmente). Il criterio dell’interpolazione consiste nelloscegliere come approssimante, la funzione (possibilmente unica)f = fn soddisfacente le seguenti condizioni:
fn(xi ) = yi i = 1, . . . , n + 1
Generalmente il numero dei parametri presenti in fn coincide con ilnumero dei punti xi , ovvero n + 1. Assegnati gli n + 1 punti(xi , yi ), i = 1, . . . , n + 1, utilizziamo il criterio dell’interpolazioneper determinare il polinomio di grado minimo che passa per i puntiassegnati. Poiche i punti sono n + 1, consideriamo il genericopolinomio di grado n
pn(x) = c1xn + c2x
n−1 + . . .+ cnx + cn+1,
definito dagli n + 1 coefficienti c1, . . . , cn+1.
![Page 13: 2015 Cn3 Approssimazione Print](https://reader034.vdocumenti.com/reader034/viewer/2022042717/563db789550346aa9a8bfa8f/html5/thumbnails/13.jpg)
Dimostriamo che se xi 6= xj per i 6= j allora esiste uno e un solpolinomio soddisfacente le condizioni (di interpolazione):
pn(xi ) = yi , i = 1, . . . , n + 1.
Imponendo le condizioni di interpolazione
c1xni + c2x
n−1i + . . .+ cnxi + cn+1 = yi , i = 1, . . . , n + 1
otteniamo il sistema lineare
xn1 . . . x1 1xn2 . . . x2 1...
......
...xnn+1 . . . xn+1 1
c1c2...cn+1
=
y1y2...yn+1
⇐⇒ Vc = y
la cui matrice dei coefficienti e la matrice di Vandermonde.
![Page 14: 2015 Cn3 Approssimazione Print](https://reader034.vdocumenti.com/reader034/viewer/2022042717/563db789550346aa9a8bfa8f/html5/thumbnails/14.jpg)
Poichedet(V ) =
∏
i>j
(xi − xj)
e gli xi sono distinti, la matrice V e non singolare. Ne deduciamoche
∃! c∗ = (c∗1 , . . . , c∗n+1)
T : Vc∗ = y .
Il polinomio pn i cui coefficienti sono soluzione del sistema Vc = y
e denominato polinomio interpolante i dati (xi , yi) oppure, seyi = f (xi ), interpolante la funzione f nei punti xi . I punti xisono detti nodi di interpolazione.
![Page 15: 2015 Cn3 Approssimazione Print](https://reader034.vdocumenti.com/reader034/viewer/2022042717/563db789550346aa9a8bfa8f/html5/thumbnails/15.jpg)
Comandi MATLAB
c = polyfit(x,y,n) calcola e memorizza in c , i coefficienti delpolinomio interpolante i punti (xi , yi ), i = 1, . . . , n + 1,definiti in x e in y , rispettivamente;
p = polyval(c,z) calcola e memorizza in p, i valori che ilpolinomio, con coefficienti definiti in c , assume nei punti di z .
![Page 16: 2015 Cn3 Approssimazione Print](https://reader034.vdocumenti.com/reader034/viewer/2022042717/563db789550346aa9a8bfa8f/html5/thumbnails/16.jpg)
ESEMPIO
Calcoliamo e rappresentiamo graficamente il polinomiointerpolante i dati (0, 1), (1,−1), (2, 1), (1/2, 2):
x = [0 1 2 1/2];
y = [1 -1 1 2];
c = polyfit(x,y,length(x)-1);
z = linspace(min(x),max(x));
p = polyval(c,z);
plot(x,y,’ro’,z,p,’b’)
0 0.2 0.4 0.6 0.8 1 1.2 1.4 1.6 1.8 2−4
−3
−2
−1
0
1
2
3
![Page 17: 2015 Cn3 Approssimazione Print](https://reader034.vdocumenti.com/reader034/viewer/2022042717/563db789550346aa9a8bfa8f/html5/thumbnails/17.jpg)
ESEMPIO
Calcoliamo i coefficienti del polinomio interpolante la funzionef (x) = 1/(1 + x2) in 13 punti equispaziati nell’intervallo [0, 1].
x = linspace(0,1,13);
f = inline(’1./(1+x.^2)’);
y = f(x);
c = polyfit(x,y,length(x)-1);
Warning: Polynomial is badly conditioned.....
A causa del noto cattivo condizionamento di un sistema lineare conmatrice dei coefficienti di Vandermonde e del costo della suarisoluzione in termini di operazioni aritmetiche, per l’effettivacostruzione di un polinomio interpolante si utilizzanorappresentazioni alternative.
![Page 18: 2015 Cn3 Approssimazione Print](https://reader034.vdocumenti.com/reader034/viewer/2022042717/563db789550346aa9a8bfa8f/html5/thumbnails/18.jpg)
Rappresentazione di Lagrange del polinomio diinterpolazione
Per ogni j = 1, . . . , n + 1 consideriamo i punti (xi , δij ),i = 1, . . . , n + 1, ovvero
(x1, 0), . . . , (xj−1, 0), (xj , 1), (xj+1, 0), . . . , (xn+1, 0)
e denotiamo con lj(x) il polinomio interpolante i suddetti punti,cioe tale che
lj(xi ) = δij =
{1 se i = j
0 se i 6= j
E immediato dimostrare che per ogni j = 1, . . . , n + 1
lj(x) =(x − x1) · · · (x − xj−1)(x − xj+1) · · · (x − xn+1)
(xj − x1) · · · (xj − xj−1)(xj − xj+1) · · · (xj − xn+1)
![Page 19: 2015 Cn3 Approssimazione Print](https://reader034.vdocumenti.com/reader034/viewer/2022042717/563db789550346aa9a8bfa8f/html5/thumbnails/19.jpg)
I polinomi di grado n
lj(x) =∏
1≤i≤n+1,i 6=j
(x − xi )
(xj − xi)
sono detti polinomi fondamentali di Lagrange associati ai nodixi . Noti i polinomi lj(x), il polinomio pn interpolante i punti(xi , yi ), i = 1, . . . , n + 1, si definisce nel seguente modo
pn(x) =n+1∑
j=1
yj lj(x)
Infatti risulta che pn e un polinomio di grado n e soddisfa lecondizioni di interpolazione:
pn(xi ) =
n+1∑
j=1
yj lj(xi ) =
n+1∑
j=1
yjδij = yi .
La rappresentazione di pn, come combinazione lineare deipolinomi lj , e detta di Lagrange.
![Page 20: 2015 Cn3 Approssimazione Print](https://reader034.vdocumenti.com/reader034/viewer/2022042717/563db789550346aa9a8bfa8f/html5/thumbnails/20.jpg)
ESEMPIO
Scriviamo la rappresentazione di Lagrange del polinomio p3(x)interpolante i punti (0, 1), (1,−1), (2, 1), (1/2, 2). Definiamodapprima i polinomi lj(x), j = 1, 2, 3, 4:
l1(x) = (x−1)(x−2)(x−1/2)(0−1)(0−2)(0−1/2)
l2(x) = (x−0)(x−2)(x−1/2)(1−0)(1−2)(1−1/2)
l3(x) = (x−0)(x−1)(x−1/2)(2−0)(2−1)(2−1/2)
l4(x) = (x−0)(x−1)(x−2)(1/2−0)(1/2−1)(1/2−2)
0 0.2 0.4 0.6 0.8 1 1.2 1.4 1.6 1.8 2−1.5
−1
−0.5
0
0.5
1
1.5
2
l1l2l3l4
Quindi definiamo p3(x):
p3(x) = 1 · l1(x)− 1 · l2(x) + 1 · l3(x) + 2 · l4(x)
![Page 21: 2015 Cn3 Approssimazione Print](https://reader034.vdocumenti.com/reader034/viewer/2022042717/563db789550346aa9a8bfa8f/html5/thumbnails/21.jpg)
Osserviamo che i polinomi lj(x) dipendono dall’insieme completodei nodi {x1, . . . , xn+1} e, pertanto se vogliamo aggiungere unpunto di interpolazione (xn+2, yn+2) all’insieme dei punti{(xi , yi )}i=1,...,n+1 dobbiamo ricalcolare tutti i polinomi lj(x).
Per questo motivo la rappresentazione di Lagrange, pur essendomolto utilizzata per dimostrare le proprieta teorichedell’interpolazione polinomiale, non viene considerata nella praticaper costruire il polinomio interpolante.
![Page 22: 2015 Cn3 Approssimazione Print](https://reader034.vdocumenti.com/reader034/viewer/2022042717/563db789550346aa9a8bfa8f/html5/thumbnails/22.jpg)
Rappresentazione di Newton del polinomio diinterpolazione
Descriviamo allora la rappresentazione del polinomio diinterpolazione che di fatto si utilizza per il calcolo del suddettopolinomio.A tal scopo, dati n + 1 punti xi con i = 1, ..., n + 1 distinti,definiamo le seguenti la quantita
f [x1, x2] =f (x2)− f (x1)
x2 − x1
differenza divisa di ordine 1 di f (x),
f [x1, x2, x3] =f [x2, x3]− f [x1, x2]
x3 − x1
differenza divisa di ordine 2, e piu in generale
f [x1, x2, . . . , xn+1] =f [x2, . . . , xn+1]− f [x1, . . . , xn]
xn+1 − x1
differenza divisa di ordine n.
![Page 23: 2015 Cn3 Approssimazione Print](https://reader034.vdocumenti.com/reader034/viewer/2022042717/563db789550346aa9a8bfa8f/html5/thumbnails/23.jpg)
Le differenze divise sono invarianti rispetto a permutazioni degliargomenti, cioe
f [x1, x2] = f [x2, x1], f [x1, x2, x3] = f [x2, x1, x3] = f [x3, x2, x1], . . .
Si definisce rappresentazione di Newton del polinomiointerpolante i punti (xi , yi ) con yi = f (xi), la seguente espressione
pn(x) = f (x1) + f [x1, x2](x − x1) + f [x1, x2, x3](x − x1)(x − x2)+ . . .+ f [x1, x2, . . . , xn+1](x − x1) . . . (x − xn)
I polinomi 1, x − x1, ...,(x − x1) . . . (x − xn) sono detti polinomi
fondamentali di Newton.E facile verificare che il polinomio
p0(x) = f (x1)
interpola f (x) in x1,
![Page 24: 2015 Cn3 Approssimazione Print](https://reader034.vdocumenti.com/reader034/viewer/2022042717/563db789550346aa9a8bfa8f/html5/thumbnails/24.jpg)
il polinomiop1(x) = f (x1)
︸ ︷︷ ︸
p0(x)
+f [x1, x2](x − x1)
interpola f (x) in x1, x2 e, cosı procedendo, denotato con pn−1(x) ilpolinomio interpolante f (x) in x1, . . . , xn, il polinomio
pn(x) = pn−1(x) + f [x1, x2, . . . , xn+1](x − x1) . . . (x − xn)
interpola f (x) in x1, . . . , xn+1.Pertanto, se vogliamo aggiungere all’insieme dei nodi x1, . . . , xn+1
un ulteriore nodo xn+2, poiche l’espressione del polinomiointerpolante f (x) in xi , i = 1, . . . , n + 2, e data da
pn+1(x) = pn(x) + f [x1, x2, . . . , xn+2](x − x1) . . . (x − xn+1),
noto pn, dobbiamo calcolare soltanto l’ultimo addendo.
![Page 25: 2015 Cn3 Approssimazione Print](https://reader034.vdocumenti.com/reader034/viewer/2022042717/563db789550346aa9a8bfa8f/html5/thumbnails/25.jpg)
Descriviamo ora l’algoritmo che consente di calcolare le differenzedivise presenti nella rappresentazione di Newton del polinomiointerpolante. A tal scopo consideriamo il polinomio di grado 3interpolante i punti (x1, f (x1)), (x2, f (x2)), (x3, f (x3)), (x4, f (x4)):
p3(x) = f (x1) + f [x1, x2](x − x1) + f [x1, x2, x3](x − x1)(x − x2)+f [x1, x2, x3, x4](x − x1)(x − x2)(x − x3)
e calcoliamo le differenze divise in esso presenti, procedendosecondo il seguente schema:
x1
x2
x3
x4
f (x1)
f (x2)
f (x3)
f (x4)
i = 1
↘→ f [x1, x2]↘→ f [x2, x3]↘→ f [x3, x4]
i = 2
↘→ f [x1, x2, x3]↘→ f [x2, x3, x4]
i = 3
↘→ f [x1, x2, x3, x4]
![Page 26: 2015 Cn3 Approssimazione Print](https://reader034.vdocumenti.com/reader034/viewer/2022042717/563db789550346aa9a8bfa8f/html5/thumbnails/26.jpg)
ESEMPIO
Scriviamo la rappresentazione di Newton del polinomio p3(x)interpolante i punti (0, 1), (1,−1), (2, 1), (1/2, 2). Calcoliamo ledifferenze divise:
0
1
2
1/2
1
−1
1
2
i = 1
↘→ −1−1
1−0 = −2
↘
→ 1−(−1)2−1 = 2
↘→ 2−1
1/2−2 = −23
i = 2
↘
→ 2−(−2)2−0 = 2
↘
→ −2/3−21/2−1 = 16
3
i = 3
↘
→ 16/3−21/2−0 = 20
3
Si ha allora
p3(x) = 1− 2(x − 0) + 2(x − 0)(x − 1) +20
3(x − 0)(x − 1)(x − 2)
![Page 27: 2015 Cn3 Approssimazione Print](https://reader034.vdocumenti.com/reader034/viewer/2022042717/563db789550346aa9a8bfa8f/html5/thumbnails/27.jpg)
Convergenza del polinomio di interpolazione
Denotato con pn il polinomio interpolante la funzione f nei puntix1, . . . , xn+1, si definisce errore di interpolazione la funzione
En(x) = f (x)− pn(x)
Osserviamo che En(x) = 0 per x = xi (avendosiEn(xi ) = f (xi )− pn(xi ) ≡ 0) e En(x) ≡ 0 per ogni x ∈ [a, b] e perf = p con p polinomio di grado n (avendosi, per l’unicita delpolinomio interpolante, pn ≡ p).Cio premesso, affrontiamo la questione della convergenza:
limn→∞
En(x) = 0 per ogni x e qualunque sia f ?
![Page 28: 2015 Cn3 Approssimazione Print](https://reader034.vdocumenti.com/reader034/viewer/2022042717/563db789550346aa9a8bfa8f/html5/thumbnails/28.jpg)
La risposta a questa domanda non e sempre affermativa; infatti sidimostra che, fissata una matrice di interpolazione ovvero unamatrice di nodi
x1x1 x2x1 x2 x3x1 x2 x3 x4. . .
con xi ∈ [a, b] e xi 6= xj , i 6= j , e sempre possibile determinare unafunzione f ∈ C [a, b] per la quale si abbia
limn→∞
||En||∞ 6= 0
La convergenza a zero di ||En||∞ dipende dalla matrice dei nodi diinterpolazione e dalla regolarita della funzione f . Se i nodi diinterpolazione vengono opportunamente scelti e f esufficientemente regolare, allora pn converge uniformemente a f ,per n → ∞.
![Page 29: 2015 Cn3 Approssimazione Print](https://reader034.vdocumenti.com/reader034/viewer/2022042717/563db789550346aa9a8bfa8f/html5/thumbnails/29.jpg)
Se i nodi di interpolazione sono scelti equispaziati in [a, b], lacondizione f ∈ C∞[a, b] non garantisce che limn→∞ ||En||∞ = 0.ESEMPIO
Se i nodi xi sono scelti equispaziati in [−5, 5] e f (x) = 11+x2
(funzione di Runge), si ha limn→∞ ||En||∞ = ∞.
−5 −4 −3 −2 −1 0 1 2 3 4 5−1.5
−1
−0.5
0
0.5
1
punti di interpolazionefunzione di Rungepolinomio interpolante p
9polinomio interpolante p
13
![Page 30: 2015 Cn3 Approssimazione Print](https://reader034.vdocumenti.com/reader034/viewer/2022042717/563db789550346aa9a8bfa8f/html5/thumbnails/30.jpg)
Se i nodi di interpolazione sono scelti equispaziati in [a, b] e f (z) eanalitica in una regione D contenente [a, b] e la distanza dei poli dif (z) da [a, b] e maggiore di b − a, allora limn→∞ ||En||∞ = 0.ESEMPIO
Se i nodi xi sono scelti equispaziati in [1, 2] e f (x) = 11+x2
(funzione di Runge), si ha limn→∞ ||En||∞ = 0.
1 1.1 1.2 1.3 1.4 1.5 1.6 1.7 1.8 1.9 20.15
0.2
0.25
0.3
0.35
0.4
0.45
0.5
0.55
punti di interpolazione funzione di Rungepolinomio interpolante p
9
polinomio interpolante p13
![Page 31: 2015 Cn3 Approssimazione Print](https://reader034.vdocumenti.com/reader034/viewer/2022042717/563db789550346aa9a8bfa8f/html5/thumbnails/31.jpg)
Se i nodi di interpolazione sono scelti coincidenti con gli zeri deipolinomi di Chebyshev,zi = − cos((2i − 1)/(2(n + 1))π) ∈ (−1, 1), i = 1, . . . , n + 1, lacondizione f ∈ C 1[−1, 1] garantisce che limn→∞ ||En(x)||∞ = 0.ESEMPIO
Se i nodi xi sono scelti coincidenti con gli zeri dei polinomi diChebyshev traslati in [−5, 5], cioe xi =
b−a2 zi +
b+a2 , a = −5 e
b = 5 e f (x) = 11+x2
(funzione di Runge), alloralimn→∞ ||En(x)||∞ = 0.
−5 −4 −3 −2 −1 0 1 2 3 4 50
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1
puntiRungep
9p
13
![Page 32: 2015 Cn3 Approssimazione Print](https://reader034.vdocumenti.com/reader034/viewer/2022042717/563db789550346aa9a8bfa8f/html5/thumbnails/32.jpg)
Funzioni polinomiali a tratti: spline
Una funzione polinomiale a tratti di grado d , associata a unapartizione dell’intervallo [a, b], e una funzione rappresentata in[a, b] da un’unione di tratti contigui di polinomi algebrici diversi,ciascuno di grado d .
0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 10
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
d=1
d=2
![Page 33: 2015 Cn3 Approssimazione Print](https://reader034.vdocumenti.com/reader034/viewer/2022042717/563db789550346aa9a8bfa8f/html5/thumbnails/33.jpg)
In generale il grado d viene scelto piccolo (d = 1, 2, 3).Osserviamo che le funzioni polinomiali a tratti sono continue, mageneralmente non sono derivabili nei punti di raccordo. Le funzionispline sono funzioni polinomiali a tratti che godono di opportunecondizioni di regolarita nei punti di raccordo. Le funzionipolinomiali a tratti vengono utilizzate in tutte quelle situazioni (peresempio, nelle applicazioni grafiche) in cui il comportamentoeccessivamente oscillatorio del polinomio di interpolazione alcrescere del grado n non e accettabile.
−5 −4 −3 −2 −1 0 1 2 3 4 50
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1
puntiRungep
12
spline
![Page 34: 2015 Cn3 Approssimazione Print](https://reader034.vdocumenti.com/reader034/viewer/2022042717/563db789550346aa9a8bfa8f/html5/thumbnails/34.jpg)
Inoltre, le funzioni polinomiali a tratti, associate a una partizionedell’intervallo [a, b] e interpolanti una funzione f nei punti dellapartizione, convergono uniformemente alla funzione interpolata alcrescere del numero dei nodi della partizione, ovvero al diminuiredell’ampiezza dei sottointervalli della partizione.Le spline cubiche sono funzioni polinomiali a tratti di grado locale3 molto utilizzate nelle applicazioni.
![Page 35: 2015 Cn3 Approssimazione Print](https://reader034.vdocumenti.com/reader034/viewer/2022042717/563db789550346aa9a8bfa8f/html5/thumbnails/35.jpg)
Dati n + 1 punti (xi , yi ), i = 1, . . . , n + 1 con xi 6= xj per i 6= j eyi = f (xi ), si definisce spline cubica interpolante i punti assegnati,la funzione S3(x) soddisfacente le seguenti condizioni:
i) S3(x) = ai + bix + cix2 + dix
3, x ∈ [xi , xi+1], i = 1, . . . , n
ii) S(k)3 (x−i ) = S
(k)3 (x+i ), k = 0, 1, 2, i = 2, . . . , n
iii) S3(xi ) = yi , i = 1, . . . , n + 1
Osserviamo che S3 dipende da 4n parametri {ai , bi , ci , di},i = 1, . . . , n; imponendo le n − 1 condizioni ii) per k = 0, 1, 2, e len + 1 condizioni di interpolazione iii), si ottiene un sistema linearedi 3(n − 1) + (n + 1) = 4n − 2 equazioni nelle 4n incognite{ai , bi , ci , di}. Pertanto, per definire univocamente una splineoccorre imporre due ulteriori condizioni.
![Page 36: 2015 Cn3 Approssimazione Print](https://reader034.vdocumenti.com/reader034/viewer/2022042717/563db789550346aa9a8bfa8f/html5/thumbnails/36.jpg)
Fra tutte le possibili scelte, tipiche condizioni aggiuntive sono:
1) S(2)3 (x1) = 0, S
(2)3 (xn+1) = 0 (spline cubiche naturali);
2) S(3)3 (x−2 ) = S
(3)3 (x+2 ), S
(3)3 (x−n ) = S
(3)3 (x+n ) (condizioni
“not-a-knot”);
3) S(1)3 (x1) = f ′(x1), S
(1)3 (xn+1) = f ′(xn+1).
Imponendo una delle suddette condizioni, la spline corrispondenteesiste e e unica. Per l’effettiva costruzione di una spline non siricorre alla risoluzione del predetto sistema lineare nelle 4nincognite {ai , bi , ci , di}, ma alla risoluzione di un sistema lineare
nelle n+ 1 incognite Mi = S(2)3 (xi ), i = 1, . . . , n+ 1, simmetrico, a
diagonale dominante e tridiagonale se si impone una dellecondizioni aggiuntive 1)-3).
![Page 37: 2015 Cn3 Approssimazione Print](https://reader034.vdocumenti.com/reader034/viewer/2022042717/563db789550346aa9a8bfa8f/html5/thumbnails/37.jpg)
Si dimostra che se con S3 denotiamo la spline cubica, interpolantei punti (xi , f (xi )) (a ≤ xi ≤ b) e soddisfacente una delle condizioniaggiuntive 1)-3), con h = max1≤i≤n(xi+1 − xi ) e supponiamo chef ∈ C 4[a, b], allora
||f (p) − S(p)3 ||∞ = O(h4−p), h → 0, p = 0, 1, 2, 3.
Pertanto, risulta che le spline cubiche S3 convergonouniformemente alla funzione f e le derivate di S3 fino a quelle diordine 3 convergono uniformemente alle corrispondenti derivate dif (simultanea approssimazione). Quest’ultimo risultato ci consentedi approssimare la derivata di una funzione f utilizzando soltantovalori di f e non quelli di f ′.
Si dimostra pero che O(h4) e il massimo ordine di convergenza chepossiamo avere con le spline considerate, cioe ||f − S3||∞ = O(h4)anche quando f ∈ C k [a, b] con k > 4 (saturazione).
![Page 38: 2015 Cn3 Approssimazione Print](https://reader034.vdocumenti.com/reader034/viewer/2022042717/563db789550346aa9a8bfa8f/html5/thumbnails/38.jpg)
Comandi MATLAB
s = spline(x,y,z) calcola e memorizza in s i valori che laspline cubica interpolante i dati (xi , yi), i = 1, . . . , n, definitiin x e in y rispettivamente, e soddisfacente la condizione“not-a-knot” 2), assume in z ;
s = spline(x,[yd1 y ydn],z) calcola e memorizza in s ivalori che la spline cubica interpolante i dati (xi , yi ),i = 1, . . . , n, definiti in x e in y rispettivamente, esoddisfacente la condizione 3) (yd1= f ′(x1), ydn= f ′(xn)),assume in z .
![Page 39: 2015 Cn3 Approssimazione Print](https://reader034.vdocumenti.com/reader034/viewer/2022042717/563db789550346aa9a8bfa8f/html5/thumbnails/39.jpg)
Criterio dei minimi quadrati (cenni)
Abbiamo gia notato che l’interpolazione polinomiale non garantisceal crescere del grado del polinomio una maggiore accuratezzanell’approssimazione di una funzione. Questo problema puo esseresuperato con l’interpolazione mediante funzioni polinomiali a tratti.Essa tuttavia mal si presta a essere utilizzata per estrapolareinformazioni da dati noti, ovvero per generare valutazioni in puntiche giacciono al di fuori dell’intervallo di interpolazione. Inquest’ultimo caso conviene utilizzare il criterio dei minimi quadrati.Tale criterio viene adottato anche quando si vuole approssimare uninsieme di dati (xi , yi ), i = 1, . . . ,m con una funzioneapprossimante f che dipende da un numero n << m di parametri.Consideriamo, come funzione approssimante f , una combinazionelineare (a coefficienti costanti) delle funzioni base ϕk(x),k = 1, . . . , n:
f (x) = c1ϕ1(x) + c2ϕ2(x) + . . .+ cnϕn(x)
![Page 40: 2015 Cn3 Approssimazione Print](https://reader034.vdocumenti.com/reader034/viewer/2022042717/563db789550346aa9a8bfa8f/html5/thumbnails/40.jpg)
Con il criterio dei minimi quadrati i coefficienti ck si determinanoimponendo che il residuo
ε2(c1, . . . , cn) =
m∑
i=1
[yi − f (xi )]2 =
m∑
i=1
[
yi −
n∑
k=1
ckϕk(xi )
]2
risulti minimo.
0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1−0.1
0
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
(xi,y
i)
(xi,p
3(x
i))
La funzione f ∗(x) =∑n
k=1 c∗kϕk(x) che soddisfa la suddetta
condizione viene definita migliore approssimazione dei dati(xi , yi ), i = 1, . . . ,m, secondo il criterio dei minimi quadrati.
![Page 41: 2015 Cn3 Approssimazione Print](https://reader034.vdocumenti.com/reader034/viewer/2022042717/563db789550346aa9a8bfa8f/html5/thumbnails/41.jpg)
Osserviamo esplicitamente che per n ≡ m − 1, la miglioreapprossimazione f ∗ dei dati (xi , yi ), i = 1, . . . ,m, secondo ilcriterio dei minimi quadrati, e la funzione interpolante i punti(xi , yi ). Infatti, per essa si ha ε2 ≡ 0.In generale, n << m e i coefficienti ck si determinano imponendola condizione necessaria per l’esistenza del minimo.
Comando MATLAB
c = polyfit(x,y,n) calcola e memorizza in c i coefficienti delpolinomio di grado n che meglio approssima secondo il criterio deiminimi quadrati i dati (xi , yi), i = 1, . . . ,m, definiti in x e in y ,rispettivamente (se n ≡ m − 1, polyfit calcola i coefficienti delpolinomio interpolante i dati assegnati).
![Page 42: 2015 Cn3 Approssimazione Print](https://reader034.vdocumenti.com/reader034/viewer/2022042717/563db789550346aa9a8bfa8f/html5/thumbnails/42.jpg)
ESEMPIO
Supponiamo di avere a disposizione un programma per il calcolodei coefficienti del polinomio di grado n che interpola o meglioapprossima un insieme di m dati secondo il criterio dei minimiquadrati (per esempio, polyfit), e di voler calcolare i coefficientidella somma esponenziale
f (x) = c1enx + c2e
(n−1)x + ...+ cn+1 =
n+1∑
k=1
cke(n+1−k)x
di ordine n, che interpola o meglio approssima secondo il criteriodei minimi quadrati i dati (xi , yi ), con i = 1, . . . ,m.
![Page 43: 2015 Cn3 Approssimazione Print](https://reader034.vdocumenti.com/reader034/viewer/2022042717/563db789550346aa9a8bfa8f/html5/thumbnails/43.jpg)
Per risolvere il problema assegnato, possiamo effettuare ilcambiamento di variabile x = log(t), ovvero t = ex :
f (x) = f (log(t)) =n+1∑
k=1
cktn+1−k =: pn(t)
che lascia inalterati i coefficienti {ck} di f e determinare, tramite ilsuddetto algoritmo, i coefficienti del polinomio pn(t) di grado n
che interpola o meglio approssima secondo il criterio dei minimiquadrati i dati (ti , yi ) = (exi , yi ), i = 1, . . . ,m.
Comando MATLAB
c = polyfit(exp(x),y,n) calcola e memorizza in c i coefficienti dellasomma esponenziale di ordine n che intepola o meglio approssimasecondo il criterio dei minimi quadrati i dati (xi , yi), i = 1, . . . ,m,definiti in x e in y , rispettivamente.