Personal tools

MN11

From Studia Informatyczne


Spis treści

Funkcje sklejane (splajny)

<<< Powrót do strony głównej przedmiotu Metody numeryczne

Interpolacja wielomianami interpolacyjnymi, chociaż korzysta z funkcji gładkich i łatwo reprezentowalnych w komputerze, ma jednak również pewne wady. Zauważmy, że błąd interpolacji może być bardzo duży (zjawisko Rungego), a poza tym interpolacja jest nielokalna: nawet mała zmiana warości funkcji w pojedynczym węźle może powodować dużą zmianę zachowania całego wielomianu interpolacyjnego. Czasem więc lepiej jest zastosować innego rodzaju interpolację, np. posługując się funkcjami sklejanymi, które tylko lokalnie są wielomianami, sklejonymi w taki sposób, by globalnie zachować pewien stopień gładkości, tzn. różniczkowalność zadaną liczbę razy.

Tego typu podejście okazało się bardzo owocne m.in. w grafice komputerowej (np. dla wizualizacji scenerii w grach komputerowych), a także np. posłużyło jako narzędzie konstrukcji skalowalnych czcionek komputerowych w Postscripcie (precyzyjniej, korzysta się tam z tzw. krzywych Beziera --- pewnych krzywych sklejanych zadanych na płaszczyźnie). Z krzywych Beziera powszechnie korzysta się również w systemach CAD (Computer Aided Design).

Zamiast terminu funkcje sklejane używa się też często terminów splajny (spline), albo funkcje gięte. Nazwy te biorą się stąd, że zadanie interpolacji naturalnym splajnem kubicznym można interpretować jako model matematyczny aparatu służącego do wytwarzania mebli giętych.

Funkcje sklejane

W ogólności przez funkcję sklejaną rozumie się każdą funkcję przedziałami wielomianową. Nas będą jednak interesować szczególne funkcje tego typu i dlatego termin funkcje sklejane zarezerwujemy dla funkcji przedziałami wielomianowych i posiadających dodatkowe własności, które teraz określimy.

Niech dany będzie przedział skończony \displaystyle [a,b] i węzły

\displaystyle a \,=\, x_0 \,<\, x_1 \,<\, \cdots \,<\, x_n \,=\, b,

przy czym \displaystyle n\ge 1.

Definicja

Funkcję \displaystyle s:R\toR nazywamy funkcją sklejaną rzędu \displaystyle r (\displaystyle r\ge 1) odpowiadającą węzłom \displaystyle x_j, \displaystyle 0\le j\le n, jeśli spełnione są następujące dwa warunki:

(i)
\displaystyle s jest wielomianem stopnia co najwyżej \displaystyle 2r-1 na każdym

z przedziałów \displaystyle [x_{j-1},x_j], tzn. \displaystyle s_{|[x_{j-1},x_j]}\in\Pi_{2r-1}, \displaystyle 1\le j\le n,

(ii)
\displaystyle s jest \displaystyle (2r-2)-krotnie różniczkowalna w sposób

ciągły na całej prostej, tzn. \displaystyle s\in C^{(2r-2)}(R).

Jeśli ponadto

(iii)
\displaystyle s jest wielomianem stopnia co najwyżej \displaystyle r-1 poza

\displaystyle (a,b), tzn. \displaystyle s_{|(-\infty,a]},s_{|[b,+\infty)}\in\Pi_{r-1},

to \displaystyle s jest naturalną funkcją sklejaną.

Klasę naturalnych funkcji sklejanych rzędu \displaystyle r opartych na węzłach \displaystyle x_j będziemy oznaczać przez \displaystyle {\cal S}_r(x_0,\ldots,x_n), albo po prostu \displaystyle {\cal S}_r, jeśli węzły są ustalone.

Na przykład funkcją sklejaną rzędu pierwszego (\displaystyle r=1) jest funkcja ciągła i liniowa na poszczególnych przedziałach \displaystyle [x_{j-1},x_j]. Jest ona naturalna, gdy poza \displaystyle (a,b) jest funkcją stała. Tego typu funkcje nazywamy liniowymi funkcjami sklejanymi.

Najważniejszymi z praktycznego punktu widzenia są jednak funkcje sklejane rzędu drugiego odpowiadające \displaystyle r=2. Są to funkcje, które są na \displaystyle R dwa razy różniczkowalne w sposób ciągły, a na każdym z podprzedziałów są wielomianami stopnia co najwyżej trzeciego. W tym przypadku mówimy o kubicznych funkcjach sklejanych. Funkcja sklejana kubiczna \displaystyle s jest naturalna, gdy poza \displaystyle (a,b) jest wielomianem liniowym, a więc \displaystyle s''(a) = s''(b) = 0.

Interpolacja i gładkość

Pokażemy najpierw ważny lemat, który okaże się kluczem do dowodu dalszych twierdzeń.

Niech \displaystyle W^r(a,b) będzie klasą funkcji \displaystyle f:[a,b]\toR takich, że \displaystyle f jest \displaystyle (r-1) razy różniczkowalna na \displaystyle [a,b] w sposób ciągły oraz \displaystyle f^{(r)}(x) istnieje prawie wszędzie na \displaystyle [a,b] i jest całkowalna z kwadratem, tzn.

\displaystyle \aligned W^r(a,b) &= \{\,f\in C^{(r-1)}([a,b]):\, f^{(r)}(x)       \mbox{  istnieje p.w. na  }  [a,b] \\     && \qquad\qquad\qquad\qquad  \mbox{  oraz  }         f^{(r)}\in{\cal L}_2(a,b)\,\}. \endaligned

Oczywiście każda funkcja sklejana rzędu \displaystyle r (niekoniecznie naturalna) należy do \displaystyle W^r(a,b).

Lemat

Niech \displaystyle f\in W^r(a,b) będzie funkcją zerującą się w węzłach, tzn.

\displaystyle f(x_j)\,=\,0,\qquad 0\le j\le n.

Wtedy dla dowolnej naturalnej funkcji sklejanej \displaystyle s\in {\cal S}_r mamy

\displaystyle \int_a^b f^{(r)}(x)s^{(r)}(x)\,dx\,=\,0.

Dowód

Dla \displaystyle r=1 funkcja \displaystyle s' jest przedziałami stała. Oznaczając przez \displaystyle a_j jej wartość na \displaystyle [x_{j-1},x_j] dostajemy

\displaystyle \aligned \int_a^b f'(x)s'(x)\,dx &=             \sum_{j=1}^n\int_{t_{j-1}}^{t_j} f'(x)a_j\,dx \\          &= \sum_{j=1}^n a_j(f(x_j)-f(x_{j-1}))\,=\,0,  \endaligned

ponieważ \displaystyle f zeruje się w \displaystyle t_j.

Rozpatrzmy teraz przypadek \displaystyle r\ge 2. Ponieważ

\displaystyle (f^{(r-1)}s^{(r)})'\,=\,f^{(r)}s^{(r)}\,+\,f^{(r-1)}s^{(r+1)},

to

\displaystyle \int_a^b f^{(r)}(x)s^{(r)}(x)\,dx\,=\,f^{(r-1)}(x)s^{(r)}(x)     \Big |_a^b \,-\,\int_a^b f^{(r-1)}(x)s^{(r+1)}(x)\,dx.

Wobec tego, że \displaystyle s jest poza przedziałem \displaystyle (a,b) wielomianem stopnia co najwyżej \displaystyle r-1 oraz \displaystyle s^{(r)} jest ciągła na \displaystyle R, mamy \displaystyle s^{(r)}(a)=0=s^{(r)}(b), a stąd

\displaystyle f^{(r-1)}(x)s^{(r)}(x)\Big |_a^b\,=\,0.

Postępując podobnie, tzn. całkując przez części \displaystyle r-1 razy, otrzymujemy w końcu

\displaystyle \int_a^b f^{(r)}(x)s^{(r)}(x)\,dx\,=\,(-1)^{r-1}       \int_a^b f'(x)s^{(2r-1)}(x)\,dx.

Funkcja \displaystyle s^{(2r-1)} jest przedziałami stała, a więc możemy teraz zastosować ten sam argument jak dla \displaystyle r=1, aby pokazać,

że ostatnia całka jest równa zeru. image:End_of_proof.gif

Funkcje sklejane chcielibyśmy zastosować do interpolacji funkcji. Ważne jest więc, aby odpowiednie zadanie interpolacyjne miało jednoznaczne rozwiązanie.

Twierdzenie O istnieniu i jednoznaczności naturalnego splajnu interpolacyjnego

Jeśli \displaystyle n+1\ge r, to dla dowolnej funkcji \displaystyle f:[a,b]\toR istnieje dokładnie jedna naturalna funkcja sklejana \displaystyle s_f\in {\cal S}_r interpolująca \displaystyle f w węzłach \displaystyle x_j, tzn. taka, że

\displaystyle s_f(x_j)\,=\,f(x_j),\qquad 0\le j\le n.

Dowód

Pokażemy najpierw, że jedyną naturalną funkcją sklejaną interpolującą dane zerowe jest funkcja zerowa. Rzeczywiście, jeśli \displaystyle s(x_j)=0 dla \displaystyle 0\le j\le n, to podstawiając w poprzednim lemacie \displaystyle f = s, otrzymujemy

\displaystyle \int_a^b \Big(s^{(r)}(x)\Big)^2\,dx\,=\,0.

Stąd \displaystyle s^{(r)} jest funkcją zerową, a więc \displaystyle s jest wielomianem stopnia co najwyżej \displaystyle r-1 zerującym się w co najmniej \displaystyle n+1 punktach \displaystyle x_j. Wobec tego, że \displaystyle n+1>r-1, otrzymujemy \displaystyle s\equiv 0.

Zauważmy teraz, że problem znalezienia naturalnej funkcji sklejanej \displaystyle s interpolującej \displaystyle f można sprowadzić do rozwiązania układu równań liniowych z macierzą kwadratową. Na każdym przedziale \displaystyle [x_{i-1},x_i], \displaystyle 1\le i\le n, jest ona postaci

\displaystyle s(x)\,=\,w_i(x)\,=\,\sum_{j=0}^{2r-1} a_{i,j}x^j,

dla pewnych współczynników \displaystyle a_{i,j}\inR, a na \displaystyle (-\infty,a] i \displaystyle [b,\infty) mamy odpowiednio

\displaystyle s(x)\,=\,w_0(x)\,=\,\sum_{j=0}^{r-1} a_{0,j}x^j

i

\displaystyle s(x)\,=\,w_{n+1}(x)\,=\,\sum_{j=0}^{r-1} a_{n+1,j}x^j.

Aby wyznaczyć \displaystyle s, musimy więc znaleźć ogółem \displaystyle 2r(n+1) współczynników \displaystyle a_{i,j}, przy czym są one związane \displaystyle (2r-1)(n+1) warunkami jednorodnymi wynikającymi z gładkości,

\displaystyle w_i^{(k)}(x_i)\,=\,w_{i+1}^{(k)}(x_i)

dla \displaystyle 0\le i\le n i \displaystyle 0\le k\le 2r-2, oraz \displaystyle n+1 niejednorodnymi warunkami interpolacyjnymi,

\displaystyle w_i(x_i)\,=\,f(x_i)

dla \displaystyle 0\le i\le n. Otrzymujemy więc układ \displaystyle 2r(n+1) równań liniowych ze względu na \displaystyle 2r(n+1) niewiadomych \displaystyle a_{i,j}.

Naturalna funkcja sklejana interpolująca \displaystyle f jest wyznaczona jednoznacznie wtedy i tylko wtedy, gdy układ ten ma jednoznaczne rozwiązanie. To zaś zachodzi, gdy zero jest jedynym rozwiązaniem układu jednorodnego. Rzeczywiście, układ jednorodny odpowiada zerowym warunkom interpolacyjnym, przy których, jak pokazaliśmy wcześniej, zerowa funkcja sklejana (której odpowiada \displaystyle a_{i,j}=0, \displaystyle \forall i,j) jest jedynym rozwiązaniem zadania interpolacyjnego. image:End_of_proof.gif

Naturalnych funkcji sklejanych możemy więc używać do interpolacji funkcji. Pokażemy teraz inną ich własność, która jest powodem dużego praktycznego zainteresowania funkcjami sklejanymi.

Twierdzenie O ekstremalnej własności splajnów naturalnych

Niech \displaystyle f\in W^r(a,b) i niech \displaystyle s_f\in {\cal S}_r będzie naturalną funkcją sklejaną rzędu \displaystyle r interpolującą \displaystyle f w węzłach \displaystyle x_j, \displaystyle 0\le j\le n. Wtedy

\displaystyle    \int_a^b \Big(  f^{(r)}(x)\Big)^2\,dx\,\ge\,   \int_a^b \Big(s_f^{(r)}(x)\Big)^2\,dx.

Dowód

Jeśli przedstawimy \displaystyle f w postaci \displaystyle f=s_f+(f-s_f), to

\displaystyle \aligned \int_a^b\Big(f^{(r)}(x)\Big)^2\,dx       &= \int_a^b\Big(s_f^{(r)}(x)\Big)^2\,dx\,+\,         \int_a^b\Big((f-s_f)^{(r)}(x)\Big)^2\,dx \\     & & \qquad\qquad + 2\,\int_a^b s_f^{(r)}(x)(f-s_f)^{(r)}(x)\,dx.  \endaligned

Funkcja \displaystyle f-s_f jest w klasie \displaystyle W^r(a,b) i zeruje się w węzłach \displaystyle x_j, \displaystyle 0\le j\le n. Z lematu wynika więc, że

\displaystyle \int_a^b s_f^{(r)}(x)(f-s_f)^{(r)}(x)dx=0, a stąd wynika teza. image:End_of_proof.gif

Wartość całki \displaystyle \int_a^b(f^{(r)}(x))^2 dx może być w ogólności uważana za miarę gładkości funkcji. Dowiedzioną nierówność możemy więc zinterpretować w następujący sposób. Naturalna funkcja sklejana jest w klasie \displaystyle W^r(a,b) najgładszą funkcją spełniającą dane warunki interpolacyjne w wybranych węzłach \displaystyle x_j.

Jak już wspomnieliśmy, najczęściej używanymi są kubiczne funkcje sklejane. Dlatego rozpatrzymy je oddzielnie.

Kubiczne funkcje sklejane

Jeśli zdecydowaliśmy się na użycie kubicznych funkcji sklejanych, powstaje problem wyznaczenia \displaystyle s_f\in{\cal S}_2 interpolującej daną funkcję \displaystyle f, tzn. takiej, że \displaystyle s_f(x_i)=f(x_i) dla \displaystyle 0\le i\le n. W tym celu, na każdym przedziale \displaystyle [x_i,x_{i+1}] przedstawimy \displaystyle s_f w postaci jej rozwinięcia w szereg Taylora w punkcie \displaystyle x_i,

\displaystyle s_f(x)\,=\,w_i(x)\,=\,a_i+b_i(x-x_i)+      c_i\frac{(x-x_i)^2}2+d_i\frac{(x-x_i)^3}6,

i podamy algorytm obliczania \displaystyle a_i,b_i,c_i,d_i dla \displaystyle 0\le i\le n-1.

Warunki brzegowe i warunki ciągłości dla \displaystyle s_f'' dają nam \displaystyle w_0''(x_0)=0=w_{n-1}''(x_n) oraz \displaystyle w_i''(x_{i+1})=w_{i+1}''(x_{i+1}), czyli

\displaystyle \aligned c_0 &= 0, \\      c_i+d_ih_i &= c_{i+1}, \qquad 0\le i\le n-2, \\    c_{n-1}+d_{n-1}h_{n-1} &= 0,  \endaligned

gdzie \displaystyle h_i=x_{i+1}-x_i. Stąd, przyjmując dodatkowo \displaystyle c_n=0, otrzymujemy

\displaystyle    d_i\,=\,\frac{c_{i+1}-c_i}{h_i},\qquad 1\le i\le n-1.

Z warunków ciągłości dla \displaystyle s_f' dostajemy z kolei

\displaystyle b_i+c_ih_i+d_i\frac{h_i^2}{2}\,=\,b_{i+1},      \qquad 0\le i\le n-2,

oraz

\displaystyle    b_{i+1}\,=\,b_i+h_i\frac{c_{i+1}+c_i}{2},      \qquad 0\le i\le n-2.

Warunki ciągłości \displaystyle s_f dają w końcu

\displaystyle    a_i+b_ih_i+c_i\frac{h_i^2}{2}+d_i\frac{h_i^3}{6}\,=\,a_{i+1},      \qquad 0\le i\le n-2.

Powyższe równania definiują nam na odcinku \displaystyle [a,b] naturalną kubiczną funkcję sklejaną. Ponieważ poszukiwana funkcja sklejana \displaystyle s_f ma interpolować \displaystyle f, mamy dodatkowych \displaystyle n+1 warunków interpolacyjnych \displaystyle w_i(x_i)=f(x_i), \displaystyle 0\le i\le n-1, oraz \displaystyle w_{n-1}(x_n)=f(x_n), z których

\displaystyle    a_i\,=\,f(x_i), \qquad 0\le i\le n-1.

Teraz możemy warunki ciągłości przepisać jako

\displaystyle f(x_{i+1})\,=\,f(x_i)+b_ih_i+c_ih_i^2+d_i\frac{h_i^3}{6},

przy czym wzór ten zachodzi również dla \displaystyle i=n-1. Po wyrugowaniu \displaystyle b_i i podstawieniu \displaystyle d_i, mamy

\displaystyle  b_i\,=\,f(x_i,x_{i+1})+h_i\frac{c_{i+1}+2c_i}{6}, \qquad 0\le i\le n-1,

gdzie \displaystyle f(x_i,x_{i+1}) jest odpowiednią różnicą dzieloną. Możemy teraz powyższe wyrażenie na \displaystyle b_i podstawić, aby otrzymać

\displaystyle c_i\frac{h_i}{6}+c_{i+1}\frac{h_i+h_{i+1}}{3}+c_{i+1}\frac{h_{i+1}}{6}    \,=\,f(x_{i+1},x_{i+2})-f(x_i,x_{i+1}).

Wprowadzając oznaczenie

\displaystyle  c_i^*\,=\,\frac{c_i}{6},

możemy to równanie przepisać jako

\displaystyle \frac{h_i}{h_i+h_{i+1}}c_i^*\,+\,2\,c_{i+1}^*\,+\,   \frac{h_{i+1}}{h_i+h_{i+1}}c_{i+2}^*\,=\,    f(x_i,x_{i+1},x_{i+2}),

\displaystyle 0\le i\le n-2, albo w postaci macierzowej

\displaystyle  \left(\begin{array} {cccccc}     2  & w_1 \\    u_2 &  2  & w_2 \\        & u_3 &  2    & w_3 \\        &     &\ddots &\ddots   &\ddots \\        &     &       & u_{n-2} &  2  & w_{n-2} \\        &     &       &         & u_{n-1} &  2      \end{array} \right)    \left(\begin{array} {c}     c_1^*\\ c_2^*\\ c_3^*\\ \vdots\\ c_{n-2}^*\\ c_{n-1}^*        \end{array} \right) \,=\,   \left(\begin{array} {c}     v_1\\ v_2\\ v_3\\ \vdots\\ v_{n-2}\\ v_{n-1}        \end{array} \right),

gdzie

\displaystyle \aligned && u_i\,=\,\frac{h_{i-1}}{h_{i-1}+h_i},\qquad       w_i\,=\,\frac{h_i}{h_{i-1}+h_i}, \\   && v_i\,=\,f(x_{i-1},x_i,x_{i+1}).  \endaligned

Ostatecznie, aby znaleźć współczynniki \displaystyle a_i,b_i,c_i,d_i należy najpierw rozwiązać układ równań liniowych, a potem zastosować wzory definiujące pozostałe współczynniki.

Zauważmy, że macierz układu równań liniowych jest trójdiagonalna i ma dominującą przekątną. Układ można więc rozwiązać kosztem proporcjonalnym do wymiaru \displaystyle n używając algorytmu przeganiania. Koszt znalezienia wszystkich współczynników kubicznej funkcji sklejanej interpolującej \displaystyle f jest więc też proporcjonalny do \displaystyle n.

MATLAB i Octave mają wbudowaną funkcję wyznaczającą naturalny kubiczny splajn interpolujący zadane wartości:

s = spline(x,y);

Aby wyznaczyć wartości takiego splajnu w zadanych punktach \displaystyle X, także musimy użyć specjalnej funkcji,

Y = ppval(s,X);

Na końcu oszacujemy jeszcze błąd interpolacji naturalnymi kubicznymi funkcjami sklejanymi na przedziale \displaystyle [a,b]. Będziemy zakładać, że \displaystyle f jest dwa razy różniczkowalna w sposób ciągły.

Twierdzenie O błędzie interpolacji splajnem kubicznym

Jeśli \displaystyle f\in F^1_M([a,b]) to

\displaystyle \|f-s_f\|_{C([a,b])}\,\le\,5\,M\,        \max_{1\le i\le n}(x_i-x_{i-1})^2.

W szczególności, dla podziału równomiernego \displaystyle x_i=a+i\frac{b-a}{n}, \displaystyle 0\le i\le n, mamy

\displaystyle \|f-s_f\|_{ C([a,b])}\,\le\,       5\,M\,\Big(\frac{b-a}n\Big)^2.

Dowód

Wykorzystamy obliczoną wcześniej postać interpolującej funkcji sklejanej \displaystyle s_f. Dla \displaystyle x\in [x_i,x_{i+1}] mamy

\displaystyle \aligned w_i(x) &= f(x_i)\,+\,\left(\frac{f(x_{i+1})-f(x_i)}{h_i} -h_i(c_{i+1}^*+2c_i^*)\right)(x-x_i) \\ &&\qquad\qquad \,+\, 3c_i^*(x-x_i)^2\,+\,\frac{c_{i+1}^*-c_i^*}{h_i}(x-x_i)^3. \endaligned

Z rozwinięcia \displaystyle f w szereg Taylora w punkcie \displaystyle x_i dostajemy \displaystyle f(x)=f(x_i)+f'(x_i)(x-x_i)+f''(\xi_1)(x-x_i)^2/2 oraz \displaystyle (f(x_{i+1})-f(x_i))/h_i=f'(x_i)+h_if''(\xi_2)/2. Stąd

\displaystyle \aligned \lefteqn{f(x)-s_f(x) \,=\, f(x)-w_i(x)} \\   &= \frac{f''(\xi_1)}2(x-x_i)^2-\left(\frac{f''(\xi_2)}2       -(c_{i+1}^*+2c_i^*)\right)h_i(x-x_i) \\   & & \qquad\qquad\qquad -3c_i^*(x-x_i)^2       -\frac{c_{i+1}^*-c_i^*}{h_i}(x-x_i)^3, \endaligned

oraz

\displaystyle \aligned  |f(x)-s_f(x)| &\le &(M+2|c_{i+1}^*|+6|c_i^*|)h_i^2 \\     &= (M+8\max_{1\le i\le n-1}|c_i^*|)h_i^2.  \endaligned

Niech teraz \displaystyle \max_{1\le i\le n-1}|c_i^*|=|c_s^*|. Z postaci układu otrzymujemy

\displaystyle \aligned |c_s^*| &= 2|c_s^*|-|c_s^*|(u_s+w_s) \,\le\,     |u_sc_{s-1}^*+2c_s^*+w_sc_{s+1}| \\    &= |f(x_{s-1},x_s,x_{s+1})|\,\le\,        \Big|\frac{f''(\xi_3)}2\Big|\,\le\,\frac 12 M,  \endaligned

a stąd

\displaystyle |f(x)-s_f(x)|\,\le\, 5\, M\, h_i^2,

co kończy dowód.

image:End_of_proof.gif

Przykład

Porównanie interpolacji splajnowej i Lagrange'a.

Interpolacja splajnowa wydaje się lepiej spełniać zadanie odtworzenia kształtu funkcji
Enlarge
Interpolacja splajnowa wydaje się lepiej spełniać zadanie odtworzenia kształtu funkcji

Jak widać, w przeciwieństwie do wielomianu interpolacyjnego, splajn interpolacyjny praktycznie pokrywa się z wykresem funkcji, tutaj: \displaystyle f(x) = \frac{1}{1+x^2}.

Uwaga

Niech

\displaystyle W^r_M(a,b)\,=\,\Big\{\,f\in W^r(a,b):\,     \int_a^b\left(f^{(r)}(x)\right)^2\,dx\le M\,\Big\}.

Ustalmy węzły \displaystyle a=x_0<\cdots<x_n=b. Dla \displaystyle f\in W^r_M(a,b), niech \displaystyle s_f będzie naturalną funkcją sklejaną interpolującą \displaystyle f w \displaystyle x_j, \displaystyle 0\le j\le n, a \displaystyle a_f dowolną inną aproksymacją korzystającą jedynie z informacji o wartościach \displaystyle f w tych węzłach, tzn.

\displaystyle a_f\,=\,\phi(f(x_0),\ldots,f(x_n)).

Załóżmy, że błąd aproksymacji mierzymy nie w normie Czebyszewa, ale w normie średniokwadratowej zdefiniowanej jako

\displaystyle \|g\|_{{\cal L}_2(a,b)}\,=\,\sqrt{\int_a^b (g(x))^2\,dx}.

Wtedy

\displaystyle \sup_{f\in W^r_M(a,b)}\|f-s_f\|_{{\cal L}_2(a,b)}\,\le\,   \sup_{f\in W^r_M(a,b)}\|f-a_f\|_{{\cal L}_2(a,b)}.

Aproksymacja naturalnymi funkcjami sklejanymi jest więc optymalna w klasie \displaystyle W^r_M(a,b).

Można również pokazać, że interpolacja \displaystyle s_f^* naturalnymi funkcjami sklejanymi na węzłach równoodległych \displaystyle x_j=a+(b-a)j/ń, \displaystyle 0\le j\le n, jest optymalna co do rzędu w klasie \displaystyle W^r_M(a,b), wśród wszystkich aproksymacji korzystających jedynie z informacji o wartościach funkcji w \displaystyle n+1 dowolnych punktach, oraz

\displaystyle \max_{f\in W^r_M(a,b)}\|f-s^*_f\|_{{\cal L}_2(a,b)}     \,\asymp\,n^{-r}.

Uwaga

Tak jak wielomiany, naturalne funkcje sklejane interpolujące dane funkcje można reprezentować przez ich współczynniki w różnych bazach. Do tego celu można na przykład użyć bazy kanonicznej \displaystyle K_j, \displaystyle 0\le j\le n zdefiniowanej równościami

\displaystyle K_j(x_i)\,=\,\left\{\begin{array} {ll}          0 &\quad i\ne j, \\          1 &\quad i=j, \end{array} \right.

przy której \displaystyle s_f(x)=\sum_{j=0}^n f(x_j)K_j(x). Baza kanoniczna jest jednak niewygodna w użyciu, bo funkcje \displaystyle K_j w ogólności nie zerują się na żadnym podprzedziale, a tym samym manipulowanie nimi jest utrudnione.

Częściej używa się bazy B-sklejanej. Można ją zdefiniować dla splajnów dowolnego rzędu za pomocą wzoru rekurencyjnego (przyjmując, że dla dowolnego \displaystyle i, \displaystyle x_i < x_{i+1}):

\displaystyle B_i^0(x) = \left\{ \beginmatrix  1, &  \mbox{ jeśli }  x_i \leq x < x_{i+1},\\ 0, &  \mbox{ w przeciwnym przypadku} ; \endmatrix  \right.
\displaystyle B_i^r(x) &= \frac{x-x_i}{x_{i+r}-x_i} B_i^{r-1}(x) + \frac{x_{i+r+1}-x}{x_{i+r+1}-x_{i+1}} B_{i+1}^{r-1}(x).

W przypadku naturalnych splajnów kubicznych, \displaystyle r=2, baza B-sklejana jest jawnie zdefiniowana przez następujące warunki:

\displaystyle \aligned B_j(x_j) &= 1, \qquad \mbox{ dla   }  0\le j\le n, \\     B_j(x) &= 0,\qquad \mbox{ dla   }  x\le x_{j-2}, j\ge 2,        \mbox{   oraz   dla   }  x\ge x_{j+2}, j\le n-2.   \endaligned

Dla \displaystyle B_0 i \displaystyle B_1 dodatkowo żądamy, aby

\displaystyle B_0''(x_0)\,=\,0\,=\,B_1''(x_0),\qquad B_1(x_0)\,=\,0,

a dla \displaystyle B_{n-1} i \displaystyle B_n podobnie

\displaystyle B_{n-1}''(x_n)\,=\,0\,=\,B_n''(x_n),       \qquad B_{n-1}(x_{n-1})\,=\,0.

Wtedy \displaystyle B_j nie zeruje się tylko na przedziale \displaystyle (x_{j-2},x_{j+2}). Wyznaczenie współczynników rozwinięcia w bazie \displaystyle \{B_i\}_{i=0}^n funkcji sklejanej interpolującej \displaystyle f wymaga rozwiązania układu liniowego z macierzą trójdiagonalną \displaystyle \{B_j(x_i)\}_{i,j=0}^n, a więc koszt obliczenia tych współczynników jest proporcjonalny do \displaystyle n.

Uwaga

Oprócz naturalnych funkcji sklejanych często rozpatruje się też okresowe funkcje sklejane. Są to funkcje \displaystyle \tilde s:R\toR spełniające warunki (i), (ii) \link{splinedef}{definicji funkcji sklejanej}, oraz warunek:

(iii)'
\displaystyle \tilde s^{(i)} jest dla \displaystyle 0\le i\le r-1

funkcją okresową o okresie \displaystyle (b-a), tzn. \displaystyle \tilde s^{(i)}(x)=\tilde s^{(i)}(x+(b-a)), \displaystyle \forall x.

Klasę okresowych funkcji sklejanych rzędu \displaystyle r oznaczymy przez \displaystyle \widetilde{\cal S}_r. Funkcje te mają podobne własności jak naturalne funkcje sklejane. Dokładniej, niech

\displaystyle  \tilde W^r(a,b)\,=\,\{\,f\in W^r(a,b):\,  f^{(i)}(a)=f^{(i)}(b),\; 0\le i\le r-1\,\},

tzn. \displaystyle \tilde W^r(a,b) jest klasą funkcji z \displaystyle W^r(a,b), które można przedłużyć do funkcji, krórych wszystkie pochodne do rzędu \displaystyle r-1 włącznie są \displaystyle (b-a)-okresowe na \displaystyle R. Wtedy dla dowolnej funkcji \displaystyle f\in\tilde W^r(a,b) zerującej się w węzłach \displaystyle x_j, oraz dla dowolnej \displaystyle \tilde s\in\widetilde{\cal S}_r mamy

\displaystyle  \int_a^b f^{(r)}(x)\tilde s^{(r)}(x)\,dx\,=\,0.

Wynika z niego jednoznaczność rozwiązania zadania interpolacyjnego dla okresowych funkcji \displaystyle f (tzn. takich, że \displaystyle f(a)=f(b)), jak również odpowiednia własność minimalizacyjna okresowych funkcji sklejanych. Dokładniej, jeśli \displaystyle f\in\tilde W^r(a,b) oraz \displaystyle \tilde s_f\in\widetilde{\cal S}_r interpoluje \displaystyle f w węzłach \displaystyle x_j, \displaystyle 0\le j\le n, to

\displaystyle \int_a^b \Big(  f^{(r)}(x)\Big)^2\,dx\,\ge\,   \int_a^b \Big(\tilde s_f^{(r)}(x)\Big)^2\,dx.

Dygresja o najlepszej aproksymacji

Klasyczne zadanie aproksymacyjne w przestrzeniach funkcji definiuje się w następujący sposób.

Niech \displaystyle F będzie pewną przestrzenią liniową funkcji \displaystyle f:[a,b]\toR, w której określona została norma \displaystyle \|\cdot\|. Niech \displaystyle V_n\subset F będzie podprzestrzenią w \displaystyle F wymiaru \displaystyle n. Dla danej \displaystyle f\in F, należy znaleźć funkcję \displaystyle v_f\in F taką, że

\displaystyle \|f-v_f\|\,=\,\min_{v\in V_n}\|f-v\|.

Okazuje się, że tak postawione zadanie ma rozwiązanie \displaystyle v_f, choć nie zawsze jest ono wyznaczone jednoznacznie.

Jako przykład, rozpatrzmy \displaystyle F=W^r(a,b). Utożsamiając funkcje \displaystyle f_1,f_2\in W^r(a,b) takie, że \displaystyle f_1(x)-f_2(x) \in\Pi_{r-1}, zdefiniujemy w \displaystyle W^r(a,b) normę

\displaystyle \|f\|\,=\,\sqrt{\int_a^b\left(f^{(r)}(x)\right)^2\,dx}.

Dla ustalonych węzłów \displaystyle a=x_0<\cdots<x_n=b, niech

\displaystyle V_{n+1}\,=\,{\cal S}_r

będzie podprzestrzenią w \displaystyle W^r(a,b) naturalnych funkcji sklejanych rzędu \displaystyle r opartych węzłach \displaystyle x_j, \displaystyle 0\le j\le n. Oczywiście \displaystyle  \mbox{dim} {\cal S}_r=n+1, co wynika z jednoznaczności rozwiązania w \displaystyle {\cal S}_r zadania interpolacji. Okazuje się, że wtedy optymalną dla \displaystyle f\in W^r(a,b) jest naturalna funkcja sklejana \displaystyle s_f interpolująca \displaystyle f w węzłach \displaystyle x_j, tzn.

\displaystyle \|f-s_f\|\,=\,\min_{s\in {\cal S}_r}\|f-s\|.

Rzeczywiście, ponieważ norma w przestrzeni \displaystyle W^r(a,b) generowana jest przez iloczyn skalarny

\displaystyle (f_1,f_2)\,=\,     \int_a^b f_1^{(r)}(x)f_2^{(r)}(x)\,dx,

jest to przestrzeń unitarna. Znane twierdzenie mówi, że w przestrzeni unitarnej najbliższą danej \displaystyle f funkcją w dowolnej domkniętej podprzestrzeni \displaystyle V jest rzut prostopadły \displaystyle f na \displaystyle V, albo równoważnie, taka funkcja \displaystyle v_f\in V_{n+1}, że iloczyn skalarny

\displaystyle (f-v_f, v)\,=\,0, \qquad\forall v\in V.

W naszym przypadku, ostatnia równość jest równoważna

\displaystyle \int_a^b(f-v_f)^{(r)}(x)s^{(r)}(x)\,dx\,=\,0,     \quad\forall s\in{\cal S}_r.

To zaś jest prawdą, gdy \displaystyle v_f interpoluje \displaystyle f w punktach \displaystyle x_j, czyli \displaystyle v_f=s_f.

Dodajmy jeszcze, że nie zawsze interpolacja daje najlepszą aproksymację w sensie klasycznym.

Literatura

W celu dogłębnego zapoznania się z omawianym na wykładzie materiałem, przeczytaj rozdział 6.4 w

  • D. Kincaid, W. Cheney Analiza numeryczna, Wydawnictwa Naukowo-Techniczne, Warszawa 2006, ISBN 83-204-3078-X.

Warto także zapoznać się (nieobowiązkowo) z rozdziałami 6.5 i 6.6 tamże.