Сплайни

Сплайн (англ. spline — планка, рейка) — функція, область визначення якої розбита на шматки, на кожному зі шматків функція є деяким поліномом (многочленом).

Сплайн
Підтримується Вікіпроєктом
Класифікаційний код ACM 2012	10003659
Сплайн у Вікісховищі

Сплайн із трьох кубічних поліномів

В задачах інтерполяції, інтерполяція сплайном краща, ніж інтерполяція многочленом, оскільки дає схожі результати навіть при менших степенях поліномів, а також при її використанні не виникає феномена Рунге.

Максимальний степінь поліномів в сплайні називається степенем сплайна. Різниця між степенем сплайна і його гладкістю називається дефектом сплайна.

Визначення та історія

Походження назви та історія

Сплайн (spline) називали гнучку металеву лінійку — універсальне лекало [ 30 листопада 2009 у Wayback Machine.], що використовували креслярі для того, щоб гладко з'єднати окремі точки на кресленні. Тобто для графічного виконання інтерполяції. Більше того, крива, що описує деформацію гнучкої лінійки зафіксованої в окремих точках є сплайном. Отже, ми маємо фізичну модель сплайн-функції (або навпаки сплайн-функція є математичною моделлю гнучкої лінійки). Інтуїтивний підхід до використання кускових функцій в задачах апроксимації зустрічався в математиці протягом тривалого часу. Але, як зазначає Корнійчук Н. П., втягнення сплайнів в теорію наближення відбулося через задачі інтерполяції, завдяки їхнім хорошим обчислювальним та апроксимативним властивостям.

Застосування

Початок розвитку теорії інтерполяції сплайнами та й сам термін сплайн відраховують з 1946 року зі статті Ізо Шонберга (Isaac Jacob Schoenberg). Особливо інтенсивний її розвиток відбувся в 1950-1970 роки, традиційною прикладною сферою використання інтерполяційних сплайнів стали в цей час системи автоматизованого проектування. Однак потенційні можливості сплайнів значно ширші ніж просто опис деяких кривих. В реальному світі велика кількість фізичних процесів за самою своєю природою є сплайнами. В механіці це деформація гнучкої пластини чи стержня, зафіксованих в окремих точках; траєкторія руху тіла, якщо сила, що діє на нього змінюється ступінчато (траєкторія штучного космічного об'єкта з активними та інерційними відрізками руху, траєкторія руху літака при ступінчатій зміні тяги двигунів та зміні профілю крила тощо.). В термодинаміці це теплообмін в стрижні складеному з фрагментів з різною теплопередачею. В хімії — дифузія через шари різних речовин. В електриці — поширення електромагнітних полів через різнорідні середовища. Тобто сплайн не надумана математична абстракція, а в багатьох випадках він є розв'язанням диференційних рівнянь, які описують цілком реальні фізичні процеси.

Алгебраїчний сплайн

Розгляд сплайнів почнемо з визначення алгебраїчного сплайна [ ]: Функція ${\displaystyle S(t)\,}$ визначена і неперервна на відрізку ${\displaystyle [a,b]\,}$ називається поліноміальним сплайном порядку ${\displaystyle m\,}$ з вузлами ${\displaystyle x_{j}\in (a\leq x_{0}<...<x_{n}\leq b)}$, якщо на кожному з відрізків ${\displaystyle [x_{j-1},x_{j})\,}$, ${\displaystyle S(t)\,}$ є алгебраїчним поліномом степені, що не перевищує ${\displaystyle m\,}$, а в кожній з точок ${\displaystyle x_{j}\,}$ деяка похідна ${\displaystyle S^{(v)}(t)\,}$ може мати розрив. Якщо в точці ${\displaystyle x_{j}\,}$ неперервні функції ${\displaystyle S(t),{S^{(i)}}(t),{\rm {}}...{\rm {}}{S^{(m-{k_{I}})}}(t)\,}$, а похідна ${\displaystyle {S^{(m-{k_{I}})}}(t)\,}$ в точці ${\displaystyle x_{j}\,}$ терпить розрив, число ${\displaystyle k=max(k_{i})\,}$ називають дефектом сплайна. Множину ${\displaystyle \{x_{0},x_{1},...,x_{n}\}\,}$ називають сіткою вузлів сплайна, а точки ${\displaystyle x_{j}\,}$ вузлами або точками стикання чи склейки сплайна.

Як слідує з визначення, для побудови сплайна, що складається з ${\displaystyle n-1\,}$ фрагмента потрібно знайти такі значення числових параметрів для кожного фрагмента — полінома степені ${\displaystyle m\,}$, які забезпечать неперервність у вузлах, як самої функції так і необхідних похідних. Отже всього слід визначити ${\displaystyle (n-1)*m\,}$ параметрів. З врахуванням умови інтерполяції та неперервності перших двох похідних визначення параметрів зводиться до розв'язання системи з ${\displaystyle n\,}$ лінійних рівнянь. Як правило, значення коефіцієнтів для відрізків поліномів безпосередньо не розраховуються.

Для визначення інтерполяційного сплайна з неперервною першою похідною достатньо розрахувати значення першої похідної у вузлах. Спосіб визначення похідних у вузлах сплайна визначає широку різноманітність інтерполяційних сплайнів. Часто похідні визначаються не як константи, а як деякі залежності від інтерпольованої функції та сітки інтерполяції.

Якщо значення першої похідної у вузлах розраховувати виходячи з умови неперервності другої похідної (вирішуючи систему з n лінійних рівнянь) то сплайн матиме дві неперервні похідні. Такий спосіб побудови сплайна, як і сам сплайн називають глобальним, оскільки при визначенні кожного з його коефіцієнтів враховується вся множина вузлів інтерполяції.

В інших випадках, для визначення окремого коефіцієнта, враховуються лише найближчі вузли інтерполяції і такі способи побудови, як і самі сплайни, називають локальними. Параметри фрагмента такого сплайна можна визначити незалежно від інших фрагментів.

Найпростішою умовою побудови фрагмента локального сплайна є умова рівності полінома на кінцях відрізків відповідним значенням інтерпольованої функції.

${\displaystyle P_{j}(t_{j})=f(t_{j}),\qquad P_{j}(t_{j-1})=f(t_{j-1})\qquad (1)}$

Для найпростішого сплайна — ламаної цієї умови цілком досить. Два коефіцієнта прямої однозначно визначаються з двох рівнянь. Такий сплайн є локальним. Для поліномів вищих степенів ми повинні додати додаткові умови таким чином, щоб загальне число рівнянь дорівнювало числу коефіцієнтів полінома. Так для сплайна 3-й степені такою умовою є рівність 1-ї похідної на кінцях відрізка деякому значенню, що визначається для сусідніх відрізків однаковим чином (у формулах (2) через значення похідної функції яку наближують).

${\displaystyle P'_{j}(t_{j})=f'(t_{j}),\qquad P'_{j}(t_{j-1})=f'(t_{j-1})\qquad (2)}$

Система з 4-х рівнянь

${\displaystyle \left[{\begin{array}{*{20}{c}}{{P_{j}}({t_{j}})=f({t_{j}})}\\{{P_{j}}({t_{j-1}})=f({t_{j-1}})}\\{{{P'}_{j}}({t_{j}})=f'({t_{j}})}\\{{{P'}_{j}}({t_{j-1}})=f'({t_{j-1}})}\\\end{array}}\right]\qquad (3)}$

дозволяє однозначно визначити 4 коефіцієнти полінома. Для полінома 5-ї степені ми повинні додатково накласти умову рівності 2-ї похідної на кінцях відрізка і т. д. Наведене вище показує, чому сплайн будують переважно з поліномів непарних степенів (з парною кількістю коефіцієнтів).

Для поліномів парних степенів при складанні системи (3) залишається невизначеною похідна в одному з кінців відрізка і умова рівності похідних (гладкості кривої) не виконуватиметься. Тому для полінома 2-ї степені неможливо досягти рівності першої похідної в точках стику, а для 4-ї степені другої похідної і так далі, виходячи з системи рівнянь (3). Для побудови сплайнів з парними степенями штучно додають додаткові умови щоб сформувати систему рівнянь подібну (3). Коли похідні полінома сплайна визначаються як відповідні похідні інтерпольованої функції, то сплайн є ермітовим.

${\displaystyle P_{j}^{(n)}({t_{j}})={f^{n}}({t_{j}}),\qquad P_{j}^{(n)}({f_{j-1}})={f^{n}}({t_{j-1}})\qquad (4)}$

Існують локальні методи побудови сплайнів Бесселя та Акіми, B — сплайни. В основному, коли йде мова про сплайни, то мають на увазі сплайни, побудовані з алгебраїчних поліномів. Саме до таких належить приведене вище визначення. Саме ці сплайни є найбільше вивченими. Проте сплайн може складатися з фрагментів функцій будь-якого класу. В розглянуто побудову таких сплайнів, та досліджуються їхні властивості. Автор не дає загального визначення побудованих сплайнів. Очевидно, що для довільних класів функцій з яких складається сплайн наведене на початку статті визначення не зовсім годиться. Якщо, наприклад, сплайн складається з відрізків експоненти то поняття дефекту сплайна втрачає зміст. Хоча кількість неперервних похідних залишиться важливою характеристикою. Побудова сплайна, фрагментами якого є розривні функції (раціональні функції, функції Паде) дещо виходить за рамки сплайнової ідеї, оскільки однією з основних переваг сплайнів є їхня гладкість. Якщо довільно розширювати такі конструкції, то стираються відмінності сплайнів від кускових функцій. Іншою перевагою сплайнів є ефективність обчислень. Надмірне ускладнення фрагментів суттєво знижує переваги сплайнів перед класичними функціями.

Для сплайнів є характерними такі ознаки: сплайн складається з фрагментів — функцій одного класу, які різняться лише своїми параметрами; на сусідні фрагменти в точках стикування накладаються певні умови, що зводяться до неперервності значень та деяких перших похідних. Сплайни — напрямок прикладної математики, що інтенсивно розвивається. В Internet міститься широка бібліографія щодо сплайнів (Spline Bibliography Database (SBD)) [ 22 квітня 2009 у Wayback Machine.].

Класифікація сплайнів

Як зазначалося вище, існує велика кількість конструкцій, які називають сплайнами. Тому зробимо спробу внести певну класифікацію в це різноманіття, маючи на меті виділити ті ознаки, які дозволять вибрати сплайни найпридатніші для конкретної прикладної задачі.

Вид фрагментів сплайна. Те що сплайн складається з фрагментів однакового виду є однією з ключових ознак, що відрізняє його від інших кускових функцій. Найвідоміші сплайни, що складаються з фрагментів — алгебраїчних поліномів не вище заданого степеня. Як правило це кубічні поліноми, або поліноми непарних степенів — лінійний, кубічний, п'ятого степеня. Вищі степені застосовують рідко, зважаючи на ускладнення розрахунків та складнощі описані в попередньому розділі. Основною їхньою перевагою є простота розрахунків та аналізу. Недоліком є те, що відносно мало реальних фізичних процесів відповідають цій залежності.

Експоненційні сплайни

Якщо гнучку металеву лінійку зафіксовану у вузлах натягнути, то розв'язком диференційного рівняння буде не алгебраїчний поліном, а експонента. Тому такі сплайни називають також напруженими. Експонента описує багато фізичних процесів в динамічних системах. Недоліком є труднощі розрахунку.

Тригонометричні сплайни

Сплайни, фрагменти яких описуються тригонометричними поліномами. Мають досить складні розрахункові вирази. Більше п'ятдесяти різноманітних за видом фрагментів сплайнів описано в роботах Попова Б. О. 

Раціональні сплайни та сплайни Паде

Їхньою особливістю є можливість розриву похідних на фрагментах, при неперервності у вузлах.

Ансер М. будує фракціональні сплайни, де фрагменти задані з допомогою Гама функції.

Доцільність застосування певного виду фрагментів ґрунтується на конкретних умовах задачі та обмеженнях реалізації. Як правило основними вимогами є досягнення заданої точності інтерполяції за прийнятних затрат часу та ресурсів на реалізацію. Вдалий вибір виду фрагментів, що відповідає характеру процесу дозволяє скоротити витрати.

Число фрагментів. Очевидно, що мінімальним числом фрагментів є один. Класичне визначення сплайна обмежує число фрагментів певним числом на скінченному відрізку. Проте можна будувати сплайни і з нескінченим числом фрагментів, а реально це методи і алгоритми котрі не потребують інформації про певну кількість фрагментів. Представником цих сплайнів є кардинальні, досліджені Шенбергом. Для побудови сплайнів з необмеженим числом фрагментів найкраще підходять локальні сплайни.

Ширина фрагментів. Варто виділити сплайни з рівною шириною фрагментів. Це дозволяє значно спростити розрахункові вирази і прискорити роботу алгоритмів та знизити витрати на реалізацію. Певного спрощення можна також досягти за рахунок застосування фрагментів з кратною шириною. Існують сплайни з нульовою шириною фрагментів (Де Бур). Це призводить до кратності вузлів і можливості наближувати сплайнами з нерозривними фрагментами розривні функції. Розрахункові вирази отримують в результаті граничних переходів. Сплайни можуть мати також фрагменти з нескінченною шириною. Ці фрагменти мають бути крайніми. Іноді це дозволяє природно задати крайові умови.

Умови стикування фрагментів. Ще одна важлива ознака, що вирізняє сплайни. Коли йде мова про сплайни, як правило, вважають що фрагменти стикуються гладко. Тобто забезпечується неперервність значень та першої похідної. Поняття дефекту сплайна пов'язане із числом неперервних похідних, що має функція-фрагмент певного виду та числом похідних, неперервність яких гарантована у вузлах. Експонента, синусоїда мають нескінчене число похідних. Для них це поняття не має змісту. Тому зручніше говорити прямо про число похідних, неперервність яких гарантована у вузлах сплайна. Практично мова йде про неперервність значень та першої, максимум — другої похідних. Розрив другої та вищих похідних візуально є непомітним, тому враховується рідко. Зрозуміло, що перша похідна в точках стику може задаватися по-різному. Найпоширеніші два прийоми. Значення першої похідної вибирається так, щоб забезпечити неперервність другої (глобальні кубічні сплайни мінімального дефекту). Перша похідна дорівнює першій похідній інтерпольованої функції (можливо наближено) в Ермітових сплайнах.

Крайові умови. Якщо сплайни мають обмежене число фрагментів, то природно в них відсутні крайні фрагменти праворуч та ліворуч. Тобто крайні вузли немає з чим стикувати. Винятком є лише періодичні сплайни, які мають природне продовження. Іноді природними називають крайові умови з нульовою похідною, хоча ніяких підстав вважати їх природнішими за інші немає. Якщо сплайн має фрагменти однакової ширини, вважаємо відсутні фрагменти тої ж ширини. Інший варіант це вважати відсутні фрагменти продовженими в нескінченність. Перевага такого підходу в можливості екстраполяції. Можна також вважати ширину фрагментів нульовою. Розрахункові вирази отримують граничними переходами. Якщо поглянути на крайові умови з точки зору формування сплайна з базисних функцій, то вони зводяться до продовження відповідних локальних базисних функцій. Ширина сусідніх фрагментів впливає на їхню форму. А просте обрізання часто призводить до осциляцій та зростання похибки на краях. Важливе значення крайові умови мають при обробці зображень та в задачах з екстраполяцією.

Додаткові обмеження. Вони частіше всього стосуються похідних у вузлах. Іноді вони випливають із фізики процесу. Наприклад, невід'ємність першої похідної при інтерполяції неспадної функції (закону розподілу). Інші умови: невід'ємність значень, рівність моментів, площ, умови нормування. Додаткові умови іноді спрощують аналіз властивостей сплайнів, але можуть серйозно ускладнювати побудову та затрати реалізації.

Сітка точок інтерполяції. Може суттєво впливати на ефективність розрахунків. Важливими є випадки рівномірної сітки та рівномірної сітки, з відстанню між точками кратною відстані між вузлами сплайна.

Локальні властивості базисних функцій. Сплайн можна представити як суму зважених базисних сплайнів. Суттєвою є ширина цих базисних функцій. Так, в глобальних сплайнах базисні сплайни ненульові на всьому відрізку інтерполяції. Хоча варто зауважити, що з певною точністю (достатньою для багатьох технічних розрахунків) їх можна вважати локальними. В локальних сплайнів ширина базисних функцій невелика (чотири фрагменти в кубічних ермітових сплайнів). Це суттєво впливає на ефективність розрахунків та затрати реалізації.

Форма представлення. Функції, що задають фрагменти сплайна, як правило, залежать від множини параметрів, завдяки яким вони змінюють свою форму. Значення параметрів на кожному із фрагментів індивідуальні. Ці параметри можуть задавати конкретний сплайн. Для поліноміальних сплайнів це поліноміальні коефіцієнти. Отже, сплайн можна представити множиною параметрів функцій на кожному з фрагментів. Назвемо це представлення пофрагментним. Таке представлення є наочним, часто має явний фізичний зміст. Але число параметрів є надмірним. Так, для кубічного сплайна необхідно мати 4*(r-1) параметри (r — число вузлів сплайна). Значно компактнішим є представлення сплайна у вигляді полінома, через базисні сплайн-функції у вигляді:

${\displaystyle S(x)=\sum \limits _{j=1}^{r}{{a_{j}}{B_{j}}(x)}}$,

де ${\displaystyle {B_{j}}(x)\,}$ — базисні сплайн-функції (як правило локальні), ${\displaystyle a_{j}\,}$ — числові коефіцієнти, що задають вагу базисних функцій при формуванні сплайна. Число параметрів, що задають сплайн рівне числу вузлів сплайна. Між параметрами функції на фрагменті та коефіцієнтами полінома-сплайна існує залежність, що дозволяє за одними коефіцієнтами знаходити інші, хоча формули можуть мати досить складний вигляд.

Зміст коефіцієнтів сплайна. Як зазначалося у попередньому пункті, зміст параметрів сплайна при пофрагментному представленні визначається типом функції. При поліноміальному представленні варто виділити випадок, коли коефіцієнти мають той самий фізичний зміст, що і вхідні дані. Тобто, коефіцієнти є значеннями сплайна у вузлах. Таку форму називатимемо Лагранжовою, за аналогією з поліномом Лагранжа. Зауважимо, що базисні сплайни цієї форми рівні одиниці в центральному вузлі і нулю у всіх інших.

Особливі сплайни

В ряді випадків розглядають функції які є близько до межі між сплайнами і звичайними функціями та сплайнами і кусковими функціями. Це:

1) сплайни, що складаються з двох фрагментів. Мають спрощений варіант побудови, але особливу увагу слід приділяти крайовим умовам;

2) Відрізково стала сплайн-функція не має неперервності навіть значень. Тривіальний варіант, що не має основної переваги сплайнів — гладкості. Так само, як і ламана має скоріше методичне значення для освоєння технології роботи зі сплайнами.

Див. також

• Крива Безьє
• Кубічний сплайн
• Кубічні сплайни Ерміта
• B-сплайн
• NURBS

Джерела

• Неперервне й гладке мінімаксне сплайн-наближення / П. С. Малачівський, В. В. Скопецький ; [відп. ред.] І. В. Сергієнко; НАН України, Ін-т кібернетики ім. В. М. Глушкова, Центр мат. моделювання Ін-ту приклад. пробл. механіки і математики ім. Я. С. Підстригача. – К. : Наук. думка, 2013. – 271 с. : табл. – (Проект "Наукова книга"). – Бібліогр.: с. 251-266 (278 назв). –
• Сплайн-функції та їхнє застосування : навч. посіб. / Б. П. Довгий, А. В. Ловейкін, Є. С. Вакал, Ю. Є. Вакал. – К. : Київський ун-т, 2017. – 120 с.
• Роджерс Д.,Адамс Дж. (2001). Математические основы машинной графики (вид. друге). Москва: Мир. с. 604 с. ISBN . {{}}: Cite має пустий невідомий параметр: |глава= ()
• I.Schoenberg (1946). Contribution to the problem of approximation of equidistant data by analytic functions. Quart.Appl.Math.,4. {{}}: Cite має пустий невідомий параметр: |глава= ()
• I.J. Schoenberg (1973). Cardinal spline interpolation. Philadelphia: PA:Society of Industrial and Applied Mathematics. {{}}: Cite має пустий невідомий параметр: |глава= ()
• Де Бор К. (1985). Практическое руководство по сплайнам. Москва: . с. 304. {{}}: Cite має пустий невідомий параметр: |глава= ()
• Корнейчук Н.П. (1984). Сплайны в теории приближения. Москва: Наука. с. 352. {{}}: Cite має пустий невідомий параметр: |глава= ()

Посилання

• spline bibliography [ 20 квітня 2009 у Wayback Machine.]
• Larry L. Schumaker [ 23 березня 2009 у Wayback Machine.]
• Carl de Boor [ 23 лютого 2009 у Wayback Machine.]
• Biomedical Imaging Group [ 16 квітня 2009 у Wayback Machine.]