베를레 적분

1. 개요

베를레 적분 Verlet Integration
분야	수치해석 × 분자동역학 × 게임 물리
대상	2차 상미분방정식 (뉴턴 운동방정식)
성질	심플렉틱 · 시간 가역 · 전역 2차 정확도
주요 변형	position Verlet, velocity Verlet
이름 유래	Loup Verlet (1967), 별칭 Störmer–Verlet

에너지가 서서히 새어 나가 시뮬레이션이 죽는 것 — 베를레는 그걸 안 한다. 그게 전부이자, 그게 위대함이다.

베를레 적분(Verlet integration)은 뉴턴의 운동방정식처럼 2차 상미분방정식(ODE)을 수치적으로 푸는 시간적분 기법이다. 가속도(힘)로부터 위치를 시간에 따라 전진시키되, 속도를 명시적으로 다루지 않고 현재와 이전 위치의 차이로 대신 표현하는 것이 특징이다. 분자동역학, 천 시뮬레이션, 물리 엔진에서 표준적으로 쓰이며, 단순함과 안정성이라는 두 마리 토끼를 동시에 잡은 드문 알고리즘으로 꼽힌다.

핵심 가치는 장기 안정성에 있다. 겉보기에 더 정확한 룽게-쿠타법(RK4) 같은 고차 기법이 오랜 시뮬레이션에서 에너지를 슬금슬금 잃거나 얻어 궤도가 나선을 그리며 무너지는 반면, 베를레는 에너지를 정확히 보존하진 않아도 그 주위에서 오차가 갇힌 채 진동한다. 별이 궤도를 백만 바퀴 돌아도 떨어지지 않고, 천이 몇 시간을 펄럭여도 폭발하지 않는 것 — 이 성질 하나로 베를레는 물리 시뮬레이션의 사실상 표준이 되었다.

2. 두 가지 형태

베를레 적분에는 널리 쓰이는 두 형태가 있다.

2.1. 기본형 (Störmer–Verlet, 위치 베를레)

가장 원초적인 형태로, 속도 변수 없이 위치만으로 전진한다. 테일러 전개를 앞뒤로 더해 1차항(속도)을 소거하면 다음을 얻는다.

$$\mathbf{x}_{n+1} = 2\mathbf{x}_n - \mathbf{x}_{n-1} + \mathbf{a}_n \, \Delta t^2$$

속도가 식에 아예 등장하지 않는다는 점이 놀랍다. 필요하면 $\mathbf{v}_n \approx (\mathbf{x}_{n+1} - \mathbf{x}_{n-1}) / (2\Delta t)$로 사후에 추정한다. 이 “속도 없음”이 게임 물리에서 결정적 이점이 되는데, 제약(constraint)을 처리할 때 그냥 위치를 원하는 자리로 옮기기만 하면 속도가 위치 이력에서 자동으로 따라오기 때문이다.¹

2.2. Velocity Verlet

속도를 명시적으로 관리해 수치적으로 더 다루기 쉬운 형태다. 위치와 속도를 같은 시각에 들고 다니되, 속도를 반 스텝씩 두 번(새 위치에서 힘을 다시 계산한 뒤 나머지 반) 나눠 갱신한다.

$$\mathbf{x}_{n+1} = \mathbf{x}_n + \mathbf{v}_n \, \Delta t + \tfrac{1}{2}\mathbf{a}_n \, \Delta t^2$$ $$\mathbf{v}_{n+1} = \mathbf{v}_n + \tfrac{1}{2}(\mathbf{a}_n + \mathbf{a}_{n+1}) \, \Delta t$$

속도를 직접 들고 있어 운동에너지·온도를 매 스텝 정확히 재야 하는 분자동역학에서 선호된다(MD 표준형으로 굳은 건 1982년 Swope 등의 논문 이후다). 정확한 산술에서는 기본형과 같은 위치 궤적을 만들지만, 기본형이 큰 값 $2\mathbf{x}_n - \mathbf{x}_{n-1}$에 작은 값 $\mathbf{a}_n\Delta t^2$를 더하느라 자릿수를 잃는 반면 이 형태는 그런 손실이 적고, $\mathbf{x}_{-1}$ 같은 가상의 이전 위치 없이 $(\mathbf{x}_0, \mathbf{v}_0)$만으로 출발할 수 있다. 첫 반 스텝 속도 갱신과 위치 갱신만 떼어 보면 시간축을 반 칸 엇갈린 도약 개구리(leapfrog) 방법과도 같은 알고리즘이다.

단, 속도 의존 힘(마찰, 항력, 랑주뱅 온도 조절)을 넣으면 $\mathbf{a}_{n+1}$이 아직 모르는 $\mathbf{v}_{n+1}$에 의존하게 돼 식이 음함수가 된다. 실무 코드는 이 부분을 연산자 분할로 따로 떼어 처리하는데, 그 순간 엄밀한 심플렉틱성은 (원래 소산계라 보존할 게 없으니) 포기하게 된다.

2.3. 정확도 차수 — 국소와 전역을 헷갈리지 말 것

기본형의 위치 갱신은 테일러 전개에서 홀수 차항이 모두 상쇄되므로 한 스텝 국소 절단오차가 $O(\Delta t^4)$ 이다. 하지만 이 오차가 $T/\Delta t$ 스텝 동안 쌓이고, 두 단계 점화식이라 누적 방식도 한 차수를 더 깎아서, 고정 시각 $T$에서의 전역 오차는 $O(\Delta t^2)$ 다. 중앙차분으로 사후 추정한 속도도 $O(\Delta t^2)$. “베를레는 4차”라는 말이 가끔 돌아다니는 건 국소 오차를 전역 정확도로 착각한 탓이다.

3. 왜 RK4보다 물리에 좋은가

정확도만 따지면 4차 정확도인 룽게-쿠타법(RK4)이 2차 정확도인 베를레를 압도한다. 그런데도 물리 시뮬레이션이 베를레를 택하는 이유는 정확도가 아니라 구조 보존에 있다.

베를레는 심플렉틱 적분기다. 한 스텝의 사상이 위상공간의 심플렉틱 2-형식을 보존한다는 뜻인데(위상공간 부피 보존은 그 결과 중 하나일 뿐, 부피만 보존한다고 심플렉틱인 건 아니다), 이는 물리적으로 해밀토니안(전체 에너지)을 정확히는 아니어도 유계(bounded)한 오차 안에 가둔다는 뜻이다. 즉 에너지가 실제 값 주위에서 진동할 뿐, 한 방향으로 계속 새거나 쌓이지 않는다.² RK4는 심플렉틱이 아니라서, 한 스텝의 오차는 작아도 그 오차가 계통적으로 누적되어 긴 적분에서는 에너지가 표류한다 — 진자는 서서히 멈추고, 궤도는 조금씩 안쪽으로 감긴다.

항목	베를레(심플렉틱)	RK4
전역 정확도	2차	4차
장기 에너지	유계 진동	표류(감쇠/발산)
스텝당 힘 계산	1회	4회
물리 시뮬 적합성	우수	부적합

짧은 궤적을 정밀하게 그리려면 RK4, 오랜 시간 물리적으로 그럴듯하게 굴리려면 베를레. 게임과 분자동역학은 언제나 후자다.

3.1. 조화 진동자로 검산

말로만 하면 믿기 어려우니 $\ddot{x} = -\omega^2 x$, $\omega = 1$, $x_0 = 1$, $v_0 = 0$을 두 방법으로 직접 굴려 상대 에너지 오차 $|E - E_0|/E_0$를 쟀다.

$\omega\Delta t$	주기 수	속도 베를레 최대 오차	RK4 최종 오차
0.1	100	0.0025	0.00009 (감소 쪽)
0.1	10,000	0.0025	0.0087 (감소 쪽)
0.3	100	0.0225	0.021 (감소 쪽)
0.3	10,000	0.0225	0.877 (에너지 88 % 소실)

읽는 법이 중요하다. 짧게 돌리면 RK4가 베를레보다 30배 정확하다. 그런데 베를레의 오차는 주기를 100배 늘려도 1자리도 안 늘어난다 — 진동자의 경우 오차 진폭이 정확히 $(\omega\Delta t)^2/4$에서 멈춘다. RK4는 한 스텝 증폭률 크기가 $|R|^2 = 1 - (\omega\Delta t)^6/72 + (\omega\Delta t)^8/576 < 1$이라 스텝마다 에너지를 아주 조금씩 잃고, $\omega\Delta t = 0.1$에서 약 63만 스텝을 쌓으면 이론값 $1 - (1 - 1.39\times10^{-8})^{628{,}319} \approx 0.0087$이 실측과 그대로 맞는다. 결국 시뮬레이션이 길어질수록 승부가 뒤집힌다.

안정성 한계도 같은 계산으로 확인된다. 베를레의 진동자 증폭 행렬은 $\omega\Delta t < 2$일 때만 고유값이 단위원 위에 머문다. 실측해 보면 $\omega\Delta t = 1.99$에서는 오차가 크긴 해도 유계이고, $2.01$에서는 200 시간 단위 만에 에너지가 $10^{16}$배로 폭발한다. MD에서 가장 빠른 진동(수소가 붙은 결합 신축, 주기 약 10 fs)이 시간 스텝을 1 fs 언저리로 묶는 이유이고, 그래서 SHAKE 같은 결합 길이 구속으로 그 진동을 얼려 2 fs까지 늘리는 게 관행이 되었다.

3.2. 시간 가역성

또 하나의 미덕은 시간 가역성(time reversibility)이다. Position Verlet 식은 $\Delta t \to -\Delta t$로 바꿔도 형태가 그대로라, 시뮬레이션을 거꾸로 돌리면 원래 경로를 되짚어 온다. 이는 물리 법칙 자체가 지닌 시간 대칭성을 이산 세계에서도 보존하는 것으로, 심플렉틱성과 더불어 장기 안정성의 뿌리다.

4. 활용

• 분자동역학 — 수만~수백만 개 원자를 수 나노초 동안 적분하는 MD 시뮬레이션의 표준 적분기다. 스텝당 힘 계산이 단 한 번이라는 점(RK4는 네 번)이 대규모 계에서 결정적 비용 절감이 된다.
• 천 시뮬레이션 — 천을 질점과 스프링의 격자로 보고, 각 질점을 position Verlet으로 굴린 뒤 “이웃 질점 간 거리 유지”라는 제약을 반복 적용하는 방식이 고전이다. 토마스 야콥센(Thomas Jakobsen)이 게임 Hitman: Codename 47(2000)의 래그돌·천에 쓴 기법이 이 접근의 교과서로 통한다.³
• 물리 엔진 — 위치 기반 동역학(Position Based Dynamics, PBD) 계열이 베를레의 “위치만 옮기면 된다”는 철학을 계승해, 제약을 위치 투영으로 직접 푸는 현대 게임 물리의 주류를 이룬다.

5. 역사

베를레 적분이라는 이름은 프랑스 물리학자 루 베를레(Loup Verlet)에게서 왔다. 그는 1967년 레너드-존스 퍼텐셜로 아르곤을 흉내 낸 입자 864개의 분자동역학 논문에서 이 방법을 (재)도입했다. 다만 이 알고리즘의 뿌리는 훨씬 깊다. Hairer·Lubich·Wanner의 역사 정리에 따르면 1791년 천문학자 들랑브르(Delambre)가 이미 같은 차분식을 썼고, 1907년 노르웨이의 수학자·지구물리학자 카를 스퇴르머(Carl Størmer)가 오로라 속 하전입자 궤적을 계산하는 데 썼으며, 1909년 카월과 크로멜린은 핼리 혜성의 궤도 계산에 동원했다. 심지어 뉴턴의 『프린키피아』(1687)에서 케플러 제2법칙을 기하학적으로 증명하는 대목도 이 방법의 한 스텝과 같은 구조로 읽힌다. 그래서 학계에서는 스퇴르머-베를레 방법(Störmer–Verlet method)이라는 이름도 널리 통용된다.⁴ 300년 넘게 여러 분야에서 거듭 재발견된 셈인데, 좋은 도구는 원래 여러 번 발명되는 법이다.

6. 관련 문서

• 분자동역학
• 룽게-쿠타법
• 물리 엔진
• 심플렉틱 적분기 · 위치 기반 동역학
• 레너드-존스 퍼텐셜 · 해밀턴 원리
• 도약 개구리 방법 · 에너지 보존
• SPH
• 충돌 감지

7. Footnotes

1. 이 성질 때문에 천 시뮬레이션에서 “옷이 캐릭터를 뚫지 않게” 하는 제약 처리가 우아해진다. 침투한 질점을 표면 밖으로 위치만 밀어내면, 다음 스텝에서 속도가 위치 이력으로부터 알아서 갱신된다. 속도를 따로 손댈 필요가 없다. ↩

2. 엄밀히는 심플렉틱 적분기가 (거의) 보존하는 것은 원래 해밀토니안이 아니라 그에 $O(\Delta t^2)$만큼 가까운 “그림자 해밀토니안(shadow Hamiltonian)“이다. 해밀토니안이 해석적이고 $\Delta t$가 충분히 작으면 이 근사가 $\Delta t$에 대해 지수적으로 긴 시간 동안 유지된다는 게 후방 오차 해석의 결론이다. “영원히”는 아니고 “우주 나이쯤은 거뜬히” 정도. 다만 MD처럼 컷오프로 퍼텐셜을 자르거나 이웃 목록을 늦게 갱신하면 힘이 매끄럽지 않아져 이 보장이 깨지고 느린 에너지 표류가 다시 나타난다. ↩

3. Jakobsen, T. (2001), “Advanced Character Physics”, GDC. 이 짧은 발표 자료 하나가 이후 십수 년간 게임 물리 프로그래머들의 필독서가 되었다. 속도 없이 위치와 제약만으로 래그돌을 굴린다는 발상이 당시엔 신선한 충격이었다. ↩

4. 뉴턴 역학의 상당수 표준 도구가 그렇듯, “베를레”라는 이름은 관행일 뿐 유일한 발명자를 가리키지 않는다. 스티글러의 명명 법칙(어떤 과학적 발견도 최초 발견자의 이름을 따지 않는다)의 또 다른 사례다. ↩