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

Полином Ньютона для интерполяции имеет вид:

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

Равносильный вариант полинома можно получить при симметричной перенумерации узлов и значений функции в исходной таблице от n до 0:

N_n(x)=B_n+B_n-1(x–x_n)+B_n-2(x–x_n)(x–x_n-1)+...+
+B₀(x–x_n)(x–x_n-1)...(x–x₁)= .

Коэффициенты полиномов определяются из условий Лагранжа

N_n(x_j)=f(x_j), 0≤j≤n

Полагаем x=x₀, тогда в формуле (*) все слагаемые, кроме A₀, обращаются в нуль и A₀=f(x₀).

Затем полагаем x=x₁, тогда f₀+A₁(x₁-x₀)=f₁, откуда находим коэффициент

A₁=(f(x₀)–f(x₁))/(x₀–x₁)=f₀₁,

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

При x=x₂ полином принимает значение

N_n(x₂)=f(x₀)+A₁(x₂–x₀)+A₂(x₂–x₀)(x₂–x₁),

из условия Лагранжа определим искомый коэффициент

A₂=(f₀₁–f₀₂)/(x₁–x₂)=f₀₁₂, где f₀₂=(f(x₀)–f(x₂))/(x₀–x₂).

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

Аналогично при x=x₃ находим коэффициент А₃:

A₃=(f₀₁₂–f₀₁₃)/(x₂–x₃)=f₀₁₂₃,
где f₀₁₃=(f₀₁–f₀₃)/(x₁–x₃), f₀₃=(f(x₀)–f(x₃))/(x₀–x₃).

Для коэффициента A_k методом математической индукции запишем следующее выражение:

A_k=(f₀₁..._k-1–f_01...k)/(x_k-1–x_k).

Полученные результаты сведем в таблицу:

x	f(x)	1	2	3	4
x0	f(x0)
x1	f(x1)	f01=
x2	f(x2)	f02=	f012=
x3	f(x3)	f03=	f013=	f0123=
x4	f(x4)	f04=	f014=	f0124=	f01234=

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

Добавление новых узлов в таблицу не изменит уже вычисленных коэффициентов, таблица будет дополнена новыми строками и столбцами разделенных разностей.

Погрешность полиномиальной аппроксимации функции f(x) определяется соотношением:

.

Так как нам обычно неизвестны заранее производные функции f(x), то по приведенной формуле можно провести апостериорную оценку погрешности, основанную на том, что при достаточно близком расположении узлов разделенные разности являются приближенными оценками производных соответствующего порядка k, деленными на k!.

Поэтому правая часть приведенного неравенства приближенно совпадает по модулю с новым членом полинома Ньютона, появляющимся при добавлении (n+1)-го узла. Таким образом, вычисление модуля каждого из членов суммы (*) позволяет установить, сколько узлов следует использовать для аппроксимации исходной функции с заданной точностью. Если узлы расположены равномерно с шагом h, то наименьшая погрешность будет в интервалах, примыкающих к центральному узлу, за счет минимальной величины произведения в правой части оценки погрешности. Особенно резко возрастает погрешность при попытках экстраполяции.

В центральном интервале оценка погрешности может быть получена по:

|f(x)-N_n(x)|<

После определения коэффициентов полинома Ньютона вычисление его значений при конкретных аргументах x наиболее экономично проводить по схеме Горнера, получаемой последовательным вынесением за скобки множителей (x–x_j) в формуле (*):

N_n(x)=f₀+(x–x₀)(f₀₁+(x–x₁)(f₀₁₂+(x–x₂)(f₀₁₂₃+...)...).

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