MIT Linear Algebra, Lecture 4: A=LU Factorization

원문 : http://www.catonmat.net/blog/mit-linear-algebra-part-four/

강의 영상 : https://www.youtube.com/watch?v=5hO3MrzPa0A

이것은 MIT Linear Algebra 4번째 강의의 4번째 리뷰포스트 입니다. 이 포스트에서는 A행렬을 하부삼각행렬(Lower-triangular) L과 상부삼각행렬(Upper-triangular) U의 곱으로 인수분해 하는것 다시 말해 A=LU를 리뷰한다. 이 강의에서는 또한 행렬곱  A·B의 역을 찾는 방법, 전치행렬  A^T의 역을 찾는 방법 그리고 행렬들의 치환을 소개한다.

이전 시간에 했던 역행렬들로 잠깐 복습을 해보자. 행렬 A의 역은  A^-1이다. 그래서 A·A^-1을 같이 곱하는것은 단위행렬 I를 만든다.

기억할 또 다른 중요한 사실은 행렬 곱은 결합법칙이 성립한다는 것 그리고 정방행렬에서 오른쪽에 행렬곱을 할때 역행렬이 있는것과 왼쪽에 역행렬이 있는것은 모두 단위행렬 I이 계산된다는 것.

처음에는 행렬 곱 A·B의 역을 찾는 방법을 강의하는데 답은 단위행렬을 얻기위해서  무엇을  행렬곱 A·B 에 곱해야만 하는가를 추론하는 것으로 해결된다.  B^-1·A^-1을 해보자. 만약 이것이 A·B의 역이라면, 이것을 A·B의 좌측 부분과 우측부분 각각에 곱하여도 똑같이 단위행렬이 나와야 한다(역행렬의 property). 이를 테스트해 보자.

오른쪽 면 부터 : (A·B)·(B^-1·A^-1) 결합법칙이 가능하기 때문에, 괄호를 조정하면 A·(B·B^-1)·A^-1. 과 같다. B·B^-1 은 단위행렬이다. 그러므로 A·(B·B^-1)·A^-1 = A·I·A^-1 = A·A^-1 = I. 이 된다.

이제 왼쪽 면 :  (B^-1·A^-1)·(A·B). 역시 결합법칙이 가능하기 때문에,  B^-1·(A^-1·A)·B 이 되고 이전과 마찬가지로 A^-1·A은 단위행렬이 되므로 

B^-1·I·B is B^-1·B = I이 된다.

우리는 (A·B)의 역행렬을 찾았고 이는 (B^-1·A^-1)이다.

다음은 행렬 A의 전치행렬을 찾는 방법이다. 이 역시 추론으로 찾아보자. 일단 A·A^-1 = I를 보자. 우리는 양변을 전치를 해도 이 관계는 유지가 될 것이다. 만약 우리가 우변을 전치시킨다면, 우리는 같은 단위행렬을 얻는다.  I^T=I이기 때문이다. 그렇다면 좌변은 어떠한가?  좌변을 전치시키면 (A·A^-1)^T = (A^-1)^T·A^T 을 얻는다. 좌변은 여전히 우변과 같으므로  (A^-1)^T·A^T = I가 된다. 그러나 이 방정식에서  A^T의 역은 (A^-1)^T이 된다는것은 아주 명백하다. 우리는 그러므로 (A^T)^-1 = (A^-1)^T이 된다는것을 알 수 있다.

마지막으로 강의는 중심주제인 A=LU 분해 로 넘어 갑니다. 평소처럼, 주제를 예제로 설명한다.

2x2 행렬 A를 보자.

이제 2행 1열에 요소를 제거할 기본행렬(Elementary matrix, E) E₂₁를 찾아 보자. 첫행을 4로 곱하고 이를 2번째 행에 빼면 2행 1열에는 0이 된다.

오른쪽 항을 보자, 이것은 우리가 찾던 상부행렬 U (주대각선 아래의 모든 요소들은 0)이다. 

이제 만약 양변에 E₂₁의 역행렬을 곱한다면, 우리는  (E₂₁)^-1·E₂₁·A = (E₂₁)^-1·U를 얻는다. 그러나 (E₂₁)^-1·E₂₁는 단위행렬이다. 그러므로 A = (E₂₁)^-1·U 이다. 이 항등식으로부터, lower-triangular matrix L 은 단지 (E₂₁)^-1 이라는 것이 명백하다.

 

인수분해의 다른 형식은 A = LDU 이다. D는 축(Pivot)을 포함한 대각행렬 이다. 이것의 예제는 아래와 같다.

이제 우리는 3x3의 임의의 행렬 A를 가지고 있다고 생각해보자, 행렬 A를 upper-triangular matrix U로 줄이기 위해서, 우리는 처음에 2행 1열의 요소를 제거한다. 즉 우리는 A(왼편으로부터)를 제거행렬 E₂₁와 곱한다. 그리고 우리는 제거행렬E₃₁ 을 왼쪽에 곱하여 3행 1열의 요소를 제거합니다. 마지막으로, 우리는 제거행렬E₃₂ 을 곱하여 3행 2열의 요소를 제거한다.

E₃₂·E₃₁·E₂₁·A = U

이것은 E₃₂·E₃₁·E₂₁ 이의 역행렬이 lower-triangular matrix인 이 방정식을 따른다. 즉  L = (E₃₂·E₃₁·E₂₁)^-1 = E₂₁^-1·E₃₁^-1·E₃₂^-1 이다.

우리는 3x3 행렬의 인수분해를 찾아냈다.

A = E₂₁^-1·E₃₁^-1·E₃₂^-1·U = L·U

행렬들  L 과 U 를 찾는 알고리즘을 정리해서 말하면, 먼저 U 행렬을 찾기위해 소거법을 한다. 그리고 난  후 L을 찾기위해 U를 찾는것에 사용된 소거 행렬들의 역행렬을 양변에 집어넣는다. 사실상 이것은 더 쉽다. 소거행렬 E를 계속 유지시키거나 역행렬을 찾을 필요조차 없다. 여러분은 각 소거단계에서 사용된 승수들을 가지고 있으면 된다. 

다음은 소거법 알고리즘의 비용에 대해 다루어졌다.  2강에서 행렬의 왼쪽에 치환 행렬을 곱하는것은 이것의 행을 바꾼다는 것을 기억해라.

1. 치환행렬P에 대한 포인트는  P의 역행렬은 이것의 전치행렬이다. P^-1 = P^T 

2.  n_xn 행렬들에 대해 n! 치환행렬들이 있다.