Modern numerikus módszerek
Bene Gyula
Eötvös Loránd Tudományegyetem, Elméleti Fizikai Tanszék
1117 Budapest, Pázmány Péter sétány 1/A
4. hét
Interpoláció egy dimenzióban
- Köbös spline interpoláció
Legyen
$$A=\frac{x_{j+1}-x}{x_{j+1}-x_j}$$
és
$$B=1-A=\frac{x-x_{j}}{x_{j+1}-x_j}$$
Ekkor az
$$y=Ay_j+By_{j+1}+\frac{1}{6}\left(A^3-A\right)(x_{j+1}-x_j)^2
y''_j+\frac{1}{6}\left(B^3-B\right)(x_{j+1}-x_j)^2 y''_{j+1}$$
harmadfokú polinom
- értéke $x=x_j$-ben $y_j$, $x=x_{j+1}$-ben $y_{j+1}$
- második deriváltjának az értéke $x=x_j$-ben $y''_j$, $x=x_{j+1}$-ben $y''_{j+1}$
Ezzel tehát az egyes $[x_j,x_{j+1}]$ intervallumok határán a függvény és
második deriváltjának folytonossága biztosított. Az $y''_j$ második deriváltak
értéke nincs megadva, azokat az első derivált folytonosságának követelményéből
kapjuk:
$$\frac{1}{6}(x_{j}-x_{j-1})y''_{j-1}+
\frac{1}{3}(x_{j+1}-x_{j-1})y''_{j}+ \frac{1}{6}(x_{j+1}-x_j)y''_{j+1}=
\frac{y_{j+1}-y_j}{x_{j+1}-x_j}-\frac{y_{j}-y_{j-1}}{x_{j}-x_{j-1}}$$
Ez $n$ pont esetén $n-2$ egyenlet az $n$ db $y''_j$ ismeretlenekre. Két
további feltételre van szükség, pl. $y'_1$ és $y'_n$ értékére, vagy $y''_1$ és
$y''_n$ értékére. Ha az utóbbi értékek nullák, természetes spline-ról
beszélünk. Az egyenletrendszer mátrixa tridiagonális.
- Lagrange-interpoláció, Neville-algoritmus
$$P_{12...n}=\sum_{j=1}^n \frac{\prod_{k=1, k\ne j}^n(x-x_k)}{\prod_{k=1, k\ne
j}^n(x_j-x_k)}y_j$$
a megadott $n$ db ponton keresztülmenő $n-1$-edfokú polinom. Legyen
$P_{i(i+1)(i+2)...(i+m)}$ az
$(x_i,y_i),\;(x_{i+1},y_{i+1}),\;...(x_{i+m},y_{i+m})$ pontokra
illeszkedő Lagrange interpoláló polinom. Érvényes a
$$P_{i(i+1)(i+2)...(i+m)}=\frac{x-x_{i+m}}{x_i-x_{i+m}}P_{i(i+1)(i+2)...(i+m-1)}+\frac{x_i-x}{x_i-x_{i+m}}P_{(i+1)(i+2)...(i+m)}$$
rekurzió, melynek ismételt alkalmazásával kapjuk végül $P_{12...n}$ értékét (Neville-algoritmus).
- Racionális törtfüggvény-interpoláció (Bulirsch és Stoer)
Legyen az $(x_i,y_i),\;(x_{i+1},y_{i+1}),\;...(x_{i+m},y_{i+m})$ pontokra
illeszkedő $R_{i(i+1)(i+2)...(i+m)}$ racionális törtfüggvény két olyan polinom
hányadosa, melyek fokszámainak összege éppen $m$, és a számláló fokszáma
egyenlő a nevezőjével (páros $m$), vagy eggyel kisebb a nevezőénél (páratlan
$m$). Érvényes a következő rekurzió, amely segítségével a
törtfüggvény-interpoláció értéke adott $x$-hez kiszámítható:
$$R_{i(i+1)(i+2)...(i+m)}=R_{(i+1)(i+2)...(i+m)}+\frac{R_{(i+1)(i+2)...(i+m)}-R_{i(i+1)(i+2)...(i+m-1)}}{\frac{x-x_i}{x-x_{i+m}}\left(1-\frac{R_{(i+1)(i+2)...(i+m)}-R_{i(i+1)(i+2)...(i+m-1)}}{R_{(i+1)(i+2)...(i+m)}-R_{(i+1)(i+2)...(i+m-1)}}\right)-1}$$
- Baricentrikus racionális interpoláció
$$R(x)=\frac{\sum_{j=0}^{n-1}\frac{w_j}{x-x_j}y_j}{\sum_{j=1}^{n}\frac{w_j}{x-x_j}}$$
Ha az $(x_k,x_{k+1})$ intervallumok átlagos hossza $h$, akkor $d$-edrendű
közelítéshez (amikor $\mathcal{O}\left(h^{d+1}\right)$ a hiba):
$$w_j=(-1)^j\sum_{i=j-d, \; 0\le i\le n-d}^j\left(\prod_{k=i,\;k\ne j}^{i+d}\frac{1}{x_j-x_k}\right)$$
bene@arpad.elte.hu