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

В математике алгоритм Невилла — это алгоритм, используемый для полиномиальной интерполяции , который был выведен математиком Эриком Гарольдом Невиллом в 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} удовлетворяют рекуррентному соотношению

$p_{i,i}(x)=y_{i},\,$	$0\leq i\leq n,\,$
$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}}},\,$	$0\leq i<j\leq n.\,$

Это повторение можно вычислить п _{0, п} ( х ), какова искомая ценность. Это алгоритм Невилла.

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

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

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

Этот алгоритм требует O ( n ² ) операции с плавающей запятой для интерполяции одной точки и O ( n ³ ) операции с плавающей запятой для интерполяции полинома степени n.

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

$p'_{i,i}(x)=0,\,$	$0\leq i\leq n,\,$
$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}}},\,$	$0\leq i<j\leq n.\,$

Приложение к численному дифференцированию

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

Ссылки

• Пресс, Уильям; Саул Теукольский; Уильям Веттерлинг; Брайан Флэннери (1992). «§3.1 Полиномиальная интерполяция и экстраполяция (зашифровано)» (PDF) . Численные рецепты в C. Искусство научных вычислений (2-е изд.). Издательство Кембриджского университета. ISBN  978-0-521-43108-8 . (ссылка плохая)
• Дж. Н. Лайнесс и К. Б. Молер, Системы Ван дер Монда и числовое дифференцирование, Numerische Mathematics 8 (1966) 458-464 ( doi: 10.1007/BF02166671 )
• Невилл, Э.Х.: Итеративная интерполяция. Дж. Индийская математика. Сок.20, 87–120 (1934)

Внешние ссылки

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