Java - algoritmy interpolácie

Základy informatiky - jazyk Java

---

---

Platforma Java - prehľad

Úvod do programovania v jazyku Java

Java - objektovo orientovaný prístup

Vzorové príklady:

Prvé programy v Jave

Vzorové triedy v Jave

Java applety

Java - desktopové aplikácie

Java - implementácia numerických algoritmov

>Java - algoritmy hľadania nulových miest
>Java - algoritmy numerického derivovania
>Java - algoritmy numerického integrovania
>Java - algoritmy aproximácie
>Java - algoritmy interpolácie

Java - triedy geometrických tvarov

Pokročilé témy:

Základy práce s NetBeans IDE a vývoj modulov

Interpolácia je matematický algoritmus, kde máme k dispozícii n bodov v rovine XY a úlohou je nájsť taký polynóm, ktorý prechádza cez všetky zadané body. Pri n bodoch dokážeme vypočítať polynóm stupňa n-1. Všeobecný tvar polynómu je:

[math]f(x)=a_nx^n+a_{n+1}x^{n-1}+...+a_1x+a_0[/math]

Interpolačný polynóm

Najpriamejším (aj keď nie najjednoduchším) spôsobom ako vypočítať interpolačný polynóm je jednoducho dosadiť známe body do predchádzajúcej rovnice. Vznikne nám tak sústava n rovníc o n neznámych. Majme nasledujúce body:

Tabuľka vstupných bodov pre interpoláciu

x	1	2	5	8	10
y	0	4	7	5	2

Pre tieto body dostávame sústavu rovníc:

[math] \begin{array}{lcr} 0=a_4 1^4 + a_3 1^3 + a_2 1^2 + a_1 1^1 + a_0 1^0 \\ 4=a_4 2^4 + a_3 2^3 + a_2 2^2 + a_1 2^1 + a_0 2^0 \\ 7=a_4 5^4 + a_3 5^3 + a_2 5^2 + a_1 5^1 + a_0 5^0 \\ 5=a_4 8^4 + a_3 8^3 + a_2 8^2 + a_1 8^1 + a_0 8^0 \\ 2=a_4 10^4 + a_3 10^3 + a_2 10^2 + a_1 10^1 + a_0 10^0 \\ \end{array} [/math]

Čo môžeme zapísať ako maticovú rovnicu:

[math] \begin{pmatrix} 1^4 & 1^3 & 1^2 & 1^1 & 1^0 \\ 2^4 & 2^3 & 2^2 & 2^1 & 2^0 \\ 5^4 & 5^3 & 5^2 & 5^1 & 5^0 \\ 8^4 & 8^3 & 8^2 & 8^1 & 8^0 \\ 10^4 & 10^3 & 10^2 & 10^1 & 10^0 \\ \end{pmatrix} \begin{pmatrix} a_0\\ a_1\\ a_2\\ a_3\\ a_4\\ \end{pmatrix}= \begin{pmatrix} 0\\ 4\\ 7\\ 5\\ 2\\ \end{pmatrix} [/math]

Túto maticovú rovnicu môžeme riešiť napríklad Gausovou eliminačnou metódou.

Lagrangeov tvar interpolačného polynómu

Pre dané body existuje iba jeden itnerpolačný polynóm. Rozdiel je len v spôsobe ako sa tento polynóm vypočíta. Lagrangeov interpolačný polynóm využíva špeciálny tvar polynómov, ktoré sa nazývajú Lagrangeove polynómy. Pre Langrangeov tvar intepolačného polynómu platia nasledujúce vzťahy:

[math]L(x) = \sum_{j=0}^{n} y_j \ell_j(x) [/math]

[math]\ell_j(x) = \prod_{i=0,\, i\neq j}^{n} \frac{x-x_i}{x_j-x_i} = \frac{(x-x_0)}{(x_j-x_0)} \cdots \frac{(x-x_{j-1})}{(x_j-x_{j-1})} \frac{(x-x_{j+1})}{(x_j-x_{j+1})} \cdots \frac{(x-x_{n})}{(x_j-x_{n})}[/math]

Kde L(x) je výsledný intepolačný polynóm a [math]\ell_j(x)[/math] sú Lagrangeove interpolačné polynómy (stupňa j).

Riešenie v jazyku Java

Triedu Extrapolacia.java doplníme o nasledujúcu metódu:

    public double interpolacia(double x) {
        double lag, lag_pol = 0;
        int j, i;
        for (j = 0; j < this.body.size() ; j++) {
            lag = 1.0;
            for (i = 0; i < this.body.size() ; i++) {
                if (i == j) {
                    continue;
                }
                lag *= (x - this.body.get(i).x) / (this.body.get(j).x - this.body.get(i).x);
            }
            lag_pol += this.body.get(j).y * lag;
        }
        return lag_pol;

    }