NumMod 1 het 9

date: 2024.04.15

Hermite-interpoláció

Eddig az $x_0,\dots ,x_n$ pontokban csak a függvény értéket írtuk elő.
Lehetséges általánosítása ennek a feladatnak, ha nem csak a függvény értékeket írjuk elő, hanem a pontbeli deriváltakat is.
A legegyszerűbb formája ennek a feladatnak, amikor csak minden pontban az első deriváltat írjuk elő, de lehet ezt általánosabban is. Előírhatjuk minden pontban a magasabbrendű deriváltakat is, de ilyenkor elő kell írnunk a legmagasabb deriváltig bezárólag az összes többit. Továbbá, nem feltétlenül kell minden pontban megadni az összes deriváltat.
Tegyük fel, hogy az $x_k$ alappontban az $m_k$-adikig írjuk elő az összes deriváltat, azaz adottak $f_k,f_k^{(1)},\dots ,f_k^{(m_k)}$
Összesen $N=n+1+m_0+m_1+\cdots +m_k$ feltétel van.
Ezek alapján azt várjuk, hogy $N-1$-ed fokú polinom egyértelműen illeszthető a pontokra.
Ez így is van!

Állítás

$\exists !H\in P_{N-1}$ amelyre $\forall k=0,\dots ,n$ $\forall i=0,\dots ,m_k$ számokra $H^i(x_k)=f_k^{(i)}$

Ezt a polinomot Hermite-féle interpolációs polinomnak nevezzük.
Speciálisan, ha $m_k=1$ minden $k$-ra, akkor úgy nevezik, hogy Hermite-Fejér-interpoláció. Ekkor az interpolált polinom fokszáma: $N=2n+2-1=2n+1$

Spline-interpoláció

Eddig a pontokra egyetlen polinomot illesztettünk.
Hátránya ennek a megközelítésnek az, hogy ha sok pont van, akkor az illesztett polinom magas fokszámú lesz. Ekkor a deriváltja is magas fokszámú és ennek a szintén magas fokszámú polinomnak sok zérushelye van, ami azt mondja az eredeti polinomról, hogy sok helyen vízszintes a deriváltja. Tehát nagyon hullámos lesz az illesztett polinom sok pont esetén.

Egy megoldás erre a problémára lehet az, hogy ne egy polinomot próbáljunk illesztetni az összes pontra, hanem szakaszonként más-más polinomot illesszünk és ezeket az alacsony fokszámú polinomokat ragasszuk össze. Ebből az ötletből jön a Spline-interpoláció.

Legegyszerűbb, amikor szakaszonként lineáris-interpolációt alkalmazunk és így kapunk egy töröttvonalat, ami összeköti az adatpontjainkat.

1. Lineáris spline-interpoláció

Az $[x_{k-1},x_k]$ szakaszon

$$s_k(x)=f_{k-1}\cdot \frac{x-x_k}{x_{k-1}-x_k}+f_k\cdot \frac{x-x_{k-1}}{x_k-x_{k-1}}$$

a fenti képlet adja meg, hogy milyen értékeket fog felvenni a spline függvény az $x\in [x_{k-1},x_k]$ pontokban.

A teljes spline-függvény viszont a következőképpen néz ki:

$$s(x)=\{\begin{array}{ll}{s}_1(x)& x\in [x_0,x_1]\\ s_2(x)& x\in [x_1,x_2]\\ ⋮& \\ s_n(x)& x\in [x_{n-1},x_n]\end{array}$$

Nyílvánvalóan az $s$ spline-függvény folytonos az $[x_0,x_{{}_n}]$ intervallumon, viszont az alappontokban csúcsos, tehát nem differenciálható ezekben a pontokban.

Kiküszöbölése a nemdifferenciálhatóságnak az, hogy magasabbfokú interplolációkat használunk szakaszonként.

2. Kvadratikus spline-interpoláció

Az $[x_{k-1},x_k]$ szakaszon $s_k\in P_2$ legyen.
Ahhoz, hogy másodfokú polinomot illesszünk szakaszonként elő kell írnunk a függvényértékeken túl a pontbeli deriváltakat is ($s^{\prime }(x_0)=d_0$)

1. Alkalmazzunk Hermite-interpolációt az $[x_0,x_1]$ szakaszon:

$$\begin{array}{rl}{s}_1\in P_1:& s_1(x_0)=f_0\\ & s_1^{\prime }(x_0)=d_0\\ & s_1(x_1)=f_1\end{array}$$

2. Hermite-interpoláció az $[x_1,x_2]$ intervallumon:

$$\begin{array}{rl}{s}_2\in P_2:& s_2(x_1)=f_1\\ & s_2(x_2)=f_2\\ & s_2^{\prime }(x_1):=s_1^{\prime }(x_1)\end{array}$$

3. Hasonlóképpen folytatjuk a további $[x_{k-1},x_k]$ intervallumokon.

Ezzel a módszerrel $s$ folytonosan differenciálható lesz.

Megjegyzés: Létezik trigonometrikus-interpoláció is.
Tegyük fel, hogy $f$ periodikus függvény $2\pi$ intervallum hosszal, és a következő pontokbab ismerjük a függvény értékeket a $[0,2\pi ]$ intervallumnak az összes $x_k=\frac{k}{n+1}\cdot 2\pi$ pontjában.

Keressük azt a

$$t_m(x)=a_0+\sum _{j=1}^m{a}_k\cdot \cos (jx)+b_k\cdot \sin (jx)$$

trigonometrikus polinomot, amelyre az igaz, hogy $t_m(x_k)=f_k$ minden $k$-ra.
$a_0,a_k,b_k$ együtthatókat diszkrét Fourier-együtthatóknak nevezzük.

Legkisebb négyzetek módszere

Felmerülhet az a baj, ha sok pont egy kupacban van és nagyjából egy alakban és pontosan szeretnénk ezekre egy polinomot illesztetni, akkor feleslegesen magasfokú lesz az illesztett polinom és nem is fogja megragadni a pontok alakjának a lényegét.
Ennek orvosolására próbáljuk meg nem pontosan illeszteni polinomot a pontokra, hanem csak legyen az a célunk, hogy minden ponthoz a legközelebb haladjonaz illesztett polinomunk.

Legyenek adva az $(x_k,f_k)$ pontok.
Olyan $P$ polinomot keresünk, amelyre:

1. Adott fokszámú (ezt mi döntjük el).
2. Globálisan az összes ponthoz a legközelebb halad.

Figyelem, ezt nem nevezzük interpolációnak, mert nem megy át minden alapponton az illesztett polinom!

Q.: Hogyan mérjük a költséget?

Lehetne azt csinálni, hogy a költség a következő: $\sum |f_k-P(x_k)|$
Ezzel az lesz a probléma, hogy nem deriválható, továbbá szeretnénk azt is, hogy nagy eltérés nagy hibát jelezzen.

Helyette legyen a költség függvényünk a következő: $\sum (f_k-P(x_k){)}^2$

Tegyük fel, hogy $p\in P_1$ polinomot akarunk illeszteni, tehát $p(x)=c_0+c_{1}x$ alakú függvényt szeretnénk illeszteni.
Hogyan kell megválasztani $c_0$ és $c_2$ együtthatókat, hogy a következő kifejezés minimális legyen:

$$\sum _{k=0}^n(f_k-c_0-c_1{x}_k{)}^2$$

Itt az $x_k,f_k$ adottak, és a $(c_0,c_1)$ számoktól függő

$$F(c_0,c_1):=\sum _{k=0}^n(f_k-c_0-c_1{x}_k{)}^2$$

${\mathbb{R}}^2\to \mathbb{R}$ függvény minimum helyét keressük.
Nézzük meg, hogy hol nulla a gradiens vektora.

$$\frac{\partial F}{\partial c_0}=\sum _{k=0}^{n}2(f_k-c_0-c_1{x}_k)\cdot (-1)=0$$ $$\frac{\partial F}{\partial c_1}=\sum _{k=0}^{n}2(f_k-c_0-c_1{x}_k)\cdot (-x_k)=0$$

A következő egyenletrendszerre jutunk:

$$\begin{array}{rl}\sum _{k=0}^n(f_k-c_0-c_1{x}_k)& =0\\ \sum _{k=0}^n(f_k{x}_k-c_0{x}_k-c_1{x}_k^2)& =0\end{array}$$

Ez egy lineáris algebrai egyenletrendszer $(c_0,c_1)$-re.
Mátrix alakban:

$$\left[\begin{array}{cc}n+1& \sum x_k\\ \sum x_k& \sum x_k^2\end{array}\right]\cdot \left[\begin{array}{c}{c}_0\\ c_1\end{array}\right]=\left[\begin{array}{c}\sum f_k\\ \sum f_k{x}_k\end{array}\right]$$

Ezt az alakot már könnyen meg lehet oldani számítógéppel és kapunk egy-egy értéket $c_0$ és $c_1$-re, amiből megkapjuk a $p=c_0+c_{1}x$ illesztett polinomot.
Megjegyzés: Ha $n\ge 1$, akkor egyértelműen létezik megoldás és ez tényleg minimum hely lesz.
Megjegyzés: Ha $N$-ed fokú polinomot szeretnénk illeszteni, akkor $(N+1)$ ismeretlenes lineáris algebrai egyenletrendszert kapunk, aminek a megoldása megadja az illesztett polinom együtthatóit.

Közelítő integrálás

Feladat: Adott egy $f\in R[a,b]$ függvény, melynek szeretnénk az integrálját meghatározni, azaz ${\int }_a^{b}f=?$
Tudjuk, ha $f$-nek létezik $F$ primitív függvénye, akkor ${\int }_a^{b}f=F(b)-F(a)$

Gyakran $F$-et nem tudjuk meghatározni, ekkor felmerül a megoldás, hogy hogyan tudjuk közelítőleg integrálni a függvényt.

Ötlet: ${\int }_a^{b}f$ geometriai jelentése a görbe alatti előjeles terület.

Közelítsük a görbe alatti területet egyszerűbb alakzat területével. Ebből az ötleből kapjuk az alapvető kvadratúraformulákat.
Vezessük be az intervallum hosszára következő változót: $h=b-a$

1. Középponti formula
   $c:=\frac{a+b}{2}$ pontban megnézzük a függvényértéket.
   $k(f):=h\cdot f(c)$

2. Trapéz formula
   Megnézzük a $(a,b,f(b),f(a))$ pontok által meghatározott trapéz területét.
   $t(f):=h\cdot \frac{f(a)+f(b)}{2}$

related: NumMod 1