По данным табл. 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)
где
Величинаf012 называется разделенной разностью второго порядка, которая при близком расположении будет пропорциональна второй производной функции f(x).
Аналогичным образом при х = находим коэффициент полинома Ньютона
,(2.12)
где
Для коэффициента Akметодом математической индукции запишем следующее выражение:
(2.13)
Полученные результаты сведем в табл. 2.2.
Таблица 2.2. Разделенные Разности
| x | Порядок разделенной разности | |||
| f0 | ||||
| Продолжение табл. 2.2 | ||||
Для построения интерполяционного полинома Ньютона используются только диагональные элементы приведенной таблицы, остальные элементы являются промежуточными данными. Поэтому в программе, реализующей вычисление коэффициента полинома, разделенные разности для экономии памяти целесообразно размещать в массиве, где первоначально хранились значения функции f(x) в узлах. Этот массив будет частично обновляться при вычислении разделенных разностей очередного порядка. Так, при вычислении разностей первого порядка элемент остается неизменным (коэффициент (2.9)), элемент заменяется на (коэффициент (2.10)), — на и т.д. При вычислении разделенных разностей второго порядка первые два элемента массива , где размещены коэффициенты и полинома, оставляем неизменными, остальные элементы заменяем разделенными разностями.
Таким образом, после вычисления все коэффициенты полинома Ньютона будут размещены последовательно в массиве узловых значений функции f(x).
Заметим, что добавление новых узлов в табл. 2.2 не изменит уже вычисленных коэффициентов, таблица будет дополнена новыми строками и столбцами разделенных разностей.
Предлагаемая схема вычислений коэффициентов интерполяционного полинома Ньютона согласно табл. 2.2 обладает рядом преимуществ по сравнению с классической схемой [1, 2 ]. Во-первых, обеспечивается меньшая погрешность вычисления разделенных разностей при близко расположенных узлах за счет меньшего количества вычитаний близких чисел. Во-вторых, сокращается количество обращений к элементам массивов узлов и значений функции f(x), так как в формулах для разделенных разностей уменьшаемые в числителе и знаменателе остаются неизвестными для разности каждого порядка. В-третьих, аналитические выражения для коэффициентов полинома Ньютона получаются более простым способом.
После определения коэффициентов полинома Ньютона вычисление его значений при конкретных аргументах х наиболее экономично проводить по схеме Горнера, получаемой путем последовательного вынесения за скобки множителей в формуле (2.6):
(2.14)
В отличие от алгоритма вычисления полинома Лагранжа при интерполировании полиномом Ньютона удается разделить задачи определения коэффициентов и вычисления значений полинома при различных значениях аргумента х. Аналогичное разделение задач происходит при интерполяции каноническим полиномом (см. п. 2.1).
Погрешность полиномиальной аппроксимации функции определяется соотношением [2]:
(2.15)
| . |
Оценку погрешности (2.15) можно провести до вычисления интерполяционного полинома, подобная оценка называется априорной. Однако обычно заранее нам не известны производные функции f(x), поэтому в вычислительной практике используют апостериорную оценку, т.е. оценку после вычислений. Апостериорная оценка основана на том, что в случае близкого расположения узлов разделенные разности являются приближенными значениями производных соответствующего порядкаk, деленными на k!. Поэтому правая часть неравенства (2.15) приближенно совпадает по модулю с новым членом полинома Ньютона (2.6), появляющимся при добавлении (п + 1) -го узла. Таким образом, вычисление модуля каждого из членов суммы (2.6) позволяет установить, сколько узлов следует использовать для аппроксимации исходной функции f(x) с заданной погрешностью.
Если узлы xkрасположены равномерно с шагом h, то наименьшая погрешность будет в интервалах, примыкающих к центральному узлу, за счет минимальной величины произведения в правой части оценки (2.15). Особенно резко увеличивается погрешность при экстраполяции. В центральном интервале (при четном количестве узлов) получена следующая оценка погрешности [1, 2 ]:
. (2.16)