Interpolációs eljárások Szakdolgozat Írta: Baloghné Koterla Orsolya Matematika BSc szak - elemző szakirány
Témavezető: Svantnerné Sebestyén Gabriella doktorandusz Alkalmazott Analízis és Számításmatematikai Tanszék Eötvös Loránd Tudományegyetem, Természettudományi Kar
Budapest 2017
Tartalomjegyzék 1. Bevezetés
3
2. Motiváció
3
3. Polinom interpoláció
4
4. Lagrange interpoláció
6
5. Newton interpoláció
8
6. Hermite interpoláció
11
7. Spline interpoláció 7.1. Szakaszonként lineáris spline interpoláció . . . . . . . . . . . . . . . 7.2. Harmadfokú spline interpoláció . . . . . . . . . . . . . . . . . . . .
12 13 15
8. Interpolációs hibabecslés 8.1. Lagrange és Newton interpolációs polinom hibabecslése . . . . . . . 8.2. Az Hermite interpolációs polinom hibabecslése . . . . . . . . . . . . 8.3. Spline interpolációs polinom hibabecslése . . . . . . . . . . . . . . .
20 20 22 23
9. Matematikai példák 9.1. Lagrange interpolációs polinom . . . . . . . . . . 9.2. Newton interpolációs polinom . . . . . . . . . . . 9.3. Hermite interpolációs polinom . . . . . . . . . . . 9.3.1. Hermite polinom előállítása - 1. módszer . 9.3.2. Hermite polinom előállítása - 2. módszer . 9.4. Spline interpolációs polinom . . . . . . . . . . . . 9.4.1. Spline interpolációs polinom előállítása - 1. 9.4.2. Spline interpolációs polinom előállítása - 2. 9.5. Példák MATLAB programmal . . . . . . . . . . .
23 23 25 26 27 27 29 29 30 31
10.Összegzés
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . módszer módszer . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
35
2
1. Bevezetés A szakdolgozatom célja, hogy az olvasó átfogó képet kapjon a különböző interpolációs módszerekről. Az interpoláció egy matematikai közelítő módszer, mely során meghatározott pontokban rendelkezésünkre álló függvényértékekre szeretnénk egy görbét illeszteni. 1. Definíció. Legyenek adottak az x0 < x1 < . . . < xn különböző alappontok és az yi = f (xi ) (i = 0, . . . , n) függvényértékek. Határozzuk meg azt a g : R → R, legfeljebb n-edfokú függvényt, amelyre teljesül a g = f (xi )
(1)
interpolációs feltétel. Többféle interpolációs módszert ismerünk. Ezek csoportosítása a közelítési függvény típusa szerint a következő: • Polinomiális: Ebben az esetben a közelítő függvények polinomok. Tehát az interpoláció segítségével az adott n+1 pontra egy legfeljebb n-ed fokú polinom illeszthető. • Trigonometrikus: A közelítő függvény ez esetben egy trigonometrikus függvény. Ez a típus a Fourier-módszer alkalmazásakor kerül előtérbe. Egy másik csoportosítás szerint: • Lokális: Az interpolációs közelítőfüggvényt csak egy adott x pont közelében lévő ponthalmazra alkalmazzuk. • Globális: Ennél a módszernél a rendelkezésünkre álló összes pontot felhasználjuk. Ebben az esetben az adott pontokat egyetlen polinom segítségével szeretnénk leírni.
2. Motiváció Az interpoláció a mindennapi életben is gyakran használt eljárás. Például abban az esetben, amikor egy mérési sorozat mintavételezéssel előállított véges számú mintája ismert, de szeretnénk az egyes minták közötti értékekről is közelítő eredményeket kapni. • A kőolajkutatásban elengedhetetlen szerepe van az interpolációnak. Egy olajmezőn lefúrunk n helyen, és az adott hely-érték párokkal megpróbáljuk megbecsülni, hogy milyen mélyen található az olaj az egyes részeken. Az olajfúrótornyot arra a helyre építik, ahol a legközelebb van a felszínhez a 3
kőolaj. Mivel a fúrások költségesek, ezért minél kevesebb fúrásból kell megkeresni ezt a helyet. Tekintsük a gyakorlatból eredő numerikus feladatot a kőolaj esetében. Az u = u(x, y, z) függvénnyel leírható a kőolaj nyomása a földalatti rétegekben a ∂u ∂ ∂u ∂ ∂u ∂ a + a + a =0 (2) ∂x ∂x ∂y ∂y ∂z ∂z differenciálegyenlet segítségével. Térben próbáljuk megoldani a feladatot, ezért a differenciálegyenlet három változós. Az u függvény meghatározásához szükségünk van bizonyos mellékfeltételekre. Az a a kőolajat rejtő kőzet, továbbá a kőolaj tulajdonságaitól függ, például a sűrűségétől. Legyen az a = a(x, y, z) együttható ismert, pozitív és korlátos. Az a értékét a következők befolyásolják: – permeabilitás, – porozitás, – a kőolaj viszkozitása, – a kőolaj sűrűsége. Ha több fúrást végzünk (xk , yk ) helyeken és sok z értékre megvizsgáljuk az eredményt, akkor meg tudjuk állapítani az a értékét. Mivel a fúrások költségesek, ezért kevés adattal kell kiszámítanunk az a értékét a háromdimenziós tartományunkban. • Az autó karosszériájának tervezése is egy interpolációs feladat. Az (xk , yk , zk ) pontok adottak. Ezek a pontok jelölik a karosszéria egyes helyeit. A karosszériának több kritériumnak is eleget kell tennie. Nemcsak a légellenállásnak kell megfelelnie, de nem távolodhat el túlságosan a pontok által meghatározott konvex lineáris buroktól sem. • A GPS is ilyen elven működik. A GPS műholdak helyének, sebességének, vagy gyorsulásának adatait interpolációs feladattal becsüljük meg.
3. Polinom interpoláció Az alábbi definíciókat és állításokat fogjuk felhasználni az interpolációs módszerek vizsgálata során. 2. Definíció. Egyismeretlenes polinomnak nevezzük a pn (x) = a0 + a1 x + a2 x2 + . . . + an xn
(3)
kifejezést, ahol n ≥ 0 egész és a0 , . . . , an komplex számok. Az x ismeretlen. Az aj xj a polinom egy tagja, az xj együtthatója aj . Az a0 = a0 x0 a konstans tag. 4
3. Definíció. A p = an xn + an−1 xn−1 + an−2 xn−2 + . . . + a2 x2 + a1 x + a0 ,
(4)
(ahol a 6= 0) kifejezést az x határozatlan n-ed fokú polinomjának nevezzük. Az a0 , a1 , a2 , . . . , an a polinom együtthatói. 4. Megjegyzés. Horner1 -sémát alkalmazunk, ha egy polinomnak meg akarjuk határozni a gyökeit. Ez egy rendezési elven alapuló eljárás. Legyen a polinom a következő: p = an xn + an−1 xn−1 + . . . + a1 x + a0 . (5) Az x helyébe egy c értéket helyettesítünk, a kapott számot a c helyen vett helyettesítési értéknek nevezzük és p(c)-vel jelöljük. Ha az egyenletbe c = 0-t helyettesítünk, akkor p(0) = a0
(6)
az eredmény, mely a polinom állandó tagja. • Először meg kell határoznunk a lehetséges racionális gyököket. Az egyenletet an xn + an−1 xn−1 + . . . + a1 x + a0 = 0
(7)
alakra rendezzük. • A táblázat kitöltésének a folyamata a következő: – A táblázat első sorába a polinom együtthatói kerülnek. – A második sorba an alá ismét an -et írunk, ez az első kiszámított értékünk. – Az utolsó kiszámított értéket megszorozzuk c-vel és hozzáadjuk a következő oszlop első sorában lévő együtthatót. A kapott értéket ebbe az oszlopba írjuk. – Az eljárást folytatva az a0 alatt a p(c) helyettesítési értéket kapjuk eredményül.
c
an an
an−1 an c + an−1
an−2 (an c + an−1 )c + an−2
... ...
a1 ...
a0 p(c)
1. táblázat. Horner-féle elrendezés
• Azokat a c értékeket, amelyekre a polinom helyettesítési értéke 0, a polinom gyökeinek nevezzük. 1
William Georg Horner (1786-1837) angol matematikus 1823-ban publikálta számításait.
5
5. Definíció. A Pn az n-ed fokú polinomok halmaza. 6. Tétel. Adott n+1 különböző pont az [a,b] intervallumon. Legyenek ezek x0 , . . . , xn . Ezenkívül adott n + 1 különböző valós érték: y0 , . . . , yn . Ekkor pontosan egy olyan pn ∈ Pn polinom létezik, amelyre teljesül a pn (xj ) = yj , j = 0, . . . , n
(8)
feltétel. Bizonyítás. A keresett polinomot nevezzük Ln (x)-nek, melyre a következő n P ak xk . Ekkor az interpolációs feltétel egyenletet tudjuk felírni: Ln (x) = k=0
teljesüléséhez az alábbi egyenlőségeknek kell teljesülnie: Ln (xi ) =
n X
ak xki = yi (i = 0, . . . , n).
(9)
k=0
Ennek a lineáris egyenletrendszernek az együttható mátrixa egy Vandermonde-mátrix. Az interpoláció definíciója szerint tudjuk, hogy az xi értékeink különböznek, ezért a mátrix determinánsa nem lehet nulla. Következtetésképpen a polinom együtthatói egyértelműen meghatározottak. 1. Állítás. Az (1)-es feladatnak legfeljebb egy megoldása létezik (unicitás). Bizonyítás. Indirekt bizonyítjuk ezt az állítást. Tegyük fel, hogy p, h ∈ Pn , p 6= h és mindkettőre teljesül az (1)-es feltétel: g(xi ) = yi , h(xi ) = yi , p(x) := (g(x) − h(x)) ∈ Pn , ekkor p(xi ) = 0, i = 0, 1, . . . , n. Ez ellentmond az algebra alaptételének, mert n + 1 gyöke van a p polinomnak.
4. Lagrange interpoláció Az első módszer, melyet vizsgálunk Lagrange2 nevéhez fűződik. A Lagrange interpolációban egy új alappont megismerését követően az eljárást az elejétől meg kell ismételni. Emiatt új alappontok bevezetése költséges eljárás. 2
Joseph-Loius Lagrange (1736-1813) francia matematikus 1795-ben publikálta a módszert.
6
7. Definíció. Adott alappontok esetén az lk =
(x − x0 ) . . . (x − xk−1 )(x − xk+1 ) . . . (x − xn ) (xk − x0 ) . . . (xk − xk−1 )(xk − xk+1 ) . . . (xk − xn )
(10)
(k = 0, . . . , n) polinomot a k-adik (alapponthoz tartozó) Lagrange alappolinomnak nevezzük. 8. Definíció. Az Ln ∈ Pn polinomot Lagrange interpolációs polinomnak nevezzük, ha n X Ln (x) = yk lk . (11) k=0
A polinom felírható a következőképpen: pn = Ln (x) =
n X
yk lk ,
(12)
k=0
ahol lk az alábbi kifejezést jelöli: lk (x) :=
n Y
(x − xi ) , (x k − xi ) i=0,i6=k
(13)
ahol k = 0, . . . , n. Ebben az esetben Ln -t Lagrange-féle interpolációs polinomnak nevezzük. 2. Állítás. A Lagrange-féle interpolációs polinomnak pontosan egy megoldása van Pn -ben. Bizonyítás. A bizonyításban jelöljük φk -val az alábbi kifejezést: n Y (x − xi ) φˆk (x) φk (x) := = ˆ φk (xj ) i=0,i6=k (xk − xi ) = 0, ha j 6= k φk (xj ) = = 1, ha j = k
φk (xj ) ∈ Pn
(14) (15) (16)
j, k = 0, . . . , n. Tekintsük a Lagrange interpolációs polinomot: Ln (x) :=
n X
yk φk (x).
(17)
k=0
Legyen pn = Ln (x), 7
(18)
mely egy n-ed fokú polinom. Az Ln (x) polinom eleget tesz a (8)-as feltételnek. Az unicitást a következőképpen bizonyítjuk: legyenek Ln1 és Ln2 n-ed fokú, különböző polinomok és elégítsék ki a (8)-as feltételt. Jelöljük Ln -nel a polinomok különbségét: Ln := Ln1 − Ln2 .
(19)
Mivel mindkét polinom teljesíti a feltételt, ezért a különbségük minden alappontban 0, azaz: Ln (xi ) = 0, i = 0, . . . , n, (20) Ln (xi )-nek n + 1 gyöke van. Tegyük fel, hogy n ∈ N∪0. Ekkor minden Pn -beli polinomnak legfeljebb n gyöke van - vagy azonosan nulla. Ebben az esetben pedig Ln1 = Ln2 .
(21)
5. Newton interpoláció Ebben a fejezetben a Newton3 interpolációt vizsgáljuk. Legyenek (xi , fi ), i = 0, . . . , n alappontok. Tekintsük az alappontokat és a rájuk illeszkedő interpolációs polinomot: Ln ∈ Pn . Továbbá legyen Ln−1 (x) ∈ Pn−1 az (xi , fi ) i = 0, 1, . . . , n − 1 pontokra illesztett interpolációs polinom. Tekintsük a következő levezetést: Ln − Ln−1 ∈ Pn , (Ln − Ln−1 )(x0 ) = 0, (Ln − Ln−1 )(x1 ) = 0, ... (Ln − Ln−1 )(xn−1 ) = 0. Ekkor kapjuk ezt az összegzést: Ln (x) − Ln−1 (x) = bn (x − x0 )(x − x1 ) . . . (x − xn−1 ), melyhez meghatározzuk a bn együtthatót. • Az egyenlet jobb oldalán az xn -en együtthatója lesz a bn . 3
Sir Isaac Newton (1642-1727) 1669-ben publikálta matematikai kutatásait.
8
(22)
• A bal oldali Ln és Ln−1 a következőképpen írható le: Y n n X x − xj Ln = fi , xi − xj i=0 j=0,j6=i n−1 n−1 X Y x − xj Ln−1 = fi . x − x i j i=0 j=0,j6=i
(23)
(24)
Ebből következik, hogy az xn együtthatója: n X
fi
i=0
! 1 . xi − xj j=0,j6=i n Y
(25)
Egy pontra illesztett interpolációs polinom: L0 (x) Nn (x) := Ln (x). Tekintsük a polinom előállítását.
=
f0 . Továbbá,
• Legyen b0 = f0 , ω0 (x) = 1 → N0 (x) = b0 ω0 (x). • Legyen Nn (x) = Nn−1 (x) + bn ωn (x), ahol N0 (x) = f0 és a Y n n X 1 bn = fi . x − x i j i=0 j=0,j6=i
(26)
Általános esetben a következőképpen írjuk le a Newton interpolációs polinomot: Nn (x) = Nn−1 (x) + bn ωn (x).
(27)
Egy n-ed fokú Newton interpolációs polinom előállítása a következő: • Ha n = 0 az egyenlet a következőképpen néz ki: N0 (x) = b0 ω0 (x), ahol b0 = fo , és ω0 (x) = 1.
(28) (29)
• A n = 1 esetben az egyenlet bővül egy taggal: N1 (x) = N0 (x) + b1 ω1 (x) = b0 ω0 (x) + b1 ω1 (x) =
1 X
bi ωi (x).
(30)
i=0
• Általános esetben a polinom felírása a következő: Nn (x) =
n X
bi ωi (x), i = 0, 1, . . . , n, azaz,
i=0
Nn (x) = Nn−1 (x) + bn ωn (x) ahol, ωn (x) =
n−1 Y j=0
9
(x − xj ).
(31)
Példa a kifejtésre: • Tekintsük először n = 1 esetben: N1 (x) = b0 ω0 (x) + b1 ω1 (x), 1 1 f1 − f0 b1 = f 0 · + f1 · = , x0 − x1 x1 − x0 x1 − x0 f1 − f0 N1 (x) = f0 · 1 + (x − x0 ). x1 − x0
(32)
• A n = 2 esetben nézzük az interpolációs polinomot: N2 (x) = b0 ω0 (x) + b1 ω1 (x) + b2 ω2 (x), ahol a ! ! 2 2 2 X Y Y 1 1 b2 = fi = f0 c + (x (x i − xj ) 0 − xj ) i=0 j=1 j=0,j6=i ! ! 1 2 Y Y 1 1 + f2 = + f1 (x1 − xj ) (x2 − xj ) j=0 j=0,j6=1
(33)
1 1 + f1 · + (x0 − x1 )(x0 − x2 ) (x1 − x0 )(x1 − x2 ) 1 . + f2 · (x2 − x0 )(x2 − x1 ) = f0 ·
– Ezt a kifejezést átalakítjuk a következőképpen: # " 1 f2 − f1 f1 − f0 . b2 = − x2 − x0 x2 − x1 x1 − x0 | {z } | {z } [x1 x2 ]f
(34)
[x0 x1 ]f
A (34)-es egyenletben megjelölt tagokat osztott differenciának nevezzük. Az osztott differencia segítségével rövidebben leírható a Newton interpolációs polinom. 9. Definíció. Osztott differenciának nevezzük az [x0 x1 . . . xn ]f kifejezést, ha [x1 x2 . . . xn ]f − [x0 x1 . . . xn−1 ]f , ahol xn − x0 b0 = [x0 ]f , b1 = [x0 x1 ]f , b2 = [x0 x1 x2 ]f , . . . az együtthatók. [x0 x1 . . . xn ]f :=
10
(35) (36)
x0
[x0 ]f & [x0 x1 ]f %
x1
&
[x1 ]f
[x0 x1 x2 ]f &
%
& ···
[x1 x2 ]f % x2
[x2 ]f
.. .
.. .
& .. .
[x0 x1 . . . xn ]f
.. .
... % %
···
xn−1 [xn−1 ]f &
% [xn−1 xn ]f
% xn
[xn ]f
Az előbbi ábrán látható, hogy az egyes osztott differenciákat hogyan lehet könnyen kiszámolni. A nyilak mutatják, hogy melyik osztott differenciákból melyik osztott differencia számolható.
6. Hermite interpoláció A következő eljárás Hermite4 interpolációnak nevezzük, mely abban különbözik az előzőektől, hogy itt ismert az alapponthoz tartozó egy vagy több derivált érték is a függvényértéken kívül. 10. Definíció. Legyenek x0 , x1 , . . . , xn adott, különböző pontok. Az xk (k = 0, 1, . . . , n) (N ) (0) (1) pontban legyen adott Nk −1 darab számérték: fk , fk , . . . , fk k−1 , ezek a függvény derivált értékei. Egy olyan Hn (x) ∈ Pn polinomot keresünk, melyre teljesülnek a következők: Hn(i) (xk ) = f (i) (xk ), i = 0, 1, . . . , Nk − 1, k = 0, 1, . . . , n
(37)
A Hn ∈ Pn polinomot Hermite-féle interpolációs polinomnak nevezzük. 11. Megjegyzés. Speciális eset, ha minden pontban a függvényértéken kívül csak az első deriváltak adottak, ekkor Hermite-Fejér interpolációról beszélünk. 4
Charles Hermite (1822-1901) francia matematikus.
11
Feladat: Olyan polinomot keresni, mely eleget tesz a kritériumoknak, vagyis az ismert pontokban, megegyeznek a függvényértékek és a derivált értékek is. x0 x1 .. .
f (x0 ) f (x1 ) .. .
f 0 (x0 ) f 0 (x1 ) .. .
... ... .. .
f N0 −1 (x0 ) f N1 −1 (x1 ) .. .
xk .. .
f (xk ) .. .
f 0 (xk ) .. .
... .. .
f Nk −1 (xk ) .. .
xn
f (xn )
f 0 (xn )
...
f Nn −1 (xn )
2. táblázat. Hermite-féle interpoláció
12. Megjegyzés. Speciális eset, ha N0 = N1 = . . . = Nn = 1, ugyanis ez a Lagrange-féle interpolációt fejezi ki. 3. Állítás. Létezik egyértelműen ilyen Hn ∈ Pn polinom. Bizonyítás. A Hn (x) polinomot a következő alakban keressük: Hn = a0 + a1 x + . . . + an xn .
(38)
A (38)-as egyenletben szereplő a0 , a1 , . . . , an n + 1 darab együttható egyértelműen meghatározható. Ha a (38)-ast behelyettesítjük a (37)-be, akkor kapunk egy lineáris, algebrai egyenletrendszert. Ha a homogén feladatnak a megoldása az alábbi egyenlet: Hn(i) (xn ) = 0, i = 0, 1, . . . , Nk − 1, k = 0, 1, . . . , n, (39) akkor a Hn polinom megoldása egyértelmű. A (39)-es feladatnak az a0 = a1 = . . . = an = 0 a megoldása. Továbbá az x = xk pont a lineáris algebrai egyenletrendszer megoldása, melynek multiplicitása Nk . Tehát az x0 , x1 , . . . , xn pontokban a multiplicitást figyelembe véve, gyökeinek száma n + 1: N0 + N1 + . . . + Nn = n + 1,
(40)
azaz a Hn ∈ Pn polinomnak legalább n + 1 gyöke van, de ez csak abban az esetben lehetséges, ha Hn (x) = 0.
7. Spline interpoláció A Lagrange, Newton, Hermite interpoláció után a szakaszonkénti interpoláció tárgyalása következik. A szakaszonkénti interpoláció esetén minden [xi , xi+1 ] szakaszra külön interpolációs polinomot adunk meg. A közbülső alappontokban a függvényértékeknek és a megfelelő deriváltaknak is meg kell egyezniük, biztosítva ezzel a függvény simaságát. 12
13. Definíció. Legyen adott az [a, b] intervallum valamely a = x0 < . . . < xn = b
(41)
s(x) : [a, b] ⊂ R → R
(42)
felosztása. Legyen az az alábbi polinom: s0 (x), s1 (x), s(x) = .. . s (x), n−1
x ∈ [x0 , x1 ), x ∈ [x1 , x2 ), .. . x ∈ [xn−1 , xn ),
ahol, ∀si (x) foka legfeljebb n. Az s(x) függvényt spline interpolációs polinomnak nevezzük.
7.1. Szakaszonként lineáris spline interpoláció A legegyszerűbb eset a szakaszonként lineáris spline interpoláció. Ebben az esetben az interpolációban szakaszonként egy egyenessel kötünk össze két egymás mellett lévő pontot.
1. ábra. Szakaszonkénti lineáris spline interpoláció
A (1)-es ábrán látható egy öt pontból előállított szakaszonkénti lineáris interpoláció.
13
Tekintsük az (xk , xk+1 ) szakaszt. A lineáris interpoláció minden intervallumában a következő interpolációs formulát alkalmazza: f = Afk + Bfk+1 ,
(43)
ahol, xk+1 − x és xk+1 − xk x − xk . B := 1 − A = xk+1 − xk A :=
(44) (45)
A következő két ábrán látható az eredeti függvény és a szakaszonkénti lineáris spline függvény.
2. ábra. Az eredeti függvény, melyen meg vannak jelölve az alappontok értékei 1 sin(x) függvény látható a [−4; 4] intervallumon. 1 + x2 Az xk alappontok a következők: x0 = −4; x1 = −3; x2 = −2; x3 = −1; x4 = 0; x5 = 1; x6 = 2; x7 = 3; x8 = 4. A (2)-es ábrán az f (x) =
14
3. ábra. Szakaszonkénti lineáris spline interpoláció bemutatása (2)-es ábrán keresztül
Látható, hogy a lineáris spline jól közelíti a függvényt az egyes intervallumokon, kivéve a [−1; 1]-es intervallumot. Itt a függvény nem képes az eredeti görbületre illeszkedni.
7.2. Harmadfokú spline interpoláció A spline-ok közül a leggyakrabban használt az úgynevezett "cubic spline", vagyis a harmadfokú spline polinom. A harmadfokú spline interpoláció minden intervallumra egy maximum harmadfokú polinomot illeszt. Szükséges feltétel, hogy kétszer folytonosan deriválható legyen a függvény. Legyen s(x) a következő függvény: s0 (x), x ∈ [x0 , x1 ), s1 (x), x ∈ [x1 , x2 ), s(x) = .. .. . . s (x), x ∈ [x , x ), n−1
n−1
ahol, ∀si (x) foka maximum 3.
15
n
Az alappontok és az értékeik a következők: s(xi ) = yi ,
(46)
ahol 0 ≤ i ≤ n. Az interpolációs feltételünket, a (46)-os egyenletet kiegészítjük a következő kritériummal: si−1 (xi ) = yi = si (xi ),
(47)
ahol 1 ≤ i ≤ n − 1. Ezzel a kiegészítéssel biztosított az interpolációs polinom folytonossága.
4. ábra. Harmadfokú spline interpoláció
Az (4)-es ábrán láthatunk egy harmadfokú spline polinomot. Elvárjuk, hogy deriválható legyen kétszer a polinom: s0i (xi+1 ) = s0i+1 (xi+1 ), 0 ≤ i ≤ n − 2, s00i (xi+1 ) = s00i+1 (xi+1 ), 0 ≤ i ≤ n − 2.
(48) (49)
Tudjuk, hogy egyértelmű megoldáshoz szükséges megfelelő számú feltétel megadása. Összesen n darab részintervallumunk van, melyekhez tartozik egy-egy legfeljebb harmadfokú polinom. Minden polinom 4 együtthatóval rendelkezik, azaz 4n együtthatót kell meghatároznunk. A folytonossági feltétel miatt az si (xi ) és si+1 (xi+1 ) szakaszokon az alappontok értékeinek meg kell egyezni, ezáltal 2n egyenletet kapunk. Az első és 16
második derivált egyezése miatti feltétel pedig további 2(n − 1) = 2n − 2 egyenletet állít elő. Azaz rendelkezésünkre áll összesen 4n − 2 egyenlet és 4n ismeretlen, amiből következik, hogy a szabadsági fok 2. Emiatt az interpolációs polinomot többféleképpen is elő tudjuk állítani. Ha az alappontok nincsenek egyenlő távolságra a felosztás nem ekvidisztáns. A hi jelölje az alappontok közötti felosztást: hi = xi+1 − xi .
(50)
Ezenfelül a második deriváltat jelölje: zi = s00 (xi ).
(51)
A harmadfokú interpolációs polinom második deriváltja egy lineáris függvény, mely a következő: s00i (x) =
x − xi+1 x − xi zi+1 − zi . hi hi
(52)
Ha az (52)-es egyenlet mindkét oldalát integráljuk az alábbi polinomot kapjuk: 1 zi+1 1 zi s0i (x) = (x − xi )2 − (x − xi+1 )2 + c˜, 2 hi 2 hi ahol c˜ egy konstanst jelöl. Most integráljuk még egyszer ezt a függvényt: si (x) =
zi+1 zi (x − xi )3 + (xi+1 − x)3 + C(x − xi ) + D(xi+1 − x). 6hi 6hi
(53)
(54)
Az interpolációs feltétel miatt si (xi ) = yi . Ezt behelyettesítve az (54)-es egyenletbe, az alábbi polinomot kapjuk: yi =
zi 3 h + Dhi , 6hi i
(55)
zi hi yi − . hi 6
(56)
ahol D=
Hasonlóképpen si+1 (xi+1 ) = yi+1 , ami a következőt jelenti: yi+1 =
zi+1 3 h + Chi , 6hi i
(57)
ahol C=
yi+1 zi+1 hi − . hi 6
17
(58)
Ezáltal vissza tudjuk helyettesíteni a C és D értékeket a (54)-es egyenletbe: ! ! z z y z h y z h i+1 i i+1 i+1 i i i i (x−xi )3 + (xi+1 −x)3 + − (x−xi )+ − (xi+1 −x). s00i (x) = 6hi 6hi hi 6 hi 6 (59) Most pedig határozzuk meg a második deriváltakat. Tekintsük a z1 , . . . , zn−1 egyenleteket. A derivált értékek az alappontokban a következők: si (xi ) = si−1 (xi ), zi+1 zi yi+1 (x − xi )2 − (xi+1 − x)2 + + 2hi 2hi hi zi+1 yi+1 zi+1 yi zi hi + (x − xi )2 + − − + , 2hi hi 6 hi 6
s0i (x) =
(60)
(61)
és zi+1 zi−1 yi (x − xi−1 )2 − (xi − x)2 + + 2hi−1 2hi−1 hi−1 yi+1 zi yi−1 zi−1 hi−1 zi (x − xi )2 + − − + . + 2hi−1 hi 6 hi−1 6
s0i−1 (x) =
(62)
Az x helyére xi -t helyettesítve: yi zi hi zi 2 yi+1 zi+1 hi − + = h + − 2hi hi 6 hi 6 hi hi yi yi+1 = − zi − zi+1 − + , 3 6 hi hi
s0i (xi ) = −
(63)
és zi yi zi yi−1 zi−1 hi−1 (hi−1 )2 + − hi−1 − + = 2hi−1 hi−1 6 hi−1 6 hi−1 hi−1 yi−1 yi zi−1 + zi − + . = 6 3 hi−1 hi−1
s0i−1 (xi ) =
(64)
Ebben az esetben a következő egyenlőség áll fenn: hi−1 hi + hi−1 hi 1 1 zi−1 + zi + zi+1 = (yi+1 − yi ) − (yi − yi−1 ). 6 3 6 hi hi−1 18
(65)
Az n+1 darab alappontra n−1 darab egyenletet tudunk felírni, ezáltal a polinom szabadsági foka 2 lesz. Emiatt különböző módon folytathatjuk a megoldást. Többféle megoldási módszer létezik. A legelterjedtebb alkalmazást most részletesebben is megismerhetjük. Legyen a peremfeltétel a következő: z0 = zn = 0.
(66)
Ezt az eljárást természetes harmadfokú spline interpolációnak nevezzük. A kapott egyenletrendszer mátrix alakban felírva a következő: y2 − y1 y1 − y0 h0 + h1 h1 z1 − h1 h0 3 6 h1 y3 − y2 y2 − y1 h + h h 1 2 2 z2 − 6 h h 2 1 3 6 . .. .. .. . = . . . . . ... y − y y − y n−2 n−3 n−2 n−1 hn−3 + hn−2 hn−2 hn−3 − zn−2 hn−2 hn−3 6 3 6 yn − yn−1 yn−1 − yn−2 hn−2 + hn−1 hn−2 − zn−1 hn−1 hn−2 6 3 Az együttható mátrix ezekkel a tulajdonságokkal rendelkezik: • szimmetrikus, • tridiagonlális, • szigorúan diagonálisan domináns. 14. Definíció. Egy A ∈ Rn×n mátrix szigorúan diagonálisan domináns, ha teljesül rá a következő kritérium: |aii | >
n X
|aij |, ahol i = 1, . . . , n, j = 1, . . . , n.
(67)
j=1,j6=i
Vagyis a főátlóban lévő értékek abszolút értéke nagyobb, mint a sorában szereplő elemek abszolút értékének összege. 1. Következmény. A invertálható.
mátrix
determinánsa
nem
egyenlő
nullával,
ezért
Tekintsük a továbbiakban azt az esetet, amikor az alappontok egyenlő távolságra helyezkednek el egymástól: hi = h (68) minden i értékre.
19
Ekkor a mátrix felírható a következő alakban: z1 2 1 y2 − 2y1 + y0 h h 3 6 1 2 1 h z h h 2 y3 − 2y2 + y1 6 3 6 . .. .. .. . . . . . .. = . . 2 1 1 y − 2y + y n−1 n−2 n−3 h h h zn−2 6 3 6 1 2 yn − 2yn−1 + yn−2 h h zn−1 6 3
8. Interpolációs hibabecslés Az interpoláció során fellépő hibát szeretnénk becsülni. Fontos, hogy ne csak azt vizsgáljuk, hogy mennyire illeszkedik a függvény az alappontokra, hanem azt is meg kell figyelnünk, hogy adott esetben mennyire tér el az eredeti függvénytől az interpolációs polinom. Ebben a fejezetben az eddig tárgyalt interpolációs polinomok hibabecslését tárgyaljuk.
8.1. Lagrange és Newton interpolációs polinom hibabecslése Legyenek (xi , fi ) i = 0, 1, . . . , n adottak és pn (x) ∈ Pn az interpolációs polinom. 4. Állítás. Tegyük fel, hogy f : [a, b] → R ismeretlen függvényre f ∈ C n+1 [a, b]. Ekkor ∀˜ x ∈ [a, b] ponthoz ∃ξ = ξ(˜ x) ∈ [a, b] szám, amelyre: f (˜ x) − pn (˜ x) =
f (n+1) (ξ) ωn+1 (˜ x). (n + 1)!
(69)
Bizonyítás. Tegyük fel, hogy x˜ 6= xi , i = 0, 1, . . . , n. Legyen ϕ(x) := f (x) − pn (x) − K · ωn+1 (x), ahol K egy egyelőre tetszőleges állandó. Válasszuk meg K értékét úgy, hogy ϕ(˜ x) = 0 teljesüljön: f (˜ x) − pn (˜ x) = K · ωn+1 (˜ x).
(70)
Tudjuk, hogy ωn+1 (˜ x) 6= 0. Emiatt a K értékét a következőképpen tudjuk kifejezni: K=
f (˜ x) − pn (˜ x) . ωn+1 (˜ x)
(71)
Ezen K értékekkel meghatározott ϕ függvénynek gyökei lesznek a következők. 20
• Ha x = x0 , akkor a következő egyenletet írhatjuk fel: ϕ(x0 ) = f (x0 ) − pn (x0 ) − K · ωn+1 (x0 ) = = f0 − f0 − K(x0 − x0 )(x0 − x1 ) . . . (x0 − xn ) = 0.
(72)
• Az x = x1 esetben az alábbi egyenlet teljesül: ϕ(x1 ) = f1 − f1 − K · ωn+1 (x1 ) = 0.
(73)
• Ha x = xn -nel, akkor ϕ(xn ) = 0.
(74)
A Rolle-tétel alapján: • ϕ függvény deriváltja az n + 1 darab pontban 0, • ϕ00 n darab pontban 0. • Majd ezt folytatva ϕ(n+1) -ig, ami legalább egy pontban 0. Legyen ξ egy olyan pont, melyre teljesülnek a feltételek: ∃ξ : ϕ(n+1) (ξ) = 0.
(75)
Legyen x˜ ∈ [a, b] tetszőleges és x˜ = xi , ekkor ϕ a következő kifejezéssel lesz egyenlő: ϕ(x) := f (˜ x) − pn (˜ x) − K · ωn+1 (x).
(76)
f (˜ x) − pn (˜ x) ⇒ ∃ξ ∈ (a, b) : ϕ(n+1) (ξ) = 0. ωn+1 (x)
(77)
Legyen K a következő: K :=
Ebben az esetben a ϕ n + 1-dik deriváltjának az értéke a ξ helyen egyenlő nullával: (n+1)
ϕ(n+1) (x) = f (n+1) − p(n+1) (x) − K · ωn+1 (x), n
(78)
ϕ(n+1) (ξ) = f (n+1) (ξ) − K · ωn+1 ! = 0.
(79)
Ennek alapján már meg tudjuk határozni K értékét, mely a következő: K=
f (n+1) (ξ) f (˜ x) − pn (˜ x) = . (n + 1)! ωn+1 (˜ x)
(80)
Ezt a hibabecslést következőképpen tudjuk pontosítani, jelölje: h := max (xi+1 − xi ). 0≤i≤n−1
21
(81)
15. Lemma. Az ωn+1 (x) hiba nagyságát a következőképpen tudjuk becsülni: |ωn+1 (x)| ≤
1 · n! · hn+1 . 4
(82)
2. Következmény. A Lagrange és Newton interpoláció n + 1-ed rendű (= az alappontok számával). Ez azt jelenti, hogy ha f ∈ Pn , akkor az interpoláció pontos, azaz pn (x) = f (x), ∀hk (x) ∈ Pk , k = 0, 1, . . . , n. Jelölje a függvény hibáját en . 16. Definíció. Ha f ∈ C n+1 [a, b], akkor az en (x)-et, en (x) := f (x) − pn (x)
(83)
hibafüggvénynek nevezzük. A hibafüggvényt végtelen normával is becsülhetjük: ||f (n+1) ||∞ · (b − a)n+1 , (n + 1)! ||f (n+1) ||∞ ||en ||∞ ≤ · hn+1 . 4 · (n + 1)!
||en ||∞ ≤
(84) (85)
8.2. Az Hermite interpolációs polinom hibabecslése 5. Állítás. Tegyük fel, hogy f ∈ C n+1 [a, b], ekkor minden x ∈ [a, b] ponthoz ∃ ξ ∈ (a, b), amelyre f (x) − Hn (x) =
f (n+1) (ξ) · ωn+1 (x). (n + 1)!
(86)
Bizonyítás. Legyen x˜ ∈ [a, b], de x˜ 6= xk , k = 0, 1, . . . , n. ϕ(x) := f (x) − Hn (x) − K · ωn+1 (x)
(87)
ahol a K állandót úgy választjuk, hogy tetszőleges x˜ pontban ϕ(˜ x) = 0: K=
f (˜ x) − Hn (˜ x) . ωn+1 (˜ x)
(88)
A ϕ függvénynek az x0 , x1 , . . . , xn pontok N0 , N1 , . . . , Nn -szeres gyökei. Tehát ϕ-nek a multiplicitását figyelembe véve x0 N0 -szoros,. . ., xn Nn -szeres és x˜ egyszeres gyök. A ϕ függvénynek legalább N0 + N1 + . . . + Nn +1 = n + 2 gyöke van. | {z } n+1
A Rolle-tétel alapján az [x0 , x1 ], [x1 , x2 ], . . . , [xn , x˜] intervallumokon ∃ gyöke a ϕ függvénynek, ezek ξ1 , ξ2 , . . . , ξn+1 . Továbbá ϕ0 (x)-nek az x0 N0 − 1-szeres gyöke, az x1 N1 − 1-szeres gyöke, . . ., xn Nn − 1-szeres gyöke. 22
Ezek szerint ϕ0 gyökeinek száma legalább (N0 − 1) + (N1 − 1) + . . . + (Nn − 1) + | {z } xk alappontokban
n + 1} | {z
= N0 +. . .+Nn = n+1. (89)
köztes pontokban
Folytatva ezt a gondolatmenetet: • ϕ00 -nak legalább n gyöke van, • ... • ϕ(n+1) -nak legalább egy gyöke van. A ϕ(n+1) (ξ) = 0 átírható a következő alakban: (n+1)
ϕ(n+1) (ξ) = 0 ⇐⇒ ϕ(n+1) (ξ) − Hn(n+1) (ξ) − K · ωn+1 (ξ) = 0. | {z } | {z } =0, Hn ∈Pn
(90)
(n+1)!
Átrendezzük a következő alakra: f (n+1) (ξ) − K · (n + 1)! = 0 ⇐⇒ f (n+1) (ξ) −
f (˜ x) − Hn (˜ x) = 0. ωn+1 (˜ x)
(91)
3. Következmény. Ha |f (n+1) | ≤ Mn+1 =⇒ |f (x) − Hn (x)| ≤
Mn+1 (b − a)n+1 . (n + 1)!
8.3. Spline interpolációs polinom hibabecslése A lineáris spline polinom hibabecslését a (17)-es tétel mondja ki. 17. Tétel. Legyen f ∈ C 2 (I), ekkor a lineáris spline interpolációs függvény hibája |s(x) − f (x)| ≤
M2 2 h, 8
(92)
ahol M2 egy felső korlát f második deriváltjára az I intervallumon, és h a szomszédos alappontok közötti maximális távolság.
9. Matematikai példák 9.1. Lagrange interpolációs polinom Adott négy alappont, melynek ismerjük az értékét. 1. Feladat. A feladat az, hogy megtaláljuk a ráilleszkedő függvényt.
23
x1 x2 x3 x4
=1 =2 =3 =4
y1 y2 y3 y4
=2 =1 =4 =3
l1 (x) =? l2 (x) =? l3 (x) =? l4 (x) =?
3. táblázat. Feladat: Lagrange-féle interpolációs polinom előállítása
1. Megoldás. Sorban kiszámoljuk a Lagrange alappolinomokat. Először az l1 (x) alappolinomot a j = 2, 3, 4 pontokban számítjuk ki: l1 (x) =
4 Y
x − xj x−2 x−3 x−4 = · · = x 1 − 2 1 − 3 1 − 4 i − xj j=1,j6=1 x3 9x2 26x = + + + 4. −6 6 −6
(93) (94)
Az l2 (x) alappolinomot a j = 1, 3, 4 pontokban számítjuk ki: l2 (x) =
4 Y
x−1 x−3 x−4 x − xj · · = = xi − xj 2−1 2−3 2−4 j=1,j6=2
x3 8x2 19x − + − 12. 2 2 2 Az l3 (x) alappolinomot pedig a j = 1, 2, 4 alappontokban tekintjük: =
l3 (x) =
4 Y
(95) (96)
x − xj x−1 x−2 x−4 = · · = xi − xj 3−1 3−2 3−4 j=1,j6=3
(97)
−7x2 14x x3 + + − 8. −2 −2 −2
(98)
=
Végül pedig az utolsó tagot a j = 1, 2, 3 helyeken számítjuk ki: l4 (x) =
4 Y
x − xj x−1 x−2 x−3 = · · = x 4 − 1 4 − 2 4 − 3 i − xj j=1,j6=4
x3 −6x2 11x + + − 6. 6 6 6 A Lagrange interpolációs polinomot a következőképpen állítjuk elő: =
L4 (x) =
4 X
f (xi ) · li (x) =
(99) (100)
(101)
i=1
x3 − 8x2 + 19x − 12 x3 − 9x2 + 26x − 24 +1· + −6 2 x3 − 7x2 + 14x − 8 x3 − 6x2 + 11x − 6 +4· +3· . −2 6 =2·
24
A végeredmény az L4 (x) interpolációs polinom: 65 4 L4 (x) = − x3 + 10x2 − x + 15. 3 3
(102)
9.2. Newton interpolációs polinom Adott öt alappont, melyeknek ismerjük az értéküket. 2. Feladat. A feladat az, hogy megtaláljuk a ráilleszkedő függvényt. x1 = −1 x2 = 1 x3 = 2 x4 = 3 x5 = 4
y1 = 1 y2 = −1 y3 = 13 y4 = 69 y5 = 221
4. táblázat. Feladat: Newton-féle interpolációs polinom előállítása
2. Megoldás. A alkalmazásával:
Newton-féle
interpolációs
eljárás
osztott
differencia
x1 y 1 & %
y2 − y1 =: n1 x2 − x1
&
x2 y 2 & %
% y3 − y2 =: n2 x3 − x2
&
x3 y 3 & %
% y4 − y3 =: n3 x4 − x3
%
%
& %
n3 − n2 =: n6 x4 − x2
&
x4 y 4 &
n2 − n1 =: n5 x3 − x1
& %
n4 − n3 =: n7 x5 − x3
y5 − y4 =: n4 x5 − x4
x5 y 5 25
n6 − n5 =: n8 x4 − x1
& %
n7 − n6 =: n9 x5 − x2
n9 − n8 =: n10 x5 − x1
Határozzuk meg az n tagokat, melyeket a mellékelt ábrán láthatunk részletezve, majd állítsuk elő az interpolációs polinomot. x1 y 1 & n1 = −1 %
&
x2 y 2
n5 = 5 &
%
&
n2 = 14
n8 = 4
%
&
%
&
&
%
&
%
&
%
x3 y 3
n6 = 21
n10 = 1
n3 = 56 %
n9 = 9
x4 y 4
n7 = 48 &
% n4 = 152
% x5 y 5 Ekkor az interpolációs polinom a következő: p4 (x) = y1 (x) + n1 (x − x1 ) + n5 (x − x1 )(x − x2 )+ + n8 (x − x1 )(x − x2 )(x − x3 ) + n10 (x − x1 )(x − x2 )(x − x3 )(x − x4 ) = = 1 + (−1)(x − (−1)) + 5(x − (−1))(x − 1)+ + 4(x − (−1))(x − 1)(x − 2) + 1(x − (−1))(x − 1)(x − 2)(x − 3) = x4 − x3 + 2x2 − 3. (103)
9.3. Hermite interpolációs polinom 3. Feladat. A feladat az, hogy megtaláljuk az alappontokra ráilleszkedő függvényt. x1 x2 x3 x4 x5
=1 =2 =2 =2 =3
f (1) = 0 f (2) = 1 f 0 (2) = 3 f 00 (2) = 0 f (3) = 1
5. táblázat. Feladat: Hermite-féle interpolációs polinom előállítása
A feladatban öt alappont van, melyekre Hermite interpolációs polinomot szeretnénk illeszteni. Ezt a feladatot kétféle eljárásban is megoldjuk. 26
9.3.1. Hermite polinom előállítása - 1. módszer 3. Megoldás. A feladatban öt pont ismert, ebből következik, hogy egy negyedfokú polinomot keresünk: p(x) = ax4 + bx3 + cx2 + dx + e. (104) Ebben a feladatban ismertek a polinom első és második derivált értékei: p0 (x) = 4ax3 + 3bx2 + 2cx + d, p00 (x) = 12ax2 + 6bx + 2c.
(105) (106)
Az egyenletekbe behelyettesítve:
f (1) = 0 f (2) = 1 f 0 (2) = 3 f 00 (2) = 0 f (3) = 1
→ → → → →
p(1) = a + b + c + d + e = 0, p(2) = 16a + 8b + 4c + 2d + e = 1, p0 (2) = 32a + 12b + 4c + d = 3, p00 (2) = 48a + 12b + 2c = 0, p(3) = 81a + 27b + 9c + 3d + e = 1.
Az egyenletrendszer megoldása 1 16 32 48 81
(107) (108) (109) (110) (111)
a következő: 1 8 12 12 27
1 4 4 2 9
1 2 1 0 3
1 1 0 0 1
0 1 3 0 1
Elvégezzük a Gauss-eliminációt ezen a mátrixon, majd behelyettesítünk a (104)-es egyenletbe. A feladat megoldása tehát: 1 3 H5 (x) = − x4 + x3 + 3x2 − 11x + 7. 2 2
(112)
9.3.2. Hermite polinom előállítása - 2. módszer 4. Megoldás. Ennek a felírása és levezetése nagyon hasonlít a Newton interpolációs polinoméhoz. A különbség az, hogy itt derivált értékekkel is számolunk. f [x, . . . , x] = | {z } k+1 darab x
Behelyettesítünk a következőféleképpen:
27
f (k) (x) k!
(113)
x1 y 1 &
%
f (x2 ) − f (x1 ) =: h1 x2 − x1
&
x2 y 2 &
%
h2 − h1 =: h5 x3 − x1
&
0
f =: h2 1! %
&
%
h6 − h5 =: h8 x4 − x1
&
f 00 =: h6 2!
x3 y 3 &
%
&
f0 = 3 =: h3 1! %
&
x4 y 4 &
%
%
%
% h7 − h6 =: h9 x5 − x2
h4 − h3 =: h7 x5 − x3
f (x5 ) − f (x4 ) =: h4 x5 − x4
x5 y 5 Az értékeket behelyettesítve az alábbi táblázatot kapjuk: x 1 y1 & h1 = 1 %
&
x 2 y2
h5 = 2 &
%
&
&
%
h8 = −2
h2 = 3 % x3 y 3
& h10 = −
h6 = 0 &
%
&
% h9 = −3
h3 = 3 %
&
&
%
% h7 = −3
x 4 y4 h4 = 0 % x 5 y5
28
1 2
h9 − h8 =: h10 x5 − x1
Ebben az esetben a megoldás: 3 1 H5 (x) = − x4 + x3 + 3x2 − 11x + 7. 2 2
(114)
9.4. Spline interpolációs polinom A spline interpolációs feladat megoldására kétféle módszert ismertetünk. 4. Feladat. A feladat az, hogy megtaláljuk az alappontokra illeszkedő függvényt. x1 = −1
y1 = 2
x2 = 0
y2 = 1
s1 (x) =? s2 (x) =? x3 = 2
y3 = −1 s02 (2) = −2
6. táblázat. Feladat: Spline interpolációs polinom előállítása
9.4.1. Spline interpolációs polinom előállítása - 1. módszer 5. Megoldás. Mivel 3 pontunk van, ezért két másodfokú spline interpolációs polinomot illesztünk az alappontokra. Az egyenleteink a következők: s1 (x) = a1 x2 + b1 x + c1 , s2 (x) = a2 x2 + b2 x + c2 .
(115) (116)
A spline feltételeit használva a következő egyenleteket kapjuk: s1 (−1) =2 s1 (0) =1 s2 (0) =1 s2 (2) = − 1 s02 (2) = − 2
−→ −→ −→ −→ −→
a1 − b 1 + c 1 c1 c2 4a2 + 2b2 + c1 4a2 + 2b2
=2 =1 =1 = −1 = −2.
Az x2 = 0 pontban a derivált értékeknek meg kell egyezniük, ezért felírható a következő egyenlőség: s01 (0) = s02 (0). 29
(117)
Ebből következik, hogy: b1 = b2 .
(118)
Írjuk fel a rendelkezésünkre álló egyenleteket: a1 − b1 =1 4a2 + 2b2 = − 2 4a2 + b2 = − 2 s2 (2) = − 1
−→ −→ −→ −→
a1 b2 b1 4a2 + 2b2 + c1
=1 =0 =0 = −1 1 a2 = − . 2
−→
b1 =b2
Ekkor az összes együttható ismert. A megoldásunk két másodfokú polinom: s1 (x) = x2 + 1, 1 s2 (x) = − x2 + 1. 2
(119) (120)
9.4.2. Spline interpolációs polinom előállítása - 2. módszer 6. Megoldás. A második módszerben az Hermite-interpoláció segítségével oldjuk meg a feladatot. 0
1 & %
−1 − 1 = −1 2
&
2 −1 & %
%
−2 + 1 1 =− 2−0 2
−2 = −2 1!
2 −1 Ez alapján az s2 spline interpolációs polinomot így írjuk fel: 1 s2 = − x2 + 1. 2 0 0 Továbbá teljesülnie kell az s2 (0) = s1 (0) egyenletnek is:
30
(121)
−1 2 & % 0
1−2 = −1 0+1
1 & %
0
& %
0+1 =1 0+1
0 =0 1!
1
Ezzel megkaptuk az s1 polinomot is: s1 = x2 + 1.
(122)
9.5. Példák MATLAB programmal A MATLAB programban könnyen lehet interpolációs feladatokat megoldani az alábbi parancsok segítségével: • z = polyf it(x, y, n): Az interpolációs alappontok x-értékei egy x vektort, az y értékei egy y vektort alkotnak. Az n értékkel meghatározhatjuk az illesztendő polinom fokszámát. Ha nincs ilyen polinom, akkor a legkisebb négyzetek elvét használva a legjobban közelítő függvényt állítja elő a program. Az interpolációs polinom együtthatói a z vektorban találhatók. • yi = polyval(z, x): A z vektorral meghatározott polinom értékét számolja ki az xi pontokban. A függvényértékek az yi vektorban jelennek meg. • yi = interpl(x, y, xi , ”módszer”): A parancs a "módszer" által meghatározott eljárással egy interpolációs polinomot illeszt az x és y koordinátákra. A "módszer" lehet például: – linear : szakaszonként lineáris, – spline : szakaszonként legfeljebb haramdfokú spline-interpoláció. Az (1)-es feladat interpolációs polinomját ábrázoltam MATLAB programmal az alábbi függvény segítségével.
31
A forráskód a következő: function lnm(n) if n = 0 & n = 1 & n = 2 & n = 3 & n = 4 disp(’Hibas adat!’) else x = [-1 1 2 3 4]; y = [1 -1 13 69 221]; p = polyfit(x, y, n) xx = −8 : 0.01 : 8; yy = polyval(p, xx); plot(x, y,0 ∗0 , xx, yy,0 r0 ) end
A programkód értelmezése: • A függvény neve: lnm. • Ha az általunk megadott n: – 6= 1, . . . , 4-gyel, akkor ’Hibas adat!’ feliratú visszajelzést kapunk, – = 1, . . . , 4-gyel, akkor: ∗ a megadott x és y koordinátákra a polyfit parancs egy maximum n-ed fokú polinomot illeszt. ∗ Megadtuk azt is, hogy a program milyen intervallumon, milyen felosztással ábrázolja a függvényt. ∗ Az alappontokon kívül minden pontra kiszámítja a polyval parancs a függvényértékeket. ∗ Végül a plot paranccsal megmondhatjuk a programnak, hogy hogyan ábrázolja a kiszámított függvényt. A programot különböző adatokra lefuttatva az alábbi eredményeket kaptam. Az (5b) ábrán négy pontra egy legfeljebb másodfokú polinomot illesztettünk. Az (5c) ábrán ugyanazokra a pontokra egy legfeljebb másodfokú polinomot illesztettünk. A hiba akkor a legkisebb, ha a közelítő polinom elsőfokú. Ekkor ugyanazt a megoldást kaptuk, mint az (5b) esetben. Az (5d) ábrán négy alappont esetén kaptuk a következő függvényt: 4 65 p = − x3 + 10x2 − x + 15. 3 3
32
(123)
(a) Legfeljebb 0. fokú polinom
(b) Legfeljebb 1. fokú polinom
(c) Legfeljebb 2. fokú polinom
(d) Legfeljebb 3. fokú polinom
5. ábra. Lagrange feladat alappontjaira írt megoldása » lnm(0) p= 2.5000 » lnm(1) p= 0.6000 1.0000 » lnm(2) p= -0.0000 0.6000 1.0000 » lnm(3) p= -1.3333 10.0000 -21.6667 15.000
33
(a) Legfeljebb 0. fokú polinom
(b) Legfeljebb 1. fokú polinom
(c) Legfeljebb 2. fokú polinom
(d) Legfeljebb 3. fokú polinom
(e) Legfeljebb 4. fokú polinom
6. ábra. Newton feladat alappontjaira írt megoldása
34
» lnms(0) p= 60.6000 » lnms(1) p= 38.4865 -8.6757 » lnms(2) p= 18.1944 -14.6215 -25.8866 » lnms(3) p= 5.7925 -8.4987 -5.9030 9.2264 » lnms(4) p= 1.0000 -1.0000 2.0000 0.0000 -3.0000 Tehát az öt alappontra illesztett negyedfokú p polinomunk a következő: p = x4 − x3 + 2x2 − 3.
(124)
10. Összegzés A szakdolgozatban különböző interpolációs eljárásokat mutattunk be elméletben és gyakorlatban. A motivációban olvashattunk gyakorlati példákról, melyek szükségessé tették az interpoláció használatát a mindennapokban. A dolgozat elején egy olyan g függvényt kerestünk, mely illeszkedett az általunk meghatározott pontokra: g = f (xi ). Több interpolációs eljárást ismertettünk. Először tárgyaltuk a Lagrange interpolációt, mely igen költséges eljárás, ha új alappontot akartunk hozzáadni az eddigiekhez. Ezután a Newton-interpolációt vizsgáltuk, amely rekurziót alkalmaz. Majd az Hermite interpolációt tárgyaltuk. Végül a Spline interpolációt vizsgáltuk, mely szakaszonként illesztett interpolációs polinomokat az alappontokra. Minden eljárásra külön meghatároztuk a hibabecsléseket, és feladatokat mutattunk be kiszámításukra. A dolgozat végén a MATLAB nevű program különböző beépített függvényeit használtuk különböző interpolációs feladatok megoldása során.
35
Köszönetnyilvánítás Szeretném megköszönni témavezetőmnek, Svantnerné Sebestyén Gabriellának a sok türelmet és biztatást. Köszönöm, hogy kitartott mellettem és, hogy mindvégig támogatott. Hálás vagyok, hogy szakértelmével jelentősen hozzájárult szakdolgozatom elkészüléséhez. Továbbá hálásan köszönöm Édesanyámnak, Húgomnak, Nagymamámnak, Nagypapámnak és férjemnek: Zoltánnak, hogy mindig mellettem álltak és segítették tanulmányaimat.
36
Hivatkozások [1] Faragó István - Alkalmazott analízis I. előadás jegyzet [2] Galántai Aurél, Jeney András - Numerikus módszerek [3] Douglas Wilhelm Harder - Numerical Analysis for Engineering [4] Dr. Havasi Ágnes - A MATLAB alapjai [5] Dr. Havasi Ágnes - Alkalmazott Analízis számítógépes módszerei I. gyakorlat jegyzet [6] Horváth Róbert, Faragó István - Numerikus módszerek [7] Kiss Emil - Bevezetés az algebrába [8] Doron Levy - Introduction to Numerical Analysis [9] Mihalkó Zita - Interpoláció [10] Stoyan Gisbert, Takó Galina - Numerikus módszerek 1. [11] Svantnerné Sebestyén Gabriella - Alkalmazott analízis I. gyakorlat jegyzet [12] Dr. Szalay István - Egyváltozós függvények differenciálása [13] Dr. Y. Sue Liu - Spline Interpolation [14] https://hu.wikipedia.org/ [15] http://www.crnl.hu/!old/tan/matek/leckek/ [16] http://www.tankonyvtar.hu/
37
