[수치해석] Polynomial form

수학 카테고리에서는 수학내용은 코딩은 하지 않고 지식만 정리하겠습니다.

수치해석을 하려면 미적분학과 선형대수의 지식이 어느정도 알아야 하긴 하는데 

일일히 다 설명하기가 어려우니 어느정도 다 안다고 가정하고 정리를 하겠습니다.

 

다항식 $p_{n}$을 표현해보겠습니다.

미적분학에서는 멱급수과 테일러 급수로 다항식을 무한 차수에 대해 표현하는데 데이터는 무한으로 갈 수 없으니 유한한 차원에 대해서 설명하겠습니다.

 

Power form

먼저 power form 부터 보면, 식이 $1,x,x^2,...,x^n$ 으로 이루어진 linear combination으로 나타내게 됩니다. 

가장 큰 차수가 n이니 degree가 n이 되겠습니다.

  $$p_{n} = a_{0} + a_{1}x + a_{2}x^{2} + ··· + a_{n}x^n = \sum_{k=0}^{n} a_{k}x^k  \tag{1}$$  

 

여기서 $a_{k}$ 는 계수입니다.

 

관점을 달리 하면 다음과 같이 표현할 수 있습니다.

$$p_{n} = b_{0} + b_{1}(x-c) + b_{2}(x-c)^2 +  ··· + b_{n}(x-c)^n$$       

즉, c가 중심(centre)이 되는 다항식으로 볼 수 있습니다. 그러면 위의 (1)식은 c=0인 다항식이 됩니다.

이런 형식을 shifted power form 이라고 합니다.

 

 

Taylor polynomial

Taylor form은 테일러 급수처럼 표현하는 형식을 말하는데 shifted power form에서 계수를 지정함으로써 나타낼 수 있습니다. 따라서 $$b_{k} = \frac{p_{n}^{(k)}(c)}{k!}$$ 이 됩니다.

수학적 귀납법으로 증명을 하면 해당값이 나옵니다. 중요한 증명이 아니니 생략합니다~!

shifted power form에서 $b_{k}$를 대체하면 다음과 같이 나옵니다.

$$p_{n}(x) = p_{n}(c) + (x-c)p'_{n}(c) + \frac{(x-c)^2}{2!}p''_{n}(c) + ··· + \frac{(x-c)^n}{n!}p_{n}^{(n)}(c)$$

여기서 $p^{(k)}$ 는 p를 k 번 미분했다는 의미입니다.

이것이 Taylor polynomial 입니다.

 

Newton form

이번에는 중심이 여러개인 경우입니다. 중심이 $c_{1},c_{2},...,c_{n}$ 일 때, 다음과 같이 표현합니다.

$$p_{n} = d_0 + d_1(x-c_1) +d_2(x-c_1)(x-c_2)+ ··· + d_n(x-c_1)...(x-c_n) = d_0 + \sum_{k=1}^{n} d_k \prod_{j=1}^{k}(x-c_j)$$

 

Newton form에서

$c_1 = ··· = c_n = c$ 로 놓으면 shifted power form 이 되고 

$c_1 = ··· = c_n = 0$ 이면 power form이 됩니다.

 

Nested evaluation 

이번에는 계산 비용(cost)을 줄이기 위한 방안으로 하는 방법입니다. 

위에서 언급한 power form을 실제로 계산하게 된다면 몇 번 곱하는지 체크할 수 있는데

k차항의 power form $a_{k}x^{k}$ 이라고 가정한다면 k 번의 곱셈이 필요하게 됩니다.

이런 항이 (1)번 식에는 n+1항으로 되어있으니 비용은 $\sum_{k=0}^{n} k = \sum_{k=1}^{n} k =  \frac{n(n+1)}{2}$ 이고 n번 더해야하니 총 비용은 $\frac{n(n+3)}{2}$ 이 됩니다. 

 

코스트 줄이는 것이 목적이므로 다음과 같이 표현할 수 있습니다.

$$p_{n}(x) = a_0 +x(a_1+x(a_{2}+···+a_{n-1}x^{n-3} + a_{n}x^{n-2}))$$

이런 방식으로 $a_n$ 까지 가게 된다면 

$$p_{n}(x) = a_0 +x(a_1+x(a_{2}+···+a_{n-1}x^{n-3} + a_{n}x^{n-2}+x(a_{n-1}+a_{n}x...))$$

이런 방식으로 만들어진 형식을 nested power form이라고 합니다.

nested form으로 만들면 계산비용이 2n으로 이차식의 계산비용에서 일차식으로 확연히 줄어들게 됩니다.

 

 

nested form을 Newton form에도 적용할 수 있는데

$$p_{n}(x) = d_{0} +(x-c_{1})(d_{1}+(x-c_{2})(d_{2}+ ···+(x-c_{n-2})(d_{n-1} + d_{n}(x-c_n))).....))$$  

이 됩니다. 3n 의 비용으로 마찬가지로 계산비용이 줄어들었습니다.