Поставим следующую задачу: построить многочлен Pn(x) степени n, который в (n+1) данной точке x0, x1,... xn, называемых узлами интерполяции, принимает данные значения y0, y1,... yn.
В данном случае речь идет о построении многочлена Pn(x) степени n, который в определенном смысле "близок" к исходной функции y(x). Известно, что любая непрерывная [a,b] функция y(x) может быть хорошо приближена полиномом Pn(x). Имеет место следующий результат.
Теорема. Для любого e > 0 существует полином Pn(x) степени n = n(e), такой, что
.
Если в качестве базиса {jk(x)} взять базис, состоящий из функций I, x, x2,..., xn , то интерполяционный полином имеет вид
. | (6.4) |
Используя условия интерполяции (6.1), имеем для определения коэффициентов ck систему уравнений
c0 + c1x0 + … + cn = y0
c0 + c1x1 + … + cn = y1;
………….
c0 + c1xn + … + cn = yn.
Определителем этой системы является отличный от нуля определитель Вандермонда
Отсюда следует единственность представления (6.4).
Более удобным для вычислений является базис полиномов Лагранжа {lk(x)} степени n относительно x, удовлетворяющий следующим условиям:
.
Искомый многочлен запишется согласно представлению (6.2) в виде
. | (6.5) |
Поскольку x0, x1,..., xk-1, xk+1,..., xn - нули многочлена lk(x), а также, учитывая, что lk(xk) = 1, имеем
. | (6.6) |
Формула (6.5) с учетом (6.6) имеет вид
. | (6.7) |
или
. | (6.8) |
Многочлен, определенный формулой (6.7), называется интерполяционным полиномом Лагранжа, а элементы базиса {lk(x)} из формулы (6.6) - коэффициентами Лагранжа.
Формулу (6.7) можно записать в более компактной форме, если ввести обозначение
w(x) = (x – x0) (x – x1) … (x – xn).
Так как
w'(xk) = (xk – x0) (xk – x1) … (xk – xk-1) (xk – xk+1) … (xk – xn),
то
lk(x) = w(x) / ((x – xk) w¢ (xk)).
Тогда
. | (6.9) |
Итак, в результате интерполирования функции мы заменили эту функцию полиномом (6.9), совпадающим с ней в узлах интерполяции x0, x1,...,xn. В остальных точках отрезка [a, b] разность R(x) = y(x) –
– Pn(x) называется остаточным членом интерполяции, представляющим погрешность метода, определяемую следующей теоремой.
Теорема. Если функция y(x) имеет на отрезке [a,b] непрерывные производные до (n+1)-го порядка включительно, то остаточный член интерполяции R(x) определяется формулой
R(x) = y(n+1)(x)w(x)/(n+1)!, a < x < b.
Число арифметических операций для вычисления значений функции y(x) по формуле (6.7) равно Q = 4n (n + 1)» 4n2.
Рассмотрим случай равноотстоящих узлов интерполяции, т.е. когда xi – xi-1 = h, i = = . Сделав замену x=x0+ht, имеем при t0=0,t1=1,...,tn=n, x-xk=h(t-k),
w(x) = hn+1t(t – 1) … (t – n), w¢(xk) = (-1)n-kk!(n – k)!hk.
Тогда выражение (6.9) для интерполяционного многочлена Лагранжа принимает вид
.