6.52 LU 분해와 피벗 선택

1. 도입

LU 분해는 정방 행렬 A \in \mathbb{R}^{n \times n} 을 하삼각 행렬 L 과 상삼각 행렬 U 의 곱으로 표현하는 행렬 분해 기법이다. 가우스 소거법의 행렬적 표현에 해당하며, 선형 연립 방정식 A\mathbf{x} = \mathbf{b} 의 해를 효율적으로 구하기 위한 가장 기본적인 직접법으로 사용된다. 한 번 분해된 L 과 U 는 여러 우변 벡터에 대해 재사용될 수 있어, 동일 계수 행렬에 대한 반복적인 해를 요구하는 로봇 동역학 시뮬레이션과 실시간 제어 분야에서 핵심적인 역할을 수행한다.

2. LU 분해의 정의

행렬 A \in \mathbb{R}^{n \times n} 에 대하여 다음 조건을 만족하는 단위 하삼각 행렬 L 과 상삼각 행렬 U 가 존재할 때, 이 표현을 A 의 LU 분해라 한다.

A = LU

여기서 L 의 대각 원소는 모두 1 이며, L 의 대각선 위쪽 원소와 U 의 대각선 아래쪽 원소는 모두 0 이다. L 의 대각 원소를 1 로 고정하는 정규화 방식을 두리틀(Doolittle) 분해라 하고, U 의 대각 원소를 1 로 고정하는 방식을 크라우트(Crout) 분해라 한다.

3. LU 분해의 존재성과 유일성

행렬 A 의 LU 분해는 항상 존재하지는 않으며, 모든 선행 주 소행렬식(leading principal minor)이 0 이 아닐 때 존재한다.

정리: A \in \mathbb{R}^{n \times n} 의 모든 선행 주 소행렬식 \det(A_k) (k = 1, 2, \dots, n)가 0 이 아니면, A 는 단위 하삼각 행렬 L 과 상삼각 행렬 U 를 사용한 유일한 LU 분해를 갖는다.

여기서 A_k 는 A 의 좌상단 k \times k 부분 행렬을 의미한다. 이 조건이 위배되면 가우스 소거 과정에서 대각 원소가 0 이 되어 소거가 진행되지 않으며, 행 교환이 필수적으로 요구된다.

4. 가우스 소거법과 LU 분해의 관계

LU 분해는 가우스 소거 과정의 행 연산을 행렬 곱으로 기록한 결과이다. 가우스 소거 과정에서 i 번째 행에서 k 번째 행을 \ell_{ik} = a_{ik}^{(k)} / a_{kk}^{(k)} 배 빼는 연산은 기본 행렬 E_{ik} 의 곱으로 표현된다. 모든 소거 단계를 거치면 다음을 얻는다.

E_{n,n-1} \cdots E_{32} E_{31} E_{21} A = U

여기서 모든 E_{ik} 의 역행렬은 \ell_{ik} 의 부호만 반전된 단순한 형태를 가지며, 그 곱은 다음과 같다.

L = E_{21}^{-1} E_{31}^{-1} E_{32}^{-1} \cdots E_{n,n-1}^{-1}

이 L 의 (i,k) 성분은 정확히 소거 과정에서 사용된 승수 \ell_{ik} 와 일치한다. 따라서 가우스 소거 과정의 승수들이 L 의 하삼각 부분을 그대로 채우게 된다.

5. LU 분해의 계산 절차

두리틀 방식의 LU 분해는 다음 점화식으로 직접 계산된다. k = 1, 2, \dots, n 에 대해 다음을 순차적으로 수행한다.

u_{kj} = a_{kj} - \sum_{s=1}^{k-1} \ell_{ks} u_{sj}, \quad j = k, k+1, \dots, n

\ell_{ik} = \frac{1}{u_{kk}} \left( a_{ik} - \sum_{s=1}^{k-1} \ell_{is} u_{sk} \right), \quad i = k+1, k+2, \dots, n

이 과정에서 u_{kk} = 0 이 발생하면 분해가 중단된다. 전체 연산량은 \frac{2}{3}n^3 + O(n^2) 부동소수점 연산에 해당하며, 이는 가우스 소거법과 동일하다.

6. 부분 피벗팅

LU 분해 과정에서 대각 원소 u_{kk} 가 0 이거나 매우 작은 값이 되면 수치적 불안정성이 발생한다. 이를 방지하기 위해 부분 피벗팅(partial pivoting)이 사용된다. k 단계에서 k 열의 k 번째부터 n 번째 행 중 절댓값이 가장 큰 원소를 선택하여 그 행을 k 번째 행과 교환한다.

부분 피벗팅을 포함한 분해는 순열 행렬 P 를 사용하여 다음과 같이 표현된다.

PA = LU

여기서 P 는 모든 행 교환 정보를 누적한 순열 행렬이며, L 의 모든 비대각 원소는 \vert \ell_{ik} \vert \le 1 을 만족한다. 부분 피벗팅이 적용된 LU 분해는 모든 가역 행렬에 대하여 항상 존재한다.

정리: 임의의 가역 행렬 A \in \mathbb{R}^{n \times n} 에 대하여 PA = LU 를 만족하는 순열 행렬 P, 단위 하삼각 행렬 L, 상삼각 행렬 U 가 존재한다.

7. 완전 피벗팅

완전 피벗팅(complete pivoting)은 매 단계에서 잔여 부분 행렬 전체에서 절댓값이 가장 큰 원소를 선택하여 행과 열을 동시에 교환하는 방식이다. 이 경우 두 개의 순열 행렬 P 와 Q 를 사용하여 다음과 같이 표현된다.

PAQ = LU

완전 피벗팅은 부분 피벗팅보다 수치적으로 더욱 안정적이지만, 매 단계에서 O((n-k)^2) 의 비교 연산이 필요하므로 추가 비용이 크다. 실제 구현에서는 부분 피벗팅이 충분한 안정성을 제공하므로 표준적으로 사용된다.

8. 피벗팅 전략의 비교

여기서 락스(rook) 피벗팅은 각 단계에서 행과 열 방향으로 번갈아 가며 최댓값을 탐색하는 절충적 방식이다.

9. 전방 대입과 후방 대입

LU 분해가 완료되면 연립 방정식 A\mathbf{x} = \mathbf{b} 는 다음 두 단계로 해결된다.

먼저 L\mathbf{y} = P\mathbf{b} 를 전방 대입(forward substitution)으로 푼다.

y_i = (P\mathbf{b})_i - \sum_{j=1}^{i-1} \ell_{ij} y_j, \quad i = 1, 2, \dots, n

다음으로 U\mathbf{x} = \mathbf{y} 를 후방 대입(back substitution)으로 푼다.

x_i = \frac{1}{u_{ii}} \left( y_i - \sum_{j=i+1}^{n} u_{ij} x_j \right), \quad i = n, n-1, \dots, 1

각 대입 단계는 n^2 의 연산량을 요구하므로, 동일한 A 에 대해 여러 우변 벡터를 처리할 때 매우 효율적이다.

10. 수치적 안정성과 성장 인자

LU 분해의 수치적 정확도는 성장 인자(growth factor) \rho 에 의해 평가된다. 성장 인자는 다음과 같이 정의된다.

\rho = \frac{\max_{i,j,k} \vert a_{ij}^{(k)} \vert}{\max_{i,j} \vert a_{ij} \vert}

여기서 a_{ij}^{(k)} 는 소거 과정의 k 단계에서의 원소를 의미한다. 부분 피벗팅의 경우 \rho \le 2^{n-1} 이라는 이론적 상한이 존재하지만, 실제로는 거의 모든 경우 \rho 가 작게 유지된다. 윌킨슨(Wilkinson)의 후방 오차 분석에 의하면 부분 피벗팅 LU 분해의 후방 오차는 \rho 에 비례하여 매우 작다.

11. 특수 행렬에 대한 LU 분해

대각 우월 행렬과 대칭 양정치 행렬에 대해서는 피벗팅 없이도 LU 분해가 안정적으로 수행된다.

정리: A 가 엄격 대각 우월 행렬, 즉 \vert a_{ii} \vert > \sum_{j \ne i} \vert a_{ij} \vert 를 모든 i 에 대해 만족하면, 피벗팅 없는 LU 분해가 존재하며 수치적으로 안정하다.

정리: A 가 대칭 양정치 행렬이면, 피벗팅 없는 LU 분해가 존재하며, 이는 촐레스키 분해 A = R^{\top} R 와 동일한 정보를 제공한다.

띠 행렬(banded matrix)에 대해서는 LU 분해가 띠 구조를 보존하므로, 띠 폭이 p 인 행렬에 대한 분해는 O(np^2) 의 연산만으로 가능하다.

12. LU 분해와 행렬식 및 역행렬

LU 분해는 행렬식과 역행렬 계산에도 활용된다. 분해 PA = LU 로부터 다음을 얻는다.

\det(A) = \det(P)^{-1} \prod_{i=1}^{n} u_{ii} = (-1)^{s} \prod_{i=1}^{n} u_{ii}

여기서 s 는 행 교환 횟수이다. 또한 A^{-1} 의 각 열은 A \mathbf{x}_j = \mathbf{e}_j 의 해로 얻을 수 있으며, 이미 분해된 L 과 U 를 사용하여 n 회의 대입 과정만으로 전체 역행렬을 계산할 수 있다.

13. 로봇공학에서의 응용

13.1 동역학 방정식의 가속도 계산

로봇 매니퓰레이터의 정동역학(forward dynamics)은 다음 형태의 운동 방정식을 따른다.

M(q) \ddot{q} = \tau - C(q, \dot{q}) \dot{q} - g(q)

여기서 M(q) 는 관절 공간 관성 행렬이며, 실시간 시뮬레이션에서는 매 적분 단계마다 \ddot{q} 를 구하기 위해 이 연립 방정식을 풀어야 한다. M(q) 는 대칭 양정치 행렬이므로 LU 분해(또는 그 특수한 형태인 촐레스키 분해)를 사용하여 안정적으로 가속도를 계산할 수 있다. 각 시간 단계에서의 \ddot{q} 산출은 LU 분해 후 전방 대입과 후방 대입을 통해 효율적으로 수행된다.

13.2 자코비안 기반 역기구학의 반복 해법

자코비안 의사 역행렬을 사용한 역기구학 알고리즘에서는 다음과 같은 정규 방정식을 반복적으로 풀어야 한다.

(J^{\top} J + \lambda^2 I) \Delta q = J^{\top} \mathbf{e}

좌변의 행렬은 대칭 양정치이므로 LU 분해 또는 촐레스키 분해를 통해 효율적으로 해결된다. 각 반복마다 우변만 변화하는 경우 분해 결과를 재사용함으로써 계산 비용을 크게 줄일 수 있다.

13.3 정적 평형의 힘 분배

다족 보행 로봇의 접촉력 분배 문제와 같이 여러 접촉점에 작용하는 힘을 분배하는 과정에서 다음 형태의 선형 시스템이 발생한다.

G \mathbf{f} = \mathbf{w}_{\text{ext}}

여기서 G 는 그래스프 행렬, \mathbf{f} 는 접촉력 벡터, \mathbf{w}_{\text{ext}} 는 외부 렌치이다. 접촉 형상이 동일하게 유지되는 동안 LU 분해를 한 번만 수행하고 외부 렌치 변화에 따라 재사용하면 실시간 제어 주기 내에서 안정적으로 힘 분배를 산출할 수 있다.

13.4 칼만 필터의 공분산 갱신

상태 추정에 사용되는 칼만 필터에서는 측정 갱신 단계에서 다음과 같은 시스템을 풀어야 한다.

(H P^{-} H^{\top} + R) \mathbf{z} = H \mathbf{x}

이때 좌변의 혁신 공분산은 대칭 양정치 행렬이며, LU 분해를 통해 안정적으로 해결된다. 부분 피벗팅이 적용된 LU 분해는 측정 잡음 공분산이 불량 조건일 경우에도 강건한 결과를 제공한다.

13.5 유한 요소 기반 가요성 로봇 해석

가요성 매니퓰레이터나 연속체 로봇의 유한 요소 모델에서는 강성 행렬 K 가 큰 희소 행렬로 나타난다. 이러한 시스템에서 정적 변형을 구하기 위해 K \mathbf{u} = \mathbf{f} 를 풀어야 하며, 희소 LU 분해와 적절한 행 및 열 재정렬(예: 최소 차수 재정렬)을 결합하면 메모리 사용량과 연산량을 모두 절감할 수 있다.

13.6 모델 예측 제어의 KKT 시스템

모델 예측 제어(MPC)의 내부 루프에서는 카루시-쿤-터커(KKT) 시스템을 반복적으로 풀어야 한다. 이 시스템은 일반적으로 대칭이지만 부정치(indefinite) 형태를 띠므로, 부분 피벗팅이 적용된 LU 분해 또는 그 변형인 부카블로크-카우프만 분해가 사용된다. 매 제어 주기마다 분해를 새로 수행하더라도 작은 차원의 문제에서는 실시간 요구를 충족할 수 있다.

13.7 매개변수 식별의 정규 방정식

로봇의 동역학 매개변수 식별 과정에서는 회귀자 행렬 W 에 대한 정규 방정식이 다음 형태로 등장한다.

(W^{\top} W) \boldsymbol{\theta} = W^{\top} \boldsymbol{\tau}

좌변은 대칭 양정치 행렬이며 LU 분해 또는 촐레스키 분해를 통해 해결된다. 식별 데이터의 양이 많을 경우 정규 방정식의 조건수가 악화될 수 있으므로 부분 피벗팅의 사용이 권장되거나, 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.
• Demmel, J. W. (1997). Applied Numerical Linear Algebra. SIAM.
• Higham, N. J. (2002). Accuracy and Stability of Numerical Algorithms (2nd ed.). 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