클렌쇼-커티스 구적

1. 개요

클렌쇼-커티스 구적 Clenshaw–Curtis Quadrature
노드	체비쇼프 극점 $x_k = \cos(k\pi/n)$, $k = 0, \dots, n$
원리	체비쇼프 보간 다항식을 항별 적분
정확도 차수	$n+1$ 점으로 $n$ 차 다항식 정확 ($n$ 짝수면 $n+1$ 차)
가중치	모두 양수 (임호프 1963), FFT 로 $O(n\log n)$
중첩성	$n \to 2n$ 이면 기존 노드를 전부 재사용
발표	클렌쇼·커티스 (1960), 선행: 페예르 (1933)
평판	「가우스의 절반 차수」인데 실전 정확도는 거의 같다 (트레페슨 2008)

다항식 차수로 따지면 가우스 구적의 절반짜리. 그런데 실제 함수를 넣어 보면 성적이 거의 같고, 노드는 공짜로 재활용된다.

클렌쇼-커티스 구적(Clenshaw–Curtis quadrature)은 $[-1, 1]$ 위의 적분 $\int_{-1}^{1} f(x)\,dx$ 를 체비쇼프 극점

$$x_k = \cos\frac{k\pi}{n},\qquad k = 0, 1, \dots, n$$

에서의 함수값으로 근사하는 구적법이다. $f$ 를 이 $n+1$ 개 점에서 체비쇼프 다항식 급수로 보간한 다음 그 다항식을 정확히 적분한다. 찰스 클렌쇼와 앨런 커티스가 1960년 「자동 컴퓨터를 위한 수치적분법」으로 발표했고, 내부 점만 쓰는 비슷한 규칙은 페예르(1933)가 먼저 냈다.¹

수치적분 문서는 이 규칙을 「가우스에 준하는 정확도」라고 한 줄로, 체비쇼프 다항식 문서는 「체비쇼프 계수 + FFT」라는 원리와 트레페슨의 결론을 한 단락으로 요약했다. 이 문서는 그보다 안쪽으로 들어가 가중치의 닫힌꼴과 FFT 계산, 차수 절반인데 왜 정확도가 같은지(그리고 언제 다른지)를 실측으로, 중첩성이 적응 구적과 희소 격자에 주는 이득을 다룬다.

2. 규칙의 구성

$x = \cos\theta$ 로 치환하면

$$\int_{-1}^{1} f(x)\,dx = \int_0^{\pi} f(\cos\theta)\sin\theta\,d\theta$$

가 된다. $f(\cos\theta)$ 는 $\theta$ 에 대해 짝수인 주기함수이므로 코사인 급수 $\tfrac{a_0}{2} + \sum_{j\ge1} a_j\cos(j\theta)$ 로 쓸 수 있고, 이 $a_j$ 가 곧 체비쇼프 계수다($T_j(\cos\theta) = \cos j\theta$). 항별로 적분하면 $\int_{-1}^1 T_j(x)\,dx$ 는 홀수 $j$ 에서 0, 짝수 $j$ 에서 $2/(1 - j^2)$ 이므로

$$\int_{-1}^{1} f(x)\,dx = a_0 + \sum_{j\ \text{짝수} \ge 2} \frac{2a_j}{1 - j^2}.$$

클렌쇼-커티스는 무한 급수의 $a_j$ 를 등간격 $\theta_k = k\pi/n$ 의 값으로 만든 이산 코사인 변환 계수로 바꾸고 $j \le n$ 에서 자른 것이다. 결과를 노드별 가중치로 정리하면($n$ 짝수)

$$w_k = \frac{c_k}{n}\left[1 - \sum_{j=1}^{n/2}\frac{b_j}{4j^2 - 1}\cos\frac{2jk\pi}{n}\right],\qquad c_k = \begin{cases}1 & k = 0, n\\ 2 & \text{그 외}\end{cases},\quad b_j = \begin{cases}1 & j = n/2\\ 2 & \text{그 외}\end{cases}$$

이다. 직접 구현해 $n = 16$ 으로 재면 가중치 합이 $2.0000000000000004$ ($\int_{-1}^1 1\,dx = 2$), 최소 가중치가 끝점의 $1/(n^2 - 1) = 0.00392$ 다. 끝점 가중치가 정확히 $1/(n^2-1)$ 이라는 것도 닫힌꼴에서 바로 나온다.

가중치는 전부 양수다(임호프 1963). 가중치 절댓값의 합이 2 로 고정되므로 함수값에 섞인 잡음이 증폭되지 않는다. 등간격 뉴턴-코츠 공식(수치적분)이 고차에서 음수 가중치를 만들어 불안정해지는 것과 대조된다 — 룽게 현상과 같은 뿌리의 문제를 체비쇼프 노드가 피한 것이다.

정확도 차수. $n+1$ 점 규칙은 $n$ 차 이하 다항식을 정확히 적분한다(보간이 정확하므로). 노드가 대칭이라 홀수 함수는 자동으로 0 이 맞으니 $n$ 이 짝수면 $n+1$ 차까지 정확하다. $n = 8$ (9 점)으로 재면 $x^7, x^8, x^9$ 은 $10^{-17}$ 수준으로 맞고, $x^{10}$ 에서 $7.2\times10^{-5}$ 오차가 처음 나타난다. 같은 9 점 가우스-르장드르 구적은 17 차까지 정확하다. 차수로만 보면 가우스가 두 배다.

3. FFT 로 가중치 뽑기

위 가중치 식을 그대로 계산하면 $O(n^2)$ 이지만, 괄호 안이 코사인 합이라 이산 코사인 변환, 곧 고속 푸리에 변환 한 번으로 모든 $w_k$ 가 나온다. 발트포겔(2006)이 페예르 1·2 규칙과 클렌쇼-커티스 가중치를 모두 길이 $n$ 의 역 FFT 하나로 만드는 짧은 알고리즘을 정리했다. 직접 구현해 $n = 16$ 에서 두 방법을 비교하면 가중치가 $10^{-16}$ 까지 일치한다.

비용 차이는 $n$ 이 크면 체감된다. 이 환경에서 2049 점 가중치를 만드는 데 FFT 판은 1.6 ms, NumPy 의 leggauss(고유값 문제를 푸는 골럽-웰시 계열)로 같은 점 수의 가우스 노드를 만드는 데 0.6 s 가 걸렸다. 다만 가우스 쪽도 헤일-타운센드식 $O(n)$ 알고리즘이 나와 있어서, 오늘날 「가우스 노드는 비싸다」는 예전만큼 결정적인 논거는 아니다. 클렌쇼-커티스의 진짜 구조적 이점은 비용보다 아래의 중첩성이다.

4. 차수는 절반인데 정확도는 같다 — 그리고 언제 다른가

같은 점 수에서 두 규칙의 절대오차를 재 보자. 점 수는 클렌쇼-커티스의 $n+1$ 과 가우스의 $n+1$ 을 맞췄다.

피적분함수	9 점 CC / 가우스	17 점	33 점	65 점
$e^x$ (전해석)	$2.0\times10^{-11}$ / $0$	$0$ / $4.4\times10^{-16}$	기계 정밀도	기계 정밀도
$1/(1+16x^2)$ (극점 $\pm i/4$)	$3.1\times10^{-2}$ / $1.4\times10^{-2}$	$5.8\times10^{-4}$ / $2.7\times10^{-4}$	$2.3\times10^{-7}$ / $9.9\times10^{-8}$	$9.5\times10^{-13}$ / $1.4\times10^{-14}$
$\lvert x\rvert^3$ (유한 매끄러움)	$4.4\times10^{-4}$ / $2.1\times10^{-4}$	$2.5\times10^{-5}$ / $1.8\times10^{-5}$	$1.6\times10^{-6}$ / $1.3\times10^{-6}$	$9.7\times10^{-8}$ / $8.8\times10^{-8}$
$e^{-1/x^2}$ ($C^\infty$, 비해석)	$5.5\times10^{-4}$ / $7.6\times10^{-4}$	$6.7\times10^{-6}$ / $1.6\times10^{-5}$	$3.6\times10^{-8}$ / $4.5\times10^{-8}$	$9.9\times10^{-13}$ / $3.4\times10^{-12}$

전해석 함수 $e^x$ 에서는 가우스가 확실히 앞선다(9 점에서 이미 기계 정밀도). 그러나 해석성이 유한한 함수에서는 두 규칙이 같은 속도로 수렴하고, 오차 비가 2 배 안팎에 머문다. $e^{-1/x^2}$ 에서는 오히려 클렌쇼-커티스가 이긴다. 트레페슨(2008)이 「가우스가 클렌쇼-커티스보다 나은가?」에서 보인 것이 정확히 이 그림이다.

왜 그런가. 피적분함수를 체비쇼프 급수 $\sum a_j T_j$ 로 보면, 구적 오차는 규칙이 정확히 적분하지 못하는 고차 항 $T_j$ ($j > n$) 들의 오차 합이다. 가우스는 $j \le 2n+1$ 까지 정확하고 그 너머에서 $O(1)$ 오차를 낸다. 클렌쇼-커티스는 $j > n$ 에서 정확하지 않다. 체비쇼프 노드 위에서 $T_j$ 는 $T_{2n-j}$ 로 에일리어싱되므로 규칙은 $T_j$ 의 적분 $2/(1-j^2)$ 대신 $2/(1-(2n-j)^2)$ 를 돌려준다. $j$ 가 $n$ 을 갓 넘는 항은 두 값이 모두 $O(1/n^2)$ 로 작아 오차도 그만큼 작고, $O(1)$ 오차는 $j$ 가 $2n$ 에 가까울 때만 생기는데 그 항의 계수 $a_j$ 는 이미 작다. 그래서 $a_j$ 가 천천히 줄어드는 함수(특이점이 구간에 가깝다)에서는 $j \in (n, 2n]$ 구간의 기여가 두 규칙에서 비슷하게 작고, 결국 양쪽 모두 「$2n$ 근처 계수의 크기」가 오차를 정한다.

꺾임(kink). $1/(1+16x^2)$ 의 체비쇼프 계수는 $\rho^{-j}$ ($\rho = \tfrac14 + \sqrt{1 + 1/16} \approx 1.281$, 극점을 지나는 베른슈타인 타원의 크기)로 줄어든다. 점 수를 촘촘히 바꿔 재면

점 수	17	25	33	41	49	57	65
CC	$5.8\times10^{-4}$	$1.1\times10^{-5}$	$2.3\times10^{-7}$	$5.4\times10^{-9}$	$1.9\times10^{-10}$	$1.1\times10^{-11}$	$9.5\times10^{-13}$
가우스	$2.7\times10^{-4}$	$5.2\times10^{-6}$	$9.9\times10^{-8}$	$1.9\times10^{-9}$	$3.6\times10^{-11}$	$6.9\times10^{-13}$	$1.4\times10^{-14}$
$\rho^{-2n}$	$3.6\times10^{-4}$	$6.9\times10^{-6}$	$1.3\times10^{-7}$	$2.5\times10^{-9}$	$4.8\times10^{-11}$	$9.2\times10^{-13}$	$1.8\times10^{-14}$

가우스는 끝까지 $\rho^{-2n}$ 을 따라간다. 클렌쇼-커티스도 41 점 근처까지는 같은 기울기를 타다가, 그다음부터 꺾여 한 점당 줄어드는 속도가 절반($\rho^{-n}$ 쪽)으로 떨어진다. 꺾이는 지점은 에일리어싱 오차 $O(a_n/n^2)$ 가 $a_{2n}$ 보다 커지는 곳이다. 즉 목표 정확도가 매우 높고 함수가 해석적일수록 가우스가 이득이고, 실무 허용오차($10^{-6}$~$10^{-10}$)와 매끄러움이 유한한 함수에서는 차이가 사실상 없다.²

5. 중첩성 — 클렌쇼-커티스의 진짜 무기

$n$ 을 $2n$ 으로 늘리면 새 노드 $\cos(k\pi/2n)$ 중 짝수 $k$ 는 옛 노드 $\cos(k'\pi/n)$ 와 정확히 같다. 이전에 계산한 함수값을 하나도 버리지 않는다. 가우스 노드는 $n$ 이 바뀌면 전부 새 위치라 처음부터 다시 계산해야 한다(이걸 피하려고 만든 것이 가우스-크론로드 쌍이다).

이 성질이 두 군데서 결정적이다.

• 적응·자동 구적. $n = 2, 4, 8, 16, \dots$ 로 늘려 가며 연속한 두 근사의 차이로 오차를 추정하고, 허용오차에 닿으면 멈춘다. 함수값 비용이 지배적인 문제(피적분함수가 PDE 해 하나)에서 버리는 평가가 없다. 체비쇼프 계수가 바닥에 닿는지를 보고 멈추는 Chebfun 의 sum 이 이 철학이다.
• 희소 격자. 스몰략 조합은 1차원 규칙 계열을 레벨별로 쌓는데, 레벨 간 노드가 중첩되어야 점 수가 폭발하지 않는다. 레벨 $i$ 에서 $2^{i-1}+1$ 점 클렌쇼-커티스가 완벽히 중첩되기 때문에 희소 격자 구적·불확실성 정량화의 확률 배치(stochastic collocation) 기본값이 됐다.

6. 실무 메모

• 구간 변환. $[a, b]$ 는 $x = \tfrac{a+b}{2} + \tfrac{b-a}{2}t$ 로 옮기고 가중치에 $(b-a)/2$ 를 곱한다. 끝점을 포함하므로 끝점에서 발산하는 함수($1/\sqrt{x}$ 류)에는 쓸 수 없다 — 그럴 땐 내부 노드만 쓰는 페예르 규칙이나 변수 치환을 쓴다.
• 끝점 특이성. $\sqrt{1 - x^2}$ 처럼 끝점에서 미분이 터지는 함수는 체비쇼프 계수가 대수적으로만 줄어 수렴이 느려진다. 가우스도 같은 처지라 이 경우의 해법은 규칙 선택이 아니라 치환이나 가중 구적(가우스-야코비)이다.
• 진동 함수. $\int f(x)e^{i\omega x}dx$ 처럼 $\omega$ 가 크면 「$f$ 만 체비쇼프 보간하고 진동 인자는 정확히 적분」하는 수정 클렌쇼-커티스(필론형)가 쓰인다. 점 수가 $\omega$ 와 무관해진다.
• 차원. 텐서곱으로 $d$ 차원을 만들면 점 수가 $(n+1)^d$ 로 폭발한다. 3~4 차원을 넘으면 희소 격자나 준몬테카를로로 가는 것이 국룰이다.³

7. 관련 문서

• 수치적분 · 체비쇼프 다항식 · 르장드르 다항식 · 직교다항식
• 이산 코사인 변환 · 고속 푸리에 변환 · 룽게 현상 · 보간과 근사
• 희소 격자 · 불확실성 정량화 · 롬베르그 적분 · 준몬테카를로
• 가우스-르장드르 구적 · 베른슈타인 타원 · 스펙트럴 방법

8. Footnotes

1. 이름은 클렌쇼-커티스지만, 노드와 아이디어의 뼈대는 1933년 페예르가 이미 냈다. 1960년의 공헌은 「자동 컴퓨터에서 쓰기 좋게」 계수 계산을 체비쇼프 급수 관점으로 정리한 것이다. 수학사에서 흔한 「이름 붙은 사람 ≠ 처음 한 사람」 사례. ↩

2. 「가우스가 두 배 차수니까 두 배 좋다」는 50년 묵은 통념을 트레페슨이 표 하나로 끝낸 사건. 다항식 차수는 다항식을 적분할 때나 의미가 있고, 세상의 피적분함수 대부분은 다항식이 아니다. ↩

3. 1차원에서 65 점이면 끝나는 일이 10차원 텐서곱에서는 $65^{10} \approx 1.3\times10^{18}$ 점이 된다. 차원의 저주는 구적법 선택으로 해결되지 않는다. 규칙을 바꾸는 게 아니라 격자를 버려야 한다. ↩