Juraj na 20:20, 16. august 2010

2010-08-16T20:20:03Z

Juraj na 19:05, 17. apríl 2010

2010-04-17T19:05:05Z

Juraj: Vytvorená stránka „Kategória:Študijné materiály Kategória:Programovanie Kategória:Informatika {{Draft}} {{Skripta programovanie}} [[Súbor:polynomicka_iterpolacia.png|thumb…“

2010-04-12T18:54:32Z

Vytvorená stránka „Kategória:Študijné materiály Kategória:Programovanie Kategória:Informatika {{Draft}} {{Skripta programovanie}} [[Súbor:polynomicka_iterpolacia.png|thumb…“

Nová stránka

[[Kategória:Študijné materiály]]
[[Kategória:Programovanie]]
[[Kategória:Informatika]]
{{Draft}}
{{Skripta programovanie}}

[[Súbor:polynomicka_iterpolacia.png|thumb|left|Červené body označujú vstupné dáta (xk,yk), modrá krivka je interpolačný polynóm]]

Polynomická interpolácia je metóda<ref>http://en.wikipedia.org/wiki/Polynomial_interpolation</ref>, pri ktorej definujeme polynóm, ktorý obsahuje všetky vstupné uzlové body.

Majme množinu n+1 vstupných bodov (''x''''i'',''y''''i'') kde žiadne dve hodnoty ''x''''i'' nie sú rovnaké. Hľadáme polynóm ''p'' stupňa najviac ''n'', pre ktorý platí:
:<math>p(x_i) = y_i,\; i=0,\ldots,n.</math>

==Lagrangeov interpolačný polynóm==

Lagrangeov polynóm<ref>http://sk.wikipedia.org/wiki/Lagrangeov_polyn%C3%B3m</ref>, pomenovaný podľa Josepha Louisa Lagrangea, je v numerickej matematike interpolujúci polynóm pre danú množinu bodov v Lagrangeovom tvare.

''Je povšimnutia hodné, že pre danú množinu bodov existuje len jeden polynóm (najmenšieho možného stupňa), ktorý interpoluje dané body. Preto je správnejšie o Lagrangeovom polynóme hovoriť ako o Lagrangeovom tvare interpolujúceho polynómu, než o Lagrangeovom interpolujúcom polynóme.''

===Definícia===
Nech je daná množina ''n'' + 1 bodov

:<math>(x_0, y_0),\ldots,(x_j, y_j),\ldots,(x_n, y_n)</math>

kde žiadne dve hodnoty <math>x_j</math> nie sú rovnaké. Potom '''interpolujúci polynóm v Lagrangeovom tvare''' pre túto množinu bodov je lineárna kombinácia

:<math>L(x) := \sum_{j=0}^{n} y_j \ell_j(x)</math>

Lagrangeových bázických polynómov

:<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>

Je povšimnutia hodné, že za predpokladu, že žiadne dve hodnoty <math>x_i</math> nie sú rovnaké (a to ani nemôžu byť, keďže by daná úloha nedávala zmysel), platí <math>x_j - x_i \neq 0</math>, čiže daný výraz je vždy dobre definovaný.

'''Grafická reprezentácia'''
[[Obrázok:Lagrange polynomial.svg|thumb|Grafická reprezentácia Lagrangeovho polynómu]]

Na obrázku je kubický Lagrangeov interpolujúci polynóm ''L''(''x'') (zobrazený čiernou farbou) pre body (−9, 5), (−4, 2), (−1, −2) a (7, 9). Tento polynóm je súčtom konštantných faktorov bázických polynómov y0''ℓ''0(''x''), y1''ℓ''1(''x''), y2''ℓ''2(''x'') a y3''ℓ''3(''x''). Interpolujúci polynóm prechádza cez všetky štyri body, každý z bázických polynómov prechádza jedným z daných bodov a na ''x''-ových súradniciach daných ostatnými bodmi má hodnotu 0.

===Implementácia v jazyku C===
'''Návrh vhodnej dátovej štruktúry'''

Pre reprezentáciu vstupných uzlových bodov si vytvorme štruktúru ''Bod'':
<source lang="c">
struct Bod{
double x,y;
};
</source>
kde ''x'' a ''y'' predstavujú x-ovú a y-ovú súradnicu bodu v rovine. Na reprezentáciu všetkých vstupných bodov si vytvorme pole štruktúr typu Bod o veľkosti ''n'' (''n'' je počet vstupných uzlových bodov).
<source lang="c">
Bod *body=new Bod[n];
</source>

<source lang="c" line>
struct Bod{
double x,y;
};

double LagrangeInterpol(Bod *data, int n, double x)
{ double lag,lag_pol=0;
int j,i;
for(j=0;j<n;j++)
{ lag=1.0;
for(i=0;i<n;i++)
{ if(i==j) continue;
lag*=(x-data[i].x) / (data[j].x-data[i].x) ;
}
lag_pol+= data[j].y*lag;
}
return lag_pol;
}

int main()
{ int n,i;
Bod *body,A;
cin>>n;
body=new Bod[n];
for(i=0;i<n;i++)
{ cin>>body[i].x; // x-ova suradnica
cin>>body[i].y; // y-ova suradnica
}
cout<<"zadaj bod zaujmu";
cin>>A.x;
A.y=LagrangeInterpol(body,n,A.x);
cout<<"Hodnota funkcie v bode"<< A.x<<" = "<< A.y<<endl;
}
</source>

==Newtonov interpolačný polynóm==
===Definícia===
Nech je daná množina ''n'' + 1 bodov

:<math>(x_0, y_0),\ldots,(x_j, y_j),\ldots,(x_n, y_n)</math>

kde žiadne dve hodnoty <math>x_j</math> nie sú rovnaké. Potom '''interpolujúci polynóm v Newtonovom tvare''' pre túto množinu bodov je lineárna kombinácia

:<math>N(x) := \sum_{j=0}^{n} a_{j} n_{j}(x)</math>

'''Newtonových bázických polynómov''' definovaných ako

:<math>n_j(x) := \prod_{i=0}^{j-1} (x - x_i)</math>

a koeficienty aj sú definované ako:

:<math>a_j := [y_0,\ldots,y_j]</math>

kde

:<math>[y_0,\ldots,y_j]</math>

je zápis rozdielových diferencií.

'''Newtonov polynóm''' môžeme zapísať ako

:<math>N(x) = [y_0] + [y_0,y_1](x-x_0) + \cdots + [y_0,\ldots,y_k](x-x_0)(x-x_1)\cdots(x-x_{k-1}).</math>
alebo
:<math>\begin{align}
& N\left( x \right)={{f}_{0}}+\sum\limits_{j=1}^{n}{{{n}_{j-1}}\left( x \right)\left[ {{x}_{0}},{{x}_{1}},...,{{x}_{j}} \right]} \\
& {{n}_{j}}\left( x \right)=\prod\limits_{i=0}^{j}{\left( x-{{x}_{i}} \right)} \\
\end{align}</math>

'''Rozdielové diferencie''' môžeme vyjadriť nasledovne:

Rozdielová diferencie <math>f\left[ {{x}_{0}},{{x}_{1}},{{x}_{2}},...,{{x}_{n}} \right]</math>, označované aj ako <math>\left[ {{x}_{0}},{{x}_{1}},{{x}_{2}},...,{{x}_{n}} \right]</math> vypočítaná z n+1 bodov <math>x_0, x_1, ..., x_n</math> funkcie ''f(x)'' je definovaná nasledovne:
:<math>f\left[ {{x}_{0}} \right]\equiv f\left( {{x}_{0}} \right)</math>
:<math>f\left[ {{x}_{0}},{{x}_{1}},...,{{x}_{n}} \right]=\frac{f\left[ {{x}_{0}},...,{{x}_{n-1}} \right]-f\left[ {{x}_{1}},{{x}_{2}},...,{{x}_{n}} \right]}{{{x}_{0}}-{{x}_{n}}}</math>

pre n>=1.

Prvé dve diferencie sú nasledovné:
:<math>f\left[ {{x}_{0}},{{x}_{1}} \right]=\frac{f\left( {{x}_{0}} \right)-f\left( {{x}_{1}} \right)}{{{x}_{0}}-{{x}_{1}}}</math>
:<math>f\left[ {{x}_{0}},{{x}_{1}},{{x}_{2}} \right]=\frac{f\left[ {{x}_{0}},{{x}_{1}} \right]-f\left[ {{x}_{1}},{{x}_{2}} \right]}{{{x}_{0}}-{{x}_{2}}}</math>

===Implementácia v jazyku C===
<source lang="c" line>
struct Bod{
double x,y;
};

double n_k(Bod *data,int j, double x)
{
double n_j=1;
for(int i=0;i<j;i++)
n_j*=(x-data[i].x);
return n_j;
}

double NewtonPol(Bod *data, int n,double x)
{
double val=0;
double *koef=new double[n];
for(int i=0;i<n;i++)
koef[i]=data[i].y;

for(int j=0;j<n-1;j++)
{ for(int i=n-1;i>j;i--)
koef[i]=(koef[i]-koef[i-1])/(data[i].x-data[i-j-1].x);
}
for(int i=0;i<n;i++)
val+=koef[i]*n_k(data,i,x);

delete koef;
return val;
}
int main()
{ int n,i;
Bod *body,A;
ifstream in;
in.open("body.txt");
in>>n;
body=new Bod[n];

for(i=0;i<n;i++)
{ in>>body[i].x; // x-ova suradnica
in>>body[i].y; // y-ova suradnica
}
A.x=1.5;
A.y=NewtonPol(body,n,A.x);
cout<<"V bode "<<A.x<<" ma Netonov iterpolacny polynom hodnotu "<<A.y;
}
</source>

==Zdroje a odkazy==
<references/>
*http://www.math.chytrak.cz/math/polynomy/lagrange.php
*http://mathworld.wolfram.com/DividedDifference.html

@@ Riadok 11: / Riadok 11: @@
 Majme množinu n+1 vstupných bodov (''x''<sub>''i''</sub>,''y''<sub>''i''</sub>) kde žiadne dve hodnoty ''x''<sub>''i''</sub>  nie sú rovnaké. Hľadáme polynóm ''p'' stupňa najviac ''n'', pre ktorý platí:
 :<math>p(x_i) = y_i,\;  i=0,\ldots,n.</math>
+__TOC__
+{{Cvicenie|Algoritmy numerickej interpolácie (riešené príklady)}}
 ==Lagrangeov interpolačný polynóm==

@@ Riadok 1: / Riadok 1: @@
-[[Kategória:Študijné materiály]]
+[[Kategória:Numerické algoritmy]]
 {{Draft}}
 {{Skripta programovanie}}

Algoritmy interpolácie - História úprav

Juraj na 20:20, 16. august 2010

Juraj na 19:05, 17. apríl 2010

Juraj: Vytvorená stránka „Kategória:Študijné materiály Kategória:Programovanie Kategória:Informatika {{Draft}} {{Skripta programovanie}} [[Súbor:polynomicka_iterpolacia.png|thumb…“