Lecture 4: Factorization into A = LU

 

Inverse of AB

 

$AA^{-1} = I = A^{-1}A$

 

$AB\square = I$ 

 

$ABB^{-1} = A$이고 $AA^{-1} = I$이므로

 

$AB$의 역행렬은 $B^{-1}A^{-1}$입니다. 

 

$B^{-1}A^{-1}AB = I$

 

원래의 행렬 곱셈의 반대 순서로 역행렬을 곱해줍니다. 

 

 

Inverse of $A^{T}$

 

$AA^{-1} = I$

 

$(A^{-1})^{T}A^{T} = I$

 

$(A^{T})^{-1}$은 $A^{T}$의 역핼렬입니다. 

 

전치 (transpose)는 row와 col의 원소를 바꾸는 것을 말합니다. 

 

 

A = LU = LDU

 

선형대수에서 Matrix Decomposition은 어떤 행렬을 여러 행렬들의 곱으로 표현하는 것을 의미합니다. 

 

목적은 계산의 편의성과 분석의 용이성 때문입니다. 

 

$A = \begin{bmatrix}
2 & 1\\ 
8 & 7
\end{bmatrix}$

 

$E_{21}A =$ $\begin{bmatrix}
1 & 0\\ 
-4 &1 
\end{bmatrix}$ $\begin{bmatrix}
2 & 1\\ 
8 & 7 
\end{bmatrix} =$ $\begin{bmatrix}
2 & 1\\ 
0 &3 
\end{bmatrix} =$ $U$

 

A = LU가 나오려면 $E_{21}$의 역행렬을 곱해주면 됩니다. 

 

즉, 소거행렬 $E_{21}$의 역행렬이 L 행렬입니다. 

 

L은 하삼각행렬 (Lower Trainagular Matrix)의 L을 따온 것입니다.

 

$A =$ $\begin{bmatrix}
2 & 1\\ 
8 &7 
\end{bmatrix}$ $=\begin{bmatrix}
1 & 0\\ 
4 & 1 
\end{bmatrix}$ $\begin{bmatrix}
2 & 1\\ 
0 &3 
\end{bmatrix} =$ $LU$

 

$E_{21}$ 역행렬을 구하는 것은 단위행렬이 되겠끔 소거 행렬을 곱해준다고 생각하면 간단합니다. 

 

=$ \begin{bmatrix}
1 & 0\\ 
4 & 1 
\end{bmatrix}$ $ \begin{bmatrix}
2 & 0\\ 
0 &3 
\end{bmatrix}$ $\begin{bmatrix}
1 & 1/2\\ 
0 & 1 
\end{bmatrix}$

 

= $LDU$

 

pivot들만 따로 뗴어서 분해하고 싶을 때는 LDU 분해를 씁니다.

 

구하는 방법은 U행렬에서 각 pivot이 속해있는 행을 해당 pivot으로 나눠준 후 새로운 행렬을 써주면 됩니다. 

 

D는 Diagonal Matrix이며 대각 행렬을 의미합니다. 

 

 

A = LU (No Row Exchanges)

 

$E_{32}E_{31}E_{21}A = U$ (No row exchanges)

 

$A = E_{21}^{-1}E_{31}^{-1}E_{32}^{-1}U = LU$

 

Inverse (reverse order)

 

$A = \begin{bmatrix}
2 &  1& 7\\ 
4 & -1 & 16\\ 
0 &-15  & 19
\end{bmatrix}$

 

$E_{31}E_{21} =$ $\begin{bmatrix}
1 & 0 & 0\\ 
0 &  1& 0\\ 
0 &  -5& 1
\end{bmatrix} $ $\begin{bmatrix}
1 & 0 & 0\\ 
-2 &  1& 0\\ 
0 &  0& 1
\end{bmatrix} =$ $\begin{bmatrix}
1 & 0 & 0\\ 
-2 &  1& 0\\ 
10 &  -5& 1
\end{bmatrix} =$ $E$ (Left of A) 

 

$E_{31} = I$입니다. 

 

$\begin{bmatrix}
1 & 0 & 0\\ 
2 &  1& 0\\ 
0 &  0& 1
\end{bmatrix}$ $\begin{bmatrix}
1 & 0 & 0\\ 
0 &  1& 0\\ 
0 &  5& 1
\end{bmatrix} =$ $\begin{bmatrix}
1 & 0 & 0\\ 
2 &  1& 0\\ 
0 &  5& 1
\end{bmatrix} =$ $L$ (Left of U)

 

$EA = U, A = LU$

 

 

A = LU (No Row Exchanges) Continue

 

$A = LU$

 

만약 어떤 행 바꿈도 없다면 소거에 사용되는 원소들은 L 행렬의 각자 위치에 그대로 들어갑니다. 

 

 

A = LU (No Row Exchanges) Cost

 

$n x n matrix A$에서 얼마나 많은 연산이 이루어 질까요? (multiply subtract)

 

n = 100이면 

 

$\begin{bmatrix}
- & - & -\\ 
- &  -& -\\ 
- &  -& -
\end{bmatrix}$ 

 

$n, n^{2}, n^{3}, n! ??$

 

$\begin{bmatrix}
- & - & -\\ 
- &  -& -\\ 
- &  -& -
\end{bmatrix} \rightarrow$ $\begin{bmatrix}
\square & - & -\\ 
0 &  -& -\\ 
0 &  -& -
\end{bmatrix}$ 

 

진행하면 about $100^{2}?$

 

$\begin{bmatrix}
- & - & -\\ 
- &  -& -\\ 
- &  -& -
\end{bmatrix} \rightarrow$ $\begin{bmatrix}
\square & - & -\\ 
0 &  -& -\\ 
0 &  -& -
\end{bmatrix} \rightarrow$ $\begin{bmatrix}
\square & - & -\\ 
0 &  \square& -\\ 
0 &  0& -
\end{bmatrix}$ 

 

About $99^{2}$

 

$n^{2} + (n-1)^{2} + ... + 3^{2} + 2^{2} + 1^{2}$

 

$n^{2} + (n-1)^{2} + ... + 3^{2} + 2^{2} + 1^{2} \approx \frac{1}{3}n^{3}$

 

Cost of $\textbf{b}$는 $n^{2}$

 

 

Permutations 3x3

 

행 교환이 필요한 경우 치환행렬을 곱해주어야 합니다. 

 

$\begin{bmatrix}
1 &  & \\ 
 & 1 & \\ 
 &  &1 
\end{bmatrix}$, $\begin{bmatrix}
0 & 1 & 0\\ 
1 & 0 & 0\\ 
 0&  0&1 
\end{bmatrix} $, $\begin{bmatrix}
0 & 0 & 1\\ 
0 & 1 & 0\\ 
 1&  0&0 
\end{bmatrix}$, $\begin{bmatrix}
1 & 0 & 0\\ 
0 & 0 & 1\\ 
 1&  0&0
\end{bmatrix}$, $\begin{bmatrix}
0 & 1 & 0\\ 
0 & 0 & 1\\ 
 1&  0&0 
\end{bmatrix}$, $\begin{bmatrix}
0 & 0 & 1\\ 
1 & 0 & 0\\ 
 0&  1&0 
\end{bmatrix} $

 

6P's 

 

치환 행렬의 조합의 개수는 n! 입니다. 

 

$P^{-1} = P^{T}$

 

치환 행렬 P는 대칭 행렬이기 때문에 역행렬이 전치와 같습니다. 

 

참고로 4x4는 24P's가 나옵니다.

 

행 바꿈이 필요한 A = LU 분해를 할 때 위와 같은 치환 행렬을 곱해서 PA = LU 꼴로 분해할 수 있습니다.