Lineární interpolace

Z Wikipedie, otevřené encyklopedie
Skočit na: Navigace, Hledání

Lineární interpolace je metoda prokládání křivek za použití lineárních mnohočlenů. Této metody se často využívá v matematice ( konkrétně v numerické analýze) a v početních aplikacích včetně počítačové grafiky. Jedná se o jednoduchou formu interpolace.

Lineární interpolace mezi dvěma známými body.[editovat | editovat zdroj]

Jsou dány dva červené body, modrá úsečka lineární interpolace mezi těmito body a hodnoty x a y nalezneme pomocí lineární interpolace.

Pokud jsou dány dva známé body souřadnicemi \scriptstyle(x_0,y_0) a \scriptstyle(x_1,y_1), lineární interpolace je přímka mezi těmito dvěma body. Pro hodnotu x je interval \scriptstyle(x_0, x_1). Hodnota y podél přímky je dána rovnicí

\frac{y - y_0}{y_1 - y_0} = \frac{x - x_0}{x_1 - x_0}

která může být odvozena geometricky z obrázku:

Vyřešením této rovnice pro y, která je neznámou v rovnici pro x dostaneme:

y = y_0 + (x-x_0)\frac{y_1 - y_0}{x_1-x_0}

Což je vzorec pro lineární interpolaci v intervalu \scriptstyle(x_0,x_1) mimo tento interval je vzorec shodný s lineární extrapolací.

Interpolace a skupina dat[editovat | editovat zdroj]

Skupina dat lineární interpolace (červené body) se skládá z částí lineárních spojovatelů (modré čáry).

Lineární interpolace je skupina referenčních bodů \scriptstyle(x_0, y_0),\, (x_1, y_1),\,\dots,\,(x_n, y_n) je definována jako spojení lineárních interpolantů mezi každou dvojicí referenčních bodů. Výsledkem je nesouvisle odvozená souvislá křivka.

Lineární interpolace a přiblížení[editovat | editovat zdroj]

Lineární interpolace se často používá k zjištění přibližné hodnoty nějaké funkce f za použití dvou známých hodnot této funkce v jiných bodech. Odchylka této přibližné hodnoty je definována jako:

R_T = f(x) - p(x) \,\!

P označuje lineární mnohočlennou interpolaci definovanou výše

p(x) = f(x_0) + \frac{f(x_1)-f(x_0)}{x_1-x_0}(x-x_0). \,\!

Toto může být dokázáno užitím Rolleho věty, která za podmínky, že f má souvislé deriváty (odvozeniny), je odchylka ohraničena:

|R_T| \leq \frac{(x_1-x_0)^2}{8} \max_{x_0 \leq x \leq x_1} |f''(x)|. \,\!

Jak můžete vidět, přiblížení mezi dvěma body dané funkce s druhou odvozeninou funkce, která je zaokrouhlená (přibližná). To je také intuitivně správně, čím více se funkce kroutí tím hůře se dělá zaokrouhlení s jednoduchou lineární interpolací.

Skupina dat lineární interpolace (červené body) se skládá z částí lineárních spojovatelů (modré čáry)

Užití[editovat | editovat zdroj]

Lineární interpolace je často používána pro zaplnění mezer v tabulce. Předpokládejme, že máme tabulku seřazující populaci nějaké země v roce 1970, 1980, 1990 a 2000 a chcete odhadnout populaci v roce 1984. Lineární interpolace je k tomu snadná cesta. Základní operace lineární interpolace mezi dvěma hodnotami je tak běžně používána v počítačové grafice, že se jí někdy říká „lerp “ (zkratka Linear intERPolation) v místní hantýrce. Tento termín se užívá jako podstatné jméno i sloveso pro operaci jako například Bresenhamův algoritmus „lerps“ (lineárně interpoluje) přípustkově mezi 2 koncovými body přímky.

Operace lineární interpolace jsou vestavěny v hardwaru všech moderních počítačových grafických kartách. Jsou často použity jako stavební blok pro více komplexní operace např. bilineární interpolace může být zhotovená ve dvou lineárních interpolacích. Protože je tato operace levná. Je to dobrá možnost k vytvoření přesných vyhledávacích tabulek s rychlým vyhledáváním pro hladké funkce bez příliš položek v tabulce.

Historie[editovat | editovat zdroj]

Lineární polace se používala už od starověku, pro zaplnění mezer v tabulkách, často s astronomickými daty. Věří se, že se používala v posledních třech stoletích př. n. l. a také řeckým matematikem a astronomem Hipparchem (2. století př. n. l.). Popis lineární interpolace může být nalezen v Algamestu 2. stol. n. l.) u Ptolemaia.

Nadstavby[editovat | editovat zdroj]

V některých situacích není lineární interpolace dostatečná. V tomto případě může být nahrazena polynomiální interpolací, či kubickou interpolací. Lineární interpolace může rovněž být rozšířena na bilineární interpolaci pro interpolaci funkcí o dvou proměnných. Bilineární interpolace se často používá jako surový filtr pro potlačení roztřepených čar. Podobně trilineární interpolace se používá k interpolaci funkcí o třech proměnných. Další rozšíření lineární interpolace se používají pro jiné typy smyček (očí) jako například trojhranná nebo čtyřboká smyčka.

V tomto článku byl použit překlad textu z článku Linear interpolation na anglické Wikipedii.