Алгоритм Невилла

В математике алгоритм Невилла — это алгоритм, используемый для полиномиальной интерполяции , который был выведен математиком Эриком Гарольдом Невиллом в 1934 году. При наличии n + 1 точек существует единственный полином степени ≤ n , который проходит через заданные точки. Алгоритм Невилла вычисляет этот полином.

Алгоритм Невилла основан на форме Ньютона интерполирующего полинома и рекурсивном соотношении для разделенных разностей . Он похож на алгоритм Эйткена (названный в честь Александра Эйткена ), который в настоящее время не используется.

Для заданного набора из n +1 точек данных ( x _i , y _i ), где нет двух одинаковых x _i , интерполирующий многочлен — это многочлен p степени не выше n со свойством

p ( x _i ) = y _i для всех i = 0,..., n

Этот многочлен существует и он уникален. Алгоритм Невилла вычисляет многочлен в некоторой точке x .

Пусть p _{i , j} обозначает многочлен степени j − i , который проходит через точки ( x _k , y _k ) для k = i , i + 1, ..., j . P _{i , j} удовлетворяют рекуррентному соотношению

${\displaystyle p_{i,i}(x)=y_{i},\,}$	${\displaystyle 0\leq i\leq n,\,}$
${\displaystyle p_{i,j}(x)={\frac {(x-x_{i})p_{i+1,j}(x)-(x-x_{j})p_{i,j-1}(x)}{x_{j}-x_{i}}},\,}$	${\displaystyle 0\leq i<j\leq n.\,}$

Эта рекуррентность может вычислить p _{0, n} ( x ), что является искомым значением. Это алгоритм Невилла.

Например, для n = 4 можно использовать рекуррентное соотношение для заполнения треугольной таблицы ниже слева направо.

${\displaystyle p_{0,0}(x)=y_{0}\,}$
	${\displaystyle p_{0,1}(x)\,}$
${\displaystyle p_{1,1}(x)=y_{1}\,}$		${\displaystyle p_{0,2}(x)\,}$
	${\displaystyle p_{1,2}(x)\,}$		${\displaystyle p_{0,3}(x)\,}$
${\displaystyle p_{2,2}(x)=y_{2}\,}$		${\displaystyle p_{1,3}(x)\,}$		${\displaystyle p_{0,4}(x)\,}$
	${\displaystyle p_{2,3}(x)\,}$		${\displaystyle p_{1,4}(x)\,}$
${\displaystyle p_{3,3}(x)=y_{3}\,}$		${\displaystyle p_{2,4}(x)\,}$
	${\displaystyle p_{3,4}(x)\,}$
${\displaystyle p_{4,4}(x)=y_{4}\,}$

Этот процесс дает p _0,4 ( x ), значение полинома, проходящего через n + 1 точек данных ( x _i , y _i ) в точке x .

Для интерполяции одной точки этому алгоритму требуется O ( n ² ) операций с плавающей точкой, а для интерполяции полинома степени n — O ( n ^{3 ) операций с плавающей точкой.}

Производную полинома можно получить тем же способом, то есть:

${\displaystyle p'_{i,i}(x)=0,\,}$	${\displaystyle 0\leq i\leq n,\,}$
${\displaystyle p'_{i,j}(x)={\frac {(x_{j}-x)p'_{i,j-1}(x)-p_{i,j-1}(x)+(x-x_{i})p'_{i+1,j}(x)+p_{i+1,j}(x)}{x_{j}-x_{i}}},\,}$	${\displaystyle 0\leq i<j\leq n.\,}$

В 1966 году Лайнесс и Молер показали, что, используя неопределенные коэффициенты для полиномов в алгоритме Невилла, можно вычислить разложение Маклорена окончательного интерполирующего полинома, что дает численные приближения для производных функции в начале координат. Хотя «этот процесс требует больше арифметических операций, чем требуется в методах конечных разностей», «выбор точек для оценки функции никак не ограничен». Они также показывают, что их метод может быть применен непосредственно к решению линейных систем типа Вандермонда.

• Press, William; Saul Teukolsky; William Vetterling; Brian Flannery (1992). "§3.1 Полиномиальная интерполяция и экстраполяция (зашифровано)" (PDF) . Numerical Recipes in C. The Art of Scientific Computing (2nd ed.). Cambridge University Press. ISBN 978-0-521-43108-8.(ссылка плохая)
• Дж. Н. Лайнесс и К. Б. Молер, Системы Ван дер Монда и числовое дифференцирование, Numerische Mathematik 8 (1966) 458-464 (doi: 10.1007/BF02166671)
• Невилл, Э. Х.: Итеративная интерполяция. J. Indian Math. Soc.20, 87–120 (1934)

• Вайсштейн, Эрик В. «Алгоритм Невилла». MathWorld .