ИНТЕРПОЛЯЦИОННЫЙ ПОЛИНОМ НЬЮТОНА

Пусть х₀, х₁,..., х_n – произвольные попарно не совпадающие узлы, в которых известны значения функции f. Запишем полином степени n в виде

N_n(x)=A₀+A₁(x–x₀)+ A₂(x–x₀)(x–x₁)+...+A_n(x–x₀)(x–x₁)...(x–x_n–1).

Если выполняются условия (2.4)

N_n(x_i)=f(x_i), i=0, 1, ..., n,

то полином будет интерполяционным. Его коэффициенты найдутся из этих условий.

Положим х=х₀, тогда f(x₀)=A₀. Коэффициент А₀ определен.

Положим х=х₁, тогда f(x₁) =f(x₀)+A₁(x₁–x₀).

Отсюда . Этот коэффициент называется разделенной разностью первого порядка. При малом расстоянии между узлами х₁ и х₀ величина f(x₀; x₁) близка к первой производной функции f(x).

Положим х=х₂ , тогда f(x₂)= f(x₀)+f(x₀; x₁)(x₂–x₀)+A₂(x₂–x₀)(x₂–x₁).

Отсюда ,

где .

Величина f(x₀; x₁; x₂) называется разделенной разностью второго порядка, и при малом расстоянии между х₀, х₁, х₂ она близка ко второй производной функции f(x).

Аналогично находятся все остальные коэффициенты:

Полином вида

называется интерполяционным полиномом Ньютона для неравных промежутков. Он тождественно совпадает с интерполяционным полиномом Лагранжа, так что все суждения о погрешности L_n(x) остаются в силе и для N_n(x).

Сравним эти две формы интерполяционных полиномов.

Полином Лагранжа явно зависит от каждого значения функции f_i,поэтому при изменении n полином требуется строить заново. Полином Ньютона выражается не через значения функции f, а через ее разделенные разности. При изменении n у него требуется только добавить или отбросить соответствующее число стандартных слагаемых. Поэтому интерполяционный полином Ньютона удобнее использовать, когда интерполируется одна и та же функция, но число узлов может меняться. Если же узлы фиксированы и интерполируется не одна, а несколько функций, то удобнее пользоваться интерполяционным полиномом Лагранжа.

Кроме того, в формуле Ньютона безразличен порядок, в котором пронумерованы узлы интерполяции. Это дает возможность подключать (или убирать) любые узловые точки в процессе построения интерполяционного полинома, причем в произвольном порядке. Пусть, например, необходимо вычислить значение функции в точке х, лежащей между узловыми точками х₈ и х₉некоторой таблицы. Перенумеровываем таблицу: х₉« х₀ ; х₈ « х₁ ; х₁₀ « х₂ ; х₇ « х₃ ; и так далее. Одновременно начинаем строить почленно интерполяционный полином Ньютона и вычислять значение f(x) с необходимой точностью.

Рассмотрим частные случаи интерполяционного многочлена Ньютона для таблиц с постоянным шагом.

1. Интерполяционный полином Ньютона для интерполирования вперед.

Пусть x_i = x₀+ih, h > 0, i = 0, 1,..., n.

Введем новую переменную t=(x – x₀)/h.

Тогда x – x₀ = t×h, x – x₁ = (t – 1)×h, ..., x – x_k = (t – k)×h и интерполяционный полином Ньютона можно записать в виде

Назовем D¹y_k = y_k+1 – y_k конечной разностью первого порядка, D²y_k=Dy_k+1 – D y_k - конечной разностью второго порядка, ...,

Dⁿy_k=D^n–1y_k+1 – D^n–1y_k - конечной разностью n-ого порядка.

Здесь у_k = f(x_k).

Конечные разности обладают следующими свойствами:

1) связь с производными: Dⁿy_k » hⁿf⁽ⁿ⁾(x), в частности для полиномов Dⁿy_k = a_nhⁿn!;

2) связь со значениями функции: , (2.7)

где – коэффициенты бинома Ньютона;

3) связь с разделенными разностями:

Тогда интерполяционный полином Ньютона можно переписать в виде

Остаточный член этой интерполяционной формулы имеет вид:

Видно, что с точки зрения уменьшения погрешности, целесообразно ограничиться случаем t<1, то есть использовать эту формулу при х₀<x<x₁ .

Для других значений аргумента, например для х₁<x<x₂,лучше взять в качестве начального значения х₁ и так далее.

Таким образом, можно записать

,

где ; i=0, 1, 2,...

Это первый интерполяционный полином Ньютона для интерполирования вперед. Его обычно используют для вычисления значений табличной функции в точках левой половины рассматриваемого отрезка, а также для экстраполяции влево (при t<0).

2. Интерполяционный полином Ньютона для интерполирования назад.

Для правой половины рассматриваемого отрезка разности лучше вычислять справа налево. Тогда t=(x – x_n)/h , –1<t<0и

Здесь x_n–1<x<x_n .

Аналогично предыдущему можно записать

i=n, n–1, n–2,...

Это второй интерполяционный полином Ньютона для интерполирования назад. Используется для вычисления значений табличной функции в точках правой половины рассматриваемого отрезка, а также для экстраполяции вправо.

Пример. Построить интерполяционный полином, если задана следующая таблица:

1. Интерполяционный полином Лагранжа

2. Интерполяционный полином Ньютона.

3. Интерполяционный полином Ньютона для интерполирования вперед. t=(x – 4)/2.

.

4. Интерполяционный полином Ньютона для интерполирования назад. t=(x – 10)/2.

.