MN11

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania


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 i węzły

przy czym .

Definicja

Funkcję nazywamy funkcją sklejaną rzędu () odpowiadającą węzłom , , jeśli spełnione są następujące dwa warunki:

(i)
jest wielomianem stopnia co najwyżej na każdym

z przedziałów , tzn. , ,

(ii)
jest -krotnie różniczkowalna w sposób

ciągły na całej prostej, tzn. .

Jeśli ponadto

(iii)
jest wielomianem stopnia co najwyżej poza

, tzn. ,

to jest naturalną funkcją sklejaną.

Klasę naturalnych funkcji sklejanych rzędu opartych na węzłach będziemy oznaczać przez , albo po prostu , jeśli węzły są ustalone.

Na przykład funkcją sklejaną rzędu pierwszego () jest funkcja ciągła i liniowa na poszczególnych przedziałach . Jest ona naturalna, gdy poza 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 . Są to funkcje, które są na 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 jest naturalna, gdy poza jest wielomianem liniowym, a więc .

Interpolacja i gładkość

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

Niech będzie klasą funkcji takich, że jest razy różniczkowalna na w sposób ciągły oraz istnieje prawie wszędzie na i jest całkowalna z kwadratem, tzn.

Oczywiście każda funkcja sklejana rzędu (niekoniecznie naturalna) należy do .

Lemat

Niech będzie funkcją zerującą się w węzłach, tzn.

Wtedy dla dowolnej naturalnej funkcji sklejanej mamy

Dowód

Dla funkcja jest przedziałami stała. Oznaczając przez jej wartość na dostajemy

ponieważ zeruje się w .

Rozpatrzmy teraz przypadek . Ponieważ

to

Wobec tego, że jest poza przedziałem wielomianem stopnia co najwyżej oraz jest ciągła na , mamy , a stąd

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

Funkcja jest przedziałami stała, a więc możemy teraz zastosować ten sam argument jak dla , aby pokazać,

że ostatnia całka jest równa zeru. 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 , to dla dowolnej funkcji istnieje dokładnie jedna naturalna funkcja sklejana interpolująca w węzłach , tzn. taka, że

Dowód

Pokażemy najpierw, że jedyną naturalną funkcją sklejaną interpolującą dane zerowe jest funkcja zerowa. Rzeczywiście, jeśli dla , to podstawiając w poprzednim lemacie , otrzymujemy

Stąd jest funkcją zerową, a więc jest wielomianem stopnia co najwyżej zerującym się w co najmniej punktach . Wobec tego, że , otrzymujemy .

Zauważmy teraz, że problem znalezienia naturalnej funkcji sklejanej interpolującej można sprowadzić do rozwiązania układu równań liniowych z macierzą kwadratową. Na każdym przedziale , , jest ona postaci

dla pewnych współczynników , a na i mamy odpowiednio

i

Aby wyznaczyć , musimy więc znaleźć ogółem współczynników , przy czym są one związane warunkami jednorodnymi wynikającymi z gładkości,

dla i , oraz niejednorodnymi warunkami interpolacyjnymi,

dla . Otrzymujemy więc układ równań liniowych ze względu na niewiadomych .

Naturalna funkcja sklejana interpolująca 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 , ) jest jedynym rozwiązaniem zadania interpolacyjnego. 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 i niech będzie naturalną funkcją sklejaną rzędu interpolującą w węzłach , . Wtedy

Dowód

Jeśli przedstawimy w postaci , to

Funkcja jest w klasie i zeruje się w węzłach , . Z lematu wynika więc, że

, a stąd wynika teza. End of proof.gif

Wartość całki 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 najgładszą funkcją spełniającą dane warunki interpolacyjne w wybranych węzłach .

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 interpolującej daną funkcję , tzn. takiej, że dla . W tym celu, na każdym przedziale przedstawimy w postaci jej rozwinięcia w szereg Taylora w punkcie ,

i podamy algorytm obliczania dla .

Warunki brzegowe i warunki ciągłości dla dają nam oraz , czyli

gdzie . Stąd, przyjmując dodatkowo , otrzymujemy

Z warunków ciągłości dla dostajemy z kolei

oraz

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

Powyższe równania definiują nam na odcinku naturalną kubiczną funkcję sklejaną. Ponieważ poszukiwana funkcja sklejana ma interpolować , mamy dodatkowych warunków interpolacyjnych , , oraz , z których

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

przy czym wzór ten zachodzi również dla . Po wyrugowaniu i podstawieniu , mamy

gdzie jest odpowiednią różnicą dzieloną. Możemy teraz powyższe wyrażenie na podstawić, aby otrzymać

Wprowadzając oznaczenie

możemy to równanie przepisać jako

, albo w postaci macierzowej

gdzie

Ostatecznie, aby znaleźć współczynniki 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 używając algorytmu przeganiania. Koszt znalezienia wszystkich współczynników kubicznej funkcji sklejanej interpolującej jest więc też proporcjonalny do .

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 , 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 . Będziemy zakładać, że jest dwa razy różniczkowalna w sposób ciągły.

Twierdzenie O błędzie interpolacji splajnem kubicznym

Jeśli to

W szczególności, dla podziału równomiernego , , mamy

Dowód

Wykorzystamy obliczoną wcześniej postać interpolującej funkcji sklejanej . Dla mamy

Z rozwinięcia w szereg Taylora w punkcie dostajemy oraz . Stąd

oraz

Niech teraz . Z postaci układu otrzymujemy

a stąd

co kończy dowód.

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

Jak widać, w przeciwieństwie do wielomianu interpolacyjnego, splajn interpolacyjny praktycznie pokrywa się z wykresem funkcji, tutaj: .

Uwaga

Niech

Ustalmy węzły . Dla , niech będzie naturalną funkcją sklejaną interpolującą w , , a dowolną inną aproksymacją korzystającą jedynie z informacji o wartościach w tych węzłach, tzn.

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

Wtedy

Aproksymacja naturalnymi funkcjami sklejanymi jest więc optymalna w klasie .

Można również pokazać, że interpolacja naturalnymi funkcjami sklejanymi na węzłach równoodległych , , jest optymalna co do rzędu w klasie , wśród wszystkich aproksymacji korzystających jedynie z informacji o wartościach funkcji w dowolnych punktach, oraz

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 , zdefiniowanej równościami

przy której . Baza kanoniczna jest jednak niewygodna w użyciu, bo funkcje 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 , ):

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

Dla i dodatkowo żądamy, aby

a dla i podobnie

Wtedy nie zeruje się tylko na przedziale . Wyznaczenie współczynników rozwinięcia w bazie funkcji sklejanej interpolującej wymaga rozwiązania układu liniowego z macierzą trójdiagonalną , a więc koszt obliczenia tych współczynników jest proporcjonalny do .

Uwaga

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

(iii)'
jest dla

funkcją okresową o okresie , tzn. , .

Klasę okresowych funkcji sklejanych rzędu oznaczymy przez . Funkcje te mają podobne własności jak naturalne funkcje sklejane. Dokładniej, niech

tzn. jest klasą funkcji z , które można przedłużyć do funkcji, krórych wszystkie pochodne do rzędu włącznie są -okresowe na . Wtedy dla dowolnej funkcji zerującej się w węzłach , oraz dla dowolnej mamy

Wynika z niego jednoznaczność rozwiązania zadania interpolacyjnego dla okresowych funkcji (tzn. takich, że ), jak również odpowiednia własność minimalizacyjna okresowych funkcji sklejanych. Dokładniej, jeśli oraz interpoluje w węzłach , , to

Dygresja o najlepszej aproksymacji

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

Niech będzie pewną przestrzenią liniową funkcji , w której określona została norma . Niech będzie podprzestrzenią w wymiaru . Dla danej , należy znaleźć funkcję taką, że

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

Jako przykład, rozpatrzmy . Utożsamiając funkcje takie, że , zdefiniujemy w normę

Dla ustalonych węzłów , niech

będzie podprzestrzenią w naturalnych funkcji sklejanych rzędu opartych węzłach , . Oczywiście , co wynika z jednoznaczności rozwiązania w zadania interpolacji. Okazuje się, że wtedy optymalną dla jest naturalna funkcja sklejana interpolująca w węzłach , tzn.

Rzeczywiście, ponieważ norma w przestrzeni generowana jest przez iloczyn skalarny

jest to przestrzeń unitarna. Znane twierdzenie mówi, że w przestrzeni unitarnej najbliższą danej funkcją w dowolnej domkniętej podprzestrzeni jest rzut prostopadły na , albo równoważnie, taka funkcja , że iloczyn skalarny

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

To zaś jest prawdą, gdy interpoluje w punktach , czyli .

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.