|
Алгоритмы - Интерполяция, аппроксимация и численное дифференцирование
Интерполяция, аппроксимация и численное дифференцирование
Алгоритмы - Интерполяция, аппроксимация и численное дифференцирование
Интерполяция, аппроксимация и численное дифференцирование
Введение в раздел
Полиномиальная интерполяция
Полиномиальная интерполяция.
Полиномиальная интерполяция с вычислением производной полинома
Полиномиальная интерполяция. Также вычисляется производная интерполирующего полинома.
Вычисление M-ой производной по N точкам полиномиальной интерполяцией
Полиномиальная интерполяция и дифференцирование полученного полинома.
Интерполяция кубическими сплайнами
Кусочно-кубическое представление функции. Неплохой способ интерполяции, быстрый и устойчивый к погрешностям.
Вычисление коэффициентов интерполирующей рациональной функции
Интерполируемая функция представляется, как отношение двух полиномов.
--------------------------------------------------------------------------------
Аппроксимация прямыми методом наименьших квадратов (МНК)
Аппроксимируемая функция представляется, как прямая.
Аппроксимация полиномами методом наименьших квадратов (МНК)
Аппроксимируемая функция представляется, как полином.
Аппроксимация кубическими сплайнами методом наименьших квадратов (МНК)
Аппроксимируемая функция представляется, как кубический сплайн. Для каждой точки задается индивидуальный весовой коэффициент.
Аппроксимация обобщенным методом наименьших квадратов (МНК)
Аппроксимируемая функция представляется, как сумма произвольных базисных функций. Для каждой точки задается индивидуальный весовой коэффициент.
Паде-аппроксимация
Аппроксимируемая функция представляется, как отношение двух полиномов.
--------------------------------------------------------------------------------
Билинейное ресэмплирование (билинейная интерполяция)
Функция задана на сетке M1 xN1 , осуществляется переход к сетке M2 xN2 .
Бикубическое ресэмплирование (бикубическая интерполяция)
Функция задана на сетке M1 xN1 , осуществляется переход к сетке M2 xN2 .
--------------------------------------------------------------------------------
Построение кривой Безье
Построение кривой Безье
|
Введение
|
Первоначально я хотел разделить задачи, решаемые в этом разделе, по трем отдельным разделам - "Интерполяция", "Аппроксимация", "Численное дифференцирование", но оказалось, что эти задачи настолько тесно взаимосвязаны, что имеет смысл рассматривать их совместно. Цель этого введения - кратко охарактеризовать методы, приведенные в разделе.
Задачи интерполяции и аппроксимации можно поделить на два класса: одномерные и многомерные. Здесь, в основном, приведены методы решения одномерных задач.
Типичные проблемы
Наиболее типичной проблемой для методов интерполяции/аппроксимации являются функции, имеющие полюса в окрестностях области интерполяции (имеются в виду полюса на комплексной плоскости).
Пример: результат полиномиальной интерполяции по 11 точкам функции

Хотя полином прошел через все указанные ему точки, но между этими точками он очень сильно отклоняется от интерполируемой функции. Причиной тому является наличие у интерполируемой функции двух полюсов в точках x = i и x = -i. Разные методы по-разному справляются с этой проблемой.
Ещё одной проблемой является работа метода в случае большого объема входных данных (тысячи точек). Трудоемкость одних методов квадратична, и они начинают работать слишком медленно. Другие методы успешно справляются с проблемой.
Методы интерполяции
- Полиномиальная интерполяция. Самый простой метод, но в ряде случаев лучше его не найти. Очень хорош для интерполяции гладких функций, особенно в случае, когда вам требуется на основе малого числа точек получить очень точный результат. Если функция "хорошая", то по десятку точек можно получить результат с точностью порядка 10 -6-10 -10. Недостатком является время работы порядка O(N 2) и очень высокая погрешность в случае недостаточно гладких функций.
- Сплайн-интерполяция. Интерполяция кусочно-кубическими функциями. Время работы порядка O(N). Устойчивый и надежный метод, сделает любую работу, если число известных точек достаточно велико.
- Рациональная интерполяция. Функция представляется, как отношение двух полиномов. Самый мощный и самый капризный из методов. Метод хорошо справляется даже с функциями, имеющими полюса в окрестностях области интерполяции, но в некоторых случаях он может добавить к интерполируемой функции несколько лишних полюсов, которых там не должно быть. Я так и не нашел реализации этого метода, полностью свободной от некоторых недостатков. Скажем, в ряде случаев просто не удается построить интерполирующую функцию. В общем, метод можно использовать, если у вас есть возможность убедиться в том, что в вашем случае он будет работать нормально. Время работы порядка N 2.
Методы аппроксимации
Существует множество методов аппроксимации, на сайте представлены лишь некоторые. Это аппроксимация по МНК и Паде-аппроксимация.
- Аппроксимация по МНК (методом наименьших квадратов) является целым семейство методов, которые аппроксимируют функцию, заданную набором точек и значений в них, как линейную комбинацию базисных функций. При этом минимизируется сумма квадратов отклонений заданных значений от построенной аппроксимирующей кривой. На сайте представлена аппроксимация прямыми, полиномами, сплайнами и произвольным набором базисных функций.
- Паде-аппроксимация - это довольно-таки экзотический способ аппроксимации, который применяется в случае, если известны значения производных функции в некоторой точке. Строится дробно-рациональный аналог разложения в степенной ряд, который на некотором классе функций оказывается предпочтительнее обычного степенного ряда.
|