Интерполяция полиномами Лагранжа и Ньютона

Постановка задачи

Пусть задана функция .  Пусть заданы точки из некоторой области . Пусть значения функции известны только в этих точках. Точки называют узлами интерполяции.  - шаг интерполяционной сетки. Задача интерполяции состоит в поиске такой функции из заданного класса функций, что 

Метод решения задачи

Полином Лагранжа

Представим интерполяционную функцию в виде полинома где - полиномы степели 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 Интерполяция полиномом Ньютона: Ошибка:

20. Построение кривой по точкам. Интерполяция кубическими сплайнами. Эффективность данного алгоритма. Привести фрагмент программы, поясняющий данный алгоритм.

Интерполяция кубическими сплайнами

Введение

Постановка математической задачи

Одной из основных задач численного анализа является задача об интерполяции функций. Пусть на отрезке задана сетка и в её узлах заданы значения функции , равные . Требуется построить интерполянту — функцию , совпадающую с функцией в узлах сетки:

( 1 )

Основная цель интерполяции — получить быстрый (экономичный) алгоритм вычисления значений для значений , не содержащихся в таблице данных.

Интерполируюшие функции , как правило строятся в виде линейных комбинаций некоторых элементарных функций:

где — фиксированный линейно независимые функции, — не определенные пока коэффициенты.

Из условия (1) получаем систему из уравнений относительно коэффициентов :

Предположим, что система функций такова, что при любом выборе узлов отличен от нуля определитель системы:

.

Тогда по заданным однозначно определяются коэффициенты .