Довольно распространенным методом интерполирования является метод Ньютона. Интерполяционный полином для этого метода имеет вид:
Pn(x) = a0 + a1(x-x0) + a2(x-x0)(x-x1) +... + an(x-x0)(x-x1)...(x-xn-1).
Задача состоит в отыскании коэффициентов ai полинома Pn(x). Коэффициенты находят из уравнения:
Pn(xi) = yi, i = 0, 1,..., n,
позволяющего записать систему:
a0 = y0;
a0 + a1(x1 - x0) = y1;
a0 + a1(x2 - x0) + a2(x2 - x0)(x2 - x1) = y2;
- - - - - - - - - - - - - - - - - - - - - - - - - - - -
a0 +... + an(xn - x0)(xn - x1)... (xn - xn-1) = yn;
Используем метод конечных разностей. Если узлы xi заданы через равные промежутки h, т.е.
xi+1 - xi = h,
то в общем случае xi = x0 + i×h, где i = 1, 2,..., n. Последнее выражение позволяет привести решаемое уравнение к виду
y0 = a0;
y1 = a0 + a1×h;
y2 = a0 + a1(2h) + a2(2h)h;
- - - - - - - - - - - - - - - - - - -
yi = a0 + a1×i×h + a2×i×h[(i-1)h] +... + ai×i!×hi,
откуда для коэффициентов получаем
a0 = y0;
,
где Dу0 – первая конечная разность.
Продолжая вычисления, получим:
где D2у0 - вторая конечная разность, представляющая собой разность разностей. Коэффициент аi можно представить в виде:
.
Поставляя найденные значения коэффициентов аi в значения для Pn(x), получим интерполяционный полином Ньютона:
Преобразуем формулу, для чего введем новую переменную , где q – число шагов, необходимых для достижения точки х, двигаясь из точки х0. После преобразований получаем:
Полученная формула известна как первая интерполяционная формула Ньютона, или формула Ньютона для интерполирования "вперед". Ее выгодно использовать для интерполирования функции y = f(x) в окрестности начального значения х – х0, где q мало по абсолютной величине.
Если записать интерполяционный многочлен в виде:
то аналогичным образом можно получить вторую интерполяционную формулу Ньютона, или формулу Ньютона для интерполирования "назад":
.
Ее обычно используют для интерполирования функции вблизи конца таблицы.
При изучении данной темы необходимо помнить, что интерполяционные многочлены совпадают с заданной функцией f(x) в узлах интерполяции, а в остальных точках, в общем случае, будут отличаться. Указанная ошибка дает нам погрешность метода. Погрешность метода интерполяции определяется остаточным членом, который для формул Лагранжа и Ньютона одинаков и который позволяет получить следующую оценку для абсолютной погрешности:
где
Если интерполирование осуществляется с одинаковым шагом, то формула для остаточного члена видоизменяется. В частности, при интерполировании "вперед" и "назад" по формуле Ньютона выражение для R(x) несколько отличаются друг от друга.
Анализируя полученную формулу, видно, что погрешность R(x) представляет собой, с точностью до постоянной произведение двух множителей, из которых один, f(n+1)(x), где x лежит внутри [x0, xn], зависит от свойств функции f(x) и не поддается регулированию, а величина другого,
определяется исключительно выбором узлов интерполирования.
При неудачном расположении этих узлов верхняя граница модуля |R(x)| может быть весьма большой. Поэтому возникает задача о наиболее рациональном выборе узлов интерполирования xi (при заданном числе узлов n) с тем, чтобы полином Пn+1(х) имел наименьшее значение.
Эта задача была решена русским математиком П.Л. Чебышевым, который доказал, что наилучший выбор в указанном смысле узлов интерполирования на отрезке [a, b] дается формулой
где
, i = 0,1,…,n
- нули так называемого полинома Чебышева:
.
В этом случае мы будем иметь:
.
Отметим, что эти узлы не являются равноотстоящими, а сгущаются около концов отрезка [a, b].