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

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

P n(x)= A 0+ A 1(x - x 0)+ A 2(x - x 0)(x - x 1)+...+ A n(x - x 0)(x - x 1)...(x - x n-1)

(5.6)

Коэффициенты этого полинома A ₀, A ₁, A ₂,..., A _n определяются из условий Лагранжа (5.3).

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

A ₀ = f ₀.

Затем полагаем x = x ₁, тогда из (5.3) имеем:

f ₀ + A ₁(x ₁- x ₀)= f ₁,

откуда находим коэффициент A ₁:

A ₁ = или A ₁ = f ₀₁.

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

При x = x ₂ полином (5.6) принимает вид:

P _n(x)= f ₀+ f ₀₁(x - x ₀)+ A ₂(x - x ₀)(x - x ₁),

откуда с учетом (5.3) получаем:

f ₂ = f ₀+ f ₀₁(x ₂- x ₀)+ A ₂(x ₂- x ₀)(x ₂- x ₁) или f ₂ - f ₀- f ₀₁(x ₂- x ₀) = A ₂(x ₂- x ₀)(x ₂- x ₁),

следовательно, коэффициент A ₂:

A ₂= = = = ,

где . Обозначая = f ₀₁₂ (разделенная разность второго порядка),

окончательно получаем выражение для A ₂:

A ₂ = f ₀₁₂ .

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

,

где ; .

Методом математической индукции можно получить для любого A _k (k=0,...,n) следующее выражение:

.

Полученные результаты сведены в представленной ниже таблице.

Следует отметить, что добавление новых узлов в исходных данных не изменяет уже вычисленные коэффициенты; таблица будет лишь дополняться новыми строками и столбцами.

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

Поэтому в программе, реализующей данный алгоритм, не нужно организовывать двумерный массив. Более того, все разделенные разности, в том числе и диагональные элементы (коэффициенты полинома) можно помещать по мере вычисления на место исходных значений f _k. Следовательно, в программе можно ограничиться только двумя массивами: Х -для узлов и F -для значений аппроксимируемой функции. Массив F по мере выполнения программы будет заполняться разделенными разностями, и в конце концов в нем будут получены коэф­фициенты полинома A ₀, A ₁, A ₂,..., A _n.

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

После определения коэффициентов A ₀, A ₁, A ₂,..., A _n вычисление значений полинома Ньютона при конкретных аргументах x рекомендуется выполнять также по схеме Горнера, для чего полином (5.8) надо преобразовать к виду:

P _n(x)= A ₀+(x-x ₀)(A ₁+(x-x ₁)(A ₂+...+(x-x _n-1) A _n)...)).

На рис.5.4 представлена блок-схема вычисления коэффициентов полинома Ньютона и его значений в точках интерполяции по схеме Горнера.

 

		Разделенные разности
x	f
x 0	f 0	= A 0
x 1	f 1	f 01=	= A 1
x 2	f 2	f 02=	f 012=	= A 2
x 3	f 3	f 03=	f 013=	f 0123=	= A 3
x 4	f 4	f 04=	f 014=	f 0124=	f 01234=	= A 4