아이켄 델타제곱법

1. 개요

아이켄 델타제곱법 Aitken's Δ² Process
입력	이미 계산된 수열의 연속한 세 항
출력	극한의 추정값 (새 수열)
정확한 경우	xn = L + C qn 꼴 (기하 오차)
가속되는 것	선형 수렴 (오차비 → λ ≠ 1)
안 되는 것	로그 수렴 (오차비 → 1)
제안	알렉산더 아이켄, 1926

수열이 기하급수적으로 극한에 다가가고 있다면, 세 점만 보고 “그래서 어디로 가는데?”를 바로 계산할 수 있다.

아이켄 델타제곱법(Aitken’s Δ² process)은 선형으로 수렴하는 수열의 연속한 세 항 $x_n, x_{n+1}, x_{n+2}$ 로부터 오차가 기하급수 $C q^n$ 꼴이라고 가정하고 극한을 외삽해, 원래 수열보다 빨리 수렴하는 새 수열을 만드는 수열 가속(sequence acceleration) 기법이다. 뉴질랜드 출신 수학자 알렉산더 아이켄이 1926년 베르누이의 다항식 근 계산법을 다루면서 발표했고, 17세기 말 일본의 세키 다카카즈가 원주율 계산에 같은 공식을 썼다는 기록도 있다¹.

스테펜센 방법 문서가 이걸 반복에 되먹이는 쪽(고정점 반복 → 2차 수렴)을 다뤘다. 이 문서는 되먹이지 않고 이미 만들어진 수열에 한 번 또는 여러 번 씌우는 쪽 — 급수 가속, 반복 적용, 섕크스 변환과 윈의 ε-알고리즘으로의 일반화, 그리고 왜 로그 수렴에는 안 듣는지 — 를 정리한다.

2. 공식과 유도

전진차분 $\Delta x_n = x_{n+1} - x_n$, $\Delta^2 x_n = x_{n+2} - 2x_{n+1} + x_n$ 으로 쓰면

$$A_n \;=\; x_n - \frac{(\Delta x_n)^2}{\Delta^2 x_n} \;=\; x_{n+2} - \frac{(x_{n+2}-x_{n+1})^2}{(x_{n+2}-x_{n+1}) - (x_{n+1}-x_n)}.$$

유도는 한 줄이다. $x_n = L + C q^n$ 이라고 놓으면 미지수가 $L, C, q$ 셋이고 식도 세 개($x_n, x_{n+1}, x_{n+2}$)다. 연립하면

$$\frac{x_{n+2}-L}{x_{n+1}-L} = \frac{x_{n+1}-L}{x_n-L} = q \quad\Longrightarrow\quad L = \frac{x_n x_{n+2} - x_{n+1}^2}{x_{n+2} - 2x_{n+1} + x_n}.$$

이게 위 식과 같다. 그래서 오차가 정확히 기하수열이면 $A_n$ 은 극한 그 자체다. 실제로 $x_n = 2 + 3\cdot 0.9^n$ 에 적용하면 배정밀도 반올림 수준($|A_n - 2| \sim 10^{-13}$)으로 2가 나온다.

마지막 식의 $L$ 꼴(분자 $x_n x_{n+2} - x_{n+1}^2$)은 대수적으로 같지만 절대 그대로 코딩하지 마라. 큰 수 둘의 차를 작은 수로 나누는 꼴이라 유효숫자가 통째로 날아간다. 최신 항 $x_{n+2}$ 에 작은 보정을 빼는 둘째 꼴이 반올림에 가장 덜 민감하다.

2.1. 언제 가속되나

오차 $e_n = x_n - L$ 이 $e_{n+1} = (\lambda + \delta_n)\, e_n$, $\delta_n \to 0$ 을 만족하고 $\lambda \ne 1$ 이면(교대 급수의 $\lambda = -1$ 도 포함)

$$\lim_{n\to\infty} \frac{A_n - L}{x_n - L} = 0$$

이 성립한다(헨리치의 정리). 즉 선형 수렴하는 수열이면 차수 자체는 몰라도 상대적으로 무조건 빨라진다. 고정점 반복 $x_{n+1} = g(x_n)$ 처럼 오차가 $e_{n+1} = g'(r) e_n + \tfrac12 g''(r) e_n^2 + \cdots$ 로 가는 경우엔 $A_n - L = O(e_n^2)$ 이 되어, 한 번 씌운 수열의 오차비가 대략 $\lambda^2$ 이 된다.

3. 검산

3.1. 고정점 반복 cos x

$x_{n+1} = \cos x_n$, $x_0 = 1$ 은 고정점 반복의 단골 예제다. 고정점 $r \approx 0.739085$ 에서 $|g'(r)| = \sin r \approx 0.674$ 라 오차가 매 스텝 0.674배씩 준다.

$n$	원래 $\lvert x_n - r\rvert$	아이켄 $\lvert A_{n-2} - r\rvert$
2	$1.18\times10^{-1}$	$1.11\times10^{-2}$
4	$5.44\times10^{-2}$	$2.18\times10^{-3}$
6	$2.49\times10^{-2}$	$4.49\times10^{-4}$
8	$1.13\times10^{-2}$	$9.29\times10^{-5}$

(같은 행은 같은 데이터 $x_0..x_n$ 만 쓴다.) 아이켄 열의 오차비가 두 스텝에 약 0.2, 즉 스텝당 약 $0.45 \approx 0.674^2$ 로 위의 예측과 맞는다. 다만 이건 여전히 선형 수렴이다 — 2차로 바꾸려면 외삽값을 다음 반복의 출발점으로 넣어야 하고, 그게 스테펜센 방법이다.

3.2. 라이프니츠 급수와 반복 적용

$\pi = 4(1 - \tfrac13 + \tfrac15 - \cdots)$ 의 부분합 $S_n$ 은 오차가 대략 $1/n$ 로 줄어 악명 높게 느리다. 오차비가 $-1$ 로 가는 교대 급수라 아이켄이 듣는다. 결과 수열에 다시 아이켄을 씌우는 반복 아이켄(iterated Aitken)도 된다.

부분합 9개($S_0, \dots, S_8$)만으로 얻는 $|\,\cdot - \pi|$:

적용 횟수	0 (그냥 $S_8$)	1	2	3	4
오차	$1.11\times10^{-1}$	$4.79\times10^{-4}$	$1.02\times10^{-5}$	$5.78\times10^{-7}$	$6.04\times10^{-8}$

부분합으로만 $6\times10^{-8}$ 에 가려면 항이 대략 $1.7\times10^{7}$ 개 필요하다. 같은 9개 숫자에서 일곱 자릿수를 더 뽑아낸 셈이다².

3.3. 실패 사례 — 바젤 급수

$\sum 1/k^2 = \pi^2/6$ 의 부분합은 오차가 $\approx 1/n$ 이고 오차비가 1로 간다(로그 수렴). 이때 아이켄은 앞자리 상수만 깎는다.

항 수 $n$	10	20	40
부분합 오차	$9.52\times10^{-2}$	$4.88\times10^{-2}$	$2.47\times10^{-2}$
아이켄 오차	$5.25\times10^{-2}$	$2.56\times10^{-2}$	$1.27\times10^{-2}$

오차가 절반이 될 뿐 여전히 $1/n$ 이다. 이건 아이켄만의 문제가 아니다 — 들라에-제르맹본(1980)이 로그 수렴 수열 전체를 가속하는 단일 변환은 존재하지 않는다는 것을 보였다. 로그 수렴에는 오차 모양을 미리 아는 방법(오일러-매클로린 보정, 리처드슨 외삽법처럼 $h^p$ 꼴을 알고 지우는 것, 레빈 변환 등)을 따로 써야 한다.

4. 섕크스 변환과 ε-알고리즘

아이켄의 가정 “오차 = 기하수열 하나”를 “기하수열 $k$ 개의 합”으로 넓힌 게 섕크스 변환(1955)이다.

$$x_n = L + \sum_{i=1}^{k} C_i\, q_i^{\,n}$$

을 $2k+1$ 개 항으로 맞춰 $L$ 을 푸는 것이고, 그 값 $e_k(x_n)$ 은 행렬식의 비로 쓴다. $k = 1$ 이 정확히 아이켄이다. 행렬식을 매번 계산하는 건 비싸고 불안정해서, 윈(1956)이 같은 값을 점화식으로 뽑는 ε-알고리즘을 냈다.

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

짝수 열 $\varepsilon_{2k}^{(n)} = e_k(x_n)$ 이 섕크스 값이고 홀수 열은 중간 계산용이다. $\varepsilon_2$ 를 풀어 쓰면 아이켄 식이 그대로 나온다. 거듭제곱 급수의 부분합에 섕크스 변환을 씌우면 파데 근사의 대각선 근처 원소가 나온다 — 그래서 아이켄·섕크스·파데·연분수는 한 집안이다.

5. 실무 — 어디서 쓰나

• 고정점 반복의 후처리. 반복을 멈춘 뒤 마지막 세 값에 한 번 씌워 자릿수를 더 얻는다. 되먹이고 싶으면 스테펜센 방법.
• 연성 해석의 동적 완화. 유체-구조 연성의 분리형 반복에서 쓰는 「아이켄 완화」는 이 공식의 벡터판으로 완화계수를 매 반복 다시 정한다. 벡터 문제를 본격적으로 가속하려면 최근 잔차 여러 개를 쓰는 앤더슨 가속이나 벡터 ε-알고리즘·MPE·RRE 쪽으로 간다.
• 급수·적분 근사. 교대 급수, 고유값 거듭제곱법의 고유값 추정 수열(오차비가 $\lambda_2/\lambda_1$ 의 거듭제곱으로 일정한 선형 수렴이다) 등 오차비가 일정한 곳이면 공짜로 자릿수를 얻는다.
• 수렴 차수 진단. 세 연속 오차의 비를 보는 것 자체가 수렴성의 실측 차수 추정과 같은 계산이다. 아이켄이 잘 들으면 선형 수렴, 효과가 미미하면 로그 수렴을 의심하면 된다.

6. 함정

• 분모 상쇄. 수렴이 진행될수록 $\Delta^2 x_n$ 은 작은 수 셋의 차가 되어 상대오차가 커진다. 반복 아이켄을 너무 깊게 쌓으면 어느 단계부터는 반올림 잡음을 외삽하게 된다. 위 라이프니츠 표도 단계를 더 쌓으면 결국 이득이 멈춘다.
• $\Delta^2 x_n = 0$. 수열이 이미 상수가 됐거나 우연히 등차일 때 0으로 나눈다. 0이거나 아주 작으면 그 항은 건너뛰는 보호 코드를 넣는다.
• 전이 구간. 반복 초기처럼 오차비가 아직 상수로 자리잡지 않았을 때 씌우면 엉뚱한 값이 나올 수 있다. 가속은 「점근 영역에 들어간 수열」의 도구다.
• 발산 수열도 무언가로 보낸다. $|\lambda| > 1$ 이어도 공식은 $L$ 을 내놓는다(그게 반발하는 고정점이다). 장점이자 함정이다³.

7. 관련 문서

• 스테펜센 방법 · 고정점 반복 · 앤더슨 가속 · 리처드슨 외삽법
• 섕크스 변환 · 윈 엡실론 알고리즘 · 파데 근사 · 롬베르그 적분
• 수렴성 · 거듭제곱법 · 유체-구조 연성 · 테일러 급수

8. Footnotes

1. 세키 다카카즈(관효)는 정다각형 둘레로 원주율을 구하면서 마지막 세 값으로 극한을 외삽했다. 아이켄보다 200년 넘게 앞선다. 서양 수학사가 동양의 선행 사례를 뒤늦게 발견하는 국룰이 여기서도 돈다. ↩

2. 새 함수 평가가 단 한 번도 없다. 이미 있는 숫자 9개를 다시 섞기만 했다. 수치해석에서 공짜 점심에 가장 가까운 물건이다. ↩

3. 발산하는 반복에 씌우니 수렴값이 나와서 “와 고쳤다” 하고 좋아했는데, 알고 보니 물리적으로 의미 없는 불안정 평형이었다는 사연은 생각보다 흔하다. 외삽은 외삽일 뿐이다. ↩