Interpolacja liniowa – szczególny przypadek aproksymacji za pomocą funkcji liniowej.
Aproksymacja (łac. approximare – przybliżać) – proces określania rozwiązań przybliżonych na podstawie rozwiązań znanych, które są bliskie rozwiązaniom dokładnym w ściśle sprecyzowanym sensie. Zazwyczaj aproksymuje się byty (np. funkcje) skomplikowane bytami prostszymi. Często stosowana w przypadku szukania rozwiązań dla danych uzyskanych metodami empirycznymi, które mogą być obarczone błędami.
Jeśli x określa wartość z przedziału x0 < x < x1, a y0 = f(x0) i y1 = f(x1) tablicę wartości danej funkcji, oraz h = x1 - x0 odstęp pomiędzy argumentami, wówczas liniową interpolację wartości L(x) funkcji f otrzymuje się jako:
Aproksymacja (łac. approximare – przybliżać) – proces określania rozwiązań przybliżonych na podstawie rozwiązań znanych, które są bliskie rozwiązaniom dokładnym w ściśle sprecyzowanym sensie. Zazwyczaj aproksymuje się byty (np. funkcje) skomplikowane bytami prostszymi. Często stosowana w przypadku szukania rozwiązań dla danych uzyskanych metodami empirycznymi, które mogą być obarczone błędami.
Jeśli x określa wartość z przedziału x0 < x < x1, a y0 = f(x0) i y1 = f(x1) tablicę wartości danej funkcji, oraz h = x1 - x0 odstęp pomiędzy argumentami, wówczas liniową interpolację wartości L(x) funkcji f otrzymuje się jako:
Interpolacja liniowa
Interpolacja wielomianowa, nazywana też interpolacją Lagrange'a, od nazwiska pioniera badań nad interpolacją Josepha Lagrange'a, lub po prostu interpolacją jest metodą numeryczną przybliżania funkcji tzw. wielomianem Lagrange'a stopnia n przyjmującym w n+1 punktach, zwanych węzłami interpolacji, wartości takie same jak przybliżana funkcja.
Interpolacja jest często stosowana w naukach doświadczalnych, gdzie dysponuje się zazwyczaj skończoną liczbą danych do określenia zależności między wielkościami.
Zgodnie z twierdzeniem Weierstrassa dowolną funkcję y=f(x), ciągłą na przedziale domkniętym, można dowolnie przybliżyć za pomocą wielomianu odpowiednio wysokiego stopnia.
Metoda interpolacji polega na:
- wybraniu n+1 punktów x0,x1,...,xn należących do dziedziny f, dla których znane są wartości
- znalezieniu wielomianu W(x) stopnia co najwyżej n takiego, że
Interpretacja geometryczna – dla danych n+1 punktów na wykresie szuka się wielomianu stopnia co najwyżej n, którego wykres przechodzi przez dane punkty.
Znajdowanie odpowiedniego wielomianu
Wielomian przyjmujący zadane wartości w konkretnych punktach można zbudować w ten sposób:
- Dla pierwszego węzła o wartości f(x0) znajduje się wielomian, który w tym punkcie przyjmuje wartość f(x0), a w pozostałych węzłach x1,x2,...,xn wartość zero.
- Dla kolejnego węzła znajduje się podobny wielomian, który w drugim węźle przyjmuje wartość f(x1), a w pozostałych węzłach x0,x2,...,xn wartość zero.
- Dodaje się wartość ostatnio obliczonego wielomianu do wartości poprzedniego.
- Dla każdego z pozostałych węzłów znajduje się podobny wielomian, za każdym razem dodając go do wielomianu wynikowego.
- Wielomian będący sumą wielomianów obliczonych dla poszczególnych węzłów jest wielomianem interpolującym.
Dowód ostatniego punktu i dokładny sposób tworzenia poszczególnych wielomianów opisany jest poniżej w dowodzie istnienia wielomianu interpolującego będącego podstawą algorytmu odnajdowania tego wielomianu.
Wielomian Lagrange'a
Postać Lagrange'a wielomianu to jedna z metod przedstawiania wielomianu, wykorzystywana często w zagadnieniach interpolacji. Dla wielomianu stopnia n wybiera się n+1 punktów – x0,x1,...,xn i wielomian ma postać:
Ponieważ
jest równy 1 dla x równego xi (licznik i mianownik są równe), 0 zaś dla wszystkich innych xj (licznik jest równy zero), można łatwo za pomocą postaci Lagrange'a interpolować dowolną funkcję:
jest równy 1 dla x równego xi (licznik i mianownik są równe), 0 zaś dla wszystkich innych xj (licznik jest równy zero), można łatwo za pomocą postaci Lagrange'a interpolować dowolną funkcję:
Wielomian ten będzie się zgadzał z funkcją f we wszystkich punktach xi.
Szybka transformacja Fouriera
Szybka transformacja Fouriera (ang. fast Fourier transform, FFT) – algorytm liczenia dyskretnej transformaty Fouriera oraz transformaty do niej odwrotnej.
Czasem używana jest też forma szybka transformata Fouriera w odniesieniu do tej metody. Ściśle jednak transformacja jest przekształceniem, a transformata wynikiem tego przekształcenia.
Niech x0, ...., xN-1 będą liczbami zespolonymi, wtedy dyskretna transformata Fouriera jest określona wzorem:
Obliczanie tych sum za pomocą powyższego wzoru zajęłoby O(N2) operacji.
Algorytmy (jak algorytm Cooleya-Tukeya) obliczające szybką transformację Fouriera bazują na metodzie dziel i zwyciężaj, rekurencyjnie dzieląc transformatę wielkości N = N1N2 na transformaty wielkości N1 i N2 z wykorzystaniem O(N) operacji mnożenia.
Najpopularniejszą wersją FFT jest FFT o podstawie 2. Jest to bardzo efektywna operacja, jednak wektor próbek wejściowych (spróbkowany sygnał) musi mieć długość N=2^k, gdzie k to pewna liczba naturalna. Wynik otrzymuje się na drodze schematycznych przekształceń, opartych o tak zwane struktury motylkowe.
Złożoność obliczeniowa Szybkiej transformacji Fouriera wynosi O(N \log_2 N), zamiast O(N^2) algorytmu wynikającego wprost ze wzoru określającego dyskretną transformatę Fouriera. Dzięki istnieniu takiego algorytmu praktycznie możliwe stało się cyfrowe przetwarzanie sygnałów (DSP), a także zastosowanie dyskretnych transformat kosinusowych (DCT) (JPEG, MP3 itd.) do kompresji.
