Interpolacja (matematyka)

W matematyce numerycznej termin interpolacja (z łaciny inter = pomiędzy i polire = gładka, grind) opisuje klasę problemów i procedur. Przy zadanych danych dyskretnych (np. Wartości pomiarowe ) znajdują się funkcje ciągłe (tzw. INTERPOL Ante lub interpolant ), które odwzorowują te dane. Następnie mówi się, że funkcja interpoluje dane.

wprowadzenie

Punkty do interpolacji

Czasami znane są tylko pojedyncze punkty funkcji, ale nie ma analitycznego opisu funkcji, który mógłby być użyty do jej oceny w dowolnym momencie. Jednym z przykładów są punkty będące wynikiem pomiaru fizycznego . Gdyby punkty mogły być połączone (możliwie gładką) krzywą, możliwe byłoby oszacowanie nieznanej funkcji w punktach pośrednich. W innych przypadkach trudna w obsłudze funkcja powinna być w przybliżeniu reprezentowana przez prostszą. Funkcja interpolacji może spełnić to wymaganie dotyczące prostoty. To zadanie jest znane jako problem interpolacji . Istnieje kilka rozwiązań tego problemu; użytkownik musi najpierw wybrać odpowiednie funkcje podejścia. W zależności od funkcji podejścia otrzymujemy inny interpolant.

Interpolacja jest rodzajem aproksymacji : rozpatrywana funkcja jest dokładnie odtwarzana przez funkcję interpolacji w punktach interpolacji i przynajmniej w przybliżeniu w pozostałych punktach. Jakość przybliżenia zależy od podejścia. Aby to docenić, potrzebne są dodatkowe informacje o funkcji . Zwykle pojawiają się one w sposób naturalny, nawet jeśli nie jesteś świadomy : często można założyć ograniczenie, ciągłość lub zróżnicowanie. ${\ displaystyle f}$${\ displaystyle f}$

Inne metody aproksymacji, takie jak obliczenie dopasowania , nie wymagają dokładnego odtworzenia danych pomiarowych. W ten sposób metody te różnią się od interpolacji. Powiązany problem ekstrapolacji szacuje wartości, które wykraczają poza definicję danych.

Problemy z interpolacją

Ogólny problem interpolacji

Dane pary liczb rzeczywistych lub zespolonych . Analogicznie do obliczeń z funkcjami, są one określane jako punkty podparcia , te jako wartości podparcia, a pary jako punkty podparcia . Teraz wybiera się funkcję podejścia, która zależy zarówno od innych parametrów, jak i od nich . Interpolacja problemem jest zadaniem powinny być dobrane w taki sposób, że . ${\ displaystyle n + 1}$${\ displaystyle (x_ {i}, \, f_ {i})}$${\ displaystyle x_ {i}}$${\ displaystyle f_ {i}}$${\ displaystyle (x_ {i}, f_ {i})}$${\ Displaystyle \ Phi (x, \, a_ {0}, \ ldots, a_ {n})}$${\ displaystyle x}$${\ displaystyle n + 1}$${\ displaystyle a_ {j}}$${\ displaystyle a_ {j}}$${\ Displaystyle \ Phi (x_ {i}, \, a_ {0}, \ ldots, a_ {n}) = f_ {i}}$

Zagadnienie interpolacji liniowej

Mówi się o problemie interpolacji liniowej, jeśli tylko liniowo od zależnej, d. H. ${\ displaystyle \ Phi}$${\ displaystyle a_ {j}}$

${\ Displaystyle \ Phi (x, \, a_ {0}, \ ldots, a_ {n}) = a_ {0} + a_ {1} \ Phi _ {1} (x) + a_ {2} \ Phi _ {2} (x) + \ cdots + a_ {n} \ Phi _ {n} (x)}$.

W szczególności interpolacja wielomianowa jest takim problemem interpolacji liniowej. Poniższe dotyczy interpolacji wielomianowej

${\ Displaystyle \ Phi (x, \, a_ {0}, \ ldots, a_ {n}) = a_ {0} + a_ {1} x + a_ {2} x ^ {2} + a_ {3} x ^ {3} + \ cdots + a_ {n} x ^ {n}}$.

Przypadków szczególnych , i nazywane są liniowe , kwadratowe i sześcienne interpolacja . W dwóch wymiarach, mówi się odpowiednio z bilinear , dwukwadratowy i Bicubic . ${\ displaystyle n = 1}$${\ displaystyle n = 2}$${\ displaystyle n = 3}$

Ponadto interpolacja trygonometryczna jest interpolacją liniową:

${\ Displaystyle \ Phi (x, \, a_ {0}, \ ldots, a_ {n}) = a_ {0} + a_ {1} e ^ {xi} + a_ {2} e ^ {2xi} + \ cdots + a_ {n} e ^ {nxi}, \ quad (i ^ {2} = - 1)}$

Nieliniowe problemy interpolacyjne

Jednym z najważniejszych problemów związanych z interpolacją nieliniową jest

• racjonalne :${\ Displaystyle \ Phi (x, \, a_ {0}, \ ldots, a_ {n}, \, b_ {0}, \ ldots, b_ {m}) = {\ frac {a_ {0} + a_ { 1} x + a_ {2} x ^ {2} + a_ {3} x ^ {3} + \ cdots + a_ {n} x ^ {n}} {b_ {0} + b_ {1} x + b_ {2} x ^ {2} + b_ {3} x ^ {3} + \ cdots + b_ {m} x ^ {m}}}}$

Metoda interpolacji

Interpolacja liniowa

Interpolacja liniowa wykonywana kawałek po kawałku

Interpolacja liniowa ustalona przez Izaaka Newtona jest najprostsza i prawdopodobnie najczęściej stosowana w praktyce. Tutaj dwa podane punkty danych ( ) i ( ) są połączone linią. Obowiązują następujące zasady: ${\ displaystyle x_ {0}, f_ {0}}$${\ displaystyle x_ {1}, f_ {1}}$

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

Odpowiada to wypukłej kombinacji punktów końcowych i . ${\ displaystyle (x_ {0}, \, f_ {0})}$${\ displaystyle (x_ {1}, \, f_ {1})}$

Aby uzyskać szczegółowe wyjaśnienie, zobacz ogólną interpolację liniową .

Wielomiany wyższego stopnia

Wielomian interpolacyjny 7. stopnia

Dla punktów danych, które różnią się parami, istnieje dokładnie jeden wielomian interpolacji -ty stopień, który odpowiada określonym wartościom podpór w określonych punktach interpolacji. Wyznaczenie współczynników wymaga rozwiązania liniowego układu równań . Istnienie takiego wielomianu interpolacyjnego można zobaczyć np. B. za pomocą formuły Lagrange'a${\ displaystyle n + 1}$ ${\ displaystyle n}$

${\ Displaystyle p (x) = \ suma _ {i = 0} ^ {n} \, f_ {i} \ prod _ {k = 0, k \ neq i} ^ {n} {\ Frac {x-x_ {k}} {x_ {i} -x_ {k}}}}$.

Wyjątkowość wynika ze znanego faktu, że wielomian -ty stopień ma co najwyżej zera. ${\ displaystyle n}$${\ displaystyle n}$

Dalsze procedury interpolacji wielomianowej znajdują się tam.

Interpolacja fragmentaryczna

Interpolacja krzywej sześciennej

Ponieważ wielomiany stają się coraz bardziej niestabilne wraz ze wzrostem stopnia, i. H. mocno wibrują między punktami interpolacji, w praktyce rzadko stosuje się wielomiany o stopniu większym niż 5. Zamiast tego interpoluje się duży zestaw danych kawałek po kawałku . W przypadku interpolacji liniowej byłby to wielokąt , w przypadku wielomianów stopnia 2 lub 3 mówi się zwykle o interpolacji sklejanej . W przypadku interpolantów zdefiniowanych w sekcjach, kwestia ciągłości i różniczkowości w punktach interpolacji ma duże znaczenie.

Interpolacja pustelnika

Jeśli oprócz punktów interpolacji , pochodne - mają być interpolowane, mówi się o problemie interpolacji Hermite'a . Rozwiązanie tego problemu można też określić w formie zamkniętej, analogicznie do metody Lagrange'a. ${\ displaystyle x_ {i}}$${\ displaystyle k}$ ${\ Displaystyle f ^ {(k)} (x_ {i}) = f_ {i} ^ {(k)}}$

Interpolacja trygonometryczna

Jeżeli jako funkcję przybliżania wybrano wielomian trygonometryczny, uzyskuje się interpolację trygonometryczną . Wzór interpolacji

${\ Displaystyle g (x) = {\ Frac {1} {2}} a_ {0} + \ suma _ {k = 1} ^ {N-1} (a_ {k} \ cos kx + b_ {k}) \ sin kx) + {\ frac {1} {2}} a_ {N} \ cos Nx \ ,, \ quad N = n / 2}$

odpowiada rozwinięciu Fouriera nieznanego interpolantu. Współczynniki Fouriera i obliczcie siebie nawzajem ${\ displaystyle a_ {k}}$${\ displaystyle b_ {k}}$

${\ Displaystyle a_ {k} \ około {\ Frac {2} {n}} \ suma _ {i = 1} ^ {n} f (x_ {i}) \ cos kx_ {i}}$i .${\ Displaystyle b_ {k} \ około {\ Frac {2} {n}} \ suma _ {i = 1} ^ {n} f (x_ {i}) \ sin kx_ {i}}$

Zakłada się, że punkty interpolacji są równomiernie rozłożone w przedziale i są okresowe poza tym przedziałem. Współczynniki można skutecznie obliczyć przy użyciu szybkiej transformaty Fouriera . ${\ displaystyle x_ {i}}$${\ Displaystyle [0; \, 2 \ pi]}$

Interpolacja logarytmiczna

Jeśli podejrzewasz lub wiesz, że dane są oparte na funkcji logarytmicznej , ta metoda jest zalecana.

W interpolacji logarytmicznej dwa znane punkty danych i połączenie krzywej logarytmicznej. Obowiązują następujące zasady: ${\ displaystyle (x_ {0}, f_ {0})}$${\ displaystyle (x_ {1}, f_ {1})}$

${\ Displaystyle {\ Frac {\ ln f- \ ln f_ {0}} {\ ln f_ {1} - \ ln f_ {0}}} = {\ Frac {x-x_ {0}} {x_ {1 } -x_ {0}}}}$

Albo inaczej:

${\ Displaystyle f (x) = f_ {0} \ cdot \ exp \ lewo ({\ Frac {(x-x_ {0}) (\ ln f_ {1} - \ ln f_ {0})} {x_ { 1} -x_ {0}}} \ right)}$

Przykład: test χ²

Regresja Gaussa (kriging)

Interpolacja procesu Gaussa (kolor niebieski) i oszacowany przedział ufności (kolor szary) luki między dwiema krzywymi (kolor czarny) o bardzo mieszanych właściwościach.

Bardzo wszechstronną i uniwersalną metodą interpolacji jest regresja procesu Gaussa lub metoda Kriginga . Oznacza to, że zarówno płynne, jak i okresowe interpolacje lub wygładzanie można przeprowadzić w dowolnych wymiarach. Za pomocą tak zwanej funkcji kowariancji można opisać specjalne właściwości danych w celu przeprowadzenia optymalnej interpolacji problemu.

Właściwości metody interpolacji:

• Nadaje się do nieregularnych punktów podparcia
• Interpolacja w dowolnych wymiarach (np. Interpolacja powierzchni)
• Optymalna interpolacja gładkich, okresowych lub hałaśliwych krzywych
• Przewidywanie przedziału ufności interpolacji

Ogólna interpolacja liniowa

Niech będzie to rzeczywista lub złożona, ciągle różniczkowalna funkcja ze zbiorem zer , przy czym wszystkie zera muszą być proste. Zbiór indeksów może być zbiorem skończonym, takim jak B. lub policzalny zbiór, taki jak lub . Jądra interpolacji są więc podane jako ${\ Displaystyle H (x)}$ ${\ Displaystyle \ {x_ {k}: k \, \ mathrm {z} \, ja \}}$${\ displaystyle I}$${\ displaystyle I = \ {1, \ kropki, N \}}$${\ displaystyle I = \ mathbb {N}}$${\ displaystyle I = \ mathbb {Z}}$

${\ Displaystyle L_ {k} (x): = {\ Frac {H (x)} {H '(x_ {k}) (x-x_ {k})}} = {\ Frac {G (x, x_ {k})} {G (x_ {k}, x_ {k})}}}$

i kontynuowane w sposób ciągły z wartością 1 w tym punkcie . Funkcja pomocnicza jest zdefiniowana poza przekątną jako ${\ displaystyle x = x_ {k}}$${\ Displaystyle G (x, y)}$${\ displaystyle x = y}$

${\ Displaystyle G (x, y): = {\ Frac {H (x) -H (y)} {xy}}}$i stale się rozwijał .${\ Displaystyle G (x, x): = H '(x)}$

Poniższe dotyczy zer , przy czym zastosowano deltę Kroneckera . ${\ Displaystyle L_ {k} (x_ {j}) = \ delta _ {k, j}}$

Jeśli teraz podane są wartości dla każdego , funkcja interpolacji jest definiowana przez ${\ displaystyle f_ {k}}$${\ displaystyle k \ in I}$

${\ displaystyle F (x): = \ suma _ {k \ in I} f_ {k} \ cdot L_ {k} (x) = \ suma _ {k \ in I} {\ Frac {G (x, x_) {k})} {G (x_ {k}, x_ {k})}} f_ {k}}$.

W przypadku policzalnego zbioru zer warunkiem zbieżności musi być

${\ Displaystyle \ suma _ {k \ in ja} \ lewo | {\ Frac {f_ {k}} {H '(x_ {k}) (1+ | x_ {k} |)}} \ prawo | <\ infty}$

być spełniony.

Przykłady

• Z określonymi punktami podparcia i funkcji rzeczywistej z , funkcja ta może być utworzona. Wtedy dostajesz${\ displaystyle \ {x_ {1}, \ dotsc, x_ {N} \}}$${\ displaystyle h}$${\ Displaystyle h (0) = 0}$${\ Displaystyle h '(0) \ neq 0}$${\ Displaystyle H (x): = h (x-x_ {1}) \ dotsm h (x-x_ {N})}$

${\ Displaystyle L_ {k} (x) = {\ Frac {h (x-x_ {k})} {h '(0) (x-x_ {k})}} \ cdot \ prod _ {j \ neq k} {\ frac {h (x-x_ {j})} {h (x_ {k} -x_ {j})}}}$.

Otrzymaną metodą interpolacji jest interpolacja Lagrange'a. Inne przykłady dotyczą funkcji interpolacji, które zmniejszają się w kierunku nieskończoności do zera lub ograniczonej funkcji interpolacji z jasnym wzorem obliczeniowym.${\ Displaystyle h (x) = x}$${\ Displaystyle h (x) = x / (1 + x ^ {2})}$${\ Displaystyle h (x) = \ sin (x)}$

• Z wielomianem dzielenia koła , ja. H. W -tym korzenie jednostki , jak punktów podparcia, doprowadzić do dyskretnej transformacji Fouriera jako metoda obliczania współczynników interpolacji wielomianowej. Dotyczy i generalnie tak${\ Displaystyle H (x): = x ^ {N} -1}$${\ displaystyle N}$ ${\ Displaystyle x_ {k}: = \ exp (i2 \ pi \, k / N)}$${\ displaystyle k = 1, \ kropki, N}$${\ Displaystyle L_ {N} (x) = {\ Frac {1} {N}} (1 + x + \ dotsb + x ^ {N-1})}$${\ Displaystyle L_ {k} (x) = L_ {N} ({\ bar {x}} _ {k} \, x)}$

${\ Displaystyle F (x) = \ suma _ {n = 0} ^ {N-1} x ^ {n} \ cdot {\ Frac {1} {N}} \ suma _ {k = 1} ^ {N } f_ {k} {\ bar {x}} _ {k} ^ {n}}$ jest.

• Z i zer , mierzy się jako funkcję interpolacji liczby kardynalnej${\ Displaystyle H (x): = \ sin (\ pi x)}$${\ displaystyle x_ {k} = k}$${\ Displaystyle k \ in \ mathbb {Z}}$

${\ Displaystyle F (x) = \ suma _ {k \ in \ mathbb {Z}} f_ {k} {\ Frac {\ sin (\ pi x)} {(- 1) ^ {+} k \ pi ( xk)}} = \ sum _ {k \ in \ mathbb {Z}} f_ {k} {\ frac {\ sin (\ pi (xk))} {\ pi (xk)}}}$.

Odgrywa to kluczową rolę w twierdzeniu o próbkowaniu Nyquista-Shannona . Warunkiem zbieżności jest

${\ Displaystyle \ suma _ {k \ in \ mathbb {Z}} \ lewo | {\ frac {f_ {k}} {1+ | k |}} \ prawo | <\ infty}$.

Reprezentacja punktów podparcia wielomianów

Bądź wielomianem. Ten wielomian można przedstawić w tak zwanej reprezentacji współczynników przez określenie wektora . Alternatywną reprezentacją, która działa bez współczynników, jest reprezentacja punktów interpolacji . Wielomian jest oceniana na wartości z i , i. to znaczy, wartości funkcji są obliczane. Para wektorów nazywana jest reprezentacją punktu podparcia wielomianu . Główną zaletą tej reprezentacji jest to, że dwa wielomiany można pomnożyć w krokach (patrz symbole Landaua ) w reprezentacji punktów podparcia . W przedstawieniu współczynników wymagane są jednak kroki. Dlatego transformacja z reprezentacji współczynników do reprezentacji punktów podparcia ma szczególne znaczenie i jest nazywana transformacją Fouriera . Transformację odwrotną uzyskuje się przez interpolację. ${\ Displaystyle p (x) = a_ {0} + a_ {1} x + a_ {2} x ^ {2} + \ dotsb + a_ {n-1} x ^ {n-1}}$${\ displaystyle (a_ {0}, \ dotsc, a_ {n-1})}$${\ displaystyle a_ {0}, \ dotsc, a_ {n-1}}$${\ displaystyle n}$${\ displaystyle x_ {i}}$${\ Displaystyle 0 \ równoważnik ja \ równoważnik n-1}$${\ displaystyle i \ in \ mathbb {N}}$${\ displaystyle p (x_ {i}) = y_ {i}}$${\ Displaystyle ((x_ {0}, \ dotsc, x_ {n-1}), (y_ {0}, \ dotsc, y_ {n-1}))}$${\ displaystyle p}$${\ Displaystyle \ Theta (n)}$${\ Displaystyle \ Theta (n ^ {2})}$

Aplikacje

Interpolacja podczas skalowania obrazu

W wielu zastosowaniach metod interpolacyjnych twierdzi się, że nowe informacje są uzyskiwane z istniejących danych przez interpolację . Ale to jest złe. Tylko przebieg funkcji ciągłej między znanymi punktami próbkowania można oszacować przez interpolację . To oszacowanie opiera się głównie na założeniu, że kurs jest nieco „płynny”, co w większości przypadków prowadzi do wiarygodnych wyników. Jednak założenie to niekoniecznie musi być poprawne. Składowe o wyższej częstotliwości, które zostały utracone podczas digitalizacji sygnału z powodu twierdzenia o próbkowaniu, nie mogą być ponownie odtworzone przez kolejną interpolację.

Dobrze znanym zastosowaniem interpolacji jest cyfrowe przetwarzanie sygnału . Podczas konwersji sygnału z niskiej częstotliwości próbkowania na wysoką (patrz konwersja częstotliwości próbkowania ), wartości próbkowania sygnału wyjściowego są interpolowane z wartości sygnału wejściowego. Szczególnym przypadkiem jest skalowanie obrazów w grafice komputerowej .

Interpolacja w wyższych wymiarach

Przedstawione powyżej proste procedury są w większości opisane tylko dla problemów 1D. Interpolacje splajnu z np. B. Wypusty cienkościenne lub inne radialne funkcje bazowe lub metoda kriginga lub regresja procesu Gaussa. Prostym sposobem interpolacji punktów w wyższych wymiarach ( ), które znajdują się w regularnej siatce, jest rekurencyjne zastosowanie interpolacji 1D. ${\ Displaystyle \ mathbb {R} ^ {2}, \ mathbb {R} ^ {3}, ...}$

Jest to wyjaśnione na przykładzie interpolacji bilinearnej.

Podane są wartości liczbowe w wierzchołkach , , i . Szukamy w miejscu wartości interpolowanej . ${\ displaystyle Q_ {11}}$${\ displaystyle Q_ {12}}$${\ displaystyle Q_ {21}}$${\ displaystyle Q_ {22}}$${\ displaystyle P}$

Procedura: interpolację liniową stosuje się dwukrotnie, np. B. pierwsza dla kierunku x. Jest określany na podstawie i za pomocą interpolacji liniowej 1D. Następnie jest określany w ten sam sposób. Wartość a jest wynikiem liniowej interpolacji 1D w kierunku y między a . ${\ displaystyle R_ {1}}$${\ displaystyle Q_ {11}}$${\ displaystyle Q_ {21}}$${\ displaystyle R_ {2}}$${\ displaystyle P}$${\ displaystyle R_ {1}}$${\ displaystyle R_ {2}}$

3D: Istnieją punkty narożne z wartościami liczbowymi dla interpolacji trójliniowej . Pierwsza interpolacja na osi X daje punkty pośrednie, które są prostopadłe do płaszczyzny . W tej płaszczyźnie interpolacja odbywa się w kierunku y w, a punkty pośrednie prowadzą do linii w kierunku z w pozycji . Ostatnia interpolacja na tej linii daje w końcu punkty, czyli poszukiwane rozwiązanie. ${\ displaystyle 2 ^ {3}}$${\ displaystyle 2 ^ {2}}$${\ displaystyle x = P_ {x}}$${\ displaystyle y = P_ {y}}$${\ displaystyle 2 ^ {1}}$${\ displaystyle x = P_ {x}, y = P_ {y}}$${\ displaystyle 2 ^ {0}}$

Metodę można zastosować do dowolnego wymiaru poprzez kolejną rekurencję.

literatura

• Josef Stoer: Matematyka numeryczna 1 . 8. wydanie, Springer 1999.
• Bernd Jähne : Cyfrowe przetwarzanie obrazu . Wydanie 4, Springer 1997.
• Oppenheim, Schafer: Przetwarzanie sygnałów w czasie dyskretnym . Oldenbourg 1992.
• Crochiere, Rabiner: Wielostronne cyfrowe przetwarzanie sygnału . Prentice Hall 1983.

linki internetowe

• Narzędzie online do interpolacji liniowej i kwadratowej z wizualizacją
• Strona Newton, Lagrange i Cubic Spline również z apletem Java