Interpolacja liniowa - Linear interpolation

Biorąc pod uwagę dwa czerwone punkty, niebieska linia jest interpolacją liniową między punktami, a wartość y przy x można znaleźć przez interpolację liniową.

W matematyce interpolacja liniowa to metoda dopasowywania krzywych za pomocą wielomianów liniowych do konstruowania nowych punktów danych w zakresie dyskretnego zestawu znanych punktów danych.

Interpolacja liniowa między dwoma znanymi punktami

W tej geometrycznej wizualizacji wartość na zielonym kole pomnożona przez odległość poziomą między czerwonym i niebieskim kółkiem jest równa sumie wartości na czerwonym kółku pomnożonej przez poziomą odległość między zielonym i niebieskim kółkiem oraz wartości w niebieski okrąg pomnożony przez poziomą odległość między zielonym i czerwonym kółkiem.

Jeśli dwa znane punkty są podane przez współrzędne i , interpolant liniowy jest linią prostą między tymi punktami. Dla wartości x w przedziale , wartość y wzdłuż prostej jest podawana z równania nachyleń ${\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}}} ,}$

które można wyprowadzić geometrycznie z rysunku po prawej stronie. Jest to szczególny przypadek interpolacji wielomianowej z n  = 1.

Rozwiązanie tego równania dla y , które jest nieznaną wartością w x , daje

${\ 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}}},}$

który jest wzorem na interpolację liniową w przedziale . Poza tym przedziałem wzór jest identyczny z ekstrapolacją liniową . ${\displaystyle (x_{0},x_{1})}$

Ten wzór można również rozumieć jako średnią ważoną. Wagi są odwrotnie proporcjonalne do odległości od punktów końcowych do punktu nieznanego; bliższy punkt ma większy wpływ niż dalszy punkt. Wagi to i , które są znormalizowanymi odległościami między nieznanym punktem a każdym z punktów końcowych. Ponieważ sumują się one do 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} \ lewo (1-{\ Frac {x-x_ {0}} {x_ {1}-x_ {0}}} \ prawo) + Y_ {1} \ lewo (1 - {\frac {x_{1}-x}{x_{1}-x_{0}}}\right)=y_{0}\left(1-{\frac {x-x_{0}}{x_{ 1}-x_{0}}}\prawo)+y_{1}\lewo({\frac {x-x_{0}}{x_{1}-x_{0}}}\prawo),}$

co daje wzór na interpolację liniową podany powyżej.

Interpolacja zbioru danych

Interpolacja liniowa na zbiorze danych (czerwone punkty) składa się z kawałków liniowych interpolantów (niebieskie linie).

Interpolacja liniowa na zbiorze punktów danych ( x ₀ ,  y ₀ ), ( x ₁ ,  y ₁ ), …, ( x _n ,  y _n ) jest zdefiniowana jako połączenie interpolacji liniowych między każdą parą punktów danych. Daje to krzywą ciągłą , z nieciągłą pochodną (na ogół), a więc klasy różniczkowalności .${\ Displaystyle C ^ {0}}$

Interpolacja liniowa jako przybliżenie

Interpolacja liniowa jest często używana do przybliżania wartości jakiejś funkcji f przy użyciu dwóch znanych wartości tej funkcji w innych punktach. Błąd tego zbliżenia jest zdefiniowany jako

${\ Displaystyle R_ {T} = f (x) -p (x)}$

gdzie p oznacza zdefiniowany powyżej wielomian interpolacji liniowej :

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

Można udowodnić za pomocą twierdzenia Rolle'a, że jeśli f ma ciągłą drugą pochodną, ​​to błąd jest ograniczony przez

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

Oznacza to, że przybliżenie między dwoma punktami na danej funkcji pogarsza się z drugą pochodną funkcji, która jest aproksymowana. Jest to również intuicyjnie poprawne: im „krzywizna” jest funkcja, tym gorsze stają się przybliżenia wykonane za pomocą prostej interpolacji liniowej.

Historia i aplikacje

Interpolacja liniowa była stosowana od starożytności do wypełniania luk w tablicach. Załóżmy, że mamy tabelę z populacją jakiegoś kraju w latach 1970, 1980, 1990 i 2000 i chcemy oszacować populację w 1994 roku. Prostym sposobem na to jest interpolacja liniowa. Uważa się, że był używany w Imperium Seleucydów (ostatnie trzy wieki pne) oraz przez greckiego astronoma i matematyka Hipparcha (II wiek pne). Opis interpolacji liniowej można znaleźć w starożytnym chińskim tekście matematycznym zatytułowanym Dziewięć rozdziałów o sztuce matematycznej (九章算術), datowanym na lata 200 pne do 100 ne i Almagest (II wne) autorstwa Ptolemeusza .

Podstawowa operacja interpolacji liniowej między dwiema wartościami jest powszechnie stosowana w grafice komputerowej . W żargonie tej dziedziny nazywa się go czasem lerpem . Termin może być używany jako czasownik lub rzeczownik dla operacji. np. „ Algorytm Bresenhama lerpsuje się przyrostowo między dwoma punktami końcowymi linii”.

Operacje Lerp są wbudowane w sprzęt wszystkich nowoczesnych procesorów graficznych. Są one często używane jako cegiełki do bardziej złożonych operacji: na przykład interpolację dwuliniową można wykonać w trzech trędowatych. Ponieważ ta operacja jest tania, jest to również dobry sposób na zaimplementowanie dokładnych tabel wyszukiwania z szybkim wyszukiwaniem w celu uzyskania płynnych funkcji bez zbyt wielu wpisów w tabeli.

Rozszerzenia

Porównanie interpolacji liniowej i dwuliniowej oraz interpolacji jedno- i dwuwymiarowych.
Czarne i czerwone / żółte / zielone / niebieskie kropki odpowiadają odpowiednio interpolowanemu punktowi i sąsiednim próbkom.
Ich wysokość nad ziemią odpowiada ich wartościom.

Precyzja

Jeśli funkcja C ⁰ jest niewystarczająca, na przykład jeśli wiadomo, że proces, który utworzył punkty danych jest gładszy niż C ⁰ , często zastępuje się interpolację liniową interpolacją splajnu lub, w niektórych przypadkach, interpolacją wielomianową .

Wielowymiarowy

Opisana tutaj interpolacja liniowa dotyczy punktów danych w jednym wymiarze przestrzennym. Dla dwóch wymiarów przestrzennych rozszerzenie interpolacji liniowej nazywa się interpolacją dwuliniową , a w trzech wymiarach interpolacją trójliniową . Zauważ jednak, że te interpolanty nie są już liniowymi funkcjami współrzędnych przestrzennych, a raczej produktami funkcji liniowych; ilustruje to wyraźnie nieliniowy przykład interpolacji dwuliniowej na poniższym rysunku. Inne rozszerzenia interpolacji liniowej można zastosować do innych rodzajów siatek, takich jak siatki trójkątne i czworościenne, w tym powierzchnie Béziera . Można je zdefiniować jako rzeczywiście wyżej wymiarową odcinkową funkcję liniową (patrz drugi rysunek poniżej).

Przykład interpolacji dwuliniowej na kwadracie jednostkowym z wartościami z 0, 1, 1 i 0,5, jak wskazano. Wartości interpolowane pomiędzy reprezentowane przez kolor.

Odcinkowo funkcja liniowa w dwóch wymiarach (góra) i politopy wypukłe, na których jest liniowa (dół)

Obsługa języka programowania

Wiele bibliotek i języków cieniowania ma funkcję pomocniczą "lerp" (w GLSL znaną zamiast mix ), zwracającą interpolację między dwoma wejściami (v0, v1) dla parametru (t) w przedziale jednostki zamkniętej [0, 1]. Sygnatury pomiędzy funkcjami lerpa są różnie zaimplementowane w obu formach (v0, v1, t) i (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;
}

Ta funkcja lerp jest powszechnie używana do mieszania alfa (parametr „t” jest „wartością alfa”), a formuła może być rozszerzona w celu mieszania wielu składników wektora (takich jak przestrzenne osie x , y , z lub r , g , b składowe koloru) równolegle.

Zobacz też

• Interpolacja dwuliniowa
• Interpolacja splajnu
• Interpolacja wielomianowa
• algorytm de Casteljau
• Blokada pierwszego rzędu
• krzywa Béziera

Bibliografia

• Meijering, Erik (2002), „Chronologia interpolacji: od starożytnej astronomii do nowoczesnego przetwarzania sygnału i obrazu” , Proceedings of the IEEE , 90 (3): 319-342, doi : 10.1109/5.993400.

Zewnętrzne linki

• Równania linii prostej na przecięciu węzła
• Dobrze zachowana interpolacja liczb i wskaźników
• „Interpolacja liniowa” , Encyklopedia Matematyki , EMS Press , 2001 [1994]
• „Formuła skończonych przyrostów” , Encyklopedia Matematyki , EMS Press , 2001 [1994]