https://ocw.mit.edu/courses/18-06-linear-algebra-spring-2010/video_galleries/video-lectures/
먼저 Inverse Matrix에서 시작한다.
A A − 1 = I = A − 1 A AA^{-1} = I = A^{-1}A A A − 1 = I = A − 1 A 위 수식과 같이 A A − 1 = I AA^{-1}=I A A − 1 = I
그렇다면 A B AB A B
A B B − 1 A − 1 = A I A − 1 = A A − 1 = I ABB^{-1}A^{-1} = AIA^{-1} = AA^{-1} = I A B B − 1 A − 1 = A I A − 1 = A A − 1 = I 위 수식과 같이 A B AB A B B − 1 A − 1 B^{-1}A^{-1} B − 1 A − 1
( A B ) − 1 = B − 1 A − 1 (AB)^{-1} = B^{-1}A^{-1} ( A B ) − 1 = B − 1 A − 1 그렇다면 A A − 1 = I AA^{-1}=I A A − 1 = I
( A − 1 ) T A T = I (A^{-1})^TA^T=I ( A − 1 ) T A T = I 위와 같이 나올 것이다. 그러면 여기서 우리는 다음과 같은 수식을 도출할 수 있겠다.
( A − 1 ) T = ( A T ) − 1 (A^{-1})^T = (A^T)^{-1} ( A − 1 ) T = ( A T ) − 1 이제 지난 강의에서 했던 Elimination에 대해서 좀더 알아보자.U U U A A A
[ − − − − ] ⏟ E 21 [ 2 1 8 7 ] ⏟ A = [ 2 1 0 3 ] ⏟ U \underbrace{ \begin{bmatrix} - & - \\ - & - \end{bmatrix} }_{E_{21}} \underbrace{ \begin{bmatrix} 2 & 1 \\ 8 & 7 \end{bmatrix} }_{A} \ = \underbrace{ \begin{bmatrix} 2 & 1 \\ 0 & 3 \end{bmatrix} }_{U} E 2 1 [ − − − − ] A [ 2 8 1 7 ] = U [ 2 0 1 3 ] 위에서 E 21 E_{21} E 2 1
먼저, U U U r o w 1 row_1 r o w 1 A A A r o w 1 row_1 r o w 1 r o w 2 row_2 r o w 2
다음으로 U U U r o w 2 row_2 r o w 2 A A A r o w 1 row_1 r o w 1 r o w 2 row_2 r o w 2
따라서 결과는 다음과 같이 나올 것이다.
[ 1 0 − 4 1 ] ⏟ E 21 [ 2 1 8 7 ] ⏟ A = [ 2 1 0 3 ] ⏟ U \underbrace{ \begin{bmatrix} 1 & 0 \\ -4 & 1 \end{bmatrix} }_{E_{21}} \underbrace{ \begin{bmatrix} 2 & 1 \\ 8 & 7 \end{bmatrix} }_{A} \ = \underbrace{ \begin{bmatrix} 2 & 1 \\ 0 & 3 \end{bmatrix} }_{U} E 2 1 [ 1 − 4 0 1 ] A [ 2 8 1 7 ] = U [ 2 0 1 3 ] 그렇다면 A = L U A=LU A = L U E 21 − 1 E_{21}^{-1} E 2 1 − 1 E 21 − 1 = L ( l o w e r t r i a n g l e ) E_{21}^{-1} = L(lower \ triangle) E 2 1 − 1 = L ( l o w e r t r i a n g l e )
[ 1 0 4 1 ] ⏟ E 21 − 1 [ 1 0 − 4 1 ] ⏟ E 21 = [ 1 0 0 1 ] ⏟ I \underbrace{ \begin{bmatrix} 1 & 0 \\ 4 & 1 \end{bmatrix} }_{E_{21}^{-1}} \underbrace{ \begin{bmatrix} 1 & 0 \\ -4 & 1 \end{bmatrix} }_{E_{21}} \ = \underbrace{ \begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix} }_{I} E 2 1 − 1 [ 1 4 0 1 ] E 2 1 [ 1 − 4 0 1 ] = I [ 1 0 0 1 ]
I I I r o w 1 row_1 r o w 1 E 21 E_{21} E 2 1 r o w 1 row_1 r o w 1 r o w 2 row_2 r o w 2 I I I r o w 2 row_2 r o w 2 E 21 E_{21} E 2 1 r o w 2 row_2 r o w 2 r o w 1 row_1 r o w 1
따라서 다음과 같이 구할 수 있겠다.
[ 2 1 8 7 ] ⏟ A = [ 1 0 4 1 ] ⏟ L [ 2 1 0 3 ] ⏟ U \underbrace{ \begin{bmatrix} 2 & 1 \\ 8 & 7 \end{bmatrix} }_{A} \ = \underbrace{ \begin{bmatrix} 1 & 0 \\ 4 & 1 \end{bmatrix} }_{L} \underbrace{ \begin{bmatrix} 2 & 1 \\ 0 & 3 \end{bmatrix} }_{U} A [ 2 8 1 7 ] = L [ 1 4 0 1 ] U [ 2 0 1 3 ] 그렇다면 여기서 좀더 나아가서 A = L D U A = LDU A = L D U D D D
[ 2 1 8 7 ] ⏟ A = [ 1 0 4 1 ] ⏟ L [ 2 1 0 3 ] ⏟ U = [ 1 0 4 1 ] ⏟ L [ 2 0 0 3 ] ⏟ D [ − − − − ] ⏟ U 2 \underbrace{ \begin{bmatrix} 2 & 1 \\ 8 & 7 \end{bmatrix} }_{A} \ = \underbrace{ \begin{bmatrix} 1 & 0 \\ 4 & 1 \end{bmatrix} }_{L} \underbrace{ \begin{bmatrix} 2 & 1 \\ 0 & 3 \end{bmatrix} }_{U} \ = \underbrace{ \begin{bmatrix} 1 & 0 \\ 4 & 1 \end{bmatrix} }_{L} \underbrace{ \begin{bmatrix} 2 & 0 \\ 0 & 3 \end{bmatrix} }_{D} \underbrace{ \begin{bmatrix} - & - \\ - & - \end{bmatrix} }_{U_2} A [ 2 8 1 7 ] = L [ 1 4 0 1 ] U [ 2 0 1 3 ] = L [ 1 4 0 1 ] D [ 2 0 0 3 ] U 2 [ − − − − ]
위에서 U 2 U_2 U 2 U U U D D D
먼저 D D D r o w 1 row_1 r o w 1 U U U r o w 1 row_1 r o w 1 U U U r o w 2 row_2 r o w 2
다음으로 D D D r o w 2 row_2 r o w 2 U U U r o w 1 row_1 r o w 1 U U U r o w 2 row_2 r o w 2
정리하면 다음과 같다.
[ 2 1 8 7 ] ⏟ A = [ 1 0 4 1 ] ⏟ L [ 2 1 0 3 ] ⏟ U = [ 1 0 4 1 ] ⏟ L [ 2 0 0 3 ] ⏟ D [ 1 1 2 0 1 ] ⏟ U 2 \underbrace{ \begin{bmatrix} 2 & 1 \\ 8 & 7 \end{bmatrix} }_{A} \ = \underbrace{ \begin{bmatrix} 1 & 0 \\ 4 & 1 \end{bmatrix} }_{L} \underbrace{ \begin{bmatrix} 2 & 1 \\ 0 & 3 \end{bmatrix} }_{U} \ = \underbrace{ \begin{bmatrix} 1 & 0 \\ 4 & 1 \end{bmatrix} }_{L} \underbrace{ \begin{bmatrix} 2 & 0 \\ 0 & 3 \end{bmatrix} }_{D} \underbrace{ \begin{bmatrix} 1 & \frac{1}{2} \\ 0 & 1 \end{bmatrix} }_{U_2} A [ 2 8 1 7 ] = L [ 1 4 0 1 ] U [ 2 0 1 3 ] = L [ 1 4 0 1 ] D [ 2 0 0 3 ] U 2 [ 1 0 2 1 1 ] 그러면 3x3 행렬의 Elimination은 어떨까.
E 32 E 31 E 21 A = U E_{32}E_{31}E_{21}A=U E 3 2 E 3 1 E 2 1 A = U 에서 A = L U A=LU A = L U E E E
A = E 21 − 1 E 31 − 1 E 32 − 1 U A=E_{21}^{-1}E_{31}^{-1}E_{32}^{-1}U A = E 2 1 − 1 E 3 1 − 1 E 3 2 − 1 U 그러면 여기서
A = E 21 − 1 E 31 − 1 E 32 − 1 U = L U A=E_{21}^{-1}E_{31}^{-1}E_{32}^{-1}U = LU A = E 2 1 − 1 E 3 1 − 1 E 3 2 − 1 U = L U E 21 − 1 E 31 − 1 E 32 − 1 = L E_{21}^{-1}E_{31}^{-1}E_{32}^{-1} = L E 2 1 − 1 E 3 1 − 1 E 3 2 − 1 = L 을 알 수 있다.
구체적인 예시로 한번 접근해보자.
다음은 E E E
[ 1 0 0 0 1 0 0 − 5 1 ] ⏟ E 32 [ 1 0 0 − 2 1 0 0 0 1 ] ⏟ E 21 = [ 1 0 0 − 2 1 0 10 − 5 1 ] = E \underbrace{ \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & -5 & 1 \end{bmatrix} }_{E_{32}} \underbrace{ \begin{bmatrix} 1 & 0 & 0 \\ -2 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix} }_{E_{21}} \ = \begin{bmatrix} 1 & 0 & 0 \\ -2 & 1 & 0 \\ 10 & -5 & 1 \end{bmatrix} = E E 3 2 ⎣ ⎢ ⎡ 1 0 0 0 1 − 5 0 0 1 ⎦ ⎥ ⎤ E 2 1 ⎣ ⎢ ⎡ 1 − 2 0 0 1 0 0 0 1 ⎦ ⎥ ⎤ = ⎣ ⎢ ⎡ 1 − 2 1 0 0 1 − 5 0 0 1 ⎦ ⎥ ⎤ = E
위처럼 Elimination들을 곱해보니 E A = U EA = U E A = U E E E
그리고 위에서 E 31 E_{31} E 3 1
먼저 r o w 2 row_2 r o w 2 r o w 1 row_1 r o w 1 r o w 3 row_3 r o w 3 r o w 2 row_2 r o w 2
그리고 r o w 2 row_2 r o w 2 r o w 1 row_1 r o w 1 r o w 3 row_3 r o w 3 r o w 2 row_2 r o w 2
이제 Inverse(reverse)를 적용해보자.
[ 1 0 0 2 1 0 0 0 1 ] [ 1 0 0 0 1 0 0 5 1 ] = [ 1 0 0 2 1 0 0 5 1 ] = L \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 ⎣ ⎢ ⎡ 1 2 0 0 1 0 0 0 1 ⎦ ⎥ ⎤ ⎣ ⎢ ⎡ 1 0 0 0 1 5 0 0 1 ⎦ ⎥ ⎤ = ⎣ ⎢ ⎡ 1 2 0 0 1 5 0 0 1 ⎦ ⎥ ⎤ = L
Inverse를 적용해보니 A = L U A=LU A = L U L L L
그리고 10도 사라졌다.
따라서
E − 1 E A = E − 1 U E^{-1}EA = E^{-1}U E − 1 E A = E − 1 U A = E − 1 U = L U A = E^{-1}U = LU A = E − 1 U = L U 수식 과정을 이해할 수 있다.
하지만 위에서 했던 모든 A = L U A=LU A = L U L L L L L L
그렇다면 n x n 행렬에 대해서 행렬의 연산 수는 얼마나 될까?
[ a . . . . . . . . . . . . . . . − . . . ] → [ a . . . 0 . . . . . . . . . . . 0 . . . ] \begin{bmatrix} a & . & . & . \\ . & . & . & . \\ . & . & . & . \\ . & . & . & . \\ - & . & . & . \end{bmatrix} \rightarrow \begin{bmatrix} a & . & . & . \\ 0 & . & . & . \\ . & . & . & . \\ . & . & . & . \\ 0 & . & . & . \end{bmatrix} ⎣ ⎢ ⎢ ⎢ ⎢ ⎢ ⎡ a . . . − . . . . . . . . . . . . . . . ⎦ ⎥ ⎥ ⎥ ⎥ ⎥ ⎤ → ⎣ ⎢ ⎢ ⎢ ⎢ ⎢ ⎡ a 0 . . 0 . . . . . . . . . . . . . . . ⎦ ⎥ ⎥ ⎥ ⎥ ⎥ ⎤
위 과정에서 연산은 얼마나 많이 필요할까?
아마 10 0 2 100^2 1 0 0 2
그리고 다음 과정으로,
[ a . . . 0 . . . . . . . . . . . 0 . . . ] → [ a . . . 0 b . . . 0 . . . . . . 0 0 . . ] \begin{bmatrix} a & . & . & . \\ 0 & . & . & . \\ . & . & . & . \\ . & . & . & . \\ 0 & . & . & . \end{bmatrix} \rightarrow \begin{bmatrix} a & . & . & . \\ 0 & b & . & . \\ . & 0 & . & . \\ . & . & . & . \\ 0 & 0 & . & . \end{bmatrix} ⎣ ⎢ ⎢ ⎢ ⎢ ⎢ ⎡ a 0 . . 0 . . . . . . . . . . . . . . . ⎦ ⎥ ⎥ ⎥ ⎥ ⎥ ⎤ → ⎣ ⎢ ⎢ ⎢ ⎢ ⎢ ⎡ a 0 . . 0 . b 0 . 0 . . . . . . . . . . ⎦ ⎥ ⎥ ⎥ ⎥ ⎥ ⎤
위 과정에서는 연산이 얼마나 많이 필요할까?
아마 9 9 2 99^2 9 9 2
이런 식으로 하다보면 n x n 행렬의 Elimination 과정에서 총 연산 수는 다음과 같이 나올 것이다.
n 2 + ( n − 1 ) 2 + . . . + 2 2 + 1 2 ≈ 1 3 n 3 n^2 + (n-1)^2 + ... + 2^2 + 1^2 \approx \frac{1}{3}n^3 n 2 + ( n − 1 ) 2 + . . . + 2 2 + 1 2 ≈ 3 1 n 3 또 다른 예시로 n x n 행렬과 n x 1 행렬 간의 곱을 생각해보자.
[ . . . . . . . . . . . . . . . . . . . . ] [ . . . . . ] \begin{bmatrix} . & . & . & . \\ . & . & . & . \\ . & . & . & . \\ . & . & . & . \\ . & . & . & . \end{bmatrix} \begin{bmatrix} . \\ . \\ . \\ . \\ . \end{bmatrix} ⎣ ⎢ ⎢ ⎢ ⎢ ⎢ ⎡ . . . . . . . . . . . . . . . . . . . . ⎦ ⎥ ⎥ ⎥ ⎥ ⎥ ⎤ ⎣ ⎢ ⎢ ⎢ ⎢ ⎢ ⎡ . . . . . ⎦ ⎥ ⎥ ⎥ ⎥ ⎥ ⎤
위 행렬곱 연산 수는 얼마나 될까?
아마 n 2 n^2 n 2
이처럼 행 간의 교환없이 단순 계산을 하면 계산 리소스가 많이 필요할 수 있다.
3 x 3 행렬을 예시로 들어보자.
[ 1 0 0 0 1 0 0 0 1 ] \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix} ⎣ ⎢ ⎡ 1 0 0 0 1 0 0 0 1 ⎦ ⎥ ⎤ [ 1 0 0 0 1 0 0 0 1 ] , [ 0 1 0 1 0 0 0 0 1 ] , [ 0 0 1 0 1 0 1 0 0 ] , [ 1 0 0 0 0 1 0 1 0 ] , [ 0 1 0 0 0 1 1 0 0 ] , [ 0 0 1 1 0 0 0 1 0 ] \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 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 \\ 0 & 1 & 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} ⎣ ⎢ ⎡ 1 0 0 0 1 0 0 0 1 ⎦ ⎥ ⎤ , ⎣ ⎢ ⎡ 0 1 0 1 0 0 0 0 1 ⎦ ⎥ ⎤ , ⎣ ⎢ ⎡ 0 0 1 0 1 0 1 0 0 ⎦ ⎥ ⎤ , ⎣ ⎢ ⎡ 1 0 0 0 0 1 0 1 0 ⎦ ⎥ ⎤ , ⎣ ⎢ ⎡ 0 0 1 1 0 0 0 1 0 ⎦ ⎥ ⎤ , ⎣ ⎢ ⎡ 0 1 0 0 0 1 1 0 0 ⎦ ⎥ ⎤ 그렇다면 만약 4 x 4 행렬에 대해서 P P P
아마 4 ! 4! 4 !
그리고 n x n 행렬에 대해서 P P P n ! n! n !
