6.57 행렬 분해의 수치적 구현과 로봇 제어 응용

1. 도입

행렬 분해는 이론적 표현과 실제 수치 계산 사이의 가교 역할을 한다. 동일한 수학적 분해라도 실제 구현 방식에 따라 정확도, 속도, 메모리 사용량, 안정성에서 큰 차이를 보이며, 로봇 제어처럼 실시간성과 신뢰성이 동시에 요구되는 환경에서는 적절한 구현 전략의 선택이 시스템 전체의 성능을 좌우한다. 본 절에서는 주요 행렬 분해의 수치적 구현 원리와 표준 라이브러리, 그리고 이러한 도구가 로봇 제어 시스템에서 활용되는 구체적인 방식을 다룬다.

2. 부동소수점 연산과 기계 정밀도

수치 행렬 분해의 정확도는 본질적으로 부동소수점 산술의 한계에 의해 결정된다. IEEE 754 표준의 배정밀도 부동소수점 수는 약 \epsilon_{\text{mach}} \approx 2.22 \times 10^{-16} 의 기계 엡실론을 갖는다. 임의의 산술 연산은 다음과 같은 후방 오차를 동반한다.

\mathrm{fl}(a \circ b) = (a \circ b)(1 + \delta), \quad \vert \delta \vert \le \epsilon_{\text{mach}}

이러한 미세한 오차가 행렬 분해의 수많은 연산을 거치면서 누적되며, 알고리즘의 안정성에 따라 누적 양상이 크게 달라진다. 후방 안정 알고리즘은 계산된 결과가 입력의 미세한 섭동에 대한 정확한 결과와 일치함을 보장한다.

3. 조건수와 오차 한계

선형 시스템 A\mathbf{x} = \mathbf{b} 의 해의 정확도는 행렬 A 의 조건수 \kappa(A) = \Vert A \Vert \cdot \Vert A^{-1} \Vert 에 의해 결정된다. 후방 안정 알고리즘으로 계산된 해 \hat{\mathbf{x}} 의 상대 오차는 다음 한계를 만족한다.

\frac{\Vert \hat{\mathbf{x}} - \mathbf{x} \Vert}{\Vert \mathbf{x} \Vert} \lesssim \kappa(A) \epsilon_{\text{mach}}

따라서 조건수가 큰 행렬에 대해서는 알고리즘의 안정성과 무관하게 결과의 정확도가 본질적으로 제한된다. 로봇 자코비안의 특이점 근방, 관성 행렬의 자세 의존적 변동, 그리고 매개변수 식별의 회귀자 행렬 등에서 조건수 문제는 자주 발생하며, 이를 인식하고 대처하는 것이 견고한 수치 구현의 핵심이다.

4. 주요 행렬 분해의 연산량 비교

대표적인 행렬 분해의 점근적 연산량은 다음과 같다.

이 표는 각 분해의 비용과 적용 가능성을 비교하는 기준을 제공한다. 실시간 제어에서는 가능한 가장 효율적인 분해를 선택해야 하며, 일반적으로 양정치성과 같은 구조적 정보를 활용하는 분해가 우선시된다.

5. 표준 수치 선형대수 라이브러리

산업과 학계에서 표준적으로 사용되는 수치 선형대수 라이브러리는 다음과 같이 계층적으로 구성된다. BLAS(Basic Linear Algebra Subprograms)는 기본적인 벡터-벡터, 행렬-벡터, 행렬-행렬 연산을 제공하며, 하드웨어 최적화의 핵심 계층이다. LAPACK(Linear Algebra Package)은 BLAS 위에 구축되어 모든 표준 행렬 분해와 연립 방정식 해법을 제공한다.

이러한 라이브러리의 구현은 캐시 효율성, 벡터화, 다중 스레딩을 고려하여 매우 정교하게 최적화되어 있으며, 직접 구현한 코드와 비교하여 수십 배 이상의 성능 차이를 보인다. 따라서 로봇 제어 시스템 개발에서는 가능한 한 검증된 라이브러리를 사용하는 것이 권장된다.

6. 블록 알고리즘과 캐시 효율성

대규모 행렬 분해의 효율성은 캐시 메모리의 효과적인 활용에 크게 의존한다. 블록 알고리즘은 행렬을 블록 단위로 나누어 처리함으로써 캐시 재사용률을 극대화한다. 예를 들어 블록 LU 분해는 다음과 같은 블록 분할을 활용한다.

\begin{pmatrix} A_{11} & A_{12} \\ A_{21} & A_{22} \end{pmatrix} = \begin{pmatrix} L_{11} & 0 \\ L_{21} & L_{22} \end{pmatrix} \begin{pmatrix} U_{11} & U_{12} \\ 0 & U_{22} \end{pmatrix}

각 블록 부분 분해는 BLAS-3 수준의 행렬-행렬 연산을 호출하며, 이는 BLAS-2 수준의 연산보다 캐시 활용 면에서 훨씬 효율적이다. 이러한 블록 구조는 LAPACK의 모든 분해 루틴에 적용되어 있다.

7. 희소 행렬 분해

로봇공학에서 자주 등장하는 큰 행렬은 대부분 희소 구조를 가진다. 그래프 SLAM의 정보 행렬, 유한 요소 모델의 강성 행렬, 다물체 동역학의 결합 행렬 등이 그 예이다. 이러한 행렬에 대해 일반적인 밀집 분해를 적용하면 비효율적이며, 희소 행렬 분해 알고리즘이 사용된다.

희소 LU 및 촐레스키 분해의 핵심은 채움(fill-in)을 최소화하는 변수 재정렬이다. 최소 차수 알고리즘, 중첩 분할(nested dissection), 역 커스힐-맥키 알고리즘 등이 표준적으로 사용된다. 적절한 재정렬을 통해 분해 과정에서 생성되는 비영 원소의 수를 크게 줄일 수 있으며, 이는 메모리 사용량과 연산 시간 모두에서 큰 개선을 가져온다.

8. 수치적 안정성 강화 기법

수치적 안정성을 강화하기 위한 표준 기법에는 다음이 있다. 첫째, 반복 정련(iterative refinement)은 분해 후 잔차를 계산하고 보정 항을 추가하여 정확도를 높인다. 둘째, 조건수 추정은 분해 결과로부터 행렬의 조건수를 추정하여 결과의 신뢰성을 평가한다. 셋째, 균등화(equilibration)는 행과 열을 적절히 척도화하여 조건수를 개선한다.

특히 반복 정련은 다음 절차로 수행된다.

1. 초기 해 \mathbf{x}^{(0)} 를 분해를 통해 계산한다.
2. 잔차 \mathbf{r}^{(k)} = \mathbf{b} - A\mathbf{x}^{(k)} 를 더 높은 정밀도로 계산한다.
3. 보정 항 \delta\mathbf{x}^{(k)} 를 분해 결과를 재사용하여 계산한다.
4. \mathbf{x}^{(k+1)} = \mathbf{x}^{(k)} + \delta\mathbf{x}^{(k)} 로 갱신한다.

이 과정은 일반적으로 두세 번의 반복만으로 기계 정밀도에 가까운 정확도를 달성한다.

9. 실시간 제약과 결정론적 실행

로봇 제어 시스템의 가장 큰 제약은 결정론적 실행 시간이다. 일반적인 수치 라이브러리는 평균 성능에 최적화되어 있어 최악의 경우 실행 시간을 보장하지 않는다. 이로 인해 실시간 제어 루프 내에서 사용되는 분해 알고리즘은 다음과 같은 특성을 가져야 한다.

1. 연산 횟수가 입력 데이터에 무관하게 결정적이어야 한다.
2. 동적 메모리 할당이 없어야 한다.
3. 분기와 캐시 미스를 최소화해야 한다.
4. 최악의 경우 실행 시간이 제어 주기 내에 보장되어야 한다.

이러한 요구사항을 충족하기 위해 로봇 제어용 수치 라이브러리는 일반 라이브러리와 별도로 개발되며, 보수적인 알고리즘 선택과 정교한 시간 분석을 통해 구현된다.

10. 분해 알고리즘 선택 지침

특정 문제에 대한 적절한 분해의 선택은 다음 기준에 따라 이루어진다.

• 행렬이 대칭 양정치이면 촐레스키 분해를 사용한다.
• 행렬이 대칭이지만 부정치이면 부카블로크-카우프만 분해를 사용한다.
• 행렬이 일반적인 정방 행렬이면 부분 피벗팅 LU 분해를 사용한다.
• 과결정 최소 제곱 문제에는 QR 분해를 사용한다.
• 랭크 결손이 의심되는 경우에는 SVD 또는 열 피벗팅 QR 분해를 사용한다.
• 고유값 정보가 필요한 경우에는 슈어 분해(일반 행렬) 또는 대칭 고유 분해(대칭 행렬)를 사용한다.

이러한 지침은 행렬의 구조적 정보를 최대한 활용하여 가장 효율적이고 안정적인 결과를 얻기 위한 것이다.

11. 로봇공학에서의 응용

11.1 정동역학 시뮬레이션

로봇 매니퓰레이터의 정동역학 방정식 M(q)\ddot{q} = \tau - C(q,\dot{q})\dot{q} - g(q) 에서 가속도를 계산하기 위해 매 시간 단계마다 관성 행렬 M(q) 에 대한 분해가 수행된다. M(q) 가 대칭 양정치이므로 촐레스키 분해가 표준이며, n 자유도 매니퓰레이터에 대해 \frac{1}{3}n^3 의 연산만으로 해결된다. 이는 1 kHz 이상의 고주파 시뮬레이션을 가능하게 하며, 모델 기반 제어와 강화 학습 환경의 핵심 계산이다.

11.2 운영 공간 제어

운영 공간 제어에서 핵심적인 운영 공간 관성 행렬 \Lambda(q) = (J M^{-1} J^{\top})^{-1} 의 계산은 두 개의 행렬 분해를 요구한다. 먼저 M 의 촐레스키 분해를 통해 M^{-1} J^{\top} 를 계산하고, 그 후 J M^{-1} J^{\top} 의 작은 차원 분해를 수행한다. 이러한 단계적 분해는 직접 역행렬 계산보다 훨씬 안정적이며, 작업 공간에서 직접 힘 또는 가속도 명령을 내릴 수 있게 한다.

11.3 자코비안 기반 역기구학

자코비안 기반 역기구학 알고리즘은 매 반복마다 자코비안의 분해를 요구한다. 여유 자유도 매니퓰레이터에 대해서는 J^{\top} 의 QR 분해 또는 감쇠 의사 역행렬 (J^{\top} J + \lambda^2 I)^{-1} J^{\top} 의 촐레스키 분해가 사용된다. 특이점 근방에서는 SVD 기반 처리가 안정적이며, 작은 특이값을 절단하여 운동의 발산을 방지한다.

11.4 동역학 매개변수 식별

로봇 동역학 매개변수의 식별은 다양한 자세에서 수집된 측정 데이터로부터 최소 제곱 문제 \min_{\boldsymbol{\theta}} \Vert Y \boldsymbol{\theta} - \boldsymbol{\tau} \Vert_2^2 를 해결하는 과정이다. 회귀자 행렬 Y 의 QR 분해를 통해 안정적이고 정확한 매개변수 추정을 얻으며, 식별 가능 매개변수와 비식별 매개변수를 분리할 수 있다. 이는 로봇의 정밀 동역학 모델 구축에 핵심적이다.

11.5 모델 예측 제어의 이차 계획

모델 예측 제어(MPC)의 내부 루프에서는 매 시간 단계마다 이차 계획 문제를 풀어야 한다. 활성 집합 방법, 내부점 방법 등의 표준 알고리즘은 모두 부분 문제로 선형 시스템을 해결하며, 이때 촐레스키 분해 또는 LDL 분해의 효율적인 갱신 알고리즘이 사용된다. 점진적 갱신을 활용하면 매 단계의 분해 비용을 크게 줄일 수 있다.

11.6 칼만 필터의 제곱근 형식

확장 칼만 필터와 무향 칼만 필터의 제곱근 형식은 공분산 행렬 대신 그 촐레스키 인자를 직접 갱신한다. 이 방식은 양정치성을 자동으로 보존하고 조건수를 절반으로 줄이며, 장시간 동작에서도 수치적 안정성을 유지한다. 시각 관성 주행거리계, 다중 센서 융합, 그리고 SLAM 시스템에서 표준적으로 사용된다.

11.7 그래프 SLAM의 희소 분해

그래프 SLAM의 핵심 계산은 거대한 희소 정보 행렬의 분해이다. 수만 개의 변수와 수십만 개의 측정을 포함하는 문제도 적절한 변수 재정렬과 희소 촐레스키 분해를 통해 효율적으로 해결된다. iSAM2와 같은 점진적 알고리즘은 새로운 측정이 들어올 때 분해 결과를 부분적으로만 갱신하여 실시간 위치 추정과 지도 작성을 가능하게 한다.

11.8 충돌 동역학과 LCP

다물체 시뮬레이션에서의 접촉 처리는 선형 상보성 문제(LCP) 또는 혼합 LCP의 해법을 요구한다. 이러한 문제의 표준 해법인 댄치그 알고리즘과 PGS(투영 가우스-자이델) 방법은 모두 양정치 부분 행렬에 대한 반복적 분해 또는 갱신을 사용한다. 강체 시뮬레이터 라이브러리는 이러한 분해를 효율적으로 구현하여 실시간 물리 시뮬레이션을 제공한다.

11.9 강인 제어기 설계

강인 제어기 설계에서 자주 등장하는 대수적 리카티 방정식과 선형 행렬 부등식은 모두 행렬 분해에 의존한다. 슈어 분해 기반 해밀토니안 방법은 리카티 방정식의 안정적인 해법을 제공하며, 내부점 방법 기반 SDP 해법은 콜레스키 분해를 반복적으로 사용한다. 이러한 도구들은 H-무한대 제어기, 슬라이딩 모드 제어기, 모델 참조 적응 제어기의 설계에 활용된다.

참고문헌

• Golub, G. H., & Van Loan, C. F. (2013). Matrix Computations (4th ed.). Johns Hopkins University Press.
• Trefethen, L. N., & Bau, D. (1997). Numerical Linear Algebra. SIAM.
• Higham, N. J. (2002). Accuracy and Stability of Numerical Algorithms (2nd ed.). SIAM.
• Anderson, E., Bai, Z., Bischof, C., et al. (1999). LAPACK Users’ Guide (3rd ed.). SIAM.
• Davis, T. A. (2006). Direct Methods for Sparse Linear Systems. SIAM.
• Featherstone, R. (2008). Rigid Body Dynamics Algorithms. Springer.
• Siciliano, B., Sciavicco, L., Villani, L., & Oriolo, G. (2009). Robotics: Modelling, Planning and Control. Springer.

Version: 1.0