Постановка задачи интерполяции
На отрезке [a, b] заданы n + 1 точки xi = х0, х1, . . ., хn, которые называются узлами интерполяции, и значения некоторой функции f(x) в этих точках
| f(x0) = y0, f(x1) = y1, . . ., f(xn) = yn. | (1) |
Требуется построить функцию F (х) (интерполяционная функция), принадлежащую известному классу и принимающую в узлах интерполяции те же значения, что и f(x), т. е. такую, что
| F(x0) = y0, F(x1) = y1, . . ., F(xn) = yn. | (2) |
Геометрически это означает, что нужно найти кривую y = F (х) некоторого определенного типа, проходящую через заданную систему точек M(xi, yi) (i = 0, 1, ..., n).
В такой общей постановке задача может иметь бесконечное множество решений или совсем не иметь решений.
Однако эта задача становится однозначной, если вместо произвольной функции F (х) искать полином j (х) (интерполяционный полином) степени не выше n, удовлетворяющий условиям (2), т. е. такой, что
| j (x0) = y0, j (x1) = y1, . . ., j (xn) = yn. | (3) |
Полученную интерполяционную формулу
| (4) |
обычно используют для приближенного вычисления значений данной функции ¦ (х) для значений аргумента х, отличных от узлов интерполяции. Такая операция называется интерполяцией функций.
Различают два вида интерполяции:
- глобальная- соединение всех точек ¦ (х) единым интерполяционным полиномом;
- локальная- соединение точек отрезками прямой (по двум точкам), отрезками параболы (по трем точкам).
18.)
Интерполяционным полиномом называется соответствующий интерполянт, в котором в качестве системы функций φk(x), выбирается полином. 
Существование и единственность интерполяционного полинома гарантируется, если все узлы интерполяции xk различны. Т.к определитель системы линейных алгебраических уравнений для нахождения коэффициентов ak является определителем Вандермонда, который, равен
и, следовательно, отличен от нуля в случае, когда все узлы xk различны и матрица системы невырождена, то решение системы существует и единственно.
Задача интерполяции функции, интерполяционные полиномы:
Пусть на отрезке [a,b] задана функция ƒ(x). Задача интерполяции (или интерполирования) состоит в построении функции g(x), совпадающей с заданной ƒ(x) в некотором наборе точек {x1,x2,...,xn+1} из отрезка [a,b] (эти точки называются узлами интерполяции), т.е. должны выполняться условия:
g(xk)=yk, k=1,2,...,n+1,
где yk - известные значения функции ƒ(x) в точках xk. Функция g(x) называется интерполянтом функции ƒ(x).
Построение интерполяционного полинома:
Для построения необходимо найти коэффициенты 
.
Для нахождения коэффициентов необходимо построить систему линейных уравнений, которая может быть получена на основании того, что многочлен проходит через все узловые точки.
.
В результате имеем систему:
Порядок системы равен 
. Параметры 
, 
известны и заданы в табличной функции. Неизвестными системы являются коэффициенты 
.
Интерполяционный многочлен по формуле Лагранжа имеет вид:
Многочлен 
является интерполяционным многочленом, т. е. в узловых точках он принимает значения таблицы.
Свернем формулу Лагранжа:
, где 
. (Алгоритм метода Лагранжа не предусматривает получение многочлена в явном виде, а сразу находит значение в промежуточных точках.)
| Построение интерполяционного многочлена по методу Ньютона | 
| 
| 
|
Пусть даны узлы –  , а  – значения функции или разделенные разности
нулевого порядка. Тогда
 ,
– разделенные разности 1-го порядка;
 ,
– разделенные разности 2-го порядка.
Разделенная разность  -го порядка для  -й точки вычисляется через разделенную
разность  -го порядка:
 .
Лемма.
Пусть  произвольные попарно несовпадающие узлы, в которых известны значения функции . Тогда алгебраический многочлен  -го порядка, который записывается
в виде:
 является интерполяционным многочленом.
Например,  .
Интерполяционный многочлен Ньютона
Интерполяционный многочлен Ньютона используется для неравных промежутков. |
19.)
. Полиномом Лагранжа 
называется полином n-й степени, проходящий через все точки 
. Если точки не образуют возвратов, то такой полином существует и является единственным. Под возвратом понимается ситуация, когда существуют две точки 
и 
такие, что 
.
Алгоритм построения полинома:
1.Полином 
строится как сумма 
полиномов n-й степени:
2.Каждый из полиномов 
, входящих в сумму, строится следующим образом. 3.Корнями полинома являются все точки 
за исключением точки 
. 4.Единственность обеспечивается за счет того, что коэффициент при старшем члене an подбирается так, чтобы полином проходил через точку . В записи Лагранжа полином выглядит следующим образом:
|
Линейная интерполяция состоит в том, что заданные точки 
(i=0. 1, ..., n) соединяются прямолинейными отрезками, и функция f(x)приближается ломаной с вершинами в данных точках.
Уравнения каждого отрезка ломаной в общем случае разные. Поскольку имеется n интервалов 
, то для каждого из них в качестве уравнения интерполяционного многочлена используется уравнение прямой, проходящей через две точки. В частности, для i-го интервала можно написать уравнение прямой, проходящей через точки 
и , в виде
Отсюда
, (1)
Следовательно, при использовании линейной интерполяции сначала нужно определить интервал, в который попадает значение аргумента x, а затем подставить его в формулу (1) и найти приближенное значение функции в этой точке.
Квадратичная интерполяция. В качестве интерполяционной функции на отрезке 
принимается квадратный трехчлен. Такую интерполяцию называют также параболической.
Уравнение квадратного трехчлена
, (2)
содержит три неизвестных коэффициента ai, bi, ci, для определения которых необходимы три уравнения. Ими служат условия прохождения параболы (2) через три точки 
. Эти условия можно записать в виде
(3)
При вычислении приближенного значения функции с помощью квадратичной интерполяции вместо формулы (1) нужно использовать (2) с учетом решения системы линейных уравнений (3). Интерполяция для любой точки 
проводится по трем ближайшим к ней узлам.
Пример. Найти приближенное значение функции y = f(x) при x = 0.32, если известна следующая таблица ее значений:
| x | 0.15 | 0.30 | 0.40 | 0.55 |
| y | 2.17 | 3.63 | 5.07 | 7.78 |
Воспользуемся сначала формулой линейной интерполяции (1). Значение x = 0.32 находится между узлами xi-1= 0.30 и xi = 0.40. В этом случае
,
,
.
Найдем теперь приближенное значение функции с помощью формулы квадратичной интерполяции (2). Составим систему уравнений (3) с учетом ближайших к точке x = 0.32 узлов: 
. Соответственно 
. Система (3.23) запишется в виде
Решая эту систему, находим 
. Искомое значение функции 
.
20.)
Схема Эйткена
Схема Эйткена предлагает более удобную форму нахождения полинома Лагранжа:
На первом этапе вычисляются многочлены L0,1(x), L1,2(x), :, Ln-1,n(x), построенные на каждой паре соседних узлов 0,1; 1,2; :; n-1,n соответственно.
При этом 
, 
, :, 
.
Таким образом, многочлены, построенные на паре соседних узлов, вычисляются по формулам: 
.
Затем на основе этих многочленов вычисляются многочлены, построенные на тройках соседних узлов: 
.
И т.д. пока не получится один многочлен, построенный на всех узлах интерполяции: 
.
Полученный многочлен L0, 1, ..., n(x) 
Ln(x).