[MIT 18.065] 1.4. Elimination and A = LU
카테고리: MIT 18.065
태그: Linear Algebra
💡 이 글은 MIT의 선형대수학 강의 MIT 18.065 Spring 2018 및 Gilbert Strang 교수님의 책 『Linear Algebra and Learning from Data』을 따라 정리했습니다. 강의 내용과 일부 연습문제 풀이를 포함합니다.
1. Introduction
1.2절에서, 1장 전체를 통해 5가지 중요한 분해(factorization)를 다룬다고 하였다.
- $A=LU$: Elimination
- $A=QR$: Orthogonalization (Gram-Schmidt)
- $S = Q \Lambda Q^T$: Eigenvalue, Eigenvector (Spectral Theorem)
- $A=X \Lambda X^{-1}$: Diagonalization
- $A=U \Sigma V^T$: Singular Value Decomposition (SVD)
여기서는 첫 번째 분해인 $A=LU$, 즉 $LU$ factorization을 다룬다. 이 분해는 $Ax=b$의 가우스 소거법(Gaussian elimination)을 통해 얻어지는데, 소거법에 대해 생각하기 전에 $Ax=b$를 어떻게 볼 것인지 생각해보자. 예시로 다음과 같은 선형방정식을 생각해보자.
\[\begin{bmatrix} 1 & -2 \\ 2 & 3 \end{bmatrix} \begin{bmatrix} x \\ y \end{bmatrix} = \begin{bmatrix} 1 \\ 9 \end{bmatrix}\]1.1. The row picture
첫 번째는 $A$의 각 행(row)과 $x$의 inner product로 간주하는 것이다. 즉 $Ax=b$는 다음과 같이 나타낼 수 있다.
\[\begin{aligned} x - 2y &= 1 \\ 2x + 3y &= 9 \end{aligned}\]즉, 2차원에서의 두 직선의 교점이 곧 해 $x$이다. 계산하면 $x=3, y=1$이고, 그림으로 나타내면 다음과 같다.
1.2. The column picture
두 번째는 $A$의 각 열(column)과 $x$의 linear combination으로 간주하는 것이다. 즉 $Ax=b$는 다음과 같이 나타낼 수 있다.
\[\begin{bmatrix} 1 & -2 \\ 2 & 3 \end{bmatrix} \begin{bmatrix} x \\ y \end{bmatrix} = x \begin{bmatrix} 1 \\ 2 \end{bmatrix} + y \begin{bmatrix} -2 \\ 3 \end{bmatrix} = \begin{bmatrix} 1 \\ 9 \end{bmatrix}\]$3 \left(\text{column} 1 \right) + 1 \left(\text{column} 2 \right) = b$ 임을 알 수 있다. 그림으로 나타내면 다음과 같다.
2차원에서는 row picture도 괜찮아 보이지만, 3차원 이상에서는 column picture가 더 직관적이다. 3차원에서 row picture로 나타내려면 3개의 평면을 그려야 하고, 그것이 교차하는 한 점을 찾아야 한다. 그러나 3차원에서도 column picture로 나타내면 3개의 벡터를 그리고, 그것들의 linear combination으로 $b$를 만들어낸다고 생각하면 된다.
2. Solving $Ax=b$ by Elimination
Column picture로 $Ax=b$를 해석할 수 있다는 것을 생각하면서 elimination에 대해 알아보자. 일반적으로 다음 과정을 거치면 upper triangular matrix $U$를 얻을 수 있다.
- $A$의 첫 번째 행(row)을 이용하여 $A$의 첫 번째 열(column)의 나머지 원소들을 0으로 만든다. 이때 첫 번째 행의 첫 번째 원소를 기준으로 나머지 원소들을 제거하는 것이므로, 이 원소를 pivot이라고 한다.
- 1의 과정을 거친 행렬의 두 번째 행을 이용하여 두 번째 열의 나머지 원소들을 0으로 만든다. 이때 두 번째 행의 두 번째 원소를 pivot으로 삼는다.
- $n$까지 반복한다.
예를 들어 첫 번째 행을 이용하여 첫 번째 열의 나머지 원소들을 0으로 만드는 과정에서 첫 번째 행에 곱해지는 비율, 즉 multiplier는 다음과 같다.
\[\ell_{21} = \frac{a_{21}}{a_{11}}, \quad \ell_{31} = \frac{a_{31}}{a_{11}}, \quad \ell_{41} = \frac{a_{41}}{a_{11}}\]이러한 $A$ 행렬의 elimination 과정은 대략 $\frac{1}{3} n^3$ 정도의 곱셈과 덧셈이 필요하다. Step $n-r+1$에서, $r$번째 row에 대해 $r-1$번 반복하여 $r$번의 곱셈과 덧셈이 필요하므로, 총 다음 횟수 만큼의 곱셈과 덧셈이 필요하기 때문이다.
\[\sum_{r=1}^{n} r(r-1) \approx \frac{1}{3} n^3\]3. The factorization $A=LU$
3.1. Interpretation of elimination
이 과정을 다음과 같이 해석해보자. 다음과 같은 방법으로 하나씩 행과 열을 줄여가는 방식이다.
\[\text{Step 1.} \quad A = \begin{bmatrix} 1 \times \text{row} 1 \\ \ell_{21} \times \text{row} 1 \\ \ell_{31} \times \text{row} 1 \\ \ell_{41} \times \text{row} 1 \end{bmatrix} + \begin{bmatrix} 0 & 0 & 0 & 0 \\ 0 & & & \\ 0 & & A_2 & \\ 0 & & & \end{bmatrix}\]여기서 첫번째로 분리된 matrix의 row는 모두 row 1의 배수이므로, 이는 rank one matrix이다. 즉 $\ell_ 1 = (1, \ell_{21}, \ell_{31}, \ell_{41})$이라고 하고, $A$의 row 1을 $u_ 1 ^\ast$이라고 하면 $\ell_ 1 u_1^\ast$이 분리된 것이다. Step 2는 다음과 같겠다.
\[\text{Step 2.} \quad A = \ell_1 u_1^\ast + \begin{bmatrix} 0 \times \text{row} 2 \\ 1 \times \text{row} 2 \\ \ell_{32} \times \text{row} 2 \\ \ell_{42} \times \text{row} 2 \end{bmatrix} + \begin{bmatrix} 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & A_3 & \\ 0 & 0 & & \end{bmatrix}\]이때 $\ell_2 = (0, 1, \ell_{32}, \ell_{42})$이고, $u_2^\ast$는 pivot row 2이다. 이러한 과정을 반복하면 다음과 같이 나타낼 수 있다.
\[A = \ell_1 u_1^\ast + \ell_2 u_2^\ast + \ell_3 u_3^\ast + \ell_4 u_4^\ast = \begin{bmatrix} 1 & \ell_{21} & \ell_{31} & \ell_{41} \\ 0 & 1 & \ell_{32} & \ell_{42} \\ 0 & 0 & 1 & \ell_{43} \\ 0 & 0 & 0 & 1 \end{bmatrix} \begin{bmatrix} \text{pivot row 1} \\ \text{pivot row 2} \\ \text{pivot row 3} \\ \text{pivot row 4} \end{bmatrix} = LU\]따라서 elimination 과정을 통해 lower triangular matrix $L$과 upper triangular matrix $U$로 $A$를 분해하는 $A=LU$ factorization을 얻을 수 있다.
3.2. The solution to $Ax=b$
이제 $Ax=b$를 풀어보자. $A=LU$로 분해하고, $Ax=b$에서 $b$도 같이 계산되어야 하므로 $b$를 additional column으로 간주하면 다음과 같다.
\[\begin{bmatrix} A & b \end{bmatrix} = \begin{bmatrix} LU & b \end{bmatrix} \rightarrow \begin{bmatrix} U & L^{-1}b \end{bmatrix} = \begin{bmatrix} U & c \end{bmatrix}\]예를 들어 다음과 같은 $Ax=b$를 풀어보자.
\[\begin{bmatrix} 2 & 3 \\ 4 & 7 \end{bmatrix} \begin{bmatrix} x \\ y \end{bmatrix} = \begin{bmatrix} 8 \\ 18 \end{bmatrix} \rightarrow \begin{bmatrix} 2 & 3 & 8 \\ 4 & 7 & 18 \end{bmatrix} \rightarrow \begin{bmatrix} 2 & 3 & 8 \\ 0 & 1 & 2 \end{bmatrix} = \begin{bmatrix} U & c \end{bmatrix}\]따라서 $y=2$를 얻으므로, back substitution을 통해 $x=1$을 얻을 수 있다.
그런데 만약 $a_{11} = 0$이면 어떻게 될까? 이 경우에는 row 1을 pivot row로 설정할 수 없다. 따라서 이런 경우에 pivot을 다른 row로 바꾸는 것이 중요하다. 이를 permutation으로 해결하고, 이것이 더욱 일반적인 $LU$ factorization이다. 그리고, 좋은 컴퓨터 알고리즘은 $a_{11} \neq 0$이더라도 pivot을 선택할 때 가장 큰 값을 pivot으로 선택한다고 한다.
3.3. Permutation (Row exchange)
$a_{11} = 0$인 예시를 하나 들어보자. 다음과 같은 $A$에 대해 $A=LU$ factorization을 하려고 할 때, row 1을 pivot row로 설정할 수 없으므로, 대신 row 3을 pivot row로 설정하자.
\[A = \begin{bmatrix} 0 & 1 & 1 \\ 1 & 3 & 7 \\ 2 & 4 & 8 \end{bmatrix}\]다음과 같이 rank one matrix $\ell_1 u_1^\ast$을 분리하면 다음과 같다.
\[\begin{bmatrix} 0 & 1 & 1 \\ 1 & 3 & 7 \\ 2 & 4 & 8 \end{bmatrix} = \begin{bmatrix} 0 \\ 1/2 \\ 1 \end{bmatrix} \begin{bmatrix} 2 & 4 & 8 \end{bmatrix} + \begin{bmatrix} 0 & 1 & 1 \\ 0 & 1 & 3 \\ 0 & 0 & 0 \end{bmatrix}\]이제 다시 row 1을 pivot row로 설정하고, 다음과 같이 rank one matrix $\ell_2 u_2^\ast$, $\ell_3 u_3^\ast$을 분리하면 다음과 같다.
\[\begin{bmatrix} 0 & 1 & 1 \\ 0 & 1 & 3 \\ 0 & 0 & 0 \end{bmatrix} = \begin{bmatrix} 1 \\ 1 \\ 0 \end{bmatrix} \begin{bmatrix} 0 & 1 & 1 \end{bmatrix} + \begin{bmatrix} 0 \\ 1 \\ 0 \end{bmatrix} \begin{bmatrix} 0 & 0 & 2 \end{bmatrix}\]따라서 $A$를 분해한 결과는 다음과 같다.
\[A = \begin{bmatrix} 0 & 1 & 1 \\ 1 & 3 & 7 \\ 2 & 4 & 8 \end{bmatrix} = \begin{bmatrix} 0 & 1 & 0 \\ 1/2 & 1 & 1 \\ 1 & 0 & 0 \end{bmatrix} \begin{bmatrix} 2 & 4 & 8 \\ 0 & 1 & 1 \\ 0 & 0 & 2 \end{bmatrix}\]이제 더 이상 $L$은 lower triangular matrix가 아니다. 현재 $A$의 pivot 순서는 row 3, 1, 2이다. 이를 row 1, 2, 3으로 바꾸어주기 위해 permutation $P$를 사용한다.
\[PA = \begin{bmatrix} 0 & 0 & 1 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \end{bmatrix} \begin{bmatrix} 0 & 1 & 1 \\ 1 & 3 & 7 \\ \mathbf{2} & \mathbf{4} & \mathbf{8} \end{bmatrix} = \begin{bmatrix} \mathbf{2} & \mathbf{4} & \mathbf{8} \\ 0 & 1 & 1 \\ 1 & 3 & 7 \end{bmatrix}\]따라서 $PA=LU$로 factorization 가능하다.
\[PA = \begin{bmatrix} 2 & 4 & 8 \\ 0 & 1 & 1 \\ 1 & 3 & 7 \end{bmatrix} = \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 1/2 & 1 & 1 \end{bmatrix} \begin{bmatrix} 2 & 4 & 8 \\ 0 & 1 & 1 \\ 0 & 0 & 2 \end{bmatrix} = LU\]여기서 다음과 같은 명제를 유추할 수 있다.
모든 invertible $n \times n$ matrix $A$에 대해 $PA=LU$가 성립한다.
참고로 Permutation matrix는 $n \times n$ matrix에 대하여 $n!$개 존재하고, $P^{-1} = P^T$ 즉 $P^T P = I$가 성립한다. 즉 $P$는 orthogonal matrix이다.
4. Selected Solutions to Problems
Problem 3.
Q. 다음 $A$에 대하여 $EA = U$가 되는 $E$를 찾고, $E^{-1} = L$을 양변에 곱해 $A=LU$를 완성하라. ($E$는 lower triangular matrix, $U$는 upper triangular matrix이다.)
\[A = \begin{bmatrix} 2 & 1 & 0 \\ 0 & 4 & 2 \\ 6 & 3 & 5 \end{bmatrix}\]이 방법은 내가 elementary linear algebra 과정에서 $LU$ factorization을 배울 때 사용했던 방법이다. $E$는 $A$의 각 행에 대해 pivot을 설정하는 과정에서 나오는 lower triangular matrix라고 생각하면 된다. 여기서는 row 1에 3을 곱해 row 3에서 빼는 과정 한 번만으로 upper triangular matrix를 얻을 수 있으므로, $E$를 다음과 같이 설정할 수 있다.
\[E = \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ -3 & 0 & 1 \end{bmatrix} \rightarrow EA = \begin{bmatrix} 2 & 1 & 0 \\ 0 & 4 & 2 \\ 0 & 0 & 5 \end{bmatrix} = U\]$E$가 row 1의 3배를 row 3에서 빼는 연산을 의미하므로, $E^{-1}$은 row 1에 3을 곱해 row 3에 더하는 연산을 의미한다. 따라서 $E^{-1}$은 다음과 같다.
\[E^{-1} = \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 3 & 0 & 1 \end{bmatrix} = L\]따라서 $A=LU$ factorization은 다음과 같다.
\[A = \begin{bmatrix} 2 & 1 & 0 \\ 0 & 4 & 2 \\ 6 & 3 & 5 \end{bmatrix} = \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 3 & 0 & 1 \end{bmatrix} \begin{bmatrix} 2 & 1 & 0 \\ 0 & 4 & 2 \\ 0 & 0 & 5 \end{bmatrix} = LU\]개인적으로는 $EA=U \rightarrow A=LU$로 두 단계로 진행하는 것보다는 rank one matrix를 이용해 한번에 $A=LU$를 찾는 것이 더 직관적이라고 생각한다. (물론 둘 다 동일한 elimination을 어떻게 해석하느냐의 차이일 뿐이다.)
Problem 8.
Q. Tridiagonal matrix, 즉 main diagonal과 two adjacent diagonal을 제외하고 모두 0인 행렬은 $A=LDL^T$로 분해할 수 있다. 이때 $L$은 lower triangular matrix, $D$는 diagonal matrix이다. 다음 $A$에 대하여 $A=LDL^T$를 찾아라.
\[A = \begin{bmatrix} a & a & 0 \\ a & a+b & b \\ 0 & b & b+c \end{bmatrix}\]Elimination 과정을 통해 다음과 같이 $A=LU$ factorization을 얻을 수 있다.
\[A = \begin{bmatrix} a & a & 0 \\ a & a+b & b \\ 0 & b & b+c \end{bmatrix} = \begin{bmatrix} 1 & 0 & 0 \\ 1 & 1 & 0 \\ 0 & 1 & 1 \end{bmatrix} \begin{bmatrix} a & a & 0 \\ 0 & b & b \\ 0 & 0 & c \end{bmatrix} = LU\]이후 아래 성질을 이용한다.
따라서 다음과 같이 $A= LDL^T$를 얻을 수 있다.
\[A = \begin{bmatrix} 1 & 0 & 0 \\ 1 & 1 & 0 \\ 0 & 1 & 1 \end{bmatrix} \begin{bmatrix} a & & \\ & b & \\ & & c \end{bmatrix} \begin{bmatrix} 1 & 1 & 0 \\ 0 & 1 & 1 \\ 0 & 0 & 1 \end{bmatrix} = LDL^T\]Problem 10.
Q. Invertible matrix $A$에 대하여, $A = LU$가 가능할 조건은 무엇인가?
Upper left submatrix를 $A_1, A_2, \cdots, A_n$이라 하자. 이때 모든 upper left submatrices $A_k$가 invertible하면 $A=LU$가 가능하다. 이는 즉 leading pricipal minor가 0이 아니라는 조건과 동치이다. Leading principal minor는 다음과 같이 정의된다.
Problem 11.
Q. 데이터 사이언스에서는 first pivot을 선택할 때, 가장 큰 값 $\vert a_{ij} \vert$를 선택하기도 한다. 예를 들어 아래 예시에서는 $\vert a_{22} \vert = 4$를 pivot으로 선택하여 다음과 같이 factorization을 진행한다.
\[\begin{bmatrix} 1 & 2 \\ 3 & \mathbf{4} \end{bmatrix} = \begin{bmatrix} 1/2 \\ 1 \end{bmatrix} \begin{bmatrix} 3 & 4 \end{bmatrix} + \begin{bmatrix} -1/2 & 0 \\ 0 & 0 \end{bmatrix} = \begin{bmatrix} 1/2 & 1 \\ 1 & 0 \end{bmatrix} \begin{bmatrix} 3 & 4 \\ -1/2 & 0 \end{bmatrix}\]이런 경우 $L$, $U$ 모두 triangular matrix가 아니다. 즉, 둘 다 permutation이 필요하다. 따라서 $P_1 A P_2 = LU$로 분해해야 한다. 이때 permutation matrix $P_1$, $P_2$를 구해 $P_1 A P_2 = LU$를 완성하라.
결국 $a_{22}$를 $a_{11}$로 만들어주면 문제가 해결된다. 따라서 row를 바꾸는 permutation matrix $P_1$, column을 바꾸는 permutation matrix $P_2$를 다음과 같이 설정하면 된다.
\[P_1 = \begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix}, \quad P_2 = \begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix}\]따라서 $P_1 A P_2 = LU$로 분해하면 다음과 같다.
\[P_1 A P_2 = \begin{bmatrix} \mathbf{4} & 3 \\ 2 & 1 \end{bmatrix} = \begin{bmatrix} 1 & 0 \\ 1/2 & 1 \end{bmatrix} \begin{bmatrix} 4 & 3 \\ 0 & -1/2 \end{bmatrix} = LU\]
댓글 남기기