Chapter 04

역행렬과 LU 분해

3장에서 가우스 소거로 $A\mathbf{x} = \mathbf{b}$ 를 한 번 풀었습니다. 그런데 공학에서는 같은 $A$ 로 수십, 수천 개의 $\mathbf{b}$ 를 풀어야 할 때가 대부분입니다. 회로 시뮬레이터는 시간 단계마다, 구조 해석 프로그램은 하중 조건마다 새 오른쪽 변을 받습니다. 매번 처음부터 소거할까요, 역행렬을 한 번 구해 두고 곱할까요? 이 장의 답은 둘 다 아닙니다. 소거 과정 자체를 기록해 두면 그 기록이 $A = LU$ 라는 두 삼각 행렬이 되고, 새 $\mathbf{b}$ 는 삼각 행렬 두 개로 순식간에 풉니다. 역행렬은 개념으로는 중요하지만 계산으로는 거의 쓰지 않는다는 것도 이 장에서 분명해집니다.

역행렬을 "변환을 되돌리는 변환"으로 이해하고, 2×2 공식과 $(AB)^{-1} = B^{-1}A^{-1}$ 을 그림으로 설명한다.
가우스–조르당 소거를 $[A \mid I]$ 에 적용해 역행렬을 손으로 구하고, 역행렬이 존재할 동치 조건을 정리한다.
소거의 승수를 모으면 하삼각 행렬 $L$ 이 된다는 것을 보이고, $A = LU$ 와 행 교환을 포함한 $PA = LU$ 를 구한다.
전진 대입과 후진 대입으로 여러 오른쪽 변을 풀고, 역행렬 방식과 연산량·정확도를 비교한다.
$A = LDU$ 와 대칭 행렬의 $A = LDL^{\mathsf T}$ 를 이해하고, 삼중대각 시스템을 $O(n)$ 에 푸는 토머스 알고리즘을 쓴다.
저항 회로의 노드 해석을 $G\mathbf{v} = \mathbf{i}$ 로 세우고 LU로 풀며, 희소 행렬의 채움(fill-in)이 순서에 따라 달라짐을 본다.

이 수식이 없었다면회로 시뮬레이터 SPICE

칩 하나를 만들기 전에 설계자는 수만~수백만 개 소자의 회로를 컴퓨터로 먼저 돌려 봅니다. SPICE 계열 시뮬레이터는 키르히호프 전류 법칙을 노드마다 세워 거대한 연립방정식 $G\mathbf{v} = \mathbf{i}$ 를 만들고, 비선형 소자 때문에 뉴턴 반복을 하고, 과도 해석에서는 그것을 시간 단계마다 되풀이합니다. 한 번의 시뮬레이션이 연립방정식 수십만 번을 푸는 셈입니다.

이것을 가능하게 한 것이 LU 분해, 그중에서도 0이 대부분인 행렬에 맞춘 희소 LU입니다. 행렬의 구조(어느 노드가 어느 노드와 연결되는가)는 반복 내내 같으니, 소거 순서와 채움 위치는 한 번만 정해 두고 숫자만 바꿔 다시 분해합니다. 역행렬을 구했다면 0이던 칸이 모두 채워져 메모리부터 감당할 수 없었을 것입니다.

노드 방정식 Gv = i→매 단계 새로 풀기→A = LU (희소)→삼각 대입 두 번

역행렬은 되돌리기 변환이다

보정한 사진을 원본으로 되돌릴 수 있을까

사진 편집 앱이 이미지에 회전·전단·확대를 섞은 2×2 변환 $A$ 를 적용했습니다. "실행 취소"를 누르면 원래 좌표로 돌아가야 합니다. 변환된 좌표 $\mathbf{y} = A\mathbf{x}$ 에서 $\mathbf{x}$ 를 되찾는 변환이 언제나 있을까요? 있다면 그것도 행렬일까요?

선형 변환을 되돌리는 변환도 선형입니다( $A$ 가 덧셈과 스칼라배를 보존하면 그 역도 보존합니다). 그러니 되돌리기 역시 행렬 하나로 쓸 수 있고, 그것이 역행렬(inverse matrix)입니다.

정의 4.1 (역행렬)

n\times n

행렬

A

에 대해

BA = I

이고

AB = I

인 행렬

B

가 있으면

A

를 가역(invertible) 또는 정칙(nonsingular)이라 하고,

B

를

A^{-1}

로 쓴다. 그런

B

가 없으면

A

는 특이(singular)하다.

역행렬은 있으면 하나뿐입니다. $B$ 와 $C$ 가 모두 역행렬이면 $B = BI = B(AC) = (BA)C = IC = C$ 이기 때문입니다. 정사각 행렬에서는 한쪽만 확인해도 충분하다는 사실( $BA = I$ 이면 자동으로 $AB = I$ )은 3절의 정리에서 나옵니다.

2×2에서는 공식이 바로 나옵니다. 직접 곱해 보면 확인할 수 있습니다.

A = \begin{bmatrix}a & b\\ c & d\end{bmatrix} \quad\Longrightarrow\quad A^{-1} = \frac{1}{ad - bc}\begin{bmatrix}d & -b\\ -c & a\end{bmatrix}\qquad (ad - bc \ne 0)

대각 원소는 자리를 바꾸고, 비대각 원소는 부호를 바꾼 뒤, 행렬식

ad - bc

로 나눈다. 행렬식이 0이면 나눌 수 없다. 그림으로는 평면이 직선으로 납작해져 어디서 왔는지 알 수 없게 된 경우다.

그림 4-1. 역행렬은 변환을 되돌린다. 곱

AB

는 오른쪽

B

가 먼저 적용되므로, 되돌릴 때는 나중에 한

A

부터 되돌린다. 그래서 곱의 역행렬은 순서가 뒤집힌다.

정리 4.1 (곱과 전치의 역행렬)

A

B

가 가역이면

AB

도 가역이고

(AB)^{-1} = B^{-1}A^{-1}

이다. 또

(A^{\mathsf T})^{-1} = (A^{-1})^{\mathsf T}

이다.
증명:

(AB)(B^{-1}A^{-1}) = A(BB^{-1})A^{-1} = AA^{-1} = I

이고 반대 순서도 같다. 전치는

A^{\mathsf T}(A^{-1})^{\mathsf T} = (A^{-1}A)^{\mathsf T} = I^{\mathsf T} = I

에서 나온다.

SIMULATOR

변환하고 되돌리기: A와 A⁻¹

Aî, Aĵ 끝점을 끌어 보세요

보기

프리셋

A와 A⁻¹

det A = ad − bc—

det A⁻¹ = 1/det A—

상태—

해볼 것: ① 'A⁻¹A'를 누르면 변환한 F가 정확히 원래 자리로 돌아옵니다. ② '거의 특이'를 고르고 'A⁻¹ 적용'을 보세요. A가 평면을 얇게 누를수록 A⁻¹은 반대로 크게 부풀려야 합니다. 측정 잡음이 있으면 이 부풀림이 잡음을 키웁니다. ③ 두 점을 원점을 지나는 한 직선 위에 놓으면 역행렬이 사라집니다. 모델: 원점을 고정하는 2×2 선형 변환, 끈 점은 0.1 단위로 맞춰집니다.

가우스–조르당: [A | I]를 [I | A⁻¹]로

3×3 이상은 공식이 없을까

2×2 공식은 외우기 쉽지만, 3×3 공식(여인수 공식, 10장)은 항이 많고 4×4 이상은 손으로 쓸 엄두가 나지 않습니다. 소거를 이미 알고 있으니 그것으로 역행렬을 구할 수는 없을까요?

$AX = I$ 를 만족하는 $X$ 를 찾는 것은 $X$ 의 열 $\mathbf{x}_1, \dots, \mathbf{x}_n$ 에 대해 $n$ 개의 연립방정식 $A\mathbf{x}_j = \mathbf{e}_j$ 를 푸는 것과 같습니다. 계수 행렬이 모두 $A$ 로 같으니 오른쪽 변 $n$ 개를 한꺼번에 붙여 소거하면 됩니다. 이것이 가우스–조르당 소거(Gauss–Jordan elimination)입니다.

앞으로 소거: 피벗 아래를 0으로 만든다(3장의 가우스 소거와 같다).
뒤로 소거: 피벗 위도 0으로 만든다. 왼쪽이 대각 행렬이 된다.
피벗으로 나누기: 각 행을 피벗으로 나눠 왼쪽을 $I$ 로 만든다. 그때 오른쪽이 $A^{-1}$ 이다.

왜 오른쪽이 $A^{-1}$ 일까요? 각 행 연산은 왼쪽에 기본 행렬 $E$ 를 곱하는 것입니다. 연산을 모두 모은 $M = E_k\cdots E_2E_1$ 이 $MA = I$ 를 만들었다면 $M = A^{-1}$ 이고, 같은 연산을 받은 오른쪽은 $MI = M = A^{-1}$ 입니다.

예제 4.1 — 손으로 푸는 2×2

A = \begin{bmatrix}2 & 1\\ 5 & 3\end{bmatrix}

의 역행렬.

\left[\begin{array}{cc|cc}2 & 1 & 1 & 0\\ 5 & 3 & 0 & 1\end{array}\right] \xrightarrow{R_2 - 2.5R_1} \left[\begin{array}{cc|cc}2 & 1 & 1 & 0\\ 0 & 0.5 & -2.5 & 1\end{array}\right] \xrightarrow{R_1 - 2R_2} \left[\begin{array}{cc|cc}2 & 0 & 6 & -2\\ 0 & 0.5 & -2.5 & 1\end{array}\right] \xrightarrow{R_1/2,\;2R_2} \left[\begin{array}{cc|cc}1 & 0 & 3 & -1\\ 0 & 1 & -5 & 2\end{array}\right]

따라서

A^{-1} = \begin{bmatrix}3 & -1\\ -5 & 2\end{bmatrix}

. 2×2 공식(

\det A = 6 - 5 = 1

)과 같고,

AA^{-1} = I

도 곱해 보면 확인된다.

SIMULATOR

가우스–조르당 단계별 실행기

—

행렬

단계—

지금까지 곱셈·나눗셈—

결과—

해볼 것: ① 3×3 행렬을 끝까지 실행해 오른쪽 블록이 A⁻¹이 되는 것을 보세요. 마지막 단계에서 AA⁻¹ = I도 검산합니다. ② '피벗 자리가 0'은 첫 단계에서 행을 바꿉니다. ③ '특이 행렬'은 세 번째 피벗을 찾지 못하고 멈춥니다. 모델: 정확한 유리수 대신 배정밀도 실수로 계산하고 소수 셋째 자리까지 보여 줍니다. 피벗은 맨 위의 0이 아닌 원소를 씁니다.

역행렬이 있을 조건, 그리고 왜 거의 계산하지 않는가

가우스–조르당이 멈추는 경우는 딱 하나, 어떤 열에서 피벗 후보가 모두 0일 때입니다. 이 관찰 하나가 서로 달라 보이는 여러 조건을 한 줄로 묶습니다.

정리 4.2 (가역 행렬 정리)

n\times n

행렬

A

에 대해 다음은 모두 동치다.

$A$ 는 가역이다.
소거(필요하면 행 교환 포함)가 0이 아닌 피벗 $n$ 개를 낸다.
$A\mathbf{x} = \mathbf{0}$ 의 해는 $\mathbf{x} = \mathbf{0}$ 뿐이다.
$A$ 의 열들은 선형 독립이다(1장 벡터와 선형 결합).
모든 $\mathbf{b}$ 에 대해 $A\mathbf{x} = \mathbf{b}$ 의 해가 정확히 하나 있다.
$A$ 는 기본 행렬들의 곱이다.
$\det A \ne 0$ 이다(10장에서 증명).
$BA = I$ 인 $B$ 가 있다(또는 $AB = I$ 인 $B$ 가 있다).

핵심 고리: 피벗이

n

개면 가우스–조르당이 끝까지 가서 역행렬을 만든다(1⇔2). 피벗이 모자라면 자유 변수가 생겨

A\mathbf{x} = \mathbf{0}

에 0 아닌 해가 생긴다(2⇔3). 열의 선형 결합이 0이 되는 것이 바로

A\mathbf{x} = \mathbf{0}

의 0 아닌 해다(3⇔4).

BA = I

이면

A\mathbf{x} = \mathbf{0}

에서

\mathbf{x} = BA\mathbf{x} = \mathbf{0}

이니 3이 성립하고, 그러면

A^{-1}

이 있으므로

B = BAA^{-1} = A^{-1}

이다(8). 그래서 정사각 행렬은 한쪽 역행렬만 확인하면 된다.

이론에서 역행렬은 이렇게 강력하지만, 수치 계산에서는 한 가지 원칙이 거의 철칙처럼 쓰입니다.

$A\mathbf{x} = \mathbf{b}$ 를 풀 때 $A^{-1}$ 을 만들지 않는다

\mathbf{x} = A^{-1}\mathbf{b}

는 식으로는 깔끔하지만, 계산으로는 손해입니다.

연산량: $n\times n$ 역행렬을 구하는 데 곱셈·덧셈이 약 $2n^3$ 회 필요합니다. LU 분해는 약 $\tfrac{2}{3}n^3$ 회로, 세 배 적습니다. 그 뒤 $\mathbf{b}$ 하나를 푸는 비용은 둘 다 약 $2n^2$ 으로 같습니다.
정확도: 역행렬을 거치면 반올림 오차가 한 단계 더 쌓이고, LU와 삼각 대입으로 푼 해보다 잔차 $\lVert A\mathbf{x} - \mathbf{b}\rVert$ 가 대체로 더 큽니다. 후진 안정성(16장) 보장도 약해집니다.
희소성: 희소 행렬의 역행렬은 거의 언제나 꽉 찬 행렬입니다(7절). 0이 99.9%인 백만 차원 행렬의 역행렬은 메모리에 담을 수조차 없습니다.

그래서 MATLAB의 A\b, NumPy의 numpy.linalg.solve, LAPACK의 dgesv는 모두 역행렬이 아니라 LU 분해로 풉니다. 역행렬 자체가 필요한 경우(공분산 행렬의 대각 원소처럼

A^{-1}

의 성분이 답인 경우)는 생각보다 드뭅니다.

A = LU: 소거의 기록

소거를 매번 다시 해야 할까

구조물의 강성 행렬 $K$ 는 그대로인데 하중 벡터 $\mathbf{f}$ 만 바람·지진·적설 조건마다 바뀝니다. 가우스 소거는 $K$ 와 $\mathbf{f}$ 를 함께 바꿔 가며 풀므로, $\mathbf{f}$ 가 바뀌면 $\tfrac{2}{3}n^3$ 짜리 소거를 처음부터 다시 해야 합니다. $K$ 에 대해 한 일은 어딘가에 남겨 둘 수 없을까요?

남겨 둘 것은 많지 않습니다. 소거의 각 단계는 " $i$ 행에서 $k$ 행의 $\ell_{ik}$ 배를 뺀다"였고, 이 승수(multiplier) $\ell_{ik} = u_{ik}/u_{kk}$ 만 기억하면 $A$ 에 한 일을 $\mathbf{b}$ 에도 언제든 똑같이 해 줄 수 있습니다. 승수를 대각선 아래에 모으면 하삼각 행렬이 됩니다.

A = LU,\qquad L = \begin{bmatrix}1 & & & \\ \ell_{21} & 1 & & \\ \ell_{31} & \ell_{32} & 1 & \\ \vdots & & \ddots & \ddots\end{bmatrix},\qquad U = \text{소거가 끝난 위삼각 행렬}

L

은 대각이 1인 하삼각 행렬(단위 하삼각)이고 대각 아래에 승수가 그 자리 그대로 들어간다.

U

의 대각 원소가 피벗이다. 승수를 부호까지 그대로 적는다는 것(빼 준 양 = 더해야 원래로 돌아오는 양)이 요점이다.

왜 승수가 "그 자리 그대로" 들어갈까요? 소거 단계 하나는 기본 행렬 $E_{ik}$ (단위 행렬의 $(i,k)$ 칸에 $-\ell_{ik}$ )를 곱하는 것이고, 모두 모으면 $E\,A = U$ 입니다. 그러면 $A = E^{-1}U$ 이고 $L = E^{-1}$ 입니다. $E_{ik}^{-1}$ 은 $(i,k)$ 칸의 부호만 바꾼 것(뺀 것을 다시 더하기)이며, 역순으로 곱하면 서로 간섭하지 않아 승수들이 자기 칸에 그대로 놓입니다. 반면 $E$ 자체에는 승수끼리 곱한 항이 섞여 들어갑니다. 그래서 $E$ 가 아니라 $L = E^{-1}$ 을 기록하는 것이 깔끔합니다.

그림 4-2. 예제 4.2의 분해. 소거하며 쓴 승수(주황)를 같은 자리에 적으면

L

, 소거가 끝난 결과가

U

(피벗은 보라). 컴퓨터는

L

과

U

를 따로 저장하지 않고

A

의 칸에 덮어쓴다.

L

의 대각 1은 적을 필요가 없기 때문이다.

예제 4.2 — 3×3 LU 분해

A = \begin{bmatrix}2 & 1 & 1\\ 4 & 5 & 3\\ -2 & 2 & 5\end{bmatrix}

1열: 피벗 2. $\ell_{21} = 4/2 = 2$ 이므로 $R_2 - 2R_1 = (0, 3, 1)$ . $\ell_{31} = -2/2 = -1$ 이므로 $R_3 - (-1)R_1 = (0, 3, 6)$ .
2열: 피벗 3. $\ell_{32} = 3/3 = 1$ 이므로 $R_3 - R_2 = (0, 0, 5)$ .
결과: $L = \begin{bmatrix}1 & 0 & 0\\ 2 & 1 & 0\\ -1 & 1 & 1\end{bmatrix}$ , $U = \begin{bmatrix}2 & 1 & 1\\ 0 & 3 & 1\\ 0 & 0 & 5\end{bmatrix}$ . 검산: $L$ 의 3행 $(-1, 1, 1)$ 은 " $U$ 의 1행 $-1$ 배 + 2행 + 3행" $= (-2, 2, 5)$ 으로 $A$ 의 3행과 같다.

SIMULATOR

L이 채워지고 U가 만들어진다

—

행렬 부분 피벗팅 (PA = LU)

단계—

최대 |승수|—

검산 max|PA − LU|—

해볼 것: ① 예제 4.2를 한 단계씩 실행하며 승수가 L의 어느 칸에 들어가는지 확인하세요. ② '2열 피벗 자리가 0'은 피벗팅 없이는 멈춥니다. 부분 피벗팅을 켜면 행을 바꾸고 P가 기록됩니다. ③ '아주 작은 피벗'에서 피벗팅을 끄면 승수가 10⁴까지 커지고, 켜면 모든 |승수| ≤ 1이 됩니다. 모델: 배정밀도 계산, 표시는 소수 셋째 자리. 부분 피벗팅은 각 열에서 절댓값이 가장 큰 원소를 피벗으로 고릅니다.

행 교환이 필요할 때: PA = LU

피벗 자리에 0이 오면 아래 행과 바꿔야 합니다(3장의 부분 피벗팅). 0이 아니어도 아주 작은 피벗은 거대한 승수를 낳고 반올림 오차를 키우므로, 실무에서는 매 열마다 절댓값이 가장 큰 원소를 피벗으로 올립니다. 그러면 모든 승수가 $|\ell_{ik}| \le 1$ 이 됩니다.

행 교환을 섞으면 $A = LU$ 가 그대로 성립하지 않습니다. 대신 바꿀 행을 미리 다 바꿔 둔 행렬 $PA$ 에 대해 교환 없는 소거를 한 것과 결과가 같습니다. $P$ 는 단위 행렬의 행 순서를 바꾼 치환 행렬(permutation matrix)입니다.

정리 4.3 (PA = LU) 모든 가역 행렬

A

에 대해 치환 행렬

P

, 단위 하삼각 행렬

L

, 대각에 0이 없는 위삼각 행렬

U

가 있어

PA = LU

이다. 행 교환이 일어나면 이미 계산한

L

의 승수들도 같이 바꿔 준다(행 전체가 이사를 가니, 그 행의 기록도 따라간다).

P^{-1} = P^{\mathsf T}

이므로

A = P^{\mathsf T}LU

로도 쓴다.

$PA = LU$ 로 $A\mathbf{x} = \mathbf{b}$ 를 풀 때는 양변에 $P$ 를 곱해 $LU\mathbf{x} = P\mathbf{b}$ 로 바꾸면 됩니다. $P\mathbf{b}$ 는 곱셈이 아니라 원소의 순서를 바꾸는 것이라 비용이 거의 없습니다. 한편 피벗팅 없이도 언제나 안전한 행렬들이 있습니다. 대각 지배 행렬(각 행에서 대각 원소의 절댓값이 나머지 절댓값의 합보다 큰 행렬)과 대칭 양의 정부호 행렬(13장)이 그렇고, 다음 절들의 열전도 행렬과 회로 행렬이 바로 이 경우입니다.

한 번 분해해 여러 번 풀기

$A = LU$ 가 있으면 $A\mathbf{x} = \mathbf{b}$ 는 $L(U\mathbf{x}) = \mathbf{b}$ 입니다. $\mathbf{c} = U\mathbf{x}$ 로 두면 삼각 시스템 두 개로 쪼개집니다.

\underbrace{L\mathbf{c} = \mathbf{b}}_{\text{전진 대입: } c_1, c_2, \dots \text{ 순서}}\qquad\text{그다음}\qquad \underbrace{U\mathbf{x} = \mathbf{c}}_{\text{후진 대입: } x_n, x_{n-1}, \dots \text{ 순서}}

전진 대입

c_i = b_i - \sum_{j \lt i} \ell_{ij}c_j

, 후진 대입

x_i = \big(c_i - \sum_{j > i} u_{ij}x_j\big)/u_{ii}

. 각각 약

n^2

번의 곱셈·덧셈. 전진 대입은 가우스 소거가

\mathbf{b}

에 하던 일을 나중에 따로 해 주는 것이다.

예제 4.3 — 예제 4.2의 분해로 풀기

\mathbf{b} = (5, 17, 7)

전진 대입 $L\mathbf{c} = \mathbf{b}$ : $c_1 = 5$ , $c_2 = 17 - 2\cdot 5 = 7$ , $c_3 = 7 - (-1)\cdot 5 - 1\cdot 7 = 5$ .
후진 대입 $U\mathbf{x} = \mathbf{c}$ : $x_3 = 5/5 = 1$ , $x_2 = (7 - 1\cdot 1)/3 = 2$ , $x_1 = (5 - 1\cdot 2 - 1\cdot 1)/2 = 1$ .
답 $\mathbf{x} = (1, 2, 1)$ . 새 $\mathbf{b}$ 가 오면 1–2만 반복한다. $L$ 과 $U$ 는 그대로다.

연산량을 비교하면 차이가 분명합니다. 오른쪽 변이 $k$ 개일 때 대략

방법	한 번만 하는 일	오른쪽 변 하나마다	$k$ 개 전체
매번 가우스 소거	—	$\tfrac{2}{3}n^3 + n^2$	$k\cdot\tfrac{2}{3}n^3$
역행렬을 구해 곱하기	$2n^3$	$2n^2$	$2n^3 + 2kn^2$
LU 분해 + 대입	$\tfrac{2}{3}n^3$	$2n^2$	$\tfrac{2}{3}n^3 + 2kn^2$

LU는 역행렬 방식보다 언제나 앞서고(분해가 세 배 싸고 그 뒤는 같다), 매번 소거하는 방식과는 $k$ 가 커질수록 격차가 벌어집니다. 아래에서 $n$ 과 $k$ 를 바꿔 보세요.

SIMULATOR

연산량 비교: 소거·역행렬·LU

오른쪽 변 개수 k 행렬 크기 n (읽기용) 컴퓨터 속도

매번 소거—

역행렬 + 곱—

LU + 대입—

LU가 빠른 배수 (매번 소거 대비)—

해볼 것: ① k = 1이면 역행렬 방식이 LU보다 약 세 배 느립니다. ② k를 n보다 크게 하면 대입 비용 2kn²이 분해 비용을 넘어서고, 역행렬과 LU의 차이는 줄지만 LU가 여전히 앞섭니다. ③ n = 10⁴, k = 100이면 매번 소거하는 방식은 LU보다 약 100배 느립니다. 모델: 곱셈·덧셈 횟수(flop)의 주요 항만 셉니다. 실제 속도는 메모리 접근과 병렬화에 크게 좌우되며, 시간은 지정한 일정 속도를 가정한 어림입니다.

A = LDU와 대칭 행렬의 A = LDLᵀ

$A = LU$ 는 비대칭입니다. $L$ 의 대각은 1인데 $U$ 의 대각은 피벗입니다. 피벗을 대각 행렬 $D$ 로 뽑아내면 양쪽이 대칭적인 모양이 됩니다.

A = LDU',\qquad D = \operatorname{diag}(u_{11}, \dots, u_{nn}),\qquad U' = D^{-1}U \;(\text{대각이 1인 위삼각})

예제 4.2에서는 $D = \operatorname{diag}(2, 3, 5)$ , $U' = \begin{bmatrix}1 & 0.5 & 0.5\\ 0 & 1 & 1/3\\ 0 & 0 & 1\end{bmatrix}$ 입니다. 이 분해는 피벗팅이 필요 없는 가역 행렬에서 유일합니다.

$A$ 가 대칭( $A = A^{\mathsf T}$ )이면 더 좋은 일이 생깁니다. $A = LDU'$ 를 전치하면 $A^{\mathsf T} = U'^{\mathsf T}DL^{\mathsf T}$ 이고, 이것도 "단위 하삼각 · 대각 · 단위 위삼각" 꼴이니 유일성에 의해 $U' = L^{\mathsf T}$ 입니다.

정리 4.4 (대칭 행렬의 LDLᵀ) 행 교환 없이 소거되는 대칭 행렬은

A = LDL^{\mathsf T}

로 분해된다.

L

만 계산하면 되므로 연산량과 저장 공간이

LU

의 절반(약

\tfrac{1}{3}n^3

)이다. 피벗(

D

의 원소)이 모두 양수이면

A

는 양의 정부호이고,

\sqrt{D}

를 나눠 담아

A = (L\sqrt{D})(L\sqrt{D})^{\mathsf T} = R^{\mathsf T}R

로 쓸 수 있다. 이것이 콜레스키 분해이며 13장에서 자세히 다룬다.

예제 4.4

A = \begin{bmatrix}4 & 2 & 2\\ 2 & 5 & 3\\ 2 & 3 & 6\end{bmatrix}

. 승수

\ell_{21} = \ell_{31} = 0.5

로 1열을 지우면 남은 블록은

\begin{bmatrix}4 & 2\\ 2 & 5\end{bmatrix}

이고(여전히 대칭!),

\ell_{32} = 0.5

로 지우면 마지막 피벗 4가 남는다. 따라서

L = \begin{bmatrix}1 & 0 & 0\\ 0.5 & 1 & 0\\ 0.5 & 0.5 & 1\end{bmatrix},\quad D = \operatorname{diag}(4, 4, 4),\quad A = LDL^{\mathsf T}.

소거 도중의 남은 블록이 계속 대칭이라는 것이

L^{\mathsf T}

만으로

U

를 대신할 수 있는 이유다.

띠 행렬: 열전도 막대를 O(n)에 풀기

칩의 방열판을 따라 온도는 어떻게 분포할까

길이 1인 막대의 양 끝 온도를 고정하고 막대 안에서 열이 발생한다고 합시다. 정상 상태 온도 $T(x)$ 는 $-kT''(x) = q(x)$ 를 만족합니다. 막대를 $n$ 개 내부 점으로 나누고 2계 도함수를 차분 $T'' \approx (T_{i-1} - 2T_i + T_{i+1})/h^2$ 으로 바꾸면 $n$ 원 연립방정식이 됩니다. 정확하게 풀려면 $n$ 을 크게 해야 하는데, $n = 10^6$ 이면 $\tfrac{2}{3}n^3 \approx 7\times 10^{17}$ 번의 연산이 필요할까요?

각 점의 방정식은 양옆 이웃만 포함하므로 행렬은 대각과 바로 위·아래 대각에만 원소가 있는 삼중대각 행렬(tridiagonal matrix)입니다.

\frac{k}{h^2}\begin{bmatrix}2 & -1 & & & \\ -1 & 2 & -1 & & \\ & \ddots & \ddots & \ddots & \\ & & -1 & 2 & -1\\ & & & -1 & 2\end{bmatrix}\begin{bmatrix}T_1\\ T_2\\ \vdots\\ T_{n-1}\\ T_n\end{bmatrix} = \begin{bmatrix}q_1 + kT_L/h^2\\ q_2\\ \vdots\\ q_{n-1}\\ q_n + kT_R/h^2\end{bmatrix}

h = 1/(n+1)

. 양 끝의 고정 온도

T_L

T_R

는 알고 있는 값이므로 오른쪽 변으로 넘어간다. 이 행렬은 대칭이고 양의 정부호라 피벗팅이 필요 없다.

소거를 해 보면 놀라운 일이 생깁니다. 1행으로 지울 것은 2행 하나뿐이고, 지운 뒤에도 0이던 칸은 0으로 남습니다. 즉 $L$ 은 대각 바로 아래 한 줄, $U$ 는 대각과 바로 위 한 줄뿐입니다. 이 사실을 이용한 소거와 대입이 토머스 알고리즘(Thomas algorithm)입니다. 행마다 상수 번의 연산(약 8회)만 하므로 전체 비용은 $O(n)$ 입니다.

정리 4.5 (띠 행렬의 LU)

A

의 원소가

|i - j| \le w

인 칸에만 있으면(반띠폭

w

) 행 교환 없는 LU에서

L

과

U

도 같은 띠 안에만 원소를 가진다. 연산량은 약

2nw^2

, 저장 공간은 약

3nw

이다. 삼중대각(

w = 1

)이면

O(n)

이다.

SIMULATOR

열전도 막대: 토머스 알고리즘으로 푸는 온도 분포

내부 점 개수 n 왼쪽 끝 온도 오른쪽 끝 온도 발열 세기 q/k

발열 분포

최고 온도—

토머스 연산량 ≈ 8n—

꽉 찬 LU ≈ ⅔n³—

해석해와 최대 차이 (균일 발열)—

해볼 것: ① n을 200까지 올려도 계산은 즉시 끝납니다. 꽉 찬 LU였다면 연산량이 n²/12, 약 3,300배 많고, n = 10⁶이면 그 차이가 10¹¹배에 이릅니다. ② 균일 발열에서는 해석해

T = T_L + (T_R - T_L)x + \tfrac{q}{2k}x(1-x)

와 차이가 반올림 수준입니다(2차 다항식에는 중앙 차분이 정확하기 때문). ③ '가운데 칩'은 폭 0.1 구간에만 열이 나서 온도가 뾰족해집니다. 모델: 1차원 정상 열전도, 균일 열전도율, 양 끝 디리클레 조건, 2차 중앙 차분.

2차원·3차원 격자에서는 이웃이 위아래 행에도 있어서 띠가 넓어지고, 띠 안의 0이던 칸이 소거 중에 채워집니다. 이 채움(fill-in)의 양은 미지수의 순서에 따라 크게 달라집니다. 극단적인 예가 "허브" 노드 하나가 모두와 연결된 화살표 모양 행렬입니다.

SIMULATOR

희소 LU의 채움: 순서가 메모리를 정한다

A의 0 아닌 칸

L + U (주황 = 채움)

구조와 순서

A의 0 아닌 칸—

L + U의 0 아닌 칸—

채움—

해볼 것: ① '허브 먼저'는 같은 행렬인데도 첫 소거에서 모든 칸이 채워집니다. ② '허브 나중'은 허브를 마지막 번호로 옮겼을 뿐인데 채움이 0입니다. ③ 2D 격자는 띠 안이 채워집니다. 실제 희소 솔버는 최소 차수(AMD), 중첩 분할(nested dissection) 같은 재번호 매기기로 채움을 줄입니다. 모델: 숫자 상쇄를 무시한 기호적 채움(구조만 봄), 행 교환 없음.

응용: 저항 회로의 노드 해석

저항 여섯 개와 전류원 하나, 각 노드의 전압은

아래 회로에서 전류원이 1번 노드로 전류를 밀어 넣습니다. 저항 값을 바꿀 때마다 모든 노드의 전압과 각 저항의 전류를 알고 싶습니다. 고리마다 전압 방정식을 세울 수도 있지만, 컴퓨터가 체계적으로 세우기 좋은 방법은 따로 있습니다.

노드 해석(nodal analysis)은 접지(0번)를 기준으로 각 노드 전압 $v_i$ 를 미지수로 두고, 노드마다 키르히호프 전류 법칙(나가는 전류의 합 = 들어오는 전원 전류)을 씁니다. 노드 $i$ 와 $j$ 사이 컨덕턴스 $g = 1/R$ 을 지나는 전류는 $g(v_i - v_j)$ 이므로, 방정식을 모으면

G\mathbf{v} = \mathbf{i},\qquad G_{ii} = \sum_{\text{노드 } i\text{에 붙은 저항}} g,\qquad G_{ij} = -g_{ij}\;(i \ne j)

G

는 컨덕턴스 행렬,

\mathbf{i}

는 각 노드로 들어오는 전원 전류. 저항 하나는

G

의 네 칸

(i,i), (j,j), (i,j), (j,i)

에

+g, +g, -g, -g

를 더한다(스탬프). 접지에 붙은 저항은

(i,i)

에만

+g

. 그래서

G

는 대칭이고, 접지로 가는 길이 있으면 양의 정부호다.

그림 4-3. 시뮬레이터의 회로. 노드 ①–③과 접지 사이에 저항 여섯 개, ①로 들어가는 전류원

I

. 노드 수가 미지수 수이고, 저항이

G

에 스탬프를 찍는다.

예제 4.5 — 모든 저항이 1 kΩ, I = 3 mA

g = 1

mS로 두면

G = \begin{bmatrix}3 & -1 & -1\\ -1 & 3 & -1\\ -1 & -1 & 3\end{bmatrix}\text{ mS},\qquad \mathbf{i} = \begin{bmatrix}3\\ 0\\ 0\end{bmatrix}\text{ mA}.

소거:

\ell_{21} = \ell_{31} = -1/3

, 남은 블록

\begin{bmatrix}8/3 & -4/3\\ -4/3 & 8/3\end{bmatrix}

\ell_{32} = -1/2

, 마지막 피벗

2

. 전진 대입

\mathbf{c} = (3, 1, 1.5)

, 후진 대입

v_3 = 0.75

v_2 = (1 + \tfrac43\cdot 0.75)/\tfrac83 = 0.75

v_1 = (3 + 0.75 + 0.75)/3 = 1.5

V. 대칭인 회로라 ②와 ③의 전압이 같다는 것도 확인된다.

SIMULATOR

노드 해석기: 저항을 바꾸면 G와 전압이 바뀐다

전류원 I R₂ (①–②) R₄ (②–③) R₅ (③–접지) R₆ (①–③)

G (mS), 분해 결과

v₁—

v₂—

v₃—

KCL 검산: 접지로 가는 전류 합—

해볼 것: ① 처음 상태(모두 1 kΩ, 3 mA)가 예제 4.5입니다. ② R₆을 0.1 kΩ 쪽으로 낮추면 ①과 ③이 거의 같은 전압이 되고 G의 (1,3) 칸이 커집니다. ③ R₅를 크게 하면 ③의 전류는 ②를 돌아 접지로 갑니다. 접지로 가는 전류의 합은 언제나 I와 같습니다. 모델: 슬라이더는 로그 눈금(0.1–100 kΩ), R₁ = R₃ = 1 kΩ 고정, 이상적인 선형 저항과 직류 전류원.

실제 회로 시뮬레이터는 전압원·인덕터·트랜지스터까지 다루기 위해 미지수에 일부 전류를 더한 수정 노드 해석(modified nodal analysis)을 쓰고, 그 행렬은 대칭이 아니어서 피벗팅이 있는 희소 LU로 풉니다. 하지만 "부품마다 스탬프를 찍어 행렬을 만들고 LU로 푼다"는 뼈대는 위 시뮬레이터와 같습니다.

이 도구가 쓰이는 곳

"한 번 분해해 여러 번 푼다"는 수치 계산의 기본기라, 연립방정식이 나오는 거의 모든 곳에 숨어 있습니다.

ANALOGBOOK회로 시뮬레이션
SPICE의 노드 해석, 동작점과 과도 해석, 뉴턴 반복마다 희소 LU. TCADBOOK소자·공정 시뮬레이션
포아송·드리프트–확산 방정식의 이산화는 거대한 희소 띠 행렬이다. MATHBOOK열확산 방정식
암시적 시간 적분은 매 단계 같은 삼중대각 행렬을 푼다. 분해는 한 번이면 된다. MATHBOOK수치 해석
유한 차분과 안정성, 반올림 오차가 쌓이는 방식. 확률과 통계회귀 분석
정규 방정식 XᵀXβ = Xᵀy는 대칭 양의 정부호라 LDLᵀ·콜레스키로 푼다. PACKAGINGBOOK열 해석
패키지 열저항망은 회로와 같은 꼴의 G·T = P 방정식이다.

핵심 정리

역행렬은 되돌리기 변환이다. 2×2는 $\tfrac{1}{ad-bc}\begin{bmatrix}d & -b\\ -c & a\end{bmatrix}$ , 곱의 역행렬은 순서가 뒤집혀 $(AB)^{-1} = B^{-1}A^{-1}$ .
가우스–조르당: $[A \mid I]$ 를 행 연산으로 $[I \mid A^{-1}]$ 로 만든다. 행 연산을 모은 행렬이 곧 $A^{-1}$ 이다.
가역 행렬 정리: 피벗 $n$ 개 ⇔ $A\mathbf{x} = \mathbf{0}$ 의 해는 0뿐 ⇔ 열이 독립 ⇔ 모든 $\mathbf{b}$ 에 해가 하나 ⇔ $\det A \ne 0$ . 정사각 행렬은 한쪽 역행렬이면 충분하다.
$A\mathbf{x} = \mathbf{b}$ 를 풀 때 역행렬을 만들지 않는다. 역행렬은 $2n^3$ , LU는 $\tfrac23 n^3$ 이고, 정확도와 희소성에서도 LU가 낫다.
$A = LU$ : $L$ 은 승수를 제자리에 적은 단위 하삼각, $U$ 는 소거 결과. 행 교환이 있으면 $PA = LU$ , 부분 피벗팅은 $|\ell_{ik}| \le 1$ 을 보장한다.
분해 뒤에는 전진 대입 $L\mathbf{c} = \mathbf{b}$ 과 후진 대입 $U\mathbf{x} = \mathbf{c}$ , 오른쪽 변 하나에 $2n^2$ .
대칭 행렬은 $A = LDL^{\mathsf T}$ (비용 절반), 피벗이 모두 양수면 콜레스키로 이어진다. 띠 행렬은 LU도 띠 안에 머물러 삼중대각은 $O(n)$ (토머스 알고리즘). 일반 희소 행렬은 순서에 따라 채움이 크게 달라진다.

확인 퀴즈

Q1. $A$ 와 $B$ 가 가역일 때 $(AB)^{-1}$ 은?

AB

는

B

를 먼저,

A

를 나중에 적용한다. 되돌릴 때는 나중 것부터:

(AB)(B^{-1}A^{-1}) = AIA^{-1} = I

. 행렬 곱은 일반적으로 교환되지 않으므로

A^{-1}B^{-1}

과는 보통 다르다.

Q2. $\begin{bmatrix}3 & 1\\ 5 & 2\end{bmatrix}^{-1}$ 은?

\det = 3\cdot 2 - 1\cdot 5 = 1

. 대각은 자리를 바꾸고 비대각은 부호를 바꾼 뒤 1로 나눈다. 원래 행렬과 곱하면

I

가 나온다.

Q3. 4×4 행렬 $A$ 에 대해 $A\mathbf{x} = \mathbf{0}$ 이 $\mathbf{x} = (1, -2, 0, 1)$ 이라는 해를 가진다. 옳은 것은?

A\mathbf{x}

는 열들의 선형 결합이므로

1\cdot\mathbf{a}_1 - 2\mathbf{a}_2 + 0\cdot\mathbf{a}_3 + 1\cdot\mathbf{a}_4 = \mathbf{0}

, 즉 열이 종속이다. 가역 행렬 정리에 의해 특이하다. 이때

A\mathbf{x} = \mathbf{b}

는

\mathbf{b}

에 따라 해가 없거나 무수히 많다(모든

\mathbf{b}

에 해가 있는 것은 아니다).

Q4. 소거에서 $R_2 - 3R_1$ , $R_3 + 2R_1$ , $R_3 - 4R_2$ 를 했다(행 교환 없음). $L$ 의 대각 아래 $(\ell_{21}, \ell_{31}, \ell_{32})$ 는?

R_i - \ell_{ik}R_k

의

\ell_{ik}

가 그대로

L

의

(i,k)

칸에 들어간다.

R_3 + 2R_1

은

R_3 - (-2)R_1

이므로

\ell_{31} = -2

. 승수가 섞이는 것은

L

이 아니라

E = L^{-1}

쪽이다.

Q5. 같은 $1000\times 1000$ 행렬로 오른쪽 변 10개를 풀어야 한다. 가장 연산이 적은 방법은?

대략 소거 10번

\approx 6.7\times 10^9

, 역행렬

2\times 10^9 + 2\times 10^7

, LU

6.7\times 10^8 + 2\times 10^7

. 크라메르 공식은 행렬식을

n+1

개 계산해야 해서 훨씬 비싸다(10장).

Q6. 부분 피벗팅을 하는 주된 이유는?

작은 피벗은 거대한 승수를 만들고, 큰 승수는 반올림 오차를 그만큼 키운다. 행 교환은 행렬식의 부호를 바꾸며(10장), 연산량은 여전히

\tfrac23 n^3

이다.

Q7. $n$ 개 내부 점의 1차원 열전도 문제(삼중대각)를 토머스 알고리즘으로 풀 때 연산량은 어떻게 늘어나나?

삼중대각 행렬의

L

과

U

는 띠 밖으로 채워지지 않으므로 행마다 상수 번(약 8회)의 연산만 한다.

n = 10^6

도 순식간에 풀린다.

Q8. 저항 회로의 컨덕턴스 행렬 $G$ 에 대해 옳지 않은 것은?

A

에서 0인 칸도 소거 중에 채워질 수 있다(채움). 얼마나 채워지는지는 노드 번호 순서에 달려 있으며, 희소 솔버가 재번호 매기기를 하는 이유다. 나머지는 모두 참이다.