📂수치해석

체비셰프 전개

빌드업 ¹

체비셰프 전개를 이해하기 위해서는 어떻게 체비셰프 전개가 나오는지를 먼저 알아야한다. 우선 최소극대화 문제를 푸는 대신 최소제곱 문제를 푼다고 생각해보자. $$ 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) $$ 이제 본격적으로 체비셰프 다항함수에 대해서 이야기해보자.

정의 ²

체비셰프 다항함수: $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$ 처럼 속터지게 순수한 항을 더할 동안 체비셰프 전개는 함수를 근사하는데 도움이 크게 되는 함수부터 우선적으로 골라 이리 더하고 저리 빼는 식으로 속도를 올린 것이다.