Интерполяция полиномами Лагранжа и Ньютона
Материал из MachineLearning.
Содержание |
Постановка задачи
Пусть задана функция
.
Пусть заданы точки
из некоторой области .
Пусть значения функции известны только в этих точках.
Точки называют узлами интерполяции.
- шаг интерполяционной сетки.
Задача интерполяции состоит в поиске такой функции из заданного класса функций, что
Метод решения задачи
Полином Лагранжа
Представим интерполяционную функцию в виде полинома
где - полиномы степели n вида:
Очевидно, что принимает значение 1 в точке и 0 в остальных узлах интерполяции. Следовательно в точке исходный полином принимает значение
Таким образом, построенный полином является интерполяционным полиномом для функции
на сетке .
Полином Ньютона
Интерполяционный полином в форме Лагранжа не удобен для вычислений тем, что при увеличении числа узлов интерполяции приходится перестраивать весь полином заново.
Перепишем полином Лагранжа в другом виде:
где - полиномы Лагранжа степени i ≤ n.
Пусть
. Этот полином имеет степень i и обращается в нуль при
.
Поэтому он представим в виде:
,
где - коэффициент при . Так как не входит в , то совпадает с коэффициентом при в полиноме . Таким образом из определения получаем:
где
Препишем формулу в виде
Рекуррентно выражая пролучам окончательную формулу для полинома:
Такое представление полинома удобно для вычисления, потому что увеличение числа узлов на единицу требует добавления только одного слагаемого.
Погрешность интерполирования
Поставим вопрос о том, насколько хорошо интерполяционный полином приближает функцию на отрезке [a,b].
Рассмотри м остаточный член:
, x ∈ [a, b].
По определению интерполяционного полинома
поэтому речь идет об оценке при значениях .
Пусть имеет непрерывную (n+1) производную на отрезке [a, b].
Тогда погрешность определяется формулой:
,
где ,
- точка из [a, b].
Так как точка наизвестна, то эта формула позволяет только оценить погрешность:
где
Из вида множетеля следует, что оценка имеет смысл только при . Если это не так, то при интерполяции используются полиномы низких степеней (n = 1,2).
Выбор узлов интерполяции
Так как от выбора узлов завист точность интерполяции, то возникает вопрос о том, как их выбирать.
С помощью выбора узлов можно минимизировать значение в оценке погрешности. Эта задача решается с помощью многочлена Чебышева [1]:
В качестве узлов следут взять корни этого многочлена, то есть точки:
Пример
В качастве примера рассмотрим интерполяцию синуса.
Возьмем равномерную решетку x = [-3,-1.5,0,1.5,3];
Интерполяция полиномом Лагранжа:
Ошибка(максимальное отклонение от sin(x) на отрезке):0.1423
Интерполяция полиномом Ньютона:
Ошибка:
Возьмем решетку x с узлами в корнях полинома Чебышева= [-2.8531,-1.7632,0,1.7634,2.8532];
Интерполяция полиномом Лагранжа:
Ошибка: 0.0944
Интерполяция полиномом Ньютона:
Ошибка:
Рекомендации программисту
Выводы
Литература
- Самарский А.А. Гулин А.В. Численные методы 1989г.
- Костомаров Д.П., Фаворский А.П. Вводные лекции по численным методам