AAA 알고리즘

1. 개요

AAA 알고리즘(AAA algorithm, adaptive Antoulas–Anderson)은 함수의 샘플값만 가지고 유리함수 근사를 자동으로 만들어 내는 탐욕적 알고리즘이다. 근사를 바리센트릭 보간의 유리 형식으로 표현하고, 매 단계 오차가 가장 큰 샘플점을 지지점(support point)으로 추가한 다음, 나머지 점들에서의 선형화된 최소제곱 문제를 특이값 분해로 풀어 가중치를 정한다. 유지 나카쓰카사, 올리비에 세테, 닉 트레페텐이 2018년 발표했고, 이름의 두 A 는 바리센트릭 유리 보간을 제어이론에 도입한 안툴라스·앤더슨(1986)에서, 맨 앞 A 는 “적응적(adaptive)” 에서 왔다.¹

유리함수 $p/q$ 는 극점을 가질 수 있어서 극점·분지점·경계층 근처의 함수를 다항식보다 지수적으로 효율 있게 근사한다(다항식이 룽게 현상으로 죽는 곳에서 산다). 문제는 계산이었다. 고전적인 파데 근사나 단항식 기저의 선형화 최소제곱은 차수가 올라가면 극도로 불량조건이 되고, 가짜 극점(프루아사르 이중항)이 튀어나온다. AAA 는 두 가지 착상 — 바리센트릭 표현과 지지점의 탐욕적 선택 — 으로 이 불안정성을 거의 없앴고, 그 결과 “유리 근사를 몇 줄로, 기계 정밀도까지” 가 가능해졌다.² 2018년 이후 모델 차수 축소, 해석적 연속, 특이점 탐지, 주파수 응답 적합 등에 빠르게 퍼졌다.

2. 표현 — 바리센트릭 유리 형식

지지점 $z_1,\dots,z_m$ 과 거기서의 값 $f_j=f(z_j)$, 가중치 $w_j$ 로

$$r(z)=\frac{n(z)}{d(z)}=\frac{\displaystyle\sum_{j=1}^{m}\frac{w_j f_j}{z-z_j}}{\displaystyle\sum_{j=1}^{m}\frac{w_j}{z-z_j}}$$

라 두자. 분자·분모에 $\prod_j(z-z_j)$ 를 곱하면 둘 다 차수 $m-1$ 다항식이므로 $r$ 은 유형 $(m-1,m-1)$ 유리함수다. 그리고 $w_j\neq0$ 이면 $z\to z_j$ 에서 $r(z)\to f_j$, 즉 지지점에서 자동으로 보간한다. 가중치를 어떻게 고르든 이 성질은 유지되므로, 가중치는 보간이 아닌 나머지 점에서의 근사 품질을 위해 자유롭게 쓸 수 있다.

이 표현이 안정적인 이유는 기저 함수 $1/(z-z_j)$ 가 지지점 근처에서 “국소화” 되어 있기 때문이다. 단항식 $1,z,z^2,\dots$ 기저가 차수 20쯤에서 수치적으로 서로 구별되지 않는 것과 대조적이다. 바리센트릭 다항식 보간(가중치를 닫힌꼴로 고정한 특수한 경우)의 안정성 분석은 바리센트릭 보간 문서에 있다.

3. 알고리즘

샘플 집합 $Z$($M$ 개 점, 수백~수천 개)와 값 $F=f(Z)$ 가 주어진다. $m=0$, $r\equiv\operatorname{mean}(F)$ 에서 시작해 반복한다.

1. 탐욕적 선택. 아직 지지점이 아닌 샘플 중 $|F_i-r(Z_i)|$ 가 최대인 점을 새 지지점 $z_m$ 으로 뽑는다.
2. 선형화된 최소제곱. 남은 점들에서 $f\,d-n\approx0$ 이 되길 원한다. 이것은 가중치에 대해 선형이다.

$$\min_{\|w\|_2=1}\;\|A\,w\|_2,\qquad A_{ij}=\frac{F_i-f_j}{Z_i-z_j}$$

여기서 $A$ 는 $(M-m)\times m$ 뢰브너(Loewner) 행렬이다. 해는 $A$ 의 가장 작은 특이값에 대응하는 오른쪽 특이벡터다. 3. 오차 확인. 모든 샘플에서 $\max_i|F_i-r(Z_i)|\le\text{tol}\cdot\|F\|_\infty$ 면 멈춘다. 기본 허용오차는 $10^{-13}$ 이다.

$f\,d-n$ 은 $f-r$ 에 $d$ 를 곱한 것이라 진짜 오차와는 다르다(이것이 “선형화” 의 의미다). 그래도 탐욕적 선택이 진짜 오차 $|f-r|$ 을 기준으로 하기 때문에 전체 알고리즘은 진짜 오차를 줄이는 방향으로 간다.

3.1. 극점·영점·유수

$r$ 의 극점은 $d(z)=0$ 의 근인데, 이것을 다항식으로 바꾸지 않고 다음 $(m+1)\times(m+1)$ 일반화 고유값 문제로 바로 구한다.

$$\begin{pmatrix}0 & w_1 & \cdots & w_m\\ 1 & z_1 & & \\ \vdots & & \ddots & \\ 1 & & & z_m\end{pmatrix}v=\lambda\begin{pmatrix}0 & & & \\ & 1 & & \\ & & \ddots & \\ & & & 1\end{pmatrix}v$$

유한 고유값 $m-1$ 개가 극점이다(무한 고유값 2개는 버린다). 영점은 첫 행의 $w_j$ 를 $w_jf_j$ 로 바꾸면 된다. 다항식 근을 동반 행렬 고유값으로 구하는 것의 바리센트릭 버전이다.

3.2. 프루아사르 이중항 청소

허용오차 근처까지 가면 극점과 영점이 거의 겹쳐 서로 상쇄하는 가짜 극점이 생길 수 있다. AAA 는 유수가 $10^{-13}$ 수준으로 작은 극점을 찾아 가장 가까운 지지점을 제거하고 최소제곱을 다시 푸는 청소 단계를 둔다. 파데 근사에서 이 문제를 강건 파데(SVD 로 수치적 계수를 잘라 냄)로 다루는 것과 같은 뿌리다.

4. 검산

$[-1,1]$ 또는 지정 구간의 등간격 2000점에서 직접 구현한 AAA(위 알고리즘 그대로, 청소 단계 생략)를 돌리고, 샘플 사이의 1만 점에서 오차를 쟀다.

$f$	지지점 수 $m$	시험 오차	비고
$e^x$	7	$1.8\times10^{-15}$	유형 (6,6)
$1/(1+25x^2)$	3	$2.3\times10^{-15}$	극점 $\pm0.2i$ 를 정확히 복원
$\log(1.1-x)$	11	$1.3\times10^{-14}$	분지점 $x=1.1$ 이 구간 바로 밖
$\tan x$, $[-1.5,1.5]$	9	$1.2\times10^{-14}$	극점 $\pm1.57079633=\pm\pi/2$
$\lvert x\rvert$	47	$2.0\times10^{-4}$	샘플 해상도가 병목 (아래)

룽게 함수 $1/(1+25x^2)$ 는 등간격 다항식 보간이 발산하는 교과서 예제지만 그 자체가 유형 (0,2) 유리함수라서, AAA 는 지지점 3개로 끝내고 극점 $\pm i/5$ 를 기계 정밀도로 돌려준다. $\tan x$ 의 오차 수열은 $28\to8.7\to0.21\to3.6\times10^{-3}\to4.5\times10^{-5}\to2.2\times10^{-7}\to1.0\times10^{-9}\to4.8\times10^{-12}\to1.2\times10^{-14}$ 로, 지지점 하나당 두 자릿수 이상씩 줄었다.

$|x|$ 행이 함정을 보여 준다. 샘플 위에서는 47개 지지점으로 $10^{-13}$ 까지 맞췄는데, 샘플 사이에서 잰 최대 오차는 $x\approx10^{-9}$, 즉 원점 바로 옆에서 $2\times10^{-4}$ 였다. 등간격 샘플의 간격(약 $10^{-3}$)보다 작은 축척의 특이점 구조는 샘플에 없으니 AAA 가 볼 수도 없다. 원 논문도 $|x|$ 처럼 특이점이 있는 함수는 특이점 쪽으로 지수적으로 몰린 샘플을 쓰라고 권한다. 유리 근사로 $|x|$ 를 근사하면 오차가 차수 $n$ 에 대해 $e^{-\pi\sqrt n}$ 꼴로 준다는 뉴먼(1964)·슈탈의 결과가 있으니 원리적으로는 가능하지만, 샘플이 특이점을 해상하는 경우에 한해서다.³

5. 어디에 쓰나

• 해석적 연속·특이점 탐지. 실축에서만 잰 데이터로 복소평면의 극점·분지점 위치를 추정한다. 극점 위치 자체가 물리량인 경우(공진 주파수, 감쇠율, 준정규 모드)에 특히 유용하다.
• 주파수 응답 적합·모델 축소. 회로·구조물의 주파수 응답 $H(i\omega)$ 샘플에서 저차 유리 전달함수를 뽑는다. 이 분야의 전통 강자는 벡터 피팅인데, AAA 는 초기 극점 추측이 필요 없다는 장점이 있다. 축소차수모델·주파수 응답 해석과 이어진다.
• 특수함수·행렬함수 근사. 함수 값을 싸게 평가하는 대리 근사를 만든 뒤, 극점-유수 분해로 $f(A)b$ 같은 행렬함수 계산을 선형계 몇 개로 바꾼다.
• 최량(minimax) 근사의 초기값. 나카쓰카사·트레페텐(2020)의 AAA-로슨은 AAA 결과를 반복 가중 최소제곱(로슨 반복)으로 다듬어 최량 유리 근사에 가깝게 만든다. 고전적인 레머즈 알고리즘이 초기값에 민감해 실패하던 문제를 상당 부분 우회한다.⁴

6. 한계

• 가짜 극점은 완전히 사라지지 않는다. 청소 단계가 대부분 잡지만, 잡음 섞인 데이터에서 허용오차를 잡음 수준보다 낮게 잡으면 잡음을 적합하는 극점이 생긴다. 허용오차는 데이터 정확도에 맞춰라.
• 실수 대칭이 기본으로 보존되지 않는다. 실함수를 근사해도 극점이 켤레쌍으로 정확히 나오지 않을 수 있다. 물리 시스템 식별처럼 켤레 대칭·안정성(극점이 좌반평면)이 필요하면 후처리나 변형판을 쓴다.
• 비용. 단계마다 SVD 를 새로 하므로 $m$ 이 수백으로 커지면 느리다. 대부분의 응용에서 $m\le100$ 이라 문제가 되진 않는다.

7. 관련 문서

• 바리센트릭 보간 · 파데 근사 · 룽게 현상 · 체비쇼프 다항식
• 특이값 분해 · 코시 행렬 · 동반 행렬 · 레머즈 알고리즘
• 벡터 피팅 · 뢰브너 행렬 · 축소차수모델

8. Footnotes

1. 읽을 때는 “트리플 에이” 라고 한다. 신용등급 최고 단계와 같은 이름이라 저자들도 이 우연을 꽤 즐긴 것으로 보인다. 알고리즘 이름 짓기에서 약자 운이 이 정도로 따르는 경우는 드물다. ↩

2. 원 논문 부록의 MATLAB 코드가 주석 빼고 수십 줄이다. “새 알고리즘인데 논문 부록에 전체 코드가 들어간다” 는 것 자체가 이 바닥에서는 강력한 홍보 문구다. ↩

3. AAA 는 “샘플에서 오차 $10^{-13}$” 을 정직하게 보고한다. 거짓말은 하지 않았다. 다만 우리가 샘플 사이도 같은 줄 알았을 뿐. 데이터 기반 근사의 영원한 교훈 — 모델은 본 것만 안다. ↩

4. 로슨 반복은 1961년 박사논문에서 나온, 가중 최소제곱의 가중치를 오차 크기에 따라 곱셈적으로 갱신해 최대 오차를 줄이는 방법이다. 60년 묵은 아이디어가 AAA 라는 좋은 초기값을 만나 다시 쓸모를 찾았다. 수치해석에서 흔한 “옛날 방법 + 새 출발점 = 새 방법” 공식. ↩