6.26 가우스 소거법과 후진 대입법

1. 가우스 소거법의 원리

가우스 소거법(Gaussian elimination)은 연립 일차 방정식을 풀이하는 가장 기본적이고 보편적인 알고리즘이며, 행렬을 삼각 형태로 환원하는 것을 핵심으로 한다. 가우스 소거법은 단순히 시스템의 풀이를 넘어, LU 분해, 행렬식 계산, 랭크 결정, 역행렬 계산 등 선형대수학의 많은 알고리즘의 기초가 되는 절차이다. 본 절에서는 가우스 소거법과 후진 대입법의 원리, 알고리즘적 절차, 수치적 고려 사항, 그리고 로봇공학에서의 응용을 체계적으로 다룬다.

2. 가우스 소거법의 두 단계

가우스 소거법은 두 단계로 구성된다.

1단계: 전진 소거(forward elimination). 기본 행 연산을 통해 계수 행렬을 상삼각 행렬로 환원한다.

2단계: 후진 대입(back substitution). 상삼각 시스템을 마지막 미지수부터 역순으로 풀어 모든 미지수의 값을 결정한다.

이 두 단계의 분리는 알고리즘의 명확성과 분석의 용이성을 제공하며, 각 단계의 계산 복잡도와 수치적 거동을 독립적으로 분석할 수 있게 한다.

3. 전진 소거의 절차

연립 일차 방정식 $A\mathbf{x} = \mathbf{b}$ 를 확장 행렬 $[A \mid \mathbf{b}]$ 로 표현한 뒤, 다음의 절차를 따른다.

3.1 알고리즘 6.26.1 (전진 소거).

각 열 $k = 1, 2, \ldots, n-1$ 에 대해 다음을 수행한다.

피벗 선택: $k$ 열에서 $k$ 행 이하의 성분 중 적절한 것을 피벗으로 선택한다.
행 교환: 필요한 경우 피벗 행을 $k$ 행으로 이동한다.
하방 소거: 각 행 $i = k+1, k+2, \ldots, n$ 에 대해

곱셈 인자 계산: $m_{ik} = a_{ik} / a_{kk}$
행 갱신: $R_i \to R_i - m_{ik} R_k$

이 절차가 끝나면 계수 행렬은 상삼각 형태가 되며, 시스템은 다음과 같이 변환된다.

$\begin{bmatrix} u_{11} & u_{12} & u_{13} & \cdots & u_{1n} \\ 0 & u_{22} & u_{23} & \cdots & u_{2n} \\ 0 & 0 & u_{33} & \cdots & u_{3n} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & 0 & \cdots & u_{nn} \end{bmatrix} \begin{bmatrix} x_1 \\ x_2 \\ x_3 \\ \vdots \\ x_n \end{bmatrix} = \begin{bmatrix} c_1 \\ c_2 \\ c_3 \\ \vdots \\ c_n \end{bmatrix}$

여기서 $u_{ii}$ 는 전진 소거 후의 피벗이고, $c_i$ 는 갱신된 우변이다.

후진 대입의 절차

상삼각 시스템 $U \mathbf{x} = \mathbf{c}$ 의 풀이는 마지막 행부터 시작한다.

알고리즘 6.26.2 (후진 대입).

마지막 미지수부터 역순으로:

$x_n = \frac{c_n}{u_{nn}}$

$x_{n-1} = \frac{c_{n-1} - u_{n-1, n} x_n}{u_{n-1, n-1}}$

$\vdots$

$x_i = \frac{c_i - \sum_{j=i+1}^{n} u_{ij} x_j}{u_{ii}}, \quad i = n-1, n-2, \ldots, 1$

각 단계에서 이미 결정된 미지수의 값을 활용하므로 새로운 단계마다 단 하나의 미지수만 결정된다.

계산 예시

다음의 시스템을 가우스 소거법으로 풀어 본다.

$\begin{bmatrix} 2 & 1 & -1 \\ -3 & -1 & 2 \\ -2 & 1 & 2 \end{bmatrix} \begin{bmatrix} x_1 \\ x_2 \\ x_3 \end{bmatrix} = \begin{bmatrix} 8 \\ -11 \\ -3 \end{bmatrix}$

3.2 전진 소거

확장 행렬:

$\left[ \begin{array}{ccc|c} 2 & 1 & -1 & 8 \\ -3 & -1 & 2 & -11 \\ -2 & 1 & 2 & -3 \end{array} \right]$

1열 소거: $m_{21} = -3/2$ , $m_{31} = -1$ .

$R_2 \to R_2 - (-3/2) R_1 = R_2 + (3/2) R_1$ :

$R_3 \to R_3 - (-1) R_1 = R_3 + R_1$ :

$\left[ \begin{array}{ccc|c} 2 & 1 & -1 & 8 \\ 0 & 1/2 & 1/2 & 1 \\ 0 & 2 & 1 & 5 \end{array} \right]$

2열 소거: $m_{32} = 2 / (1/2) = 4$ .

$R_3 \to R_3 - 4 R_2$ :

$\left[ \begin{array}{ccc|c} 2 & 1 & -1 & 8 \\ 0 & 1/2 & 1/2 & 1 \\ 0 & 0 & -1 & 1 \end{array} \right]$

후진 대입

마지막 행으로부터: $-x_3 = 1 \implies x_3 = -1$

두 번째 행: $\frac{1}{2} x_2 + \frac{1}{2} (-1) = 1 \implies x_2 = 3$

첫 번째 행: $2 x_1 + 3 - (-1) = 8 \implies 2 x_1 = 4 \implies x_1 = 2$

따라서 해는 $\mathbf{x} = (2, 3, -1)^\top$ 이다.

알고리즘의 계산 복잡도

전진 소거

$n$ 차 시스템에 대한 전진 소거의 연산량은 다음과 같이 분석된다.

$k$ 번째 열의 소거 단계에서는 $(n-k)$ 개의 행에 대해 각각 $(n-k+1)$ 번의 곱셈 및 덧셈이 수행된다 (피벗 행과의 비교는 $n-k$ 개 성분이지만 우변까지 포함하여 $n-k+1$ 개).
총 곱셈의 수: $\sum_{k=1}^{n-1} (n-k)(n-k+1) \approx \frac{n^3}{3}$

따라서 전진 소거의 복잡도는 $O\left(\frac{n^3}{3}\right)$ 이다.

후진 대입

후진 대입의 $i$ 번째 단계에서는 $(n-i)$ 개의 곱셈과 1개의 나눗셈이 수행된다. 총 곱셈의 수:

$\sum_{i=1}^{n} (n-i) \approx \frac{n^2}{2}$

따라서 후진 대입의 복잡도는 $O(n^2)$ 이다.

3.3 종합

전진 소거가 지배적이므로 가우스 소거법의 총 복잡도는 $O\left(\frac{n^3}{3}\right)$ 이다. 이는 가우스-조르단 소거법( $\sim n^3/2$ )보다 약간 더 효율적이다.

4. 피벗팅 전략

4.1 피벗팅의 필요성

전진 소거의 각 단계에서 피벗이 0이거나 매우 작으면 다음과 같은 문제가 발생한다.

0인 피벗: $m_{ik} = a_{ik} / a_{kk}$ 의 분모가 0이므로 알고리즘이 실패한다.
작은 피벗: 곱셈 인자가 매우 커져 다른 행의 성분이 폭발적으로 증가하며, 이는 부동 소수점 연산에서 큰 오차를 유발한다.

4.2 부분 피벗팅 (Partial Pivoting)

각 단계에서 $k$ 열의 $k$ 행 이하 성분 중 절댓값이 가장 큰 것을 피벗으로 선택하고, 그 행을 $k$ 행과 교환한다.

$\text{argmax}_{i \geq k} |a_{ik}|$

부분 피벗팅은 모든 곱셈 인자 $|m_{ik}| \leq 1$ 임을 보장하여 수치적 안정성을 크게 개선한다.

완전 피벗팅 (Complete Pivoting)

행과 열을 모두 검색하여 가장 큰 절댓값을 가지는 성분을 피벗으로 선택한다.

$\text{argmax}_{i, j \geq k} |a_{ij}|$

완전 피벗팅은 더 우수한 수치 안정성을 제공하지만, 매 단계에서 $(n-k)^2$ 개의 비교를 요구하므로 부분 피벗팅보다 훨씬 비싸다. 실용적으로는 부분 피벗팅이 표준이다.

4.3 스케일된 부분 피벗팅 (Scaled Partial Pivoting)

각 행의 최대 절댓값으로 정규화한 후 부분 피벗팅을 수행한다. 행마다 스케일이 크게 다른 시스템에서 효과적이다.

5. 가우스 소거법의 행렬 분해 해석

가우스 소거법의 본질은 다음의 행렬 분해 (LU 분해)와 동치이다.

$P A = L U$

여기서 $P$ 는 행 교환을 표현하는 순열 행렬, $L$ 은 단위 하삼각 행렬(곱셈 인자를 성분으로 가짐), $U$ 는 상삼각 행렬(전진 소거 후의 결과)이다.

이 분해를 한 번 수행하면, 동일한 $A$ 에 대해 다양한 우변 $\mathbf{b}$ 를 가지는 시스템을 효율적으로 풀 수 있다. 즉, $A\mathbf{x} = \mathbf{b}$ 를 다음의 두 단계로 푼다.

전진 대입으로 $L \mathbf{y} = P \mathbf{b}$ 를 풀어 $\mathbf{y}$ 를 얻는다.
후진 대입으로 $U \mathbf{x} = \mathbf{y}$ 를 풀어 $\mathbf{x}$ 를 얻는다.

각 단계는 $O(n^2)$ 이므로, LU 분해 후의 시스템 풀이는 매우 효율적이다.

수치적 고려 사항

반올림 오차의 누적

가우스 소거법의 각 산술 연산은 부동 소수점 반올림 오차를 누적한다. 부분 피벗팅을 사용하면 일반적으로 수치 안정성이 크게 향상되지만, 병조건 행렬에 대해서는 여전히 큰 오차가 발생할 수 있다.

잔차 검증

해 $\mathbf{x}$ 를 얻은 후 잔차 $\mathbf{r} = \mathbf{b} - A\mathbf{x}$ 를 계산하여 해의 정확도를 평가할 수 있다. 잔차가 큰 경우 반복 정밀화(iterative refinement)를 통해 정확도를 개선할 수 있다.

병조건 시스템

조건수가 큰 시스템에 대해서는 가우스 소거법의 결과가 작은 입력 변화에 매우 민감하다. 이러한 경우 QR 분해나 SVD 기반 풀이가 더 신뢰할 만한 결과를 제공한다.

특수 시스템에 대한 가우스 소거법

대칭 양정치 시스템

대칭 양정치 행렬의 경우 피벗팅 없이 가우스 소거법이 안정적으로 진행되며, 그 결과는 촐레스키 분해 $A = LL^\top$ 과 동치이다. 또한 대칭성으로 인해 연산량이 표준 가우스 소거법의 절반이 된다.

띠 행렬

대각선을 중심으로 좁은 띠에만 비0 성분이 있는 행렬은 가우스 소거법 후에도 띠 구조를 유지하며, 띠 너비 $w$ 에 대해 복잡도가 $O(n w^2)$ 로 줄어든다.

희소 행렬

희소 행렬에 대한 가우스 소거법은 채움 발생을 최소화하는 적절한 변수 순서화와 결합되어 효율적으로 수행된다.

로봇공학에서의 응용

동역학 가속도 계산

매니퓰레이터의 정방향 동역학 $M(\mathbf{q}) \ddot{\mathbf{q}} = \boldsymbol{\tau} - \mathbf{h}$ 에서 가속도 $\ddot{\mathbf{q}}$ 를 구하는 표준적 방법은 가우스 소거법(또는 그 대칭 양정치 변형인 촐레스키 분해)이다. 관성 행렬은 양정치이므로 피벗팅 없이 안정적으로 진행되며, 시뮬레이션의 매 시간 단계에서 수행된다.

역기구학의 반복적 풀이

수치적 역기구학에서 자코비안 기반 갱신 식

$J(\mathbf{q}_k) \Delta \mathbf{q} = \mathbf{e}_k$

는 매 반복마다 풀어야 하는 작은 선형 시스템이며, 가우스 소거법이 직접 적용된다.

5.1 칼만 필터의 갱신

표준 칼만 필터의 갱신 단계에서 측정 잡음 행렬과 사전 공분산이 결합된 행렬

$S = H P^- H^\top + R$

은 일반적으로 작은 대칭 양정치 행렬이며, 이를 풀어 칼만 게인을 결정하는 데 가우스 소거법(또는 촐레스키)이 사용된다.

모델 예측 제어의 QP 풀이

모델 예측 제어에서 매 제어 주기에 풀어야 하는 이차 계획법은 KKT 시스템의 풀이로 환원되며, 그 핵심 단계가 가우스 소거법 기반의 분해이다.

강성 행렬 시스템

유연체 로봇과 유한 요소 모델에서 강성 방정식 $K \mathbf{u} = \mathbf{f}$ 는 일반적으로 큰 희소 시스템이며, 띠 또는 희소 가우스 소거법으로 효율적으로 풀이된다.

캘리브레이션 시스템

로봇 캘리브레이션, 카메라 캘리브레이션, 손-눈 캘리브레이션 등에서 발생하는 작은 또는 중간 크기의 선형 시스템은 가우스 소거법으로 해석된다.

그래프 SLAM의 정규 방정식

그래프 SLAM의 가우스-뉴턴 반복은 매 반복에서 큰 희소 정규 방정식을 풀이하며, 변수 순서화와 결합된 희소 가우스 소거법(또는 촐레스키)이 표준 도구이다.

참고문헌

Strang, G. (2023). Introduction to Linear Algebra (6th ed.). Wellesley-Cambridge Press.
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.

Version: 1.0