Интерполяционный полином Ньютона
Лекции.Орг

Поиск:


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




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

Pn(x)=A0+A1(x-x0)+A2(x-x0)(x-x1)+...+An(x-x0)(x-x1)...(x-xn-1) (5.6)

Коэффициенты этого полинома A0, A1, A2,...,An определяются из условий Лагранжа (5.3).

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

A0 = f0.

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

f0 + A1(x1-x0)= f1,

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

A1 = или A1 = f01.

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

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

Pn(x)= f0+f01(x-x0)+A2(x-x0)(x-x1) ,

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

f2 = f0+f01(x2-x0)+A2(x2-x0)(x2-x1) или f2 -f0-f01(x2-x0) = A2(x2-x0)(x2-x1) ,

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

A2= = = = ,

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

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

A2 = f012 .

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

,

где ; .

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

.

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

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

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

Поэтому в программе, реализующей данный алгоритм, не нужно организовывать двумерный массив. Более того, все разделенные разности, в том числе и диагональные элементы (коэффициенты полинома) можно помещать по мере вычисления на место исходных значений fk. Следовательно, в программе можно ограничиться только двумя массивами: Х-для узлов и F-для значений аппроксимируемой функции. Массив F по мере выполнения программы будет заполняться разделенными разностями, и в конце концов в нем будут получены коэф­фициенты полинома A0,A1,A2,... ,An.

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

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

Pn(x)=A0+(x-x0)(A1+(x-x1)(A2+...+(x-xn-1)An)...)).

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

 

    Разделенные разности  
x f
x0 f0 =A0      
  x1   f1 f01=   =A1      
  x2   f2 f02= f012=   =A2      
  x3   f3 f03= f013= f0123=   =A3  
  x4   f4 f04= f014= f0124= f01234=   =A4
                     

 





Дата добавления: 2015-02-12; просмотров: 565 | Нарушение авторских прав | Изречения для студентов


Читайте также:

Рекомендуемый контект:


Поиск на сайте:



© 2015-2020 lektsii.org - Контакты - Последнее добавление

Ген: 0.004 с.