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

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

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

Алгоритм

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

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

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

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

${ Displaystyle р_ {я, я} (х) = у_ {я}, ,}$	${ Displaystyle 0 Leq я Leq п, ,}$
${ 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 я$

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

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

${ Displaystyle p_ {0,0} (х) = y_ {0} ,}$
	${ Displaystyle p_ {0,1} (х) ,}$
${ Displaystyle p_ {1,1} (х) = y_ {1} ,}$		${ Displaystyle p_ {0,2} (х) ,}$
	${ Displaystyle p_ {1,2} (х) ,}$		${ Displaystyle p_ {0,3} (х) ,}$
${ Displaystyle p_ {2,2} (х) = y_ {2} ,}$		${ Displaystyle p_ {1,3} (х) ,}$		${ Displaystyle p_ {0,4} (х) ,}$
	${ Displaystyle p_ {2,3} (х) ,}$		${ Displaystyle p_ {1,4} (х) ,}$
${ Displaystyle p_ {3,3} (х) = y_ {3} ,}$		${ Displaystyle p_ {2,4} (х) ,}$
	${ Displaystyle p_ {3,4} (х) ,}$
${ Displaystyle p_ {4,4} (х) = y_ {4} ,}$

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

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

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

${ Displaystyle р '_ {я, я} (х) = 0, ,}$	${ Displaystyle 0 Leq я Leq п, ,}$
${ 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 я$

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

Лайнесс и Молер показали в 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 от Бехзада Торкиана