Интерполяция многочленами
На практике чаще всего применяют интерполяцию многочленами. Это связано прежде всего с тем, что многочлены легко вычислять, легко аналитически находить их производные и множество многочленов плотно в пространстве непрерывных функций (теорема Вейерштрасса).
Линейная интерполяция
Интерполяционная формула Ньютона
Метод конечных разностей
ИМН-1 и ИМН-2
Многочлен Лагранжа (интерполяционный многочлен)
По схеме Эйткена
Сплайн-функция
Кубический сплайн
Пусть
задана функция
.
Пусть заданы точки
из
некоторой области
.
Пусть
значения функции
известны
только в этих точках.
Точки
называют
узлами интерполяции.
-
шаг интерполяционной сетки.
Задача
интерполяции состоит в поиске такой
функции
из
заданного класса функций, что
Метод решения задачи Полином Лагранжа
Представим
интерполяционную функцию в виде
полинома
где
-
полиномы степели n вида:
Очевидно,
что
принимает
значение 1 в точке
и
0 в остальных узлах интерполяции.
Следовательно в точке
исходный
полином принимает значение
Таким
образом, построенный полином
является
интерполяционным полиномом для функции
на
сетке
.
Полином Ньютона
Интерполяционный
полином в форме Лагранжа не удобен для
вычислений тем, что при увеличении числа
узлов интерполяции приходится
перестраивать весь полином заново.
Перепишем
полином Лагранжа в другом виде:
где
-
полиномы Лагранжа степени i ≤ n.
Пусть
.
Этот полином имеет степень i и обращается
в нуль при
.
Поэтому он представим в виде:
,
где
-
коэффициент при
.
Так как
не
входит в
,
то
совпадает
с коэффициентом при
в
полиноме
.
Таким образом из определения
получаем:
где
Препишем
формулу
в
виде
Рекуррентно
выражая
пролучам
окончательную формулу для полинома:
Такое
представление полинома удобно для
вычисления, потому что увеличение числа
узлов на единицу требует добавления
только одного слагаемого.
Погрешность интерполирования
Поставим
вопрос о том, насколько хорошо
интерполяционный полином
приближает
функцию
на
отрезке [a,b].
Рассмотри м остаточный
член:
,
x ∈
[a, b].
По определению интерполяционного
полинома
поэтому
речь идет об оценке
при
значениях
.
Пусть
имеет
непрерывную (n+1) производную на отрезке
[a, b].
Тогда погрешность определяется
формулой:
,
где
,
-
точка из [a, b].
Так как точка
наизвестна,
то эта формула позволяет только оценить
погрешность:
где
Из
вида множетеля
следует,
что оценка имеет смысл только при
.
Если это не так, то при интерполяции
используются полиномы низких степеней
(n = 1,2).
Выбор узлов интерполяции
Так
как от выбора узлов завист точность
интерполяции, то возникает вопрос о
том, как их выбирать. С помощью выбора
узлов можно минимизировать значение
в
оценке погрешности. Эта задача решается
с помощью многочлена Чебышева [1]:
В
качестве узлов следут взять корни этого
многочлена, то есть точки:
12. Многомерная интерполяция данных
Триангуляция:
1)Опред какой ячейке принадлеж. заданное х;
2)Выбираем свою сист координат для найденной ячейки(масштабное /аффинное/преобразование)
x1’’=a1*x’
рисунок
3) вычисл у в точке х''
-) требуется, чтобы точки были на вершинах n-мерных прямоугол областей
-) на границах между ячейками гладкость может исчезать
+) в пределах каждой области интерполирующая ф-ция гладкая и непрерывная
+)не нужно решать дополнит задачи(на подготов этапе)
В различных приложениях широко используют двумерные и трехмерные таблицы. Например, теплофизические свойства различных веществ зависят от температуры и давления, а оптические характеристики - еще и от длины волны излучения.
При
многомерной интерполяции из-за
громоздкости таблиц необходимо брать
достаточно большие шаги по аргументам,
т.е. сетка узлов, на которой строят
таблицу, получается довольно грубой.
Поэтому требуется вводить преобразование
переменных
,
,
,
подбирая подходящие формулы. При удачном
выборе таких формул можно использовать
в новых переменных интерполяционный
полином невысокой степени.
Осуществляя
многомерную интерполяцию, следует
помнить, что расположение узлов не может
быть произвольным. Например, при
интерполяции полиномом первой степени
узлы
не должны лежать на одной прямой в
плоскости. Действительно, определитель
системы трех уравнений
(1.27)
записывается в виде
(1.28)
Условие размещения трех точек на одной прямой выглядит следующим образом:
.
После простых преобразований имеем
,
(1.29)
т.е. если узлы лежат на одной прямой, то определитель (1.28) обращается в нуль и построить полином вида (1.27) невозможно. Проверять условия подобного типа достаточно сложно, поэтому на практике стремятся строить регулярные сетки, как правило, прямоугольные и равномерные, когда узлы являются точками пересечения двух взаимно перпендикулярных систем параллельных прямых. На этой сетке проводят простую последовательную интерполяцию: сначала по строкам, а затем по столбцам.
При
последовательной интерполяции завышается
степень интерполяционного полинома.
При треугольной конфигурации расположения
узлов степень многочлена будет
минимальной. Многочлен
-й
степени в форме Ньютона в этом случае
можно представить как обобщение
одномерного варианта записи:
.
(1.30)