Lineární interpolace - Linear interpolation

Vzhledem ke dvěma červeným bodům je modrá čára lineární interpolant mezi body a hodnotu y v x lze zjistit lineární interpolací.

V matematice je lineární interpolace metoda přizpůsobení křivky pomocí lineárních polynomů ke konstrukci nových datových bodů v rozsahu diskrétní sady známých datových bodů.

Lineární interpolace mezi dvěma známými body

V této geometrické vizualizaci se hodnota v zeleném kruhu vynásobená vodorovnou vzdáleností mezi červeným a modrým kruhem rovná součtu hodnoty v červeném kruhu vynásobeného vodorovnou vzdáleností mezi zeleným a modrým kruhem a hodnotou na modrý kruh vynásobený vodorovnou vzdáleností mezi zeleným a červeným kruhem.

Jsou -li dva známé body dány souřadnicemi a , je lineární interpolant přímka mezi těmito body. Pro hodnotu x v intervalu je hodnota y podél přímky dána z rovnice svahů ${\ displaystyle (x_ {0}, y_ {0})}$ ${\ displaystyle (x_ {1}, y_ {1})}$ ${\ displaystyle (x_ {0}, x_ {1})}$

{\ displaystyle {\ frac {y-y_ {0}} {x-x_ {0}}} = {\ frac {y_ {1} -y_ {0}} {x_ {1} -x_ {0}}} ,}

které lze geometricky odvodit z obrázku vpravo. Jedná se o speciální případ polynomické interpolace s n = 1.

Řešení této rovnice pro y , což je neznámá hodnota v x , dává

{\ Displaystyle y = y_ {0}+(x-x_ {0}) {\ frac {y_ {1} -y_ {0}} {x_ {1} -x_ {0}}} = {\ frac {y_ {0} (x_ {1} -x)+y_ {1} (x-x_ {0})} {x_ {1} -x_ {0}}},}

což je vzorec pro lineární interpolaci v intervalu . Mimo tento interval je vzorec identický s lineární extrapolací . ${\ displaystyle (x_ {0}, x_ {1})}$

Tento vzorec lze také chápat jako vážený průměr. Váhy jsou nepřímo úměrné vzdálenosti od koncových bodů k neznámému bodu; bližší bod má větší vliv než vzdálenější bod. Váha je tedy a , což jsou normalizované vzdálenosti mezi neznámým bodem a každým z koncových bodů. Protože tyto částky jsou 1, ${\ textstyle 1-{\ frac {x-x_ {0}} {x_ {1} -x_ {0}}}}$ ${\ textstyle 1-{\ frac {x_ {1} -x} {x_ {1} -x_ {0}}}}$

{\ Displaystyle y = y_ {0} \ left (1-{\ frac {x-x_ {0}} {x_ {1} -x_ {0}}} \ right)+y_ {1} \ left (1- {\ frac {x_ {1} -x} {x_ {1} -x_ {0}}} \ right) = y_ {0} \ left (1-{\ frac {x-x_ {0}} {x_ { 1} -x_ {0}}} \ right)+y_ {1} \ left ({\ frac {x-x_ {0}} {x_ {1} -x_ {0}}} \ right),}

což dává vzorec pro lineární interpolaci uvedený výše.

Interpolace datové sady

Lineární interpolace na datové sadě (červené body) se skládá z kusů lineárních interpolantů (modré čáry).

Lineární interpolace na sadě datových bodů ( x ₀ , y ₀ ), ( x ₁ , y ₁ ),…, ( x _n , y _n ) je definována jako zřetězení lineárních interpolantů mezi každou dvojicí datových bodů. Výsledkem je spojitá křivka s diskontinuální derivací (obecně), tedy třídy diferencovatelnosti . ${\ displaystyle C^{0}}$

Lineární interpolace jako aproximace

Lineární interpolace se často používá k aproximaci hodnoty některé funkce f pomocí dvou známých hodnot této funkce v jiných bodech. Chyba této aproximace je definována jako

{\ displaystyle R_ {T} = f (x) -p (x),}

kde p označuje lineární interpolační polynom definovaný výše:

{\ Displaystyle p (x) = f (x_ {0})+{\ frac {f (x_ {1})-f (x_ {0})} {x_ {1} -x_ {0}}} (x -x_ {0}).}

Pomocí Rollovy věty lze dokázat , že pokud f má spojitou druhou derivaci, pak je chyba ohraničena

{\ Displaystyle | R_ {T} | \ leq {\ frac {(x_ {1} -x_ {0})^{2}} {8}} \ max _ {x_ {0} \ leq x \ leq x_ { 1}} | f '' (x) |.}

To znamená, že aproximace mezi dvěma body na dané funkci se zhoršuje s druhou derivací funkce, která je aproximována. To je také intuitivně správné: čím je funkce „křivější“, tím horší jsou aproximace provedené jednoduchou lineární interpolací.

Historie a aplikace

Lineární interpolace se používá od starověku k vyplňování mezer v tabulkách. Předpokládejme, že máme tabulku se seznamem obyvatel některé země v letech 1970, 1980, 1990 a 2000 a že chceme odhadnout populaci v roce 1994. Lineární interpolace je snadný způsob, jak toho dosáhnout. To je věřil, že to bylo používáno v Seleucid říši (poslední tři století BC) a řeckým astronomem a matematikem Hipparchus (druhé století BC). Popis lineární interpolace lze nalézt ve starověkém čínském matematickém textu nazvaném Devět kapitol o matematickém umění (九章算術), datovaném od roku 200 př. N. L. Do roku 100 n. L. A Almagestu (2. století n . L. ) Od Ptolemaia .

Základní operace lineární interpolace mezi dvěma hodnotami se běžně používá v počítačové grafice . V žargonu tohoto pole se mu někdy říká lerp . Termín lze pro operaci použít jako sloveso nebo podstatné jméno . např. „ Bresenhamův algoritmus se přírůstkově pohybuje mezi dvěma koncovými body čáry.“

Operace Lerp jsou zabudovány do hardwaru všech moderních procesorů počítačové grafiky. Často se používají jako stavební bloky pro složitější operace: například bilineární interpolaci lze provést třemi lerpy. Protože je tato operace levná, je to také dobrý způsob, jak implementovat přesné vyhledávací tabulky s rychlým vyhledáváním hladkých funkcí, aniž byste museli mít příliš mnoho položek v tabulce.

Rozšíření

Porovnání lineární a bilineární interpolace některé 1- a 2-dimenzionální interpolace.
Černé a červené / žluté / zelené / modré body odpovídají interpolovanému bodu a sousedním vzorkům.
Jejich výšky nad zemí odpovídají jejich hodnotám.

Přesnost

Pokud je funkce C ⁰ nedostačující, například pokud je proces, který vytvořil datové body, znám jako hladší než C ⁰ , je běžné nahradit lineární interpolaci interpolací spline nebo v některých případech polynomickou interpolací .

Vícerozměrné

Lineární interpolace, jak je zde popsána, je pro datové body v jedné prostorové dimenzi. U dvou prostorových dimenzí se rozšíření lineární interpolace nazývá bilineární interpolace a ve třech dimenzích trilineární interpolace . Všimněte si však, že tyto interpolanty již nejsou lineárními funkcemi prostorových souřadnic, ale produkty lineárních funkcí; toto je ilustrováno jasně nelineárním příkladem bilineární interpolace na obrázku níže. Další rozšíření lineární interpolace lze použít na jiné druhy sítí, jako jsou trojúhelníkové a čtyřstěnné sítě, včetně Bézierových povrchů . Ty mohou být definovány jako skutečně nadrozměrná lineární funkce po částech (viz druhý obrázek níže).

Příklad bilineární interpolace na jednotkovém čtverci s hodnotami z 0, 1, 1 a 0,5, jak je uvedeno. Interpolované hodnoty mezi nimi reprezentované barvou.

Kousková lineární funkce ve dvou rozměrech (nahoře) a konvexní polytopy, na kterých je lineární (dole)

Podpora programovacího jazyka

Mnoho knihoven a stínovacích jazyků má pomocnou funkci „lerp“ (v GLSL se místo toho používá jako mix ) a vrací interpolaci mezi dvěma vstupy (v0, v1) pro parametr (t) v uzavřeném jednotkovém intervalu [0, 1]. Podpisy mezi funkcemi lerp jsou různě implementovány v obou formách (v0, v1, t) a (t, v0, v1).

// Imprecise method, which does not guarantee v = v1 when t = 1, due to floating-point arithmetic error. This method is monotonic
// This form may be used when the hardware has a native fused multiply-add instruction.
float lerp(float v0, float v1, float t) {
  return v0 + t * (v1 - v0);
}

// Precise method, which guarantees v = v1 when t = 1. This method is monotonic only when v0 * v1 < 0. Lerping between same values might not produce the same value
float lerp(float v0, float v1, float t) {
  return (1 - t) * v0 + t * v1;
}

Tato funkce lerp se běžně používá pro míchání alfa (parametr „t“ je „hodnota alfa“) a vzorec lze rozšířit tak, aby mísil více složek vektoru (například prostorové osy x , y , z nebo r , g , b barevné složky) paralelně.

Viz také

Reference

Meijering, Erik (2002), „Chronologie interpolace: od starověké astronomie k modernímu zpracování signálu a obrazu“ , Proceedings of the IEEE , 90 (3): 319–342, doi : 10.1109/5.993400.

externí odkazy

Rovnice přímky v cut-the-uzel
Dobře vychovaná interpolace čísel a ukazatelů
„Lineární interpolace“ , Encyclopedia of Mathematics , EMS Press , 2001 [1994]
„Vzorec konečných přírůstků“ , Encyclopedia of Mathematics , EMS Press , 2001 [1994]

Languages

In other projects