[Linear algebra] 4. Factorization into A=LU

Lecture

https://ocw.mit.edu/courses/18-06-linear-algebra-spring-2010/resources/lecture-4-factorization-into-a-lu/

Lecture 4: Factorization into A = LU | Linear Algebra | Mathematics | MIT OpenCourseWare

 

Note

• A= LU 는 가장 간단한 Decomposition 형태로 elimination 과정에서 나온다. (no row exchange/permutation)
• elimination은 EA=U 형태로 나오는데 이 상태에서 좌우 lower triangle 형태인 E의 inverse를 취하면 A=LU형태가 되는 것.
• 한번 더 분해해서 A=LDU 형태로도 정리 가능.
  
  

• A=LU decomposition의 장점?
  
  첫째, L을 이용해 표현하면 elimination step에서 row의 영향력이 더 깔끔하게 보인다. 
  
  EA=U 형태에서 최종 E를 보면 elimination step이 얽혀진 형태여서 실제 elementary matrix들에 등장하지 않는 수들이 생겨 지저분한 형태가 된다. 예를 들어, 3x3 matrix에서 elimination을 진행한다고 했을 때, 3번째 row는 elimination이 끝난 새로운 2번째 row를 이용해 elimination을 한다. 최종 E에는 3번째 row가 1번째 row로부터 받는 영향까지 들어있어 새로운 수가 생긴다.
  위 사진 예시에서 실제로는 elimination에 사용되는 2와 5가 핵심이지만 최종 형태를 보면 10이 생겨있다. 하지만 L 형태로 표기하면 L의 row에는 그 값이 한 눈에 보인다. 실제 핵심수로만 구성된 matrix가 L이다.
  
  

• 둘째, elimination을 실제 구현할 때 (소프트웨어로 구현하거나 실제로 풀 때) operation 수를 크게 줄인다.
  
  elimination step에서 실제로 해야하는 operation 수를 보면 n x n matrix에 대해  n**2 + (n-1)**2 + ... + 1 으로 거의1/3 n**3이다. Ax=b를 푼다고 했을 때 좌측 A에 대한 cost 뿐만 아니라 b에 대한 cost도 column이 적다 뿐이지 같을 것이니 꽤 크다. 하지만 LU decomposition을 미리 해두면 A에 대한 cost는 그대로 겠지만 추후에 b에 대한 cost를 n**2로 낮출 수 있다. (증명이 복잡한가 그냥 점프해서 강의에서 말한다.)
• permutation matrix는 transposed matrix가 inverse matrix다.