Программирование формулы Лагранжа

Свернем формулу Лагранжа (11.6). В результате получим

где

но при этом обязательно выполнение условия .

При построении алгоритма используют конструкцию из двух включенных циклов:

Внешним циклом накапливаем сумму .

Внутренним циклом накапливаем произведение .

Алгоритм (рис.11.3) не предусматривает получение интерполяционного многочлена в явном виде, а сразу решает задачу интерполирования функции в заданной точке, x=D.

Обозначения в алгоритме:

n - степень интерполяционного многочлена Лагранжа (11.6), равная количеству узловых точек N минус один, т.е. n=N-1.

D - значение аргумента в точке, для которой решается задача интерполирования табличной функции (11.1).

L - значение многочлена (11.6).

Рис. 11.3. Схема алгоритма интерполяции по Лагранжу

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

Дана табличная функция:

i	xi	yi
0	x0	y0
1	x1	y1
2	x2	y2
...	...	...
n	xn	yn

или

(11.1)

Точки с координатами (x_i, y_i) называются узловыми точками или узлами.

Количество узлов в табличной функции равно

N=n+1.

Необходимо найти значение этой функции в промежуточной точке, например, x=D, причем .

Для решения задачи строим интерполяционный многочлен.

Интерполяционный многочлен по формуле Ньютона имеет вид:

(11.7)

где

n - степень многочлена,

- разделенные разности 0-го, 1-го, 2-го,:., n-го порядка, соответственно.

Разделенные разности

Значения f(x₀), f(x₁),:, f(x_n), т.е. значения табличной функции в узлах, называются разделенными разностями нулевого порядка (k=0).

Отношение называется разделенной разностью первого порядка (k=1) на участке [x₀, x₁] и равно разности разделенных разностей нулевого порядка на концах участка [x₀, x₁], разделенной на длину этого участка.

Для произвольного участка [x_i, x_i+1] разделенная разность первого порядка (k=1) равна

Отношение называется разделенной разностью второго порядка (k=2) на участке [x₀, x₂] и равно разности разделенных разностей первого порядка, разделенной на длину участка [x₀, x₂].

Для произвольного участка [x_i, x_i+2] разделенная разность второго порядка (k=2) равна

Таким образом, разделенная разность k-го порядка на участке [x_i, x_i+k] может быть определена через разделенные разности (k-1)-го порядка по рекуррентной формуле:

(11.8)

где

n - степень многочлена.

Максимальное значение k равно n. Тогда i =0 и разделенная разность n-го порядка на участке [x₀,x_n] равна , т.е. равна разности разделенных разностей (n-1)-го порядка, разделенной на длину участка [x₀,x_n].

Разделенные разности являются вполне определенными числами, поэтому выражение (11.7) действительно является алгебраическим многочленом n-й степени. При этом в многочлене (11.7) все разделенные разности определены для участков [x₀, x_0+k], .

Лемма: алгебраический многочлен (11.7), построенный по формулам Ньютона, действительно является интерполяционным многочленом, т.е. значение многочлена в узловых точках равно значению табличной функции

Докажем это. Пусть х=х₀, тогда многочлен (11.7) равен

Пусть х=х₁, тогда многочлен (11.7) равен

Пусть х=х₂, тогда многочлен (11.7) равен

Заметим, что решение задачи интерполяции по Ньютону имеет некоторые преимущества по сравнению с решением задачи интерполяции по Лагранжу. Каждое слагаемое интерполяционного многочлена Лагранжа зависит от всех значений табличной функции y_i, i=0,1,:n. Поэтому при изменении количества узловых точек N и степени многочлена n (n=N-1) интерполяционный многочлен Лагранжа требуется строить заново. В многочлене Ньютона при изменении количества узловых точек N и степени многочлена n требуется только добавить или отбросить соответствующее число стандартных слагаемых в формуле Ньютона (11.7). Это удобно на практике и ускоряет процесс вычислений.