다항식 보간법

수치해석학에서 **다항식 보간법**(Polynomial interpolation)은 주어진 자료 집합의 점들을 통과하는 가장 낮은 차수의 다항식으로 보간법을 하는 것이다.

서로 다른 개의 자료점 (x_0,y_0), \ldots, (x_n,y_n)이 주어졌을 때, 다항 함수 p(x)=a_0+a_1x+\cdots+a_nx^n가 각 j\in\{0,1,\dotsc,n\}에 대해 p(x_j)=y_j를 만족하면 자료를 **보간**한다고 말한다.

이러한 다항식은 항상 유일하며, 일반적으로 라그랑주 다항식과 뉴턴 다항식의 두 가지 명시적 공식으로 주어진다.

## 응용
보간 다항식의 원래 용도는 자연로그 및 삼각 함수와 같은 중요한 초월 함수의 값을 근사하는 것이었다. 몇 개의 정확하게 계산된 자료점으로부터, 해당 보간 다항식은 임의의 근처 점에서 함수를 근사할 것이다. 다항식 보간법은 또한 수치 적분 (심프슨 공식) 및 수치 상미분 방정식 (다중 격자법) 알고리즘의 기초를 이룬다.

컴퓨터 그래픽스에서는 다항식을 사용하여 몇 가지 지정된 점(예: 타이포그래피의 글자 모양)이 주어졌을 때 복잡한 평면 곡선을 근사할 수 있다. 이는 일반적으로 베지에 곡선을 사용하여 수행되는데, 이는 보간 다항식의 간단한 일반화이다(지정된 점뿐만 아니라 지정된 접선도 가짐).

수치해석학에서 다항식 보간법은 카라추바 곱셈 및 톰-쿡 알고리즘과 같은 이차 미만의 곱셈 및 제곱을 수행하는 데 필수적이다. 여기서 곱 다항식의 점을 통한 보간은 필요한 특정 곱을 산출한다. 예를 들어, a = f(x) = a0x0 + a1x1 + ··· 및 b = g(x) = b0x0 + b1x1 + ···가 주어지면, 곱 ab는 W(x) = f(x)g(x)의 특정 값이다. W(x)의 점은 작은 x 값에서 쉽게 찾을 수 있으며, 이러한 점을 기반으로 한 보간은 W(x)의 항과 특정 곱 ab를 산출한다. 카라추바 곱셈에서 공식화된 바와 같이, 이 기술은 겸손한 크기의 입력에 대해서도, 특히 병렬 하드웨어에서 이차 곱셈보다 상당히 빠르다.

컴퓨터 과학에서 다항식 보간법은 또한 다자간 보안 컴퓨팅 및 비밀 공유 알고리즘으로 이어진다.

## 보간 정리
서로 다른 x_j가 없는 n+1개의 이변량 자료점 (x_0,y_0),\dotsc,(x_n,y_n) \in \R^2에 대해, 이 점들을 보간하는 차수가 최대 n인 유일한 다항식 p(x)가 존재한다. 즉, p(x_0)=y_0, \ldots, p(x_n)=y_n이다.

등가적으로, 보간 노드 x_j의 고정된 선택에 대해, 다항식 보간은 실수 값의 (n+1)튜플 (y_0,\ldots,y_n)\in \R^{n+1}과 차수가 최대 n인 실수 다항식의 벡터 공간 P(n) 사이의 선형 전단사 함수 L_n을 정의한다.
L_n : \mathbb{R}^{n+1}  \stackrel{\sim}{\longrightarrow}\,  P(n).

이것은 일종의 유일해성 정리이다. 이 정리는 실수 \R 대신 임의의 무한 체 (예: 유리수 또는 복소수)에 대해서도 유효하다.

### 첫 번째 증명
라그랑주 기저 함수 L_0(x),\ldots,L_n(x)를 다음과 같이 고려한다:
L_j(x)=\prod_{i\neq j}\frac{x-x_i}{x_j-x_i}
= \frac{(x-x_0)\cdots(x-x_{j-1})(x-x_{j+1})\cdots(x-x_n)}
{(x_j-x_0)\cdots(x_j-x_{j-1})(x_j-x_{j+1})\cdots(x_j-x_n)}.

L_j(x)는 차수 n의 다항식이고, 각 j\neq k에 대해 L_j(x_k)=0이며, L_k(x_k)=1임을 알 수 있다. 따라서 선형 결합:
p(x) = \sum_{j=0}^n y_j L_j(x)
는 p(x_k)=\sum_j y_j \,L_j(x_k) = y_k 를 가지므로, p(x)는 차수 n의 보간 다항식이다.

유일성을 증명하기 위해, 차수가 최대 n인 또 다른 보간 다항식 q(x)가 존재하여 모든 k=0,\dotsc,n에 대해 p(x_k)=q(x_k)라고 가정한다. 그러면 p(x)-q(x)는 n+1개의 서로 다른 영점( x_k들)을 갖는 차수가 최대 n인 다항식이다. 그러나 차수가 최대 n인 영이 아닌 다항식은 최대 n개의 영점을 가질 수 없으므로, p(x)-q(x)는 영 다항식이어야 한다. 즉, p(x)=q(x)이다.

### 두 번째 증명
보간 다항식을 다음과 같은 형태로 작성한다:

이를 보간 방정식 p(x_j) = y_j에 대입하면, 계수 a_j에 대한 연립 일차 방정식을 얻는다. 이를 행렬-벡터 형식으로 나타내면 다음과 같은 행렬 곱셈이 된다:
\begin{bmatrix}
x_0^n  & x_0^{n-1} & x_0^{n-2} & \ldots & x_0 & 1 \\
x_1^n  & x_1^{n-1} & x_1^{n-2} & \ldots & x_1 & 1 \\
\vdots & \vdots    & \vdots    &        & \vdots & \vdots \\
x_n^n  & x_n^{n-1} & x_n^{n-2} & \ldots & x_n & 1
\end{bmatrix}
\begin{bmatrix} a_n \\ a_{n-1} \\ \vdots \\ a_0 \end{bmatrix}  =
\begin{bmatrix} y_0 \\ y_1 \\ \vdots \\ y_n \end{bmatrix}.

보간 다항식 p(x)는 위 행렬 방정식 X \cdot A = Y의 해 A = (a_n,\ldots,a_0)에 해당한다. 왼쪽의 행렬 X는 방데르몽드 행렬이며, 그 행렬식은 \textstyle \det(X) = \prod_{1 \le i 로 알려져 있다. 노드 x_j가 모두 다르므로 행렬식은 0이 아니다. 이는 행렬이 가역이며 방정식이 유일한 해 A = X^{-1}\cdot Y를 가진다는 것을 보장한다. 즉, p(x)는 존재하며 유일하다.

### 귀결
f(x)가 차수가 최대 n인 다항식이라면, n+1개의 서로 다른 점에서 f(x)를 보간하는 다항식은 f(x) 자체이다.

## 보간 다항식 구성
섬네일|right|붉은 점들은 자료점 를 나타내고, 파란 곡선은 보간 다항식을 나타낸다.

### 라그랑주 보간법

라그랑주 다항식을 이용하여 즉시 다항식을 다음과 같이 작성할 수 있다:
\begin{align}
 p(x) &= \frac{(x-x_1)(x-x_2)\cdots(x-x_n)}{(x_0-x_1)(x_0-x_2)\cdots(x_0-x_n)} y_0 \\
 [4pt]    &+ \frac{(x-x_0)(x-x_2)\cdots(x-x_n)}{(x_1-x_0)(x_1-x_2) \cdots(x_1-x_n)}y_1 \\
 [4pt]    &+ \cdots\\
 [4pt]    &+\frac{(x-x_0)(x-x_1)\cdots(x-x_{n-1})}{(x_n-x_0)(x_n-x_1)\cdots(x_n-x_{n-1})}y_n \\
[7pt]
&=\sum_{i=0}^n \Biggl( \prod_{\stackrel{\!0\,\leq\, j\,\leq\, n}{j\,\neq\, i}} \frac{x-x_j}{x_i-x_j} \Biggr) y_i
=\sum_{i=0}^n \frac{p(x)}{p'(x_i)(x-x_i)}\,y_i
\end{align}행렬 인수의 경우, 이 공식은 실베스터 공식이라고 불리며, 행렬 값 라그랑주 다항식은 프로베니우스 공변량이다.

:

### 뉴턴 보간법

#### 정리
노드 x_i (i = 0,1,2,3,\cdots,n)에서 f를 보간하는 차수가 n 이하인 다항식을 p_n이라 하자. 노드 x_i (i = 0,1,2,3,\cdots,n, n+1)에서 f를 보간하는 차수가 n+1 이하인 다항식을 p_{n+1}이라 하자. 그러면 p_{n+1}은 다음과 같이 주어진다:
p_{n+1}(x) = p_n(x) +a_{n+1}w_n(x) 
여기서 w_n(x) := \prod_{i=0}^n (x-x_i)  는 뉴턴 기저라고도 하며, a_{n+1} :={f(x_{n+1})-p_n(x_{n+1}) \over w_n(x_{n+1})}    이다.

**증명:**

이것은 i = 0,1,2,3,\cdots,n인 경우에 대해 보일 수 있다:
p_{n+1}(x_i) = p_n(x_i) +a_{n+1}\prod_{j=0}^n (x_i-x_j) = p_n(x_i) 
그리고 i = n+1일 때:
p_{n+1}(x_{n+1}) = p_n(x_{n+1}) +{f(x_{n+1})-p_n(x_{n+1}) \over w_n(x_{n+1})}   w_n(x_{n+1}) = f(x_{n+1})  
차수가 n+1 미만인 보간 다항식의 유일성에 따라, p_{n+1}(x) = p_n(x) +a_{n+1}w_n(x) 가 요구되는 다항식 보간이다. 따라서 함수는 다음과 같이 표현될 수 있다:

p_{n}(x) = a_0+a_1(x-x_0)+a_2(x-x_0)(x-x_1)+\cdots + a_n(x-x_0)\cdots(x-x_{n-1}) .

#### 다항식 계수
a_i를 찾기 위해, 위 방정식에서 p_{n} (x_i)=f(x_i)=y_i  를 행렬 형태로 배열하여 형성된 하삼각 행렬을 풀어야 한다:
: \begin{bmatrix}
      1 &         & \ldots &        & 0  \\
      1 & x_1-x_0 &        &        &    \\
      1 & x_2-x_0 & (x_2-x_0)(x_2-x_1) &        & \vdots   \\
 \vdots & \vdots  &        & \ddots &    \\
      1 & x_k-x_0 & \ldots & \ldots & \prod_{j=0}^{n-1}(x_n - x_j)
\end{bmatrix}
\begin{bmatrix}     a_0 \\     \\     \vdots \\     \\     a_{n} \end{bmatrix} =
\begin{bmatrix}      y_0 \\  \\  \vdots \\ \\    y_{n} \end{bmatrix}

계수는 다음과 같이 유도된다:
: a_j := [y_0,\ldots,y_j]

여기서

: [y_0,\ldots,y_j]

는 나눗셈 차분에 대한 표기법이다. 따라서 뉴턴 다항식은 n개 점의 다항식 보간 공식을 제공하는 데 사용된다.

#### 뉴턴 전진 공식
x_0, x_1, \dots, x_k가 등간격으로 연속적으로 배열되어 있을 때, 뉴턴 다항식은 단순화된 형태로 표현될 수 있다.

만약 x_0, x_1, \dots, x_k가 연속적으로 배열되어 있고, {x}_{i}={x}_{0}+ih   (i = 0, 1, ..., k)와 같이 등간격이며, 어떤 변수 x가 {x}={x}_{0}+sh로 표현된다면, 차이 x-x_i는 (s-i)h로 작성될 수 있다. 따라서 뉴턴 다항식은 다음과 같이 된다.

: \begin{align}
N(x) &= [y_0] + [y_0,y_1]sh + \cdots + [y_0,\ldots,y_k] s (s-1) \cdots (s-k+1){h}^{k} \\
&= \sum_{i=0}^{k}s(s-1) \cdots (s-i+1){h}^{i}[y_0,\ldots,y_i] \\
&= \sum_{i=0}^{k}{s \choose i}i!{h}^{i}[y_0,\ldots,y_i].
\end{align}

나눗셈 차분과 전진 차분 사이의 관계는 다음과 같이 주어진다.
[y_j, y_{j+1}, \ldots , y_{j+n}] = \frac{1}{n!h^n}\Delta^{(n)}y_j,
y_i=f(x_i)라고 할 때, 이전 절에서 x의 표현이 대신 x=x_j+sh로 간주되었다면, **뉴턴 전진 보간 공식**은 다음과 같이 표현된다.
f(x) \approx N(x)=N(x_j+sh) = \sum_{i=0}^{k}{s \choose i}\Delta^{(i)} f(x_j)

이는 x_j 이후의 모든 점의 보간이다. 다음과 같이 전개된다.
f(x_j+sh)=f(x_j)+\frac{s}{1!}\Delta f(x_j)+ \frac{s(s-1)}{2!}\Delta^2 f(x_j)+\frac{s(s-1)(s-2)}{3!}\Delta^3 f(x_j)+\frac{s(s-1)(s-2)(s-3)}{4!}\Delta^4 f(x_j)+\cdots


#### 뉴턴 후진 공식
노드가 {x}_{k},{x}_{k-1},\dots,{x}_{0}으로 재정렬되면 뉴턴 다항식은 다음과 같다.

: N(x)=[y_k]+[{y}_{k}, {y}_{k-1}](x-{x}_{k})+\cdots+[{y}_{k},\ldots,{y}_{0}](x-{x}_{k})(x-{x}_{k-1})\cdots(x-{x}_{1}).

만약 {x}_{k},\;{x}_{k-1},\;\dots,\;{x}_{0}가 {x}_{i}={x}_{k}-(k-i)h (i = 0, 1, ..., k)와 같이 등간격으로 떨어져 있고, {x}={x}_{k}+sh라면,

: \begin{align}
N(x) &= [{y}_{k}]+ [{y}_{k}, {y}_{k-1}]sh+\cdots+[{y}_{k},\ldots,{y}_{0}]s(s+1)\cdots(s+k-1){h}^{k} \\
&=\sum_{i=0}^{k}{(-1)}^{i}{-s \choose i}i!{h}^{i}[{y}_{k},\ldots,{y}_{k-i}].
\end{align}

나눗셈 차분과 후진 차분 사이의 관계는 다음과 같이 주어진다.
[{y}_{j}, y_{j-1},\ldots,{y}_{j-n}] = \frac{1}{n!h^n}\nabla^{(n)}y_j, 
y_i=f(x_i)라고 할 때, 이전 절에서 x의 표현이 대신 x=x_j+sh로 간주되었다면, **뉴턴 후진 보간 공식**은 다음과 같이 표현된다.
f(x) \approx N(x) =N(x_j+sh)=\sum_{i=0}^{k}{(-1)}^{i}{-s \choose i}\nabla^{(i)} f(x_j).

이는 x_j 이전의 모든 점의 보간이다. 다음과 같이 전개된다.
f(x_j+sh)=f(x_j)+\frac{s}{1!}\nabla f(x_j)+ \frac{s(s+1)}{2!}\nabla^2 f(x_j)+\frac{s(s+1)(s+2)}{3!}\nabla^3 f(x_j)+\frac{s(s+1)(s+2)(s+3)}{4!}\nabla^4 f(x_j)+\cdots


### 다이아몬드 도표
다이아몬드 도표는 주어진 자료 집합에 대해 구성할 수 있는 여러 가지 보간 공식을 설명하는 데 사용되는 도표이다. 왼쪽 가장자리에서 시작하여 도표를 가로질러 오른쪽으로 이동하는 선은 다음 규칙을 따르면 보간 공식을 나타내는 데 사용될 수 있다.
섬네일|다이아몬드 도표: 다항식 보간의 기하학적 표현.

# 왼쪽에서 오른쪽으로 가는 단계는 덧셈을 나타내고, 오른쪽에서 왼쪽으로 가는 단계는 뺄셈을 나타낸다.
# 단계의 기울기가 양수이면, 사용될 항은 차분과 그 바로 아래 인수의 곱이다. 단계의 기울기가 음수이면, 사용될 항은 차분과 그 바로 위 인수의 곱이다.
# 단계가 수평이고 인수를 통과하면, 인수와 그 바로 위아래 두 항의 평균 곱을 사용한다. 단계가 수평이고 차분을 통과하면, 차분과 그 바로 위아래 두 항의 평균 곱을 사용한다.

인수는 다음 공식을 사용하여 표현된다:
C(u+k,n)=\frac{(u+k)(u+k-1)\cdots(u+k-n+1)}{n!} 

#### 등가성 증명
경로가 \Delta^{n-1}y_s    에서 \Delta^{n+1}y_{s-1}    로 이동할 때, (a) \Delta^{n}y_{s-1}    를 통해, (b) C(u-s ,n) 를 통해, 또는 (c) \Delta^{n}y_s 를 통해 세 가지 중간 단계를 거쳐 연결될 수 있다. 이 세 가지 두 단계 경로의 등가성을 증명하면 모든 (n단계) 경로가 시작과 끝이 같으면서 같은 공식을 나타내도록 변형될 수 있음을 증명할 것이다.

경로 (a):

C(u-s, n) \Delta^n y_{s-1}+C(u-s+1, n+1) \Delta^{n+1} y_{s-1}    

경로 (b):

C(u-s, n) \Delta^n y_s + C(u-s, n+1) \Delta^{n+1} y_{s-1}            

경로 (c):

C(u-s, n) \frac{\Delta^n y_{s-1}+\Delta^n y_{s}}{2} \quad+\frac{C(u-s+1, n+1)+C(u-s, n+1)}{2} \Delta^{n+1} y_{s-1}    

경로 a와 b의 기여를 뺀다:

\begin{aligned}
\text{경로 a - 경로 b}= & C(u-s, n)(\Delta^n y_{s-1}-\Delta^n y_s) +(C(u-s+1, n+1)-C(u-s, n-1)) \Delta^{n+1} y_{s-1} \\
= & - C(u-s, n)\Delta^{n+1} y_{s-1} + C(u-s, n) \frac{(u-s+1)-(u-s-n)}{n+1} \Delta^{n+1} y_{s-1}  \\
= & C(u-s, n)(-\Delta^{n+1} y_{s-1}+\Delta^{n+1} y_{s-1} )=0 \\
\end{aligned}    

따라서 경로 (a)와 경로 (b)의 기여는 동일하다. 경로 (c)는 경로 (a)와 (b)의 평균이므로, 역시 다항식에 동일한 함수를 기여한다. 따라서 시작점과 끝점이 같은 경로의 등가성이 입증되었다. 가장 왼쪽 모서리의 다른 값으로 경로를 이동할 수 있는지 확인하기 위해, 두 단계 경로만으로 충분하다: (a) \Delta y_s          를 통해 y_{s+1}          에서 y_{s}          로 또는 (b) y_{s+1}          와 y_{s}           사이의 인수를 통해 \Delta y_s          를 통해 y_{s}          로 또는 (c) y_{s}          에서 시작한다.

경로 (a)

y_{s+1}+C(u-s-1,1) \Delta y_s - C(u-s, 1) \Delta y_s         

경로 (b)

\frac{y_{s+1}+y_s}{2}+\frac{C(u-s-1,1)+C(u-s, 1)}{2} \Delta y_s - C(u-s, 1) \Delta y_s         

경로 (c)

y_{s}          

\Delta y_{s} = y_{s+1}-y_s    이므로, 위 식에 대입하면 모든 항이 y_{s}          로 줄어들고 따라서 등가임이 보인다. 따라서 이 경로들은 가장 왼쪽 모서리에서 시작하여 공통점으로 끝날 수 있도록 변형될 수 있다.

#### 뉴턴 공식
y_0 에서 \Delta^n y_0 로 음의 기울기 횡단선을 취하면 모든 n+1 개의 연속적으로 배열된 점들의 보간 공식을 얻게 되며, 이는 뉴턴의 전진 보간 공식과 동등하다.

\begin{aligned}
y(s)  &=y_0+C(s, 1) \Delta y_0+C(s, 2) \Delta^2 y_0+C(s, 3) \Delta^3 y_0+\cdots \\
& =y_0+s \Delta y_0+\frac{s(s-1)}{2} \Delta^2 y_0+\frac{s(s-1)(s-2)}{3 !} \Delta^3 y_0+\frac{s(s-1)(s-2)(s-3)}{4 !} \Delta^4 y_0+\cdots
\end{aligned}    

반면, y_n 에서 \nabla^n y_n = \Delta^n y_0 로 양의 기울기 횡단선을 취하면 모든 n+1 개의 연속적으로 배열된 점들의 보간 공식을 얻게 되며, 이는 뉴턴의 후진 보간 공식과 동등하다.

\begin{aligned}
y(u) & =  y_k+C(u-k, 1) \Delta y_{k-1}+C(u-k+1,2) \Delta^2 y_{k-2} +C(u - k+2,3) \Delta^3 y_{k-3}+\cdots \\
& = y_k+(u-k) \Delta y_{k-1} +\frac{(u-k+1) (u-k)}{2} \Delta^2 y_{k-2}+\frac{(u-k+2)(u-k+1)(u-k)}{3 !} \Delta^3 y_{k-3}+\cdots   \\
y(k+s) & = y_k+(s) \nabla y_{k} +\frac{(s+1) s}{2} \nabla^2 y_{k}+\frac{(s+2)(s+1) s}{3 !} \nabla^3 y_{k}+\frac{(s+3)(s+2)(s+1) s}{4 !} \nabla^4 y_{k}+\cdots \\
\end{aligned}    

여기서 s=u-k 는 뉴턴 보간법에서 도입된 해당 숫자이다.

#### 가우스 공식
y_0 에서 음의 기울기로 오른쪽으로 지그재그 선을 취하면 가우스 전진 공식을 얻는다.

y(u)=y_0+u \Delta y_0+\frac{u(u-1)}{2} \Delta^2 y_{-1} +\frac{(u+1)u\left(u-1\right)}{3 !} \Delta^3 y_{-1}+  \frac{(u+1)u\left(u-1\right)(u-2)}{4 !} \Delta^4 y_{-2} + \cdots                     

반면, y_0 에서 양의 기울기로 시작하면 가우스 후진 공식을 얻는다.

y(u)=y_0+u \Delta y_{-1}+\frac{(u+1)u}{2} \Delta^2 y_{-1} +\frac{(u+1)u\left(u-1\right)}{3 !} \Delta^3 y_{-2}+  \frac{(u+2)(u+1)u\left(u-1\right)}{4 !} \Delta^4 y_{-2} + \cdots                          

#### 스털링 공식
y_0 에서 오른쪽으로 수평 경로를 취하면 스털링 공식을 얻는다.

\begin{aligned}
y(u)&= y_0 +u \frac{\Delta y_0+\Delta y_{-1}}{2}+\frac{C(u+1,2)+C(u, 2)}{2} \Delta^2 y_{-1} +C(u+1,3) \frac{\Delta^3 y_{-2}+\Delta^3 y_{-1}}{2}+\cdots \\
& = y_0+u \frac{\Delta y_0+\Delta y_{-1}}{2}+\frac{u^2}{2} \Delta^2 y_{-1}+\frac{u(u^2-1)}{3 !} \frac{\Delta^3 y_{-2}+\Delta^3 y_{-1}}{2}+\frac{u^2(u^2-1)}{4!}\Delta^4 y_{-2}+\cdots
\end{aligned}    

스털링 공식은 가우스 전진 공식과 가우스 후진 공식의 평균이다.

#### 베셀 공식
y_0 와 y_1  사이의 인수에서 시작하여 오른쪽으로 수평 경로를 취하면 베셀 공식을 얻는다.

\begin{align}
y(u)&=1{\frac{y_{0}+y_{1}}{2}}+{\frac{C(u,1)+C(u-1,1)}{2}}\Delta y_{0}+C(u,2){\frac{\Delta^{2}y_{-1}+\Delta^{2}y_{0}}{2}}+\cdots\\
    &=  \frac{y_{0}+y_{1}}{2}+\left(u-{\frac{1}{2}}\right)\Delta y_{0}+\frac{u(u-1)}{2}\frac{\Delta^{2}y_{-1}   +\Delta^{2}y_{0}}{2}+\frac{\left(u-{\frac{1}{2}}\right)u\left( u-1\right)}{3!}\Delta^{3} y_{0}
  + \frac{(u+1)u(u-1)(u-2)}{4!}\frac{\Delta^{4}y_{-1}+\Delta^{4}y_{-2}}{2}+\cdots\\
\end{align}                      

### 방데르몽드 알고리즘
위 두 번째 증명에 나오는 방데르몽드 행렬은 조건수가 클 수 있으며, 이로 인해 가우스 소거법을 사용하여 연립 방정식을 풀 경우 계수 를 계산하는 데 큰 오차가 발생할 수 있다.

따라서 여러 저자들이 가우스 소거법에 필요한 O(n3) 연산 대신 O(n2) 연산으로 수치적으로 안정적인 해를 계산하기 위해 방데르몽드 행렬의 구조를 활용하는 알고리즘을 제안했다. 이 방법들은 먼저 다항식의 뉴턴 보간을 구성한 다음 이를 단항식 형식으로 변환하는 방식에 의존한다.

### 비방데르몽드 알고리즘
차수 의 다항식 벡터 공간 P(n)에서 보간 다항식 p(x)를 찾기 위해, P(n)에 대한 일반적인 단항식 기저를 사용하고 가우스 소거법으로 방데르몽드 행렬을 역행렬화하여 계산 비용이 O(n3) 연산이 된다. 이 알고리즘을 개선하려면, P(n)에 대한 더 편리한 기저를 사용하면 계수 계산을 단순화할 수 있으며, 그 후에는 이를 다시 단항식 기저로 변환해야 한다.

한 가지 방법은 보간 다항식을 뉴턴 형식(즉, 뉴턴 기저 사용)으로 작성하고, 네빌 알고리즘과 같이 나눗셈 차분 방법을 사용하여 계수를 구성하는 것이다. 비용은 O(n<sup>2</sup>) 연산이다. 게다가, 자료 집합에 추가 점이 추가되는 경우 O(n)의 추가 작업만 필요하며, 다른 방법의 경우 전체 계산을 다시 수행해야 한다.

또 다른 방법은 p(x)의 계수를 계산하는 것이 아니라 원래 자료 집합에 없는 점 x = a에서의 단일 값 p(a)만 계산하는 것이 목적일 때 선호된다. 라그랑주 형식은 O(n2)의 복잡도로 p(a) 값을 계산한다.

베른슈타인의 바이어슈트라스 근사 정리의 구성적 증명에서 베른슈타인 형식이 사용되었으며, 베지에 곡선 형태로 컴퓨터 그래픽스에서 큰 중요성을 얻었다.

## 값의 선형 결합으로서의 보간
서로 다른 위치 x_j를 가진 (위치, 값) 자료점 집합 (x_0, y_0), \ldots, (x_j, y_j), \ldots, (x_n, y_n)이 주어졌을 때, 보간 다항식 y(x)는 x_j에 따라 x의 다항식인 계수를 사용하여 값 y_j의 선형 결합으로 간주될 수 있다. 예를 들어, 라그랑주 형식의 보간 다항식은 선형 결합이다.
y(x) := \sum_{j=0}^{k} y_j c_j(x)
각 계수 c_j(x)는 주어진 위치 x_j에 대한 해당 라그랑주 기저 다항식으로 주어진다.
c_j(x) = L_j(x_0,\ldots,x_n;x) = \prod_{ 0 \le i \le n \atop i \neq j } \frac{x-x_i}{x_j-x_i}
= \frac{(x-x_0)}{(x_j-x_0)} \cdots \frac{(x-x_{j-1})}{(x_j-x_{j-1})} \frac{(x-x_{j+1})}{(x_j-x_{j+1})} \cdots
\frac{(x-x_n)}{(x_j-x_n)}.

계수는 값 y_j가 아니라 위치 x_j에만 의존하므로, 동일한 위치에서 두 번째 자료점 집합 (x_0, v_0), \ldots, (x_n, v_n)에 대한 보간 다항식을 찾기 위해 동일한 계수를 사용할 수 있다.
v(x) := \sum_{j=0}^{k} v_j c_j(x).

더 나아가, 계수 c_j(x)는 위치 사이의 상대적 간격 x_i-x_j에만 의존한다. 따라서, 점들이 새로운 변수 t = ax+b (아핀 변환 of x, x=\tfrac{t-b}{a}에 의해 역변환됨)로 주어지는 세 번째 자료 집합이 주어졌을 때:
(t_0, w_0), \ldots, (t_j, w_j) \ldots, (t_n, w_n) \qquad \text{단}\qquad t_j = ax_j + b,
이전 계수 다항식의 변환된 버전을 사용할 수 있다:\tilde c_j(t) :=  c_j(\tfrac{t-b}{a}) = c_j(x), 그리고 보간 다항식을 다음과 같이 작성할 수 있다:w(t) := \sum_{j=0}^{k} w_j \tilde c_j(t).자료점 (x_j,y_j)는 종종 등간격 위치를 가지며, 이는 아핀 변환에 의해 x_j = j로 정규화될 수 있다. 예를 들어, 자료점
(0,y_0), (1,y_1), (2,y_2).
라그랑주 형식의 보간 다항식은 선형 결합이다.
\begin{align}
y(x) := \sum_{j=0}^2 y_j c_j(x)
&= y_0 \frac{(x-1)(x-2)}{(0-1)(0-2)} + y_1 \frac{(x-0)(x-2)}{(1-0)(1-2)} + y_2 \frac{(x-0)(x-1)}{(2-0)(2-1)} \\
&= \tfrac12 y_0 (x-1)(x-2) - y_1 (x-0)(x-2) + \tfrac12 y_2 (x-0)(x-1).
\end{align} 

예를 들어, y(3) = y_3 = y_0 - 3y_1 + 3y_2  이고 y(1.5) = y_{1.5} = \tfrac18 (-y_0 + 6y_1 + 3y_2)이다.

등간격 점의 경우 유한 차분법으로도 처리할 수 있다. 값의 수열 v=\{v_j\}_{j=0}^\infty의 첫 번째 차분은 u_j = v_{j+1}-v_j 로 정의되는 수열 \Delta v = u = \{u_j\}_{j=0}^\infty 이다. 이 연산을 반복하면 n차 차분 연산 \Delta^n v = u가 되며, 이는 다음과 같이 명시적으로 정의된다.
u_j = \sum_{k=0}^n (-1)^{n-k} {n\choose k} v_{j+k}, 
여기서 계수는 부호가 있는 파스칼 삼각형, 즉 이항 변환 계수 삼각형을 형성한다.

차수 d의 다항식 y(x)는 양의 정수점에서 값의 수열 y_j = y(j)를 정의하며, 이 수열의 (d+1)^{\text{th}} 차분은 항상 0이다:
\Delta^{d+1} y = 0. 
따라서 등간격 점에서 y_0,\ldots,y_n 값이 주어지고 n=d+1 이면 다음이 성립한다:
(-1)^n y_0 + (-1)^{n-1} \binom{n}{1} y_1 + \cdots - \binom n{n-1} y_{n-1} +  y_n= 0. 
예를 들어, 이차 다항식 y(x)의 등간격 4개 자료점 y_0,y_1,y_2,y_3 은 0 = -y_0 + 3y_1 - 3y_2 + y_3를 만족하며, y_3에 대해 풀면 위에서 라그랑주 방법을 사용하여 얻은 것과 동일한 보간 방정식을 얻는다.

## 보간 오차: 라그랑주 나머지 공식
주어진 함수 f를 노드 x0,..., xn에서 차수 의 다항식 p_n으로 보간할 때 다음과 같은 오차를 얻는다.
f(x) - p_n(x) = f[x_0,\ldots,x_n,x] \prod_{i=0}^n (x-x_i) 
여기서 f[x_0,\ldots,x_n,x]는 자료점
(x_0,f(x_0)),\ldots,(x_n,f(x_n)),(x,f(x)) 
의 (n+1)차 나눗셈 차분이다.
더 나아가, 닫힌 구간 I에서 번 연속 미분 가능하며, n+1개의 서로 다른 점 x_0,\ldots,x_n\in I에서 f를 보간하는 차수가 최대 인 다항식 p_n(x)에 대해 라그랑주 나머지 형태의 오차가 존재한다. 각 x\in I에 대해 다음을 만족하는 \xi\in I가 존재한다.
 f(x) - p_n(x) = \frac{f^{(n+1)}(\xi)}{(n+1)!} \prod_{i=0}^n (x-x_i). 

이 오차 한계는 곱 \left | \prod (x - x_i) \right |을 최소화하도록 보간점 를 선택할 것을 제안하며, 이는 체비쇼프 노드로 달성된다.

### 라그랑주 나머지 증명
오차 항을  R_n(x) = f(x) - p_n(x) 로 설정하고, 보조 함수를 다음과 같이 정의한다:
 Y(t) = R_n(t) - \frac{R_n(x)}{W(x)} W(t) \qquad\text{여기서}\qquad
W(t) = \prod_{i=0}^n (t-x_i). 
따라서:
 Y^{(n+1)}(t) = R_n^{(n+1)}(t) - \frac{R_n(x)}{W(x)} \ (n+1)! 

그러나 p_n(x)는 차수가 최대 인 다항식이므로  R_n^{(n+1)}(t) = f^{(n+1)}(t) 이고, 다음과 같다:
 Y^{(n+1)}(t) = f^{(n+1)}(t) - \frac{R_n(x)}{W(x)} \ (n+1)! 

이제 는 R_n(t)와 W(t)의 근이므로  Y(x)=Y(x_j)=0 이며, 이는 가 적어도 개의 근을 가짐을 의미한다. 롤의 정리에 따라, Y^\prime(t)는 적어도 개의 근을 가지며, 반복적으로 Y^{(n+1)}(t)는 구간 에 적어도 하나의 근 를 가진다. 따라서:
 Y^{(n+1)}(\xi) = f^{(n+1)}(\xi) - \frac{R_n(x)}{W(x)} \ (n+1)! = 0 

그리고:
 R_n(x) = f(x) - p_n(x) = \frac{f^{(n+1)}(\xi)}{(n+1)!} \prod_{i=0}^n (x-x_i) .

이것은 테일러 정리의 라그랑주 나머지 항 뒤에 있는 추론과 유사하다. 사실, 테일러 나머지는 모든 보간 노드 가 동일한 경우 보간 오차의 특별한 경우이다. x = x_i (모든 i에 대해)일 때 오차가 0이 된다는 점에 유의해야 한다. 따라서 최대 오차는 두 연속 노드 사이의 구간 내 어느 한 점에서 발생한다.

### 등간격 구간
등간격 보간 노드 x_i = a + ih (i=0,1,\ldots,n,) 및 h = (b-a)/n인 경우, 보간 오차 공식의 곱 항은 다음과 같이 제한될 수 있다.
\left|\prod_{i=0}^n (x-x_i)\right| = \prod_{i=0}^n \left|x-x_i\right| \leq \frac{n!}{4} h^{n+1}.

따라서 오차 한계는 다음과 같이 주어질 수 있다.
 \left|R_n(x)\right| \leq \frac{h^{n+1}}{4(n+1)} \max_{\xi\in[a,b]} \left|f^{(n+1)}(\xi)\right| 

그러나 이것은 f^{(n+1)}(\xi)가 h^{n+1}에 의해 지배된다는 것을 가정한다. 즉, f^{(n+1)}(\xi) h^{n+1} \ll 1이다. 여러 경우에 이것은 사실이 아니며 오차는 실제로 일 때 증가한다(룽게 현상 참조). 이 문제는 수렴 특성 섹션에서 다룬다.

## 르베그 상수

보간 노드 x0, ..., xn과 모든 보간 노드를 포함하는 구간 [a, b]를 고정한다. 보간 과정은 함수 f를 다항식 p로 매핑한다. 이것은 [a, b]의 모든 연속 함수 공간 C([a, b])에서 자기 자신으로의 매핑 X를 정의한다. 매핑 X는 선형이며 차수 n 이하의 다항식 부분 공간 P(n) 에 대한 사영작용소이다.

르베그 상수 L은 X의 작용소 노름으로 정의된다. 다음이 성립한다(르베그 보조정리의 특별한 경우):
 \left\|f-X(f)\right\| \le (L+1) \left\|f-p^*\right\|. 

다시 말해, 보간 다항식은 가능한 최상의 근사치보다 최대 (L + 1)배 더 나쁘다. 이는 L을 작게 만드는 보간 노드 집합을 찾는 것이 좋다는 것을 시사한다. 특히, 체비쇼프 노드의 경우 다음이 성립한다.
 L \le \frac2\pi \log(n+1) + 1.

등간격 노드의 경우 n에 대한 성장이 기하급수적이기 때문에 체비쇼프 노드가 다항식 보간에 매우 좋은 선택이라는 결론을 다시 내린다. 그러나 이 노드들은 최적이 아니다.

## 수렴 특성
어떤 종류의 함수와 어떤 보간 노드에 대해 보간 다항식의 수열이 일 때 보간되는 함수로 수렴하는지 묻는 것은 자연스러운 일이다. 수렴은 점별, 균등 또는 특정 적분 노름 등 다양한 방식으로 이해될 수 있다.

등간격 노드의 경우 상황이 다소 좋지 않은데, 무한히 미분 가능한 함수에 대해서도 균등 수렴이 보장되지 않는다. 카를 룽게의 고전적인 예시는 구간 에서 함수 f(x) = 1 / (1 + x2)이다. 보간 오차 는 일 때 무한히 증가한다. 또 다른 예시는 구간 에서 함수 f(x) = |x|인데, 이 경우 보간 다항식은 x = ±1, 0 세 점을 제외하고는 점별로도 수렴하지 않는다.

더 나은 수렴 특성은 다른 보간 노드를 선택하여 얻을 수 있다고 생각할 수 있다. 다음 결과는 다소 고무적인 답변을 제공하는 것처럼 보인다.

그러나 이 방법의 단점은 새로운 함수 f(x)마다 보간 노드를 새로 계산해야 한다는 것이고, 이 알고리즘은 수치적으로 구현하기 어렵다는 것이다. 보간 다항식의 수열이 임의의 연속 함수 f(x)로 수렴하는 단일 노드표가 존재할까? 안타깝게도 답은 부정적이다.

이 증명은 본질적으로 위에 정의된 르베그 상수의 하한 추정치를 사용하며, 르베그 상수는 Xn의 작용소 노름이다(여기서 Xn은 Πn에 대한 사영 연산자이다). 이제 우리는 다음과 같은 노드 표를 찾는다.

\lim_{n \to \infty} X_n f = f,\text{ for every }f \in C([a,b]).

바나흐-슈타인하우스 정리에 따르면, 이는 Xn의 노름이 균등하게 유계일 때만 가능하며, 이는 다음을 알고 있으므로 사실일 수 없다.

\|X_n\|\geq \tfrac{2}{\pi} \log(n+1)+C.

예를 들어, 등간격 점이 보간 노드로 선택되면 룽게 현상의 함수는 그러한 보간의 발산을 보여준다. 이 함수는 에서 연속일 뿐만 아니라 무한히 미분 가능함에 유의해야 한다. 그러나 더 나은 체비쇼프 노드의 경우, 다음 결과 때문에 그러한 예시를 찾기가 훨씬 더 어렵다.

## 관련 개념
룽게 현상은 의 값이 높을 때 보간 다항식이 자료점 사이에서 심하게 진동할 수 있음을 보여준다. 이 문제는 일반적으로 스플라인 보간을 사용하여 해결된다. 여기서 보간 함수는 다항식이 아니라 스플라인 곡선: 더 낮은 차수의 여러 다항식의 연결이다.

주기함수를 조화 함수로 보간하는 것은 푸리에 변환을 통해 이루어진다. 이것은 조화 기저 함수를 사용한 다항식 보간의 한 형태로 볼 수 있으며, 삼각 보간 및 삼각 다항식을 참조하라.

에르미트 보간법 문제는 노드에서 다항식 p의 값뿐만 아니라 주어진 차수까지의 모든 도함수도 주어지는 경우이다. 이것은 동시 다항식 합동 시스템과 동일하며, 다항식에 대한 중국인의 나머지 정리를 통해 해결될 수 있다. 버크호프 보간법은 0부터 k까지의 모든 차수가 아닌 일부 차수의 도함수만 지정되는 더 일반적인 경우이다.

미분 및 적분 방정식의 해를 위한 콜로케이션 방법은 다항식 보간을 기반으로 한다.

유리 함수 모델링 기술은 다항 함수들의 비를 고려하는 일반화이다.

마지막으로, 고차원 다변수 보간법이 있다.

## 같이 보기
* 뉴턴 급수
* 다항 회귀
* 스플라인 스무딩

## 내용주

## 각주

## 참고 문헌
* 
* 
* 

## 더 읽어보기
* 
* 
* 
* 
* 

* J. L. Walsh: Interpolation and Approximation by Rational Functions in the Complex Domain, AMS (Colloquium Publications, Vol.20), ISBN 0-8218-1020-0 (1960). Chapter VII:'Interpolation by Polynomials'.

## 외부 링크
* 
* ALGLIB은 C++ / C#로 구현되어 있다.
* GSL은 C로 다항식 보간 코드를 가지고 있다.
* 다항식 보간 시연.

분류:다항식
분류:보간법