3. Gaussian Elimination and LU Factorization

1. Gaussian Elimination

아래와 같은 linear equations를 풀려고 한다.

 

\begin{align} x_{1} + x_{2} &= 2 \\ 2x_{1} - x_{2} &= -4 \end{align}

 

일반적으로 두 등식 간에 연산을 취하여 아래의 꼴을 만들면 답을 쉽게 구할 수 있다.

\begin{align} \\ x_{1} + x_{2} &= 2 \\ -3x_{2} &= -8 \end{align}

 

즉, 일단 바로 위의 등식과 같은 triangular form을 얻으면 풀렸다고 봐도 된다. 이렇게 행렬을 triangular form으로 만들기 위한 방법을 Gaussian Elimination Method라고 한다. 즉, $A \mathbf{x} = \mathbf{b}$에서 $A$를 upper triangular form으로 바꾸기 위한 방법이다.

 

가우스 소거법에선 등식에 대해 $3$가지의 연산을 수행할 수 있다. 이 연산들을 적용하면서 행렬을 upper triangular form으로 바꾼다.

 

 

• 어떤 행에 상수배를 하여 다른 행에 더하는 연산
• 서로 다른 두 행을 바꾸는 연산(이대로는 elimination을 더 이상 진행할 수 없을 때 사용)
• 어떤 행에 $0$이 아닌 상수를 곱해 스케일하는 연산

 

행렬 $A$에 $E$를 곱하여 이러한 row operation을 적용할 수 있다. 각 연산에 대한 $E$의 꼴은 여기에서 자세히 볼 수 있다.

 

가우스 소거법 을 적용한 후 얻는 행렬을 row echelon form(REF)이라고 한다. REF와 RREF에 대한 개념은 여기에서 볼 수 있다. 피벗(pivots)이란 REF의 각 행에서 $0$이 아닌 첫 번째 요소들을 의미한다.

 

$n$개의 미지수를 포함하는 $n$개의 등식에 대한 $A$를 생각해보자. $A$의 REF 꼴에서 pivots이 $n$개 라면 해당 linear equations에는 해가 존재하며 $1$개로 유일하다.

 

가우스 소거법 을 끝까지 수행할 수 없는(피벗이 $n$개가 아닌 경우) 경우 permanent breakdown이 발생했다고 하며, 이는 linear equations의 해가 없거나 무수히 많음을 의미한다.

 

 

 

2. LU Factorization

LU 분해에서 $L$은 Lower triangular matrix, $U$는 Upper triangular matrix를 뜻한다. 즉, $A$를 그러한 행렬의 곱으로 분해한 것이다.

 

가우스 소거법의 적용을 행렬곱의 관점에서 보자면 $E_{32}E_{31}E_{21}A = U$와 같다. 여기선 단순히 예를 들기 위함이므로 $E$의 개수와 밑의 첨자는 어떤 row operation을 적용했는지에 따라 당연히 다양하게 바뀐다. 위의 블로그 링크글들을 이해했다면, row operation 행렬 $E$는 역행렬이 존재함을 알 수 있다. 그러므로 $A = (E_{32}E_{31}E_{21})^{-1}U$인데 여기서 $E$ 묶음들의 역행렬은 Lower triangular matrix 꼴이다. 그러므로 $A$는 LU 분해가 되었다.

 

LU 분해를 하는 가장 큰 이유는 $A \mathbf{x} = \mathbf{b}$에서 $\mathbf{b}$가 계속 바뀌는 경우, 해를 빠르게 구할 수 있다는 장점이 있기 때문이다. $A \mathbf{x} = LU \mathbf{x} = \mathbf{b}$인데, $U \mathbf{x} = \mathbf{c}$로 두고 $Lc = \mathbf{b}$를 먼저 풀어보자. triangular form이므로 해를 구하는 것은 쉽다. 구한 $\mathbf{c}$로 $U \mathbf{x} = \mathbf{c}$를 풀면된다. 이 또한 triangular form이므로 해를 구하는 것이 쉽다.

 

모든 정사각행렬은 LU 분해로 나타낼 수 있다.

 

 

읽어 볼 만한 글 : 가우스 소거법과 가우스-조던 소거법

 

 

 

3. LDU Factorization

LU 분해에서, $U$는 $DU^{'}$로 한 번더 분해될 수 있다. 여기서 $D$는 diagonal matrix(대각 행렬)이며, 대각 원소는 피벗이다.

 

 

 

4. Symmetric Matrices

$A$ matrix is said to be symmetric if $A^{T} = A$

 

Properties of symmetric matrices

• If $A$ is symmetric and invertible, then $A^{-1}$ is symmetric
• $R^{T}R$ and $RR^{T}$ are symmetric for any matrix $R$
• For a symmetric matrix $A$ having $LDU$ factorization, $U=L^{T}$. That is, $A=LDL^{T}$