[Numerical Analysis] Polynomial Interpolation

• $(x,f(x))$ 의 데이터를 가지고 $f(x)$를 approximation 하는 방법에 대하여 기술한 포스팅이다
• 'Numerical Methods and Optimizaiton : An Introduction (Sergiy Butenko)' - chapter 5 를 참고하였다

 

많은 Engineering 과 Science 에서 요구되는 문제들은 주어진 데이터들을 이용하여 함수 $f(x)$를 알아내는 방법들이 요구된다.

이러한 문제들을 Polynomical approximation을 통해 해결하고자 한다.

 

1. Polynomial 의 함수의 형태

1.1 power form

$$p(x) = a_0 + a_1x+a_2x^2 + \dots +a_nx^n$$

1.2 shifted power form (with center c)

$$p(x) = b_0 + b_1(x-c)+b_2(x-c)^2 + \dots +b_n(x-c)^n$$

1.3 Newton form

$$p(x) = a_0 + a_1(x-c_1)(x-c_2)+ \dots + a_n(x-c_1)\dots (x-c_n)$$

$$= a_0 + \sum_{k=1}^n a_k \prod_{i=1}^k (x-c_i)$$

(Newton form의 경우 모든 $c_i = c$ 일 경우 power form 과 같은 형태가 된다

 

즉 polynomial interpolation은 polynomial form의 계수인 $a_i$들을 구하는 과정임을 알 수 있다.

이제 Polynomical 함수 중 하나인 Lagrange polynomial 을 이용하여 Interpolation 을 수행하여 보자

 

2. Polynomial Interpolation Methods

data $(x_0,y_0), \dots , (x_n, y_n)$ 이 주어졌을때 Lagrange polynomial 은 아래와 같다.

$$l_j(x) = \frac{(x-x_0)(x-x_1)\dots (x-x_{j-1})(x-x_{j+1})\dots (x-x_n)}{(x_j-x_0)(x_j-x_1)\dots (x_j-x_{j-1})(x_j-x_{j+1})\dots (x_j-x_n)}$$

$$= \prod_{i =0, i \neq j}^n \frac{(x-x_i)}{(x_j - x_i)}$$

 

2.1 Lagrange method

lagrange polynomal을 이용하여 함수를 Interpolation하면 아래와 같다

$$p(x) = y_0l_0(x) + y_1l_1(x)+ \dots +y_nl_n(x)$$

$$\sum_{j = 0}^n y_j \prod_{i =0, i \neq j}^n \frac{(x-x_i)}{(x_j - x_i)}$$

 

2.2 Newton's method

기존의 n개 의 data points에 새로운 data point (x_{n+1}, y_{n+1}) 가 추가되는 경우 Lagrange method로는 기존의 $p_{n}(x)$ 을 이용할 수가 없다. 즉 새롭게 다시 구해야 한다. 하지만 Newton's method를 이용하면 $p_n(x)$를 이용하여 $p_{n+1}(x)$를 구하는 것이 가능해진다

$$p_{n+1}(x) = \sum_{j = 0}^n a_j \prod_{i = 0}^{j-1} (x-x_i) + a_{n+1} \prod_{i = 0}^n(x-x_i) = q(x) + r(x)$$

이 경우 interpolating polynomial 의 uniqueness로 $q(x) = p_n(x)$이므로,

$$p_{n+1}(x) = p_n(x) + a_{n+1}\prod_{i = 0}^n(x-x_i)$$

위에 식의 $x$에 새롭게 얻어진 $x_{n+1}$을 넣으면 아래와 같이 $p_n(x)$ 을 이용하여 $p_{n+1}(x)$ 를 효율적으로 구할 수 있다.

 $$ y_{n+1} = p_{n+1}(x_{n+1}) = p_n(x_{n+1})+a_{n+1}\prod_{i=0}^n(x_{n+1}- x_i)$$

$$a_{n+1}  = \frac{y_{n+1}-p_n(x_{x+1})}{\prod_{i =0}^n(x_{n+1}-x_i)}$$