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

По данным табл. 2.1 построим интерполяционный полином степени п в виде, предложенном Ньютоном:

. (2.6)

Равносильный вариант полинома можно записать при симметричной перенумерации узлов исходной таблицы 0 →n, 1→n-1, 2→n-2,…

(2.7)

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

. (2.8)

Полагаем , тогда в формуле (2.6) все слагаемые, кроме , обращаются в нуль, следовательно,

(2.9)

Затем полагаем , тогда по условию (2.8)

,

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

(2.10)

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

При х = полином (2.6) принимает значение

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

, (2.11)

где

 

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

Аналогичным образом при х = находим коэффициент полинома Ньютона

(2.12)

где

 

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

(2.13)

Полученные результаты сведем в табл. 2.2.

Таблица 2.2. Разделенные Разности

x		Порядок разделенной разности

 

 

Для построения интерполяционного полинома Ньютона использу­ются только диагональные элементы приведенной таблицы, остальные элементы являются промежуточными данными. Поэтому в программе, реализующей вычисление коэффициента полинома, разделенные раз­ности для экономии памяти целесообразно размещать в массиве, где первоначально хранились значения функции f(x) в узлах. Этот мас­сив будет частично обновляться при вычислении разделенных разно­стей очередного порядка. Так, при вычислении разностей первого по­рядка элемент остается неизменным (коэффициент (2.9)), элемент заменяется на (коэффициент (2.10)), — на и т.д. При вычислении разделенных разностей второго порядка первые два эле­мента массива , где размещены коэффициенты и полинома, оставляем неизменными, остальные элементы заменяем разделенными разностями.

Таким образом, после вычисления все коэффициенты полинома Нью­тона будут размещены последовательно в массиве узловых значений функции f(x).

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

Предлагаемая схема вычислений коэффициентов интерполяцион­ного полинома Ньютона согласно табл. 2.2 обладает рядом преиму­ществ по сравнению с классической схемой [2, 1 ]. Во-первых, обес­печивается меньшая погрешность вычисления разделенных разностей при близко расположенных узлах за счет меньшего количества вычи­таний близких чисел. Во-вторых, сокращается количество обращений к элементам массивов узлов и значений функции f(x), так как в фор­мулах для разделенных разностей уменьшаемые в числителе и зна­менателе остаются неизвестными для разности каждого порядка. В-третьих, аналитические выражения для коэффициентов полинома Нью­тона получаются более простым способом.

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

(2.14)

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

Погрешность полиномиальной аппроксимации функции определя­ется соотношением [2]:

(2.15)

где

Оценку погрешности (2.15) можно провести до вычисления интер­поляционного полинома, подобная оценка называется априорной. Од­нако обычно заранее нам не известны производные функции f(x), по­этому в вычислительной практике используют апостериорную оценку, т.е. оценку после вычислений. Апостериорная оценка основана на том, что в случае близкого расположения узлов разделенные разности яв­ляются приближенными значениями производных соответствующего порядка к, деленными на к!. Поэтому правая часть неравенства (2.15) приближенно совпадает по модулю с новым членом полинома Ньюто­на (2.6), появляющимся при добавлении (п + 1) -го узла. Таким об­разом, вычисление модуля каждого из членов суммы (2.6) позволяет установить, сколько узлов следует использовать для аппроксимации исходной функции f(x) с заданной погрешностью.

Если узлы Xfc расположены равномерно с шагом h, то наименьшая погрешность будет в интервалах, примыкающих к центральному узлу, за счет минимальной величины произведения в правой части оценки (2.15). Особенно резко увеличивается погрешность при экстраполя­ции. В центральном интервале (при четном количестве узлов) получена следующая оценка погрешности [2, 1 ]:

. (2.16)