Interpolacja

W ograniczonym przedziale rozpatrzmy ciąg punktów:

(1)

które nazywamy węzłami interpolacji oraz ciąg liczb rzeczywistych:

(2)

które interpretujemy jako dane wartości pewnej funkcji Funkcja jest zatem wyznaczana w sposób dyskretny za pomocą jej wartości na zbiorze (1)

(3)

• Zadanie interpolacji polega na znalezieniu takiej funkcji , zwanej funkcją interpolującą, przybliżającej stablicowaną funkcję która w węzłach interpolacji przybiera takie same wartości, co funkcja

• W zadaniu interpolacji na podstawie tablicy wartości funkcji (3) określamy jej postać analityczną, przy wykorzystaniu której można obliczyć wartości funkcji w dowolnym punkcie (*) nie pokrywającym się z węzłami interpolacji.

• Interpolacja funkcji często występuje w praktyce, gdyż funkcje określone na dyskretnym zbiorze argumentów są np.

  • wynikami pomiarów lub wynikami obliczeń numerycznych.

  • Ponadto prawie wszystkie klasyczne wzory różniczkowania i całkowania numerycznego oraz przybliżonego rozwiązywania równań różniczkowych otrzymuje się wprost ze wzorów interpolacyjnych. 

  • Wykresy w Excelu

• (*) ekstrapolacja

• Tabela danych

Interpolacja, ekstrapolacja

Cel interpolacji

Znalezienie funkcji odpowiedniej klasy przechodzącej przez dany zestaw punktów (węzłów) w przestrzeni dwu- lub więcej wymiarowej.

Rodzaje interpolacji:

• Interpolacja wielomianami

• Interpolacja funkcjami wymiernymi

• Interpolacja funkcjami trygonometrycznymi

• Interpolacja funkcjami sklejanymi

Zastosowania interpolacji

• Szacowanie określonych wielkości w punktach pośrednich.

• Prowadzenie gładkich krzywych lub powierzchni przez punkty pomiarowe lub z symulacji (funkcje sklejane).

• Algorytmy numeryczne, np.:

  • Znajdowanie miejsc zerowych funkcji

  • Różniczkowanie i całkowanie numeryczne.

Interpolacja liniowa

Zależnie od postaci funkcji interpolującej sformułowane zadanie interpolacji może mieć dokładnie jedno rozwiązanie, może nie mieć rozwiązań albo mieć ich nieskończenie wiele.

W przypadku wielomianu

(4)

z warunków interpolacji (3) otrzymujemy następujący układ równań liniowych:

(5)

w którym niewiadomymi są współczynniki Wyznacznik podstawowy tego układu równań jest wyznacznikiem Vandermonda

Tak więc układ równań (5) ma dokładnie jedno rozwiązanie, które przyjmujemy jako współczynniki szukanego wielomianu interpolacyjnego (4).

Interpolacja wielomianowa

• Przez n+1 punktów można przeprowadzić unikalny wielomian stopnia n

• Wyznaczanie w opisany sposób wielomianów interpolacyjnych nie jest jednak zadaniem łatwym
  ze względu na:

  • złe uwarunkowanie zadania, wynikające z nie-korzystnej akumulacji błędów (macierz jest pełna i może być nieosobliwa)

  • duży koszt obliczeń spowodowany koniecznością rozwiązywania układu równań liniowych.

• Podajmy ogólniejsze sformułowanie zadania interpolacji, opierające się na przyjęciu liniowo-niezależnego układu funkcji

Niech mamy układ liniowo-niezależnych funkcji

(6)

określonych na ograniczonym lub nieograniczonym przedziale .

Należy znaleźć takie współczynniki

(7)

których kombinacja liniowa z funkcjami (6) spełnia warunki interpolacji (3)

(8)

Zauważmy, że w zadaniu interpolacji (4) - (5) przyjęliśmy następujący układ funkcji liniowo-niezależnych:

(9)

Interpolacja Lagrange’a

Wielomian interpolacyjny (n punktów danych, stopień n-1):

• Tzw. funkcje kardynalne:

• Funkcje kardynalne mają właściwość:

• W punktach węzłowych zawsze tylko jedna ma wartość równą 1, pozostałe są równe zeru

• Np. przypadek n=2 (liniowy):

• Np. przypadek n=3 (kwadratowy):

Macierz charakterystyczna układu równań (8) jest więc macierzą jednostkową i wynika stąd, że wielomian

(12)

jest wielomianem stopnia co najwyżej n, przyjmującym w węzłach interpolacji wartości (3). Otrzymany wielomian nazywany jest wielomianem interpolacyjnym Lagrange’a.

Wprowadzając oznaczenie

(13)

możemy wzór (12) zapisać w postaci

, (14)

gdzie (15)

W charakterze przykładu znajdziemy wielomian interpolacyjny Lagrange’a, który w punktach: -2, 1, 2, 4 przyjmuje wartości: 4, 2, -1, 10. Ze wzoru (12) dla n = 3 mamy

W szczególnym przypadku dla n = 1 ze wzoru (12) otrzymamy znany wzór interpolacji liniowej

W podobny sposób dla n = 2 wyznaczymy równanie paraboli przechodzącej przez trzy punkty:

(16)

Jeśli węzły interpolacji są równoodległe

(17)

gdzie: (), wtedy po wprowadzeniu pomocniczej zmiennej

(18)

wielomian oraz jego pochodną można zapisać następująco:

(19)

co pozwala na znaczne uproszczenie postaci wielomianu interpolacyjnego (14)

Oszacowanie błędu wzoru interpolacyjnego

Uwaga! Wyższy stopień wielomianu interpolacyjnego (więcej węzłów) wcale nie musi oznaczać poprawy jakości interpolacji. Przykładem negatywnym jest interpolowanie funkcji y=|x| lub y=1/(1+ax²). Wręcz przeciwnie: im niższy stopień wielomianu tym bezpieczniej.

INTERPOLACJA NEWTONA

Interpolacja Newtona jest oparta na przyjęciu jako układu funkcji liniowo-niezależnych wielomianów czynnikowych postaci:

(21)

Po podstawieniu tej bazy do (8) otrzymujemy układ równań z trójkątną macierzą charakterystyczną:

(4.22)

Przed rozwiązaniem tego układu równań niezbędne jest wprowadzenie pojęcia ilorazów różnicowych. Dla funkcji określonej na dyskretnym zbiorze argumentów (3) definiujemy ilorazy różnicowe pierwszego rzędu:

(23)

oraz rekurencyjnie ilorazy różnicowe rzędu k

(24)

Obliczanie powyższych ilorazów różnicowych można wykonać w łatwiejszy sposób przy wykorzystaniu zależności

(25)

lub posługując się następującą tablicą ilorazów różnicowych:

Przykładowo dla wielomianu trzeciego stopnia dla węzłów interpolacji: tablica ilorazów różnicowych ma postać:

Rozwiązując kolejne równania układu równań (22) otrzymujemy:

(26)

Tak więc wzór interpolacyjny Newtona ma postać:

(27)

Współczynniki   wielomianu interpolacyjnego Newtona

(28)

można wyznaczyć również w inny sposób, wykorzystując zależność rekurencyjną

Wielomiany mają współczynnik równy jedności przy zatem współczynnik jest równy współczynnikowi przy w wielomianie interpolacyjnym Lagrange’a

Stąd oraz na mocy związku (25) jest

Przykład. Znaleźć wielomian interpolacyjny Newtona, który w punktach: 0, 2, 3, 5 przyjmuje
wartości: 1, 3, 2, 5.

Sporządzamy najpierw tablicę ilorazów różnicowych:

i następnie otrzymujemy

Wyznaczanie przedziałów izolacji

• Można stwierdzić, że jeżeli znaki funkcji na granicach przedziału są jednakowe, to równanie w przedziale [a,b] nie ma pierwiastka lub ilość ich jest parzysta.

• Jeżeli znaki są różne, oznacza to, że przedział [a,b] zawiera chociażby jeden pierwiastek.

• Zadanie polega na odnalezieniu takich przedziałów [x_i,x_i+1] ⊂ [a, b], które zawierają pojedyncze pierwiastki.

• W tym celu będziemy obliczać wartości funkcji F(x) od punktu x=a do x=b z krokiem h (dostatecznie małym). Jeżeli w sąsiednich punktach funkcja ma przeciwne znaki:

• F(x)F(x+h)<0,

• będzie to oznaczało, że przedział [x, x+h] zawiera pierwiastek.

• Można dopełnić algorytm sprawdzaniem na każdym kroku spełnienia warunku:

• (F(x)-F(x-h))(F(x+h)-F(x))>0.

• W przeciwnym przypadku krok należy dzielić na pół dopóki nie przekonamy się, że pierwiastka w przedziale nie ma.

Metoda bisekcji

Metoda równego podziału (metoda połowienia, metoda bisekcji, metoda połowienia przedziału) - jedna z metod rozwiązywania równań nieliniowych. Opiera się ona na następującym twierdzeniu: Jeżeli funkcja ciągła f(x) ma na końcach przedziału domkniętego wartości różnych znaków, to wewnątrz tego przedziału, istnieje co najmniej jeden pierwiastek równania f(x) = 0.

Mamy daną funkcję f(x) oraz przedział <a,b>, w którym będziemy poszukiwali miejsca zerowego. Aby można było zastosować algorytm połowienia muszą być spełnione poniższe warunki:

Funkcja f(x) jest określona w każdym punkcie przedziału <a,b>. Określoność funkcji oznacza, iż dla każdej wartości argumentu x z przedziału <a,b> potrafimy policzyć wartość funkcji.

Kroki algorytmu

Gdy funkcja f(x) spełnia powyższe trzy warunki, to w przedziale <a,b> zagwarantowane jest istnienie pierwiastka i możemy go wyszukać algorytmem połowienia. Zasada jest następująca:

1. Wyznaczamy punkt x_o jako środek przedziału <a,b>.

2. Obliczamy wartość funkcji w punkcie x_o. Sprawdzamy, czy f(x_o) znajduje się dostatecznie blisko 0:

3. Jeśli nierówność jest spełniona, to x_o jest poszukiwaną wartością pierwiastka. Zwracamy wynik i kończymy algorytm. W przeciwnym razie za nowy przedział poszukiwań pierwiastka przyjmujemy tą połówkę <a,x_o> lub <x_o,b>, w której funkcja zmienia znak na krańcach i przechodzimy ponownie do punktu 1.

Warunki zakończenia obliczeń

Algorytm powtarzamy od początku dotąd, aż:

1. znajdziemy pierwiastek, czyli spełniona będzie nierówność

2. przedział <a,b> osiągnie założoną długość (może to być również epsilon)

3. wykonamy określoną ilości iteracji.

Metoda stycznych

Metoda stycznych (Newtona) opiera się na następującej zasadzie: dla danego przybliżenia początkowego x₀ tworzy się ciąg x₁, x₂, …

Element x_n+1 wyznaczamy aproksymując funkcję f(x) styczną do jej wykresu w punkcie (x_n, f(x_n)) i wybierając x_n+1 jako odciętą punktu przecięcia tej stycznej z osią x. Dlatego do wyznaczenia x_n+1 służy równanie:

f(x_n) + (x_n+1 - x_n)f’(x_n) = 0

Metodę Newtona określa następujący wzór iteracyjny:

x_n+1 = x_n + h_n gdzie h_n = -f(x_n)/f’(x_n)

Kroki algorytmu

1. Sprawdzamy, czy w punkcie x0 funkcja spełnia warunek: f’(x₀) f’’(x₀) > 0

2. Obliczamy kolejną iterację z wcześniej podanego wzoru.

3. Sprawdzamy, czy otrzymane przybliżenie jest dostatecznie bliskie zeru.

Wybieranie punktu początkowego w przypadku, gdy dany jest przedział izolacji pierwiastka

Jeżeli dany jest przedział [a,b] występowania pierwiastka, to możemy posłużyć się następującą zasadą wyboru punktu początkowego, aby proces był stabilny:

1. jeżeli f’(a) f’’(a) > 0 to x₀ = a;

2. jeżeli f’(a) f’’(a) < 0 to x₀ = b.

Oczywiście na krańcach przedziału funkcja musi posiadać przeciwne znaki, gdyż gwarantuje to istnienie pierwiastka.

Warunki zakończenia algorytmu

1. wartość f(x_n) leży dostatecznie blisko zera – o mniej niż zadana dokładność

2. wartość h_n jest mniejsza od zadanej dokładności

Metoda cięciw (reguła falsi)

Niech dany będzie przedział izolacji pierwiastka funkcji f(x) pokazanej na rysunku – [a,b]. Jako pierwsze przybliżenie wybieramy punkt przecięcia prostej łączącej punkty (a,f(a)) i (b,f(b)) z osią x.

Punkt przecięcia można wyznaczyć ze wzoru: x₁ = a - f(a)(b - a)/(f(b) - f(a)).

Do wyznaczenia drugiego przybliżenia x₂ bierze się drugi zestaw punktów (x₁,f(x₁)) i (b,f(b)), otrzymując:

x₂ =x₁ - f(x₁)(b - x₁)/(f(b) - f(x₁)).

Ogólnie można napisać, że w i+1 przybliżeniu wartość pierwiastka wynosi:

x_i+1 = x_i - f(x_i)(b - x_i)/(f(b) - f(x_i)).

Dla funkcji pokazanej na rysunku przybliżenia mają następującą postać:

x₁ = b - f(b)(a - b)/(f(a) - f(b)).

x₂ =x₁ - f(x₁)(a - x₁)/(f(a) - f(x₁)).

x_i+1 = x_i - f(x_i)(a - x_i)/(f(a) - f(x_i)).

Ogólnie można napisać:

x_i+1 = x_i - f(x_i)(x_p - x_i)/(f(x_p) - f(x_i))

gdzie xp to a lub b zgodnie z następującą regułą:

1. jeżeli f’(c) f’’(c) > 0 to x_p = b;

2. jeżeli f’(c) f’’(c) < 0 to x_p = a,

gdzie c = (a + b)/2.

Kompresja

Kompresja BEZSTRATNA

Nie dopuszcza utraty informacji, czyli po dekompresji otrzymujemy dane zgodne z oryginałem.

• W zależności od rodzaju danych wejściowych potrafi zmniejszyć je o 20-50%

• Używana tam, gdzie nie można dopuścić żadnej różnicy pomiędzy danymi oryginalnymi a danymi uzyskanymi z rekonstrukcji

• Kompresja tekstów (do not send money != do now send money)

• Kompresja baz danych banków (500.00zł != 5.00zł)

• Kompresja obrazów medycznych

• Kompresja programów komputerowych (błędna działanie)

Kompresja STRATNA

Dopuszcza pewną stratę informacji. Dane, które zostały skompresowane w ten sposób, nie można zazwyczaj odtworzyć dokładnie z wersji zakodowanej.

• Lepszy stopień kompresji niż w przypadku kompresji bezstratnej, nawet 90%

• Kompresja mowy( nie jest potrzebna dokładna wartość każdej próbki mowy)

• Kompresja wideo( np. MPEG, AVI, MOV)

• Kompresja obrazów( redukcja liczby barw, JPEG)

• Kompresja dźwięku( ucho ludzkie jest w stanie usłyszeć dźwięki z zakresu 4Hz – 15 Hz, VOC, WAV, MPEG, Layer 1,MP3)

• Miary jakości kompresji

• Algorytmy kompresji można oceniać według różnych kryteriów. Możemy mierzyć:

• złożoność algorytmu kompresji

• pamięć potrzebną do implementacji algorytmu

• szybkość działania algorytmu na konkretnym komputerze

• rozmiar kompresji

• podobieństwo danych po rekonstrukcji do danych oryginalnych

Sensowną miarą tego, jak efektywnie algorytm kompresuje określony zbiór danych, jest stosunek liczby bitów potrzebnych do reprezentacji danych przed kompresją do liczby bitów potrzebnych do reprezentacji danych po kompresji. Proporcja ta nazwana jest stopniem kompresji. np. Przyjmijmy, że dla obrazu będącego kwadratową tablicą o rozmiarze 256x256 pikseli potrzeba 65536 bajtów. Jeśli skompresowana postać tego obrazu zajmuje 16384 bajty, to stopień kompresji wynosi 4:1

Stopień kompresji można przedstawić jako redukcję rozmiaru danych wyrażoną procentowo względem rozmiaru danych oryginalnych ( 75%)

Średnia bitowa – średnia liczba bitów potrzebna do reprezentacji pojedynczej próbki(2 gdy przyjmiemy, że na piksel przypada 8 bit)

Metoda kodowania długich serii

• Metoda ta nie potrzebuje żadnych informacji początkowych o danych wejściowych, zostają one na bieżąco czytane, kodowane i zapisywane do wyjścia.

• Opiera się na zastępowaniu serii takich samych danych (znaków) występujących po sobie rekordem danych, w którym znajduje się na przykład tylko liczba wystąpień tej samej danej (długości serii) oraz wzorca.

• Zakodowane w ten sposób dane nie dają gwarancji poprawnego rozkodowania, gdyż nie jesteśmy w stanie rozpoznać czy nadchodząca dana jest licznikiem powtórzeń czy dana. Dlatego należy dodać tzw. marker.

Metoda unikatowej wartości

• Blok danych wejściowych dzielony jest na podbloki danych w ten sposób, aby na przykład w każdym podbloku nie występowała jedna wartość z przedziału wszystkich dozwolonych wartości.

• W każdym podciągu nie występuje tylko jedna z zakresu dozwolonych wartości i ona zostaje ustawiona jako marker dla danego podciągu

• Następnie kompresji podlegają podciągi w ten sposób, że wykryta seria powtórzeń zastępowana jest rekordem zawierającym: marker, długość serii, dana powtarzana

• Opłacalna, gdy liczba powtarzających się wartości jest większa niż 2

• Metodą ta kompresowane są np.. Pliki graficzne w formacie PIC (PC Paint)

Metoda RLE (Run Length Encoding)

• Jawnie nie występuje marker ponieważ dane dzielone są na dwa rodzaje serii: serie danych powtarzających się i serie danych swobodnych

• Po serii danych swobodnych nastąpi seria powtarzających się danych (jedynie po serii danych powtarzających się może wystąpić następna seria danych powtarzających się)

• Wprowadza znacznik przed długością serii, który informuje jaka to będzie seria (wystarczy 1 bit)

• Aby nie tracić na kompresji serie danych powtarzających się o długości < 3 traktujemy jako dane swobodne o ile istnieje taka możliwość

• Stosowana w formatach animacji FLI,FLC

Metoda HUFFMANA (1960)

• Oparta na statycznym rozkładzie prawdopodobieństwa wystąpienia znaków

• Zamianie na krótszą podlega reprezentacja znaków występujących w wejściu

• Np. Jeśli znak „B” był w wejściu reprezentowany w kodzie ASCII czyli był 8-bitowa daną, to po kodowaniu może zajmować np. 6 bitów.

• Do realizacji kodowania należy utworzyć strukturę drzewa znaków, występujących w wejściu, drzewa zbudowanego w specjalny sposób na podstawie częstotliwości występowania każdego znaku w wejściu.

• Wykorzystywany często jaki ostatni etap kompresji złożonej (zmniejszają rozmiar o 20 -40 %)

• Radzi sobie dobrze zarówno z grafiką, tekstem czy modułami wykonywalnymi

• Wadą jest szybkość działania

Budowa drzewa Huffmana

Założenia:

• Waga danego węzła jest sumą wag jego liści

• Waga korzenia jest liczbą znaków w wejściu

• Idąc do korzenia do końcowego liścia wartości wag muszą być malejące

Algorytm:

• Utwórz listę pojedynczych drzew z każdego znaku o wadze odpowiadającej liczbie wystąpień tego znaku w wejściu

• Dopóki pozostały przynajmniej 2 drzewa w liście:

1. Pobierz dwa drzewa o najmniejszej wadze i użyj ich jako liści do nowego drzewa, którego wagą będzie suma jego liści

2. Dwa pobrane drzewa usuń z listy wstawiając tam nowopowstałe

3. Wejście: ciąg 17 znaków = AGAAKHAGAAHKAKHA

1. Wybierz dwa znaki o najmniejszej liczbie wystąpień i utwórz z nich liście korzenia drzewa, w którym zapisz sumę ich wag

2. Wybierz następne dwa znaki o najmniejszych wagach i utwórz z nich taką sama strukturę

3. Kolejna dwa najmniejsze wagi to wagi powstałych korzeni dlatego potraktuj je jako liście następnego korzenia drzewa

4. Na koniec został tylko korzeń z waga 9 i znak „A” z wagą 8. Połącz je ze sobą. Efektem końcowym jest drzewo Huffmana z wagą końcową korzenia równą liczbie wszystkich znaków

5. Do każdego znaku prowadzi tylko jedna droga. Oznaczając na każdym węźle drogę do lewego liścia przez 0, a do prawego poprzez 1, możemy wygenerować drogę od korzenia drzewa do każdego znaku poprzez ciąg zerojedynkowy, czyli liczbę binarna

6. Im znak występuje częściej w danych wejściowych tym przypisany ma krótszy kod.

W naszym przykładzie:

Wejście:AGAAKHAGEAAHKAKHA, długość = 17[bajtów] = 136 [bitów]

Wyjście:10011101001110011101101010100111, długość =32[bity]