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

Пусть х ₀, х ₁ ,..., х_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= D y_{k+ 1} – D y_k - конечной разностью второго порядка,...,

D ⁿy_k= D ^{n– 1} y_{k+ 1} – D ^{n– 1} y_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 ,...

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

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

xк	yк	D1 y	D2 y 0	D3 y 0

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

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

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

.

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

.