Interpolacja

Zadaniem interpolacji jest podanie przybliżonych wartości funkcji w punktach nie będących węzłami oraz oszacowanie błędów tych przybliżeń. W tym celu należy znaleźć funkcję F(x) zwaną funkcją interpolującą, która w węzłach (punkty tablicowe) przyjmuje takie same wartości, jak funkcja z tablicy wartości F(x_i)=f(x_i). Można powiedzieć, że interpolacja jest w pewnym sensie zadaniem odwrotnym do tablicowania funkcji - przy tablicowaniu mając analityczną postać funkcji budujemy tablicę jej wartości. Przy interpolacji na bazie tablicy wartości funkcji określamy jej postać analityczną. Funkcji interpolującej poszukuje się najczęściej jako funkcji pewnej określonej postaci - mogą to być wielomiany algebraiczne. Dla takiej funkcji łatwo wykonuje się różne działania (arytmetyczne, różniczkowanie i całkowanie) ponadto informacja o takich funkcjach nie obciąża pamięci maszyny.

Interpolacja wielomianowa

Interpolacyjne Lagrange'a

Zagadnienie interpolacyjne Lagrange'a charakteryzuje się wymaganiem, aby wartości funkcji interpolującej równały się wartościom funkcji interpolowanej w n+1 punktach.

Twierdzenie:

Zagadnienie interpolacji Lagrange'a ma jednoznaczne rozwiązanie postaci:

(1)

Przykład:

x	81	100	121
f(x)	9	10	11

(aby otrzymać przybliżoną wartość
należy do powyższego wielomianu wstawić za x 97)

Postać (1) wielomianu Lagrange'a nie jest wygodna w zastosowaniach praktycznych. Wykorzystuje się tu tzw. postać Newtona wielomianu Lagrange'a, to jest postać (2)
, gdzie p_k(x) wielomiany definiowane następująco:

p₀(x) = 1;

p_k(x)=(x-x₀)(x-x₁)...(x-x_k-1), k>0, a

Współczynniki b_k noszą nazwę ilorazów różnicowych funkcji f opartych na węzłach x₀ do x_k. Zapisujemy to b_k=f[x₀,x₁,...,x_k].

Definicja:

Ilorazem różnicowym rzędu k funkcji f opartym na parami różnych węzłach x_l,x_l+1,...,x_l+k (punkty należą do dziedziny funkcji f) nazywamy wyrażenie:

Twierdzenie:

Dla dowolnego układu parami różnych węzłów x_l,x_l+1,...,x_l+k z dziedziny funkcji f zachodzi następujący wzór rekurencyjny:

f[x_l]=f(x_l)

Przykład:

x	x0	x1	x2
f(x)	f(x0)	f(x1)	f(x2)

Algorytmiczne obliczenie współczynników b_k we wzorze (2):

X	f(x)	f[*,*]	f[*,*,*]	f[*,*,*,*]	f[*,*,*,*,*]
x0	f(x0)
x1	f(x1)	f[x0,x1]
x2	f(x2)	f[x1,x2]	f[x0,x1,x2]
x3	f(x3)	f[x2,x3]	f[x1,x2,x3]	f[x0,x1,x2,x3]
x4	f(x4)	f[x3,x4]	f[x2,x3,x4]	f[x1,x2,x3,x4]	f[x0,x1,x2,x3,x4]

Współczynniki b_k ze wzoru (2) są równe odpowiednio zaznaczonym wartościom.

Jeżeli rzeczywiste węzły x₀,...,x_n są uporządkowane rosnąco lub malejąco to przedstawiony algorytm jest numerycznie poprawny ze względu na każdy iloraz różnicowy brany z osobna. Nie jest numerycznie poprawny ze względu na całą tablicę wyznaczonych ilorazów.

Często węzły interpolacyjne są rzeczywiste i równoodległe, to znaczy i-ty węzeł x_i=x₀+ih, i=0(1)h

Zawsze można znaleźć takie t, że x=x₀+th

Interpolacja Hermite'a

Przy interpolacji Hermite'a danych jest k+1 różnych węzłów x₀,...,x_k oraz liczby naturalne m₀,...,m_k takie, że
, zadanie interpolacji Hermite'a polega na znalezieniu dla danej tablicy funkcji f wielomianu H_n stopnia nie większego niż n spełniającego warunki:

; i=0(1)k ; j=0(1)m_i-1 w szczególności, gdy m_i=1 dla i=0(1)k interpolacja Hermite'a sprowadza się do interpolacji Lagrange'a.

Twierdzenie:

Zagadnienie interpolacji Hermite'a ma jednoznaczne rozwiązanie.

Dla wprowadzenia postaci szukanego wielomianu H_n definiujemy funkcję:

Zauważmy, że każda 0≤l≤n daje się jednoznacznie przedstawić w postaci l=s(i)+j, gdzie i=0(1)k, j=0(1)m_i-1.

Definiujemy wielomiany

p₀(x)=1

Ilorazy różnicowe przypadek węzłów krotnych

Definicja:

Przy podanych poniżej założeniach funkcji f jej ilorazy różnicowe oparte na węzłach krotnych określa się zależnościami

1. dla i-krotnego węzła x_j :

dla różnych węzłów x_s,x_s+1,...,x_s+k o krotnościach i_s,i_s+1,...,i_s+k iloraz różnicowy określa zależność:

Zakładamy tu istnienie pochodnych f rzędu j w punkcie x_s+m gdzie: f^(j)(x_s+m); m=0,1,...,k, j=0,1,...,i_s+m-1, w przypadku węzłów jednokrotnych definicja ta pokrywa się z definicją ilorazów różnicowych.

Twierdzenie:

Współczynniki b_l (l=s(i)+j, i=0,...,k j=0,m_i-1) postaci Newtona wielomianu Hermite'a są równe ilorazom różnicowym interpolowanej funkcji f opartym na początkowych i-1 węzłach x_i z uwzględnieniem ich krotności oraz na węźle x_i z krotnością j+1, tzn.

b_l=b_s(i)+j=f[x₀,m₀;...;x_i-1,m_i-1;x_i,j+1]

Tak, więc rozwiązanie zadania interpolacyjnego Hermite'a jest jednoznacznie określonym wielomianem postaci:

Reszta interpolacyjna

Postać reszty interpolacyjnej r(x)=f(x)-H_n(x) . Zauważmy, że z warunków interpolacyjnych wynika, iż węzły są m_i-krotnymi zerami funkcji r(x). Możemy, zatem resztę r(x) przedstawić w postaci: r(x)=p_n+1(x)g(x) gdzie

Funkcja g(x) jest określona jednoznacznie poza węzłami x_i.

Twierdzenie:

Jeżeli funkcja f jest m_i-1-krotnie różniczkowalna w punktach x_i (i=0,1,...,k) to dla x (x≠x_i) nie będących węzłami: r(x) = p_n+1(x)f[x₀,m₀;...;x_k,m_k,x]

Twierdzenie:

Jeżeli rzeczywista funkcja f ma ciągłą n+1 pochodną na przedziale [a,b] zawierającym węzły x_i i punkt x to istnieje punkt ξ∈[a,b] taki, że:

Przykład:

Ocenić, z jaką dokładnością można obliczyć ln100,5 za pomocą interpolacji Lagrange'a, jeżeli dane są wartości:

	x	f(x)
x0	100	ln100
x1	101	ln101
x2	103	ln103

n=2

f(x)=lnx

Uwzględniając postać reszty i bazując na interpolacji Hermite'a otrzymujemy zależność:

f(x)=H_n(x)+r(x)

Interpolacja funkcjami sklejania

Uzyskanie poprawnych przybliżeń interpolacyjnych wobec postaci reszty wiąże się ze zwiększeniem stopnia wielomianu interpolacyjnego. Ponieważ podejście takie jest bardzo kosztowne obarczone potencjalnym dużym błędem numerycznym stosuje się inne metody. Jedną z takich metod jest wykorzystywanie funkcji sklejanych (spline).

Zadanie interpolacyjne

Niech (Δ) będzie układem punktów x₀,...,x_n dzielących przedział [a,b] na N części

(Δ): a=x₀<x₁<...<x_n=b

W każdym z podprzedziałów (x_i,x_i+1) przybliżamy funkcję wielomianem ustalonego stopnia (możliwie niskiego). Istotne jest, aby tak skonstruowane przybliżenie będące na każdym z podprzedziałów wielomianem (na ogół różnym) było ciągłe wraz z odpowiednimi pochodnymi na całym przedziale [a,b]. Funkcjami mającymi takie własności są na przykład tak zwane funkcje sklejane.

Definicja:

Funkcję rzeczywistą S nazywamy funkcją sklejaną stopnia m z węzłami (Δ), jeżeli:

1. w każdym przedziale (x_i-1,x_i) dla i=0,1,..,N+1

(z definicji x_-1=-∞, x_N+1=∞) S jest wielomianem stopnia nie większego niż m

2. S i jej pochodne rzędu 1,2,...,m-1 są ciągłe na całej osi rzeczywistej (S∈C^m-1)

Szczególnym przypadkiem funkcji sklejanych są wielomiany.

Definicja:

Funkcję sklejaną stopnia 2m-1 z węzłami (Δ) nazywamy neutralną funkcją sklejaną, jeżeli (-∞,x₀) i (x,∞) dana jest wielomianami stopnia m-1, a nie stopnia 2m-1. Klasą funkcji sklejanych stopnia m o węzłach (Δ) będziemy oznaczali symbolem S_m(Δ), a klasę naturalnych funkcji sklejanych stopnia 2m-1 symbolem N_2m-1(Δ).

Lemat:

Dowolna funkcja sklejana S∈S_m(Δ) daje się jednoznacznie przedstawić w postaci:

gdzie:

p(x) jest wielomianem stopnia co najwyżej m.

Przykład:

Zbadać własności różniczkowe funkcji z(x)=(x-x_i)^m_t gdy m=2.

z'(x_i)_-=0

z'(x_i)₊=0

funkcja jest różniczkowalna w x_i jest nieciągła w x_i.

W przypadku ogólnym:

funkcja ta ma ciągłe pochodne do rzędu m-1 i pochodną rzędu m nieciągłą w x_i.

Lemat:

Dowolna funkcja S∈N_2m-1(Δ) daje się jednoznacznie przedstawić w postaci:

,

gdzie p(x) wielomian stopnia nie wyższego niż m-1, a współczynniki a_j spełniają równania:

r=0,...,m-1

Twierdzenie:

Jeżeli węzły x_i są różne dla i=0,...,N oraz 1 ≤ m ≤ N+1 to dla dowolnych wartości y_i istnieje dokładnie jedna naturalna funkcja sklejania S∈N_2m-1(Δ) interpolująca punkty (x_i,y_i), tzn. taka funkcja S, że S(x_i)=y_i, i=0,...N

Przykład:

Skonstruować naturalną funkcję interpolacyjną sklejaną S stopnia 1 interpolującą punkty (x_i,y_i), i=0,...,N.

2m-1=1 → m=1, czyli p(x) ma stopień 0.

W każdym, z podprzedziałów [x_i,x_i+1] i=0,...,N-1 funkcja S ma postać S(x)=a_i+b_it, gdzie t=x-x_i

Z warunków interpolacyjnych:

S(x_i)=y_i=a_i, i=0,...,N-1

Z ciągłości funkcji S w punktach x_i (i=1,...,N-1) mamy:

a_i+b_ih_i=a_i+1,

h_i=x_i+1-x_i,

Stąd:
, i=0,...,N-1

Stąd:

,

, i=0,...,N-1

Interpolacja odwrotna

Jest to jeden z naturalnych sposobów rozwiązania równań postaci f(x)=0. Załóżmy, że dana jest tablica funkcji (argumenty i wartości).

x	..................
f(x)	..................

Chcemy obliczyć pierwiastek równania f(x).

Należy zauważyć, że wyznaczenie punktu x takiego, że f(x)=0 jest równoważne znalezieniu wartości funkcji g odwrotnej do funkcji f w 0. W tym celu należy zmodyfikować tabelę funkcji f następująco:

f(x)	f(x0)	f(x1)	......	f(xn)
g^-1(f(x))	x0	x1	......	xn

Traktując wartość funkcji f jako węzły interpolacyjne konstruuje się wielomian interpolacyjny i wartość tego wielomianu w 0 będzie stanowić przybliżenie szukanego zera funkcji f.

Przy rozwiązywaniu tego zagadnienia zakładamy, że funkcja f spełnia założenia twierdzenia o funkcji odwrotnej i że szukany pierwiastek leży w zbiorze wyznaczonym przez węzły interpolacji.

Zagadnienie interpolacji Taylora

Wzór Taylora jest dość często wykorzystywanym narzędziem w analizie matematycznej i jej zastosowaniach, włącznie z metodami numerycznymi. Jest on pewnym uogólnieniem tak zwanego wzoru różnic skończonych. Ma on postać następującą:

Innymi słowami, jeżeli funkcja określona jest w pewnym otoczeniu punktu x₀ oraz posiada pochodną n-tego rzędu w tym otoczeniu, to wielomian algebraiczny

może służyć jako przybliżenie funkcji f w rozpatrywanym otoczeniu. Bliskość f i p charakteryzuje się tym, że n+1 funkcjonałów liniowych ma odpowiednio równe wartości dla f i p. Funkcjonały te mają postać

Rzeczywiście dla wielomianu

mamy

więc

k=0,1,2,...,n.

Wyznacznik w tym przypadku wygląda następująco:

i oczywiście jest różny od zera. Tym samym zapewnione jest istnienie oraz jednoznaczność wielomianu interpolacyjnego we wzorze Taylora, przy warunku, że jest on rozwiązaniem zagadnienia interpolacyjnego określonego na podstawie funkcjonałów

Jeżeli x₀=0 wzór Taylora nazywany jest wzorem Maclaurina.

Wzór Taylora jest bardzo wygodnym narzędziem do przybliżenia funkcji, gdy interesują nas wartości f w bliskim otoczeniu punktu x₀.

Zagadnienie interpolacji Abela-Gonczarowa

Zagadnienie interpolacyjne Niels'a Henryk'a Abela'a i W.L.Gonczarowa polega na znalezieniu takiego wielomianu interpolacyjnego danej funkcji, że jego wartość równa jest wartości funkcji w danym punkcie x₀, natomiast wartości pierwszych pochodnych równe są w innym punkcie, wartości drugich pochodnych - jeszcze w innym punkcie itd. Ściślej mówiąc, zagadnienie to charakteryzuje się następującym ciągiem funkcjonałów liniowych:

.

Węzły x₀,x₁,x₂,...,x_n mogą być dowolne. Gdy wszystkie węzły takie same, wtedy zagadnienie sprowadza się do zagadnienia interpolacyjnego Taylora.

Wyznacznik dla ropatrywanego problemu jest postaci:

jest on zawsze różny od zera. Więc istnieje jednoznacznie określony wielomian p(x) n-tego stopnia, który spełnia równości

k=0,1,2,...,n.

Wyraźmy p(x) za pomocą wielomianów

Oczywiście A_k(x) jest wielomianem algebraicznym stopnia k, który spełnia warunki

Z ostatnich równości wynika, że rozwiązanie zagadnienia interpolacyjnego Abela-Gonczarowa wyraża się wzorem:

który nazywa się wzorem interpolacyjnym Abela-Gonczarowa.

Interpolacja za pomocą wielomianów trygonometycznych

Wielomiany trygonomertyczne, tak samo jak wielomiany algebraiczne, są najczęściej spotykanym narzędziem stosowanym do przybliżania funkcji. Wielomian trygonometryczny rzędu m jest postaci

.

Jest więc on wielomianem uogólnionym względem funkcji bazowych

1, cosx, sinx, cos2x, sin2x, ..., cosnx, sinnx.

Ponieważ każdy wielomian trygonometryczny rzędu m jest kombinacją liniową 2m+1 funkcji bazowych, to w sformułowaniu odpowiedniego zagadnienia interpolacyjnego bierze udział 2m+1 funkcjonałów liniowych. Z powodu okresowości wielomianów trygonometrycznych w przedziale postaci [a,a+2π].

Zagadnienie interpolacyjne Lagrange'a dla wielomianów trygonometrycznych sformułować można analogicznie jak dla wielomianów algebraicznych. Wymagane jest przy tym, aby węzły znajdowały się w przedziale postaci [a,a+2π].

Niech x₀,x₁,x₂,...,x_2m będą 2m+1 różnymi liczbami z przedziału [0,2π]. Ciąg funkcjonałów liniowych dla tego zagadnienia jest postaci

l_k(f)=f(x_k); k=0,1,2...,2m.

Funkcje

są wielomianami trygonometrycznymi rzędu m, dla których zachodzi

(1)

Istotnie, powyższą równość (1) można bezpośrednio sprawdzić, zaś fakt, że ϕ_m,k(x) jest wielomianem trygonometrycznym rzędu m wynika ze znanych tożsamości trygonometrycznych.

Uwzględniając tożsamość (1) trygonometryczny wielomian interpolacyjny Lagrange'a zapisać można w sposób następujący:

Zagadnienie interpolacyjne Lagrange'a ma w tym przypadku dokładnie jedno rozwiązanie.

Interpolacja Padé

Przy ogólnym sformułowaniu zagadnienia interpolacyjnego, jako zbiór funkcji interpolujących w większości przypadków wybierana jest przestrzeń liniowa skończenie wymiarowa. W ten sposób każdą funkcję interpolującą przedstawić można za pomocą skończonego ciągu liczb. Wymaganie o reprezentacji funkcji interpolującej będzie spełnione również wtedy, gdy zbiór funkcji nie jest przestrzenią liniową skończenie wymiarową. Przykładem takiego zbioru jest zbiór funkcji wymiernych.

Oznaczamy przez R_p,q zbiór funkcji wymiernych, dla których licznik jest najwyżej stopnia p, zaś mianownik - stopnia q.

Innymi słowy, jeżeli r∈ R_p,q, to

oraz m ≤ p,n ≤ q. Ponieważ pomnożenie licznika i mianownika przez tę samą liczbę, różną od zera, nie zmienia wartości ułamka, to każdy element, należący do R_p,q, określony jest jednoznacznie za pomocą p+q+1 liczb.

Zagadnienie interpolacyjne Padé jest odpowiednikiem zagadnienia interpolacyjnego Taylora, przy czym zamiast wielomianów algebraicznych funkcjami interpolującymi są funkcje wymierne. Ciąg funkcjonałów, charakteryzujących to zagadnienie, jest postaci

l_k(f)=f^(k)(x₀); dla k=0,1,2,...p+q.

Niech dana będzie funkcja f. Poszukujemy funkcji wymiernej r, należącej do R_p,q, dla której l_k(r)=l_k(f) lub r^(k)(x₀)=f^(k)(x₀), k=0,1,2,...,p+q.

Gdy q=0, interpolacja Padé sprowadza się do interpolacji Taylora.

Problem istnienia i jednoznaczności wymiernej funkcji interpolującej nie da się rozwiązać tak samo jak w przypadku skończenie wymiarowej przestrzeni funkcji interpolujących. Łatwo jest stwierdzić, że to zagadnienie może nie mieć rozwiązania.

Materiały pomocnicze:

Wykłady prof. dr hab. Szulca

B. Senedow, „Stare i nowe w metodach numerycznych”

Josef Stoer, Roland Bulirsch, „Wstęp do analizy numerycznej”

Josef Stoer, „Wstęp do metod numerycznych”

Internet

Opracował Marcin Łański

---