Кубічний сплайн приклад обчислення. Теорія сплайнів приклади рішення

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

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

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

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

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

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

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

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

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

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

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

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

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

1.1.

1.2. Кубічні сплайни. 4Спеціальна форма

запис сплайну. 5

1.3.

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

1.4.

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

1.5. Варіанти завдань. 19,Список літератури 21 1. Інтерполяція сплайнами. У випадках, коли проміжок [(a) b

], на якому потрібно замінити функцію

f xВеликий, можна застосувати інтерполяцію сплайнами. 1.1. Кубічні сплайни.Інтерполяційні сплайни

3-го Варіанти завдань. 19, Список літератури 21порядку - це функції, що складаються з шматків багаточленів. a -го
порядку. У вузлах сполучення забезпечується безперервність функції, її першої та другої похідних. Апроксимуюча функція складається з окремих багаточленів, як правило, однаково невеликого ступеня, визначених кожен на своїй частині відрізка . У випадках, коли проміжок [(a). Нехай на відрізку [ Варіанти завдань. 19, Список літератури 21] речової осі задана сітка, у вузлах якої визначено значення(a), функції

Потрібно побудувати на відрізку [
] безперервну функцію-сплайн
,S=1,… яка задовольняє наступним умовам:Для побудови сплайну потрібно знайти коефіцієнти 4 яка задовольняє наступним умовам: багаточленів 4 яка задовольняє наступним умовам:-2 i

n 4 яка задовольняє наступним умовам:. , тобто.

невідомих коефіцієнта, які задовольняють

рівнянням (1), (2), (3). Щоб система рівнянь мала рішення, додають ще дві додаткові (крайові) умови. Використовується три типи крайових умов:
. Введемо такі позначення змінних:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

приклад.

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

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

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

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

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

У нашому випадку яка задовольняє наступним умовам:=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):

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

Це функція, яка:

Проходить через все задані точки
,
;

На кожному відрізку між сусідніми точкамиє кубічною параболою;

Безперервна разом зі своїми першою та другою похідними у всіх точках.).

інтерполяція
локальна			глобальна
лінійна	параболічна	кубічна парабола	поліном ступеня ( N-1)	кубічний сплайн
Мал. 1.5.

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

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

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

Якщо маємо безперервну або дискретну функціюзазвичай використовують 5 видів перетворень функцій:

Безперервна в дискретну (дискретизація),

Дискретна в безперервну (інтерполяція),

Дискретна в безперервну (апроксимація),

Безперервна в безперервну (інтерполяція),

Дискретна до дискретної (згладжування).

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

Кубічний сплайн.
Кубічні сплайни для інтерполяції запропонував використовувати Шенберг у 1949 р. Слово "сплайн" походить від назви довгих тонких металевих рейок, які з давніх-давен німецькі креслярські кріпили гвоздиками на кульмані замість лекал для проведення складних кривих.

Кубічний сплайн- це функція, яка:

Проходить через усі задані крапок
,
;

На кожному відрізку між сусідніми точками є кубічний поліном;

Безперервна разом зі своїми першою та другою похідними у всіх точках.

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

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

Причому між заданими точками маємо відрізок, тож у цій формулі
.

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

, , ,

(2.2)

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

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

Розглянемо два будь-які сусідні відрізки
і
з номерами
і . Крапка для них є загальною, див. рис. 2.1.

Для правого відрізка кубічний сплайн має вигляд (2.1), а лівого, тобто. при

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

Такі трійки рівнянь можна записати для всіх внутрішніх вузлів.
, що дає
рівнянь.

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

Часто систему рівнянь (2.8) записують для других похідних у вузлах, позначаючи їх
. Тоді вона набуває вигляду (Бахвалов, Чисельні методи, М., 2002):

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

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

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

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

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

.

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

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

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

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

.

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

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

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

.

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

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

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

.

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

.

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

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

.

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

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

Мал. 41. Параметричний сплайн у формі Ерміта. Витягнутість кривої праворуч забезпечується тим, що .

Розглянемо форму Безьє, яка відрізняється від форми Ерміта способом завдання граничних умов, а саме замість векторів і вводяться точки (і відповідні їм радіус вектори) і , як показано на рис.42, такі що виконуються умови: і .

Мал. 42. Параметричний сплайн у формі Безьє.

Перехід від форми Ерміта до форми Безьє здійснюється перетворенням:

, (*)

де - геометричний вектор Безьє. Підставляючи це у вираз для , отримуємо

Корисною властивістюсплайнів у формі Безьє є те, що крива завжди лежить усередині опуклої оболонки, утвореної чотирикутником. Цю властивість можна довести, користуючись тим, що у вираженні (*) коефіцієнти набувають значення від 0 до 1 та їх сума дорівнює одиниці.

Зауважимо, що матриця виду

- називається матрицею Безьє.

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

1. Ньюмен, Спрулл, Основи інтерактивної машинної графіки, М. Світ, 1976.

2. Енджел Й. Практичне введенняу машинну графіку, Радіо та Зв'язок, 1984.

3. А. Вен-Дем, Дж. Фолі, Основи інтерактивної машинної графіки, т.1-2, М. Світ, 1985.

4. Є.В. Жикін, А.В.Боресков, Комп'ютерна графіка. Динаміка, реалістичні їхображення, М., Діалог-МІФІ, 1995, 1997.

5. Л. Амерал, Машинна графіка мовою С, в 4-х томах, вид-во Сол. Систем, 1992.

6. Комп'ютер знаходить розум. Пров. з англ. За ред. В.Л.Стефанюка, М. Світ, 1990.

7. Роджерс, алгоритмічні засади машинної графіки. М. Світ, 1989.

8. Грайс, Графічні засоби персональних комп'ютерів, М., Світ, 1980.

9. Роджерс, Адамс, Математичні основимашинної графіки, М. Машинобудування, 1985.

10. Гілою, Інтерактивна машинна графіка, М., Світ, 1981.

11. Ф. Препарату, М. Шеймос, Обчислювальна геометрія: Вступ, М. Світ, 1989.

12. А. Фокс, М. Пратт, Обчислювальна геометрія, М., Світ, 1982.

13. А.Б.Боресков, Е.В.Шікіна, Г.Е.Шікіна, Комп'ютерна графіка: перше знайомство, Під ред. Е.В.Шікіна, М., Фінанси та статистика, 1996.

14. А.В.Фролов, Г.В.Фролов, Графічний інтерфейс GDI в MS WINDOWS, Москва, Вид-во Діалог-МІФІ, 1994.

15. Майкл Ласло, Обчислювальна геометрія та комп'ютерна графіка на С ++, Москва, Біном, 1997.

16. Ю.Тихомиров, Програмування тривимірної графіки, С.-Пб.: БХВ-Санкт-Петербург,1999.

17. А.Хонич, Як самому створити тривимірну гру. М.:МІКРОАРТ, 1996.

18. М.Маров, 3D Studio MAX 2.5: довідник - СПб: "Пітер", 1999. - 672 с.

19. А. Ла Мот, Д. Раткліфф та ін. Секрети програмування ігор / Перев. з англ. - СПб: Пітер, 1995. - 720 с.

20. Н. Томпсон, Секрети програмування тривимірної графіки для Windows 95. Перев. - СПб: Пітер, 1997. - 352 с.

* У цьому визначенні при заміні, скажімо, осі Oz на вісь Ox решта осей замінюється за правилом циклічної перестановки, тобто Oy заміниться на Oz, а Ox заміниться на Oy. Усього циклічних перестановок може бути три: (x, y, z) (y, z, x) (z, x, y).

* Більше суворе визначенняоднорідних координат дається в розділі лінійної алгебри"Проективні простори".

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

Почну з невеликої вступної. Будучи студентом 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) (return A * Math. - _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; ) public ) ( 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; 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, і тоді «закон», що пов'язує всі ці числа, – це