[수치해석] Divided difference interpolation

Largrange interpolation 을 컴퓨터로 실행하게 되면 $x_i-x_j$ 를 일일히 계산해야 해서 계산량이 많아져서 비효율적입니다. 이에 대한 계산비용을 줄이고 다양한 방식을 접목하기 위해 기호를 정의해서 계산량을 개선하는 시도입니다.

 

Divided differences

미분을 보면 다음과 같습니다.

 

$$\frac{df(x)}{dx} = f'(x) = \lim_{h \to 0} {\frac{f(x+h)-f(x)}{h}}$$

 

이 식을 해석을 해보면 x와 x+h 사이의 기울기를 h를 줄여가면서 순간 기울기를 구하겠다는 얘기입니다. 

f'(x)를 그림으로 그려보면 다음과 같습니다.

 

즉, tangent line을 그리는 것입니다. 미적분을 공부하면 다 아는 내용이지만 다시 정리를 해보았습니다.

 

이렇게 정의되는 미분을 직접 계산하지 않고 estimate를 하겠습니다. 

데이터셋이 $(x_0,f_0), ... , (x_n,f_n)$ 이라 할 때, $x=x_i$ 에서의 f의 기울기는 $\frac{f(x_{i+1})-f(x_i)}{x_{i+1}-x_i}$ 가 됩니다.

오차는 어찌하든 발생하기 마련이니 미분 f'(x)를 기울기로 대체하겠습니다. 

 

$$f'(x_i) \approx \frac{f(x_{i+1})-f(x_i)}{x_{i+1}-x_i} = f[x_i,x_{i+1}]$$

 

기호화로 f[x_i,x_{i+1}]이라 하겠습니다. 이를 the first_order divided difference of f at $x=x_i$ 라 합니다.

이 기호를 확장해서 세점일때는 다음과 같이 씁니다. 이거는 2계미분도 아니고 단순한 기호를 활용한 확장입니다.

 

$$f[x_i,x_{i+1},x_{i+2}] = \frac{f[x_{i+1},x_{i+2}]-f[x_i,x_{i+1}]}{x_{i+2}-x_i}$$

 

이를 the second-order divied difference of f at $x=x_i$ 라 합니다.

 

n+1의 데이터셋에 대해서는 다음과 같이 씁니다. 이름을 붙인다면 Higher-order divided difference of f at $x=x_k$입니다.

$$f[x_0,x_1,...,x_{k-1},x_{k}] = \frac{f[x_1,...,x_k]-f[x_0,...,x_{k-1}]}{x_k-x_0}$$

 

마지막으로 $f_i = f[x_i]$ 로 표시하고 the divided difference of order zero of f at $x=x_i$ 이라 합니다.

 

실질적으로 Lagrange interpolation을 보더라도 f'(x) 하나만 나오고 나머지는 나오지 않으니 큰 무리는 없는 기호화인 듯 합니다.

 

Divided difference polynomial

이제 Lagrange interpolation에 divide difference를 적용해보겠습니다.

 

먼저 linear interpolating polynomial 입니다. 

$$\begin{align} p_1(x) & = \left( \frac{x-x_1}{x_0-x_1} \right) f_0 + \left( \frac{x-x_0}{x_1-x_0} \right) f_1 \\ & = f_0 +\left( \frac{f_1-f_0}{x_1-x_0} \right)(x-x_0) \\ & = f[x_0]+f[x_0,x_1](x-x_0) \end{align}$$  

 

이 방식으로 더해 나가면 $p_n(x) = p_{n-1}(x) + f[x_0,...,x_n](x-x_0)...(x-x_{n-1})$ 으로 점화식처럼 표기할 수 있습니다.

정리하면 다음과 같습니다.

$$p_n(x) = f[x_0] + \sum_{k=1}^{n} {f[x_0,...,x_k]} \prod_{i=0}^{k-1} {(x-x_i)}$$

 

이를 Newton divided difference polynomial 이라고 합니다. 

 

예제

Newton divided difference polynomial 과 Lagrange polynomial의 계산비교의 예를 보겠습니다. 이 예제는 Introduction to numerical analysis 라는 책에서 가져왔습니다.

 

데이터셋 (1,0),(-1,-2),(2,3) 에 대한 quardratic polynomial을 만들어보겠습니다.

먼저 Newton divided difference polynomial 입니다.

divided difference를 계산하면 다음과 같이 됩니다.
f[$x_0$}=0, f[$x_1$]=-2, f[$x_2$]=3 

f[$x_0,x_1$]=1,  f[$x_1,x_2$]= $\frac{5}{3}$

f[$x_0,x_1,x_2$]= $\frac{2}{3}$ 

 

이제 대입만 해주면 됩니다.

 

$$\begin{align} p_2(x) & = f[x_0] +(x-x_0)f[x_0,x_1] +(x-x_0)(x-x_1)f[x_0,x_1,x_2] \\ & = 0+(x-1)+\frac{2}{3}(x-1)(x+1) \\ & =\frac{2x^{2}}{3}+x-\frac{5}{3} \end{align}$$  

 

 

Lagrange polynomial 입니다. 

 

$\ell_0(x) = \frac{(x-x_1)(x-x_2)}{(x_0-x_1)(x_0-x_2)} = \frac{(x+1)(x-2)}{(2)(-1)} = \frac{-x^2+x+2}{2}$

$\ell_1(x) = \frac{(x-x_0)(x-x_2)}{(x_1-x_0)(x_1-x_2)} = \frac{(x-1)(x-2)}{(-2)(-3)} = \frac{x^2-3x+2}{6}$

$\ell_2(x) = \frac{(x-x_0)(x-x_1)}{(x_2-x_0)(x_2-x_1)} = \frac{(x-1)(x+1)}{(1)(3)} = \frac{x^2 -1}{3}$

 

$$p_2(x) = \sum_{k=0}^{2} {\ell_k(x)f_k} = 0 \ell_0(x) -2\ell_1(x) +3\ell_2(x) = \frac{2x^2+3x-5}{3}$$

 

비교해보면 계산방법의 차이만 있을 뿐 결과는 같게 나옵니다. 

더 효율적인 Newton divided difference polynomial 을 이용해 계산을 하면 많은 계산비용에서 벗어날 수 있습니다. 

 

관련 포스팅

[수치해석] Lagrange interpolation