7.51 다단계 방법과 아담스 방법

1. 다단계 방법의 기본 개념

1.1 단일 단계 방법과의 차이

룽게-쿠타법과 같은 단일 단계(single-step) 방법은 현재 시각의 정보 $(t_n, y_n)$ 만을 이용하여 다음 시각의 해 $y_{n+1}$ 을 계산한다. 반면 다단계(multistep) 방법은 이전 여러 시각의 해 $y_n, y_{n-1}, \ldots, y_{n-k+1}$ 과 함수값 $f_n, f_{n-1}, \ldots, f_{n-k+1}$ 을 함께 활용한다. 이미 계산된 정보를 재사용하므로, 각 단계에서의 함수 평가 횟수를 최소화하면서 높은 차수의 정확도를 달성할 수 있다.

1.2 일반적 선형 다단계 방법

$k$ 단계 선형 다단계 방법(linear multistep method, LMM)의 일반 형태는 다음과 같다.

$\sum_{j=0}^{k} \alpha_j y_{n+1-j} = h\sum_{j=0}^{k} \beta_j f_{n+1-j}$

여기서 $\alpha_0 = 1$ 이고, $f_{n+1-j} = f(t_{n+1-j}, y_{n+1-j})$ 이다. $\beta_0 = 0$ 이면 명시적(explicit) 방법이고, $\beta_0 \neq 0$ 이면 암시적(implicit) 방법이다.

2. 아담스-바시포스 방법

2.1 유도

아담스-바시포스(Adams-Bashforth, AB) 방법은 다음의 적분 관계에서 출발한다.

$y(t_{n+1}) = y(t_n) + \int_{t_n}^{t_{n+1}} f(t, y(t))\,dt$

피적분함수 $f(t, y(t))$ 를 이전 시각의 함수값 $f_n, f_{n-1}, \ldots$ 를 이용하여 뉴턴 후진 차분 보간 다항식(Newton backward difference interpolation polynomial)으로 근사하면 아담스-바시포스 공식이 유도된다. 보간 다항식의 차수에 따라 방법의 차수가 결정된다.

2.2 주요 공식

다음은 1~4단계 아담스-바시포스 공식이다.

1단계 (전진 오일러):

$y_{n+1} = y_n + hf_n$

2단계:

$y_{n+1} = y_n + \frac{h}{2}(3f_n - f_{n-1})$

3단계:

$y_{n+1} = y_n + \frac{h}{12}(23f_n - 16f_{n-1} + 5f_{n-2})$

4단계:

$y_{n+1} = y_n + \frac{h}{24}(55f_n - 59f_{n-1} + 37f_{n-2} - 9f_{n-3})$

$k$ 단계 아담스-바시포스 방법은 $k$ 차 정확도를 갖는다. 각 시간 단계에서 함수 $f$ 를 1회만 새로 평가하면 되므로, 동일 차수의 룽게-쿠타 방법에 비하여 단계당 계산 비용이 현저히 낮다.

3. 아담스-몰턴 방법

3.1 유도와 공식

아담스-몰턴(Adams-Moulton, AM) 방법은 보간 다항식에 현재 시각의 함수값 $f_{n+1}$ 도 포함하는 암시적 방법이다.

1단계 (암시적 사다리꼴 규칙):

$y_{n+1} = y_n + \frac{h}{2}(f_{n+1} + f_n)$

2단계:

$y_{n+1} = y_n + \frac{h}{12}(5f_{n+1} + 8f_n - f_{n-1})$

3단계:

$y_{n+1} = y_n + \frac{h}{24}(9f_{n+1} + 19f_n - 5f_{n-1} + f_{n-2})$

4단계:

$y_{n+1} = y_n + \frac{h}{720}(251f_{n+1} + 646f_n - 264f_{n-1} + 106f_{n-2} - 19f_{n-3})$

$k$ 단계 아담스-몰턴 방법은 $(k+1)$ 차 정확도를 갖는다. 즉, 동일한 단계 수에서 아담스-바시포스 방법보다 1차 높은 정확도를 달성하며, 오차 상수도 더 작다.

4. 아담스-바시포스와 아담스-몰턴의 비교

방법	유형	$k$ 단계의 차수	함수 평가/단계	안정성
아담스-바시포스	명시적	$k$	1회 (신규)	조건부 안정
아담스-몰턴	암시적	$k+1$	반복 필요	더 넓은 안정성

아담스-몰턴 방법은 더 높은 차수와 넓은 안정성 영역을 가지나, 암시적 방정식의 풀이가 필요하다는 단점이 있다. 실용적으로는 두 방법을 결합한 예측자-수정자 방식이 널리 사용된다.

5. 예측자-수정자 방법

5.1 ABM 방법

아담스-바시포스-몰턴(ABM) 예측자-수정자(predictor-corrector) 방법은 아담스-바시포스 공식으로 예측하고, 아담스-몰턴 공식으로 수정하는 2단계 절차이다.

예측 (AB $k$ ):

$\tilde{y}_{n+1} = y_n + h\sum_{j=0}^{k-1} b_j^* f_{n-j}$

평가:

$\tilde{f}_{n+1} = f(t_{n+1}, \tilde{y}_{n+1})$

수정 (AM $k$ ):

$y_{n+1} = y_n + h\sum_{j=-1}^{k-1} b_j f_{n-j}$

여기서 수정 단계에서 $f_{n+1}$ 을 $\tilde{f}_{n+1}$ 로 대체한다. 이 PECE(Predict-Evaluate-Correct-Evaluate) 방식에서 각 시간 단계의 함수 평가는 2회이다.

5.2 밀른 추정에 의한 오차 제어

예측값 $\tilde{y}_{n+1}$ 과 수정값 $y_{n+1}$ 의 차이로부터 국소 절단 오차를 추정할 수 있다. 이를 밀른 장치(Milne’s device)라 한다.

$\text{err} \approx \frac{y_{n+1} - \tilde{y}_{n+1}}{2^p - 1} \cdot C$

여기서 $C$ 는 예측자와 수정자의 오차 상수의 비에 의존하는 상수이다. 이 오차 추정값을 이용하여 적응적 시간 간격 제어를 수행할 수 있다.

6. 시동 문제와 해결 방법

6.1 시동의 필요성

$k$ 단계 다단계 방법은 최초 $k$ 개의 해 $y_0, y_1, \ldots, y_{k-1}$ 을 필요로 한다. 초기 조건으로부터는 $y_0$ 만 주어지므로, 나머지 $k-1$ 개의 시동값(starting values)을 별도로 계산하여야 한다.

6.2 시동 방법

시동값을 구하는 방법은 다음과 같다.

룽게-쿠타 시동: 동일한 시간 간격과 차수를 갖는 룽게-쿠타 방법으로 처음 $k-1$ 단계를 적분한다. 이 방법이 가장 널리 사용되며, 시동의 정확도가 전체 적분의 정확도를 좌우하므로 다단계 방법과 동일하거나 높은 차수의 룽게-쿠타 방법을 사용하여야 한다.
점진적 차수 증가: 1단계 방법으로 $y_1$ 을 구하고, 2단계 방법으로 $y_2$ 를 구하는 식으로 점진적으로 차수를 높여가는 방법이다.

7. 영안정성과 수렴

7.1 영안정성

다단계 방법의 영안정성(zero-stability)은 시간 간격 $h \to 0$ 의 극한에서 방법이 안정한지를 판정한다. 특성 다항식 $\rho(\zeta) = \sum_{j=0}^{k} \alpha_j \zeta^{k-j}$ 의 근이 모두 단위원 내부에 있거나, 단위원 위의 근이 단순근(simple root)인 경우 영안정하다.

이 조건을 만족하지 않으면 시간 간격을 아무리 줄여도 수치 해가 발산할 수 있으므로, 영안정성은 다단계 방법의 기본적 요건이다. 아담스 방법은 모든 차수에서 영안정하다.

7.2 수렴 정리

달퀴스트의 등가 정리(Dahlquist’s equivalence theorem)에 의하면, 일관성(consistency)과 영안정성은 수렴(convergence)의 필요충분조건이다. 즉, 다단계 방법이 수렴하기 위해서는 차수 조건을 만족하고(일관성) 동시에 영안정하여야 한다.

8. 가변 차수 및 가변 시간 간격 구현

8.1 가변 차수 전략

실용적인 아담스 방법 구현에서는 시간 간격뿐만 아니라 차수도 적응적으로 변경한다. 각 단계에서 현재 차수 $k$ 와 인접 차수 $k-1$ , $k+1$ 에 대한 오차 추정값을 비교하여, 가장 효율적인 차수를 선택한다. 차수를 높이면 정확도가 향상되나 안정성 영역이 줄어들고, 차수를 낮추면 안정성은 향상되나 정확도가 감소한다.

8.2 노르트시크 배열

가변 시간 간격 구현에서는 노르트시크(Nordsieck) 배열이 효율적이다. 노르트시크 벡터는 해와 그 스케일된 도함수로 구성된다.

$\mathbf{z}_n = \begin{bmatrix} y_n \\ h\dot{y}_n \\ \frac{h^2}{2}\ddot{y}_n \\ \vdots \end{bmatrix}$

시간 간격 변경 시 노르트시크 벡터의 간단한 스케일 변환만으로 과거 정보를 조정할 수 있으므로, 보간이나 재계산이 불필요하다. MATLAB의 ode113과 Sundials의 CVODE가 이 구조를 채택하고 있다.

9. 로봇 동역학에서의 활용

9.1 장시간 시뮬레이션에서의 효율

다단계 방법은 단계당 함수 평가가 1~2회에 불과하므로, 함수 평가 비용이 큰 다자유도 로봇 시뮬레이션에서 유리하다. 특히 관성 행렬의 분해가 각 함수 평가마다 필요한 순방향 동역학 문제에서, 함수 평가 횟수의 절감은 직접적인 계산 시간 단축으로 이어진다.

9.2 주의 사항

다단계 방법은 시동 비용이 존재하고, 시간 간격 변경 시 과거 정보의 재처리가 필요하므로, 시간 간격이 빈번하게 변하는 문제에서는 룽게-쿠타 방법에 비하여 비효율적일 수 있다. 또한 불연속적인 입력(충격 토크, 접촉 전환 등)이 존재하면 다단계 방법의 과거 정보가 무효화되므로, 불연속점에서 적분을 재시작하여야 한다.

10. 요약

다단계 방법은 이전 시각의 계산 정보를 재활용하여 각 단계의 함수 평가 횟수를 최소화하면서 높은 차수의 정확도를 달성한다. 아담스-바시포스 방법은 명시적이고, 아담스-몰턴 방법은 암시적이며, 이 둘을 결합한 예측자-수정자 방식이 실용적으로 널리 사용된다. 다단계 방법의 수렴은 일관성과 영안정성에 의해 보장되며, 가변 차수 및 가변 시간 간격 전략과 노르트시크 배열을 통한 효율적 구현이 가능하다. 로봇 동역학 시뮬레이션에서 함수 평가 비용이 지배적인 경우 다단계 방법이 유효한 대안이 된다.

참고 문헌

Hairer, E., Nørsett, S. P., & Wanner, G. (1993). Solving Ordinary Differential Equations I: Nonstiff Problems (2nd ed.). Springer.
Butcher, J. C. (2016). Numerical Methods for Ordinary Differential Equations (3rd ed.). Wiley.
Ascher, U. M. & Petzold, L. R. (1998). Computer Methods for Ordinary Differential Equations and Differential-Algebraic Equations. SIAM.
Shampine, L. F. & Gordon, M. K. (1975). Computer Solution of Ordinary Differential Equations: The Initial Value Problem. W. H. Freeman.
Hindmarsh, A. C. et al. (2005). “SUNDIALS: Suite of nonlinear and differential/algebraic equation solvers.” ACM Transactions on Mathematical Software, 31(3), 363–396.

version: 0.1.0