Математика / Интерполяция

Алгоритм Невилла: интерполяция в одной точке

Рекурсия Невилла вычисляет значение интерполяционного полинома в выбранной точке, последовательно объединяя результаты для соседних узлов. Она удобна, когда нужен один ответ по небольшому набору данных, а строить и хранить весь полином незачем.

Опубликовано: 12 ноября 2026 г.Обновлено: 12 ноября 2026 г.

Формула

P_{i,\ldots,i+m}(x)=\frac{(x-x_{i+m})P_{i,\ldots,i+m-1}(x)+(x_i-x)P_{i+1,\ldots,i+m}(x)}{x_i-x_{i+m}}

Схема Значения интерполяционного полинома

Точки (0;1), (1;2), (2;5) задают полином y=x²+1; маркер показывает вычисление при x=0,5.

Обозначения

$x_i$: i-й узел интерполяции, единица аргумента
$y_i$: значение функции в узле x_i, единица функции
$x$: точка, в которой вычисляется интерполянт, единица аргумента
$P_{i,…,i+m}(x)$: полином степени не выше m по соседним узлам, единица функции
$m$: число шагов объединения (степень не выше m), —

Когда применять

Алгоритм применяют в численном анализе, когда по нескольким табличным значениям требуется оценить функцию в одной заданной точке. Последняя ячейка треугольной таблицы дает искомое значение; промежуточные строки показывают, как линейные интерполянты для соседних узлов объединяются в полиномы все большей степени. Для многих запросов по одним и тем же узлам обычно выгоднее один раз построить форму полинома и затем переиспользовать ее.

Условия применения

Узлы x_i должны быть попарно различны, а данные y_i должны относиться к одной и той же функции или согласованному набору измерений. Рекурсия строится на отрезках соседних узлов: для каждого уровня берут два результата предыдущего уровня и получают полином, проходящий через объединённый набор точек. Если x совпадает с узлом, ответ равен табличному значению; формула также применима вне диапазона узлов, но там это уже экстраполяция.

Ограничения

Алгоритм не устраняет плохую обусловленность самой интерполяционной задачи: при большом числе узлов или неудачном их расположении малые ошибки данных могут заметно влиять на результат. Для высоких степеней возможны осцилляции, поэтому одна вычисленная точка не гарантирует точного восстановления неизвестной функции между узлами. При повторных запросах эффективнее хранить коэффициенты Ньютона или барицентрические веса; при шумных измерениях нужна аппроксимация, а не точное прохождение через все точки.

Подробное объяснение

Начальный уровень таблицы состоит из самих значений: P_{i,i}(x)=y_i.

На следующем уровне два соседних узла задают линейный интерполянт. Общая рекурсия совмещает два полинома, один построен по x_i,…,x_{i+m-1}, другой — по x_{i+1},…,x_{i+m}. Их коэффициенты выбраны так, чтобы сохранить значения на общих узлах, а в точке x получить интерполяционный полином на всём объединённом наборе.

После нескольких уровней остается одно число, равное значению полинома Лагранжа степени не выше числа узлов минус один. Рекурсия вычисляет значение единственного полинома, заданного узлами и данными. Результат совпадает с результатом форм Лагранжа и Ньютона при тех же узлах и данных.

В таблице важно сохранять порядок узлов, явно подписывать целевое x и на каждом шаге использовать именно соседние элементы предыдущего уровня. Различные узлы делают знаменатель x_i−x_{i+m} ненулевым. Для устойчивого ручного счёта полезно оставлять дроби до последнего шага и проверять крайние случаи: при x=x_i ответ должен вернуть y_i, а при двух узлах — совпасть с обычной линейной интерполяцией.

Как пользоваться формулой

Запишите узлы в одном порядке и рядом поставьте соответствующие табличные значения; проверьте, что узлы различны и единицы аргумента согласованы.
Укажите целевое x. В первом столбце таблицы разместите P_{i,i}(x)=y_i для каждого узла.
Для каждой пары соседних элементов предыдущего столбца вычислите значение по рекурсии Невилла, используя внешние узлы этого объединённого интервала.
Продолжайте строить столбцы, пока не останется одно значение для всего набора узлов; это значение интерполянта в x.
Проверьте результат подстановкой в простые граничные случаи и укажите, была ли точка внутри диапазона узлов или за его пределами.

Историческая справка

В первой половине XX века расчёт по таблицам требовал вычислять значения интерполянта без развёртывания всех его коэффициентов. Одну из схем такого расчёта описал Эрик Гарольд Невилл в статье Iterative interpolation, опубликованной в томе 20 журнала Indian Mathematical Society. Именно эту публикацию цитирует Питер Уинн в работе об интерполяции рациональными функциями.

При записи таблицы по соседним наборам узлов линейный шаг обобщается на полиномы старших степеней. Это позволяет после каждого объединения работать с одним числом для фиксированного x. Как видно из единственности полиномиальной интерполяции по различным узлам, итоговое значение совпадает с формами Лагранжа и Ньютона. Современные учебные описания используют имя Невилла для этого вычислительного алгоритма.

Историческая линия формулы

Алгоритм назван в честь Эрика Гарольда Невилла и связан с его работами по конечным разностям и вычислительной математике первой половины XX века. Он вычисляет значение того же полинома, который можно задать формами Лагранжа или Ньютона; историческая атрибуция относится к рекурсивному способу расчёта.

Пример

Пусть известны точки (0; 1), (1; 2), (2; 5), а нужно оценить значение при x=0,5. Узлы различны, и искомая точка лежит внутри диапазона [0; 2], так что это интерполяция. Начальный столбец таблицы: P₀₀=1, P₁₁=2, P₂₂=5. Для первых двух узлов получаем P₀₁=(0,5−1)·1/(0−1)+(0−0,5)·2/(0−1)=1,5. Для узлов 1 и 2: P₁₂=(0,5−2)·2/(1−2)+(1−0,5)·5/(1−2)=0,5. Объединяем результаты для всего набора: P₀₁₂=((0,5−2)·1,5+(0−0,5)·0,5)/(0−2)=1,25. Ответ: 1,25. Проверка независимым способом: заданные значения лежат на параболе y=x²+1; подстановка целевой точки дает 0,5²+1=1,25. Значит, табличная рекурсия согласуется с известным выражением полинома.

Частая ошибка

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

Практика

Задачи с решением

Интерполянт для неравномерных узлов

Условие. Для узлов 0, 1 и 3 известны значения 2, 3 и 11. Найдите интерполянт при x=2.

Решение. Для первых двух узлов получаем P₀₁=2+2·(3−2)=4. Для пары 1 и 3 получаем P₁₂=3+(2−1)·(11−3)/(3−1)=7. При объединении вес первого результата (3−2)/3=1/3, второго 2/3. Сумма 4/3+14/3=6.

Ответ. 6.

Вычисление по трём неравномерным узлам

Условие. Для точек (1; 2), (2; 3), (4; 11) вычислите интерполянт при x=3.

Решение. Для пары 1,2 получаем P₀₁=4; для пары 2,4 получаем P₁₂=7. Тогда P₀₁₂=((3−4)·4+(1−3)·7)/(1−4)=6. Проверка: точки лежат на y=x²−2x+3, при x=3 значение равно 6.

Ответ. 6

Дополнительные источники

https://mathworld.wolfram.com/NevillesAlgorithm.html
https://www.math.kent.edu/~reichel/courses/numerical.analysis.2/Numerical-book.pdf
https://dlmf.nist.gov/3.3
https://mathresearch.utsa.edu/Legacy/Peter-Wynn/downloadable/Interpolation/02_Interpolation_by_the_use_of_rational_functions.pdf

Связанные формулы

Математика

Интерполяция Лагранжа: полином через заданные точки

$P_n(x)=\sum_{k=0}^{n}y_kL_k(x),\qquad L_k(x)=\prod_{\substack{0\leq j\leq n\\j\ne k}}\frac{x-x_j}{x_k-x_j}$

Формула Лагранжа строит полином степени не выше n по n+1 различным узлам. Каждый базисный множитель выбирает значение своего узла и обращает вклады остальных узлов в ноль.

Математика

Интерполяция Ньютона: таблица разделённых разностей

$P_n(x)=f[x_0]+\sum_{k=1}^{n}f[x_0,\ldots,x_k]\prod_{j=0}^{k-1}(x-x_j),\quad f[x_i,\ldots,x_j]=\frac{f[x_{i+1},\ldots,x_j]-f[x_i,\ldots,x_{j-1}]}{x_j-x_i}$

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

Математика

Линейная интерполяция: значение между двумя узлами

$P(x)=y_0+\frac{y_1-y_0}{x_1-x_0}(x-x_0)=(1-t)y_0+ty_1,\quad t=\frac{x-x_0}{x_1-x_0}$

Линейная интерполяция оценивает значение между двумя заданными точками по соединяющей их прямой. Доля положения внутри интервала задаёт веса концов; оценка учитывает наклон, но не кривизну исходного графика.

Математика

Барицентрическая интерполяция: веса и вычисление полинома

$P(x)=\frac{\sum_{k=0}^{n}\dfrac{w_ky_k}{x-x_k}}{\sum_{k=0}^{n}\dfrac{w_k}{x-x_k}},\qquad w_k=\frac{1}{\prod_{j\ne k}(x_k-x_j)},\quad x\ne x_k$

Барицентрическая форма вычисляет полином Лагранжа через заранее рассчитанные веса узлов. Она удобна для множества запросов по одной таблице; при точном совпадении аргумента с узлом нужно сразу вернуть узловое значение.