Интерполяция кубическими сплайнами
Материал из MachineLearning.
(→Список литературы) |
Версия 08:37, 20 октября 2008
Содержание |
Введение
Постановка математической задачи
Одной из основных задач численного анализа является задача об интерполяции функций. Пусть на отрезке задана сетка и в её узлах заданы значения функции , равные . Требуется построить интерполянту — функцию , совпадающую с функцией в узлах сетки:
Основная цель интерполяции — получить быстрый (экономичный) алгоритм вычисления значений для значений , не содержащихся в таблице данных.
Интерполируюшие функции , как правило строятся в виде линейных комбинаций некоторых элементарных функций:
где — фиксированный линейно независимые функции, — не определенные пока коэффициенты.
Из условия (1) получаем систему из уравнений относительно коэффициентов :
Предположим, что система функций такова, что при любом выборе узлов отличен от нуля определитель системы:
.
Тогда по заданным однозначно определяются коэффициенты .
Изложение метода
Интерполяция кубическими сплайнами является частным случаем кусочно-полиномиальной интерполцией. В этом специальном случае между любыми двумя соседними узлами функция интерполируется кубическим полиномом. его коэффициенты на каждом интервале определяются из условий сопряжения в узлах:
Кроме того, на границе при и ставятся условия
Будем искать кубический полином в виде
Из условия имеем
Вычислим производные:
и потребуем их непрерывности при :
Общее число неизвестных коэффициентов, очевидно, равно , число уравнений (4) и (5) равно . Недостающие два уравнения получаем из условия (2) при и :
Выражение из (5) , подставляя это выражение в (4) и исключая , получим
Подставив теперь выражения для и в первую формулу (5), после несложных преобразований получаем для определения разностное уравнение второго порядка
С краевыми условиями
Условие эквивалентно условию и уравнению . Разностное уравнение (6) с условиями (7) можно решить методом прогонки, представив в виде системы линейных алгебраических уравнений вида , где вектор соответствует вектору , вектор поэлементно равен правой части уравнения (6), а матрица имеет следующий вид:
где и .
Метод прогонки
Метод прогонки, основан на предположении, что искомые неизвестные связаны рекуррентным соотношением:
Используя это соотношение, выразим и через и подставим в i-e уравнение:
,где - правая часть i-го уравнения. Это соотношение будет выполняться независимо от решения, если потребовать
Отсюда следует:
Из первого уравнения получим:
После нахождения прогоночных коэффициентов и , используя уравнение (1), получим решение системы. При этом,
Пример: интерполирование неизвестной функции
Построим интерполянту для для функции , заданной следующим образом:
1 | 1.0002 |
2 | 1.0341 |
3 | 0.6 |
4 | 0.40105 |
5 | 0.1 |
6 | 0.23975 |
В результате интерполяции были рассчитаны следующие коэффициенты интерполянты:
Интервал | ||||
---|---|---|---|---|
1,0002 | -0,140113846 | 0,440979231 | -0,266965385 | |
1,0341 | -0,291901538 | -0,359916923 | 0,217718462 | |
0,6 | -0,22553 | 0,293238462 | -0,266658462 | |
0,40105 | -0,100328462 | -0,506736923 | 0,306015385 | |
0,1 | -0,134456154 | 0,411309231 | -0,137103077 |
Ошибка интерполяции
Нас будет интересовать поведение максимального уклонения сплайна от интерполируемой функции в зависимости от максимального расстояния между соседними узлами интерполирования, т.е. зависимость величины
от шага h, где .
Известно, что если функция имеет четыре непрерывные производные, то для ошибки интерполяции определенным выше кубическим сплайном верна следующая оценка
причем константа в этом неравенстве является наилучшей из возможных
Пример: интерполяция синуса
Постром интерполянту функции на отрезке , взяв равномерно отстоящие узлы с шагом 0.5 и шагом 0.25, и сравним полученные результаты.
Ошибка интерполяции | Оценка ошибки | |
---|---|---|
0.429685 | 3.(3) | |
0.005167 | 0.208(3) |
Список литературы
- А.А.Самарский, А.В.Гулин. Численные методы М.: Наука, 1989.
- А.А.Самарский. Введение в численные методы М.: Наука, 1982.
- Костомаров Д.П., Фаворский А.П. Вводные лекции по численным методам
- Н.Н.Калиткин. Численные методы М.: Наука, 1978.
См. также
- Интерполяция каноническим полиномом
- Тригонометрическая интерполяция
- Рациональная интерполяция
- Проблема выбора узлов для интерполяции
- Практикум ММП ВМК, 4й курс, осень 2008