Splajn (matematyka)

Aby zapoznać się z narzędziem do rysowania, zobacz Płaski splajn .

Pojedyncze węzły na 1/3 i 2/3 tworzą splajn trzech wielomianów sześciennych spotykających się z ciągłością parametryczną C ² . Potrójne węzły na obu końcach przedziału zapewniają, że krzywa interpoluje punkty końcowe

W matematyce splajn jest specjalną funkcją określoną fragmentarycznie przez wielomiany . W problemach z interpolacją interpolacja splajnem jest często preferowana zamiast interpolacji wielomianowej, ponieważ daje podobne wyniki, nawet przy użyciu wielomianów niskiego stopnia , unikając jednocześnie zjawiska Runge'a dla wyższych stopni.

W poddziedzinach informatyki projektowania wspomaganego komputerowo i grafiki komputerowej termin splajn częściej odnosi się do fragmentarycznie wielomianowej ( parametrycznej ) krzywej . Splajny są popularnymi krzywymi w tych poddziedzinach ze względu na prostotę ich konstrukcji, łatwość i dokładność oceny oraz ich zdolność do aproksymacji złożonych kształtów poprzez dopasowanie krzywej i interaktywne projektowanie krzywych.

Termin splajn pochodzi od elastycznych urządzeń splajnowych używanych przez stoczniowców i kreślarzy do rysowania gładkich kształtów.

Wstęp

Termin „splajn” jest używany w odniesieniu do szerokiej klasy funkcji używanych w aplikacjach wymagających interpolacji i/lub wygładzania danych. Dane mogą być jednowymiarowe lub wielowymiarowe. Funkcje splajnu dla interpolacji są zwykle określane jako minimalizatory odpowiednich miar chropowatości (na przykład całkowa kwadratowa krzywizna) z zastrzeżeniem ograniczeń interpolacji. Splajny wygładzające można postrzegać jako uogólnienia splajnów interpolacyjnych, w których funkcje są określone w celu zminimalizowania ważonej kombinacji średniego kwadratowego błędu aproksymacji obserwowanych danych i miary chropowatości. W przypadku wielu znaczących definicji miary chropowatości stwierdzono, że funkcje splajnu mają charakter skończonych wymiarów, co jest głównym powodem ich użyteczności w obliczeniach i reprezentacji. W pozostałej części tej sekcji skupimy się całkowicie na jednowymiarowych splajnach wielomianowych i używamy terminu „splajn” w tym ograniczonym znaczeniu.

Definicja

Zaczniemy od ograniczenia naszej dyskusji do wielomianów w jednej zmiennej . W tym przypadku splajn jest fragmentaryczną funkcją wielomianową . Ta funkcja, nazwijmy ją S , pobiera wartości z przedziału [ a , b ] i odwzorowuje je na zbiór liczb rzeczywistych ${\ displaystyle \ mathbb {R}}$

${\ Displaystyle S: [a, b] \ do \ mathbb {R}.}$

Chcemy, aby S było określone fragmentarycznie. Aby to osiągnąć, niech przedział [ a , b ] będzie objęty k uporządkowanymi, rozłącznymi podprzedziałami,

${\ Displaystyle [t_ {i}, t_ {i + 1}] {\ mbox {}} i = 0, \ ldots, k- 1}$

${\ Displaystyle [a, b] = [t_ {0}, t_ {1}} \ kubek [t_ {1}, t_ {2} })\cup \cdots \cup [t_{k-2},t_{k-1})\cup [t_{k-1},t_{k})\cup [t_{k}]}$

${\ Displaystyle a = t_ {0} \ równoważnik t_ {1} \ równoważnik \ cdots \ równoważnik t_ {k-1} \ równoważnik t_ {k} = b }$

Na każdym z tych k „kawałków” [ a , b ] chcemy zdefiniować wielomian, nazwijmy go P _i .

${\ Displaystyle P_ {i}: [t_ {i}, t_ {i + 1}] \ do \ mathbb {R}}$ .

W i- tym podprzedziale [ a , b ] S jest określone przez P _i ,

${\ Displaystyle S (t) = P_ {0} (t) {\ mbox {}} t_ {0} \ równoważnik t <t_ {1 },}$

${\ Displaystyle S (t) = P_ {1} (t) {\ mbox {}} t_ {1} \ równoważnik t <t_ {2},}$

${\ Displaystyle \ vdots}$

${\ Displaystyle S (t) = P_ {k-1} (t) {\ mbox {}} t_ {k-1} \ równoważnik t \ równoważnik t_ {k}.}$

Dane k+1 punkty t _i nazywane są węzłami . Wektor $_$ _ _ _ Jeśli węzły są równomiernie rozmieszczone w przedziale [ a , b ] mówimy, że splajn jest jednorodny , w przeciwnym razie mówimy , że jest niejednorodny .

$rzędu$ z elementów wielomianu ja _ma stopień co najwyżej n , to mówi się, że splajn ma stopień (lub n + 1 ).

Jeśli $,$ sąsiedztwie że splajn ma ₍ co najmniej) gładkość do ${ r_{i}}}$ o t _ja . Oznacza to, że w t _i dwa wielomiany P _i-1 i P _i mają wspólne wartości pochodnych od pochodnej rzędu 0 (wartość funkcji) do pochodnej rzędu r _i (innymi słowy, dwa sąsiednie elementy wielomianu łączą się z utratą gładkości co najwyżej n - r _i )

${\ Displaystyle P_ {i-1} ^ {(0)} (t) = P_ {i} ^ {(0)} (t)}$

${\ Displaystyle P_ {i-1} ^ {(1)} (t) = P_ {i} ^ {(1)} (t )}$

${\ Displaystyle \ vdots}$

${\ Displaystyle P_ {i-1} ^ {(r_ {i})} (t) = P_ {i} ^ {(r_ {i}) }(t)}$ .

wektor ${\ Displaystyle {\ mathbf {r}} = (r_ {1}, \ kropki, r_ {k-1})}$ splajn ma gładkość ${\ Displaystyle C ^ {r_ {i}}}$ w t _ja dla ${\ Displaystyle i = 1, \ ldots, k-1}$ nazywa się wektorem gładkości dla splajnu.

Biorąc pod uwagę wektor węzła ${\ mathbf$ stopień n i wektor gładkości ${r}}}$ dla ${\ Displaystyle {\ mathbf {t}}}$${\ Displaystyle \ leq n} o$ wektor węzła i wektor gładkości ${\ Displaystyle {\ mathbf {r}}}$${\ Displaystyle {\ mathbf {r}}}$ . Wyposażony w operację dodawania dwóch funkcji (dodawanie punktowe) i branie rzeczywistych wielokrotności funkcji, zbiór ten staje się rzeczywistą przestrzenią wektorową. Ta przestrzeń splajnu jest zwykle oznaczana przez ${\ Displaystyle S_ {n} ^ {\ mathbf {r}} ({\ mathbf {t}})$ }

W matematycznym badaniu splajnów wielomianowych pytanie, co się stanie, gdy dwa węzły, powiedzmy t _i oraz t _{i +1} , zostaną przesunięte razem, ma łatwą odpowiedź. Kawałek wielomianu P _i ( t ) znika, a kawałki P _{i −1} ( t ) i P _{i +1} ( t ) łączą się z sumą strat ciągłości dla t _i oraz t _{i +1} . To jest,

${\ Displaystyle S (t) \ w do ^ {n-j_ {i} -j_ {i + 1} } [t_ {i} = t_ {i + 1}],}$ gdzie $\ Displaystyle j_ {i} = nr_ {i}}$

Prowadzi to do bardziej ogólnego zrozumienia wektora węzłów. Utratę ciągłości w dowolnym punkcie można uznać za wynik wielu węzłów zlokalizowanych w tym punkcie, a typ splajnu można całkowicie scharakteryzować za pomocą stopnia n i rozszerzonego wektora węzłów

${\ Displaystyle (t_ { 0},t_{1},\cdots,t_{1},t_{2},\cdots,t_{2},t_{3},\cdots,t_{k-2},t_{k-1} ,\cdots ,t_{k-1},t_{k})}$

gdzie t _ja powtarza się _{jot ja} razy dla ${\ Displaystyle i = 1, \ kropki, k-1}$ .

Krzywa parametryczna na przedziale [ a , b ]

${\ Displaystyle G (t) = (X (t), Y (t)) {\ mbox {}} t\w [a,b]}$

jest krzywą splajnu , jeśli zarówno X , jak i Y są funkcjami splajnu tego samego stopnia z tymi samymi rozszerzonymi wektorami węzłów w tym przedziale.

Przykłady

Załóżmy, że przedział [ a , b ] wynosi [0,3], a podprzedziały to [0,1], [1,2] i [2,3]. Załóżmy, że elementy wielomianu mają być stopnia 2, a elementy na [0,1] i [1,2] muszą łączyć się wartością i pierwszą pochodną (w t = 1), podczas gdy elementy na [1,2] i [ 2,3] łączą się po prostu wartością (przy t = 2). To zdefiniowałoby typ splajnu S ( t ), dla którego

${\ Displaystyle S (t) = P_ {0} (t) = -1 + 4 t-t ^ {2} \mbox{ , }}0\równik t<1}$

${\ Displaystyle S (t) = P_ {1} (t) = 2 t {\ mbox {,}} 1 \ równoważnik t <2}$

${\ Displaystyle S (t) = P_ {2} (t) = 2-t + t ^ {2} {\ mbox {}} 2 \ równoważnik t \ równoważnik 3}$

byłby członkiem tego typu, a także

${\ Displaystyle S (t) = P_ {0} (t) = -2-2 t ^ {2} {\ mbox {, }}0\równik t<1}$

${\ Displaystyle S (t) = P_ {1} (t) = 1-6 t + t ^ {2} {\ mbox {}} 1 \ równoważnik t <2}$

${\ Displaystyle S (t) = P_ {2} (t) = -1 + t-2t ^ {2} {\ mbox {}} 2 \ równoważnik t\równik 3}$

byłby członkiem tego typu. (Uwaga: chociaż element wielomianu 2 t nie jest kwadratowy, wynik nadal nazywany jest splajnem kwadratowym. Pokazuje to, że stopień splajnu jest maksymalnym stopniem jego części wielomianowych). Rozszerzony wektor węzła dla tego typu splajnu byłby być (0, 1, 2, 2, 3).

Najprostszy splajn ma stopień 0. Nazywa się go również funkcją schodkową . Kolejny najprostszy splajn ma stopień 1. Jest również nazywany splajnem liniowym . Zamknięty splajn liniowy (tzn. pierwszy i ostatni węzeł są takie same) na płaszczyźnie jest po prostu wielokątem .

Wspólny splajn to naturalny sześcienny splajn stopnia 3 z ciągłością C ² . Słowo „naturalny” oznacza, że ​​drugie pochodne wielomianów splajnu są równe zeru w punktach końcowych przedziału interpolacji

${\ Displaystyle S '' (a) \ = S'' (b) = 0.}$

Wymusza to, aby splajn był linią prostą poza interwałem, nie zakłócając jednocześnie jego gładkości.

Algorytm obliczania naturalnych splajnów sześciennych

Splajny sześcienne mają postać $\ Displaystyle {S} _ {j}\left(x\right)=a_{j}+b_{j}\left(x-x_{j}\right)+c_{j}{\left(x-x_{j}\right) }^{2}+d_{j}{\left(x-x_{j}\right)}^{3}}$ .
Dany układ współrzędnych ${\ Displaystyle C = \ lewo [\ lewo ({x} _ {0}, {y} _ {0} \ prawo), \ lewo ({x} _ {1}, {y}_{1}\right),....,\left({x}_{n},{y}_{n}\right)\right]} chcemy znaleźć zbiór$ n $\ styl wyświetlania n\,}$ splajny ${\ Displaystyle {S} _ {i} \ lewo (x \ prawej)}$ dla ${\ Displaystyle i = 0, \ ldots, n-1.}$

Muszą one spełniać:

• ${\ Displaystyle S_ {i} \ lewo (x_ {i} \ prawej) = y_ {i }=S_{i-1}\left(x_{i}\right),i=1,\ldots ,n-1.}$
• ${\ Displaystyle S_ {0} \ lewo (x_ {0} \ prawo) = y_ {0}.}$
• ${\ Displaystyle S_ {n-1} \ lewo (x_ {n} \ prawo) = y_ {n}.}$
• ${\ Displaystyle {S'} _ {i} \ lewo (x_ {i} \ prawo) = {S'}_{i-1}\left(x_{i}\right),i=1,\ldots ,n-1.}$
• ${\ Displaystyle {S''} _ {i} \ lewo (x_ {i} \ prawo) ={S''}_{i-1}\left(x_{i}\right),i=1,\ldots ,n-1.}$
• ${\ Displaystyle {S''} _ {0} \ lewo (x_ {0} \ prawej) = {S''} _ {n-1} \left(x_{n}\right)=0}$ .

Zdefiniujmy jeden splajn sześcienny $jako$ -krotkę ${\ Displaystyle (a, b, c, d, x_ {t}) \$ gdzie $do {\ Displaystyle a, b, c \,}$ i $\ Displaystyle d \,}$ odpowiadają współczynnikom w postaci pokazanej wcześniej i ${\ Displaystyle x_ {t} \,}$ jest równe do ${\ displaystyle x_ {j}. \,}$

Algorytm obliczania naturalnych splajnów sześciennych: Dane wejściowe: zestaw współrzędnych do ${\ displaystyle C \,$ z ${\ Displaystyle \ lewo | C \ prawo | = n + 1}$ Dane wyjściowe: zestaw splajnów, który składa się z n 5-krotek.

1. Utwórz nową tablicę a o rozmiarze n + 1 i dla ${\ Displaystyle i = 0, \ ldots, n}$ ustaw ${\ Displaystyle a_ {i} = y_ {i} \,}$
2. Utwórz nowe tablice b i d każda o rozmiarze n .
3. $x_{i+1}-x_{i}\,}$ nową tablicę h rozmiarze n i dla h $1$${$
4. Utwórz nową tablicę α o rozmiarze n i dla ${\ Displaystyle i = 1, \ ldots, n-1}$ zestaw ${\ Displaystyle {\ alfa} _ {i} = {\ Frac {3} {{h} _ {i}}} \ lewo ({a} _ {i + 1} - {a} _ {i} \ prawo )-{\frac {3}{{h}_{i-1}}}\left({a}_{i}-{a}_{i-1}\right)}$ .
5. Utwórz nowe tablice c , l , μ i z każda o rozmiarze ${\ Displaystyle n + 1 \,}$ .
6. Ustaw ${\ mu} _ {0} = z_ {0} = 0 \,}$
7. ja $1, \ ldots, n-1 \,}$
   1. l $\ lewo ({x} _ {i + 1} - {x}_{i-1}\right)-{h}_{i-1}{\mu }_{i-1}}$ .
   2. Ustaw ${\ Displaystyle {\ mu} _ {i} = {\ Frac {{h} _ {i}} {{l} _ {i}}}}$ .
   3. zestaw ${\ Displaystyle {z} _ {i} = {\ Frac {{\ alfa} _ {i} - {h} _ {i-1} {z}_{i-1}}{{l}_{i}}}}$ .
8. zestaw ${\ Displaystyle l_ {n} = 1; z_ {n} = c_ {n} = 0. \,}$
9. dla ${\ Displaystyle j = n-1, n-2, \ ldots, 0}$
   1. zestaw do $z_ {j} - {\ mu} _ {j} c_ {j + 1} \,}$
   2. Ustaw ${j} = {\ Frac {{a} _ {j + 1} - { a}_{j}}{{h}_{j}}}-{\frac {{h}_{j}\left({c}_{j+1}+2{c}_{j} \right)}{3}}}$
   3. zestaw re $\ Displaystyle d_ {j} = {\ Frac {{c} _ {j + 1} - {c} _ {j}} {3 {h}$
10. Utwórz nowy zestaw Splines i nazwij go zestaw_wyjściowy. Wypełnij go n splajnami S .
11. ja $= 0, \ ldots, n-1}$
    1. Zestaw S _{ja , a} = a _ja
    2. Ustaw S _{ja , b} = b _ja
    3. Ustaw S _{ja , do} = do _ja
    4. Ustaw S _{ja , re} = re _ja
    5. Ustaw S _{ja , x} = x _ja
12. Wyjście zestaw_wyjściowy

Notatki

Można by zapytać, jakie znaczenie ma więcej niż n wielokrotnych węzłów w wektorze węzłów, ponieważ prowadziłoby to do ciągłości takich jak

${\ Displaystyle S (t) \ w C ^ {- m} {\ mbox {}} m> 0}$

w miejscu tak dużej różnorodności. Zgodnie z konwencją każda taka sytuacja wskazuje na prostą nieciągłość między dwoma sąsiednimi elementami wielomianu. Oznacza to, że jeśli węzeł t _i pojawia się więcej niż n + 1 razy w rozszerzonym wektorze węzłów, wszystkie jego wystąpienia przekraczające ( n + 1) można usunąć bez zmiany charakteru splajnu, ponieważ wszystkie krotności n + 1, n + 2, n + 3 itd. mają to samo znaczenie. Powszechnie przyjmuje się, że każdy wektor węzła definiujący dowolny typ splajnu został usunięty w ten sposób.

Klasyczny typ splajnu stopnia n używany w analizie numerycznej ma ciągłość

${\ Displaystyle S (t) \ w \ operatorname {C} ^ {n-1} [a, b], \,}$

co oznacza, że ​​każde dwa sąsiednie elementy wielomianu spotykają się pod względem wartości i pierwszych n - 1 pochodnych w każdym węźle. Matematyczny splajn, który najdokładniej modeluje splajn płaski , to sześcienny ( n = 3), dwukrotnie różniczkowalny w sposób ciągły ( C ² ), naturalny splajn, który jest splajnem tego klasycznego typu z dodatkowymi warunkami nałożonymi w punktach końcowych a i b .

Inny rodzaj splajnu, który jest często używany w grafice, na przykład w programach do rysowania, takich jak Adobe Illustrator firmy Adobe Systems , ma elementy, które są sześcienne, ale mają co najwyżej ciągłość

${\ Displaystyle S (t) \ w \ operatorname {C} ^ {1} [a, b].}$

Ten typ splajnu jest również używany w PostScript , a także w definicji niektórych komputerowych czcionek typograficznych.

Wiele systemów projektowania wspomaganego komputerowo, zaprojektowanych z myślą o wysokiej klasy grafice i animacji, wykorzystuje rozszerzone wektory węzłów, na przykład Autodesk Maya . Systemy projektowania wspomaganego komputerowo często wykorzystują rozszerzoną koncepcję splajnu znaną jako niejednorodny wymierny B-splajn (NURBS).

Jeśli dostępne są próbkowane dane z funkcji lub obiektu fizycznego, interpolacja splajnu jest podejściem do tworzenia splajnu, który przybliża te dane.

Wyrażenie ogólne dla interpolującego splajnu ^{sześciennego} C2

Ogólne wyrażenie na i -ty interpolujący splajn sześcienny C ² w punkcie x z warunkiem naturalnym można znaleźć za pomocą wzoru

${\ Displaystyle S_ {i} (x) = {\ Frac {z_ {i }(x-t_{i-1})^{3}}{6h_{i}}}+{\frac {z_{i-1}(t_{i}-x)^{3}}{6h_{ i}}}+\lewo[{\frac {f(t_{i})}{h_{i}}}-{\frac {z_{i}h_{i}}{6}}\prawo](x -t_{i-1})+\lewo[{\frac {f(t_{i-1})}{h_{i}}}-{\frac {z_{i-1}h_{i}}{ 6}}\prawo](t_{i}-x)}$

Gdzie

• ${\ Displaystyle z_ {i} = f ^ {\ pierwsza \ pierwsza} (t_ {i})}$ to wartości drugiej pochodnej w i- tym węźle.
• ${\ Displaystyle h_ {i} ^ {} = t_ {i} -t_ {i-1}}$
• ${\ Displaystyle f (t_ {i} ^ {})}$ to wartości funkcji w i -tym węźle.

Reprezentacje i nazwy

Dla danego przedziału [ a , b ] i danego rozszerzonego wektora węzłów na tym przedziale krzywe stopnia n tworzą przestrzeń wektorową . W skrócie oznacza to, że dodanie dowolnych dwóch splajnów danego typu daje splajn tego danego typu, a pomnożenie splajnu danego typu przez dowolną stałą daje splajn tego danego typu. Wymiar przestrzeni zawierającej wszystkie splajny określonego typu można policzyć z rozszerzonego wektora węzłów :

${\ Displaystyle a = t_ {0}< \underbrace {t_{1}=\cdots =t_{1}} _{j_{1}}<\cdots <\underbrace {t_{k-2}=\cdots =t_{k-2}} _{j_ {k-2}}<t_{k-1}=b}$

${\ Displaystyle j_ {i} \ równoważnik n + 1 ~, ~ ~ i = 1, \ ldots, k-2.}$

Wymiar jest równy sumie stopnia plus krotności

${\ Displaystyle d = n + \ suma _ {i = 1} ^ {k-2} j_ {i}.}$

Jeśli typ splajnu ma nałożone dodatkowe warunki liniowe, wynikowy splajn będzie leżał w podprzestrzeni. Na przykład przestrzeń wszystkich naturalnych splajnów sześciennych jest podprzestrzenią przestrzeni wszystkich splajnów ^{sześciennych} C2 .

Literatura splajnów jest pełna nazw specjalnych typów splajnów. Nazwy te zostały powiązane z:

• Wybory dokonane w celu przedstawienia splajnu, na przykład:
  • używając funkcji bazowych dla całego splajnu (dając nam nazwę B-splajn )
  • używając wielomianów Bernsteina zastosowanych przez Pierre'a Béziera do przedstawienia każdego fragmentu wielomianu (dając nam nazwę splajny Béziera )
• Wybory dokonane podczas tworzenia rozszerzonego wektora węzłów, na przykład:
  • stosując pojedyncze węzły dla ciągłości C ^{n -1} i równomiernie rozmieszczając te węzły na [ a , b ] (co daje nam jednolite splajny )
  • używanie węzłów bez ograniczeń co do rozstawu (co daje nam niejednorodne splajny )
• Wszelkie specjalne warunki nałożone na splajn, na przykład:
  • wymuszanie zerowych pochodnych w punktach a i b (dając nam naturalne splajny )
  • wymaganie, aby podane wartości danych znajdowały się na splajnie (dając nam splajny interpolujące )

Często wybierano specjalną nazwę dla typu splajnu spełniającego dwa lub więcej głównych elementów powyżej. Na przykład splajn Hermite'a to splajn wyrażony za pomocą wielomianów Hermite'a do reprezentowania każdego z poszczególnych elementów wielomianu. Są one najczęściej używane z n = 3; to znaczy, jak splajny Cubic Hermite . W tym stopniu można je dodatkowo wybrać tak, aby były tylko stycznie ciągłe ( C ¹ ); co oznacza, że ​​wszystkie węzły wewnętrzne są podwójne. Wynaleziono kilka metod dopasowania takich splajnów do danych punktów; to znaczy uczynić je interpolującymi splajnami i zrobić to przez oszacowanie prawdopodobnych wartości stycznych, w których spotykają się dwa elementy wielomianu (dając nam splajny kardynalne , splajny Catmull-Rom i splajny Kochanka-Bartelsa , w zależności od zastosowanej metody).

Dla każdej z reprezentacji należy znaleźć pewne sposoby oceny, aby wartości splajnu mogły być tworzone na żądanie. Dla tych reprezentacji, które wyrażają każdą pojedynczą część wielomianu P _i ( t ) w kategoriach jakiejś bazy wielomianów stopnia n , jest to koncepcyjnie proste:

• t ∈ $}]}$ +
• Wyszukaj podstawę wielomianu wybraną dla tego przedziału ${\ Displaystyle P_ {0}, \ ldots, P_ {k-2}}$
• Znajdź wartość każdego wielomianu bazowego w t : ${\ Displaystyle P_ {0} (t), \ ldots, P_ {k-2} (t)}$
• ₀ Poszukaj współczynników kombinacji liniowej tych wielomianów bazowych, które dają splajn w tym przedziale c , ..., c _{k -2}
• Dodaj tę liniową kombinację podstawowych wartości wielomianu, aby uzyskać wartość splajnu w t :

${\ Displaystyle \ suma _ {j = 0} ^ {k-2} c_ {j} P_ {j} (t).}$

Jednak etapy oceny i podsumowania są często łączone w sprytny sposób. Na przykład wielomiany Bernsteina są podstawą wielomianów, które można efektywnie oceniać w kombinacjach liniowych przy użyciu specjalnych relacji powtarzalności. To jest esencja algorytmu De Casteljau , który występuje w krzywych Béziera i splajnach Béziera ).

Jednak w przypadku reprezentacji, która definiuje splajn jako liniową kombinację splajnów bazowych, potrzebne jest coś bardziej wyrafinowanego. Algorytm de Boora jest skuteczną metodą oceny B-sklejanych .

Historia

Zanim pojawiły się komputery, obliczenia numeryczne wykonywano ręcznie. Chociaż używano funkcji zdefiniowanych fragmentarycznie, takich jak funkcja znaku lub funkcja schodkowa , generalnie preferowano wielomiany, ponieważ łatwiej było z nimi pracować. Wraz z pojawieniem się komputerów splajny zyskały na znaczeniu. Początkowo były używane jako zamiennik wielomianów w interpolacji, a następnie jako narzędzie do konstruowania gładkich i elastycznych kształtów w grafice komputerowej.

Powszechnie przyjmuje się, że pierwszym matematycznym odniesieniem do splajnów jest artykuł Schönberga z 1946 r., który jest prawdopodobnie pierwszym miejscem, w którym słowo „splajn” jest używane w połączeniu z gładkim, fragmentarycznym przybliżeniem wielomianowym. Jednak pomysły mają swoje korzenie w przemyśle lotniczym i stoczniowym. W przedmowie do (Bartels et al., 1987) Robin Forrest opisuje „ wyciąganie po profilach ”, technikę używaną w brytyjskim przemyśle lotniczym podczas II wojny światowej do konstruowania szablonów samolotów przez przepuszczanie cienkich drewnianych pasków (zwanych „ wypustami” ) ") poprzez punkty ułożone na podłodze dużego strychu projektowego, technikę zapożyczoną z projektowania kadłubów statków. Przez lata praktyka projektowania statków wykorzystywała modele do projektowania w małym. Pomyślny projekt był następnie nanoszony na papier milimetrowy i kluczowe punkty działki zostały ponownie wykreślone na większym papierze milimetrowym w pełnym rozmiarze. Cienkie drewniane paski zapewniały interpolację kluczowych punktów w gładkie krzywe. Paski były utrzymywane na miejscu w dyskretnych punktach (zwanych przez Forresta „kaczkami” ; Schoenberg użył „psów” lub „szczurów”) i między tymi punktami przybierałby kształty o minimalnej energii odkształcenia. Według Forresta jednym z możliwych impulsów dla modelu matematycznego tego procesu była potencjalna utrata krytycznych elementów konstrukcyjnych całego samolotu gdyby strych został trafiony przez wrogą bombę. Doprowadziło to do „wyciągnięcia stożkowego”, w którym wykorzystano sekcje stożkowe do modelowania położenia krzywej między kaczkami. Wyciągnięcie stożkowe zostało zastąpione przez to, co nazwalibyśmy splajnami na początku lat 60. praca JC Fergusona w Boeing i (nieco później) przez MA Sabin w British Aircraft Corporation .

Słowo „splajn” było pierwotnie słowem dialektu wschodnioangielskiego .

Wydaje się, że zastosowanie splajnów do modelowania karoserii samochodowych ma kilka niezależnych początków. Kredyt jest zgłaszany w imieniu de Casteljau w Citroën , Pierre'a Béziera w Renault oraz Birkhoffa , Garabediana i de Boora w General Motors (zob. Przynajmniej jeden z artykułów de Casteljau został opublikowany, ale niezbyt szeroko, w 1959 roku. Praca De Boora w General Motors zaowocowało opublikowaniem wielu artykułów na początku lat sześćdziesiątych, w tym niektórych fundamentalnych prac nad B-splajnami .

Prace prowadzono również w firmie Pratt & Whitney Aircraft, gdzie zatrudniono dwóch autorów (Ahlberg i in., 1967) — pierwszego obszernego opracowania splajnów — oraz w firmie David Taylor Model Basin autorstwa Feodora Theilheimera . Praca w General Motors jest szczegółowo opisana w (Birkhoff, 1990) i (Young, 1997). Davis (1997) podsumowuje część tego materiału.

• Ferguson, James C, Interpolacja krzywej wielu zmiennych, J. ACM, tom. 11, nie. 2, s. 221-228, kwiecień 1964.
• Ahlberg, Nielson i Walsh, Teoria splajnów i ich zastosowania, 1967.
• Birkhoff, Dynamika płynów, obliczenia reaktorów i reprezentacja powierzchni, w: Steve Nash (red.), A History of Scientific Computation , 1990.
• Bartels, Beatty i Barsky, Wprowadzenie do splajnów do użytku w grafice komputerowej i modelowaniu geometrycznym, 1987.
• Birkhoff i de Boor, Odcinkowa interpolacja wielomianowa i aproksymacja, w: HL Garabedian (red.), Proc. Sympozjum General Motors z 1964 r., s. 164–190. Elsevier, Nowy Jork i Amsterdam, 1965.
• Davis, B-splajny i projektowanie geometryczne , SIAM News, obj. 29, nie. 5, 1997.
• Epperson, Historia splajnów , NA Digest, tom. 98, nie. 26, 1998.
• Stoer & Bulirsch, Wprowadzenie do analizy numerycznej. Springer-Verlag . P. 93-106. ISBN 0387904204
• Schoenberg, Przyczynki do problemu aproksymacji równoodległych danych przez funkcje analityczne, Quart. Aplikacja Matematyka, tom. 4, s. 45–99 i 112–141, 1946.
• Young, Garrett Birkhoff i matematyka stosowana, Zawiadomienia o AMS, tom. 44, nr. 11, s. 1446-1449, 1997.
• Chapra, Canale, „Metody numeryczne dla inżynierów”, wydanie 5.

Linki zewnętrzne

Teoria

• Interaktywne wprowadzenie do splajnów , ibiblio.org

Funkcja Excela

• XLL Excel Addin Function Implementacja splajnu sześciennego

Narzędzia online

• Narzędzie online do interpolacji splajnu sześciennego
• Uczenie się przez symulacje Interaktywna symulacja różnych splajnów sześciennych
• Symetryczne krzywe splajnu , animacja autorstwa Theodore'a Graya , The Wolfram Demonstrations Project , 2007.

Kod komputerowy

• Notes, PPT, Mathcad, Maple, Mathematica, Matlab , Instytut Holistycznych Metod Numerycznych
• różne procedury , NTCC
• Sisl: Opensource biblioteka C dla NURBS , SINTEF
• VBA Spline Interpolation , vbnumericalmethods.com