Kwangmin Kim - Ch.2 §2.6 — Elimination = Factorization: A = LU

1 이 절이 다루는 것

§2.3에서 소거법의 각 단계를 소거 행렬 \(E_{ij}\) 로 표현했다.

\[ E_{32} E_{31} E_{21} A = U \]

이 절은 여기서 한 걸음 더 나아간다. \(E\) 들을 반대편으로 옮기면 \(A\) 를 두 행렬의 곱 \(LU\) 로 분해할 수 있다. 이것이 선형대수에서 가장 중요한 분해인 \(A = LU\) 분해이다.

노트

§2.6의 핵심 질문

\(A = LU\) 의 \(L\) 은 어디서 오는가?
왜 \(L\) 에 소거 승수 \(\ell_{ij}\) 가 그대로 들어가는가?
\(A = LU\) 를 알면 \(Ax = b\) 를 어떻게 더 효율적으로 푸는가?
소거의 연산량은 얼마인가?

2 \(A = LU\) 의 유도

2.1 2×2 예시로 시작

\(A\) 에서 \(U\) 로 가는 소거:

\[ E_{21} A = \begin{bmatrix} 1 & 0 \\ -3 & 1 \end{bmatrix} \begin{bmatrix} 2 & 1 \\ 6 & 8 \end{bmatrix} = \begin{bmatrix} 2 & 1 \\ 0 & 5 \end{bmatrix} = U \]

승수 \(\ell_{21} = 6/2 = 3\). \(E_{21}\) 의 \((2,1)\) 위치에 \(-3\) 이 들어간다.

이제 양변의 왼쪽에 \(E_{21}^{-1}\) 을 곱한다.

\[ A = E_{21}^{-1} U = \begin{bmatrix} 1 & 0 \\ 3 & 1 \end{bmatrix} \begin{bmatrix} 2 & 1 \\ 0 & 5 \end{bmatrix} = \begin{bmatrix} 2 & 1 \\ 6 & 8 \end{bmatrix} = A \checkmark \]

\(E_{21}^{-1}\) 이 \(L\) 이다. \(L\) 은 소거를 “되돌리는” 행렬 — \(E_{21}\) 이 “빼기”였다면 \(L\) 은 “더하기”이다.

\[ \boxed{A = LU, \quad L = E_{21}^{-1} = \begin{bmatrix} 1 & 0 \\ 3 & 1 \end{bmatrix}} \]

직관: \(U \to A\) 로 가는 과정이 \(L\) 이다. 소거가 앞방향(\(A \to U\))이라면, \(L\) 은 역방향(\(U \to A\))이다.

2.2 3×3 일반화

\(3 \times 3\) 행렬의 소거 전체:

\[ (E_{32} E_{31} E_{21}) A = U \]

\(A\) 를 왼변으로 옮기면:

\[ A = E_{21}^{-1} E_{31}^{-1} E_{32}^{-1} \cdot U = LU \]

중요

순서 주의: \(E\) 들이 \(A\) 에 적용된 순서(\(E_{21} \to E_{31} \to E_{32}\))와, 역행렬들이 \(U\) 앞에 붙는 순서(\(E_{21}^{-1}, E_{31}^{-1}, E_{32}^{-1}\))는 반대이다.

\((ABC)^{-1} = C^{-1}B^{-1}A^{-1}\) — 역행렬은 역순으로 곱한다.

2.3 \(L\) 의 구조

각 소거 행렬의 역행렬은 하삼각 행렬이다.

\[ E_{21}^{-1} = \begin{bmatrix} 1 & 0 & 0 \\ \ell_{21} & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix},\quad E_{31}^{-1} = \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ \ell_{31} & 0 & 1 \end{bmatrix},\quad E_{32}^{-1} = \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & \ell_{32} & 1 \end{bmatrix} \]

세 역행렬을 곱하면 (§2.4 예시에서 검증했듯):

\[ L = E_{21}^{-1} E_{31}^{-1} E_{32}^{-1} = \begin{bmatrix} 1 & 0 & 0 \\ \ell_{21} & 1 & 0 \\ \ell_{31} & \ell_{32} & 1 \end{bmatrix} \]

승수들이 정확히 자신의 위치에 들어간다.

3 왜 승수들이 \(L\) 에 간섭 없이 들어가는가

이것이 \(A = LU\) 에서 가장 놀라운 사실이다. 보통 행렬을 곱하면 원소들이 뒤섞이는데, 여기서는 그렇지 않다.

3.1 핵심 이유: 피벗 행은 \(U\) 의 행이다

소거 3행을 계산할 때의 실제 연산을 추적한다.

\[ (\text{Row 3 of } U) = (\text{Row 3 of } A) - \ell_{31}(\text{Row 1 of } U) - \ell_{32}(\text{Row 2 of } U) \]

중요한 점: 3행에서 빼는 것은 \(A\) 의 행이 아니라 \(U\) 의 행이다. 소거 중에 1행과 2행은 이미 고정되어 \(U\) 의 1행, 2행이 되었다. 이 행들은 이후 변하지 않는다.

이 식을 재배열하면:

\[ (\text{Row 3 of } A) = \ell_{31}(\text{Row 1 of } U) + \ell_{32}(\text{Row 2 of } U) + 1 \cdot (\text{Row 3 of } U) \]

이것이 \(A = LU\) 의 3행이다. \(L\) 의 3행은 \([\ell_{31}, \ell_{32}, 1]\) 이다. 모든 행이 이 패턴을 따른다.

직관: 소거가 진행될수록 사용된 피벗 행들은 “확정”되어 \(U\) 에 보존된다. 후속 소거는 이미 확정된 \(U\) 의 행들을 빼기 때문에, 각 승수 \(\ell_{ij}\) 는 독립적으로 자신의 자리를 차지한다. 서로 “방해”하지 않는다.

3.2 구체적 수치 예시

§2.2~2.3에서 사용한 3×3 행렬:

\[ A = \begin{bmatrix} 2 & 4 & -2 \\ 4 & 9 & -3 \\ -2 & -3 & 7 \end{bmatrix} \]

소거 단계별 승수: - \(\ell_{21} = 4/2 = 2\) (2행에서 1행의 2배 뺌) - \(\ell_{31} = -2/2 = -1\) (3행에서 1행의 \((-1)\) 배 뺌 = 1행을 더함) - \(\ell_{32} = 1/1 = 1\) (3행에서 2행의 1배 뺌)

\[ L = \begin{bmatrix} 1 & 0 & 0 \\ 2 & 1 & 0 \\ -1 & 1 & 1 \end{bmatrix}, \quad U = \begin{bmatrix} 2 & 4 & -2 \\ 0 & 1 & 1 \\ 0 & 0 & 4 \end{bmatrix} \]

검증:

\[ LU = \begin{bmatrix} 1 & 0 & 0 \\ 2 & 1 & 0 \\ -1 & 1 & 1 \end{bmatrix} \begin{bmatrix} 2 & 4 & -2 \\ 0 & 1 & 1 \\ 0 & 0 & 4 \end{bmatrix} = \begin{bmatrix} 2 & 4 & -2 \\ 4 & 9 & -3 \\ -2 & -3 & 7 \end{bmatrix} = A \checkmark \]

4 \(L\) 의 성질 정리

노트

\(A = LU\) 분해의 구조 (행 교환 없는 경우)

\(L\): 하삼각 행렬(Lower Triangular) — 대각선 아래에 소거 승수 \(\ell_{ij}\), 대각선은 모두 1.
\(U\): 상삼각 행렬(Upper Triangular) — 대각선에 피벗, 대각선 위에 소거 결과.
조건: \(A\) 의 모든 피벗이 0이 아닐 때 (행 교환 불필요).

추가 관찰: - \(A\) 의 행이 0으로 시작하면 \(L\) 의 해당 행도 0으로 시작한다 (소거 불필요). - \(A\) 의 열이 0으로 시작하면 \(U\) 의 해당 열도 0으로 시작한다. - 중간에 있는 0들은 소거 과정에서 채워질 수 있다 (fill-in).

5 \(A = LDU\) 변형 — 더 대칭적인 분해

\(L\) 의 대각선은 모두 1이지만, \(U\) 의 대각선은 피벗이다. 이 비대칭을 해소하려면 \(U\) 에서 피벗을 뽑아 대각 행렬 \(D\) 를 만든다.

피벗 \(d_1, d_2, \ldots, d_n\) 을 대각에 갖는 행렬 \(D\):

\[ U = D \cdot \tilde{U} \]

여기서 \(\tilde{U}\) 는 \(U\) 의 각 행을 해당 피벗으로 나눈 것 — 대각선이 모두 1인 상삼각 행렬이다.

\[ A = L \cdot D \cdot \tilde{U} = LDU \]

2×2 예시:

\[ A = \begin{bmatrix} 1 & 0 \\ 3 & 1 \end{bmatrix} \begin{bmatrix} 2 & 8 \\ 0 & 5 \end{bmatrix} = \underbrace{\begin{bmatrix} 1 & 0 \\ 3 & 1 \end{bmatrix}}_{L} \underbrace{\begin{bmatrix} 2 & 0 \\ 0 & 5 \end{bmatrix}}_{D} \underbrace{\begin{bmatrix} 1 & 4 \\ 0 & 1 \end{bmatrix}}_{\tilde{U}} \]

\(LDU\) 의 의미: \(L\) 과 \(\tilde{U}\) 가 대칭적으로 대각선 1을 갖는다. \(A\) 가 대칭 행렬이면 \(\tilde{U} = L^\top\) 이 성립한다(§4에서 다룸).

6 \(Ax = b\) 를 두 삼각 시스템으로 풀기

\(A = LU\) 를 알면 \(Ax = b\) 를 효율적으로 풀 수 있다.

\[ Ax = b \implies LUx = b \]

\(Ux = c\) 로 놓으면 두 단계로 분리된다.

중요

두 단계 풀이

전진 소거(Forward): \(Lc = b\) 풀기 — 위에서 아래로 (전방 대입)
후방 대입(Backward): \(Ux = c\) 풀기 — 아래에서 위로 (후방 대입)

6.1 왜 두 단계로 나누는가?

\(A = LU\) 를 한 번만 계산해 두면, 우변 \(b\) 가 달라져도 \(L, U\) 를 다시 계산할 필요가 없다.

실용적 의미: 공학·과학 계산에서 같은 행렬 \(A\) 에 여러 우변 \(b_1, b_2, \ldots\) 를 푸는 경우가 흔하다. \(A = LU\) 분해를 한 번 하고(\(O(n^3)\)), 각 우변에 두 삼각 풀이를 적용(\(O(n^2)\))하면 훨씬 효율적이다.

6.2 전진 소거: \(Lc = b\)

\(L\) 의 대각선이 모두 1이므로 위에서 아래로 순차 계산한다.

\[ L = \begin{bmatrix} 1 & 0 & 0 \\ \ell_{21} & 1 & 0 \\ \ell_{31} & \ell_{32} & 1 \end{bmatrix},\quad b = \begin{bmatrix} b_1 \\ b_2 \\ b_3 \end{bmatrix} \]

\[ c_1 = b_1 \] \[ c_2 = b_2 - \ell_{21} c_1 \] \[ c_3 = b_3 - \ell_{31} c_1 - \ell_{32} c_2 \]

직관: 이것은 소거를 우변 \(b\) 에도 적용하는 것이다. \(L\) 에 저장된 승수들을 꺼내 \(b\) 를 \(c\) 로 변환한다.

6.3 후방 대입: \(Ux = c\)

\(U\) 의 대각선에 피벗이 있으므로 아래에서 위로 계산한다.

\[ U = \begin{bmatrix} u_{11} & u_{12} & u_{13} \\ 0 & u_{22} & u_{23} \\ 0 & 0 & u_{33} \end{bmatrix},\quad c = \begin{bmatrix} c_1 \\ c_2 \\ c_3 \end{bmatrix} \]

\[ x_3 = c_3 / u_{33} \] \[ x_2 = (c_2 - u_{23} x_3) / u_{22} \] \[ x_1 = (c_1 - u_{12} x_2 - u_{13} x_3) / u_{11} \]

6.4 구체적 예시

\[ A = \begin{bmatrix} 1 & 2 \\ 4 & 9 \end{bmatrix} = \begin{bmatrix} 1 & 0 \\ 4 & 1 \end{bmatrix}\begin{bmatrix} 1 & 2 \\ 0 & 1 \end{bmatrix} = LU \]

\(b = (5, 21)^\top\) 로 \(Ax = b\) 풀기.

Step 1 — \(Lc = b\):

\[ c_1 = 5, \quad c_2 = 21 - 4 \cdot 5 = 1 \implies c = \begin{bmatrix} 5 \\ 1 \end{bmatrix} \]

Step 2 — \(Ux = c\):

\[ x_2 = 1/1 = 1, \quad x_1 = (5 - 2 \cdot 1)/1 = 3 \implies x = \begin{bmatrix} 3 \\ 1 \end{bmatrix} \]

검증: \(Ax = (1 \cdot 3 + 2 \cdot 1, 4 \cdot 3 + 9 \cdot 1) = (5, 21) = b \checkmark\)

7 연산량 분석

7.1 분해 단계 (Factor): \(A \to LU\)

소거는 열 1부터 열 \(n-1\) 까지 순서대로 진행된다. \(k\) 번째 열 소거는 \((n-k) \times (n-k)\) 행렬 부분에 작용한다.

\[ \text{총 곱셈 수} \approx n^2 + (n-1)^2 + \cdots + 2^2 + 1^2 = \sum_{k=1}^{n} k^2 \approx \frac{1}{3}n^3 \]

\[ \boxed{A \to LU \text{ 분해 연산량}: \frac{1}{3}n^3 \text{ 곱셈} + \frac{1}{3}n^3 \text{ 뺄셈}} \]

직관: 소거가 진행될수록 작용하는 행렬이 작아진다. \(n \times n\) 에서 시작해 \((n-1) \times (n-1)\), \(\ldots\), \(1 \times 1\) 까지. 크기의 제곱합이 \(\frac{1}{3}n^3\) 에 가깝다.

7.2 풀이 단계 (Solve): \(Lc = b\), \(Ux = c\)

각 삼각 시스템 풀이는 \(n\) 개의 행 각각에 대해 점점 늘어나는 수의 계산이 필요하다.

\[ \text{전진 소거} (L c = b): \quad 0 + 1 + 2 + \cdots + (n-1) = \frac{n(n-1)}{2} \approx \frac{n^2}{2} \]

\[ \text{후방 대입} (U x = c): \quad n + (n-1) + \cdots + 1 = \frac{n(n+1)}{2} \approx \frac{n^2}{2} \]

\[ \boxed{Ax = b \text{ 풀이 연산량 (LU 알 때)}: n^2 \text{ 곱셈}} \]

7.3 분해 vs 풀이 비교

단계	연산량
\(A \to LU\) 분해	\(\approx \frac{1}{3}n^3\)
\(Ax = b\) 풀이 (LU 사용)	\(\approx n^2\)
\(Ax = b\) 풀이 (\(k\) 번째 우변)	\(\approx k \cdot n^2\) (분해 1회 + 풀이 \(k\) 회)

\(n = 1000\) 이면 분해는 \(\approx 3 \times 10^8\) 연산이지만, LU를 알면 각 새 우변은 \(\approx 10^6\) 연산만 필요하다. 분해가 압도적으로 비싸고, 풀이는 저렴하다.

7.4 대역 행렬(Band Matrix)의 연산량 절감

대역폭(bandwidth) \(w\) 인 대역 행렬은 주대각선에서 \(w\) 개 이하의 대각선에만 0이 아닌 원소가 있다. 이 0들은 소거 후에도 \(L\) 과 \(U\) 에서 0으로 유지된다 (fill-in 없음).

\[ \text{대역 행렬 분해}: \frac{1}{3}n^3 \to nw^2 \]

\[ \text{대역 행렬 풀이}: n^2 \to 2nw \]

삼대각 행렬(\(w = 1\)): 분해 \(O(n)\), 풀이 \(O(n)\) — 선형 시간.

8 직관: 왜 \(A = LU\) 가 중요한가

힌트

\(A = LU\) 는 “분해 후 재사용” 패러다임이다

Factor once (비쌈, \(O(n^3)\)): \(A\) 를 \(L\) 과 \(U\) 로 분해.
Solve many (저렴, \(O(n^2)\) each): 새 \(b\) 마다 \(Lc = b\), \(Ux = c\) 만 풀면 됨.

이것은 LAPACK 같은 수치 선형대수 라이브러리의 핵심 설계 철학이다. LAPACK 문서에 따르면 “이 상황은 너무 흔하고 절감이 너무 중요해서, 단일 시스템을 하나의 서브루틴으로 푸는 기능은 제공하지 않는다.”

\(L\) 과 \(U\) 에 담긴 정보:

\(U\): 소거가 완료된 상삼각 행렬 — 피벗들이 대각선에 있다. 행렬의 “계수”와 “가역성” 정보를 담는다.
\(L\): 소거의 “기록지” — 어떤 행에서 어떤 배수를 뺐는지 기록. 새 우변 \(b\) 가 오면 \(L\) 을 꺼내 같은 연산을 \(b\) 에 재적용한다.

9 Worked Examples

9.1 예시 1: 3×3 완전 분해

\[ A = \begin{bmatrix} 2 & 1 & 0 \\ 1 & 2 & 1 \\ 0 & 1 & 2 \end{bmatrix} \]

Step 1 — \(E_{21}\) 적용 (\(\ell_{21} = 1/2\)):

\[ \begin{bmatrix} 2 & 1 & 0 \\ 1 & 2 & 1 \\ 0 & 1 & 2 \end{bmatrix} \to \begin{bmatrix} 2 & 1 & 0 \\ 0 & 3/2 & 1 \\ 0 & 1 & 2 \end{bmatrix} \]

Step 2 — \(E_{32}\) 적용 (\(\ell_{32} = (1)/(3/2) = 2/3\)):

\[ \to U = \begin{bmatrix} 2 & 1 & 0 \\ 0 & 3/2 & 1 \\ 0 & 0 & 4/3 \end{bmatrix} \]

피벗: \(2, 3/2, 4/3\). \(\ell_{31} = 0\) (A의 \((3,1)\) 원소가 이미 0).

\[ L = \begin{bmatrix} 1 & 0 & 0 \\ 1/2 & 1 & 0 \\ 0 & 2/3 & 1 \end{bmatrix}, \quad A = LU \checkmark \]

\(LDU\) 분해: \(D = \text{diag}(2, 3/2, 4/3)\).

9.2 예시 2: \(Lc = b\), \(Ux = c\) 두 단계 풀이

위 \(A\) 에서 \(b = (1, 2, 3)^\top\) 으로 \(Ax = b\) 풀기.

Step 1 — \(Lc = b\) (전진):

\[ c_1 = 1 \] \[ c_2 = 2 - \frac{1}{2} \cdot 1 = \frac{3}{2} \] \[ c_3 = 3 - 0 \cdot 1 - \frac{2}{3} \cdot \frac{3}{2} = 3 - 1 = 2 \]

\[ c = \begin{bmatrix} 1 \\ 3/2 \\ 2 \end{bmatrix} \]

Step 2 — \(Ux = c\) (후방):

\[ x_3 = 2 / (4/3) = 3/2 \] \[ x_2 = (3/2 - 1 \cdot 3/2) / (3/2) = 0 / (3/2) = 0 \] \[ x_1 = (1 - 1 \cdot 0 - 0 \cdot 3/2) / 2 = 1/2 \]

\[ x = \begin{bmatrix} 1/2 \\ 0 \\ 3/2 \end{bmatrix} \]

검증: \(Ax = (2 \cdot 1/2 + 1 \cdot 0, 1 \cdot 1/2 + 2 \cdot 0 + 1 \cdot 3/2, 0 + 1 \cdot 0 + 2 \cdot 3/2) = (1, 2, 3) = b \checkmark\)

9.3 예시 3: 파스칼 행렬의 \(A = LU\)

파스칼 삼각형의 원소로 이루어진 대칭 행렬 \(P\) (4×4):

\[ P = \begin{bmatrix} 1 & 1 & 1 & 1 \\ 1 & 2 & 3 & 4 \\ 1 & 3 & 6 & 10 \\ 1 & 4 & 10 & 20 \end{bmatrix} \]

소거하면 모든 피벗이 1이다. 승수들도 모두 1. \(L\) 의 모든 원소가 “파스칼 삼각형”에서 온다.

\[ L = \begin{bmatrix} 1 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 \\ 1 & 2 & 1 & 0 \\ 1 & 3 & 3 & 1 \end{bmatrix}, \quad U = L^\top = \begin{bmatrix} 1 & 1 & 1 & 1 \\ 0 & 1 & 2 & 3 \\ 0 & 0 & 1 & 3 \\ 0 & 0 & 0 & 1 \end{bmatrix} \]

\(P\) 가 대칭 행렬이므로 \(U = L^\top\) — \(LDU\) 에서 \(D = I\) 이고 \(\tilde{U} = L^\top\).

10 ML/DL에서의 연결

10.1 정규방정식과 \(LU\) 분해

최소자승법의 정규방정식 \(A^\top A x = A^\top b\) 에서, \(A^\top A\) 는 대칭·양정치 행렬이다. 이 경우 \(LU\) 분해 대신 Cholesky 분해 \(A^\top A = LL^\top\) 를 쓰면 연산량이 절반으로 줄어든다.

10.2 가중치 행렬의 갱신 — Sherman-Morrison-Woodbury

딥러닝 최적화에서 가중치 행렬의 소규모 업데이트가 자주 일어난다. \(A = LU\) 를 알고 있을 때 \(A + UV^\top\) 의 역행렬은 기존 역행렬을 재사용하여 계산할 수 있다 — Sherman-Morrison-Woodbury 공식. \(LU\) 분해가 기반이 된다.

10.3 배치 선형 시스템 — GPU 병렬화

딥러닝 추론에서 \(AX = B\) (\(X\) 의 각 열이 독립적인 입력 샘플)를 GPU에서 풀 때, \(A = LU\) 분해를 한 번 하고 \(X\) 의 각 열에 대한 삼각 풀이를 병렬 처리한다. 분해(\(O(n^3)\))는 직렬, 풀이(\(O(n^2) \times B\) 개 배치)는 병렬로 처리되므로 전체 효율이 크게 향상된다.

11 코드로 확인하기

11.1 Step 1 — \(A = LU\) 분해 직접 구현

import numpy as np

def lu_no_pivot(A):
    """
    행 교환 없는 LU 분해.
    반환: L (하삼각, 대각 1), U (상삼각, 피벗이 대각)
    """
    n = A.shape[0]
    A = A.copy().astype(float)
    L = np.eye(n)

    for k in range(n - 1):           # 피벗 열 k
        pivot = A[k, k]
        if abs(pivot) < 1e-12:
            raise ValueError(f"피벗 = 0: 행 교환 필요 (열 {k})")
        for i in range(k + 1, n):    # 피벗 아래 행들
            ell = A[i, k] / pivot
            L[i, k] = ell            # 승수를 L에 기록
            A[i, k:] -= ell * A[k, k:]  # 소거
    U = A
    return L, U


A = np.array([[2, 4, -2], [4, 9, -3], [-2, -3, 7]], dtype=float)
L, U = lu_no_pivot(A)

print("L:\n", L)
print("U:\n", U)
print("LU == A?", np.allclose(L @ U, A))

11.2 Step 2 — \(Lc = b\), \(Ux = c\) 두 단계 풀이

def forward_sub(L, b):
    """하삼각 시스템 Lc = b 전방 대입."""
    n = len(b)
    c = np.zeros(n)
    for k in range(n):
        c[k] = b[k] - L[k, :k] @ c[:k]
        # L[k,k] = 1이므로 나눗셈 불필요
    return c


def back_sub(U, c):
    """상삼각 시스템 Ux = c 후방 대입."""
    n = len(c)
    x = np.zeros(n)
    for k in range(n - 1, -1, -1):
        x[k] = (c[k] - U[k, k+1:] @ x[k+1:]) / U[k, k]
    return x


def solve_lu(A, b):
    L, U = lu_no_pivot(A)
    c = forward_sub(L, b)
    x = back_sub(U, c)
    return x


b = np.array([2, 8, 10], dtype=float)
x = solve_lu(A, b)
print("해 x:", x)
print("검증 Ax:", A @ x, "== b:", b)

# 여러 우변을 동시에 처리
B = np.array([[2, 1], [8, 0], [10, -3]], dtype=float)  # 우변 2개
L, U = lu_no_pivot(A)
X = np.column_stack([solve_lu(A, B[:, j]) for j in range(2)])
print("다중 우변 해:\n", X)

11.3 Step 3 — 연산량 측정

import time

def benchmark_lu(n_list):
    for n in n_list:
        A = np.random.randn(n, n) + n * np.eye(n)  # 대각 우세 (피벗 0 방지)
        b = np.random.randn(n)

        t0 = time.time()
        L, U = np.linalg.qr(A)  # numpy LU (scipy 사용이 더 정확)
        t_factor = time.time() - t0

        print(f"n={n:5d}: LU 분해 {t_factor:.4f}초")

benchmark_lu([100, 500, 1000, 2000])

12 핵심 요약

\(A = LU\) 유도: \((E_{32}E_{31}E_{21})A = U \implies A = E_{21}^{-1}E_{31}^{-1}E_{32}^{-1}U = LU\).
\(L\) 에 승수가 그대로 들어가는 이유: 소거 시 빼는 행은 \(A\) 의 행이 아닌 이미 확정된 \(U\) 의 행이므로, 각 승수 \(\ell_{ij}\) 가 서로 간섭하지 않는다.
\(A = LDU\): \(U\) 에서 피벗을 \(D\) 로 분리하면 \(L\) 과 \(\tilde{U}\) 모두 대각 1을 갖는다. 대칭 행렬이면 \(\tilde{U} = L^\top\).
두 단계 풀이: \(Lc = b\) (전진 대입, \(O(n^2)\)) → \(Ux = c\) (후방 대입, \(O(n^2)\)).
연산량: 분해 \(\frac{1}{3}n^3\), 풀이 \(n^2\). 분해 1회 + 풀이 다수가 핵심 전략.