네빌 알고리즘

수학에서 네빌의 알고리즘은 수학자 에릭 해롤드 네빌이^{[citation needed]} 도출한 다항식 보간술에 사용되는 알고리즘이다.n + 1점을 부여하면 주어진 점을 통과하는 ≤ n의 고유한 다항식이 있다.네빌의 알고리즘은 이 다항식을 평가한다.

네빌의 알고리즘은 보간 다항식의 뉴턴 형태와 분단 차이에 대한 재귀 관계를 기반으로 한다.오늘날에는 사용되지 않는 아이트켄의 알고리즘(알렉산더 에이트켄의 이름을 딴 이름)과 비슷하다.

알고리즘

두_i x가 같지 않은 n+1 데이터 점_i 집합(x_i, y)이 주어진 경우, 보간 다항식은 속성과 함께 최대 n의 다항 p이다.

p(x_i) = 모든 i에 대한_i y = 0,……,n

이 다항식은 존재하며 독특하다.네빌의 알고리즘은 다항식을 어떤 지점 x에서 평가한다.

p는_i,j k = i, i + 1, j에 대한 점(x_k, y_k)을 통과하는 도 j - i의 다항식을 나타낸다.p는_i,j 재발 관계를 만족한다.

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

이 반복은 찾고 있는 값인 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(x)를_0,4 산출하는데, p(x)는 x 지점에서 n + 1 데이터 점(x_i, y_i)을 거치는 다항식의 값이다.

이 알고리즘은 단일 점을 보간하기 위해 O(n²) 부동소수점 연산이 필요하고, 도 n의 다항식을 보간하기 위해서는 O(n³) 부동소수 연산이 필요하다.

다항식의 파생상품은 동일한 방법으로 구할 수 있다. 즉, 다음과 같다.

${\displaystyle p'_{i,i}(x)=0,\,}$	$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}}},\,}$	$##################################,}$

수치적 분화에 대한 적용

리니스와 몰러는 1966년 네빌 알고리즘의 다항식 계수에 대해 결정되지 않은 계수를 사용하여 원점에서 함수 파생에 대한 수치적 근사를 산출하는 최종 보간 다항식의 마클로린 확장을 계산할 수 있다는 것을 보여주었다."이 공정은 유한 차이 방법에서 요구되는 것보다 더 많은 산술 연산이 필요하다"는 반면, "함수 평가를 위한 점의 선택은 어떤 식으로든 제한되지 않는다"는 것이다.그들은 또한 그들의 방법이 밴더몬드 유형의 선형 시스템 해법에 직접 적용될 수 있다는 것을 보여준다.

참조

• Press, William; Saul Teukolsky; William Vetterling; Brian Flannery (1992). "§3.1 Polynomial Interpolation and Extrapolation (encrypted)" (PDF). Numerical Recipes in C. The Art of Scientific Computing (2nd ed.). Cambridge University Press. doi:10.2277/0521431085. ISBN 978-0-521-43108-8. (링크 불량)
• J. N. 리니스와 C.B.몰러, 반 데르 몬드 시스템 및 수치 구분, 수문수학 8 (1966) 458-464 (doi: 10.1007/BF02166671)
• 네빌, E.H.:반복 보간법.J. 인디안 수학.Soc.20, 87–120 (1934년)

외부 링크

• Weisstein, Eric W. "Neville's Algorithm". MathWorld.