Доброго часу, Хабр!

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

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

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

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

Читати далі →

Оптимальна апроксимація сплайнами

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



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



Читати далі →