Interpolazione Polinomiale a tratti

Serena Morigi
Dipartimento di Matematica
Università di Bologna
Interpolazione
Polinomiale a tratti
Dai polinomi ai polinomi a
tratti…..
˜ I polinomi sono funzioni regolari,
facilmente calcolabili, con derivata ed
antiderivata ancora in forma polinomiale,
approssimano funzioni continue..
˜ I polinomi possono presentare la
caratteristica di oscillare all’aumentare del
grado;
˜ Buon comportamento su piccoli intervalli
e grado basso (n <4,5);
Serena Morigi
Dipartimento di Matematica
Università di Bologna
Dai polinomi …..
ai polinomi a tratti
Si suddivide l’intervallo in tratti più piccoli e si lavora su questi
con polinomi di grado relativamente basso;
Serena Morigi
Dipartimento di Matematica
Università di Bologna
Interpolazione Polinomiale a
tratti
˜ Siano assegnate m+1 osservazioni yi,
i=0,..,m nei punti (NODI):
a = x0 < x1 < x2 < ... < xm = b
˜ Un polinomio interpolante a tratti consiste
di m polinomi di grado n<<m:
p0 ( x), p1 ( x),..., pm −1 ( x),
pk ( x) definito su [ xk , xk +1 ]
soddisfa
Serena Morigi
p k ( xk ) = y k
pk ( xk +1 ) = yk +1
Dipartimento di Matematica
k = 0,..., m − 1
Università di Bologna
Polinomi a tratti di interpolazione
di grado 1
yk +1 − yk
p( x ) = pk ( x ) = yk + ( x − xk )
; x ∈ [ xk , xk +1 ]
xk +1 − xk
a=x1 x2 xk
Serena Morigi
xk+1
Dipartimento di Matematica
xm+1=b
Università di Bologna
Polinomi a tratti di interpolazione
• Si è però persa un’ importante proprietà:
i polinomi a tratti non sono necessariamente funzioni
regolari:
• ESEMPIO: se n=1, p(x) è funzione continua, ma
p’(x) non è continua, assume un valore costante dk
y k +1 − y k
dk =
xk +1 − xk
su ogni sottointervallo, con salti nei nodi.
Serena Morigi
Dipartimento di Matematica
Università di Bologna
Pendenza nei punti
Serena Morigi
Dipartimento di Matematica
Università di Bologna
Interpolazione cubica (n=3) a
tratti di Hermite
Dati i valori y0,..,ym corrispondenti ai parametri
x0,..,xm, e le corrispondenti tangenti d0,..,dm
Determinare un polinomio
cubico C1 a tratti che
interpoli i dati:
Serena Morigi
p ( xi ) = yi , i = 0,.., m
d
p ( xi ) = d i
dt
Dipartimento di Matematica
Università di Bologna
m polinomi cubici --> 4m incognite,
su ciascun tratto risolvere il sistema 4x4:
⎧ p ( xk ) = y k ;
⎨
⎩ p ' ( xk ) = d k ;
p ( xk +1 ) = yk +1
p ' ( xk +1 ) = d k +1
Polinomio cubico interpolante a tratti:
3
3hk s − 2 s
hk − 3hk s + 2 s
yk +
yk +1 +
p( x) =
3
3
hk
hk
2
3
2
3
s ( s − hk )
s ( s − hk )
dk
d k +1 +
2
2
hk
hk
2
s = x − xk
Serena Morigi
2
hk = xk +1 − xk
Dipartimento di Matematica
Università di Bologna
Stime delle derivate
hk=xk+1-xk
fk=yk+1-yk
yk
k=0,..,m-1
dk=fk/hk
Dk = (1 − ck )d k −1 + ck d k
yk+1
yk-1
xk-1
xk
xk+1
Es. (stima di Bessel) no oscillazioni
hk −1
ci =
hk −1 − hk
Serena Morigi
Dipartimento di Matematica
Università di Bologna
Interpolazione
polinomiale a tratti
Siano assegnate m+1 osservazioni yk k=0,..,m
nei punti distinti xk in [a,b]
nodi
x0 x1
a
x2
xk
b
un polinomio interpolante a tratti consiste di m
polinomi pk(x),k=0,..,m-1, di grado n<<m :
pk ( x) definito su [ xk , xk +1 ]
1)
pk −1 ( xi ) ≡ pk ( xi ) = yi , k = 1,.., m − 1
2)
pk(l−)1 ( xk ) = pk(l ) ( xk ) l = 0,.., N
k = 1,..., m − 1
L’interpolante a tratti è di classe CN ,funzione continua fino alla
derivata
di ordine N≤n-1Dipartimento di Matematica
Serena Morigi
Università di Bologna
Def. Funzione Spline s(x)
1. s( x ) ≡ s j ( x ), x ∈ I j ,
j = 0,.., k , s j ( x ) ∈ Pn
2. continuità sui nodi :
D ( l ) s j −1 ( x j ) ≡ D ( l ) s j ( x j ), l = 0,.., n − 1 ( s( x ) ∈ C n −1 )
I0
x0
I1
x1
Ik-1
x2
Ik
xk
xk+1
Spline polinomiale:
polinomio a tratti con condizioni di massima
regolarità nei nodi
Serena Morigi
Dipartimento di Matematica
Università di Bologna
Esempio: spline cubica naturale
Spline Interpolante i dati (xi,yi), i=1,..3 è definita da due pol. cubici
su intervalli [x1,x2] e [x2,x3] che si raccordano C2.
x1
p1 ( x ) = a1 + a2 x + a3 x 2 + a4 x 3
x2
x3
p2 ( x ) = b1 + b2 x + b3 x 2 + b4 x 3
Risolvere il sistema 8x8 nelle incognite ai, bi, i=1,4
⎧ a1 + a2 x1 + a3 x12 + a4 x13 = y1 a1 + a2 x2 + a3 x2 2 + a4 x2 3 = y2
⎪
2
3
2
3
b
b
x
b
x
b
x
y
b
b
x
b
x
b
x
+
+
+
=
+
+
+
⎪1 2 2 3 2
4 2
2
1
2 3
3 3
4 3 = y3
⎪
2
2
2
3
2
3
a
a
x
a
x
b
b
x
b
x
+
+
=
+
+
⎨
2
3 2
4 2
2
3 2
4 2
⎪
2a3 + 6a4 x2 = 2b3 + 6b4 x2
⎪
⎪⎩
2a3 + 6a4 x1 = 0 2b3 + 6b4 x3 = 0
Serena Morigi
Dipartimento di Matematica
Università di Bologna
Esempio: spline cubica naturale
p1 ( x ) = a1 + a2 x + a3 x 2 + a4 x 3
p2 ( x ) = b1 + b2 x + b3 x 2 + b4 x 3
⎡1 x1
⎢
⎢1 x 2
⎢0 0
⎢
⎢0 0
⎢0 1
⎢
⎢0 0
⎢0 0
⎢
⎢⎣0 0
x12
x13
0
0
0
x22
0
x23
0
0
1
0
0
x2
x22
0
2 x2
2
0
3x22
6 x2
1 x3
x32
0 − 1 − 2 x2
0
0
−2
2
0
6 x1
0
0
0
0
0
0
2
0 ⎤ ⎡ a1 ⎤ ⎡ y1 ⎤
⎥⎢ ⎥ ⎢ ⎥
0 ⎥ ⎢a2 ⎥ ⎢ y 2 ⎥
x23 ⎥ ⎢ a3 ⎥ ⎢ y 2 ⎥
⎢ ⎥
3 ⎥ ⎢a ⎥
x3 ⎥ ⎢ 4 ⎥ ⎢ y 3 ⎥
=
2 ⎥⎢ b ⎥
⎢0⎥
− 3 x2 1
⎥⎢ ⎥ ⎢ ⎥
− 6 x2 ⎥ ⎢ b2 ⎥ ⎢ 0 ⎥
0 ⎥⎥ ⎢ b3 ⎥ ⎢ 0 ⎥
⎢ ⎥ ⎢ ⎥
6 x3 ⎥⎦ ⎢⎣ b4 ⎥⎦ ⎢⎣ 0 ⎥⎦
Funzioni di base diverse da quelle polinomiali qui utilizzate
portano a sistemi con matrici coefficienti con strutture a banda.
Serena Morigi
Dipartimento di Matematica
Università di Bologna
Interpolazione di funzioni
˜ Assegnati i punti Pi(ti,yi) con valori
trovare la funzione che passa per
tali punti
f(ti)=yi
i=0,..,n
˜ Risolvere il sistema lineare:
Va = Y
Serena Morigi
Dipartimento di Matematica
Università di Bologna
Curve in forma
parametrica
Una curva parametrica nello spazio è definita da tre funzioni
x(t) y(t) e z(t) del parametro t. Al variare di t, le coordinate
(x(t),y(t),z(t)) individuano un punto che si sposta sulla curva.
F(a)
z
x
y
ti
F(t)
F(b)
ti
F(t)=(x(t),y(t),z(t))
a
b
t in [a,b] individua un segmento di curva
Serena Morigi
Dipartimento di Matematica
Università di Bologna
Interpolazione con curve in
forma parametrica
˜ Assegnati i punti Pi(xi,yi) con valori
dei parametri corrispondenti ti
trovare la curva c(t)=(cx(t),cy(t))
che passa per tali punti
c(ti)=Pi i=0,..,m
˜ Risolvere in R2 i due sistemi lineari:
Va1 = xi Va2 = yi
Serena Morigi
Dipartimento di Matematica
Università di Bologna
Curve spline di interpolazione
˜ Problema:
Determinare una curva s(t)=(sx(t),sy(t))
di grado p tale che passi nell’ordine per
m+1 punti Pi=(xi,yi) i=0,..,m del piano
preassegnati.
˜ Algoritmo:
˜ Determinare i valori dei nodi di
interpolazione ti
˜ Risolvere le due funzioni spline di
interpolazione sx e sy :
sx(ti)=xi;
e
sy(ti)=yi;
Serena Morigi
Dipartimento di Matematica
Università di Bologna
Esempio:
Controllo di un robot 2D
˜ Le equazioni che regolano il
braccio sono le seguenti:
˜ posizione della fine del primo link
x1 = L1 cos(θ1 )
(x1,y1)
y1 = L1 sin(θ1 )
˜ posizione della fine del secondo
link (x2,y2) x2 = x1 + L2 cos(θ1 + θ 2 )
y 2 = y1 + L2 sin(θ1 + θ 2 )
˜ quindi, le coordinate (x,y) della
mano del robot sono date da
x2 = L1 cos(θ1 ) + L2 cos(θ1 + θ 2 )
y 2 = L1 sin(θ1 ) + L2 sin(θ1 + θ 2 )
Serena Morigi
Dipartimento di Matematica
Università di Bologna
Esempio:
Controllo di un robot 2D
˜ Queste due equazioni sono risolte per angoli in
funzione di x ed y in modo tale che si possa
determinare gli angoli necessari per spostare
la mano ad una posizione specificata da (x,y).
Le relazioni risultanti sono le seguenti:
R2 = x2 + y 2
cos(θ 2 ) =
R
2
2
− L1
y
α = arctan( )
x
Serena Morigi
− L2
2 L1L2
2
2
2
L1
R +
− L2
cos( β ) =
2 L1R
⎧α + β
θ1 = ⎨
⎩α − β
Dipartimento di Matematica
2
se θ 2 < 0
se θ 2 ≥ 0
Università di Bologna
Esempio:
Controllo di un robot 2D
Funzioni spline interpolano i valori di
θ1(ti) e θ2(ti) in corrispondenza
degli istanti ti prefissati;
θ1(ti) e θ2(ti) corrispondono agli
angoli che permettono di
posizionare il link2 del robot nelle
posizioni (x(ti),y(ti)) assegnate
agli istanti ti.
Serena Morigi
Dipartimento di Matematica
Università di Bologna