선형대수학 [6], A=LU Factorization (LU분해)

지난 시간에는 정방행렬 A가 주어지면 A의 역행렬을 구하는 알고리즘에 대해 배웠습니다. 이번에는 정방행렬 A를 두 개의 삼각행렬로 분해하는 LU Factorization 알고리즘에 대해 배워보겠습니다.

우선 LU Factorization에 대해 배우기 위해서는 삼각행렬이 뭔지 알아야겠죠?

---

삼각행렬(Triangular Matrix)

삼각행렬은 행렬의 원소 가운데 대각 원소 위(또는 아래)의 원소가 모두 0인 행렬을 의미합니다.

예를 들면 아래와 같은 두 행렬은 모두 삼각행렬입니다.

이 중에서 0이 아닌 원소들이 위쪽에 존재하는 A의 경우 Upper Triangular Matrix라고 부르고, 아래쪽에 존재하는 B의 경우 Lower Triangular Matrix라고 부릅니다.

Upper Triangular Matrix의 경우 문자 로 표기하며 Lower Triangular Matrix의 경우 문자 로 표기합니다.

4번째 포스팅에서 설명드렸던 소거행렬의 경우에도 Lower Triangular Matrix에 속합니다. 대각 원소의 위에 있는 원소들이 모두 0이기 때문입니다.

두 번째 행에서 첫 번째 행에 k를 곱한 값을 빼주는 소거행렬을 다시 한번 살펴볼까요? 

여러개의 소거행렬을 곱하는 경우에도 마찬가지입니다. 소거행렬들의 곱은 반드시 Lower Triangular Matrix 형태로 나타나게 됩니다.

실제로 연산을 해보신다면 그렇게 되는 이유를 쉽게 짐작하실 수 있으리라 생각합니다.

---

LU Factorization (LU분해)

LU Factorization은 어려운 내용이 아닙니다. 임의의 정방행렬 가 주어지면, 이 행렬을 두 개의 삼각행렬(과)의 조합으로 나타낼 수 있다는 의미입니다.