6.152 수치 선형대수학의 개요와 중요성

로봇 시스템에서 다루는 거의 모든 계산 문제는 궁극적으로 선형 시스템의 풀이, 고유값 분해, 행렬 분해 등의 선형대수 연산으로 귀결된다. 수치 선형대수학(numerical linear algebra)은 이러한 연산을 유한 정밀도(finite precision) 컴퓨터에서 효율적이고 정확하게 수행하는 알고리즘과 이론을 다루는 분야이다. 본 절에서는 수치 선형대수학의 핵심 개념과 로봇공학에서의 중요성을 개관한다.

1. 수치 선형대수학의 범위

수치 선형대수학이 다루는 주요 문제는 다음과 같다.

문제 유형	수학적 표현	로봇공학 응용
선형 시스템 풀이	$A\mathbf{x} = \mathbf{b}$	역기구학, 상태 추정
최소 제곱 문제	$\min \lVert A\mathbf{x} - \mathbf{b} \rVert$	캘리브레이션, 궤적 최적화
고유값 문제	$A\mathbf{x} = \lambda \mathbf{x}$	안정성 분석, PCA
특이값 분해	$A = U\Sigma V^\top$	자세 추정, 차원 축소
행렬 분해	$A = LU$ , $A = QR$ , $A = LL^\top$	실시간 필터, 최적화

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

컴퓨터는 실수를 유한 자릿수의 부동 소수점(floating point)으로 표현한다. IEEE 754 배정밀도(double precision) 표준에서 실수 $x$ 는 다음과 같이 표현된다.

$\text{fl}(x) = \pm m \times 2^e$

여기서 $m$ 은 52비트 가수(mantissa), $e$ 는 11비트 지수(exponent)이다. 기계 엡실론(machine epsilon) $\epsilon_{\text{mach}}$ 는 $1 + \epsilon_{\text{mach}} \neq 1$ 을 만족하는 가장 작은 양수로, 배정밀도에서 다음과 같다.

$\epsilon_{\text{mach}} = 2^{-52} \approx 2.22 \times 10^{-16}$

부동 소수점 연산에서 실수 $x$ 의 표현 오차는 다음을 만족한다.

$\frac{\vert \text{fl}(x) - x \vert}{\vert x \vert} \leq \epsilon_{\text{mach}}$

산술 연산의 결과에도 유사한 상대 오차가 발생한다.

$\text{fl}(a \odot b) = (a \odot b)(1 + \delta), \quad \vert \delta \vert \leq \epsilon_{\text{mach}}$

여기서 $\odot$ 은 $+, -, \times, \div$ 중 하나이다.

3. 조건 수와 문제의 민감도

수치 문제의 민감도(sensitivity)를 정량화하는 핵심 개념이 조건 수(condition number)이다. 선형 시스템 $A\mathbf{x} = \mathbf{b}$ 에서 $A$ 의 조건 수는 다음과 같이 정의된다.

$\kappa(A) = \lVert A \rVert \lVert A^{-1} \rVert$

2-노름을 사용하는 경우, 조건 수는 최대 특이값과 최소 특이값의 비이다.

$\kappa_2(A) = \frac{\sigma_{\max}}{\sigma_{\min}}$

조건 수의 의미는 다음과 같다. $\mathbf{b}$ 에 상대 오차 $\delta \mathbf{b}$ 가 존재할 때, 해 $\mathbf{x}$ 의 상대 오차는 다음의 상한을 가진다.

$\frac{\lVert \delta \mathbf{x} \rVert}{\lVert \mathbf{x} \rVert} \leq \kappa(A) \frac{\lVert \delta \mathbf{b} \rVert}{\lVert \mathbf{b} \rVert}$

$A$ 자체에도 오차 $\delta A$ 가 있는 경우에는 다음이 성립한다.

$\frac{\lVert \delta \mathbf{x} \rVert}{\lVert \mathbf{x} \rVert} \leq \kappa(A) \left( \frac{\lVert \delta A \rVert}{\lVert A \rVert} + \frac{\lVert \delta \mathbf{b} \rVert}{\lVert \mathbf{b} \rVert} \right) + O(\kappa^2 \epsilon)$

$\kappa(A)$	해석	유효 자릿수 손실
$\sim 1$	매우 잘 조건화됨	0
$\sim 10^3$	양호	약 3자리
$\sim 10^8$	나쁘게 조건화됨	약 8자리
$\sim 10^{16}$	특이에 가까움	거의 모든 자릿수

4. 전진 오차와 후진 오차

수치 알고리즘의 정확도를 평가하는 두 가지 관점이 있다.

전진 오차(forward error): 계산된 해 $\hat{\mathbf{x}}$ 와 정확한 해 $\mathbf{x}$ 의 차이이다.

$\text{forward error} = \lVert \hat{\mathbf{x}} - \mathbf{x} \rVert$

후진 오차(backward error): 계산된 해 $\hat{\mathbf{x}}$ 가 어떤 섭동된 문제의 정확한 해가 되는 최소 섭동의 크기이다.

$\text{backward error} = \min \left\{ \lVert \delta A \rVert : (A + \delta A) \hat{\mathbf{x}} = \mathbf{b} \right\}$

두 오차의 관계는 다음과 같다.

$\text{forward error} \leq \kappa(A) \times \text{backward error}$

후진 안정(backward stable) 알고리즘은 후진 오차가 $O(\epsilon_{\text{mach}})$ 인 알고리즘이다. 후진 안정한 알고리즘을 잘 조건화된 문제에 적용하면, 전진 오차도 $O(\epsilon_{\text{mach}})$ 수준이 된다.

5. 핵심 행렬 분해

수치 선형대수학에서 가장 중요한 행렬 분해와 그 특성을 요약하면 다음과 같다.

5.1 LU 분해

정사각 행렬 $A \in \mathbb{R}^{n \times n}$ 을 하삼각 행렬 $L$ 과 상삼각 행렬 $U$ 의 곱으로 분해한다.

$PA = LU$

여기서 $P$ 는 부분 피벗팅(partial pivoting)을 위한 치환 행렬이다. 계산 복잡도는 $O(\frac{2}{3}n^3)$ 이며, 선형 시스템 $A\mathbf{x} = \mathbf{b}$ 를 효율적으로 풀 수 있다.

5.2 QR 분해

$A \in \mathbb{R}^{m \times n}$ ( $m \geq n$ )을 직교 행렬 $Q$ 와 상삼각 행렬 $R$ 로 분해한다.

$A = QR$

하우스홀더 반사(Householder reflection)를 이용한 QR 분해는 후진 안정하며, 계산 복잡도는 $O(2mn^2 - \frac{2}{3}n^3)$ 이다. 최소 제곱 문제에서 정규 방정식보다 수치적으로 안정적이다.

5.3 촐레스키 분해

대칭 양정치 행렬 $A$ 를 하삼각 행렬 $L$ 의 곱으로 분해한다.

$A = LL^\top$

계산 복잡도는 $O(\frac{1}{3}n^3)$ 으로, LU 분해의 절반이다. 칼만 필터의 공분산 행렬 갱신과 배치 추정의 정보 행렬 풀이에 핵심적으로 사용된다.

5.4 특이값 분해(SVD)

$A \in \mathbb{R}^{m \times n}$ 을 다음과 같이 분해한다.

$A = U \Sigma V^\top$

여기서 $U \in \mathbb{R}^{m \times m}$ 와 $V \in \mathbb{R}^{n \times n}$ 은 직교 행렬이고, $\Sigma \in \mathbb{R}^{m \times n}$ 은 특이값을 대각에 가지는 행렬이다. SVD는 최소 제곱 문제, 랭크 결정, 의사 역행렬(pseudoinverse) 계산, 행렬 근사 등에 사용되는 가장 범용적인 분해이다. 계산 복잡도는 $O(\min(mn^2, m^2 n))$ 이다.

5.5 고유값 분해

대칭 행렬 $A \in \mathbb{R}^{n \times n}$ 의 고유값 분해는 다음과 같다.

$A = Q \Lambda Q^\top$

여기서 $Q$ 는 고유 벡터로 구성된 직교 행렬, $\Lambda$ 는 고유값의 대각 행렬이다. 비대칭 행렬의 경우에는 슈어 분해(Schur decomposition)를 사용한다.

$A = Q T Q^\top$

여기서 $T$ 는 상삼각 행렬이다.

6. 반복법과 직접법

선형 시스템 풀이 방법은 크게 직접법(direct method)과 반복법(iterative method)으로 분류된다.

특성	직접법	반복법
대표 알고리즘	LU, QR, 촐레스키	켤레 기울기(CG), GMRES
계산 복잡도	$O(n^3)$ (밀집), $O(n)$ (희소, 대역)	반복당 $O(n)$ (희소)
메모리	$O(n^2)$ (밀집)	$O(n)$ (희소)
정확도	기계 정밀도	반복 횟수에 의존
적합한 경우	소규모-중규모, 밀집 행렬	대규모, 희소 행렬

로봇공학에서 실시간 상태 추정은 대부분 소규모-중규모 시스템( $n < 100$ )이므로 직접법이 적합하지만, 대규모 SLAM이나 번들 조정에서는 반복법이 효율적이다.

7. 희소 행렬 연산

로봇 상태 추정에서 발생하는 행렬(정보 행렬, 야코비 행렬 등)은 대부분 희소(sparse) 구조를 가진다. 희소 행렬의 비영 요소 수가 $\text{nnz}$ 일 때, 희소 행렬-벡터 곱의 복잡도는 $O(\text{nnz})$ 이다.

희소 촐레스키 분해에서는 채움(fill-in) 현상이 발생한다. 원래 행렬에서 영이었던 위치에 분해 후 비영 요소가 나타나는 것이다. 채움을 최소화하기 위해 변수 순서를 최적화하는 방법이 사용된다.

근사 최소 차수(Approximate Minimum Degree, AMD) 순서화는 채움을 효과적으로 줄이는 대표적인 방법이다. 그래프 기반 SLAM에서 정보 행렬의 변수 순서를 AMD로 최적화하면, 분해 시간과 메모리 사용량을 크게 줄일 수 있다.

8. 수치 안정성의 로봇공학 응용

수치 선형대수학의 원리가 로봇공학에서 직접적으로 중요한 대표적인 사례를 정리하면 다음과 같다.

칼만 필터의 수치 안정성: 표준 칼만 필터에서 공분산 행렬 $P$ 의 갱신 과정은 수치 오차의 축적에 의해 $P$ 의 양정치성을 잃을 수 있다. 제곱근 필터(square root filter)는 $P = SS^\top$ 을 유지하면서 $S$ 를 직접 갱신하여 양정치성을 보장한다. 이는 촐레스키 분해를 칼만 필터에 통합한 것이다.

정규 방정식 vs QR 분해: 최소 제곱 문제 $\min \lVert A\mathbf{x} - \mathbf{b} \rVert$ 를 정규 방정식 $A^\top A \mathbf{x} = A^\top \mathbf{b}$ 로 푸는 경우, 조건 수가 $\kappa(A^\top A) = \kappa(A)^2$ 로 제곱된다. QR 분해를 사용하면 $\kappa(A)$ 수준의 조건 수로 풀 수 있으므로, 수치적으로 더 안정적이다.

의사 역행렬과 특이 시스템: 로봇 팔의 야코비 행렬이 특이 배치(singular configuration)에 가까울 때, 통상적인 역행렬 대신 특이값 분해 기반의 의사 역행렬을 사용한다.

$A^+ = V \Sigma^+ U^\top$

여기서 $\Sigma^+$ 는 $\sigma_i > \epsilon$ ( $\epsilon$ 은 적절한 임계값)인 특이값의 역수만 취하고 나머지는 0으로 설정한 것이다. 이를 잘린 SVD(truncated SVD)라 하며, 감쇠 최소 제곱(damped least squares)과 함께 특이점 근방에서의 수치 안정성을 보장한다.

$\mathbf{x} = \sum_{\sigma_i > \epsilon} \frac{\mathbf{u}_i^\top \mathbf{b}}{\sigma_i} \mathbf{v}_i$

9. 계산 복잡도 요약

연산	밀집 행렬 복잡도	비고
행렬-벡터 곱 ( $A\mathbf{x}$ )	$O(n^2)$	희소: $O(\text{nnz})$
행렬-행렬 곱 ( $AB$ )	$O(n^3)$	Strassen: $O(n^{2.807})$
LU 분해	$O(\frac{2}{3}n^3)$	피벗팅 포함
QR 분해	$O(\frac{4}{3}n^3)$	하우스홀더 반사
촐레스키 분해	$O(\frac{1}{3}n^3)$	대칭 양정치 한정
SVD	$O(4n^3)$	전체 분해 기준
고유값 분해	$O(10n^3)$	QR 알고리즘

로봇 시스템에서 실시간 성능이 요구되는 경우, 문제의 구조(대칭성, 양정치성, 희소성, 대역 구조 등)를 최대한 활용하여 적절한 분해 방법과 알고리즘을 선택하는 것이 필수적이다.

참고 문헌

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.
Strang, G. (2019). Linear Algebra and Its Applications (5th ed.). Cengage Learning.
Barfoot, T. D. (2017). State Estimation for Robotics. Cambridge University Press.

v 0.1