체비셰프 전개

체비셰프 전개

Chebyshev Expansion

빌드업 1

체비셰프 전개를 이해하기 위해서는 어떻게 체비셰프 전개가 나오는지를 먼저 알아야한다. 우선 최소극대화 문제를 푸는 대신 최소제곱 문제를 푼다고 생각해보자. $$ M_{n} (f) := \inf_{\deg(r) \le n } \left\| f - r \right\|_{2} $$ $f : [a,b] \to \mathbb{R}$ 에 대해 위와 같이 최소제곱 문제가 주어져있다고 하자. 목표는 $M_{n} (f)$ 를 최소화하는 $n$ 차 이하의 다항함수 $r_{n}^{ \ast }$ 를 찾는 것이다. 다행스럽게도 다항함수의 공간 $\mathbb{R} [ x ]$ 은 웨이트 $w(x)$ 가 주어진 내적 $\displaystyle \left< f , g \right> : = \int_{a}^{b} f(x) g(x) w(x) dx$ 에 대해 유한차원 내적 공간이 되고, 그램-슈미트 프로세스에 의해 오소노멀 베이시스 $\left\{ \varphi_{k} \right\}_{k=0}^{n}$ 의 존재성이 보장되어 있어서 $$ r(x) = b_{0} \varphi_{0} (x) + b_{1} \varphi_{1} (x) + \cdots + b_{n} \varphi_{n} (x) $$ 와 같이 $r(x)$ 의 선형결합을 찾는 문제로 바꿀 수 있다. 다시 말해 최소제곱 문제란 $$ | f - r |_{2}^{2} = \int_{a}^{b} \left[ f(x) - \sum_{j=0}^{n} b_{j} \varphi_{j} (x) \right]^{2} w(x) dx $$ 이 최소값이 되도록 하는 $r = r_{n}^{ \ast }$ 을 찾는 것이다. $$ \begin{align*} \displaystyle 0 \le & | f - r |_{2}^{2} \\ =& \left< f - \sum_{j=0}^{n} b_{j} \varphi_{j} , f - \sum_{j=0}^{n} b_{j} \varphi_{j} \right> \\ =& \left< f , f \right> - 2 \sum_{j=0}^{n} b_{j} \left< f , \varphi_{j} \right> + \sum_{i} \sum_{j} b_{i} b_{j} \left< \varphi_{i} , \varphi_{j} \right> \\ =& | f |_{2}^{2} - 2 \sum_{j=0}^{n} b_{j} \left< f , \varphi_{j} \right> + \sum_{j=0}^{n} b_{j}^2 \\ =& | f |_{2}^{2} - \sum_{j=0}^{n} \left< f , \varphi_{j} \right>^2 + \sum_{j=0}^{n} \left[ \left< f , \varphi_{j} \right> - b_{j} \right]^2 \end{align*} $$ 여기서 $| f |_{2}^{2}$ 과 $\displaystyle \sum_{j=0}^{n} \left< f , \varphi_{j} \right>^2$ 는 $f$ 와 $\left\{ \varphi_{k} \right\}_{k=0}^{n}$ 이 이미 정해져있으므로 변하지 않는다. 따라서 가장 마지막 항 $\displaystyle \sum_{j=0}^{n} \left[ \left< f , \varphi_{j} \right> - b_{j} \right]^2$ 를 최소화하는 경우를 찾아야하는데, 이는 간단하게도 $b_{j} = \left< f , \varphi_{j} \right>$ 고 따라서 다음과 같은 최소제곱해를 구할 수 있다. $$ r_{n}^{ \ast } (x) = \sum_{j=0}^{n} \left< f , \varphi_{j} \right> \varphi_{j} (x) $$ 이제 본격적으로 체비셰프 다항함수에 대해서 이야기해보자.

정의 2

체비셰프 다항함수: $T_{n} (x) = \cos \left( n \cos^{-1} x \right)$ 을 제1종 체비셰프 다항함수라고 한다.

  • [3] 함수의 내적: $\displaystyle \left<f, g\right>:=\int_a^b f(x) g(x) w(x) dx$ 에 대해 웨이트 $w$ 를 $\displaystyle w(x) := {{1} \over { \sqrt{1 - x^2} }}$ 와 같이 주면 $\left\{ T_{0} , T_{1}, T_{2}, \cdots \right\}$ 은 직교 집합이 된다.

직교 기저 $\left\{ T_{k} \right\}_{k = 0}^{n}$ 이 정규화되도록 오소노멀 베이시스 $\left\{ \varphi_{k} \right\}_{k=0}^{n}$ 를 다음과 같이 정의하자. $$ \varphi_{n} (x) := \begin{cases} \displaystyle \sqrt{ {{1} \over { \pi }} } & , n=0 \\ \displaystyle \sqrt{ {{2} \over { \pi }} } T_{n} (x) & , n \in \mathbb{N} \end{cases} $$ 이러한 베이시스에 대해 다음 시리즈를 체비셰프 최소제곱 근사 , 혹은 그냥 체비셰프 전개 라고도 한다. $$ C_{n} (x) := \sum_{j=0}^{n} \left< f , \varphi_{j} \right> \varphi_{j} (x) $$ 혹은 때때로 $T_{k}$ 을 그대로 쓰는게 더 편할 때도 있어서 아래처럼 쓰기도 한다. $$ c_{j} := {{2} \over { \pi }} \int_{-1}^{1} {{f(x) T_{j} (x) } \over {\sqrt{1 - x^2 }}} dx $$

$$ C_{n} (x) = c_{0} + \sum_{j=1}^{n} c_{j} T_{j} (x) $$

설명

체비셰프 전개가 좋은 이유는 위와 같이 함수 근사에 좋은 조건들을 비교적 잘 만족시키기 때문이다:

  • (i): $f$ 가 $[-1,1]$ 에서 $f^{(r)}$ 이 존재하고 연속이라고 하면 체비셰프 최소제곱 근사 $C_{n}$ 와 $f,r$ 에 따른 어떤 상수 $B$ 에 대해 $\displaystyle | f - C_{n} |_{\infty} \le {{B \ln n} \over {n^{r}}}$
  • (ii): $C_{n+1} (x) = C_{n} (x) + c_{n+1} T_{n+1} (X)$
  • (iii): $\displaystyle c_{n+1} \sim {{1} \over {2^{n}}}$

함수 근사에 좋은 베이시스의 조건:

  • (i): $\displaystyle p_{n} (x)$ 이 $\displaystyle \left\{ \varphi_{n} (x) \in \mathbb{Q} [ x ] : n \ge 0 \right\}$ 의 선형결합으로 나타나며, $\displaystyle \max_{x \in [a,b]} | f(x) - p_{n} (x) |$ 이 원하는만큼 작아지도록 하는 $n \in \mathbb{N}$ 이 존재해야한다.
  • (ii): $p_{n} (x)$ 은 $\displaystyle p_{n} (x) = \sum_{k=0}^{n} a_{k} \varphi_{n} (X)$ 과 같이 계산되는 게 좋다. 즉, 오차를 줄이려고 할 때마다 완전히 새롭게 계산하는 게 아니라 새로운 항을 더함으로써 계산하는 게 좋다.
  • (iii): $| a_{n} |$ 이 빠르게 $0$ 으로 수렴하는 게 좋다. 즉, 최대한 적은 항만 더해도 빠르게 수렴하는 게 좋다.
  • (i): 체비셰프 전개를 알아야하는 가장 중요한 이유 중 하나다. 애초에 최소제곱법이란 분산이 가장 작아지도록 하는 근사해를 찾는것이지 글로벌하게 오차가 가장 작아지도록 하는 해를 찾는 방법은 아니다. 오차의 합이나 적분으로 계산하다보니 어떤 부분에선 잘 맞는데 어떤 부분에선 많이 틀릴 수도 있다. 그러한 불안함을 외면할 거였다면 애초부터 함수 근사를 할 이유가 없었다.함수 근사의 진짜 목적은 유니폼한 오차를 최소화하는 것, 즉 $\displaystyle \rho_{n} (f) = \inf_{\deg(q) \le n } \left\| f - q \right\|_{\infty}$ 가 작아지는 근사를 하는 것이다. $n^r$ 에 비해 $\ln n$ 의 발산 속도는 꽤나 느리므로, $\displaystyle | f - C_{n} |_{\infty} \le {{B \ln n} \over {n^{r}}}$ 이라는 부등식은 놀랍게도 체비셰프의 최소제곱 근사가 최소극대화 문제에서도 제법 쓸만하다는 것을 의미한다.
  • (ii): $T_{n}$ 은 이미 재귀적으로 모두 정해져있다. 이를 계산하는 것은 별로 어렵지 않으며, $c_{j}$ 역시 단순무식하게 계산하면 그만이다. 원하는 정확도까지 한 번에 계산할 필요가 없다는 점은 실용적인 측면에서 언제나 환영이다. 덜 정교해도 되면 그만큼 계산을 아낄 수 있고, 더 정교해야하더라도 이제까지 해온 계산을 버릴 필요가 없기 때문이다.
  • (iii): $f$ 를 근사하기 위한 다항함수 $p_{n+1}$ 을 다음과 같이 두 가지 방법으로 나타내보자. $$ \begin{align*} p_{n+1} (x) :=& a_{0} + a_{1} x + \cdots + a_{n} x^{n} + a_{n+1} x^{n+1} \\ p_{n+1} (x) :=& c_{0} + c_{1} T_{1} (x) + \cdots + c_{n} T_{n} (x) + c_{n+1} T_{n+1} (x) \end{align*} $$ $p_{n+1} (X)$ 의 최고차항의 계수 $a_{n+1}$ 은 곧 $c_{n+1} T_{n+1} (x)$ 의 최고차항의 계수와 같다. 그런데 $$ \begin{align*} T_{0} (x) =& 1 \\ T_{1} (x) =& x \\ T_{n+1} (x) =& 2x T_{n} (x) - T_{n-1} (x) \end{align*} $$ 이므로 $T_{n+1} (x)$ 의 최고차항의 계수는 $2^{n}$ 이다. 이를 수식으로 요약하면 $$ a_{n+1} = c_{n+1} 2^{n} \implies c_{n+1} = {{a_{n+1}} \over {2^{n}}} $$ 이다. 한편 $| T_{m} (x) | = \left| \cos \left( m \cos^{-1} x \right) \right| \le 1$ 이므로 $\displaystyle \left| c_{m+1} T_{m+1} (x) \right| = {{1} \over {2^{m}}} \left| a_{m+1} T_{m+1} (x) \right|$ 이라는 항은 꽤, 아니 엄청 빠르게 감소함을 알 수 있다. 이는 정성적으로 말해서 체비셰프 전개가 처음부터 좋은 베이시스를 취한것이라고 말 할 수 있다. 테일러 전개가 $1 , x , x^{2} , x^{3} , \cdots$ 처럼 속터지게 순수한 항을 더할 동안 체비셰프 전개는 함수를 근사하는데 도움이 크게 되는 함수부터 우선적으로 골라 이리 더하고 저리 빼는 식으로 속도를 올린 것이다.

  1. Atkinson. (1989). An Introduction to Numerical Analysis(2nd Edition): p216. ↩︎

  2. Atkinson. (1989). An Introduction to Numerical Analysis(2nd Edition): p219. ↩︎

댓글