# 가속 기법(Aitken 가속 등) 수치 해석에서 비선형 방정식을 풀이할 때 고전적인 고정점 반복법이나 단순 불변 반복으로는 수렴 속도가 만족스럽지 못한 경우가 많다. 예컨대 $x\_{k+1}=g(x\_k)$ 형태의 고정점 반복이 구하고자 하는 근 $r$로 수렴한다고 해도, 이 수렴이 선형적이거나 매우 완만하다면 계산 효율이 떨어지게 된다. 가속 기법(acceleration method)이란 이러한 완만한 수렴 과정을 가속하여 적은 반복 횟수로 더 정확한 해에 도달하도록 하는 테크닉들을 가리킨다. Aitken 가속, Steffensen 방법, 일반화 Richardson 가속 등을 대표적으로 들 수 있다. 본 절에서는 이러한 가속 기법들 중 Aitken 가속을 중심으로 엄밀하게 살펴보고, 이어서 관련 확장 기법들을 다룬다. #### 단순 고정점 반복과 그 수렴 속도 고정점 반복 $x\_{k+1} = g(x\_k)$ 방식으로 비선형 방정식 $f(x)=0$의 근사해를 구하는 상황을 가정해 보자. $x^{(0)}$를 초기값으로 설정했을 때, 아래와 같이 반복하며 $$ x^{(k+1)} = g\bigl(x^{(k)}\bigr) $$ 이 때 $g$가 해 $r$ 부근에서 미분의 절댓값이 1보다 작다면(즉 $|g'(r)|<1$), 적절한 조건에서 $x^{(k)} \to r$로 수렴하게 된다. 그러나 $|g'(r)|$이 $1$에 가까울수록 수렴 속도는 매우 느리게 진행한다. 수렴 순서를 1차라 하는 선형 수렴(linear convergence)은 반복 횟수가 많아질수록 심각한 시간 낭비를 야기한다. #### 수열 가속의 원리 Aitken 가속은 수열 $x^{(0)}, x^{(1)}, x^{(2)},\dots$ 자체를 적당한 공식을 통해 변환하여 새로운 수열 $y^{(0)}, y^{(1)}, y^{(2)},\dots$를 얻고, 이 새로운 수열은 종종 더 빠른 수렴을 보이게 만든다. 간단하게 말하자면, 어떤 수열에서 연속된 항들의 선형적 변화를 추정한 뒤에, 그 변화를 제거하면서 수렴 성능을 높이는 원리로 이해할 수 있다. 다음과 같은 일반적 상황을 생각한다. 해 $r$로 수렴한다 가정한 반복 수열이 있다: $$ x^{(k)} \to r $$ 이때, $x^{(k)}$가 $r$에 매우 가깝다는 전제 하에, 연속된 세 점 $x^{(k)}, x^{(k+1)}, x^{(k+2)}$를 이용하여 $r$ 근방에서 일어나는 '잔차(residual)'의 변화를 추정한다. 이를 통해 새로운 점 $$ y^{(k)} = x^{(k)} - \frac{\bigl(x^{(k+1)} - x^{(k)}\bigr)^2}{x^{(k+2)} - 2,x^{(k+1)} + x^{(k)}} $$ 를 정의하면, $k$가 증가함에 따라 $y^{(k)}$의 수렴은 $x^{(k)}$의 원래 수렴보다 훨씬 빨라진다. 위 식에서 분모가 $x^{(k+2)} - 2,x^{(k+1)} + x^{(k)}$ 형태로 나타나는 이유는, 수열 항 사이의 2차 차분을 통해 수렴 과정을 선형 근사하고, 그 선형 근사 성분을 제거하는 과정이 반영되었기 때문이다. #### Aitken 가속의 유도 보다 엄밀한 관점에서 Aitken 가속 공식의 유도 과정을 짧게 살펴보자. $x^{(k)}$가 선형적으로 근사해를 따라간다고 가정하면, 다음과 같은 모형을 쓸 수 있다: $$ x^{(k)} = r + \alpha ,\lambda^k $$ 여기서 $r$은 실제 해이고, $\alpha$와 $\lambda$($|\lambda| < 1$)는 특정 상수이다. 즉 수렴률이 거의 선형적으로 $\lambda^k$의 형태를 갖는다고 볼 수 있다. 위의 세 점 $$ x^{(k)},\quad x^{(k+1)},\quad x^{(k+2)} $$ 에 대해 선형 추정 양상을 이용하면 $$ \begin{align} x^{(k+1)} - x^{(k)} \approx \alpha,\lambda^k(\lambda - 1), \\ x^{(k+2)} - x^{(k+1)} \approx \alpha,\lambda^k(\lambda^2 - \lambda). \end{align} $$ 위 등식을 통해 $\lambda^k$ 항을 부분 소거해가면 새롭게 정의되는 점 $y^{(k)}$는 $$ y^{(k)} \approx r + \text{(더 높은 차수의 미소항)}, $$ 와 같이 원래 수열보다 해 $r$에 훨씬 밀착된 근사값이 됨을 보일 수 있다. 이를 좀 더 일반화하면 추정 오차 항이 대폭 줄어들며, 수열의 유효적 수렴 차수가 상승하게 된다. #### Steffensen 방법과의 비교 Aitken 가속이 $x^{(k+1)} - x^{(k)}$ 등을 활용해 '고정된' 수열을 가속화한다면, Steffensen 방법(Secant-like 방식)은 직접적인 반복 과정에 적용하여 다음과 같은 형태를 얻는다: $$ x^{(k+1)} = x^{(k)} - \frac{\bigl(f\bigl(x^{(k)}\bigr)\bigr)^2}{f\bigl(x^{(k)} + f(x^{(k)})\bigr) - f\bigl(x^{(k)}\bigr)}. $$ 이는 기본적으로 Newton 방법에 가까운 구조지만, 미분을 사용하지 않고 $f$의 두 점에서의 함수값으로 근사를 진행한다. Aitken 가속은 고정점 반복 $x^{(k+1)} = g(x^{(k)})$에서 생성되는 수열을 직접 개선하며, Steffensen 방법은 함수 $f$를 정의한 다음 $g(x) = x - f(x)$ 식 또는 유사 구조로 활용함으로써 차이점이 있다. 하지만 둘 다 수렴 가속을 위해 유사한 아이디어(연속된 두 혹은 세 점에서의 차분을 이용하여 선형 성분을 제거)를 쓴다는 공통점이 있다. #### 다차원 문제로의 확장 고려 Aitken 가속 등은 일변수 문제뿐 아니라 다차원 문제로도 확장 가능하다. 다만 다차원 문제의 경우 벡터 형태의 고정점 반복 $$ \mathbf{x}^{(k+1)} = \mathbf{g}\bigl(\mathbf{x}^{(k)}\bigr) $$ 이 이루어지므로, 2차 차분과 같은 개념을 다차원 편미분이나 차분 연산에 맞게 정리해야 한다. 일부 고급 가속 기법은 Jacobian을 명시적으로 사용하지 않고도 (quasi-Newton 유도 방식 등) 적절히 변환하여 고차 수렴을 유도한다. Aitken 가속의 이런 확장은 이론적으로 가능하지만, 실제로는 베이스가 되는 반복법 자체가 Newton 방법 등 고차 수렴을 이미 갖추고 있을 경우 크게 도움이 안 될 수도 있다. 그러나 미분 연산 비용이 크고, 혹은 $g$가 단순 반복 구조를 띠지만 수렴이 느린 경우에 가속 방법이 매우 유효하다. #### 일반화 Richardson 가속 Aitken 가속은 반복 수열에서 발생하는 ‘선형적’(또는 준선형적) 수렴을 $\Delta^2$ 차분으로 추정하여 제거한다. 이에 비해 Richardson 가속(Richardson extrapolation)은 초기적으로 적분 근사나 수열의 오차항 제거 기법에서 출발하였고, 이를 보다 일반화하면 반복 수열의 수렴 가속에도 다양하게 응용할 수 있다. 일반화 Richardson 가속(Generalized Richardson acceleration)은 Aitken 가속을 포함해, 여러 형태의 고정점 반복 혹은 적분 순차 근사 수열 등에서 오차항을 체계적으로 억제하기 위한 기법들을 포괄하는 개념이다. **기본 원리** Richardson 가속은 흔히 적분값이나 미분방정식 해석에서, 격자 크기나 단계 크기를 줄여가며 얻은 근사값을 외삽(extrapolation)하여 높은 정확도를 얻는 방법으로 잘 알려져 있다. 이를 수열 가속 관점에서 해석하면, “수열의 항 $x^{(k)}$가 특정 형태의 오차 항(예: $h^p$ 꼴)과 함께 참값 $r$에 접근한다”는 가정 아래, 서로 다른 $h$(또는 $h$의 배수)로 계산된 근사치를 외삽하여 오차 항이 사라지도록 만드는 식이다. 보다 일반적으로는, 반복 수열 $$ x^{(k)} = r + \alpha\_k ,\varphi\_k $$ 형태를 생각해 볼 수 있다. 여기서 $\alpha\_k$와 $\varphi\_k$는 $k$에 따라 변화하는 어떤 오차 상수와 함수(또는 벡터)라 할 수 있는데, 수렴 과정에서 $\alpha\_k,\varphi\_k$가 0으로 가면서 $x^{(k)}$가 $r$에 가까워진다. 만약 $\alpha\_k$와 $\varphi\_k$에 대해 충분히 구체적인 거동(예: $\varphi\_k$가 기하급수적으로 작아진다거나, $k$와 함께 일정한 방식으로 변한다는 등)을 알 수 있다면, Richardson 가속 구조를 통해 오차 항을 소거하거나 크게 줄이는 공식을 유도할 수 있다. Richardson 방식에서 자주 볼 수 있는 전형적 예시를 간단히 보여주면, $x^{(k)}$를 $k$에 따른 근사치라 하고, 이 수열이 $$ x^{(k)} - r = C , \Delta^p + O(\Delta^{p+1}) $$ 꼴의 오차를 가진다고 가정한다. 여기서 $\Delta$는 $k$와 연동된 어떤 매개변수(적분에서의 분할 폭 등)다. $\Delta$의 값을 절반으로 줄인 근사치 등을 동시에 이용하면, $$ x^{(k)} \quad\text{와}\quad x^{(k')}, $$ 에서 $k'$이 $k$보다 더 세밀한(또는 더 많이 반복한) 상태를 반영한다. 그리하여 외삽 공식을 세우면, 대략 $$ \hat{r} = \frac{2^p, x^{(k')} - x^{(k)}}{2^p - 1} $$ 형태의 추정값 $\hat{r}$을 얻는다. 이는 오차항 $C , \Delta^p$가 상쇄되도록 설계된 것이다. 이 아이디어를 반복 수열의 각 단계에 맞추어 더 정교하게 적용하는 것이 일반화 Richardson 가속이며, 그 과정에서 Aitken 가속(= $p=1$인 특수 경우)도 자연스럽게 포함된다고 볼 수 있다. **수열 변환과 외삽 매트릭스** 수열 가속의 관점에서 Richardson, Euler, Shanks 등 다양한 변환 방식은, “수열의 일정 구간(연속된 항들을 포함)에서 주어진 데이터를 토대로 특정 외삽을 수행한다”는 공통된 구조를 가진다. 이를 매트릭스 연산 관점에서 정리한 문헌도 많은데, 각 단계에서 $$ \mathbf{E} , \mathbf{x} = \mathbf{y} $$ 꼴의 ‘가속 변환’을 수행하는 것으로 해석한다. 여기서 $\mathbf{x}$는 원본 반복 수열(또는 여러 계층의 근사치)로 구성된 벡터, $\mathbf{y}$는 외삽한 결과(가속된 새로운 수열 항), $\mathbf{E}$는 외삽에 필요한 계수를 담은 매트릭스 또는 텐서적 구조다. Aitken 가속에서의 $\Delta^2 x^{(k)}$ 계산도 일종의 2차 차분 행연산으로 볼 수 있고, Richardson 외삽 계수 또한 위 공식에서 보듯이 $2^p$ 등의 계수를 활용한다. 다차원으로 확장할 때도 유사한 구조를 취하지만, 차분이나 외삽에서 고려해야 할 항이 단순 scalar가 아닌 벡터(혹은 행렬)나 복잡한 구조일 수 있다. 따라서 소위 Multidimensional extrapolation 기법이 별도로 연구되는 경우가 많다. **비선형 문제에서의 적용** 비선형 문제나 비선형 편미분방정식 등을 수치적으로 풀 때, 흔히 사전에 설정된 $g$ 형태나 반복 방정식으로부터 $\mathbf{x}^{(k+1)} = \mathbf{g}(\mathbf{x}^{(k)})$를 계속 수행한다. 이때 각 반복 결과 $\mathbf{x}^{(k)}$가 비교적 천천히 수렴한다면, Richardson 계열 기법으로 부분 수열을 골라 가속하는 시도를 할 수 있다. 예를 들어, 어떤 시점까지 얻은 $$ \mathbf{x}^{(k)},\quad \mathbf{x}^{(k+1)},\quad \dots,\quad \mathbf{x}^{(k+m)} $$ 을 이용해, 이 벡터들이 해 $\mathbf{r}$로 가는 경로에서 일정한 형태의 오차 감퇴 모델을 가정하면, 외삽 계수를 구해 $\mathbf{r}$에 가까운 새로운 근사점을 얻는다. 특히 수치유체해석(CFD)처럼 복잡한 시스템에서, 높은 해상도 격자(혹은 해석 단계)로 갈수록 계산 비용이 급증하는 상황에서 Richardson extrapolation 기법을 활용해 비교적 적은 비용으로 오차를 줄이려는 전략이 종종 사용된다(물론 그 정밀도와 신뢰도는 문제 설정에 따라 달라진다). **고차 주문(차수) 외삽** Aitken 가속과 Steffensen 방법이 1차(즉, 선형 차분) 중심이라면, 일반화 Richardson 기법은 더 높은 차수 $p$를 상정하고 외삽 계수를 설계할 수 있다. 예를 들면, $$ x^{(k)} - r \approx a\_1 \lambda^k + a\_2 \lambda^{2k} + \cdots $$ 와 같이 여러 항의 지수감쇠를 갖는 오차를 추정하는 모델을 세우고, 이를 동시에 소거하기 위한 계수를 도출할 수도 있다. 이 경우 연속된 $k, k+1, k+2, \dots$에서 얻은 항들을 조합하는 과정은 더 복잡해지지만, 그만큼 오차 항이 빠르게 줄어드는 효과를 기대한다. 다만 모델링 단계에서 오차 구조를 잘못 가정하면, 가속이 제대로 이뤄지지 않을 뿐 아니라 수치 난조가 발생할 가능성도 커진다. 따라서 일반화된 Richardson 가속을 적용할 때는, 문제가 어떤 형태의 잔차(residual)를 보이는지, 수렴 양상이 기하급수적(또는 다항식)인지를 미리 확인하는 것이 필수적이다. **실제 계산과정에서의 주의점** Richardson 가속이든 Aitken 가속이든, 고차 외삽을 시도할수록 수치 오차 증폭에 더욱 민감해진다. 즉, 분모가 작은 경우와 마찬가지로, 계수 매트릭스 $\mathbf{E}$에서 발생하는 불안정 문제가 커질 가능성이 높아진다. 또한 실제론 고정점 반복 단계가 진행됨에 따라, 오차 모델(예: $\alpha \lambda^k$) 자체가 약간씩 변형되는 경우도 있다. 이때는 여러 구간으로 나누어 가속하거나, 변동하는 파라미터를 동적으로 업데이트해 주는 기법(Adaptive scheme)을 고민해야 한다. #### Anderson 가속(혼합) 기법 비선형 방정식의 고정점 반복을 가속하는 방식 중에서, Anderson 가속(Anderson acceleration, 또는 Pulay mixing)은 실무적 규모의 문제에서 매우 효과적인 방법으로 알려져 있다. Anderson 가속은 원래 전산화학(Chemistry), 전산물리(Physics) 분야에서 적분-미분 방정식을 동시에 풀 때 혼합 기법(mixing method)으로 널리 쓰였으며, 최근에는 다양한 고차원 비선형 문제에서도 점차 채택되는 추세다. Aitken 가속이나 Steffensen 방법이 1차 혹은 2차 차분 정보를 활용해 스칼라 영역(또는 소규모 벡터)에서 수렴을 빠르게 만드는 개념이라면, Anderson 가속은 더 큰 차원의 $\mathbf{x}$에 대해서도 비교적 안정적이고 효율적인 가속 효과를 보이는 것이 특징이다. **기본 아이디어** 기본 고정점 반복식 $$ \mathbf{x}^{(k+1)} = \mathbf{g}\bigl(\mathbf{x}^{(k)}\bigr) $$ 을 수행한다고 할 때, Anderson 가속은 최근 몇 번의 반복에서 얻은 잔차 벡터들을 모아, $\mathbf{g}\bigl(\mathbf{x}^{(k)}\bigr) - \mathbf{x}^{(k)}$의 선형 결합을 통해 ‘최적의’ 오차 소멸 방향(혹은 투영)을 찾아낸 다음, 그 방향으로 보정한 값을 새 반복의 후보로 사용하는 방식이다. 즉, 최근 $m$번의 반복에서 발생한 잔차 $$ \mathbf{r}^{(i)} = \mathbf{g}\bigl(\mathbf{x}^{(i)}\bigr) - \mathbf{x}^{(i)} $$ 들을 열벡터로 쌓아서 특정 최소제곱(minimum-norm) 조건을 만족하는 계수를 구하고, 이를 이용해 고정점 갱신 시 더 유리한 방향으로 이동시키는 구조다. 일반적인 Anderson 가속의 알고리즘 요약은 아래처럼 쓸 수 있다(단, 구체적 구현에 따라 변형이 다양하다). **Anderson 가속 알고리즘 개념 요약** 초기값 $\mathbf{x}^{(0)}$를 정하고, $k$단계에서 먼저 $$ \mathbf{x}^{(k+1)}\_{\text{temp}} = \mathbf{g}\bigl(\mathbf{x}^{(k)}\bigr) $$ 를 계산한다. 그 다음, 최근 $m$개 단계의 잔차 및 바뀐 $\mathbf{x}$에 대해 $$ \Delta \mathbf{X}^{(i)} = \mathbf{x}^{(i+1)} - \mathbf{x}^{(i)},\quad \Delta \mathbf{R}^{(i)} = \mathbf{r}^{(i+1)} - \mathbf{r}^{(i)}, $$ 를 모은 뒤, 어떤 최소제곱 문제 $$ \min\_{\boldsymbol{\alpha}} \Bigl|\sum\_{i} \alpha\_i,\Delta \mathbf{R}^{(i)}\Bigr| $$ 를 풀고, 여기서 얻은 $\boldsymbol{\alpha}$를 이용해 $$ \mathbf{x}^{(k+1)} = \mathbf{x}^{(k+1)}\_{\text{temp}} - \sum\_i \alpha\_i ,\Delta \mathbf{X}^{(i)} $$ 와 같은 형태로 최종 보정값을 구성한다. 위 식을 조금 변형하면, 기본적으로 $$ \mathbf{x}^{(k)} + \mathbf{r}^{(k)} \quad\text{(고정점 반복 결과)} $$ 를 여러 단계에 걸쳐 얻어낸 ‘차분’ 결합으로 개선한다고 볼 수 있다. Anderson 가속은 잔차를 기반으로 직접 개선 방향을 구하기 때문에, 미분( Jacobian ) 정보를 요구하지 않는 장점이 있다. **Anderson 가속과 Aitken 가속의 관계** Aitken 가속이 스칼라 고정점 반복을 2차 차분($\Delta^2$)을 이용해 바로 빨리 수렴시키는 것처럼, Anderson 가속은 고차원 문제에서 연속된 몇 단계의 정보(차분의 열벡터들)를 모아 유사한 효과를 노린다. 스칼라 문제에서 $m=2$ 정도로 설정하면 Anderson 가속이 Aitken 가속과 거의 동일하게 작동하는 경우가 있다. 즉, Anderson 가속은 고차원 문제에 대한 Aitken 가속의 자연스러운 확장판이라고도 볼 수 있다. **수치적 고려사항** Anderson 가속을 적용할 때도, 모인 벡터들 $\Delta \mathbf{R}^{(i)}$가 서로 거의 종속(dependent)에 가까워지면 계산이 불안정해질 수 있다. 특히 고차원 문제에서 $m$(메모리로 저장할 과거 단계 수)을 크게 잡으면, 잔차 벡터들이 선형 종속에 가까워지며 역행렬(또는 pseudo-inverse) 연산에서 수치적 난조가 발생할 가능성이 커진다. 실무 구현에서는 $m$을 너무 크게 잡지 않고, 잔차 벡터들의 정규화(norm check)나 직교화(Gram-Schmidt 등)를 수행해가며 Anderson 혼합을 적용하기도 한다. 반복 중에 수렴이 어느 정도 이뤄지면 $m$을 축소하거나, 주기적으로 잔차 벡터를 리셋하는 방식을 두어 수치안정성을 유지하기도 한다. **Python 예시** 다음은 (아주 간단한 형태로) Anderson 가속을 적용하는 예시다. 여기서도 스칼라 문제를 예로 들지만, 실무에서는 $\mathbf{x}$와 $\mathbf{g}(\mathbf{x})$가 벡터나 행렬 형태를 가질 수 있다. ```python import math import numpy as np def g(x): return math.cos(x) def anderson_acceleration(x0, m=2, tol=1e-10, max_iter=100): # m: 과거 단계 몇 개를 모아 회귀(혼합)할지 결정 x_list = [x0] r_list = [g(x0) - x0] x_current = x0 for k in range(max_iter): x_new = g(x_current) r_new = x_new - x_current # 과거 데이터 보관 x_list.append(x_new) r_list.append(r_new) # m보다 길어지면 오래된 자료 삭제 if len(x_list) > m+1: x_list.pop(0) r_list.pop(0) # Anderson 보정 # ΔX_i, ΔR_i 계산 dx = [] dr = [] for i in range(len(x_list)-1): dx.append( x_list[i+1] - x_list[i] ) dr.append( r_list[i+1] - r_list[i] ) dx = np.array(dx).reshape(-1,1) # 열벡터들 dr = np.array(dr).reshape(-1,1) # 최소제곱문제: min_alpha || sum alpha_i * dr_i || # 단, sum(alpha_i) = 1 등의 조건이 포함되기도 함(변형 가능) # 간단히 pseudo-inverse로 구해보자 # 만약 dr가 2D 이상이라면 dr.T @ dr이 invertible해야 함 alpha = 0 if dr.shape[0] > 0: A = dr # (n,1) 형태일 수도, 일반적이면 (n,m) ATA = A.T @ A if abs(ATA) > 1e-15: alpha = - (np.linalg.inv(ATA) @ A.T @ r_new)[0] x_anderson = x_new + alpha * ( - dx[-1] ) if abs(x_anderson - x_current) < tol: return x_anderson x_current = x_anderson return x_current root_estimated = anderson_acceleration(1.0, m=2) print("Anderson acceleration estimate =", root_estimated) ``` 이 예시에서는 스칼라 문제여서 $m=2$ 정도로 설정했고, 단 하나의 차원만 다루므로 실제로는 Aitken 가속에 가까운 형식으로 계산된다. 벡터 문제인 경우, $dx$와 $dr$가 행렬이나 고차원 벡터 열들의 집합이 되어, 이들을 최소제곱 관점에서 처리해 $\boldsymbol{\alpha}$를 구한다. 이 때 $\boldsymbol{\alpha}$는 다중 변수로 구성될 수 있으며, 잔차를 최소화하는 범위 내에서 Anderson 갱신을 적용한다. **실무 적용 사례** 크기가 큰 비선형 시스템(예: 유한요소해석, 전산유체역학, 양자화학 시뮬레이션 등)에서, Newton-Krylov류 방식으로는 Jacobian 또는 그 근사를 구하는 데 비용이 많이 들 수 있다. 이때 단순 고정점 반복(예: Picard iteration)을 수행하면서, Anderson 가속으로 수렴 속도를 높이는 전략이 자주 쓰인다. 특히 전산화학에서 “Pulay mixing”이라는 이름으로 전자밀도 반복 업데이트에 활용되고 있으며, DFT(Density Functional Theory) 계산에서도 수렴 효율을 대폭 개선하는 기법으로 자리 잡았다. Aitken 가속과 Steffensen 방법, Richardson 외삽, 그리고 Anderson 가속 등은 모두 “잇달아 반복되며 발생하는 잔차 또는 수열 항들”에서 규칙성을 뽑아내, 불필요한(또는 선형적인) 느린 변화 성분을 제거함으로써 빠른 근사 접근을 시도한다는 공통 구조를 가진다. 다만 Anderson 가속은 여러 과거 단계의 정보를 한꺼번에 활용해, 다차원 문제에서 효과가 더 확실히 나타난다는 점이 큰 장점이다. #### Wynn의 ε 알고리즘 Aitken 가속을 비롯한 여러 수열 가속 기법은 일반적으로 “연속된 몇 개 항의 차분 관계를 이용해, 지수 형태의 느린 수렴 오차를 제거”한다는 골격을 지닌다. Wynn의 ε 알고리즘(Wynn’s epsilon algorithm)은 이러한 기본 구상을 보다 정교하게 확장한 것으로, Shanks 변환을 효과적으로 계산하기 위한 절차로도 해석된다. Shanks 변환 자체가 “$\Delta^2$ 차분을 반복적으로 적용하여 지수 꼴 수렴 오차를 소거”하려는 아이디어라면, Wynn은 이를 효율적으로 구현하기 위한 재귀적 행렬 연산 알고리즘을 제안했다. 그 결과, 연속된 $x^{(k)}$ 항들을 재구성함으로써 강력한 가속 효과(높은 차수의 오차 항 제거)를 얻게 된다. **Shanks 변환과 ε 알고리즘의 관계** Shanks 변환은 $x^{(k)}$라는 원본 수열이 있을 때, 다음과 같은 “유리형 근사(rational approximation)”를 통해 오차 항을 소거하려는 방식이다. Aitken 가속 공식 $$ y^{(k)} = x^{(k)} - \frac{(x^{(k+1)}-x^{(k)})^2}{x^{(k+2)} - 2,x^{(k+1)} + x^{(k)}} $$ 는 사실 Shanks 변환에서 한 번의 변환만 취한 경우와 동일하다. 이를 좀 더 높은 단계로 반복 적용하면, $$ \epsilon\_{n}^{(k)} $$ 라는 2차원 테이블(혹은 삼각 형태)을 구성하게 되는데, Wynn의 ε 알고리즘은 이 테이블을 효율적으로 채워 넣는 재귀식을 제시한다. Wynn의 ε 알고리즘에서 $\epsilon\_0^{(k)}$는 원래 주어진 수열의 항 $x^{(k)}$를 그대로 받으며, $\epsilon\_{j+1}^{(k)}$를 생성하기 위해 $$ \epsilon\_{j+1}^{(k)} = \epsilon\_{j-1}^{(k+1)} + \frac{1}{\epsilon\_{j}^{(k+1)} - \epsilon\_{j}^{(k)}} $$ 와 같은 형태(적절한 부호와 함께)의 재귀 공식을 이용한다. 여기서 $j$는 변환의 층을 나타내고, $k$는 수열 항의 인덱스 역할을 한다. 이 과정을 통해 적절히 선택된 $\epsilon\_{2n}^{(0)}$나 $\epsilon\_{2n}^{(1)}$ 등이 가속화된 근사값에 해당한다. Aitken 가속은 사실상 $\epsilon$ 알고리즘의 $(j=2)$까지만 사용하는 꼴이라고도 볼 수 있다. **반복 수열에서의 활용** Wynn의 $\epsilon$ 알고리즘을 반복 수열에 적용할 경우, 일반적으로 $x^{(0)}, x^{(1)}, x^{(2)}, \dots$를 얻어나가면서, 각 항을 $\epsilon\_0^{(k)}$에 순차로 넣고, 재귀적으로 $\epsilon\_j^{(k)}$들을 갱신해나간다. 그리고 $k$가 커져갈수록, 어느 특정 단계(또는 특정 행과 열)에 위치하는 $\epsilon\_j^{(k)}$가 진짜 해에 매우 근접하는 추정값 역할을 한다. 실제로는 Aitken과 달리 $\epsilon$ 알고리즘은 여러 열(column)을 동시에 구해야 하므로 계산량이 더 들 수 있다. 그러나 특정 구조의 문제에서 수렴이 매우 느리거나, 오차가 뚜렷한 지수 꼴(또는 유사 지수 꼴)을 보일 때 훨씬 강력한 가속 효과를 발휘하기도 한다. **수치 안정성과 적용 시 주의사항** Aitken 가속과 마찬가지로, Wynn의 ε 알고리즘도 분모 $$ \epsilon\_{j}^{(k+1)} - \epsilon\_{j}^{(k)} $$ 가 0에 가까워지면 난처해진다. 특히 높은 차수 변환($j$가 큰 경우)에서는 수치 오차가 예민해지고, 분모가 실제로 극도로 작아질 가능성도 높아진다. 또한 $\epsilon$ 알고리즘은 가능한 한 “인접 항 사이의 오차 감쇠 패턴이 일관성”을 갖는 상황에서 가장 효과적이다. 만약 수열 항이 비주기적으로 크게 요동하거나(예: 비선형 방정식에서 잘못된 초기값으로 발산 직전), 오차 모델이 급격히 변하는 경우에는 $\epsilon$ 알고리즘이 불필요하게 과적합(overfitting) 비슷한 양상을 보여 되려 오차가 커질 수도 있다. 이런 이유로, 실제 반복 계산에서는 일정 단계마다 검사하여 $\epsilon$ 알고리즘을 재시작(혹은 중간 단계까지만 사용)하는 방안을 고려하기도 한다. **예시 구현(스칼라)** 아래 코드는 가장 기본적인 형태로 Wynn의 ε 알고리즘을 스칼라 수열에 적용하는 예시다. 실제로는 오차 방지와 예외 처리를 강화해야 한다. ```python import math def wynn_epsilon_algorithm(sequence, max_columns=20): # sequence: x^{(0)}, x^{(1)}, ... # max_columns: j방향으로 몇 개까지 전개할지 # 반환값: 가속 후의 근사값(또는 테이블) n = len(sequence) # 2D 리스트(파이썬 기준)로, epsilon[j][k] 형태 epsilon = [[0.0]*(n) for _ in range(max_columns+1)] # 초기화: epsilon[0][k] = sequence[k] for k in range(n): epsilon[0][k] = sequence[k] # 재귀 공식으로 epsilon[j][k] 채우기 for k in range(n-1): for j in range(1, max_columns+1): if k+1 < n and epsilon[j][k] != 0: denom = epsilon[j][k+1] - epsilon[j][k] if abs(denom) < 1e-15: # 불안정 또는 division by zero 우려 break epsilon[j+1][k] = epsilon[j-1][k+1] + 1.0 / denom return epsilon # 예시로 x^{(k)} = 고정점 반복 cos(x)의 일부 항 seq = [] x = 1.0 for k in range(10): seq.append(x) x = math.cos(x) eps_table = wynn_epsilon_algorithm(seq) # eps_table[j][k]를 통해 특정 (j,k)에서의 가속값을 얻을 수 있다. # 예: 가속이 잘 된다면 eps_table[2][k], eps_table[4][k] 등이 좋은 근사값. ``` 이 코드는 매우 단순화된 형태로, 실제로는 $j$와 $k$에 따른 인덱스가 엄밀히 정의되어야 하고, 분모가 매우 작거나 0인 경우를 세밀히 처리해야 한다. 또한 $j$가 증가함에 따라 수치적으로 유의미한 결과가 보장되지 않을 수 있으므로, 원하는 수준의 가속 효과가 관측되면 중도에 중단하기도 한다. #### 중간 결론 Aitken 가속, Steffensen 방법, Richardson 외삽, Anderson 가속, Wynn의 ε 알고리즘 등은 모두 비선형 방정식 해석에서의 반복 수열을 더 빠르고 안정적으로 수렴시키기 위한 강력한 도구들이다. 이들 기법은 문제 특성과 수열의 오차 모델(기하급수형, 다항식형 등)에 따라 성능 차이가 크게 날 수 있다. 다음 절에서는 실제 예제와 실험 결과를 바탕으로 각 가속 방법의 적용 가능성과 한계점을 살펴본다. #### 가속 기법의 실제 응용과 성능 평가 비선형 방정식을 풀기 위해 반복법을 실행해본 경험이 있다면, 느린 수렴으로 인해 불필요하게 많은 계산 시간이 소요되는 문제를 종종 접하게 된다. 이때 가속 기법(Aitken, Anderson, Wynn의 ε 알고리즘 등)을 적절히 도입하면, 같은 반복 횟수로도 훨씬 높은 정밀도를 얻을 수 있거나, 혹은 목표 오차 범위 내에 도달하는 데 필요한 반복 횟수를 크게 줄일 수 있다. 하지만 현실의 복잡한 문제에서는 다양한 이슈가 얽혀있다. **오차 추정과 사전분석** 가속 기법이 효과적이려면, 수열 항들 사이의 오차 구조가 어느 정도 예측 가능하거나 일정해야 한다. 예컨대 $x^{(k+1)} - x^{(k)}$가 매우 불규칙하게 진동한다면, Aitken이나 Shanks 변환을 적용해도 분모가 불안정하게 변하거나, 일시적으로 발산하는 수치를 낳을 위험이 있다. 가속 전, 혹은 계산 초기 단계에서 $f(x)$ 또는 $g(x)$의 특성을 분석하여, 고정점 반복이 안정적으로 $\lambda^k$ 꼴(또는 다항식 꼴)로 접근할 가능성이 높은지, $|g'(r)|$이 어느 정도인지, 혹은 문제 구조상 다중 근이 존재할 우려는 없는지 등을 점검하는 것이 좋다. 이렇게 오차 구조를 어느 정도 파악해 두면, 가속 기법에서 분모가 갑자기 0에 가깝게 되어 난조를 일으키는 상황을 예상하고 방어 코드를 짤 수 있다. **간헐적 리셋 전략** 가속 기법 중 어떤 것을 쓰더라도, 반복이 충분히 진행되어 해 근방에 도달한 시점에서 분모가 급격히 작아지거나, 잔차 벡터들이 거의 선형 종속이 되어서 수치가 흔들리는 일이 일어날 수 있다. 이때는 가속 변환 테이블이나 과거 단계 데이터를 일시적으로 초기화(reset)하는 전략을 쓰면 효과적이다. 예컨대 Anderson 가속에서 $m$번의 과거 데이터를 모으되, 새 단계에서 “잔차가 특정 임계값 이하로 작아졌다”거나 “계수 행렬이 ill-conditioned 상태에 빠졌다”라고 판단되면, 일부분(혹은 전부)을 버리고 다시 모으기 시작한다. Wynn의 ε 알고리즘을 쓸 때도, 열(column)과 행(row)이 어느 정도 커진 후 분모가 작아지는 양상이 나타나면, 적절히 중단하거나 더 낮은 차수 변환만 사용한다. **하이브리드 접근: 가속 기법과 Newton류 기법의 결합** Newton 방법이 빠른 수렴 속도를 갖는다는 것은 널리 알려져 있지만, Jacobian 혹은 Hessian 계산 비용이 매우 큰 대규모 문제에서는 Newton 방법 자체가 부담스러울 수 있다. 따라서 미분 정보를 활용하지 않는 Picard 반복(혹은 단순 고정점 반복)을 기본으로 돌리되, 적절한 시점에 가속 기법을 적용하거나, 혹은 quasi-Newton 식으로 근사 Jacobian을 점진적으로 업데이트하는 방법이 널리 쓰인다. 특히 Anderson 가속과 quasi-Newton 접근의 결합은 상당히 강력한 수렴 촉진 효과를 발휘하는 것으로 보고되고 있으며, 다차원 대형 문제(고차원 유한요소 해석, DFT 계산 등)에서 유용하다. Newton-Krylov 방법 등을 쓰는 것보다 구현이 간단하고 메모리 사용량도 상대적으로 낮을 수 있다는 이점이 있다. **메모리 비용과 계산 비용** 가속 기법이 적용된 알고리즘은, 일반적으로 “분모를 구성하기 위해 연속된 수열 항 몇 개”를 기억해야 하며, 스칼라 문제에서는 그 비용이 미미하지만 고차원 문제에서는 여러 단계의 벡터를 저장하기 위해 추가 메모리를 소모한다. Anderson 가속을 예로 들면, 과거 $m$단계의 잔차 벡터를 $n$차원이라고 할 때 $m\times n$ 수준의 데이터가 필요하다. $m$이 커지면 잔차 벡터들 간의 내적 및 역행렬(또는 pseudo-inverse) 계산이 빈번해져서, 한 번의 반복 단계마다 비용이 늘어난다. 이와 같이 가속 기법이 실제로 효율적인가를 판단하려면, “총 반복 횟수 단축 효과”와 “추가 계산/저장 비용”을 균형 있게 따져야 한다. 작은 문제에서는 Aitken 가속이나 Steffensen 기법이 적절할 수 있고, 중간 규모 이상의 벡터 문제에서는 Anderson 가속이 더 좋은 선택이 될 수 있다. 하지만 매우 큰 문제에서는 $m$을 너무 크게 두면 계산 과정이 복잡해지고 수치 안정성도 나빠질 수 있다. **예제: 단순 고정점 반복 vs. 가속된 반복** 비교적 단순한 예로, 특정 $f(x)$에 대해 $x^{(k+1)} = g(x^{(k)})$ 형태의 반복을 실행할 때, Aitken 가속과 Anderson 가속을 각각 적용해 본다고 하자. 초기값을 여러 개로 바꿔 가며 테스트하면, 어떤 초기값 구간에서는 가속 기법이 빠르게 수렴하나, 다른 구간에서는 분모가 작아져 계산이 튀고 오히려 고정점 반복보다 늦어지는 경우도 있을 수 있다. 이런 현상은 “수렴 영역의 경계 부근” 또는 “초기값이 해에서 너무 멀리 떨어진 지점”에서 특히 두드러진다. 따라서 실전에서는 가속 기법 자체가 불안정해질 가능성을 고려해, 반복 과정 중에 잔차나 오차가 너무 커지는지 모니터링하고, 필요하면 다른 방법(NR, Secant, 두 방법의 혼합 등)으로 전환하기도 한다. **추가 내용** 가속 기법들의 이론은 매우 방대하고, 실전 구현에서 수치안정성을 확보하기 위한 다양한 변형이 존재한다. 본 장에서는 대표적인 기법들과 핵심 아이디어, 간단한 예제 코드를 살펴보았지만, 보다 복잡한 다차원 비선형 문제를 풀 때는 * (1) 문제 특성에 대한 사전 지식, * (2) 적절한 초기화 및 예외 처리, * (3) 최적의 매개변수($m$ 등) 선정, * (4) 필요 시 알맞은 시점에서의 리셋 등을 종합적으로 고려해야 한다.