Алгоритм Невиля - Nevilles algorithm

В математике Алгоритм Невилла алгоритм, используемый для полиномиальная интерполяция что было выведено математиком Эрик Гарольд Невилл^{[нужна цитата ]}. Данный п +1 балл, существует единственный многочлен степени ≤ п который проходит через данные точки. Алгоритм Невилла вычисляет этот многочлен.

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

Алгоритм

Учитывая набор п+1 точки данных (Икс_я, у_я) где нет двух Икс_я одинаковы, интерполирующий полином - это полином п степени не более п с собственностью

п(Икс_я) = у_я для всех я = 0,…,п

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

Позволять п_я,j обозначим многочлен степени j − я который проходит через точки (Икс_k, у_k) за k = я, я + 1, …, j. В п_я,j удовлетворяют рекуррентному соотношению

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

Это повторение можно вычислитьп_0,п(Икс), что и является искомым значением. Это алгоритм Невилла.

Например, для п = 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}\,}$

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

Этот алгоритм требует О (п²) операции с плавающей запятой.

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

${\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 году, что, используя неопределенные коэффициенты для многочленов в алгоритме Невилла, можно вычислить разложение Маклорена последнего интерполяционного многочлена, которое дает численные приближения для производных функции в начале координат. Хотя «этот процесс требует больше арифметических операций, чем требуется в методах конечных разностей», «выбор точек для оценки функции никоим образом не ограничен». Они также показывают, что их метод может быть применен непосредственно к решению линейных систем типа Вандермонда.

Рекомендации

• Пресс, Уильям; Саул Теукольский; Уильям Веттерлинг; Брайан Флэннери (1992). «§3.1 Полиномиальная интерполяция и экстраполяция (зашифрованные)» (PDF). Числовые рецепты в C. Искусство научных вычислений (2-е изд.). Издательство Кембриджского университета. Дои:10.2277/0521431085. 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.
• Код Java от Бехзада Торкиана