- Kombinatorika
- Halmazok, rendezett párok, leképezések
- Matematikai logika, ítéletkalkulus
- Gráfelméleti alapok
- Gráfok izomorfiája és síkbarajzolhatósága
- Gráfok bejárása és gráfalgoritmusok
- Kromatikus szám, klikk, perfekt gráfok
- Gráfparaméterek, párosítások
- Hálózatok
- Irányított gráfok, gráfalgoritmusok irányított gráfokban
- Lineáris leképezések
- Menger tételei, többszörös összefüggőség
- Páros gráfok, párosítások
- Sajátérték, sajátvektor, sajátfelbontás
- Teljes indukció
- Oszthatóság
- Euklideszi algoritmus & Diofantoszi egyenletek
- Kongruenciák
- Mátrixok
- Lineáris egyenletrendszerek
- Determináns, adjungált, kvadratikus alakok
- Komplex számok
- Polinomok
- Interpolációs polinomok
- Csoportok, gyűrűk, testek
Interpolációs polinomok
Interpoláció
Az interpoláció egy közelítő módszer, amely a függvény ismert értékei alapján ad közelítést a nem ismert értékeire.
Langrange-féle interpolációs polinom
A Lagrange-féle interpolációs polinom megadja azt a polinomot, amely $x_1$-ben $y_1$-et, $x_2$-ben $y_2$-t és így tovább $x_n$-ben $y_n$ értéket vesz föl. Általánosan így tudjuk legyártani:
\( P(x) = \sum_{j=1}^{n}{ \prod_{k \neq j}^n{ \frac{x-x_k}{x_j-x_k} \cdot y_j } } \)
Newton interpoláció
A Newton interpoláció első lépése, hogy elkészítjük a Newton-együtthatókat:
\( N_1 = \frac{ y_2 - y_1}{x_2 - x_1 } \quad N_2 = \frac{ y_3 - y_2 }{ x_3 - x_2 } \quad N_3 = \frac{ y_4 - y_3 }{ x_4 - x_3 } \)
\( N_4 = \frac{ N_2 - N_1}{x_3 - x_1} \quad N_5 = \frac{ N_3 - N_2}{x_4 -x_2} \)
\( N_6 = \frac{ N_5 - N_4 }{ x_4 - x_1 } \)
A polinomot pedig így kapjuk meg:
\( P(x) = y_1 + N_1 (x-x_1) + N_4 (x-x_1)(x-x_2) + N_6 (x-x_1)(x-x_2)(x-x_3) \)
Hermite interpoláció
A Hermite interpoláció abban különbözőik a Lagrange és Newton féle interpolációktól, hogy az $x_1, x_2, \dots , x_n$ helyeken nem csak az eredeti polinom-függvény értékeit, hanem a deriváltjait is nézzük.
A keresett polinomfüggvény mindig egyel kisebbfokú lesz, mint az interpolációs pontok száma ($k$) és a következő alakban keressük:
\( f(x) = a_{k-1} x^{k-1} + a_{k-2} x^{k-2} + \dots + a_1 x + a_0 \)
A polinom együtthatóit úgy kapjuk meg, hogy az ismert adatokat behelyettesítjük és egy egyenletrendszert alkotunk belőle, amit pl. Gauss eliminációval megoldhatunk.
Interpoláció hibabecslése
Ha az $f$ függvény $n+1$-szer deriválható az $x_1, x_2, \dots, x_n$ és $x$ által kifeszített $I$ intervallumon, akkor az interpoláció hibája:
\( E_n(x) = \frac{ f^{ (n+1) } ( \xi_x ) }{ (n+1)! } \cdot \prod_{i=1}^{n} (x-x_i) \quad \xi_x \in I \)
a) Adjuk meg azt a polinomot, ami 1-ben 3-at vesz föl, 2-ben 5-öt és 4-ben 1-et.
b) Adjuk meg azt a polinomot, ami 1-ben 4-et, 2-ben 3-at és 4-ben 2-t vesz fel.
Gyártsunk egy olyan polinom-függvényt, ami 1-ben 3-at, 2-ben 6-ot, 4-ben 2-t és 5-ben 4-et vesz föl.
Gyártsunk egy olyan polinom-függvényt, ami 1-ben 3-at, 2-ben 6-ot, 4-ben 2-t és 5-ben 4-et vesz föl, a Newton interpoláció segítségével.
Gyártsunk egy olyan polinom-függvényt, ami a következőket tudja:
\( x_1 = 1 \quad f(1)=2 \quad f'(1)=7 \quad f''(1)=36 \)
\( x_2=2 \quad f(2)=52 \quad f'(2)=127 \)
\( x_3=0 \quad f'(0)=-1 \)
Négy helyen végeznek függőleges próbafúrásokat, hogy megállapítsák a geológiai szerkezetet.
A fúrásokból vett minta alapján a dolomitréteg ezeken a tengerszintfeletti magasságokon kezdődik:
\( x_1 = 0 \; km \quad y_1 = 680 \; m\)
\( x_2 = 5 \; km \quad y_2 = 810 \; m\)
\( x_3 = 10 \; km \quad y_3 = 720 \; m\)
\( x_4 = 15 \; km \quad y_4 = 960 \; m\)
Egy interpolációs polinom segítségével próbáljuk meghatározni, hogy milyen magasan húzódik a dolomitréteg alsó határa.
Számoljuk ki az alábbi pontokhoz illeszthető harmadfokú természetes spline polinomot.
Számoljuk ki egy másodfokú interpolációs polinom segítségével, hogy mennyi $log_{2}3$.
Itt mindet megtudhatsz az interpolációs polinomokról. Megnézzük, hogy mire jó az interpoláció és hogyan kell legyártani az interpolációs polinomokat. Szuper-érthetően elmeséljük neked, hogy mi az a Lagrange-féle interpolációs polinom és mire lehet használni. Az interpolációs polinomok közül ez a legegyszerűbb és a leggyakoribb. Megnézzük a Lagrange interoláció képletét és nézünk rá példákat. Röviden és érhetően megnézheted, hogy mi az a Newton interpoláció és mire lehet használni. Az interpolációs polinomok közül ez a második legnépszerűbb. A Newton interpoláció képlete és példák Newton interpolációra. Végül pedig jön egy újabb módszer interpolációs polinomok gyártására, amit Hermite interpolációnak hívunk. Ez abban különbözik az előzőktől, hogy nem csak az eredeti polinom-függvény értékeit, hanem a deriváltjainak értékeit is nézzük.
Egy olyan polinomot fogunk gyártani, ami előre megadott pontokon megy át. Ezeket a polinomokat interpolációs polinomnak nevezzük. Interpolációs polinomból többféle is van. Az egyik legegyszerűbb a Lagrange-féle interpolációs polinom. Szintén könnyen használható és elterjedt a Newton-interpoláció és a Hermite-interpoláció is. Mindegyikre fogunk nézni egy-egy példát. Íme, itt vannak a pontok. Vagy épp ezek. Vagy ezek. A dolog lényege, hogy bárhol lehetnek, és bármennyi. Minél több pontunk van, a polinom fokszáma annál nagyobb lesz. Kezdetnek most elég ez a három. Azt a polinom-függvényt fogjuk megalkotni, ami 1-ben 3-at vesz föl… 2-ben 5-öt… és 4-ben 1-et. Először egy olyan polinomot fogunk gyártani, ami 1-ben 3-at vesz föl és a másik két helyen nullát. Ehhez mindössze annyit kell megértenünk, hogy ez a polinom: Itt nulla. Meg itt… Meg itt, meg itt. És, ha azt szeretnénk, hogy még 6-ban is nulla legyen… Hát, éppen arról is lehet beszélni. Az a polinom-függvény, ami 1-ben 3-at vesz föl és a másik két helyen nullát, valahogy így fog kinézni. De sajnos van egy kis gond. Ha behelyettesítjük az 1-et… akkor nem jön ki a 3. Eddig jó. Most gyártani fogunk egy másik polinom-függvényt, ami 1-ben és 4-ben nulla… De ha 2-t helyettesítünk bele, akkor van egy kis gond. Nem az jön ki, ami nekünk kéne. Ezt a kis problémát így tudjuk megoldani. Ha most ebbe helyettesítjük be a 2-t… Nem túl meglepő módon az jön ki, hogy 1. Mondjuk, jobb lenne, ha az jönne ki, hogy 5. Hát, ezen könnyen lehet segíteni. Ezzel megalkottuk azt a polinom-függvényt, ami 1-ben és 4-ben nullát vesz föl, 2-ben pedig a függvényérték 5. És végül itt jön az a polinom-függvény, ami 1-ben és 2-ben nulla, 4-ben pedig 1-et vesz föl. Eddig ott járunk, hogy 1-ben és 2-ben nulla. De 4-ben sajnos… Hát nem baj, akkor jön megint az előző trükk. És ha most helyettesítjük be a 4-et… Akkor már az jön ki, hogy 1. És az pont jó is. Nézzük, mi történik, ha ezt a három polinomot összeadjuk. Az így kapott polinom éppen azt tudja, amit kell. 1-ben 3-at vesz föl, 2-ben 5-öt, és 4-ben 1-et. Lássunk még egy ilyet. Gyártsunk egy olyan polinom-függvényt, ami 1-ben 4-et, 2-ben 3-at és 4-ben 2-t vesz föl. Az első polinom a másik két helyen nulla… ha pedig x1-et helyettesítjük be, akkor 4-et kall kapnunk. Az második polinom is a másik két helyen nulla… és x2-ben 3-at kell kapnunk. Végül itt jön a harmadik polinom. Az első két helyen nullát vesz föl… ha 4-et helyettesítünk bele, akkor pedig 2-t. Az interpolációs polinomok világában ez a módszer az egyik legegyszerűbb. És úgy hívják, hogy Lagrange-féle interpolációs polinom. Most pedig lássuk, mi történik akkor, ha nem három, hanem négy pont van. Gyártsunk egy olyan polinom-függvényt, ami 1-ben 3-at, 2-ben 6-ot, 4-ben 2-t és 5-ben 4-et vesz föl. Először egy olyan polinomot fogunk gyártani, ami a másik három helyen nulla… és 1-ben pedig 3-at vesz föl. Aztán itt jön ez, ami 2-ben 6-ot vesz föl, a másik három helyen pedig nullát. Végül még kellenek nekünk ezek is. Azt a polinomot, amely x1-ben y1-et, x2-ben y2-t és így tovább xn-ben yn értéket vesz föl általánosan így tudjuk legyártani: Ennek a polinomnak a fokszáma n-1 és Lagrange-féle interpolációs polinomnak nevezzük. A képlet így első ránézésre megjegyezhetetlennek tűnik… de azért van remény. Itt az első tagban pont az x1-es tényező hiányzik. Ez a fura jel itt azt jelenti, hogy produktum, vagyis össze kell szorozni. Az n-edik tagban pedig az xn-es tényezők hiányoznak. Na, és ezek vannak összeadva 1-től n-ig. Hát ez csodás. De ami még ennél is csodálatosabb, hogy nem csak Lagrange-féle interpolációs polinomok léteznek.
Most egy nagyon vicces dolgot fogunk csinálni. Egy olyan polinomot fogunk gyártani, ami előre megadott pontokon megy át. Ezeket a polinomokat interpolációs polinomnak nevezzük. Íme, itt vannak a pontok. Vagy épp ezek. Vagy ezek. A dolog lényege, hogy bárhol lehetnek, és bármennyi. Minél több pontunk van, a polinom fokszáma annál nagyobb lesz. Kezdetnek most elég ez a három. Azt a polinom-függvényt fogjuk megalkotni, ami 1-ben 3-at vesz föl… 2-ben 5-öt… és 4-ben 1-et. Először egy olyan polinomot fogunk gyártani, ami 1-ben 3-at vesz föl és a másik két helyen nullát. Ehhez mindössze annyit kell megértenünk, hogy ez a polinom: Itt nulla. Meg itt… Meg itt, meg itt. És, ha azt szeretnénk, hogy még 6-ban is nulla legyen… Hát, éppen arról is lehet beszélni. Az a polinom-függvény, ami 1-ben 3-at vesz föl és a másik két helyen nullát, valahogy így fog kinézni. De sajnos van egy kis gond. Ha behelyettesítjük az 1-et… akkor nem jön ki a 3. Eddig jó. Most gyártani fogunk egy másik polinom-függvényt, ami 1-ben és 4-ben nulla… De ha 2-t helyettesítünk bele, akkor van egy kis gond. Nem az jön ki, ami nekünk kéne. Ezt a kis problémát így tudjuk megoldani. Ha most ebbe helyettesítjük be a 2-t… Nem túl meglepő módon az jön ki, hogy 1. Mondjuk, jobb lenne, ha az jönne ki, hogy 5. Hát, ezen könnyen lehet segíteni. Ezzel megalkottuk azt a polinom-függvényt, ami 1-ben és 4-ben nullát vesz föl, 2-ben pedig a függvényérték 5. És végül itt jön az a polinom-függvény, ami 1-ben és 2-ben nulla, 4-ben pedig 1-et vesz föl. Eddig ott járunk, hogy 1-ben és 2-ben nulla. De 4-ben sajnos… Hát nem baj, akkor jön megint az előző trükk. És ha most helyettesítjük be a 4-et… Akkor már az jön ki, hogy 1. És az pont jó is. Nézzük, mi történik, ha ezt a három polinomot összeadjuk. Az így kapott polinom éppen azt tudja, amit kell. 1-ben 3-at vesz föl, 2-ben 5-öt, és 4-ben 1-et. Lássunk még egy ilyet. Gyártsunk egy olyan polinom-függvényt, ami 1-ben 4-et, 2-ben 3-at és 4-ben 2-t vesz föl. Az első polinom a másik két helyen nulla… ha pedig x1-et helyettesítjük be, akkor 4-et kall kapnunk. Az második polinom is a másik két helyen nulla… és x2-ben 3-at kell kapnunk. Végül itt jön a harmadik polinom. Az első két helyen nullát vesz föl… ha 4-et helyettesítünk bele, akkor pedig 2-t. Az interpolációs polinomok világában ez a módszer az egyik legegyszerűbb. És úgy hívják, hogy Lagrange-féle interpolációs polinom. Most pedig lássuk, mi történik akkor, ha nem három, hanem négy pont van.
Gyártsunk egy olyan polinom-függvényt, ami 1-ben 3-at, 2-ben 6-ot, 4-ben 2-t és 5-ben 4-et vesz föl. Itt jön most egy másik módszer, ami első ránézésre bonyolultabbnak tűnik, mint a Lagrange-polinom... De második ránézésre kiderül, hogy könnyebb. Ezt a módszert Newton-interpolációnak hívják és a lényege a következő. Elkészítjük ezeket a Newton-együtthatókat. És most már csak ezekre lesz szükség. Ez a polinom pontosan megegyezik a Lagrange interpolációval keletkező polinommal. Viszont megvan az a kellemes tulajdonsága, hogy könnyebb összevonni. Hát ezt tudja a Newton-interpoláció.
Itt jön egy újabb módszer interpolációs polinomok gyártására. Ez a módszer abban különbözik az előző kettőtől, hogy az x1, x2, xn helyeken nem csak az eredeti polinom-függvény értékeit, hanem a deriváltjait is nézzük.
Gyártsunk például egy olyan f(x) polinom-függvényt, ami a következőket tudja:
A keresett polinom-függvény ötödfokú lesz.
Azért, mert hat interpolációs pont van megadva és a polinom fokszáma mindig eggyel kisebb, mint az interpolációs pontok száma.
Ezt a nagyon remek egyenletrendszert kell már csak megoldanunk, és kész is.
Az ilyen egyenletrendszereket megoldani rémesen unalmas.
Ezzel foglalkozik a lineáris algebra.
Megoldhatjuk például Gauss eliminációval, vagy elemi bázistranszformációval is.
És a megoldás…
Hát ezt tudja a csodálatos Hermite interpoláció.
És most lássuk, mire használhatnánk ezeket az interpolációs polinomokat, jóra vagy rosszra…
Kezdjük a rosszal.
Egy alagút tervezett nyomvonala 600 méteres tengerszintfeletti magasságban halad.
A kőzet, amelybe az alagutat fúrják gránit, de nem sokkal 600 méter felett egy vízbetörések miatt veszélyes dolomitréteg húzódik, amit az építkezés során szeretnének elkerülni.
Ha ugyanis vannak olyan szakaszok, ahol a dolomit benyúlik 600 méter alá…
akkor változtatni kell a terveken.
Négy helyen végeznek függőleges próbafúrásokat, hogy megállapítsák a geológiai szerkezetet.
A fúrásokból vett minta alapján a dolomitréteg ezeken a tengerszintfeletti magasságokon kezdődik:
Egy interpolációs polinom segítségével megpróbáljuk meghatározni, hogy milyen magasan húzódik a dolomitréteg alsó határa.
Használjuk, mondjuk a Newton-interpolációt.
Már jön is.
A négy adatból kapott interpolációs polinom:
Ha ugyanis vannak olyan szakaszok, ahol a dolomit benyúlik 600 méter alá…
akkor változtatni kell a terveken.
Négy helyen végeznek függőleges próbafúrásokat, hogy megállapítsák a geológiai szerkezetet.
A fúrásokból vett minta alapján a dolomitréteg ezeken a tengerszintfeletti magasságokon kezdődik:
Egy interpolációs polinom segítségével megpróbáljuk meghatározni, hogy milyen magasan húzódik a dolomitréteg alsó határa.
Használjuk, mondjuk a Newton-interpolációt.
Már jön is.
A négy adatból kapott interpolációs polinom:
Az interpolációs polinom alapján feltételezhető, hogy a dolomitréteg ezen a 15 kilométeres szakaszon nem nyúlik 600 méteres tengerszintfeletti magasság alá.
Hogyha az alagút fúrása közben tudni szeretnénk, hogy várhatóan mekkora magasságban kezdődik a dolomitréteg...
Egyszerűen csak be kell helyettesíteni az interpolációs polinomba, hogy éppen hol tartunk a fúrással:
Ha ezt elég sok helyen kiszámoljuk, akkor azt is meg tudjuk mondani, hogy az ötödik és a tizenötödik kilométer között hol lesz a legalacsonyabban a dolomitréteg határa.
De mielőtt megalapítanánk az alagútfúró vállalkozásunkat, azért nem árt, ha tudjuk, hogy erre a négy pontra még jópár polinom-függvény illeszthető.
És bizony lehet köztük olyan is, amely az alagút számára végzetes.
Azt, hogy az interpolációs polinom mennyire tér el a valódi helyzettől, az interpoláció hibájának nevezzük.
Nézzük, hogyan működik az interpolációs polinomok hibabecslése.
Számoljuk ki egy másodfokú interpolációs polinom segítségével, hogy mennyi
Ehhez készítenünk kell egy olyan interpolációs polinomot, aminek a grafikonja a logaritmusfüggvény görbéjét rajzolja ki, legalábbis a 3-hoz közeli x-ekre.
A másodfokú interpolációs polinomhoz három alappontra lesz szükség.
Itt is jön az első:
Hát igen, ha már esetleg elhalványultak a logaritmussal kapcsolatos emlékeink…
Ez azt mondja meg, hogy 2-t hányadikra kell emelni, hogy 1-et kapjunk.
Aztán itt jön ez is:
Meg ez:
Na, erről mondjuk fogalmunk sincs, hogy mennyi…
Hiszen éppen ezt akarjuk kiszámolni.
Hát jó, akkor itt van helyette ez:
Ezek lesznek az alappontok.
Az interpolációs polinomot bármelyik módszerrel készíthetjük.
Most legyen például a Lagrange.
Ez a polinom azt tudja, hogy 1-ben, 2-ben és 4-ben pontosan ugyanazokat az értékeket veszi föl, mint a .
Máshol azért már adódnak problémák…
Negatív x-ekre például a logaritmus függvény grafikonja nem pont ilyen.
De minket most csak a 3-hoz közeli x-ekre érdekel a dolog.
Nézzük meg mi történik, ha behelyettesítjük a 3-at.
A kérdés az, hogy mekkora a hiba.
Vagyis a kapott eredmény mennyivel tér el a valódi –tól.
Szerencsére éppen itt jön erre egy képlet.
Ha az f függvény n+1-szer deriválható az x1, x2, … xn és x által kifeszített I intervallumon, akkor az interpoláció hibája:
Ez egy igazán remek képlet, próbáljuk meg értelmezni.
Most éppen n=3 tehát szükség lesz az f függvény negyedik deriváltjára.
Meg is van a negyedik derivált, amibe ezt a bizonyos –t kell behelyettesítenünk.
Fogalmunk sincs, hogy pontosan mennyi, de az biztos, hogy
Ez alapján pedig tudunk egy becslést adni erre: