[수치해석] Lagrange interpolation

이전에 쓴 포스팅인 Polynomial interpolation 을 연결하는 내용입니다.

이번 포스팅은 Lagrange interpolation 에 대한 내용입니다. 

이전 포스팅에서는 세 점의 데이터를 가지고 quadratic polynomial로 보간함수를 만드는 작업을 했었습니다.

이번에는 점이 n+1개인 경우입니다. 사실상 많은 숫자를 의미하는데 계산편의를 위해 n+1개로 하겠습니다.

$(x_0,f_0),...,(x_n,f_n)$ 의 데이터에서 보간함수 $P_n(x)$ 를 만들려고 합니다. 당연히 같은 값의 점은 하나도 없습니다.

만들어야 하는 보간함수 $P_n(x)$ 는 

1. $P_n(x)$ 의 차수(degree)는 n보다 작았으면 좋겠고
2. 지금 사용할 데이터 $(x_0,f_0),...,(x_n,f_n)$ 를 지나야 합니다.

이 두가지 조건을 만족하는 $P_n(x)$을 만들 수 있는지 살펴보겠습니다.

Approch

$P_n(x)$ 를 만들기 위해서 이전 포스팅에서 만들었던 $P_1(x)$ 에서 시작을 해봅시다. 

$P_1(x)$ 을 symmetric form으로 변형을 할 거에요. 쉽게 말해서 $f_0, f_1$ 기준으로 항정리를 하면 $f_0,f_1$ 의 계수가 유사하게 생기게 됩니다.

 

$$\begin{align} P_{1}(x)  = a+bx & = \frac{f_{1}-f_{0}}{x_{1}-x_{0}}(x-x_{0})+f_{0}  = \left(\frac{x-x_1}{x_0-x_1} \right) f_0 + \left( \frac{x-x_0}{x_1-x_0} \right) f_1 = \ell_0(x)f_0 + \ell_1(x)f_1 \end{align}$$  

 

그러면 $\ell_0(x)와 \ell_1(x)$ 는 같은 인덱스의 $x_i$ 값은 1이 되고 나머지는 0이 되는 구조가 됩니다.

즉, $$\ell_k(x_i) = \begin{cases} 0   & \text{if } i \ne k \\ 1   & \text{if } i = k  \end{cases}$$ 가 됩니다.

 

이런 접근으로 계속 가서 아래와 같이 만들면서 조건도 맞으면 금상첨화입니다.

$P_n(x) = \ell_0(x)f_0+\ell_1(x)f_1+...+\ell_n(x)f_n$

 

$\ell_0, ... ,\ell_n$ 의 차수가 n보다 작거나 같다면 첫번째 조건을 만족합니다.

두번째 조건을 만족하려면 $P_n(x_i) = f_i$ 가 나오면 됩니다.

즉, 두번째 조건을 만족하려면 $\ell_0(x_0)$을 기준으로 본다면 $\ell_0(x_0) =1$ 이고 나머지 항은 0이어야 합니다. 

$P_1(x)$ 에서 했던 접근으로 간다면 두 조건을 만족하는 $\ell_0(x)$ 는 다음과 같이 됩니다.

$$\ell_0(x) = C_0(x-x_1)(x-x_2)...(x-x_n-1)(x-x_n), \\ where \ C_0 = \frac{1}{(x_0-x_1)(x_0-x_2)....(x_0-x_n)}$$

 

이렇게 된다면 $\ell_0(x)$ 는 두가지 조건을 만족하게 됩니다. 

좀 더 정리하면 다음과 같이 됩니다.

 

$$\ell_0(x) = \frac{(x-x_1)(x-x_2)...(x-x_n)}{(x_0-x_1)(x_0-x_2)...(x_0-x_n-1)(x_0-x_n)} = \prod_{i=1}^n {\frac{x-x_i}{x_0-x_1}}$$

 

나머지 $\ell_k(x)$ 도 위와 같이 형성됩니다. 따라서 0을 포함한 k의 $\ell_k(x)$ 는 다음과 같이 표현할 수 있습니다. 

$$\ell_k(x) = \prod_{i=0, i \ne k}^n { \frac{x-x_i}{x_k-x_i} } \ , k=1,...,n$$

 

이렇게 만든 $\ell_k$ 를 Lagrange polynomials 라 합니다.

Lagrange polynomials 를 $P_n(x)$ 에 대입을 하면 다음과 같이 나옵니다. 

$$P_n(x) = \sum_{k=0}^{n} {f_k} \prod_{i=0, i \ne k}^n {\frac{x-x_i}{x_k-x_i}}$$

$P_n(x)$ 를 Lagrange interpolating polynomial of degree n 이라 합니다.

그래서 이전 포스팅에서 다룬 Polynomial interpolation의 일반화된 형태로 볼 수 있습니다.

 

 

Error

$P_n(x)$ 를 구했으니 Error 함수 $e_n(x)$를 구해서 오차범위를 알아봅시다.

 

그전에 한가지를 알고 가야합니다. 오차계산의 편의를 위한 작업입니다. 

$Lemma) \ \ f(x)-P_n(x) = (x-x_0)···(x-x_n) \frac{f^{(n+1)}(\alpha)}{(n+1)!}$

증명은 다음과 같습니다. 보실분은 클릭하셔서 보세요.

$g(x) = f(x) - P_n(x) + \lambda(x-x_0)···(x-x_n)$, $\lambda$ 는 임의 상수라 한다.

$x=\alpha\ $ 에서의 error를 구하고 싶다면 $g(\alpha) = 0$ 이 되는 $\lambda$를 선택해주어야 한다.

즉, $0 = f(\alpha) - P_n(\alpha) + \lambda(\alpha-x_0)···(\alpha-x_n)$ 이기 때문에

$$\lambda = - \frac{f(\alpha)-P_n(\alpha)}{(\alpha-x_0)···(\alpha-x_n)}$$

이 되어야 한다.

∴ $g(x) = f(x) -P_n(x) - \frac{(x-x_0)···(x-x_n)}{(\alpha-x_0)···(\alpha-x_n)}(f(\alpha)-P_n(\alpha))$

그러면 g(x)는 $x=x_0,...,x_n,\alpha$ 에서 해를 갖게 된다.

Rolle의 정리(the extended Rolle Thm) 에 의해, $g^{(n+1)}$ 은 적어도 하나의 해를 갖게 되는데, 이 해를 $\xi_{\alpha}$ 라 하면 다음이 성립한다.

 

$$g^{(n+1)}(x) = f^{(n+1)}(x) - \frac{(n+1)!}{(\alpha-x_0)···(\alpha-x_n)}(f(\alpha)-P_n(\alpha))$$

 

$$\Rightarrow 0=g^{(n+1)}(\xi_{\alpha}) = f^{(n+1)}(\xi_{\alpha}) - \frac{(n+1)!}{(\alpha-x_0)···(\alpha-x_n)}(f(\alpha)-P_n(\alpha))$$

 

$$∴  f(x) - P_n(x) = (x-x_0)···(x-x_n) \frac{f^{(n+1)}(\xi_{\alpha})}{(n+1)!}$$

 

 

Lemma 가 되었으니 오차범위는 다음과 같이 됩니다.

$M_{n+1} = max|f^{(n+1)}(x)|, x_0<x<x_n$ 일때,

$$|e_n(x)| = |f(x)-P_n(x)|  \leqq |(x-x_0)···(x-x_n)| \frac{M_{n+1}}{(n+1)!}$$

 

오차함수도 또한 Lagrange polynomial로 일반화되어서 다항식으로 표현되는 식에 대해서 적용할 수 있습니다.

 

관련 포스팅

[수치해석] Polynomial form

[수치해석] Polynomial interpolation

 

참고문헌

Introduction to numerical analysis / alastair wood

Theory and Applications of Numerical Analysis-Academic Press / G. M. M. Phillips, Peter J. Taylo