Interpoláció
Az interpoláció matematikai közelítő módszer, amely egy függvény nem ismert értékeire az ismert értékek alapján ad közelítést.
Általános értelmezés
szerkesztésA függvény két számhalmaz elemei között fennálló kapcsolatok sokaságát írja le elméletileg, a kapcsolatrendszer megjelenítéséhez a két leggyakrabban alkalmazott eszköz a képlet és a grafikon. A függvény ismeretében az értelmezési tartomány bármely eleméhez egyértelműen hozzárendelhető az értékkészlet egy-egy eleme.
Van, hogy két számhalmaz között egyértelmű kapcsolatot sejtünk, de nem ismerjük a kapcsolatot végtelen számú elemre definiáló függvényt, csupán véges számú igazolt kapcsolat felsorolása áll a rendelkezésünkre. Például egy tengeröbölben megmértük a víz káliumtartalmát különböző mélységekben. További mérések költséges elvégzése helyett a meglevő adatokból kiindulva szeretnénk közelítő káliumtartalom-értékeket kapni más mélységekre is. Valójában mindenképpen ezt tennénk, egymáshoz bármilyen közeli mélységekben végeznénk el a mérést, mivel ha nem végtelenül sűrűn, azaz folyamatosan mérünk, akkor a mérésünk csak mintavételeket tartalmaz, amelyek közötti értékek csakis interpolációval lesznek megnevezhetők.
Az interpoláció egy ilyen esetben két célra is használatba vehető. Egyrészt ha a függvény értelmezési tartományából egy olyan értéket, ez esetben egy olyan vízmélységet választunk ki, amelyhez nem tartozik ismert, megmért adat, akkor az ehhez a mélységhez tartalmazó káliumtartalom-értéket a hasonló mélységekben mért, ténylegesen ismert értékek alapján becsüljük meg.
Az interpoláció másik eredménye pedig az lehet, hogy felállíthatunk, kifejezhetünk egy olyan általános modellfüggvényt, amely pontosan illeszkedik az ismert, mért értékekhez, és a feltételezésünk szerint kellő pontossággal követi a valóságban létező, csak általunk nem ismert összefüggés vonalát. Ennek a modellfüggvénynek a segítségével már nem csak egy bizonyos értékhez, hanem bármilyen mélységértékhez tartozó káliumtartalmat megkaphatjuk, és ez az érték feltételezhetően a modellezés technikájából eredő pontossággal felel meg annak az értéknek, amelyet a valóságban a mérés eredményeként kapnánk. Ha a modellfüggvény menetében egy szűkebb tartományon belül bizonytalanná válunk, akkor ez az abban a tartományban elvégzett további mérésekkel egyértelműsíthető.
A közelítő modellfüggvény létrehozásának két elkülönülő esete van. Az egyik eset az, amikor a megközelítendő függvénykapcsolatnak azzal a szakaszával foglalkozunk, amelynek az értelmezési tartománya a mérések helyeinek tartományán belül van. Ez az interpoláció (inter latinul 'között'). Ilyenkor a mért értékek közötti ismeretlen értékekre adunk becslést. A másik eset az, amikor az ismert értékek értelmezési tartományán kívül eső értékek közelítéséhez készítünk modellfüggvényt. Ez az extrapoláció (extra latinul 'kívül'), és másfajta matematikai módszerek használatosak hozzá. Ez utóbbival gyakorlatilag olyan modellfüggvényt állítunk fel, amellyel a már valamennyire ismert függvényszakasz folytatására adunk közelítést. (A folytatás az ismert szakaszt megelőző vagy követő tartományt is jelentheti.)
Matematikai értelmezés
szerkesztésAz interpoláció során célunk az f(x) függvény alakjának egy i(x) függvénnyel való minél pontosabb megközelítése olyan formában, hogy a közelítő függvény is áthaladjon az ismert, táblázatba szedett, ún. tabulált pontokon, tehát elégítse ki az yi = i(xi) feltételt. Interpolációról akkor beszélünk, ha az x pont, melyben az i(x) értéket szeretnénk megbecsülni, a megadott pontok legkisebb és legnagyobb értéke által meghatározott intervallumon belül helyezkedik el. Az interpoláció módszere feltételezi a függvény valamilyen szintű simaságát, vagyis hogy a függvény második deriváltjának abszolút értéke sehol sem nagyobb egy elfogadható értéknél.
Az interpolációs módszereket több osztályba sorolhatjuk. A közelítési függvények típusát tekintve lehetnek:
- Polinomiálisak, amikor a közelítő függvények polinomok (ezek a legelterjedtebb módszerek). Az interpoláció segítségével n különböző számpárra, vagyis n pontra egyértelműen illeszthető egy (n-1)-ed fokú polinom, amely átmegy a közölt pontokon.
- Trigonometrikusak, amikor a szinuszos illetve koszinuszos függvények közreműködésével interpolálunk. Hasznosnak bizonyulnak az interpolációval egybekötött Fourier-módszerek alkalmazásának esetén.
- Racionális, amikor egyes függvények nem közelíthetőek jól polinomokkal, viszont sikeresen használhatjuk a racionális függvények bővebb osztályát. Racionális függvény alatt két polinom arányát értjük.
Attól függően, hogy milyen más tulajdonságokkal szeretnénk felruházni a közelítő függvényt, az interpoláció lehet:
- Lokális, abban az esetben ha az I(x) közelítőfüggvény meghatározásakor az x közelében fellelhető néhány pontot vesszük figyelembe. Ez azt eredményezi, hogy a magasabb rendű deriváltakban nem kapunk folytonos függvényt.
- Globális, abban az esetben, ha az összes rendelkezésre álló (xi , yi) pontot felhasználjuk, bármely x értékről lenne szó.
- Spline, olyankor merül fel, amikor elvárjuk a közelítőfüggvény folytonosságát. A spline függvény egy meghatározott szakaszon értelmezett polinom, tehát lokális módszer, viszont a változás a polinom együtthatóinál következik be, mivel ezeket úgy rögzítjük le, hogy globális simaságot biztosítson a közelítőfüggvénynek.
Bármelyik módszert is használjuk, szükséges az x érték lokalizálása, vagyis annak az [xj ; xj+1) szakasznak az azonosítása, amelyen belül ez elhelyezkedik. Matematikai megfogalmazásban, adott x0 ≤ x ≤ xn értékre keressük azt a m ∈[0; n] természetes számot, melyre fennáll, hogy xm ≤ x ≤ xm+1.
Lineáris interpoláció
szerkesztésA lineáris interpoláció a legegyszerűbb interpolációs módszer. Az alábbi példa segítségével bemutatható az eljárás célja és lényege.
Tegyük fel, hogy egy műanyagfajta hőmérséklete és szilárdsága közötti összefüggést kutatjuk. A feladat kitalált, tehát a bemutatott eredmény is csak egy kitalált példa. Az 1. ábrán láthatóak szerint a mintadarabot 7 különféle hőmérsékletre melegítettük, és mindegyik hőmérsékleten egy igen körülményes módszerrel megmértük a műanyag szilárdságát. A kapott mérési adatokat derékszögű koordináta-rendszerben ábrázoljuk, amelyen az x tengelyen sorakoznak a hőmérsékleti értékek, az y tengelyen pedig az eredményül kapott szilárdsági mutatók. A vizsgált műanyag egy teljesen új, ismeretlen anyag, amelynek a tulajdonságait most próbáljuk felderíteni, ezért gyakorlatilag semmilyen sejtésünk nincs arról, hogy a hőmérséklet→szilárdság függvény görbéje hogyan nézhet ki, csak a látható hét pontot ismerjük belőle.
Szeretnénk egy becsült, egy közelítő értéket előállítani a már ismert eredmények alapján a kék vonalkával jelzett hőmérsékleten várható szilárdságról. Ez a kék érték a már megismert értékek tartományán belül van, azaz interpolációval állítjuk elő a becslésünket. Elsőként kiválasztjuk a kérdéses x értékhez legközelebbi két ismert értéket, ezeket P1 és P2 pontokkal jelöltük, a többit most figyelmen kívül hagyjuk (2. ábra). A két szomszédos érték koordinátái az x tengelyen x1 és x2, a hozzájuk tartozó mérési értékek rendre y1 és y2. Kiválaszthatnánk az x értéket pontosan félúton x1 és x2 között is, amely végül is egy középarányos számítását fogja eredményezni, de a módszert tetszőleges x értékre tárgyaljuk.
A 3. ábrán látható, hogy a módszer alapjaként először a P1 és P2 pontokon át egy egyenest húzunk. Az egyenes (latinul linea) adja a lineáris interpoláció nevét, más interpolációs technikánál másféle görbék kötik össze az ismert pontokat. Az egyenes dőlésének iránya és meredeksége nem lényeges a módszer szempontjából, kivéve annyit, hogy az egyenes nem lehet merőleges az x tengelyre, mert az ellentétben állna a függvény fogalmának definíciójával. Mivel az áthidaló egyenes nem függőleges, ezért valahol mindenképpen metszi azt a vizsgált x értékhez húzott (kék) merőleges. A 4. ábrán kissé felnagyítva láthatjuk a helyzetet, amelyen ez a kimetszett pont P, és az ebből az y tengelyre bocsátott (vízszintes) merőleges jelöli ki a tengelyen a pont y koordinátájának értékét (5. ábra). Tehát a lineáris interpoláció révén a keresett x értékhez a P1P2 szakaszon találtunk egy P pontot, amelynek a koordinátái (x;y). Az a kérdés maradt, hogy a P1 és P2 ismert koordinátáinak segítségével hogyan fejezhetjük ki a közelítő P pont koordinátáit, azaz az y értékét.
Kihasználhatjuk, hogy a pontokhoz húzott, a tengelyekre merőleges segédvonalak mindig kijelölnek egy P0P2P1 háromszöget, amelyben a P0 pontnál levő szög derékszög (4. ábra). Mivel a nagyobbik, sárga háromszög mértanilag hasonló a zölden csíkozott, kisebb háromszöghöz, ezért az oldalaik hossza között egyenes arányosság van. A sárga háromszög alsó befogójának a hossza x2–x1, a zöld háromszög alsó befogójának hossza pedig x–x1. E kettő aránya megegyezik a függőleges befogók hasonlóképp számítható hosszaival. Azaz:
- .
Ebből kifejezhető:
- .
Ennek a képletnek a birtokában bármilyen x-hez, amely az (x1:x2) intervallumon belül van, megadható az az y, amelyet az interpoláció révén az igazi, nem ismert érték közelítésének tekintünk.
A 6. ábrán látható, ahogy az összes ismert pontot összekötöttük a szomszédjával, megkapva így egy olyan törtvonalat, amely a keresett függvényt a reményeink szerint elfogadható pontossággal modellezi, közelíti. Az előző képletünk csak egy ilyen szakaszra adta meg x és y kapcsolatát, de azt kiterjeszthetjük a teljes mért tartományra. A modellfüggvényünk törtvonal, a töréspontjainál nem illeszthetők hozzá érintők egyértelműen, más szóval a lineáris interpoláció modellfüggvénye nem differenciálható, a deriváltja szakadozott és lépcsőzetes. Így az n darab ismert értékhez illesztett általános modellfüggvény csak szakaszokra bontva határozható meg:
- ahol , valamint és
vagyis i egész szám, amely 1 és n-1 között van, a független változó x* pedig két egymással szomszédos ismert pont közé esik, amelyek sorszáma i és i+1.
A 7. ábrán a közelítésre ráhelyeztük azt a görbét, amely a hőmérséklet és a szilárdság közötti valóságos összefüggést ábrázolja, azt az összefüggést, amelyet egy igazi kutatáskor továbbra sem ismernénk, esetleg későbbi kutatások derítenék majd ki ennek a függvénynek a pontos alakját. Ha igen nagy számú mérést végeznénk, akkor a sok mérés eredménye ezt a görbét rajzolná ki, de lehet, hogy a sok mérés elvégzése túlzott költséggel jár, ezért elégedtünk meg néhány méréssel. A lineáris interpoláció eredménye a valódi görbe szelőinek láncolatából áll. Láthatjuk, hogy egyes részeken elég jó közelítést kaptunk az interpolációnkkal, de a 2. és 3. pont közötti ívre az eddigi méréseink nem utaltak, ezt a kiemelkedést az interpolációnk nem jósolta meg, ezen belül meglehetősen hibás becslést tettünk.
Ám hogy a közelítés mennyire lett eredményes, a bekeretezett szakasz nagyításán, a 8. ábrán megtekinthető. A közelítés sárga és a valóság zöld vonalai viszonylag közel vannak egymáshoz. De nem szabad elfeledkeznünk arról, hogy az egy bizonyos x értékhez tartozó interpolált és valódi y értékeket az x-ből induló függőleges vonallal jelöljük ki. Márpedig ebben az irányban a két görbe között már jelentős értékkülönbség mutatkozik. A közelítésnek ez a várható hibája mindig a meredekebb görbeszakaszokon lesz a legnagyobb.
A 9. ábrán látható az, ami a józan ész szerint is várható, vagyis ha sűrűbb mérési értékeket gyűjtünk össze, akkor a közelítő szakaszok rövidebbek lesznek, így jóval kisebb lesz a távolságuk a valóságos értékek görbéjétől. (Hasonlítsuk össze a görbét a 6. ábra eredményével.) Ha a mérési pontok sűrűsége a végtelenhez tart, akkor az interpoláció és a valódi függvény közötti eltérés a nullához tart.
Az eljárás során felmerülhet a kérdés, hogy a 4. ábrából levezetett képletünkben nem használtuk-e ki azt, hogy a közelítő egyenesünk csökkenő irányba lejt. A 10. ábrán látható egy másik helyzet, amelyről kiderül, hogy a képlet ekkor is ugyanaz. A helyes értelmezés feltétele, hogy az x tengely mentén a P2 jobbra legyen a P1-től, és a P0P1 szakasz függőleges legyen, vagyis az x tengelyre merőleges, ahogy ez az ábrákon látható is.
Mivel ez az interpoláció egyszerű módszer, a végrehajtási időt tekintve gyors is, viszont az általa kapott megközelítés durva, és várhatóan nagy eltéréseket fog eredményezni. Az eltérések természetesen csak a valódi összefüggés pontosabb megismerése után lesznek láthatók, emiatt annak mértékéről sem tudhatunk pontosabbat. Ha a valódi összefüggés lineáris, akkor az interpolációnk tökéletes közelítést produkál, ha viszont a fenti példában látható változatos görbe, az eltérés jelentőssé válhat. A mért pontok elhelyezkedése itt változatos görbét sejtetett, tehát lényeges pontatlanságra számíthattunk.
Más értelmezés
szerkesztésA lineáris interpoláció a legegyszerűbb interpolációs módszer. Lényege az, hogy az egymás után következő pontokat egyenessel kötjük össze, tehát elsőrendű polinomokat használunk (m=1).Ez egy lokális módszer és az ≡ ilin(x) függvény deriváltja nem folytonos.A függvényt [xj ;xj+1] szakaszonként határozzuk meg.Az x ∈ [xj; xj+1] intervallumon = Aj(x)yj + Bj(x)yj+1 formában írja fel a közelítést.
Az és függvényekre azt kapjuk, hogy
- .
Algoritmus a lineáris interpolációhoz
szerkesztésdef Lokalizalas(x, X):
k=0
m=0
l=n-1
if x==X[l]:
k=l-1
while l-k>1:
m=(k+l)/2
if x<X[m]:
l=m
else:
if x==X[m]:
return m
else:
k=m
return k
#azt az indexet teritem vissza, amelyiknel meg eppen nagyobb az x
def LinearisInterpolacio(x, X, Y):
i=0
i=Lokalizalas(x, X)
return Y[i]+(Y[i+1]-Y[i])/(X[i+1]-X[i])*(x-X[i])
X=[0, 0.78, 1.57, 2.35, 3.1, 4, 4.8, 5.5, 6.6]
Y=[0, 0.7, 1, 0.75, 0.1, -0.66, -1.05, -0.7, 0]
X1=np.linspace(0,6.6,n1)
Y1=[0]*n1
plt.plot(X,Y, 'og')
for i in range(n1):
Y1[i]=LinearisInterpolacio(X1[i], X, Y)
plt.plot(X1,Y1, '--r')
plt.show()
A kód futtatása után az interpoláció a következőképpen néz ki:
Lagrange-interpoláció
szerkesztésA Lagrange-interpoláció egy globális interpolációs módszer. Bár több interpolációs polinomot is meg kell határoznunk, ezek mindegyike a teljes (x1; xn) intervallumon értelmezett, és egy pont kivételével az összes xi pontra szükség van együtthatóinak meghatározására. A polinomok foka n-1.
Az interpolációs függvény alakja:
, ahol m-ed fokú polinomok.
A fenti feltételek kielégítését m=n-1 a következőképpen érhetjük el:
.
Észrevéve azt, hogy úgy a számlálóból mint a nevezőből hiányzik a j-edik tag.Belátható a kikötés.
A teljes Lagrange-interpolációs függvény alakja tehát:
.
A Lagrange-interpoláció nagy előnye a lineáris interpolációval szemben a függvény simasága, illetve deriváltjainak folytonossága. Ennek tudható be az, hogy sok esetben jobb, valósabb megközelítést lehet elérni vele, mint a lineárissal. Figyelembe véve, hogy egy olyan polinomról van szó melynek foka a tabulált pontok számával nő, leglényegesebb hátránya a Lagrange-interpolációnak az, hogy bizonyos esetekben indokolatlanul erőteljes hullámzások jelennek meg a polinom grafikus képében, két egymást követő pont között.Ez annak tudható be, hogy az eredeti, a tabulált pontokat származtató, f(x) megközelítendő függvény nem polinomiális és egy megközelítő polinom csak úgy tud eleget tenni az összes pont érintési követelményének, hogy a pontok között lokális maximumokon és minimumokon halad keresztül.
Algoritmus a Lagrange interpolációhoz
szerkesztésimport math
import numpy as np
import matplotlib.pyplot as plt
n=11
n1=100
def LagrangeInterpolacio(x, X, Y):
y=0
for i in range(n):
p=1
for j in range(n):
if i!=j:
p=p*(x-X[j])/(X[i]-X[j])
y=y+p*Y[i]
return y
X=[0,1,2,3,4,5,6,7,8,9,10]
Y=[0.5,1,2.2,3,4,5.5,6.7,8,8.1,9,10.3]
X1=np.linspace(0,10,n1)
Y1=[0]*n1
plt.plot(X,Y, 'og')
for i in range(n1):
Y1[i]=LagrangeInterpolacio(X1[i], X, Y)
plt.plot(X1,Y1, '--r')
plt.show()
A kód futtatása után az interpoláció a következőképpen néz ki:
Köbös spline-interpoláció
szerkesztésA Lagrange-interpoláció fentebb megfogalmazott hátrányát kiküszöbölendő, kisebb fokú polinomokat használunk, melyeket lokálisan definiálunk. Az egyes polinomok mindig két egymást követő tabulált pont között értelmezettek, viszont megtartva a simasági tulajdonságaiból a Lagrange-interpolációs polinomnak, úgy határozzuk meg a polinomok együtthatóit, hogy a tabulált illeszkedési pontok helyén a deriváltak megfelelőképpen viselkedjenek. A köbös spline esetén, mint neve is elárulja, harmadfokú polinomokkal kötjük össze az egymást követő pontokat. A harmadfokú polinom négy együtthatója soknak tűnik, ha figyelembe vesszük, hogy elsőfokú polinomokkal is ki tudtuk elégíteni az interpoláció alapfeltételét.A magasabb fok és az azzal járó, plusz információt hordozó együtthatók szerepe az, hogy olyan módon görbüljön a két pont között a polinom, hogy annak végpontjainál simán illeszkedjen a szomszédos szakaszokon értelmezett polinomokhoz.
Konkrétan, az interpolációs függvénnyel szemben támasztott követelmények a következők:
- Legyen folytonos, miként azt az egyenlet is megkívánja.
- Az elsőrendű derivált ja legyen folytonos és sima.
- A másodrendű derivált is legyen folytonos.
Feladatunk ez esetben az, hogy meghatározzuk az egyes szakaszokon értelmezett polinomok együtthatóit a fentebbi feltételek tiszteletben tartásával. Szem előtt tartjuk, hogy a tabulált pontokban a másodrendű derivált értelmezett és jól meghatározott értéket kell felvegyen.A számítás megkönnyítése érdekében úgy tekintjük, mintha a másodrendű derivált értékei ezekben a pontokban ismertek lennének és y″(j)-vel jelöljük őket. Minthogy az y″(x) derivált folytonos kell hogy legyen, az interpolációs polinom másodrendű deriváltját leírhatjuk lineáris interpolációval.
Az [xj , xj+1 ) intervallumon fennáll, hogy:
- , ahol az Aj(x) és Bj(x) függvények azonosak a lineáris interpolációnál már egyszer megadottakkal.
Az interpolációs függvényszakaszról tudjuk, hogy maga is folytonosan kapcsolódik a szomszédos szakaszokon értelmezett függvényekhez, de a simasági követelmények miatt általában nemlineáris. Teljesen általánosan felírható mint
- , ahol a folytonossági feltételt kielégítendő kikötjük, hogy .
Tekintve az és függvények lineáris voltát, illetve a fentebb említett két kifejezés kapcsolatát, érvényes, hogy:
, melynek kétszeres integrálása után a -et felírhatjuk, mint , ahol fennáll, hogy:
- és .
Megoldva a két másodrendû differenciálegyenlet et x-ben, és figyelembe véve, hogy azt kapjuk, hogy
.
A keresett interpolációs polinom meg is lenne határozva, ha az másodrendű derivált értékek, az -hez hasonlóan tabuláltak, azaz ismertek lennének. Viszont mindeddig csak az és másodrendű derivált folytonosságát használtuk fel és az elsőrendű deriváltét nem.Az intervallumon:
- .
Felírva ugyanezt az szakaszra:
.
A derivált folytonossága azt jelenti, hogy , mely az
egyenlethez vezet. Ez n-2 egyenletet jelent n darab ismeretlen értékre.
Következésképpen tehetünk további két kikötést.
- és -t nullának vesszük, mely módszer a természetes köbös spline néven ismeretes. -úgy rögzítjük le ezt a két értéket, hogy az elsőrendű deriváltak, és adott értékeket vegyenek fel a két szélső pontban.
A lineáris egyenletrendszer tridiagonális és megoldása az ismeretlenekben könnyedén elvégezhető.
Alkalmazások
szerkesztésKépinterpoláció
szerkesztésKépek interpolációja bármilyen digitális fotónál felmerül valamilyen stádiumban, akár mozaiktalanítás akár nagyítás esetében. Általában abban az esetben merül fel ha nagyítás, elferdítés vagy forgatás történik. A képméretezés a pixelek teljes számának növelése avagy csökkentésekor, míg a ferdítés vagy a forgatás széles körben fordulhat elő: lencsék torzítását kijavító, perspektívaváltó vagy forgató interpolációk. Akkor is, ha ugyanazt a képet méretezzük, forgatjuk, ferdítjük, az eredmény jelentős mértékben függ majd az interpoláció algoritmusától. Ez csupán egy közelítés, tehát a kép veszíteni fog a minőségéből minden esetben. Az interpoláció egy már megadott adatnak felhasználásával működik, megbecsülve a még nem ismert pontok értékét.
Átméretezés
szerkesztésA képinterpoláció két irányba működik, és egy pixel színének illetve ennek intenzitásának legjobb közelítését igyekszik elérni, a környező cellák tulajdonságait véve alapul. Ellentétben a hőmérséklet fluktuációival (a bevezetőben megadott példa keretén belül) a pixelek értékei változhatnak hirtelen egyik helyről a másikra. Minél több információt ismerünk a környező cellákról, az interpoláció annál pontosabb lesz. Ebből következik, hogy minél jobban kinyújtunk egy képet, annál nagyobb mértékben romlik a minősége.
Forgatás
szerkesztésInterpoláció merül fel minden egyes olyan esetben, ahol forgatni vagy disztorziálni, torzítani kell egy képet. A 90 fokos forgatás veszteségmentes, mert egy cella sincs áthelyezve két pixel közötti határra (és így megosztva). Abban az esetben, ha a forgatás nem 90 fokos, már a legelső forgatásnál észrevehető, hogy romlott a minőség. Következésképpen a kép minőségének romlása egyenesen arányos a forgatások számának növekedésével. Az eredmények javíthatóak az interpoláció algoritmusának pontosításával vagy a megadott adatok hibájának csökkentésével.
Források
szerkesztés- Lázár Zsolt, Lázár József, Járai-Szabó Ferenc – Numerikus módszerek (Kolozsvári Egyetemi Kiadó, 2008)
- dr. Kis Ottó, Kovács Margit – Numerikus módszerek (Műszaki Könyvkiadó, 1973)
- Obádovics J. Gyula – Matematika (Műszaki Könyvkiadó, Budapest, 1980) (613-616. o.)