Свернем формулу Лагранжа (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) |
Точки с координатами (xi, yi) называются узловыми точками или узлами.
Количество узлов в табличной функции равно
N=n+1.Необходимо найти значение этой функции в промежуточной точке, например, x=D, причем 
.
Для решения задачи строим интерполяционный многочлен.
Интерполяционный многочлен по формуле Ньютона имеет вид:
| (11.7) |
где
n - степень многочлена,
- разделенные разности 0-го, 1-го, 2-го,:., n-го порядка, соответственно.
Разделенные разности
Значения f(x0), f(x1),:, f(xn), т.е. значения табличной функции в узлах, называются разделенными разностями нулевого порядка (k=0).
Отношение 
называется разделенной разностью первого порядка (k=1) на участке [x0, x1] и равно разности разделенных разностей нулевого порядка на концах участка [x0, x1], разделенной на длину этого участка.
Для произвольного участка [xi, xi+1] разделенная разность первого порядка (k=1) равна
Отношение 
называется разделенной разностью второго порядка (k=2) на участке [x0, x2] и равно разности разделенных разностей первого порядка, разделенной на длину участка [x0, x2].
Для произвольного участка [xi, xi+2] разделенная разность второго порядка (k=2) равна
Таким образом, разделенная разность k-го порядка на участке [xi, xi+k] может быть определена через разделенные разности (k-1)-го порядка по рекуррентной формуле:
| (11.8) |
где
n - степень многочлена.
Максимальное значение k равно n. Тогда i =0 и разделенная разность n-го порядка на участке [x0,xn] равна 
, т.е. равна разности разделенных разностей (n-1)-го порядка, разделенной на длину участка [x0,xn].
Разделенные разности 
являются вполне определенными числами, поэтому выражение (11.7) действительно является алгебраическим многочленом n-й степени. При этом в многочлене (11.7) все разделенные разности определены для участков [x0, x0+k], 
.
Лемма: алгебраический многочлен (11.7), построенный по формулам Ньютона, действительно является интерполяционным многочленом, т.е. значение многочлена в узловых точках равно значению табличной функции
Докажем это. Пусть х=х0, тогда многочлен (11.7) равен
Пусть х=х1, тогда многочлен (11.7) равен
Пусть х=х2, тогда многочлен (11.7) равен
Заметим, что решение задачи интерполяции по Ньютону имеет некоторые преимущества по сравнению с решением задачи интерполяции по Лагранжу. Каждое слагаемое интерполяционного многочлена Лагранжа зависит от всех значений табличной функции yi, i=0,1,:n. Поэтому при изменении количества узловых точек N и степени многочлена n (n=N-1) интерполяционный многочлен Лагранжа требуется строить заново. В многочлене Ньютона при изменении количества узловых точек N и степени многочлена n требуется только добавить или отбросить соответствующее число стандартных слагаемых в формуле Ньютона (11.7). Это удобно на практике и ускоряет процесс вычислений.
