Tekst źródłowy strony MN11


<!-- 
Konwertowane  z pliku LaTeX przez latex2mediawiki, zob. http://www.ii.uj.edu.pl/&nbsp;pawlik1/latex2mediawiki.php.
Niezb�dne rozszerzenia i modyfikacje oryginalnego latex2mediawiki 
wprowadzi� przykry@mimuw.edu.pl
-->
 
=Funkcje sklejane (splajny)=

{{powrot |Metody numeryczne | do strony głównej 
przedmiotu <strong>Metody numeryczne</strong>}}

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 ([[MN09#Zjawisko Rungego i dobór węzłów interpolacji|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. <strong>krzywych Beziera</strong> --- 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 <strong>splajny</strong> (''spline''), albo <strong>funkcje gięte</strong>. 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 
<strong>funkcje sklejane</strong> 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 <math>[a,b]</math> i węzły 

<center><math>a \,=\, x_0 \,<\, x_1 \,<\, \cdots \,<\, x_n \,=\, b, 
</math></center>

przy czym <math>n\ge 1</math>. 

{{definicja|||

Funkcję <math>s:R\to R</math> nazywamy <strong>funkcją sklejaną rzędu <math>r</math></strong> (<math>r\ge 1</math>) odpowiadającą węzłom <math>x_j</math>, <math>0\le j\le n</math>, jeśli spełnione są następujące 
dwa warunki:
 
; (i)
:  <math>s</math> jest wielomianem stopnia co najwyżej <math>2r-1</math> na każdym 
z przedziałów <math>[x_{j-1},x_j]</math>, tzn. 
<math>s_{|[x_{j-1},x_j]}\in\Pi_{2r-1}</math>, <math>1\le j\le n</math>, 

; (ii)
:  <math>s</math> jest <math>(2r-2)</math>-krotnie różniczkowalna w sposób 
ciągły na całej prostej, tzn. <math>s\in C^{(2r-2)}(R)</math>.
 
Jeśli ponadto 
 
; (iii)
:  <math>s</math> jest wielomianem stopnia co najwyżej <math>r-1</math> poza 
<math>(a,b)</math>, tzn. <math>s_{|(-\infty,a]},s_{|[b,+\infty)}\in\Pi_{r-1}</math>,
 
to <math>s</math> jest naturalną funkcją sklejaną. 
}}

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

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

Najważniejszymi z praktycznego punktu widzenia są jednak 
funkcje sklejane rzędu drugiego odpowiadające <math>r=2</math>. Są 
to funkcje, które są na <math>R</math> 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 <strong>kubicznych funkcjach sklejanych</strong>. Funkcja 
sklejana kubiczna <math>s</math> jest naturalna, gdy poza <math>(a,b)</math> jest 
wielomianem liniowym, a więc <math>s''(a) = s''(b) = 0</math>.

==Interpolacja i gładkość==

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

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

<center><math>\begin{align} 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)\,\}.
\end{align}</math></center>

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

{{lemat|||
 
Niech <math>f\in W^r(a,b)</math> będzie funkcją 
zerującą się w węzłach, tzn. 

<center><math>f(x_j)\,=\,0,\qquad 0\le j\le n</math></center>

Wtedy dla dowolnej naturalnej funkcji sklejanej <math>s\in {\cal S}_r</math> 
mamy 

<center><math>\int_a^b f^{(r)}(x)s^{(r)}(x)\,dx\,=\,0. 
</math></center>

}}

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

<center><math>\begin{align} \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, 
\end{align}</math></center>

ponieważ <math>f</math> zeruje się w <math>t_j</math>. 

Rozpatrzmy teraz przypadek <math>r\ge 2</math>. Ponieważ 

<center><math>(f^{(r-1)}s^{(r)})'\,=\,f^{(r)}s^{(r)}\,+\,f^{(r-1)}s^{(r+1)}, 
</math></center>

to 

<center><math>\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</math></center>

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

<center><math>f^{(r-1)}(x)s^{(r)}(x)\Big |_a^b\,=\,0. 
</math></center>

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

<center><math>\int_a^b f^{(r)}(x)s^{(r)}(x)\,dx\,=\,(-1)^{r-1}
      \int_a^b f'(x)s^{(2r-1)}(x)\,dx</math></center>

Funkcja <math>s^{(2r-1)}</math> jest przedziałami stała, a więc możemy 
teraz zastosować ten sam argument jak dla <math>r=1</math>, aby pokazać, 
że ostatnia całka jest równa zeru.}}

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|O istnieniu i jednoznaczności naturalnego splajnu interpolacyjnego|

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

<center><math>s_f(x_j)\,=\,f(x_j),\qquad 0\le j\le n</math></center>

}}

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

<center><math>\int_a^b \Big(s^{(r)}(x)\Big)^2\,dx\,=\,0</math></center>

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

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

<center><math>s(x)\,=\,w_i(x)\,=\,\sum_{j=0}^{2r-1} a_{i,j}x^j, 
</math></center>

dla pewnych współczynników <math>a_{i,j}\in R</math>, a na 
<math>(-\infty,a]</math> i <math>[b,\infty)</math> mamy odpowiednio 

<center><math>s(x)\,=\,w_0(x)\,=\,\sum_{j=0}^{r-1} a_{0,j}x^j 
</math></center>

i

<center><math>s(x)\,=\,w_{n+1}(x)\,=\,\sum_{j=0}^{r-1} a_{n+1,j}x^j. 
</math></center>

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

<center><math>w_i^{(k)}(x_i)\,=\,w_{i+1}^{(k)}(x_i) 
</math></center>

dla <math>0\le i\le n</math> i <math>0\le k\le 2r-2</math>, oraz <math>n+1</math> 
niejednorodnymi warunkami interpolacyjnymi,

<center><math>w_i(x_i)\,=\,f(x_i)
</math></center>

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

Naturalna funkcja sklejana interpolująca <math>f</math> 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 <math>a_{i,j}=0</math>, <math>\forall i,j</math>) jest jedynym rozwiązaniem zadania interpolacyjnego.}}

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|O ekstremalnej własności splajnów naturalnych|

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

<center><math>
  \int_a^b \Big(  f^{(r)}(x)\Big)^2\,dx\,\ge\,
  \int_a^b \Big(s_f^{(r)}(x)\Big)^2\,dx. 
</math></center>

}}

{{dowod|||
Jeśli przedstawimy <math>f</math> w postaci 
<math>f=s_f+(f-s_f)</math>, to 

<center><math>\begin{align} \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. 
\end{align}</math></center>

Funkcja <math>f-s_f</math> jest w klasie <math>W^r(a,b)</math> i zeruje się w węzłach 
<math>x_j</math>, <math>0\le j\le n</math>. Z lematu wynika więc, że 
<math>\int_a^b s_f^{(r)}(x)(f-s_f)^{(r)}(x)dx=0</math>, a stąd wynika teza.}}

Wartość całki <math>\int_a^b(f^{(r)}(x))^2 dx</math> 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 <math>W^r(a,b)</math> najgładszą funkcją spełniającą dane 
warunki interpolacyjne w wybranych węzłach <math>x_j</math>. 

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 <math>s_f\in{\cal S}_2</math> 
interpolującej daną funkcję <math>f</math>, tzn. takiej, że 
<math>s_f(x_i)=f(x_i)</math> dla <math>0\le i\le n</math>. W tym celu, na każdym 
przedziale <math>[x_i,x_{i+1}]</math> przedstawimy <math>s_f</math> w postaci jej 
rozwinięcia w szereg Taylora w punkcie <math>x_i</math>,

<center><math>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</math>,</center>

i podamy algorytm obliczania <math>a_i,b_i,c_i,d_i</math> 
dla <math>0\le i\le n-1</math>. 

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

<center><math>\begin{align} 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, 
\end{align}</math></center>

gdzie <math>h_i=x_{i+1}-x_i</math>. Stąd, przyjmując dodatkowo 
<math>c_n=0</math>, otrzymujemy 

<center><math>
  d_i\,=\,\frac{c_{i+1}-c_i}{h_i},\qquad 1\le i\le n-1</math></center>

Z warunków ciągłości dla <math>s_f'</math> dostajemy z kolei 

<center><math>b_i+c_ih_i+d_i\frac{h_i^2}{2}\,=\,b_{i+1}, 
    \qquad 0\le i\le n-2</math>,</center>

oraz 

<center><math>
  b_{i+1}\,=\,b_i+h_i\frac{c_{i+1}+c_i}{2}, 
    \qquad 0\le i\le n-2. 
</math></center>

Warunki ciągłości <math>s_f</math> dają w końcu 

<center><math>
  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. 
</math></center>

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

<center><math>
  a_i\,=\,f(x_i), \qquad 0\le i\le n-1</math></center>

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

<center><math>f(x_{i+1})\,=\,f(x_i)+b_ih_i+c_ih_i^2+d_i\frac{h_i^3}{6}</math>,</center>

przy czym wzór ten zachodzi również dla <math>i=n-1</math>. 
Po wyrugowaniu <math>b_i</math> i podstawieniu <math>d_i</math>, 
mamy 

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

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

<center><math>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}). 
</math></center>

Wprowadzając oznaczenie 

<center><math>
c_i^*\,=\,\frac{c_i}{6}, 
</math></center>

możemy to równanie przepisać jako

<center><math>\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}), 
</math></center>

<math>0\le i\le n-2</math>, albo w postaci macierzowej 

<center><math>
\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)</math>,</center>

gdzie 

<center><math>\begin{align} && 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}). 
\end{align}</math></center>

Ostatecznie, aby znaleźć współczynniki <math>a_i,b_i,c_i,d_i</math> 
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 <math>n</math> używając [[MN08#Macierze trójdiagonalne|algorytmu przeganiania]]. Koszt znalezienia wszystkich współczynników kubicznej funkcji sklejanej interpolującej <math>f</math> jest więc też proporcjonalny do <math>n</math>. 

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

 <div style="margin: 1em; padding:1em; color: #006; background-color:#fcfcfc;"><pre>s = spline(x,y);
</pre></div> 
 
Aby wyznaczyć wartości takiego splajnu w zadanych punktach <math>X</math>, także musimy użyć specjalnej funkcji,

 <div style="margin: 1em; padding:1em; color: #006; background-color:#fcfcfc;"><pre>Y = ppval(s,X);
</pre></div> 
 
Na końcu oszacujemy jeszcze błąd interpolacji naturalnymi 
kubicznymi funkcjami sklejanymi na przedziale <math>[a,b]</math>. 
Będziemy zakładać, że <math>f</math> jest dwa razy 
różniczkowalna w sposób ciągły.

{{twierdzenie|O błędzie interpolacji splajnem kubicznym|O błędzie interpolacji splajnem kubicznym|

Jeśli <math>f\in F^1_M([a,b])</math> to 

<center><math>\|f-s_f\|_{C([a,b])}\,\le\,5\,M\,
       \max_{1\le i\le n}(x_i-x_{i-1})^2</math></center>

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

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

}}

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

<center><math>\begin{align} 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.
\end{align}</math></center>

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

<center><math>\begin{align} 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,
\end{align}</math></center>

oraz 

<center><math>\begin{align} 
|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. 
\end{align}</math></center>

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

<center><math>\begin{align} |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, 
\end{align}</math></center>

a stąd

<center><math>|f(x)-s_f(x)|\,\le\, 5\, M\, h_i^2, 
</math></center>

co kończy dowód. 
}}

<div style="margin-top:1em; padding-top,padding-bottom:1em;">
<span  style="font-variant:small-caps;">Przykład</span> 
<div class="solution" style="margin-left,margin-right:3em;">

Porównanie interpolacji splajnowej i Lagrange'a.

[[Image:MNrunge17czebyspline.png|thumb|550px|center|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: <math>f(x) = \frac{1}{1+x^2}</math>.

</div></div>

<div style="margin-top:1em; padding-top,padding-bottom:1em;">
<span  style="font-variant:small-caps;">Uwaga</span> 
<div class="solution" style="margin-left,margin-right:3em;">

Niech 

<center><math>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\}</math></center>

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

<center><math>a_f\,=\,\phi(f(x_0),\ldots,f(x_n))</math></center>

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

<center><math>\|g\|_{{\cal L}_2(a,b)}\,=\,\sqrt{\int_a^b (g(x))^2\,dx}. 
</math></center>

Wtedy 

<center><math>\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)}. 
</math></center>

Aproksymacja naturalnymi funkcjami sklejanymi jest więc optymalna w klasie <math>W^r_M(a,b)</math>. 

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

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

</div></div>

<div style="margin-top:1em; padding-top,padding-bottom:1em;">
<span  style="font-variant:small-caps;">Uwaga</span> 
<div class="solution" style="margin-left,margin-right:3em;">

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 <math>K_j</math>, <math>0\le j\le n</math> zdefiniowanej równościami 

<center><math>K_j(x_i)\,=\,\left\{\begin{array} {ll}
         0 &\quad i\ne j, \\
         1 &\quad i=j, \end{array} \right.</math></center>

przy której <math>s_f(x)=\sum_{j=0}^n f(x_j)K_j(x)</math>. Baza kanoniczna jest jednak niewygodna w użyciu, bo funkcje <math>K_j</math> 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 <math>i</math>, <math>x_i < x_{i+1}</math>):

<center><math>B_i^0(x) = \left\{ \begin{matrix}  1, &  \mbox{ jeśli }  x_i \leq x < x_{i+1},\\
0, &  \mbox{ w przeciwnym przypadku} ;
\end{matrix} 
\right.</math></center>

<center><math>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)</math></center>

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

<center><math>\begin{align} 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.  
\end{align}</math></center>

Dla <math>B_0</math> i <math>B_1</math> dodatkowo żądamy, aby 

<center><math>B_0''(x_0)\,=\,0\,=\,B_1''(x_0),\qquad B_1(x_0)\,=\,0, 
</math></center>

a dla <math>B_{n-1}</math> i <math>B_n</math> podobnie 

<center><math>B_{n-1}''(x_n)\,=\,0\,=\,B_n''(x_n),
      \qquad B_{n-1}(x_{n-1})\,=\,0</math></center>

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

<div style="margin-top:1em; padding-top,padding-bottom:1em;">
<span  style="font-variant:small-caps;">Uwaga</span> 
<div class="solution" style="margin-left,margin-right:3em;">

Oprócz naturalnych funkcji sklejanych często rozpatruje się też <strong>okresowe funkcje sklejane</strong>. Są to funkcje <math>\tilde s:R\to R</math> spełniające  warunki '''(i)''', '''(ii)''' \link{splinedef}{definicji funkcji sklejanej}, oraz warunek: 
  
; (iii)'
:  <math>\tilde s^{(i)}</math> jest dla <math>0\le i\le r-1</math> 
funkcją okresową o okresie <math>(b-a)</math>, tzn. 
<math>\tilde s^{(i)}(x)=\tilde s^{(i)}(x+(b-a))</math>, <math>\forall x</math>. 
 
Klasę okresowych funkcji sklejanych rzędu <math>r</math> oznaczymy przez <math>\widetilde{\cal S}_r</math>. Funkcje te mają podobne własności jak naturalne funkcje sklejane. Dokładniej, niech 

<center><math>
\tilde W^r(a,b)\,=\,\{\,f\in W^r(a,b):\,  f^{(i)}(a)=f^{(i)}(b),\; 0\le i\le r-1\,\}</math>,</center>

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

<center><math>
\int_a^b f^{(r)}(x)\tilde s^{(r)}(x)\,dx\,=\,0. 
</math></center>

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

<center><math>\int_a^b \Big(  f^{(r)}(x)\Big)^2\,dx\,\ge\,
  \int_a^b \Big(\tilde s_f^{(r)}(x)\Big)^2\,dx. 
</math></center>

</div></div>

==Dygresja o najlepszej aproksymacji==

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

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

<center><math>\|f-v_f\|\,=\,\min_{v\in V_n}\|f-v\|. 
</math></center>

Okazuje się, że tak postawione zadanie ma rozwiązanie <math>v_f</math>, choć nie zawsze jest ono wyznaczone jednoznacznie. 

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

<center><math>\|f\|\,=\,\sqrt{\int_a^b\left(f^{(r)}(x)\right)^2\,dx}.  
</math></center>

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

<center><math>V_{n+1}\,=\,{\cal S}_r
</math></center>

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

<center><math>\|f-s_f\|\,=\,\min_{s\in {\cal S}_r}\|f-s\|. 
</math></center>

Rzeczywiście, ponieważ norma w przestrzeni <math>W^r(a,b)</math> generowana jest przez iloczyn skalarny 

<center><math>(f_1,f_2)\,=\,
    \int_a^b f_1^{(r)}(x)f_2^{(r)}(x)\,dx, 
</math></center>

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

<center><math>(f-v_f, v)\,=\,0, \qquad\forall v\in V. 
</math></center>

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

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

To zaś jest prawdą, gdy <math>v_f</math> interpoluje <math>f</math> w punktach <math>x_j</math>, czyli <math>v_f=s_f</math>.

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 <b>rozdział 6.4</b> w
* D. Kincaid, W. Cheney <cite>Analiza numeryczna</cite>, Wydawnictwa Naukowo-Techniczne, Warszawa 2006, ISBN 83-204-3078-X.
 
Warto także zapoznać się (nieobowiązkowo) z rozdziałami&nbsp;6.5 i&nbsp;6.6 tamże.