Geometrie/Lagrangeova interpolace

Popis

Chceme-li aproximovat funkci, která je dána svými hodnotami v $n+1$ bodech $x_{i},i=0,1,...,n$ (body $x_{i}$ nazýváme uzly interpolace), a požadujeme-li, aby aproximace procházela zadanými body, použijeme aproximaci interpolačním polynomem. Aproximace nám potom poslouží k získání přibližné hodnoty zadané funkce v libovolném bodě intervalu $<x_{0},x_{n}>$ .

Máme-li zadány hodnoty funkce $f$ v $n+1$ různých bodech, tzn. máme zadáno $n+1$ tzv. interpolačních podmínek pro polynom, je zřejmé, že stupeň hledaného polynomu bude $n$ . Lze ukázat, že mezi všemi polynomy nejvýše $n$ -tého stupně existuje právě jeden, který je interpolačním polynomem pro zadanou funkci. Pro určení interpolačního polynomu existuje několik postupů, ale je třeba si uvědomit, že pro zadanou funkci všechny postupy určí stejný polynom.

Langrangeův interpolační polynom (čteme lagrándžův) je jedním ze známějších a také snadných způsobů interpolace funkce zadané pouze v diskrétních bodech.

Nechť tedy máme dáno n+1 bodů, přes které funkce prochází. Pak můžeme pomocí níže popsané rovnice nalézt interpolační funkci, která se původní rovnici snaží co nejvíce přiblížit.

Vyjádření

Lagrangeův interpolační polynom se dá zapsat rovnicí

$P_{n}(u)=\sum _{i=0}^{n}P_{i}L_{i}^{n}(u),$

kde

$L_{i}^{n}(u)=\prod _{j=0,j\neq i}^{n}{\frac {u-u_{j}}{u_{i}-u_{j}}}$

kde $P_{i}$ jsou zadané funkční hodnoty.

Vlastnosti

Lagrangeův interpolační vzorec má význam především pří teoretickém zkoumání vlastností interpolačních polynomů. Pro praktické počítání ale není příliš výhodný. Například když se rozhodneme přidat další uzlový bod, musíme znovu přepočítat všechny polynomy $L_{i}$ . V takovém případě je výhodnější použít jiný interpolační algoritmus.

Nevýhodou interpolačních polynomů je, že neplatí čím více bodů máme zadáno, tím přesnější funkci dostáváme. Pro jakoukoliv volbu uzlů interpolace vždy existuje spojitá funkce, pro kterou interpolační proces nekonverguje stejnoměrně. Navíc se při větším počtu bodů interpolační funkce na koncích více „vlní“, což v řadě případů nemusí být pro interpolaci zrovna nejlepší.

Algoritmizace

Metoda Lagrange počítá hodnotu Lagrangova polynomu zadaného stupně pro daný index a nezávislý parametr t. Uveďme si ještě nějaké poznámky k proměnným a použitým metodám.

Vector: třída popisující vektor,
Richpoint: třída popisující bod,
ctrlPoly: body řídícího polygonu.

private double Lagrange(int stupen,int index, double t) {	
 double ret=1;
 for (int j=0;j<stupen;j++) {
  if (j!=index) ret*=(t-j)/(index-j);
 }
 return ret;
}

Počítá bod na křivce pomocí Lagrangova polynomu

public override Vector GetPoint(double t) {
 Vector ret = new Vector();
 for (int i=0;i<ctrlPoly.Count;i++) {
  ret+=Lagrange(ctrlPoly.Count,i,t)*((RichPoint)ctrlPoly[i]).Locate;
 }
 return ret;
}

Autoři

Tento text vypracovali studenti Univerzity Palackého v Olomouci katedry Matematické informatiky jako zápočtový úkol do předmětu Počítačová geometrie.