///
Search
📄

Chapter 6

How to find the beset approximating polynomial in the uniform norm

본 챕터에선 앞에서 확인한 내용들을 기반으로 체비셰프를 이용하여 uniform-norm에 대한 근사문제를 풀어본다. 또한 L2L^2-norm과의 비교를 진행할 것이며 그 후에 최적근사함수를 찾기 위한 몇가지 테크닉을 살펴볼 것이다. 본 챕터의 마지막에선 몇가지 예제를 제공하여 살펴본다.

6.1 Chebyshev’s solution

이번 섹션에선 체비셰프가 해결할 수 있었던 최적화 문제를 단계별로 살펴본다.
우선 체피셰프가 풀고싶어 했던 문제는 아래와 같다.

Problem 3.

구간 [−1,1][-1,1]에서 f(x)=xnf(x)=x^n 에 대한 n−1n-1차 최적근사 다항식 pn−1=∈Pn−1p_{n-1}=\in\mathcal{P}_{n-1}를 찾아라.
이 문제는 f(x)=xnf(x)=x^n과 pn−1(x)p_{n-1}(x)사이의 에러를 최소화하는 문제며 즉 max⁡x∈[−1,1]∣xn−pn−1∣\max_{x\in[-1,1]}{|x^n-p_{n-1}|}를 최소화하는 pn−1p_{n-1}를 찾아야 한다.
이를 해결하기 위한 체비셰프의 솔루션은 아래단계와 같이 진행된다.
1.
개념을 단순화 시킨다. E(x)=xn−pE(x)=x^n-p이고 M=∣∣E∣∣∞M=||E||_{\infty}라 하자. 기존에 보인대로 E(x)E(x)는 (n−1)+2=n+1(n-1)+2=n+1개의 alternating set을 갖는다(−1≤x0<x1<⋯<xn≤1-1\le x_0 < x_1 < \cdots <x_n \le 1). 또한 E(x)E(x)는 적어도 (n−1)+1=n(n-1)+1=n개의 해를 가지고 모든 ii에 대해 ∣E(xi)∣=M|E(x_i)|=M와 E(xi+1)=−E(xi)E(x_{i+1})=-E(x_i)가 성립한다.
2.
E(xi)E(x_i)는 E(x)E(x)의 극점이다. 따라서 구간 (−1,1)(-1,1)의 임의의 점 xix_i는 E′(xi)=0E^{\prime}(x_i)=0을 만족한다. 또한 E′(x)E^{\prime}(x)는 n−1n-1차 다항식이므로 n−1n-1개의 해를 갖게 된다. 즉, x0x_0과 xnx_n은 각각 양 끝점 −1-1과 11이 되어야 구간부호가 바뀌는 alternating set임과 동시에 E′(x)E^{\prime}(x)의 해가 아니게 된다. 따라서 아래 식이 성립한다.
xi∈(−1,1)      and      E′(xi)=0      for      i=1,⋯ ,n−1,x0=−1,      E′(x0)≠0,xn=1,      E′(xn)≠0.\begin{align*} x_i\in (-1,1)\;\;\;\mathbf{and} \;\;\; &E^{\prime}(x_i)=0 \;\;\; &\mathbf{for}\;\;\;i=1,\cdots,n-1,&\\ x_0=-1,\;\;\;&E^{\prime}(x_0)\neq 0,& x_n=1,\;\;\;E^{\prime}(x_n)\neq0.& \end{align*}
3.
다항식 M2−E2∈P2nM^2-E^2\in \mathcal{P}_{2n}에 대해 고려한다. i=0,1,⋯ ,ni=0,1,\cdots,n에 대해 M2−(E(xi))2=0M^2-(E(x_i))^2=0가 성립하고 구간 [−1,1][-1,1]에서 M2−E2≥0M^2-E^2\ge0이 성립한다. 즉, M2−E2M^2-E^2은 xix_i에서 00이 되고 모든 구간에 대해 00보다 크므로 x1,⋯ ,xn−1x_1,\cdots,x_{n-1}는 중근(double root)이 된다. M2−E2M^2-E^2은 2n2n차 다항식이므로 최대 2n2n개의 해를 갖는다. 2(n−1)+2=2n2(n-1)+2=2n이므로 이는 M2−E2M^2-E^2가 n−1n-1개의 중근과 22개의 단일근(single root)를 가지며 이것이 M2−E2M^2-E^2의 모든 해가 됨을 알 수 있다.
4.
다음은 (E′(x))2∈P2(n−1)(E^{\prime}(x))^2\in\mathcal{P}_{2(n-1)}에 대해 고려한다. 위 2,3번단계에서 x1,⋯ ,xn−1x_1,\cdots,x_{n-1}에서 중근을 가짐을 알 수 있고 이에 따라 이들이 E′(x)=0E^{\prime}(x)=0의 해가 됨을 알 수 있다. 따라서 (1−x2)(E′(x))2(1-x^2)(E^{\prime}(x))^2은 x1,⋯ ,xn−1x_1,\cdots,x_{n-1}에서 중근을 가지고 x0=−1x_0=-1과 xn=1x_n=1에서 단일근을 가지는 다항식이다. 또한 (1−x2)(E′(x))2∈P2n(1-x^2)(E^{\prime}(x))^2\in \mathcal{P}_{2n}이므로 M2−E2M^2-E^2와 같은 차수로 같은 해를 가진다.
5.
위 4번단계로 부터 (1−x2)(E′(x))2(1-x^2)(E^{\prime}(x))^2과 M2−E2M^2-E^2는 같은 차수의 같은해를 가지는 다항식임을 알 수 있다. 이는 두 다항식이 어느 한쪽에 상수곱을 해서 같은 식으로 만들어 줄 수 있음을 의미한다. E(x)E(x)는 일계수다항식 이므로 최고차항의 계수가 11이 된다. 이에 따라 E′(x)E^{\prime}(x)의 최고차항 계수는 nn이 된다. 그러므로 아래 식이 성립한다.
M2−(E(x))2=(1−x2)(E′(x))2n2E′(x)M2−(E(x))2=n1−x2.M^2-(E(x))^2=\frac{(1-x^2)(E^{\prime}(x))^2}{n^2} \\ \frac{E^{\prime}(x)}{\sqrt{M^2-(E(x))^2}} = \frac{n}{\sqrt{1-x^2}}.
E′E^{\prime}은 어떤 구간에선 양의 값을 가지며 때문에 일관성을 잃지 않고 [−1,x1][-1,x_1]에선 양수라고 둘 수 있다. 이를 통해 부호에 대한 고려를 제외하고 양 변을 적분하면 아래와 같다.
arccos⁡(E(x)M)=narccos⁡(x)+CE(x)=Mcos⁡(narccos⁡(x)+C)\arccos\bigg(\frac{E(x)}{M}\bigg)=n\arccos(x)+C \\ E(x)=M\cos(n\arccos(x)+C)
∫arccos⁡(x)dx=11−x2+C\int{\arccos(x)}dx = \frac{1}{\sqrt{1-x^2}} + C이므로 위와 같은 식이 만족된다. 또한 위에서 E(−1)≥0E(-1)\ge0임을 가정했으므로 E(−1)=−ME(-1)=-M이 된다. 따라서 아래 식을 전개하면
E(−1)=Mcos⁡(narccos⁡(−1)+C)=−Mcos⁡(nπ+C)=−1nπ+C=arccos⁡(−1)=π+2kπ    (k∈Z)C=mπ      with      n+m      oddE(x)=±Mcos⁡(narccos⁡(x)).\begin{align*} E(-1)=M\cos(n\arccos(-1)+C)=-M \\ \cos(n\pi+C)=-1\\ n\pi+C=\arccos(-1)=\pi+2k\pi\;\;(k\in \mathbb{Z})\\ C=m\pi\;\;\;\mathbf{with}\;\;\;n+m\;\;\;\mathbf{odd} \\ E(x)=\pm M \cos(n\arccos(x)). \end{align*}
cos⁡(narccos⁡(x))\cos(n\arccos(x))는 nn번째 체비셰프 다항식이다. Tn+1(x)=2xTn(x)−Tn−1(x)T_{n+1}(x)=2xT_n(x)-T_{n-1}(x)이므로 nn차식의 최대차항의 계수는 2n−12^{n-1}이다. 따라서 최대차항의 계수가 11인 E(x)E(x)는 E(x)=2−n+1Tn(x)E(x)=2^{-n+1}T_n(x)라 할 수 있다. ∣x∣<1|x|<1에 대해 ∣Tn(x)∣≤1|T_n(x)|\le1이므로 최소값 M=2−n+1M=2^{-n+1}이다.

Theorem 6

임의의 nn에 대해 p∈Pn−1p\in \mathcal{P}_{n-1}인 함수 p(x)=xn−2−n+1Tn(x)p(x)=x^n-2^{-n+1}T_n(x)는 모든 q∈Pn−1q\in \mathcal{P}_{n-1}에 대해 아래 식을 만족한다.
2−n+1=max⁡∣x∣≤1∣xn−p(x)∣<max⁡∣x∣≤1∣xn−q(x)∣2^{-n+1}=\max_{|x|\le1}|x^n-p(x)| < \max_{|x|\le1}|x^n-q(x)|

Proof.

Corollary 2

구간 C[a,b]C[a,b]에서 일계수 nn차 다항식의 최소크기(smallest norm)는 아래와 같다.
(b−a)n2n2n−1⋅Tn(2x−b−ab−a).\frac{(b-a)^n}{2^n2^{n-1}}\cdot T_n \bigg(\frac{2x-b-a}{b-a}\bigg).

Proof.

위 Theorem 6와 Corollary 2를 이용하여 구간 [−1,1][-1,1]에서 최고차항의 계수가 a0a_0인 nn차 다항식 f(x)f(x)에 대한 n−1n-1차 최적근사 다항식 p(x)p(x)을 구하는 방법을 아래와 같이 일반화 할 수 있다.

Corollary 3 (Generalization)

최고차항의 계수가 a0a_0인 함수 f(x)f(x)가 주어졌을 때,
1.
구간 [−1,1][-1,1]에서 f(x)f(x)에 최대 n−1n-1차인 최적근사 다항식 p(x)p(x)는 아래와 같다.
p(x)=f(x)−a02−n+1Tn(x),p(x)=f(x)-a_02^{-n+1}T_n(x),
또한 최대오차(maximum error)로 a02−n+1a_0 2^{-n+1}를 갖는다. 이 테크닉을 체비셰프 최적화(Chebyshev approximation)이라 한다.
2.
구간 C[a,b]C[a,b]에서 최소크기(smallest norm)를 가지는 nn차 다항식은 아래와 같다.
a0⋅(b−a)n2n2n−1⋅Tn(2x−b−ab−a)a_0\cdot\frac{(b-a)^n}{2^n2^{n-1}}\cdot T_n\bigg(\frac{2x-b-a}{b-a}\bigg)
이 테크닉을 smallest norm이라 한다.
위 두 개의 방식을 통해 최고차항의 계수가 a0a_0인 최적근사 다항식 p(x)∈Pnp(x) \in \mathcal{P}_n을 구할 수 있다. 섹션6.3에선 두 방식을 통해 최적근사 다항식을 찾아볼 것이다.

6.2 Comparison to approximation in the L2L^2-norm

이번 세션에선 L2L^2-norm에서의 근사와 uniform-norm에서의 근사를 비교할 것이다.

6.2.1 Differences between approximation in the L2L^2-norm and in the uniform norm

이번 섹션에선 L2L^2-norm과 uniform-norm에서 최적화 과정의 차이점을 살펴볼 것이다.
이 두가지 방식의 두 가지 차이점은 아래와 같다.
•
Uniform-norm: 최대 절대편차를 최소화 한다. 따라서 ∣∣f(x)−p(x)∣∣2=max⁡a≤x≤b∣f(x)−p(x)∣||f(x)-p(x)||_2=\max_{a\le x \le b}|f(x)-p(x)|를 최소화 하는 과정을 가진다.
•
L2L^2-norm: 최대 절대편차의 제곱의 합을 최소화한다. 따라서 ∣∣f(x)−p(x)∣∣2=∫ba∣f(x)−p(x)∣2dx||f(x)-p(x)||_2 = \sqrt{\int_b^a|f(x)-p(x)|^2dx}를 최소화 한다.
함수 norm의 값은 어떤 norm이냐 뿐만 아니라 어떤 함수를 쓰느냐에도 많은 영향을 받는다.
∣∣f∣∣∞<∞||f||_{\infty} < \infty일 때 아래 수식이 성립한다.
∣∣f∣∣2=∫ab∣f∣2dx≤(b−a)∣∣f∣∣∞||f||_2 = \sqrt{\int_a^b|f|^2dx} \le (b-a)||f||_{\infty}
그러나 어떤 함수는 ∣∣f∣∣2||f||_2는 작고 ∣∣f∣∣∞||f||_{\infty}는 큰 값을 계산할 수 도 있다. 그러므로, norm을 선택하는 것은 최적화 문제의 솔루션에 많은 영향을 줄 수 있다.

6.2.2 Similarity between approximation in the L2L^2-norm and in the uniform norm

이번 섹션에선 두 norm의 유사한 점을 살펴본다.
chapter 5에서 체비셰프 다항식이 (−1,1)(-1,1)에서 weight function이 w(x)=11−x2w(x)=\frac{1}{\sqrt{1-x^2}} 일 때 직교(orthogonal) 한 것을 확인했다(직교하게 만들기 위해 weight function을 이렇게 잡았다고 해도 된다). 이 구간에선 L2L^2-norm과 uniform-norm에서 모두 최적근사 다항식이 같다.
물론 대수 다항식을 제외한 나머지 함수에선 아래와 같은 식이 성립하지 않아 위 가정이 맞지 않는다.
∫−11f(x)g(x)1−x2dx≠max⁡x∈[−1,1]∣f(x)−g(x)∣.\int^1_{-1}\frac{f(x)g(x)}{\sqrt{1-x^2}}dx \neq \max_{x\in[-1,1]}|f(x)-g(x)|.
때문에 본 예제에선 구간[−1,1][-1,1]에서 f(x)=xnf(x)=x^n를 가정하여 진행한다.
내적 공간 VV에서 f(x)f(x)의 basis는 {1,x,x2,⋯ ,xn}\{1, x, x^2, \cdots,x^n \}이고 이를 그램-슈미트 과정을 진행시키면 아래와 같다.
u1=(1∣∣x1∣∣)x1=1πp1=⟨x2,u1⟩u1=⟨x,1π⟩1π=0u2=1∣∣x2−p1∣∣(x2−p1)=1∣∣x∣∣x=2πxp2=⟨x3,u1⟩u1+⟨x3,u2⟩u2=⟨x2,1π⟩1π+⟨x2,2πx⟩2πx=12u3=1∣∣x3−p2∣∣(x3−p2)=1∣∣x2−12∣∣(x2−12)=22π(x2−12).\begin{align*} &u_1=&\bigg(\frac{1}{||x_1||}\bigg)x_1 &=\frac{1}{\sqrt{\pi}} \\ &p_1=&\langle x_2, u_1 \rangle u_1=\langle x, \frac{1}{\sqrt{\pi}} \rangle \frac{1}{\sqrt{\pi}} &=0 \\ &u_2=&\frac{1}{||x_2-p_1||}(x_2-p_1)=\frac{1}{||x||}x &= \frac{\sqrt{2}}{\sqrt{\pi}}x \\ &p_2=&\langle x_3,u_1 \rangle u_1 + \langle x_3,u_2\rangle u_2= \langle x^2,\frac{1}{\sqrt{\pi}}\rangle \frac{1}{\sqrt{\pi}} + \langle x^2, \frac{\sqrt{2}}{\sqrt{\pi}}x\rangle\frac{\sqrt{2}}{\sqrt{\pi}}x &= \frac{1}{2} \\ &u_3=&\frac{1}{||x_3-p_2||}(x_3-p_2)=\frac{1}{||x^2-\frac{1}{2}||}(x^2-\frac{1}{2}) &= \frac{2\sqrt{2}}{\sqrt{\pi}}(x^2-\frac{1}{2}). \end{align*}
이번엔 다른 직교 시스템의 항을 통해 p(x)p(x)를 계산한다.
{1π,2πT1,2πT2,⋯ ,2πTn}.\{ \frac{1}{\sqrt{\pi}}, \frac{\sqrt{2}}{\sqrt{\pi}}T_1, \frac{\sqrt{2}}{\sqrt{\pi}}T_2,\cdots,\frac{\sqrt{2}}{\sqrt{\pi}}T_n\}.
p(x)=⟨f,u1⟩⟨u1,u1⟩u1(x)+⟨f,u2⟩⟨u2,u2⟩u2(x)+⋯+⟨f,un⟩⟨un,un⟩u(x).p(x)=\frac{\langle f,u_1 \rangle}{\langle u_1,u_1 \rangle}u_{1}(x) + \frac{\langle f,u_2 \rangle}{\langle u_2,u_2 \rangle}u_{2}(x) + \cdots + \frac{\langle f,u_n \rangle}{\langle u_n,u_n \rangle}u_{}(x).
모든 i=1,⋯ ,ni=1,\cdots,n에 대해 ⟨ui,ui⟩=1\langle u_i, u_i \rangle = 1이 성립하므로 위 식을 다시 아래와 같이 정리할 수 있다.
p(x)=⟨f,1π⟩1π+⟨f,2πT1⟩2πT1+⋯+⟨f,2πTn⟩2πTn.p(x)=\langle f,\frac{1}{\sqrt{\pi}} \rangle\frac{1}{\sqrt{\pi}} + \langle f,\frac{\sqrt{2}}{\sqrt{\pi}}T_1 \rangle\frac{\sqrt{2}}{\sqrt{\pi}}T_1 + \cdots + \langle f,\frac{\sqrt{2}}{\sqrt{\pi}}T_n \rangle\frac{\sqrt{2}}{\sqrt{\pi}}T_n.
이를 계산하면 아래와 같다.
⟨f,u1⟩=1π∫−11xn(1−x2)dx⟨f,u2⟩=2π∫−11xnT1(1−x2)dx⟨f,u3⟩=2π∫−11xnT2(1−x2)dx          ⋮⋮                                        \begin{align*} &\langle f,u_1 \rangle&=\frac{1}{\sqrt{\pi}}\int_{-1}^1\frac{x^n}{\sqrt{(1-x^2)}} dx \\ &\langle f,u_2 \rangle&=\frac{\sqrt{2}}{\sqrt{\pi}}\int_{-1}^1\frac{x^nT_1}{\sqrt{(1-x^2)}} dx \\ &\langle f,u_3 \rangle&=\frac{\sqrt{2}}{\sqrt{\pi}}\int_{-1}^1\frac{x^nT_2}{\sqrt{(1-x^2)}} dx \\ &\;\;\;\;\;\vdots &\vdots \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; \end{align*}
위 식은 상당히 복잡하여 계산과정은 생략한다. 즉, 이 경운 L2L^2-norm을 사용하면 계산하기 상당히 까다로와 진다. 그러나 체비셰프 최적화를 이용할 경우 아래와 같이 훨씬 더 쉽고 간단하게 최적화 과정을 진행할 수 있다.
n=n=
f(x)=f(x)=
BasisBasis
p(x)=p(x)=
11
xx
{1}\{1\}
00
22
x2x^2
{1,x}\{1,x\}
12\frac{1}{2}
33
x3x^3
{1,x,x2}\{1,x,x^2\}
34x\frac{3}{4}x
44
x4x^4
{1,x,x2,x3}\{1,x,x^2,x^3\}
x2−14x^2-\frac{1}{4}
55
x5x^5
{1,x,x2,x3,x4}\{1,x,x^2,x^3,x^4\}
54x3−516x\frac{5}{4}x^3-\frac{5}{16}x
66
x6x^6
{1,x,x2,x3,x4,x5}\{1,x,x^2,x^3,x^4,x^5\}
32x4−916x2+132\frac{3}{2}x^4-\frac{9}{16}x^2+\frac{1}{32}

6.3 Other techniques and utilities

이번 세션에선 최적근사 다항식을 찾기 위한 두 가지 테크릭을 사려보고 왜 이러한 테크닉이 유용한가를 확인한다.

6.3.1 Economization

TnT_n을 xnx^n에 대한 식으로 표현한 것과 반대로 xnx^n을 TnT_n과 관련된 식으로 표현할 수 있다.
1=T0x=T1x2=12(T0+T2)x3=14(3T1+T3)x4=18(3T0+4T2+T4)\begin{align*} &1=T_0 \\ &x=T_1 \\ &x^2=\frac{1}{2}(T_0+T_2) \\ &x^3=\frac{1}{4}(3T_1+T_3) \\ &x^4=\frac{1}{8}(3T_0+4T_2+T_4) \end{align*}
xx의 제곱형태를 체비셰프 다항식으로 표현함으로써 계산량을 줄일 수 있다. 게다가 체비셰프 형태는 훨씬 더 작은 계수를 가지며 이로써 더 적은 오차로 낮은 차수의 다항식으로 근사할 수 있다.

Example 3.

이번 예제에선 구간 [−1,1][-1,1]에서 f(x)=1−x+x2−x3+x4f(x)=1-x+x^2-x^3+x^4의 최적근사함수 p(x)∈P3p(x)\in\mathcal{P}_3를 찾는다. 위 식 f(x)f(x)를 체비셰프 다항식을 통해 다시 아래와 같이 표현할 수 있다.
1−x+x2−x3+x4=T0−T1+12(T0+T2)−14(3T1+T3)+18(3T0+4T2+T4)=158T0−74T1+T2−14T3+18T4.\begin{align*} 1-x+x^2-x^3+x^4 &= T_0-T_1+\frac{1}{2}(T_0+T_2)-\frac{1}{4}(3T_1+T_3)+\frac{1}{8}(3T_0+4T_2+T_4) \\ &=\frac{15}{8}T_0-\frac{7}{4}T_1+T_2-\frac{1}{4}T_3+\frac{1}{8}T_4. \end{align*}
3차함수로 근사할 것이기 때문에 T4T_4항을 없애야 한다. 때문에 최적근사함수는 p=78−x+2x2−x3p=\frac{7}{8}-x+2x^2-x^3가 된다. 이렇게 근사하면 대략 18\frac{1}{8}의 오차를 가진다. 만약 이러한 테크닉을 활용하지 않고 q(x)=1−x+x2−3x3q(x)=1-x+x^2-3x^3라 하면 오차를 거의 11정도로 가져가게 된다.
일반적인 상황에서 전체과정은 다음과 같다. 함수 f(x)f(x)는 멱급수(power series)거나 멱급수로 표현이 가능하기 때문에 f(x)≈Pn(x)=anxn+an−1xn−1+⋯+a1x+a0f(x)\approx P_n(x)=a_nx^n+a_{n-1}x^{n-1}+\cdots + a_1x+a_0로 표현할 수 있다. 이를 더 낮은 차수인 Pn−1P_{n-1}로 근사해야한다. PnP_n과 같이 ana_n을 최고차항의 계수로 갖는 nn차 다항식을 QnQ_n이라 하면 Qn=anxn+⋯=an2−n+1Tn+⋯Q_n=a_nx^n+\cdots=a_n2^{-n+1}T_n+\cdots로 표현할 수 있다. 이 때 Pn−1=Pn−QnP_{n-1}=P_n-Q_n로 표현할 수 있다. 따라서 아래와 같이 전개된다.
max⁡∣f(x)−Pn−1(x)∣=max⁡∣f(x)−(Pn(x)−Qn(x))∣≤max⁡∣f(x)−Pn(x)∣+max⁡∣Qn(x)∣\begin{align*} \max|f(x)-P_{n-1}(x)| &= \max|f(x)-(P_n(x)-Q_n(x))| \\ &\le \max|f(x)-P_n(x)|+\max|Q_n(x)| \end{align*}
만약 f(x)f(x)가 멱급수 형태라면 max⁡∣f(x)−Pn(x)∣=0\max|f(x)-P_n(x)|=0이 된다. QnQ_n을 가장 큰 오차로 근사하면 an2−n+1Tna_n2^{-n+1}T_n라 둘 수 있다. 따라서 ∣x∣<1|x|<1에서 ∣Tn(x)∣≤1|T_n(x)|\le 1이므로 Qn≈an2−n+1Tn≤an2−n+1∣Tn∣≤an2−n+1Q_n\approx a_n2^{-n+1}T_n \le a_n2^{-n+1}|T_n| \le a_n2^{-n+1}라 할 수있다. 정리하면 max⁡∣Qn(x)∣=an2−n+1\max |Q_n(x)|=a_n2^{-n+1}라 할 수 있고 최종적으로 정확도 오차는 an2n−1\frac{a_n}{2^{n-1}}라 할 수 있다.

6.3.2 Transformation of the domain

위 예제에선 구간 [−1,1][-1,1]에서의 문제를 다루었다. 그러나 정의역의 구간은 이와 다를 수 있으므로 유한한 구간으로 가지는 변수 a≤y≤ba\le y \le b를 −1≤x≤1-1\le x\le 1로 치환하여 문제를 해결할 수 있다. 치환을 위해 아래와 같이 yy와 xx의 관계식을 도출할 수 있다.
y=12(b−a)x+12(b+a)y=\frac{1}{2}(b-a)x+\frac{1}{2}(b+a)
만약 yy의 구간이 0≤y≤10 \le y \le 1이라 하면 아래와 같이 단순화 된다.
y=12(x+1),      x=2y−1y=\frac{1}{2}(x+1),\;\;\;x=2y-1
위와 같이 정의된 정의역을 위해 체비셰프 다항식 Tn⋆(x)=Tn(2x−1),  0≤x≤1T^{\star}_n(x)=T_n(2x-1),\;0\le x \le 1로 표현하면 아래와 같이 정리할 수 있다.
T0⋆(x)=1      1=T0⋆                                                                                    T1⋆(x)=2x−1      x=12(T0⋆+T1⋆)                                                        T2⋆(x)=8x2−8x+1      x2=18(3T0⋆+4T1⋆+T2⋆)                              T3⋆(x)=32x3−48x2+18x−1      x3=132(10T0⋆+15T1⋆+6T2⋆+T3⋆)\begin{align*} &T^{\star}_0(x)=1\;\;\; &1=T^{\star}_0 \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\\ &T^{\star}_1(x)=2x-1\;\;\; &x=\frac{1}{2}(T^{\star}_0 + T^{\star}_1) \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\\ &T^{\star}_2(x)=8x^2-8x+1\;\;\; &x^2=\frac{1}{8}(3T^{\star}_0 + 4T^{\star}_1+T^{\star}_2) \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\\ &T^{\star}_3(x)=32x^3-48x^2+18x-1\;\;\; &x^3=\frac{1}{32}(10T^{\star}_0 + 15T^{\star}_1+6T^{\star}_2 + T^{\star}_3) &\\ \end{align*}
위 수식은 xx를 2x−12x-1로 치환하거나 Tn+1⋆(x)=2(2x−1)Tn⋆(x)−Tn−1⋆(x)T^{\star}_{n+1}(x)=2(2x-1)T^{\star}_{n}(x)-T^{\star}_{n-1}(x)를 이용하여 도출할 수 있다. 도메인의 구간이 작을수록 오차의 크기가 더 줄어들게 된다.

Example 4.

f(x)=x3+x2f(x)=x^3+x^2을 이차 다항식으로 근사해보자. 이 문제를 economization으로 풀어본다.
먼저 구간 [−1,1][-1,1]에서 진행한다.
x3+x2=14(3T1+T3)+12(T0+T2)=12T0+34T1+12T2+14T3.\begin{align*} x^3+x^2&=\frac{1}{4}(3T_1+T_3) + \frac{1}{2}(T_0+T_2) \\ &=\frac{1}{2}T_0+\frac{3}{4}T_1+\frac{1}{2}T_2+\frac{1}{4}T_3. \end{align*}
이차 다항식으로 근사해야하므로 T3T_3항을 제거한다. 이 때 최대오차는 14\frac{1}{4}가 되고 최적근사함수는 p(x)=x3+34xp(x)=x^3+\frac{3}{4}x가 된다.
다음은 같은 문제를 다루되 구간을 [0,1][0,1]로 두고 T⋆T^{\star}를 통해 해결한다.
x3+x2=132(10T0⋆+15T1⋆+6T2⋆+T3⋆)+18(3T0⋆+4T1⋆+T2⋆)=1116T0⋆+3132T1⋆+516T2⋆+132T3⋆\begin{align*} x^3+x^2&=\frac{1}{32}(10T^{\star}_0+15T^{\star}_1+6T^{\star}_2+T^{\star}_3)+\frac{1}{8}(3T^{\star}_0+4T^{\star}_1+T^{\star}_2) \\ &= \frac{11}{16}T^{\star}_0+\frac{31}{32}T^{\star}_1+\frac{5}{16}T^{\star}_2+\frac{1}{32}T^{\star}_3 \end{align*}
다음 T3⋆T^{\star}_3항을 제거한다. 이때 p(x)=132−916x+52x2p(x)=\frac{1}{32}-\frac{9}{16}x+\frac{5}{2}x^2가 되고 최대오차는 132\frac{1}{32}가 된다.
다음은 같은 문제를 다루되 구간을 [−3,3][-3,3]에서 진행한다.
먼저 변수를 치환하는 과정을 진행한다.
y=12(b−a)x+12(b+a)=12(3+3)(x)+12(3−3)=3x,      x=13y.\begin{align*} y&=\frac{1}{2}(b-a)x+\frac{1}{2}(b+a) \\ &=\frac{1}{2}(3+3)(x)+\frac{1}{2}(3-3) \\ &=3x, \;\;\; x=\frac{1}{3}y. \end{align*}
이를 이용하여 4차까지 체비셰프 다항식을 표현하면 아래와 같다.
T0⋆(x)=1      1=T0⋆                                                                                    T1⋆(x)=13x      x=3T1⋆                                                                                T2⋆(x)=29x2−8x+1      x2=18(3T0⋆+4T1⋆+T2⋆)                              T3⋆(x)=32x3−48x2+18x−1      x3=132(10T0⋆+15T1⋆+6T2⋆+T3⋆)\begin{align*} &T^{\star}_0(x)=1\;\;\; &1=T^{\star}_0 \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\\ &T^{\star}_1(x)=\frac{1}{3}x\;\;\; &x=3T^{\star}_1 \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\\ &T^{\star}_2(x)=\frac{2}{9}x^2-8x+1\;\;\; &x^2=\frac{1}{8}(3T^{\star}_0 + 4T^{\star}_1+T^{\star}_2) \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\\ &T^{\star}_3(x)=32x^3-48x^2+18x-1\;\;\; &x^3=\frac{1}{32}(10T^{\star}_0 + 15T^{\star}_1+6T^{\star}_2 + T^{\star}_3) &\\ \end{align*}
이를 이용하여 f(x)f(x)를 표현하면 아래와 같이 전개된다.
x3+x2=274T3⋆+814T1⋆+92T2⋆+92T0⋆x^3+x^2=\frac{27}{4}T^{\star}_3+\frac{81}{4}T^{\star}_1+\frac{9}{2}T^{\star}_2+\frac{9}{2}T^{\star}_0
다음 T3⋆T^{\star}_3항을 제거한다. 이때 p(x)=x2+274xp(x)=x^2+\frac{27}{4}x가 되고 최대오차는 274\frac{27}{4}가 된다.
최대오차는 구간 [0,1][0,1]에서 132\frac{1}{32}, 구간 [−1,1][-1,1]에서 14\frac{1}{4}, 구간 [−3,3][-3,3]에서 274\frac{27}{4}이 되며 이를 통해 구간의 크기가 증가 할 수록 최대오차의 크기가 늘어남을 확인할 수 있다.

6.3.3 Generating function

이번 섹션에선 앞에서 활용했던 TnT_n이나 Tn⋆T_n^{\star}의 일반 표현식을 찾아본다. 이를 위해 급수의 인 ∑n=0∞anTn(x)\sum^{\infty}_{n=0}a^n T_n(x)에 대해 고민해보자. x=cos⁡(θ)x=\cos(\theta)라 하면(−1≤x≤1-1\le x \le 1) 아래와 같이 전개된다.
Tn(x)=cos⁡(narccos⁡(x))=cos⁡(narccos⁡(cos⁡(θ)))=cos⁡(nθ)=einθ−isin⁡(nθ)\begin{align*} T_n(x)=\cos(n\arccos(x))=\cos(n\arccos(\cos(\theta)))=\cos(n\theta)=e^{in\theta}-i\sin(n\theta) \end{align*}
여기서 실수부만 고려하면 anTn(x)=aneinθa^nT_n(x)=a^ne^{in\theta}가 된다. 따라서 아래와 같이 전개가 가능하다.
∑n=0∞aneinθ=∑n=0∞(aeiθ)n=(1−aeiθ)−1={1−a(cos⁡(θ)+isin⁡(θ))}−1={1−a(x+i(1−x2)12}−1={1−ax−ia(1−x2)12}−1=1−ax+ia(1−x2)12(1−ax)2+a2(1−x2).\begin{align*} \sum^{\infty}_{n=0}a^ne^{in\theta}=\sum^{\infty}_{n=0}(ae^{i\theta})^n=(1-ae^{i\theta})^{-1}=\{1-a(\cos(\theta)+i\sin(\theta))\}^{-1} \\ =\{1-a(x+i(1-x^2)^{\frac{1}{2}}\}^{-1}=\{1-ax-ia(1-x^2)^{\frac{1}{2}}\}^{-1} \\ =\frac{1-ax+ia(1-x^2)^{\frac{1}{2}}}{(1-ax)^2+a^2(1-x^2)}. \end{align*}
이에 따라 급수의 합 ∑n=0∞anTn(x)\sum^{\infty}_{n=0}a^n T_n(x)의 실수부만 취하고 등비수열의 공식을 이용하여 아래와 같이 식을 전개할 수 있다.
∑n=0∞anTn(x)=1+aT1(x)+a2T2(x)+⋯=1−ax(1−ax)2+a2(1−x2)=1−ax1−2ax+a2=1−ax1−a(2x−a)=(1−ax){1+a(2x−a)+a2(2x−a)2+⋯ }                                                    =(1−12a⋅2x){1+a(2x−a)+a2(2x−a)2+⋯ }.\begin{align*} \sum^{\infty}_{n=0}a^n T_n(x)&=1+aT_1(x)+a^2T_2(x)+\cdots \\ &=\frac{1-ax}{(1-ax)^2+a^2(1-x^2)} =\frac{1-ax}{1-2ax+a^2} \\ &=\frac{1-ax}{1-a(2x-a)}=(1-ax)\{1+a(2x-a)+a^2(2x-a)^2+\cdots\} \\ &\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;=(1-\frac{1}{2}a\cdot2x)\{1+a(2x-a)+a^2(2x-a)^2+\cdots\}. \end{align*}
n≥1n\ge1에서 오른쪽 항을 ana^n를 기준으로 generating function을 만들면 아래와 같이 정리된다.
Tn(x)=12[(2x)n−{2(n−11)−(n−21)}(2x)n−2+{2(n−22)−(n−32)}(2x)n−4−⋯].T_n(x)=\frac{1}{2}\bigg[(2x)^n-\bigg\{2\bigg(\begin{matrix}n-1\\1\end{matrix}\bigg)-\bigg(\begin{matrix}n-2\\1\end{matrix}\bigg)\bigg\}(2x)^{n-2}\\ +\bigg\{2\bigg(\begin{matrix}n-2\\2\end{matrix}\bigg)-\bigg(\begin{matrix}n-3\\2\end{matrix}\bigg)\bigg\}(2x)^{n-4}-\cdots\bigg].
xnx^n에 대한 generating function을 찾기 위해 xnx^n를 아래와 같이 넣는다.
xn=(eiθ+e−iθ2)n.x^n=\Bigg(\frac{e^{i\theta}+e^{-i\theta}}{2}\Bigg)^n.
이를 적용하면 아래와 같이 정리할 수 있다.
xn=12n−1{Tn(x)+(n1)Tn−2(x)+(n2)Tn−4(x)+⋯}.x^n=\frac{1}{2^{n-1}}\bigg\{T_n(x)+\bigg(\begin{matrix}n\\1\end{matrix}\bigg)T_{n-2}(x)+\bigg(\begin{matrix}n\\2\end{matrix}\bigg)T_{n-4}(x)+\cdots\bigg\}.
nn이 짝수면 T0(x)T_0(x)의 계수는 반이 된다.
정의역의 구간을 0≤x≤10\le x \le 1으로 하면 위 식들을 xx를 2x−12x-1로 치환할 수 있다. 그러나 이렇게 하지 않고 아래 체비셰프 다항식의 성질을 이용한다.
Tm(Tn(x))=Tn(Tm(x))=cos⁡(nmθ)=Tnm(x).T_m(T_n(x))=T_n(T_m(x))=\cos(nm\theta)=T_{nm}(x).
m=2m=2라 하여 Tn(T2(x))T_n(T_2(x))를 계산한다.
T2(x)=2x2−12Tn2(x)−1=2Tn(x)⋅Tn(x)−1=2⋅12[Tn+n(x)+Tn−n]−1=T2n(x)+T0−1=T2n(x)\begin{align*} &T_2(x)=2x^2-1 \\ &2T_n^2(x)-1=2T_n(x)\cdot T_n(x)-1 \\ &=2\cdot\frac{1}{2}\bigg[T_{n+n}(x)+T_{n-n}\bigg]-1=T_{2n}(x)+T_0-1=T_{2n}(x) \end{align*}
위 두식을 이용하여 아래와 같이 Tn(T2(x))T_n(T_2(x))을 전개할 수 있다.
Tn(T2(x))=Tn(2x2−1)=T2(Tn(x))=2Tn2(x)−1=T2n(x).T_n(T_2(x))=T_n(2x^2-1)=T_2(T_n(x))=2T^2_n(x)-1=T_{2n}(x).
위 식을 x2x^2을 xx로 치환하면 Tn(2x−1)=Tn⋆(x)T_n(2x-1)=T_n^{\star}(x)가 되며 Tn(2x−1)=Tn(2(x12)2−1)=Tn(T2(x12))=T2(Tn(x12))T_n(2x-1)=T_n(2(x^{\frac{1}{2}})^2-1)=T_n(T_2(x^{\frac{1}{2}}))=T_2(T_n(x^{\frac{1}{2}}))가 된다. 이를 이용하면 아래와 같이 전개된다.
Tn(2x−1)=Tn⋆(x)=T2(Tn(x12))=T2n(x12).T_n(2x-1)=T^{\star}_n(x)=T_2(T_n(x^{\frac{1}{2}}))=T_{2n}(x^{\frac{1}{2}}).
따라서 Tn⋆(x)=T2n(x12)T_n^{\star}(x)=T_{2n}(x^{\frac{1}{2}})이므로 위의 Tn(x)T_n(x)에 대해 정리한 식에 n대신 2n으로 치환하고 xx를 x12x^{\frac{1}{2}}으로 치환하여 계산하면 아래와 같이 정리할 수 있다.
Tn⋆(x)=12[22nxn−{2(n−11)−(n−21)}2n−2xn−1+⋯]xn=122n−1{Tn⋆(x)+(2n1)Tn−1⋆(x)+⋯}T_n^{\star}(x)=\frac{1}{2}\bigg[2^{2n}x^n-\bigg\{2\bigg(\begin{matrix}n-1\\1\end{matrix}\bigg)-\bigg(\begin{matrix}n-2\\1\end{matrix}\bigg)\bigg\}2^{n-2}x^{n-1}+\cdots\bigg] \\ x^n=\frac{1}{2^{2n-1}}\bigg\{T_n^{\star}(x)+\bigg(\begin{matrix}2n\\1\end{matrix}\bigg)T_{n-1}^{\star}(x)+\cdots \bigg\}
이 또한 nn이 짝수는 T0⋆(x)T_0^{\star}(x)가 반이 된다.

6.3.4 Small coefficients and little error

구간 [−1,1][-1,1]에서 small norm을 가지는 다항식은 아주 큰 계수를 가질 수 있어 활용이 불편할 수 있다. 체비셰프 다항식은 작은 계수를 가지며 이를 이용하여 적은 오차로도 기존 다항식의 계수를 훨씬 작은 값으로 만들 수 있다. 이를 아래 예제와 함께 보인다.

Example 5.

아래와 같은 다항식에 대해 고려한다.
(1−x2)10=1−10x2+45x4−120x6+210x8−252x10+210x12−120x14+45x16−10x18+x20.\begin{align*} (1-x^2)^{10}&=1-10x^2+45x^4-120x^6+210x^8-252x^{10} \\ &+210x^{12}-120x^{14}+45x^{16}-10x^{18}+x^{20}. \end{align*}
위 다항식은 아주 큰 계수를 가지나 이를 체비셰프 형태로 바꾸면 아래와 같다.
(1−x2)10=1524288{92378T0−167960T2+125970T4−77520T6+38760T8−15504T10+4845T12−1140T14+190T16−20T18+T20}.\begin{align*} (1-x^2)^{10}&=\frac{1}{524288}\{92378T_0-167960T_2+125970T_4-77520T_6 \\ &+38760T_8-15504T_{10}+4845T_{12}-1140T_{14}+190T_{16}-20T_{18}+T_{20}\}. \end{align*}
위 식은 가장 큰 계수가 ≈0.32\approx 0.32가 되고 이는 기존 식의 가장 큰 계수 252252보다 훨씬 더 작은값이 된다. 또한 마지막 3개 항을 제거해도 최대 오차가 단지 0.00040.0004를 가진다.

6.3.5 Tayler expansion

economization 테크닉은 또한 테일러 급수에도 적용될 수 있다.

Example 6.

테일러 다항식은 −1≤x,  ∣ξ∣≤1-1\le x,\;|\xi|\le1일 때 ex=∑k=0nxkk!+xn+1(n+1)!eξe^x=\sum_{k=0}^n\frac{x^k}{k!}+\frac{x^{n+1}}{(n+1)!}e^{\xi}가 된다. 만약 n=6n=6이면 이 식의 오차는 e7!=0.0005\frac{e}{7!}=0.0005가 된다.
6차항까지 economization을 진행하면 아래와 같다.
∑k=06xkk!=1720(x6+6x5+30x4+120x3+360x2+720x+720)=1.26606T0+1.13021T1+0.27148T2+0.04427T3+0.00547T4+0.00052T5+0.00004T6.\sum^6_{k=0}\frac{x^k}{k!}=\frac{1}{720}(x^6+6x^5+30x^4+120x^3+360x^2+720x+720) \\ =1.26606T_0+1.13021T_1+0.27148T_2+\\ 0.04427T_3+0.00547T_4+0.00052T_5+0.00004T_6.
이 때 뒤 두개 항을 제거하면 추가 오차가 단지 0.000560.00056이 된다. 이를 기존 테일러 다항식의 오차 0.00050.0005에 더해도 총 오차는 0.0010.001이며 이는 4차 테일러 다항식으로 했을 때 오차 e5!≈0.023\frac{e}{5!}\approx 0.023보다 훨씬 더 적은 오차를 갖는다.

6.3.6. Algorithm to find the alternating set, the polynomial and the error

전에 살펴보았듯이 E=f−pE=f-p는 구간 [−1,1][-1,1]에서 최대값이 ±M\pm M인 alternating set을 최소 n+2n+2개 가진다.
이러한 성질을 이용하여 최적 근사 다항식 pp와 최대오차(maximum error)를 구할 수 있다. 재귀 프로세스를 따르며 아래 단계로 이루어져 있다.
[알고리즘]
1.
구간 [−1,1][-1,1]에서 임의의 n+2n+2개 점 x0,x1,⋯ ,xn+1x_0,x_1,\cdots,x_{n+1}을 선택한다. k번째 재귀 프로세스에서 찾은 다항식을 p(k)(x)p^{(k)}(x), 이 때 최대 오차를 En(k)E^{(k)}_n라 하자. 이 때 최대오차를 En(1)(x)E^{(1)}_n(x)로 갖는 p(1)(x)p^{(1)}(x)는 alternating set에서 ±M1\pm M_1의 값을 가진다.
2.
양 끝점이나 극점 중 ∣En(1)(x)∣=∣f(x)−p(1)(x)∣|E_n^{(1)}(x)|=|f(x)-p^{(1)}(x)|이 최대값을 갖는 xn+2x_{n+2}을 찾는다.
3.
만약 위 최대값이 M1M_1보다 클 경우 x0,⋯ ,xn+1x_0,\cdots,x_{n+1}중 하나를 xn+2x_{n+2}로 변경한다. 이 때 변경 후의 En(1)(x)E_n^{(1)}(x)이 부호가 연속적으로 바뀌도록 한다.
4.
조건을 만족할 때 까지 1~3번 과정을 반복한다.