[MIT Linear Algebra] 4. Factorization into A = LU

• 본 게시글은 Gilbert strang 교수님의 Linear Algebra, MIT 정리글입니다.
• 개인적인 공부를 위해 작성한 글이며, 잘못된 내용이 존재할 가능성이 있습니다.
• 잘못된 내용, 오타는 지적해 주시면 감사하겠습니다.

강의링크:

https://www.youtube.com/watch?v=MsIvs_6vC38

---

이번 강의에서 살펴볼 내용은 다음과 같다.

• Inverse of 
• product of elimination matrics
• A=LU (no row exchanges)

 

강의 초반, 다음 성질을 설명한다.

 

 

다음으로 왜 A=LU를 사용하는지 살펴본다.

먼저 다음 식을 만족하는 Elimination matrix가 있다고 생각해 보자.

 

 

 

만약 기존의 Elimination matrix만을 사용해 보자.

 

 

얼핏 보면 전혀 문제가 없다. 사실 문제는 없다.

직관적이지 않다는 점을 제외하고는.

좌측의 식에는 존재하지 않던 새로운 인자, 10이 등장하였기 때문이다.

 

그럼 만약 reverse oreder을 사용하는 inverse의 성질을 활용하면 어떨까?

 

 

우측의 식은 Lower matrix, L이다.

그리고 매우 직관적이다. 

Elimination matrix의 inverse를 구할 때는 부등호만 변경하면 되므로(항상 이런 것인지는 모르겠음) 간편하고,

우측의 결과도 좌측에 존재하는 인자로만 구성되어 있다.

 

결론은 다음과 같다.

A=LU

If no row excahges, multipliers go directly into L

 

product of Elimination matrix을 그대로 사용하는 것이 아니라,

inverse를 통해 변환해서 활용하면 계산이 편하고, 분석이 용이해진다.

 

그럼 약간은 번외의 질문을 생각해 보자.

"How many operations on nxn matrix A?"

선형대수를 처음 접하는 사람에게는 매력적인 질문이 아닐 수 있다.

그러나 AI 등 실제로 행렬을 활용하는 사람에게는 매우 중요한 질문이다. 

 

Elimination을 진행하는 과정에서 다음과 같은 연산이 필요하다. 자세한 내용은 강의의 26분부터 시청 바란다.

 

 

위 operations은 matrix A에만 필요한 연산량이고,

실제로는 AX=b의 matrix b에도 연산이 필요하니(n 제곱), 더 많은 연산량이 요구될 것이다.

 

그래서 Row exchange가 필요하다.

그리고 Row excahnge는 Permutation matrix를 활용하면 가능하다.

 

참고 Permutation matrix는 다음의 성질을 지니고 있다.