- Mátrixok és vektorok
- Vektorok, egyenesek és síkok egyenletei
- Vektorterek, független és összefüggő vektorok
- Lineáris egyenletrendszerek, mátrixok rangja és inverze
- Determináns, adjungált, kvadratikus alakok
- Sajátérték, sajátvektor, sajátfelbontás
- Lineáris leképezések
- Síkbeli és térbeli leképezések és mátrixaik
- Egyenletrendszerek optimális megoldása, pszeudoinverz
- Lineáris programozás alapok
- Vektornorma, mátrixnorma, mátrixok kondíciószáma
- Ortogonális mátrixok, Fourier-együtthatók, Gram-Schmidt ortogonalizáció
- Mátrixok LU-felbontása és QR-felbontása
- Iterációs módszerek egyenletrendszerek megoldására
- Komplex számok
- Polinomok
- Interpolációs polinomok
- Oszthatóság
- Euklideszi algoritmus, Diofantoszi egyenletek
- Kongruenciák, Euler-Fermat tétel
- 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$.
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.
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.
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: