Interpolační křivky
‡
Formulace problému
„ dáno: n + 1 bodů v rovině
„
úkol: nalézt takovou křivku, která danými body prochází
y
fn
f2
f0
f1
x0
Počítačová geometrie
x1
x2
...
xn
x
Petra Surynková
Interpolační křivky
‡
‡
Hermitova interpolace
v bodech x0 , x1 , x2 ...xn známe funkční hodnoty f 0 , f1 , f 2 ... f n
a navíc hodnoty prvních derivací f 0′, f1′, f 2′... f n′
„
body x0 , x1 , x2 ...xn - jsou navzájem různé
„
hledáme polynom
H ( x) tak, aby platilo
H ( xi ) = fi , H ′( xi ) = fi ′, i = 0,..., n
„
celkem 2n + 2 podmínek
tedy stupně nejvýše 2n + 1
Počítačová geometrie
polynom s
2n + 2 koeficienty,
Petra Surynková
Interpolační křivky
‡
Hermitova interpolace
„
polynom budeme hledat v následujícím tvaru (obdoba
Lagrangeova interpolačního polynomu)
n
n
i =0
i =0
H 2 n+1 ( x) = ∑ hi ( x) f ( xi ) + ∑ hi ( x) f ′ ( xi ) , kde
hi ( x), hi ( x) jsou polynomy stupně nejvýše 2n + 1 s vlastnostmi
hi ( x j ) = δ ij =
hi′( x j ) = 0
Počítačová geometrie
0, i ≠ j
1, i = j
0, i ≠ j
hi′( x j ) = δ ij =
1, i = j
hi ( x j ) = 0
Petra Surynková
Interpolační křivky
‡
Hermitova interpolace
„ polynom hi ( x ) má kořeny x , x ,..., x , x ,...x , přičemž
0
1
i −1
i +1
n
všechny tyto kořeny jsou dvojnásobné
„
polynom
hi ( x) zapíšeme ve tvaru
hi ( x) = ( Ai x + Bi )( x − x0 ) ( x − x1 ) ... ( x − xi −1 ) ( x − xi +1 ) ... ( x − xn )
2
„
2
2
2
2
bez újmy na obecnosti můžeme psát
hi ( x) = ( ai x + bi )
( x − x0 ) ( x − x1 ) ...( x − xi−1 ) ( x − xi+1 ) ...( x − xn )
2
2
2
2
2
( xi − x0 ) ( xi − x1 ) ...( xi − xi−1 ) ( xi − xi+1 ) ...( xi − xn )
= ( ai x + bi ) li2 ( x)
2
2
2
2
2
=
li ( x) - Lagrangeovy polynomy
Počítačová geometrie
Petra Surynková
Interpolační křivky
‡
Hermitova interpolace
„ koeficienty ai , bi určíme z podmínek hi ( xi ) = 1, hi′ ( xi ) = 0
ai = −2li′ ( xi )
bi = 1 + 2 xi li′ ( xi )
„
celkem má polynom
hi ( x) tvar
hi ( x) = ⎣⎡1 − 2 ( x − xi ) li′ ( xi ) ⎤⎦ li2 ( x)
Počítačová geometrie
Petra Surynková
Interpolační křivky
‡
Hermitova interpolace
„ polynom hi ( x ) má kořeny x0 , x1 ,...xn , přičemž tyto kořeny jsou
dvojnásobné s výjimkou xi
„ polynom hi ( x ) zapíšeme ve tvaru
hi ( x) = Ci ( x − xi )( x − x0 ) ( x − x1 ) ...( x − xi −1 ) ( x − xi +1 ) ...( x − xn )
2
„
2
2
2
2
bez újmy na obecnosti můžeme psát
x − x0 ) ( x − x1 ) ... ( x − xi −1 ) ( x − xi +1 ) ... ( x − xn )
(
hi ( x) = ci ( x − xi )
2
2
2
2
2
−
−
−
−
−
x
x
x
x
...
x
x
x
x
...
x
x
( i 0 ) ( i 1 ) ( i i−1 ) ( i i+1 ) ( i n )
= ci ( x − xi ) li2 ( x)
2
2
2
2
2
=
li ( x) - Lagrangeovy polynomy
Počítačová geometrie
Petra Surynková
Interpolační křivky
‡
Hermitova interpolace
„ koeficient ci určíme z podmínky hi′ ( xi ) = 1
ci = 1
„
celkem má polynom
hi ( x) tvar
hi ( x) = ( x − xi ) li2 ( x)
„
Hermitův interpolační polynom můžeme vyjádřit ve tvaru
n
n
i =0
i =0
H 2 n+1 ( x) = ∑ ⎡⎣1 − 2 ( x − xi ) li′ ( xi ) ⎤⎦ li2 ( x) f ( xi ) + ∑ ( x − xi ) li2 ( x) f ′ ( xi )
Počítačová geometrie
Petra Surynková
Interpolační křivky
‡
Interpolace pomocí spline křivky
„
„
„
„
nevýhodou polynomiální interpolace – změna některého z uzlů
má vliv na celkový výsledný polynom
už při relativně nízkém počtu uzlů – polynomy značně oscilují
rozdělení daného intervalu na několik podintervalů, na každém z
nich konstruujeme obecně různý polynom – konstrukce po
částech polynomiální funkce
(lze použít i u parametricky popsaných křivek)
Počítačová geometrie
Petra Surynková
Interpolační křivky
‡
Interpolace pomocí spline křivky
„
„
v bodech x0 , x1 , x2 ...xn známe funkční hodnoty y0 , y1 , y2 ... yn
dělení intervalu a, b
a = x0 < x1 < x2 < ... < xn = b
„
označme délku i-tého intervalu
xi −1 , xi
hi = xi − xi −1
„
„
hledáme po částech polynomiální interpolant – S ( x )
- tzv. interpolační spline
na každém intervalu xi −1 , xi je S ( x ) polynom Si ( x )
Počítačová geometrie
Petra Surynková
Interpolační křivky
‡
Interpolace pomocí spline křivky
„ Spline stupně k - S ( x )
‡
splňuje interpolační podmínky
S ( xi ) = yi , i = 0,1...n
‡
na každém intervalu
xi −1 , xi
Si ( x) - je polynom k-tého stupně
‡
S ( x) má spojité derivace až do řádu (k-1)
Počítačová geometrie
Petra Surynková
Interpolační křivky
‡
Interpolace pomocí spline křivky
„
Lineární interpolační spline
‡
každé dva sousední body jsou spojeny úsečkou
yi − yi −1
Si ( x) = yi −1 +
( x − xi−1 ) =
xi − xi −1
yi
Si ( x )
yi − yi −1
yi −1 +
( x − xi−1 )
hi
yi −1
xi −1
Počítačová geometrie
xi
Petra Surynková
Interpolační křivky
‡
Interpolace pomocí spline křivky
„ Kubický interpolační spline S ( x )
‡
splňuje interpolační podmínky
S ( xi ) = yi , i = 0,1...n
‡
na každém intervalu
xi −1 , xi
Si ( x) - je polynom třetího stupně
‡
platí
Si ( xi ) = Si +1 ( xi ), i = 1, 2,..., n − 1
Si′( xi ) = Si′+1 ( xi ), i = 1, 2,..., n − 1
Si′′( xi ) = Si′′+1 ( xi ), i = 1, 2,..., n − 1
Počítačová geometrie
Petra Surynková
Interpolační křivky
‡
Interpolace pomocí spline křivky
„ Kubický interpolační spline S ( x )
‡
dva volné parametry – přidání podmínek, nejčastěji:
S ′′ ( x0 ) = S ′′ ( xn ) = 0
přirozený kubický spline
Počítačová geometrie
Petra Surynková
Download

přednáška4 (.pdf)