Природний кубічний сплайн. Кубічні сплайни

Нехай на задана безперервна функція 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 - ступеня, то

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

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

І вже майже рік з того моменту, як спала на думку ідея для другої. В силу багатьох обставин (насамперед – лінощів і забудькуватості), ця ідея так і не була реалізована раніше, але зараз я зібрався, написав весь цей матеріал і готовий представити його вашій увазі.

Почну з невеликої вступної. Будучи студентом 4-го, на той момент курсу бакалаврату, я вивчав курс « Комп'ютерна графіка». Багато там було різних цікавих (і не дуже) завдань, але одне просто особливо запало мені в душу: інтерполяція кубічними сплайнами із заданими першими похідними на кінцях інтервалу. Користувач повинен був ставити значення перших похідних, а програма - рахувати та виводити на екран інтерполяційну криву. Особливість і основна складність завдання полягає в тому, що задаються саме перші похідні, а не другі як у класичній постановці сплайн-інтерполяції.
Як я її вирішував, і до чого воно зрештою прийшло, я якраз і викладу у цій статті. І так, якщо за описом завдання ви не зрозуміли ні в чому її зміст, ні в чому складність, не переживайте, все це я також намагатимуся розкрити. Тож поїхали.

А, ні, зачекайте один момент. Ось вам два числових ряди:
a) 2, 4, 6, 8, ?
b) 1, 3, ? , 7, 9

Які числа мають стояти дома запитань і чому? Ви справді впевнені у своїй відповіді?

Інтерполяція

Інтерполяція, інтерполювання (від латів. inter-polis – «розгладжений, підновлений, оновлений; перетворений») – у обчислювальній математиці спосіб знаходження проміжних значень величини за наявним дискретним набором відомих значень. (с) Вікіпедія

Слід розуміти, що неможливість постійного спостереження за відповідним параметром – це зазвичай будь-яке технологічне обмеження. З розвитком техніки таких ситуацій стає дедалі менше. Із сучасних завдань такого плану – траєкторія руху, наприклад, марсоходу. Підтримувати безперервний сеанс зв'язку (поки що) все ще неможливо, а контролювати його переміщення і малювати красиві траєкторії хочеться. Виходить, що конкретні координати можна дізнатися тільки в ті моменти, коли зв'язок все-таки налагоджений, а траєкторію цілком доводиться відновлювати за отриманими таким чином іноді точками.
Інший варіант застосування інтерполяції. Деякі сучасні телевізори показують зображення з частотою оновлення картинки до >=1000Гц (хоча це все ще незначні значення). Більшість телевізорів так не вміє, але навіть так багато хто відображає картинку на частоті 100Гц - така величина вже цілком собі класика. А якщо вірити вікіпедії, то у кінематографі «частота 24 кадри на секунду є загальносвітовим стандартом». Для того, щоб перетворити 24 кадри в секунду вихідного відеопотоку на 100 кадрів в секунду результату, телевізор використовує інтерполяцію. А саме якісь алгоритми в стилі «взяти два сусідні кадри 1 і 2, порахувати різницю між ними і сформувати з неї 3 додаткові кадри, які треба впхнути між тими двома первісними» -> виходять кадри 1, 1_1 , 1_2 , 1_3 , 2

Для подальших міркувань візьмемо простіший приклад. Уявімо, наприклад, лабораторну роботуз географії в якомусь 6-му класі (до речі, у мене колись і справді була така). Необхідно кожні 3 години вимірювати температуру повітря та записувати дані, а потім здати вчителеві графік зміни температури від часу доби. Припустимо, за результатами вимірювань у нас вийшла така табличка (дані придумані випадковим чином і ніяк не претендують на якусь правдоподібність):

Відобразимо отримані дані на графіку:

Власне, дані записані та відображені на графіку. Ми впритул підійшли до завдання інтерполяції – як за наявними точками відновити плавну криву?

Кількість умов та ступінь інтерполіруючого полінома

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

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

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

Повертаючись до нашого завдання з температурою – у ньому ми визначили 6 точок, отже, щоб провести поліном єдиним чином, він має бути 5-го ступеня

Інтерполуючий поліном тоді виглядатиме так:

$inline$-\frac(x^5)(14580)+\frac(13x^4)(1944)-\frac(41x^3)(162)+\frac(983x^2)(216)-\frac (2273x)(60)+117$inline$

А зараз слід зробити важливе зауваження і пояснити, що я мав на увазі під «умовою». Поліном можна задати не тільки координатами точок, якими він проходить, умовами можуть бути будь-які параметри цього полінома. У найпростішому випадку це справді координати точок. Але як умову можна взяти, наприклад, першу похідну цього полінома в будь-якій точці. Другу похідну. Третю похідну. Загалом, будь-яку можливу похідну до будь-якої з точок, в якій цей поліном існує. Поясню на прикладі:
Пряму можна задати однозначно, як я вже казав, двома точками:

Ту ж пряму, з іншого боку, можна визначити координатою однієї точки та кутом нахилу альфа до горизонталі:

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

Нехай нам задано такі три умови:

Умов три, отже, ми хочемо отримати поліном другого ступеня:

Підставляємо

Вважаємо першу похідну та вважаємо

Вважаємо другу похідну та вважаємо

Звідси отримуємо, що наш поліном виглядає так:

Інтерполяція кубічними сплайнами

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

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

Повертаючись до розказаного в попередньому пункті, для того, щоб однозначно задати один поліном 3-го ступеня, необхідно 4 умови. У цьому завданні ми маємо 5 поліномів, тобто, щоб задати їх усі, нам потрібно сумарно 5∙4=20 умов. І ось як вони виходять:

1) Перший поліном визначено на першій та другій точках – це дві умови. Другий поліном визначено на другій та третій точках – ще дві умови. Третій поліном, четвертий, п'ятий – кожен із них визначено на 2-х точках – сумарно це дає 10 умов.

2) Для кожної проміжної точки з множини (а це 4 точки з часом 12:00, 15:00, 18:00, 21:00) має виконуватися умова, що перші та другі похідні для лівого та правого поліномів повинні збігатися. Формульно:

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

3) Залишаються дві умови, які поки що не визначені. Це так звані «граничні умови», від завдання яких і залежить, який сплайн вийде. Зазвичай задають другі похідні на кінцях інтервалу рівними 0:

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

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

Складність завдання полягає в тому, що задаючи перші похідні на кінцях інтервалу, так, ми задаємо цей сплайн. Теоретично. А ось порахувати його на практиці - завдання досить складне і абсолютно неочевидне (бажаючі можуть подивитися код знаходження природного сплайну на Вікі - ru.wikipedia.org/wiki/Кубічний_сплайн - і спробувати його зрозуміти хоча б). Зрозуміло, я зовсім не хотів провести купу часу, закопавшись у матан і намагаючись вивести потрібні формули. Я хотів більш просте та елегантне рішення. І я знайшов його.
Розглянемо наш сплайн та візьмемо перший з його інтервалів. На цьому інтервалі вже задано 3 умови:

Задається користувачем

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

Нічим не обґрунтоване припущення

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

Обчислюється з

Обчислюється з

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

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

І спробувати знайти таке значення, при якому зверталася б у 0 - і це буде тим самим правильнимзначенням, яке будує шуканий користувачем сплайн:

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

Отже, ми гарантовано знаходимо шуканий сплайн за 3 прогони таких обчислень.

Трохи коду та скріншотів програми

Class CSplineSubinterval (public double A(get;) public double B(get;) public double C(get;) public double D(get;) double df, double ddf) ( _p1 = p1; _p2 = p2; B = ddf; C = df; D = p1.Y; A = (_p2.Y - B * Math.Pow(_p2.X - _p1.X, 2) - C * (_p2.X - _p1.X) - D) / Math.Pow(_p2.X - _p1.X, 3); ) public double F(int x) - _p1.X, 3) + B * Math.Pow(x - _p1.X, 2) + C * (x - _p1.X) + D; ) public double Df(int x) ( return 3 * A * Math .Pow(x - _p1.X, 2) + 2 * B * (x - _p1.X) + C; B; ) )

Class CSpline ( private readonly CPoint _points ; private readonly CSplineSubinterval _splines ; public double Df1 ( get ( return _points.Df ; ) set ( _points.Df = value ; ) ) .Ddf = value; )) public double Dfn ( get ( return _points[_points.Length - 1].Df; ) set ( _points[_points.Length - 1].Df = value; ) ) public double Ddfn ( get ( return _points[_points.Length - 1].Ddf; ) set ( _points[_points.Length - 1].Ddf = value; ) ) public CSpline(Cpoint points) ( _points = points; _splines = new CSplineSubinterval; ) ) ( const double x1 = 0; var y1 = BuildSplines(x1); const double x2 = 10; var y2 = BuildSplines(x2); _points.Ddf = -y1 * (x2 - x1) / (y2 - y1); BuildSplines (_points.Ddf);_points[_points.Length - 1].Ddf = _splines[_splines.Length - 1].Ddf(_points[_points.Length - 1].X); df = _points.Df, ddf = ddf1;for (var i = 0; i< _splines.Length; i++) { _splines[i] = new CSplineSubinterval(_points[i], _points, df, ddf); df = _splines[i].Df(_points.X); ddf = _splines[i].Ddf(_points.X); if (i < _splines.Length - 1) { _points.Df = df; _points.Ddf = ddf; } } return df - Dfn; } }

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

Переваги та недоліки алгоритму

Навскидку можна сказати, що складність алгоритму - O(N), оскільки, як я вже казав, незалежно від кількості точок, достатньо двох прогонів обчислень, щоб отримати правильне значеннядругий похідний на лівому кінці інтервалу, і ще одного, щоб побудувати сплайн.

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

Тож у чому завинили тести IQ?

Розглянемо спочатку ряд «2, 4, 6, 8, ?»
Уявімо цей числовий рядяк безліч пар значень:

Де як ми беремо саме число, а як – порядковий номерцього числа. Яке значення має бути на місці?

Думка, до якої я намагаюся плавно підвести – це те, що ми можемо підставити будь-яке значення. Адже, що за фактом перевіряють такі завдання? Здатність людини визначити якесь правило, яке пов'язує всі наявні числа, і за цим правилом вивести наступне число в послідовності. Говорячи науковою мовою, тут стоїть завдання екстраполяції (завдання інтерполяції полягає в тому, щоб знайти криву, що проходить через усі точки всередині деякого інтервалу, а завдання екстраполяції – продовжити цю криву за межі інтервалу, «пророкувавши» таким чином поведінку кривої надалі). Так ось, екстраполяція не має однозначного рішення. Взагалі. Ніколи. Якби було інакше, люди давним-давно передбачили прогноз погоди на всю історію людства вперед, а стрибки курсу рубля ніколи не були б несподіванкою.

Зрозуміло, передбачається, що правильна відповідь у цьому завдання все-таки є і вона дорівнює 10, і тоді «закон», що пов'язує всі ці числа, – це

МІНІСТЕРСТВО ОСВІТИ І НАУКИ РОСІЙСЬКОЇ ФЕДЕРАЦІЇ

Федеральна державна автономна освітня установа

вищої професійної освіти

"Уральський федеральний університет імені першого Президента Росії Б.Н.Єльцина"

Інститут радіоелектроніки та інформаційних технологій – РТФ

Кафедра Автоматика та інформаційні технології

Інтерполяція сплайнами

МЕТОДИЧНІ ВКАЗІВКИ До лабораторної роботи з дисципліни «Чисельні методи»

Упорядник І.А.Селіванова, ст.викладач.

ІНТЕРПОЛЯЦІЯ СПЛАЙНАМИ:Методичні вказівки до практичним заняттямз дисципліни «Кількісні методи»

Вказівки призначені для студентів усіх форм навчання напряму 230100 – «Інформатика та обчислювальна техніка».

Ó ФДАОУ ВПО «УрФУ імені першого Президента Росії Б.Н.Єльцина», 2011

1. ІНТЕРПОЛЯЦІЯ СПЛАЙНАМИ. 4

1.1. Кубічні сплайни. 4

1.2. Спеціальна формазапис сплайну. 5

1.3. Квадратичні сплайни. 13

1.4. Завдання на практику. 18

1.5. Варіанти завдань. 19

Список літератури 21

1. Інтерполяція сплайнами.

У випадках, коли проміжок [ a,b], на якому потрібно замінити функцію f(x) Великий, можна застосувати інтерполяцію сплайнами.

1.1. Кубічні сплайни.

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

Нехай на відрізку [ a, b] речової осі x задана сітка, у вузлах якої визначено значення
функції f(x). Потрібно побудувати на відрізку [ a, b] безперервну функцію-сплайн S(x), яка задовольняє наступним умовам:

Для побудови сплайну потрібно знайти коефіцієнти
багаточленів
,i=1,… n, тобто. 4 n невідомих коефіцієнта, які задовольняють 4 n-2 рівнянням (1), (2), (3). Щоб система рівнянь мала рішення, додають ще дві додаткові (крайові) умови. Використовується три типи крайових умов:

Умови (1), (2), (3) та одну з умов (4), (5), (6) утворюють СЛАУ порядку 4 n. Рішення системи можна здійснити за допомогою методу Гауса. Однак, вибравши спеціальну форму запису кубічного багаточлена, можна суттєво знизити порядок розв'язуваної системи рівнянь.

1.2. Спеціальна форма запису сплайну.

Розглянемо відрізок
. Введемо такі позначення змінних:

Тут
- Довжина відрізка
,

,
- допоміжні змінні,

x- Проміжна точка на відрізку
.

Коли x пробігає всі значення на інтервалі
, змінна змінюється від 0 до 1, а
змінюється від 1 до 0

Нехай кубічний багаточлен
на відрізку
має вигляд:

Змінні і
визначаються стосовно конкретного відрізку інтерполяції.

Знайдемо значення сплайну
на кінцях відрізка
. Крапка
є початковою для відрізка
тому =0,
=1 і відповідно (3.8):
.

На кінці відрізка
=1,
=0 і
.

Для інтервалу
крапка
є кінцевою, тому =1,
=0 та з формули (9) отримуємо:
. Таким чином, виконується умова безперервності функції S(x) у вузлах стикування кубічних багаточленів незалежно від вибору чисел i .

Для визначення коефіцієнтів  i , i=0,… n продиференціюємо (8) двічі як складну функціювід x. Тоді

Визначимо другі похідні сплайну
і
:

Для багаточлена
крапка є початком відрізка інтерполяції та =0,
=1, тому

З (15) та (16) випливає, що на відрізку [ a,b]сплайн-функція, «склеєна» зі шматків багаточленів 3-го порядку, має безперервну похідну 2-го порядку.

Щоб отримати безперервність першої похідної функції S(x), вимагатимемо у внутрішніх вузлах інтерполяції виконання умови:

Для природного кубічного сплайну
, отже, система рівнянь матиме вигляд:

і система рівнянь (17) матиме вигляд:

приклад.

Вихідні дані:

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

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

Для різних крайових умов (4), (5), (6) знайдемо коефіцієнти кубічних сплайнів.

1. Розглянемо перші крайові умови.

У нашому випадку n=3,
,
,
. Щоб знайти
використовуємо систему рівнянь (3.18):

Обчислимо і , використовуючи формули (7) та (11):

Підставимо отримані значення до системи рівнянь:

.

Рішення системи:

З урахуванням перших крайових умов коефіцієнти сплайну:

Розглянемо визначення коефіцієнтів сплайну з урахуванням крайових умов (3.5):

Знайдемо похідну функції
:

Обчислимо
і
:

Підставимо в систему рівнянь (21) значення і :

Використовуючи формулу (20) визначимо  0 та  3:

З урахуванням конкретних значень:

та вектор коефіцієнтів:

Розрахуємо значення кубічного сплайну S(x) у серединах відрізків інтерполяції.

Середини відрізків:

Для обчислення значення кубічного сплайну в серединах відрізків інтерполяції скористаємося формулами (7) та (9).

3.1.

Знайдемо і
:

У формулу (3.9) підставляємо коефіцієнти

3.2.

Знайдемо і
:

, для крайових умов (4), (5), (6):

3.3.

Знайдемо і
:

У формулу (9) підставляємо коефіцієнти
, для крайових умов (4), (5), (6):

Складемо таблицю:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

.

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

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

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

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

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

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

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

.

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

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

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

.

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

.

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

Недоліки шматково-лінійної та поліноміальної інтерполяції призвели до розробки теорії сплайн-функції (від англійського слова 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).