Побудова кубічного сплайну. Кубічний інтерполяційний сплайн

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

Розглянемо найпоширеніший варіант сплайн-інтерполяції – інтерполяцію кубічними сплайнами.

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

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

де a i, b i, c i, d i- Коефіцієнти сплайну, що визначаються з додаткових умов; i = 1,2,3,....n- Номер сплайну.

Усього сплайнів на один менше, ніж точок інтерполяції. Інтерполяцію сплайнами можна назвати шматково-поліноміальною.

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

1. Рівність значень сплайнів та функції f(x)у вузлових точках - умови Лагранжа:

, . (6.10)

2. Безперервність першої та другої похідних від сплайнів у вузлах:

Крім перерахованих умов, слід додати умови на кінцях, тобто в точках x 0і x n. У загальному випадкуці умови залежать від конкретного завдання. Ми користуємося умовами вільних кінців сплайнів, тобто. поза інтервалом функція описується поліномом першого ступеня - прямою лінією:

, . (6.12)

Умови (6.10)-(6.12) дозволяють знайти коефіцієнти a i, b i, c i, d iвсіх nсплайнів. Їх значення виражаються такими формулами:

, (6.13)

де у перших трьох рівняннях i = 1,2,...n, а в третьому i = 2,3,..n;

h i = x i -x i -1 - i-й крок аргументу.

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

Спочатку вирішується система з n - 1 лінійних рівняньдля з i. Потім визначаються b iі d iза відомими коефіцієнтами з i, а iвідомо - це значення функції f(x)у вузлових точках. У кожне рівняння визначення з iвходить лише три невідомі з послідовними значеннями індексів c i - 1, c i, c i +1. Така матриця, що має відмінні від нуля лише елементи головної та двох сусідніх діагоналей, називається тридіагональні.

Програмну реалізацію розглянутого алгоритму наведено нижче (ПРОГРАМА 6.2). Наведено фрагмент, в якому розраховуються коефіцієнти сплайнів за вузловими значеннями функції, що інтерполується.

Для формування тридіагональної матриці Kc використано масив кроків аргументу h i. У процедурі Gaussрозраховується допоміжний масив cv, що має на 2 елементи менше, ніж масив с., так як з 0 і c n +1 відомі і дорівнюють нулю. При великому числірівнянь для розв'язання систем з тридіагональною матрицею застосовують метод прогонки, що є варіантом методу послідовних винятків. Результати розрахунків із використанням інтерполяції сплайнами наведено на рис.6.4. Як інтерполюваної функції було взято струм котушки електромагніта.

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

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

Криві та поверхні, що зустрічаються в практичні завдання, часто мають досить складну форму, що не допускає універсального аналітичного завданняв цілому за допомогою елементарних функцій. Тому їх збирають із порівняно простих гладких фрагментів - відрізків (кривих) або вирізків (поверхень), кожен з яких може бути цілком задовільно описаний за допомогою елементарних функцій однієї або двох змінних. При цьому цілком природно вимагати, щоб гладкі функції, які використовуються для побудови часткових кривих або поверхонь, мали схожу природу, наприклад, були б багаточленами однакового ступеня. А щоб крива або поверхня, що виходить в результаті, виявилася досить гладкою, необхідно бути особливо уважним у місцях стикування відповідних фрагментів. Ступінь багаточленів вибирається із простих геометричних міркувань і, як правило, невелика. Для гладкої зміни дотичної вздовж усієї складової кривої достатньо описувати стикувані криві за допомогою багаточленів третього ступеня кубічних багаточленів. Коефіцієнти таких многочленів завжди можна підібрати так, щоб кривизна відповідної складової кривої була безперервною. Кубічні сплайни, що виникають при вирішенні одновимірних завдань, можна пристосувати до заглиблення фрагментів складових поверхонь. І тут цілком природно з'являються бікубічні сплайни, що описуються за допомогою багаточленів третього ступеня кожної з двох змінних. Робота з такими сплайнами потребує значно більшого обсягу обчислень. Але правильно організований процесдозволить врахувати безперервно наростаючі можливості обчислювальної технікив максимального ступеня. Сплайн-функції Нехай на відрізку , тобто зауваження. Індекс (t) у чисел а вказує на те. що набір коефіцієнтів, яким визначається функція 5 (х), на кожному частковому відрізку Д свій. На кожному з відрізків Д1 сплайн 5(х) є многочленом ступеня р і визначається на цьому відрізку р + 1 коефіцієнтом. Усього часткових відрізків - те. Отже, щоб повністю визначити сплайн, необхідно знайти (р + 1)то чисел Умова) означає безперервність функції 5(ж) та її похідних у всіх внутрішніх вузлах сітки ш. Число таких вузлів m - 1. Тим самим, для відшукання коефіцієнтів всіх многочленів виходить р(т - 1) умов (рівнянь). Для повного визначеннясплайну не вистачає (умов (рівнянь). Вибір додаткових умов визначається характером розглянутої задачі, а іноді й просто - бажанням користувача. ТЕОРІЯ СПЛАЙНІВ приклади рішення Найчастіше розглядаються завдання інтерполяції та згладжування, коли потрібно побудувати той чи інший сплайн за заданим масивом точок на площині В Завданнях інтерполяції потрібно, щоб графік сплайну проходив через точки що накладає на його коефіцієнти m + 1 додаткових умов (рівнянь). а, 6] - граничних (крайових) умов.Можливість вибору різних граничних умов дозволяє будувати сплайни, що володіють різними властивостями.У задачах згладжування сплайн будують так, щоб його графік проходив поблизу точок (я "У") 1,... , т, а не через них, міру цієї близькості можна визначати по-різному, що призводить до значної різноманітності сплайнів, що згладжують. Описані можливості вибору при побудові сплайн-функцій далеко не вичерпують всього їхнього різноманіття. І якщо спочатку розглядалися лише кусково-поліноміальні сплайн-функції, то в міру розширення сфери їх додатків стали виникати сплайни, «склеєні» та з інших елементарних функцій. Інтерполяційні кубічні сплайни Постановка задач інтерполяції Нехай на відрізку [а, 6) задана сітка ш Розглянемо набір чисел Завдання. Побудувати гладку на відрізку (а, 6) функцію яка приймає у вузлах сітки про задані значення, тобто Зауваження. Сформульована задача інтерполяції полягає у відновленні гладкої функції, заданої таблично (рис. 2). різних рішень. Накладаючи на функцію, що конструюється додаткові умови, можна досягти необхідної однозначності. У додатках часто виникає необхідність наблизити функцію, задану аналітично, за допомогою функції з досить хорошими властивостями. Наприклад, у тих випадках, коли обчислення значень заданої функції /(х) у точках відрізка [а, 6] пов'язане зі значними труднощами та/або задана функція /(х) не має необхідної гладкості, зручно скористатися іншою функцією, яка досить добре наближала б задану функцію і була позбавлена ​​зазначених її недоліків. Завдання інтерполяції функції. Побудувати на відрізку [а, 6] гладку функцію а(х), що збігається у вузлах сітки ш с заданою функцією/ (Х). Визначення інтерполяційного кубічного сплайну Інтерполяційним кубічним сплайном S(x) на сітці ш називається функція, яка 1) на кожному з відрізків, є багаточленом третього ступеня, 2) двічі безперервно диференційована на відрізку [а, Ь], тобто належить класу С2 а, 6], і 3) задовольняє умовам На кожному з відрізків сплайн S(x) є багаточленом третього ступеня та визначається на цьому відрізку чотирма коефіцієнтами. Усього відрізків - т. Отже, щоб повністю визначити сплайн, необхідно знайти 4т чисел Умова означає безперервність функції S(x) та її похідних S"(x) і 5"(х) у всіх внутрішніх вузлах сітки ш. Число таких вузлів - m - 1. Тим самим, для відшукання коефіцієнтів всіх многочленів виходить ще 3 (m - 1) умов (рівнянь). Разом з умовами (2) виходять умови (рівняння). Граничні (крайові) умови Два умови задаються у вигляді обмежень на значення сплайна і/або його похідних на кінцях проміжку [а, 6]. При побудові інтерполяційного кубічного сплайну найчастіше використовуються крайові умови наступних чотирьох типів. A. Крайові умови 1-го типу. - наприкінці проміжку [а, Ь] задаються значення першої похідної шуканої функції. Б. Крайові умови 2-го типу. - на кінці проміжку (а, 6) задаються значення другої похідної шуканої функції. B. Крайові умови 3-го типу. називаються періодичними. Виконання цих умов природно вимагати в тих випадках, коли функція, що інтерполується, є періодичною з періодом Т = Ь-а. Г. Крайові умови 4-го типу. вимагають особливого коментарю. Коментар. У внутрішніх вузлах сепсі третя похідна функції S(x), взагалі, розривна. Однак кількість розривів третьої похідної можна зменшити за допомогою умов 4-го типу. У цьому випадку побудований сплайн тричі безперервно диференціюємо на проміжках Побудова інтерполяційного кубічного сплайну Опишемо спосіб обчислення коефіцієнтів кубічного сплайну, при якому число величин, що підлягають визначенню, дорівнює. На кожному з проміжків інтерполяційна сплайн-функція шукається в наступному виглядіТут ТЕОРІЯ СПЛАЙНІВ приклади рішення а числа є рішенням системи лінійних алгебраїчних рівнянь, Вид якої залежить від типу крайових умов. Для крайових умов 1-го і 2-го типів ця система має такий вигляд, де Коефіцієнти залежать від вибору крайових умов. Крайові умови 1-го типу: Крайові услоемв 2-го типу: У разі крайових умов 3-го типу система для визначення чисел записується так Число невідомих у останній системіі тп, оскільки зумови періодичності випливає, що по = пт. Для крайових умов 4-го типу система визначення чисел, має вигляд де По знайденому рішенню системи числа по і пт можна визначити з допомогою формул Важливе зауваження. Матриці всіх трьох лінійних алгебраїчних системє матрицями з діагональним переважним. Тамі матриці не вироджено, і тому кожна з цих систем має єдине рішення. Теорема. Інтерполяційний кубічний сплайн, що задовольняє умовам (2) та крайової умови одного з перерахованих чотирьох типів, існує і єдний. Таким чином, побудувати інтерполяційний кубічний сплайн - це знайти його коефіцієнти Коли коефіцієнти сплайну знайдені, значення сплайну S(x) у довільній точці відрізка [а, Ь] можна знайти г!о формулі (3). Однак для практичних обчислень більше підходить наступний алгоритм знаходження величини 5(ж). Нехай х 6 [х», Спочатку обчислюються величини А і В за формулами а потім знаходиться величина 5(ж): Застосування цього алгоритму істотно скорочує обчислювальні витрати на визначення величини Поради користувачеві певною міроюкерувати властивостями інтерполяційних сплайнів. А. Вибір граничних (крайових) умов. Вибір граничних умов є одним із центральних проблем при інтерполяції функций. Він набуває особливої ​​важливості в тому випадку, коли необхідно забезпечити високу точність апроксимації функції f(x) сплайном 5(ж) поблизу кінців відрізка [а, 6). Граничні значення помітно впливають на поведінку сплайна 5(ж) поблизу точок а і Ь, і цей вплив у міру віддалення від них швидко слабшає. Вибір граничних умов часто визначається наявністю додаткових відомостей щодо поведінки апроксимованої функції f(x). Якщо на кінцях відрізка (а, 6) відомі значення першої похідної f"(x), то природно скористатися крайовими умовами 1-го типу. Якщо на кінцях відрізка [а, 6] відомі значення другої похідної f"(x), то природно скористатися крайовими умовами 2-го типу. Якщо є можливість вибору між крайовими умовами 1-го та 2-го типів, то перевагу слід надати умовам 1-го типу. Якщо f(x) - періодична функція, то слід зупинитися на крайових умовах 3-го типу. Якщо ніякий додаткової інформаціїпро поведінку апроксимованої функції немає, часто використовують так звані природні граничні умови. крайові умови 1-го або 2-го типу, але не з точними значеннямивідповідних похідних, а з їх різницевими апроксимаціями. Точність такого підходу невисока. Практичний досвід розрахунків показує, що у ситуації найбільш доцільним є вибір граничних умов 4-го типу. Б. Вибір вузлів інтерполяції. Якщо третя похідна f""(x) функції терпітрозрив у деяких точках відрізка [а, Ь], то для поліпшення якості апроксимації ці точки слід включити до числа вузлів інтерполяції. Якщо розривна друга похідна /"(х), то для того, щоб уникнути осциляції сплайну поблизу точок розриву, необхідно вжити спеціальних заходів. Зазвичай вузли інтерполяції вибирають так, щоб точки розриву другої похідної потрапляли всередину проміжку \xif), такого, що. Величину а можна вибрати шляхом чисельного експерименту (часто досить покласти а = 0,01) Існує набір рецептів з подолання труднощів, що виникають при першій розривній похідної f "(x). Як один з найпростіших можна запропонувати такий: розбити відрізок апроксимації на проміжки, де похідна безперервна, і на кожному з цих проміжків побудувати сплайн. Вибір інтерполяційної функції (плюси та мінуси) Підхід 1-й. Інтерполяційний багаточлен Лагранжа За заданим масивом ТЕОРІЯ СПЛАЙНІВ приклади рішення (рис.3) інтерполяційний багаточлен Лагранжа визначається формулою Властивості інтерполяційного багаточлена Лагранжа доцільно розглядати з двох протилежних позицій, обговорюючи основні переваги окремо від недоліків. Основні переваги 1-го підходу: 1) графік інтерполяційного багаточлена Лагранжа проходить через кожну точку масиву; будь-якого порядку; 4) заданим масивом інтерполяційний багаточлен визначено однозначно. Основні недоліки 1-го підходу: 1) ступінь інтерполяційного багаточлена Лагранжа залежить від числа вузлів сітки, і чим більше це число, тим вище ступінь інтерполяційного багаточлена і, отже, тим більше потрібно обчислень, 2) зміна хоча б однієї точки в масиві вимагає повного перерахунку коефіцієнтів інтерполяційного багаточлена Лагранжа, 3) додавання нової точкив масив збільшує ступінь інтерполяційного багаточлена Лагранжа на одиницю і призводить до повного перерахунку його коефіцієнтів; 4) при необмеженому подрібненні сітки ступінь інтерполяційного багаточлена Лагранжа необмежено зростає. Поведінка інтерполяційного багаточлена Лагранжа при необмеженому подрібненні сітки взагалі потребує особливої ​​уваги. Коментарі А. Про наближення безперервної функціїбагаточлен. Відомо (Вейєрштрасс, 1885 рік), що будь-яка безперервна (а тим паче гладка) на відрізку функція може бути як завгодно добре наближена цьому відрізку многочленом. Опишемо цей факт мовою формул. Нехай f(x) – функція, безперервна на відрізку [а, 6]. Тоді для будь-якого е > 0 знайдеться такий многочлен Р„(х),що для будь-якого х із проміжку [а, 6] буде виконуватися нерівність (рис. 4) Зазначимо, що багаточленів навіть одного ступеня, що наближають функцію f(x) із зазначеною точністю існує нескінченно багато. Побудуємо на відрізку [а, 6] сітку w. Зрозуміло, що її вузли, взагалі кажучи, не збігаються з точками перетину графіків багаточлена Рп(х) та функції f(x) (рис. 5). Тому взятої сітки многочлен Рп(х) перестав бути інтерполяційним. При апроксимації безперервної функції інтерполяційним багаточленом Jla-гракжа його графік не тільки не повинен бути близьким графіку функції f(x) у кожній точці відрізка [а, Ь), але може ухилятися від цієї функції як завгодно сильно. Наведемо два приклади. Приклад 1 (Рунг, 1901). При необмеженому збільшенні числа вузлів функції на відрізку [-1, 1] виконується гранична рівність (рис.6) Приклад 2 (Бериштейн, 1912год). Послідовність інтерполяційних багаточленів Лагранжа, побудованих на рівномірних сітках шт для безперервної функції /(х) = |х| на відрізку зі зростанням числа вузлів т не прагне функції / (х) (рис.7). Підхід другий. Кусочно-лииейнм інтерполяція При відмові від гладкості функції, що інтерполюється, співвідношення між числом переваг і числом недоліків можна помітно змінити в бік перших. Побудуємо шматково-лінійну функцію шляхом послідовного з'єднанняточок (xit у,) прямолінійними відрізками (рис. 8). Основні переваги 2-го підходу: 1) графік кусково-лінійної функції проходить через кожну точку масиву; 2) конструйована функція легко описується (число відповідних коефіцієнтів відповідних) лінійних функційдля сітки (1) дорівнює 2т); 3) заданим масивом побудована функція визначена однозначно; 4) ступінь багаточленів, що використовуються для опису інтерполяційної функції, не залежить від числа вузлів сітки (рівна 1); чисел (коефіцієнтів двох прямолінійних ланок, що виходять з нової точки); 6) додавання додаткової точки до масиву вимагає обчислення чотирьох коефіцієнтів. Шматково-лінійна функція досить добре поводиться і при подрібненні сітки. я Основний недолік 2-го підходу: апроксимуюча шматково-лінійна функціяне є гладкою: перші вироблені терплять розрив у вузлах сітки (вухах інтерполяції). Підхід третій. Сплайн-інтерполяція Запропоновані підходи можна об'єднати так, щоб кількість перерахованих переваг обох підходів збереглася при одночасному зменшенні недоліків. Це можна зробити шляхом побудови гладкої інтерполяційної сплайн-функції ступеня. Основні переваги 3-го підходу: 1) графік побудованої функції проходить через кожну точку масиву; багаточленів не залежить від числа вузлів сітки і, отже, не змінюється при його збільшенні; 5) побудована функція має безперервні похідні до порядку р - 1 включно; 6) побудована функція має гарні апроксимаційні властивості. Коротка довідка. Запропонована назва - сплайн - не є випадковим - введені нами гладкі шматково-поліноміальні функції і креслярські сплайни тісно пов'язані. Розглянемо гнучку ідеально тонку лінійку, що проходить через розташовані на площині (х, у) опорні точкимасиву. Відповідно до закону Бернуллі-Ейлера лінеаризоване рівняння вигнутої лінійки має вигляд де S(x) - вигин, М(х) - змінний лінійно від опори до опори згинальний момент, Е1 - жорсткість лінійки. Функція S(x), що описує формулі нейки, є многочленом третього ступеня між кожним і двома сусідніми точкамимасиву (опорами) і двічі безперервно диференційована по всьому проміжку (а, 6). Коментар. 06 інтерполюванні безперервної функції На відміну від інтерполяційних багаточленів Лагранжа, послідовність інтерполяційних кубічних сплайнів на рівномірній сітці завжди сходить до безперервної інтерполюваної функції, причому з поліпшенням диференціальних властивостей цієї функції швидкість збіжності підвищується. приклад. Для функції кубічний сплайн на сітці з числом вузлів m = 6 дає похибку апроксимації того ж порядку, що і інтерполяційний багаточлен Ls(z), а на сітці з числом вузлів m = 21 ця похибка настільки мала, що в масштабі звичайного книжкового малюнка просто не може бути показана (рис.10) (інтерполяційний многочлен 1>2о(г) дає в цьому випадку похибку близько 10 000 Ж). Властивості імперопольського кубічного сплайну А. Алпроксимаційні властивості кубічного сплайну. Апроксимаційні властивості інтерполяційного сплайну залежать від гладкості функції f(x) - чим вище гладкість функції, що інтерполюється, тим вище порядок апроксимації і при подрібненні сітки тим вище швидкість збіжності. Якщо функція f(x), що інтерполується, безперервна на відрізку Якщо інтерполована функція f(x) має на відрізку [а, 6] безперервну першу похідну, тобто інтерполяційний сплайн, що задовольняє граничним умовам 1-го або 3-го типу, то при h О маємо У цьому випадку не тільки сплайн сходиться до функції, що інтерполується, але і похідна сплайна сходиться до похідної цієї функції. Якщо сплайн S(x) апроксимує на відрізку [а, Ь] функцію f(x), яке перша і друга похідні апроксимують відповідно функції Б. Екстремальна властивість кубічного сплайну. Інтерполяційний кубічний сплайн має ще один корисною властивістю. Розглянемо наступний приклад. ример. Побудувати функцію/(х), що мінімізує функціонал на класі функцій із простору С2, графіки яких проходять через точки масиву Серед усіх функцій, що проходять через опорні точки (х;, /(х,)) і належать зазначеному простору, саме кубічний сплайн 5( х), що задовольняє крайовим умовам, доставляє Екстремум (мінімум) функціоналу Зауваження 1. Часто саме цю екстремальну властивість беруть як визначення інтерполяційного кубічного сплайну. Примітка 2. Цікаво відзначити, що інтерполяційний кубічний сплайн має описану вище екстремальну властивість на дуже широкому класі функцій, а саме, на класі |о, 5]. 1.2. Згладжуючі кубічні сплайни Про постановку задачі згладжування Нехай задані сітка і набір чисел Коментар до вихідних даних На практиці часто доводиться мати справу з випадком, коли значення у масиві задані з деякою похибкою. Фактично це означає, що для кожного зазначений інтервал і будь-яке число з цього інтервалу може бути взято як значення у . Величини у, зручно інтерпретувати, наприклад, як результати вимірювань деякої функції у(х) при заданих значенняхзмінної х, що містять випадкову похибку. При вирішенні задачі відновлення функції за такими її «експериментальними» значеннями навряд чи доцільно використовувати інтерполяцію, оскільки інтерполяційна функція буде слухняно відтворювати химерні осциляції, обумовлені випадковою компонентою в масиві (у,). Більш природним є підхід, заснований на процедурі згладжування, яка покликана якось зменшити елемент випадковості в результаті вимірювань. Зазвичай у таких завданнях потрібно знайти функцію, значення якої при х = ж, * = 0, 1,.... т, потрапляли б у відповідні інтервали і яка мала б, крім того, досить хороші властивості. Наприклад, мала б безперервні перші і другі похідні, або її графік був би не дуже викривлений, тобто не мав би сильних осциляцій. Завдання подібного роду виникає і тоді, коли по заданому (точно) масиву потрібно побудувати функцію, яка проходила б не через задані точки, а поблизу них і до того ж змінювалася досить плавно. Інакше кажучи, потрібна функція хіба що згладжувала заданий масив, а чи не интерполировала його. Нехай задані сітка ш і два набори чисел ТЕОРІЯ СПЛАЙНІВ приклади розв'язання Завдання. Побудувати гладку на відрізку [а, А] функцію, значення якої у вузлах сітки і відрізнялися від чисел у, - на задані величини -Зшочтіо. Сформульована задача згладжування полягає ввідновлення гладкої функції, заданої таблично. Зрозуміло, що таке завдання має багато різних рішень. Накладаючи на функцію, що конструюється, додаткові умови, можна домогтися необхідної однозначності. Визначення кубічного сплайну, що згладжує Згладжуючим кубічним сплайном S(x) на сітці ш називається функція, яка 1) на кожному з відрізків являє собою багаточлен третього ступеня, 2) двічі безперервно диференційована на відрізку [а, 6], тобто належить класу С2 [а , Ь], 3) доставляє мінімум функціоналу де - задані числа 4) задовольняє граничним умовам одного з трьох наведених нижче типів. Граничні (крайові) умови Граничні умови задаються як обмежень на значення сплайна та його похідних у граничних вузлах сітки ш. А. Граничні умови 1-го типу. - Наприкінці проміжку [а, Ь) задаються значення першої похідної шуканої функції. Кордонні умови 2-го типу. - другі похідні шуканої функції на кінцях проміжку (а, Ь) дорівнюють нулю. В. Граничні умови 3-го типу. називаються періодичними. Теорема. типів, визначений однозначно Визначення: Кубічний сплайн, що мінімізує функціонал J(f) і задовольняє граничним умовам i-готипу, називається згладжуючим сплайном i-готипу. У цьому відрізку чотирма коефіцієнтами.Усього відрізків - т. Значить, для того, щоб повністю визначати сплайн, необхідно знайти 4т чисел Умова означає безперервність функції 5(аг) і се похідних у всіх внутрішніх вузлах сітки о. Тим самим, для відисивнення коефіцієнтів всіх багаточленів виходить 3 (m - 1) умов (рівнянь). функція шукається в такому вигляді Тут а числа і є рішенням системи лінійних алгебраїчних рівнянь, вид якої залежить від типу крайових умов. Опишемо спочатку, як перебувають величини п*. Для крайових умов 1-го та 2-го типів система лінійних рівнянь для визначення величин Hi записується в наступному вигляді де відомі числа). Коефіцієнти залежить від вибору граничних умов. Граничні умови 1-го типу: Граничні умови 2-го типу: У разі граничних умов 3-го типу система для визначення чисел записується так: причому всі коефіцієнти обчислюються за формулами (5) (величини з індексами к і т + к вважають я рівними : Важливо* зауваження Матриці систем не вироджені і тому кожна з цих систем має єдине рішення Якщо числа п, - знайдені, то величини легко визначаються за формулами де У разі періодичних граничних умов у функціонал (4), дозволяєте певною мірою управляти властивостями сплайнів, що згладжують, якщо все і згладжуючий сплайн виявляється інтерполяційним.Це, зокрема, означає, що чим точніше задані величини, тим менше дошки повинні бути відповідні вагові коефіцієнти. пройшов через точку (х^, Ук), то відповідний ним у ваговий множник р \ слід поломити рівним нулю. Тоді природно вимагати, щоб сплайн, що згладжує, задовольняв умові або, що те ж, У найпростішому випадку вагові коефіцієнти pi можна задати, наприклад, форму-де з - деяка досить мала постійна. Однак такий вибір ваг р, не дозволяє використовувати «коридор», обумовлений похибками величин у,-. Більш раціональний, але й більш трудомісткий алгоритм визначення величин р може виглядати наступним чином. Якщо на fc-й ітерації величини знайдені, то вважають де е - мале число, яке вибирається експериментально з урахуванням розрядної сітки комп'ютера, значень Д, і точності розв'язання системи лінійних рівнянь алгебри. Якщо fc-й ітерації в точці я, порушилася умова (6), то остання формула забезпечить зменшення відповідного вагового коефіцієнта р,. Якщо ж то на наступній ітерації збільшення р, призводить до більш повному використанню «коридору» (6) і, в кінцевому рахунку, сплайну, що більш плавно змінюється. Дещо теорії А. Обґрунтування формул для обчислення коефіцієнтів інтерполяційного кубічного сплайну. Введемо позначення де m, - невідомі поки що величини. Їх число дорівнює m + 1. Сплайн, записаний у формі, де задовольняє умовам інтерполяції і безперервний на всьому проміжку [а, Ь\: поклавши у формулі, отримаємо відповідно. Крім того, він має на проміжку [а, 6] безперервну першу похідну: продиференціювавши співвідношення (7) і поклавши, отримаємо соот-. ственно. Покажемо, що числа т можна вибрати так, щоб сплайн-функція (7) мала на відрізку [а, 6] безперервну другу похідну. Обчислимо на проміжку другу похідну сплайну: У точці х, - 0 (при t = 1) маємо Обчислимо на проміжку другу похідну сплайну У точці маємо З умови безперервності другої похідної у внутрішніх вузлах сітки а; отримуємо m - 1 співвідношення де Додаючи до цих т - 1 рівнянь ще два, що випливають з крайових умов, отримуємо систему з m + 1 лінійного рівня алгебри з т + I невідомої miy i = 0, 1. ... , m. Система рівнянь для обчислення величин гщ у разі крайових умов 1-го та 2-го типів має вигляд де (крайові умови 1-го типу), (крайові умови 2-го типу). Для періодичних крайових умов (крайові умови 3-го типу) сітку про; подовжують ще на один вузол і вважають тоді система для визначення величин го* матиме вигляд Для того щоб отримати систему рівнянь для визначення чисел го, у разі крайових умов 4-го типу, знайдемо на відрізку [ третю похідну сплайну (7) і вимагатимемо її безперервності у другому та (го - !)-му вузлах сітки. Маємо З останніх двох співвідношень отримуємо відсутні два рівняння, що відповідають крайовим умовам 4-го типу: Виключаючи з рівнянь невідоме гоо, а з рівнянь невідоме пц, в результаті отримаємо систему рівнянь Зазначимо, що кількість невідомих у цій системі дорівнює го - I. 6. Обгрунтування формул дм обчислення юефііє хто згладжує субічес сплайну. Введемо позначення де Zi та nj - невідомі поки що величини. Їх число дорівнює 2т + 2. Сплайн-функція, записана у формі безперервна на всьому проміжку (а, 6]: поклавши в цій формулі, отримаємо відповідно Покажемо, що числа z, і п можна обрати так, щоб сплайн, записаний у формі ( 8), мав на проміжку [а, 6] безперервну першу похідну. У точці маємо З умови безперервності першою виробницею сплайну у внутрішніх вузлах сітки і --> отримуємо m - 1 співвідношення Цей зв'язок зручно записати в матричній формі. Тут використані наступні позначення. співвідношення (8) і поклавши, отримаємо відповідно Еше олю матричне співвідношення виходить із умови мінімуму функціоналу (4). Маємо Два останні матричні рівністі можна розглядати як лінійну систему 2т+2 лінійних рівнянь алгебри щодо 2т + 2 невідомих. Замінюючи в першій рівності стовпець його виразом, отриманим із співвідношення (9), приходимо до матричного рівняння ТЕОРІЯ СПЛАЙНІВ приклади рішення для визначення стовпця М. Це рівняння має єдине рішення внаслідок того, що матриця A + 6HRH7 завжди невироджена. Знайшовшого, ми легко визначаємо м. Еамсшині. Елементи трелдмаголальних матриць А і Н визначають лише параметрами сітки і (сс кроками hi) і не залежать від величин у ^. Лінійний простір кубічних сплайн-функцій Безліч кубічних сплайнів, побудованих на відрізку [а, 6) по сіті wcra+l вузлом, є лінійним просторомрозмірності т + 3: 1) сума двох кубічних сплайнів, побудованих по сітці і>, та добуток кубічного сплайну, побудованого по сітці та>, на довільне числотаємніше є кубічними сплайнами, побудованими по цій сітці, 2) будь-який кубічний сплайн, побудований по сітці і з вузла, повністю визначається т + 1 значенням величин у цих вузлах і двома граничними умовами - всього то + 3 параметрами. Вибравши в цьому просторі базис, що складається з m + 3 лінійно незалежних сплайнів, ми можемо записати довільний кубічний сплайн а(х) у вигляді їхньої лінійної комбінації причому єдиним чином. Зауваження. Подібне завдання сплайн широко поширене в обчислювальній практиці. Особливо зручним є базнс, що складається з так званих кубічних сплайнів (базових, або фундаментальних, сплайнів). Застосування Д-сплайн дозволяє істотно знизити вимоги до обсягу пам'яті комп'ютера. Л-сплайн. В-сплайномнульового ступеня, побудованим на числовій прямій по сітці ш, називається функція вила В-сплайн ступеня до ^I, побудований на числовій прямій по сітці іг, визначається за допомогою рекурентної формули Графіки В-сплайнів першої В,-1"(ж) і другий в\7\х) ступенів представлені на рис.11 і 12 відповідно. довільного ступеняможе бути відмінний від нуля тільки на деякому відрізку (визначуваному до + 2 вузлами). Кубічні В-сплайн зручніше нумерувати так, щоб сплайн В,-3 * (я) був відмінний від нуля на відрізку яг, - +2]. Наведемо формулу для кубічного сплайну третього ступеня для випадку рівномірної сітки(З кроком Л). Маємо в інших випадках. Типовий графік кубічного В-сплайнупредставлений на рис. 13. Позиками*. функція а) двічі безперервно диференційована на відрізку тобто належать класу С2[а, »), до б) відмінна від нуля тільки на чотирьох послідовних відрізках m + 3 кубічних В-сплайнів: Це сімейство утворює базис у просторі кубічних сплайнів на відрізку (а, Ь). , може бути представлений на цьому відрізку у вигляді лінійної комбінації Умовами задачі коефіцієнти ft, цього розкладання визначаються однозначно. інтерполяцій з граничними умовами першого роду), ці коефіцієнти обчислюються із системи наступного виду. величин б-i&m+i виходить лінійна система з невідомими 5q, ... , Ьт і трьох діаюнальної матрицею. Умова забезпечує діагональне переважання і, отже, можливість застосування методу прогонки для її вирішення. 3ММЧМЮ 1. Лінійні системианалогічного виду виникають ЛРН розгляді та інших завдань інтерполяції. Зммчнм* 2. Порівняно з алгоритмами, описаними у розділі 1.1, застосування Я-сплайн в * завданнях інтерполяції дозволяє зменшити* обсяг збереженої інформації, тобто суттєво знизити вимоги до обсягу пам'яті комп'ютера, хоч і призводить до збільшення кількості операцій. Побудова сплайнових кривих за допомогою сплайн-функцій Вище розглядалися масиви, точки яких були занумеровані так, що їх абсциси утворювали послідовність, що строго зростала. Наприклад, випадок, зображений на рис. 14, коли у різних точокмасиву однакові абсциси, що не допускався. Це визначало і вибір класу апроксимуючих кривих (трафіки функцій), і спосіб їх побудови. Однак запропонований вище метод дозволяє досить успішно будувати інтерполяційну криву і в загальному випадку, коли нумерація точок масиву та їх розташування на площині, як правило, не пов'язані (рис. 15). Більше того, ставлячи завдання побудови інтерполяційної кривої, можна вважати заданий масив непоганим, тобто Ясно, що для вирішення цієї спільного завданнянеобхідно істотно розширити клас допустимих кривих, включивши в нього і замкнуті криві, і криві, що мають точки самоперетину, і просторові криві. Такі криві зручно описувати за допомогою параметричних рівняньПотрібний. додатково, щоб функції мали достатню гладкість, наприклад, належали класу С1 [а, /0] або класу Для відшукання параметричних рівнянь кривої, що послідовно проходить через всі точки масиву, надходять таким чином. 1-й крок. На довільно взятому відрізку , i= 1, 2,…, N,рішення шукатимемо у вигляді полінома третього ступеня:

S i(x)=a i +b i(x–x i)+c i(x–x i) 2 /2+d i(x–x i) 3 /6

Невідомі коефіцієнти a i , b i , c i , d i , i= 1, 2,..., N,знаходимо з:

Умов інтерполяції: S i(x i)=f i , i= 1, 2,..., N;S 1 (x 0)=f 0 ,

Безперервності функції S i(x i– 1 )=S i– 1 (x i –1), i= 2, 3,..., N,

Безперервності першої та другої похідної:

S/i(x i– 1)=S/i- 1 (x i –1), S // i(x i –1)=S // i –1 (x i –1), i= 2, 3,..., N.

Враховуючи, що для визначення 4 Nневідомих отримуємо систему 4 N-2 рівнянь:

a i = f i , i = 1, 2,..., N,

b i h i - c i h i 2 /2+ d i h i 3 /6=f i - f i –1 , i= 1, 2,..., N,

b i – b i–1 = c i h i – d i h i 2 /2, i= 2, 3,..., N,

d i h i = c i – c i– 1 , i= 2, 3,..., N.

де h i = x i - x i - 1. Два рівняння, що бракують, виводяться з додаткових умов: S //(a)=S //(b)=0. Можна показати, що у цьому . Із системи можна виключити невідомі b i , d i ,отримавши систему N+ 1 лінійних рівнянь (СЛАУ) визначення коефіцієнтів c i:

c 0 = 0, c N = 0,

h i c i –1 + 2(h i +h i +1)c i +h i +1 c i +1 = 6 , i= 1, 2,…, N–1. (1)

Після цього обчислюються коефіцієнти b i , d i:

, i= 1, 2,..., N. (2)

У разі постійної сітки h i = hця система рівнянь спрощується.

Ця CЛАУ має тридіагональну матрицю і вирішується методом прогонки.

Коефіцієнти визначаються з формул:

Для обчислення значення S(x) у довільній точці відрізка z∈[a, b] необхідно вирішити систему рівнянь на коефіцієнти c i , i= 1,2,…, N–1, потім знайти всі коефіцієнти b i, d i.Далі необхідно визначити, на який інтервал [ x i 0, x i 0–1 ] потрапляє ця точка, і знаючи номер i 0 ,обчислити значення сплайну та його похідних у точці z

S(z)=a i 0 +b i 0 (z–x i 0)+c i 0 (z–x i 0) 2 /2+d i 0 (z–x i 0) 3 /6

S/(z)=b i 0 +c i 0 (z–x i 0)+d i 0 (z–x i 0) 2 /2, S //(z)=c i 0 +d i 0 (z–x i 0).

Потрібно обчислити значення функції у точках 0.25 та 0.8, використовуючи сплайн – інтерполяцію.

У разі: h i =1/4, .

Випишемо систему рівнянь для визначення:

Вирішуючи цю систему лінійних рівнянь, отримаємо: .

Розглянемо точку 0.25, що належить першому відрізку, тобто. . Отже, отримаємо,

Розглянемо точку 0.8, що належить четвертому відрізку, тобто. .

Отже,

Глобальна інтерполяція

В разі глобальної інтерполяціїзнаходиться єдиний поліном на всьому інтервалі [ a, b], тобто. будується поліном, який використовується для інтерполяції функції f(x) по всьому інтервалі зміни аргументу x. Шукатимемо інтерполюючу функцію у вигляді полінома (багаточлена) mступеня P m(x)=a 0 +a 1 x+a 2 x 2 +a 3 x 3 +…+a m x m.Яким має бути ступінь багаточлена, щоб задовольнити всі умови інтерполяції? Припустимо, що задані дві точки: ( x 0 , f 0) та ( x 1 , f 1), тобто. N=1. Через це можна провести єдину пряму, тобто. інтерполюючою функцією буде поліном першого ступеня P 1 (x)=a 0 +a 1 x.Через три точки (N=2) можна провести параболу P 2 (x)=a 0 +a 1 x+a 2 x 2 і т.д. Розмірковуючи таким способом, можна припустити, що поліном повинен мати ступінь N .

Для того щоб довести це, випишемо систему рівнянь на коефіцієнти. Рівняння системи являють собою умови інтерполяції при кожному x=x i:

Ця система є лінійною щодо шуканих коефіцієнтів a 0 , a 1 , a 2 , …,a N.Відомо, що СЛАУ має рішення, якщо її визначник відмінний від нуля. Визначник цієї системи

носить ім'я визначника Вандермонда. З курсу математичного аналізу відомо, що він відмінний від нуля, якщо x k≠x m(Тобто всі вузли інтерполяції різні). Таким чином доведено, що система має рішення.

Ми показали, що для знаходження коефіцієнтів
a 0 , a 1 , a 2 , …,a Nтреба вирішити СЛАУ, що є складним завданням. Але є інший спосіб побудови полінома N-й ступеня, який не вимагає вирішення такої системи.

Поліном Лагранжа

Рішення шукаємо у вигляді , де l i(z) – базисні поліноми N-й ступеня, для яких виконується умова: . Переконаємося в тому, що якщо такі поліноми збудовані, то L N (x)задовольнятиме умовам інтерполяції:

Як побудувати базисні поліноми? Визначимо

, i= 0, 1,..., N.

Легко зрозуміти, що

Функція l i(z) є поліномом Nступеня від zта для неї виконуються умови "базисності":

0, i≠k;, тобто. k=1,…,i-1 або k=i+1,…,N.

Таким чином, нам вдалося вирішити задачу про побудову інтерполюючого полінома N-шого ступеня, і для цього не потрібно вирішувати СЛАУ. Поліном Лагранжа можна записати у вигляді компактної формули: . Похибка цієї формули можна оцінити, якщо вихідна функція g(x) має похідні до N+ 1 порядку:

.

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

Розглянемо окремі випадки. Нехай N = 1, тобто. задані значення функції лише у двох точках. Тоді базові поліноми мають вигляд:

, тобто. отримуємо формули шматково-лінійної інтерполяції.

Нехай N = 2. Тоді:

В результаті ми отримали формули так званої квадратичної чи параболічної інтерполяції.

Приклад:Задані значення певної функції:

Потрібно знайти значення функції при z= 1, використовуючи інтерполяційний поліном Лгранжа. Для цього випадку N=3, тобто. Полін Лагранжа має третій порядок. Обчислимо значення базисних поліномів при z=1:

Підбір емпіричних формул

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

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

Для практики важливим є випадок апроксимації функції многочленами, тобто. .

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

Метод найменших квадратів

Нехай для вихідних даних x i , f i , i = 1,…,N (нумерацію краще починати з одиниці),обраний вид емпіричної залежності: з невідомими коефіцієнтами. Запишемо суму квадратів відхилень між обчисленими за емпіричною формулою та заданими дослідними даними:

Параметри знаходимо з умови мінімуму функції . У цьому полягає Метод найменших квадратів (МНК).

Відомо, що в точці мінімуму всі приватні похідні відрівнюють нулю:

(1)

Розглянемо застосування МНК для окремого випадку, що широко використовується на практиці. Як емпіричну функцію розглянемо поліном

Формула (1) для визначення суми квадратів відхилень набуде вигляду:

Обчислимо похідні:

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

Нехай на задана безперервна функція f(x). Введемо сітку

і позначимо f i=f(x i), i=0,1,N .

Сплайном, що відповідає даній функції f(x) і даним вузлам, називається функція S(x), що задовольняє наступним умовам:

1. На кожному сегменті , i=1,2,N , функція S(x) є багаточленом третього ступеня;

2. Функція S(x), а також її перша та друга похідні
безперервні на ;

Остання умова називається умовою інтерполювання, а сплайн, який визначається умовами 1)-3), називається також інтерполяційним кубічним сплайном

Доведемо існування та єдиність сплайну, що визначається перерахованими умовами. Наведений нижче доказ містить спосіб побудови сплайна.

У проміжку між парою сусідніх вузлів інтерполяційна функція є багаточленом 3-го ступеня, який зручно записати у вигляді:

Коефіцієнти многочлена визначають з умов вузлах. Він повинен набувати табличних значень:

(1)

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

(2)

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

3)

Дві умови, які бракують, зазвичай отримують з природного припущення про нульову кривизну графіка на кінцях:

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

Рівняння (1-4) утворюють систему лінійних рівнянь визначення 4N невідомих коефіцієнтів. Цю систему можна вирішити шляхом виключення Гауса, але вигідніше привести її до спеціального вигляду.

Рівняння (1) дає відразу всі коефіцієнти а i.З рівнянь (3) та (4)

(5)

Підставимо (5) в (1), одночасно виключаючи аi = fi -1 , Отримаємо:

(6)

Виключаючи тепер (3) b i та b i +1 по (6) та d iпо (5), отримуємо систему рівнянь для з i:

Матриця цієї системи 3-х діагональна. Такі системи економно вирішуються шляхом прогонки.

З огляду на діагонального переважання система має єдине рішення.

Після перебування з iвизначаються a i , b iі d iта визначається вид кубічних багаточленів (сплайнів) на кожному відрізку.

Таким чином, доведено, що існує єдиний кубічний сплайн, який визначається умовами 1)-3) та граничними умовами

Зауважимо, що можна розглядати інші граничні умови.

Можна розглянути і більш загальне завдання інтерполяції функції сплайн - багаточлен n-ого ступеня

,

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

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

ЛЕКЦІЯ №14

ЛІКАРСЬКЕ ІНТЕГРУВАННЯ

ПРОСТІ КВАДРАТУРНІ ФОРМУЛИ

Загальна формула прямокутників

1. Квадратурна формула лівих прямокутників.

2. Формула правих прямокутників

3. Квадратурна формула середніх прямокутників

Розрахунок похибки формул чисельного інтегрування.

Нехай h>0 досить мало, х 0 =0.

Розкладемо функцію в ряд Тейлора на околиці х 0 =0. :

Локальна похибка для малого відрізка h -

, тобто

Властивість адитивності

- Похибка на відрізку.

Квадратурні формули Ньютона-Котеса

Якщо багаточлен n - ступеня, то

Це квадратурні формули інтерполяційного типу. Тут С до - Коефіцієнти Котесу

Безрозмірні формули.

ПОТОЧКОВИЙ ОПИС ПОВЕРХНЬ.

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

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

приклад: Ділянки ґрунту на інших планетах, форми небесних тіл, інформація про які отримана в результаті супутникових зйомок. Мікрооб'єкти зняті за допомогою електронних мікроскопів.

Вихідна інформація про поточечно описані об'єкти подається у вигляді матриці тривимірних координат точок.

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

o моделювання кривих;

o апроксимації даних за допомогою кривих;

o виконання функціональних апроксимацій;

o розв'язання функціональних рівнянь.

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

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

1) Функція повинна проходити через усі точки: , ;

2) Функція має бути двічі безперервно диференційована, тобто мати безперервну другу похідну по всьому відрізку .

На кожному з відрізків, будемо шукати нашу функцію у вигляді полінома третього ступеня:

.

Сплайнова функція

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

Перейдемо до складнішого випадку – завдання кривих у тривимірному просторі. У разі функціонального завдання кривої можливі багатозначності у разі самоперетинів та незручності при значеннях похідних рівних. Зважаючи на це, шукатимемо функцію в параметричному вигляді. Нехай - незалежний параметр, такий, що . Кубічним параметричним сплайном назвемо таку систему рівнянь:

Координати точок на кривій описуються вектором , а три похідні задають координати відповідного вектора дотику в точці. Наприклад, для координати:

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

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

Перепишемо вираз для у векторному вигляді:

.

Позначимо вектор рядок і вектор стовпець коефіцієнтів, тоді.

З (*) випливає, що , . Для дотичних ,

Звідси отримуємо векторно-матричне рівняння:

.

Ця система вирішується щодо знаходженням зворотної матриці розміром.

.

Тут – ермітова матриця, – геометричний вектор Ерміта. Підставимо вираз для знаходження: . Аналогічно інших координат: , .