Comments 15
Приблизительно год назад я решал задачу аппроксимации массива точек в трехмере при помощи сплайн-плоскости. К сожалению, массивы у меня были «плохие» и постоянно получались «колодцы» или «горы» там, где их быть не должно, как в примере автора.
В сети очень много сплайн-алгоритмов и их реализаций на различных языках именно для двумерных случаев (первая половина статьи, например, повторяет методичку, которую нам раздавали на втором курсе), а вот для трёхмерных и, тем более, n-мерных случаев толковых алгоритмов, а тем более реализаций, я лично найти не смог.
Может быть автор или кто-нибудь ещё сможет описать реализацию подобных «гладких» сплайнов для трехмера?
Посмотрите книгу Curve and Surface Fitting with Splines (Numerical Mathematics and Scientific Computation), автор Paul Dierckx. Основные идеи в статье взяты оттуда.
Человеческим зрением вижу две кривых на первом рисунке. Вы ничего в критериях не потеряли?
Очередной сэнсэй дорвался до редактора формул и наваял «туториал», ненужный тем, кто умеет и непонятный тем, кто не умеет :)
В своё время пытался подобным образом решать аналогичную задачу, но не осилил, заткнулся на выборе узлов. Решил её другим способом — последовательной аппроксимацией функцией a*sin(k*x)+b*cos(k*x)
Неплохая статья, но предложенный метод решения проблемы наименьших квадратов не самый устойчивый — вычисление AT A возводит число обусловленности проблемы в квадрат. Часто надежнее (но медленнее) для подобных проблем использовать SVD
На всякий случай скажу очевидную вещь — выбор критериев остаётся делом произвола и не имеет однозначных формальных критериев.
Ну т.е. приведённые «нехорошие примеры» — в реальности, в некоторых случаях — могут оказаться вполне хорошими.
Понимать это может только человек, подбирающий сплайн.
Я нечто подобное в свое время генетическим алгоритмом делал. Довольно забавно в динамике наблюдать, как кривая подстраивается под точки.
Чтение математической литературы может быть увлекательнее любого детектива.

Сначала — завязка. Поставлена понятная задача и показано решение. Интересно, открываем.
Функция s(x) на интервале [a, b] называется сплайном степени k на сетке с горизонтальными узлами image
Что за g, почему 2k? Интрига. Но уже в следующем предложении интрига раскрывается, заодно показывая несколько иллюстраций, из которых понятно, что «ну это всё просто!». Расслабляемся и читаем дальше.
Строго говоря, они должны доставлять минимум функции
image
Хмм… Похоже на метод наименьших квадратов. Приятно чувствовать, что какие-то знания у меня есть. И тут вдруг — неожиданный поворот сюжета:
Для удобства запишем в матричном виде:
image
Что за палочки, что за цифры, нас такому не учили! Страшно. И хотя дальше матрица в привычном представлении присутствует, чувство тревоги не уходит. И вот:
Тогда вся задача и все предыдущие формулы сводятся к решению простой системы линейных уравнений:
Звучит как очевидный факт, но мне же это совсем не очевидно! Расстроившись, я пошёл пить чай.

(спустя некоторое время)
Хм… Минимизировать разницу между производными для обеспечения гладкости — это сильно!

(спустя ещё некоторое время)
Что-то формул всё больше и больше. Посмотрю-ка я пока просто картинки, а к формулам попозже вернусь.

(финал)
О, код на питоне! Написан вроде неплохо. Значит, теперь в формулы не обязательно вникать, можно же и отладчиком прогнать, если вдруг что. Облегчение.


(вместо заключения)
Многие авторы математических алгоритмов не прикладывают к своим статьям никакого кода, считая, что для программиста его математические выкладки должны быть очевидными. К сожалению, это редко когда так. Для программиста конструкция for(){for(){...}} более понятна, чем Σ Σ, даже если знать, что Σ — это сумма, и несмотря на то, что она длиннее. Поэтому автору отдельный респект за код.
Вот это хороший материал! Идеально подходит как для исследований, так и для лекций. А есть Интернет-ссылки на какие-нибудь работы автора в научных журналах, чтобы потом сослаться?
Как я писал выше, Вы можете сослаться на книгу «Curve and Surface fitting with splines» автора Paul Dierckx. Я лишь модифицировал взятый оттуда алгоритм.
А лично у меня лишь одна статья в англоязычном научном журнале, и ссылаться на неё Вам вряд ли придётся =)
Only those users with full accounts are able to leave comments. Log in, please.