[수치해석] 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 의 비용으로 마찬가지로 계산비용이 줄어들었습니다.