섕크스 변환

1. 개요

섕크스 변환 Shanks Transformation
입력	수열의 연속한 2k+1 항
가정	오차 = 기하수열 k 개의 합
k = 1	아이켄 델타제곱법
계산	윈의 ε-알고리즘 (행렬식 대신 점화식)
급수에 쓰면	파데 근사와 같은 값
제안	슈미트 1941, 섕크스 1955

아이켄이 「기하수열 하나」로 극한을 찍었다면, 섕크스는 「기하수열 여러 개」로 찍는다. 그 덕에 발산하는 급수에서도 값을 뽑아낸다.

섕크스 변환(Shanks transformation)은 수열 $S_n$ 의 오차가 $k$ 개 기하수열의 합 $S_n \approx S + \sum_{i=1}^{k} c_i q_i^{\,n}$ 이라고 가정하고, 연속한 $2k+1$ 개 항으로 미지수 $S, c_i, q_i$ 를 맞춰 극한 $S$ 를 추정하는 비선형 수열 가속 변환이다. 그 값을 $e_k(S_n)$ 으로 쓰고, $k = 1$ 이 정확히 아이켄 델타제곱법이다. 대니얼 섕크스가 1955년 논문에서 체계화했고¹, 같은 변환이 R. J. 슈미트(1941)의 연립방정식 반복 풀이 논문에 먼저 나온다.

아이켄 문서가 정의와 ε-알고리즘 점화식, 파데 근사와의 관계를 한 절로 요약해 두었다. 이 문서는 그 요약 밑에 있는 것 — 행렬식 공식과 정확히 맞는 수열의 특성(핵 정리), 파데 근사와의 정확한 대응, 발산 급수에 대한 실측, 그리고 반복 아이켄과의 비교에서 섕크스가 지는 경우와 배정밀도에서 표가 무너지는 지점 — 을 다룬다.

2. 정의 — 행켈 행렬식의 비

$\Delta S_n = S_{n+1} - S_n$ 으로 쓰면

$$e_k(S_n) = \frac{ \begin{vmatrix} S_n & S_{n+1} & \cdots & S_{n+k} \\ \Delta S_n & \Delta S_{n+1} & \cdots & \Delta S_{n+k} \\ \vdots & \vdots & & \vdots \\ \Delta S_{n+k-1} & \Delta S_{n+k} & \cdots & \Delta S_{n+2k-1} \end{vmatrix} }{ \begin{vmatrix} 1 & 1 & \cdots & 1 \\ \Delta S_n & \Delta S_{n+1} & \cdots & \Delta S_{n+k} \\ \vdots & \vdots & & \vdots \\ \Delta S_{n+k-1} & \Delta S_{n+k} & \cdots & \Delta S_{n+2k-1} \end{vmatrix} }$$

이다. 분모 아래쪽 블록은 차분 수열로 만든 행켈 행렬이다. $k = 1$ 을 풀어 쓰면 $\bigl(S_n S_{n+2} - S_{n+1}^2\bigr)/\bigl(S_{n+2} - 2S_{n+1} + S_n\bigr)$, 곧 아이켄 공식이다.

이 정의는 선형 차분방정식으로 읽으면 더 자연스럽다. 상수 $a_0, \dots, a_k$ 에 대해

$$\sum_{i=0}^{k} a_i\,(S_{n+i} - S) = 0$$

이 성립하는 $S$ 와 $a_i$ 를 $2k+1$ 개 항에서 찾는 것이다. $a_i$ 는 정규화($\sum a_i = 1$)하면 $k$ 개 미지수라 $\Delta S$ 로 만든 $k$ 개 식으로 정해지고, 그 뒤 $S$ 가 나온다. 행렬식 비는 이걸 크래머 공식으로 쓴 것뿐이다.

2.1. 윈의 ε-알고리즘

행렬식을 $k$ 마다 계산하면 $O(k^3)$ 이고 수치적으로도 나쁘다. 윈(1956)은 같은 값을 마름모 점화식

$$\varepsilon_{j+1}^{(n)} = \varepsilon_{j-1}^{(n+1)} + \frac{1}{\varepsilon_j^{(n+1)} - \varepsilon_j^{(n)}}, \qquad \varepsilon_{-1}^{(n)} = 0,\ \varepsilon_0^{(n)} = S_n$$

으로 뽑는 방법을 냈고, 짝수 열이 $\varepsilon_{2k}^{(n)} = e_k(S_n)$ 이다. 홀수 열은 차분 수열의 섕크스 값의 역수 $1/e_k(\Delta S_n)$ 이라 중간 계산용이다. 50자리 정밀도로 행렬식 정의와 ε 표를 비교하면 $k = 6$ 까지 차이가 $10^{-46}$ 이하 — 같은 것을 계산한다. 자세한 구현은 윈 엡실론 알고리즘으로 넘긴다.

3. 핵 정리 — 어떤 수열에서 정확한가

$e_k(S_n) = S$ 가 모든 $n$ 에서 성립하는 수열 전체를 그 변환의 핵(kernel)이라 한다. 위 차분방정식 표현에서 바로 답이 나온다 — $S_n - S$ 가 $k$ 차 상수계수 선형 점화식을 만족하고 그 특성다항식이 1을 근으로 갖지 않으면($\sum a_i \ne 0$) 정확하다. 점화식의 일반해는

$$S_n = S + \sum_i P_i(n)\, q_i^{\,n}, \qquad \sum_i \bigl(\deg P_i + 1\bigr) = k$$

꼴이다. 즉 기하수열 $k$ 개뿐 아니라, 중근이 있으면 $n q^n$ 같은 다항식 곱 항까지 핵에 들어간다.

실측: $S_n = 2 + 3(0.5)^n + (-0.8)^n + n(0.3)^n$ 은 근 $0.5$, $-0.8$, $0.3$(중근)으로 4차 점화식을 만족한다. 50자리로 $e_k(S_0)$ 를 재면

$k$	1	2	3	4	5
$\lvert e_k - 2\rvert$	1.48	0.214	$2.5\times10^{-3}$	$1.3\times10^{-49}$	$7\times10^{-50}$

로 $k = 4$ 에서 정확히 떨어진다. $k = 3$ 은 거의 맞히지만(근 하나를 못 잡은 오차) 정확하지는 않다.

이 정리가 선형 반복법과 연결되는 지점이 흥미롭다. $\mathbf{x}_{n+1} = G\mathbf{x}_n + \mathbf{c}$ 의 각 성분은 $G$ 의 고유값들의 거듭제곱 합이므로, 서로 다른 고유값이 $k$ 개면 $e_k$ 가 정확한 해를 준다. 벡터판 외삽(MPE, RRE)을 선형 반복에 쓰면 각각 아놀디형 방법·GCR/GMRES 와 수학적으로 동치라는 것이 시디(1988)의 결과다 — 외삽과 크리로프 부분공간법은 같은 동전의 양면이다.

4. 파데 근사와의 정확한 대응

거듭제곱 급수 $f(x) = \sum c_j x^j$ 의 부분합 $S_n = \sum_{j=0}^{n} c_j x^j$ 에 섕크스 변환을 씌우면

$$e_k(S_n) = [\,n+k\,/\,k\,]_f(x)$$

— 분자 차수 $n+k$, 분모 차수 $k$ 인 파데 근사의 값과 같다. $f = e^x$, $x = 1$ 로 확인하면 $e_1(S_0) = 3 = [1/1]$, $e_2(S_0) = 2.714285714\ldots = [2/2]$, $e_1(S_2) = 2.722222\ldots = [3/1]$, $e_2(S_2) = 2.718253968\ldots = [4/2]$ 로 15자리 전부 일치한다. ε 표의 짝수 열이 파데 표의 대각선을 따라 걷는 셈이고, 그래서 ε-알고리즘은 「파데 근사를 계수 대신 부분합에서 직접 계산하는 방법」이기도 하다.

이 대응이 섕크스 변환의 진짜 힘을 설명한다. 파데 근사는 급수의 수렴 반경 밖에서도, 심지어 수렴 반경이 0인 발산 급수에서도 의미 있는 값을 줄 수 있기 때문이다.

5. 실측

5.1. 교대 급수 ln 2 — 반복 아이켄에게 진다

$\ln 2 = 1 - \tfrac12 + \tfrac13 - \cdots$ 의 부분합 13개($S_1, \dots, S_{13}$)로 50자리 계산했다. 부분합 자체의 오차는 $3.7\times10^{-2}$ 다.

$k$	1	2	3	4	5	6
사용 항 수	3	5	7	9	11	13
$\lvert e_k - \ln 2\rvert$	$6.85\times10^{-3}$	$1.86\times10^{-4}$	$5.27\times10^{-6}$	$1.52\times10^{-7}$	$4.40\times10^{-9}$	$1.28\times10^{-10}$

$k$ 가 하나 늘 때마다 오차가 36.8, 35.3, 34.7, 34.5, 34.4 배씩 줄며 34 근처로 자리 잡는다. $\ln(1+x)$ 의 대각 파데 근사가 $x = 1$ 에서 수렴하는 속도 $\bigl(\tfrac{\sqrt2-1}{\sqrt2+1}\bigr)^{2} = (1+\sqrt2)^{-4} \approx 1/33.97$ 과 맞아떨어진다.

그런데 같은 13개 항에 아이켄을 6번 거듭 씌우면 오차가 $4.6\times10^{-13}$ 이다. 섕크스 $e_6$ 보다 약 300배 좋다. 라이프니츠 급수에서도 9개 항으로 반복 아이켄 4단은 $6.0\times10^{-8}$(아이켄 델타제곱법 문서의 표), 섕크스 $e_4$ 는 $6.6\times10^{-7}$ 이었다. 교대 급수처럼 오차 구조가 「기하수열 몇 개」보다 「$1/n$ 의 거듭제곱 전개 × $(-1)^n$」에 가까운 수열에서는, 매 단계 국소적으로 다시 맞추는 반복 아이켄이 더 유리할 수 있다. 섕크스가 아이켄의 상위 호환이라는 통념은 틀렸다 — 둘 다 같은 $2k+1$ 개 항을 쓰지만 가정하는 오차 모형이 다르다².

5.2. 발산 급수 — 오일러의 급수

$\sum_{k\ge0} (-1)^k k!$ 은 부분합이 $1, 0, 2, -4, 20, -100, \dots$ 으로 날뛰는, 어느 기준으로 봐도 발산하는 급수다. 오일러는 이 급수에 $\int_0^\infty \frac{e^{-t}}{1+t}\,dt = 0.5963473623\ldots$ (곰페르츠 상수)라는 값을 줬다³. 이 적분을 $1/(1+t)$ 의 급수로 전개해 항별로 적분하면 정확히 저 급수가 형식적으로 나온다. 부분합 21개에 섕크스를 씌우면:

$k$	1	2	4	6	8	10
$\lvert e_k(S_0) - 0.59634\ldots\rvert$	$7.0\times10^{-2}$	$1.9\times10^{-2}$	$2.5\times10^{-3}$	$4.7\times10^{-4}$	$1.1\times10^{-4}$	$3.2\times10^{-5}$

발산하는 수열에서 올바른 값으로 수렴한다. 이 급수는 스틸체스 급수라서 대각 파데 근사가 수렴한다는 이론적 보장이 있고, 섕크스는 그 파데를 부분합에서 직접 계산한 것이다. 수렴은 기하급수가 아니라 느리다 — 계수가 $k!$ 로 자라는 급수라 이 정도가 한계다. 섭동 이론에서 나오는 점근 급수를 처리할 때 이 성질이 쓰인다.

6. 배정밀도의 한계와 특이 규칙

라이프니츠 급수 $\pi = 4\sum (-1)^k/(2k+1)$ 의 부분합 40개를 배정밀도로 ε 표에 넣으면:

$k$	2	4	6	8	10	11	12
오차	$7.5\times10^{-4}$	$6.6\times10^{-7}$	$5.7\times10^{-10}$	$5.0\times10^{-13}$	$2.2\times10^{-15}$	$1.3\times10^{-15}$	NaN

$k = 10$ (21개 항)에서 기계 정밀도에 닿고, $k = 12$ 에서 표가 NaN 으로 무너진다. 이웃한 두 값이 비트 단위로 같아져 분모가 정확히 0이 되었기 때문이다. 0이 아니더라도 분모가 작은 수의 차이면 상대오차가 폭발한다 — 아이켄 델타제곱법의 분모 상쇄가 열마다 누적되는 것이다.

실무 구현은 셋 중 하나를 한다.

• 열 깊이 제한: 인접한 짝수 열 값의 차가 허용오차 밑으로 내려가면 거기서 멈추고 그 값을 답으로 낸다. 위 표에서 $k = 10$ 근처에서 멈추면 된다.
• 윈의 특이 규칙(Wynn, 1963): 분모가 0 근처일 때 마름모 하나 대신 더 넓은 「십자」 관계로 건너뛰어 계산을 이어 간다.
• 정밀도 올리기: 표 깊이가 정말 필요하면 4배·임의 정밀도로 계산한다. 같은 40개 항을 50자리로 계산하면 $k = 12$ 에서 $3.8\times10^{-19}$, $k = 19$ 에서 $7.2\times10^{-30}$ 까지 무리 없이 내려간다.

7. 쓰임

• 급수·격자합 가속: 교대 급수, 푸리에 급수의 부분합, 물리의 격자합처럼 오차비가 일정하거나 몇 개 성분으로 갈리는 수열.
• 발산·점근 급수 재합산: 섭동 전개, 고온·저온 전개처럼 계수가 계승으로 자라는 급수에서 파데/섕크스 재합산은 표준 도구다. 보렐 재합산과 함께 쓰인다.
• 반복법 후처리와 벡터 외삽: 스칼라 섕크스를 벡터로 일반화한 벡터·위상 ε-알고리즘, MPE, RRE 는 비선형 반복의 가속에 쓰이고, 실무에서 가장 많이 쓰이는 친척이 앤더슨 가속이다.
• 고유값 추정: 거듭제곱법의 레일리 몫 수열처럼 고유값 비율의 거듭제곱 몇 개로 오차가 이뤄진 수열은 핵 정리에 가깝게 맞는다.

8. 관련 문서

• 아이켄 델타제곱법 · 윈 엡실론 알고리즘 · 스테펜센 방법 · 리처드슨 외삽법 · 롬베르그 적분
• 파데 근사 · 행켈 행렬 · 점근 급수 · 테일러 급수
• 앤더슨 가속 · 크리로프 부분공간법 · GMRES · 거듭제곱법 · 수렴성

9. Footnotes

1. 섕크스는 $\pi$ 를 10만 자리까지 처음 계산한 사람(렌치와 함께, 1961년 계산)으로 더 유명하다. 수렴 가속 논문을 쓴 사람이 결국 가장 무식하게 많이 계산한 기록으로 이름을 남겼다는 건 아이러니라면 아이러니. ↩

2. 「$k$ 를 키우면 무조건 좋아진다」도 비슷한 착각이다. 위 표에서 보듯 깊이 들어갈수록 반올림이 먼저 이긴다. 가속기는 수열의 오차 구조에 대한 가설이고, 가설이 틀리면 가속기는 그냥 비싼 평균기다. ↩

3. 오일러가 이 급수에 값을 매긴 건 18세기다. 당시 수학자들 상당수는 「발산 급수의 합」이라는 말 자체를 신성모독으로 여겼는데, 2세기 뒤 섕크스·파데·보렐이 오일러 편을 들어 주었다. ↩