[선형대수] 4. Factorization into A=LU (LU 분해)

1. Inverse of AB, A^T

 

먼저, 행렬 AB의 역행렬과 행렬 A의 전치행렬 A^T의 역행렬을 알아보자.

 

1) (AB)^-1 (단, A^-1 과 B^-1 가 존재할 때)

 

(AB)(B^-1A-^-1) = I

(B^-1A^-1)(AB) = I

 

---> 즉, 곱의 역행렬은 순서가 뒤바뀐 채로 역행렬을 취해주면 된다.

 

 

2) (A^T)^-1 (단, A^-1 가 존재할 때)

 

AA^-1 = I 에서 양변 모두 Transpose 하면,

 

(A^-1)^TA^T = I 

 

이때, (A^-1)^T 가 A^T의 역행렬이므로 

 

(A^T )^-1 = (A^-1)^T

 

---> 즉, 전치와 역행렬은 서로 교환이 가능하다.

 

 

 

 

 

2. Factorization into 'A=LU'

 

 

위처럼 소거법에서 사용했던 행렬 E의 역행렬을 구해 A = E^-1U 의 형태로 만들어 주는 것을 LU분해(LU-Decomposition)라고 한다.

 

이때, E의 역행렬(모든 E의 역행렬들의 곱)을 행렬 L로 나타낸다. E의 역행렬을 구하는 방법은 소거법을 설명하는 글에서 다룬 적 있다.

 

 

또한, 필요에 따라 한 단계 더 나아가 행렬 U에서 대각 성분이 pivot으로만 이루어진 대각행렬 D을 분해할 수도 있다.

 

방법은 pivot이 속해있는 행을 pivot 값으로 나누어준다고 생각하면 된다.

 

 

 

 

 

이제 A_3x3 행렬을 통해 LU분해를 알아보도록 하자.

 

소거법에 의해서 행렬 A에 총 3번의 소거 행렬을 곱해 행렬 U를 얻었다고 해보자. 이때, 행 교환은 없었다고 하자.

 

E₃₂E₃₁E₂₁A = U   ------   (1) EA = U 형태

 

식 (1)을 역행렬을 이용해 다시 표현하면,

 

A = E₂₁^-1E₃₁^-1E₃₂^-1U   ------   (2) A = LU 형태

 

식 (1)과 (2) 중 어느 것이 더 유용할까? 아래의 예를 통해 비교할 수 있다.

 

 

A와 U의 관계를 이해하기에 식 (2)가 더 유리하다. 

 

식 (1)은 소거 행렬들의 곱에 의해서 행렬 E의 3행 1열 성분이 10이 되어 행렬 EA를 계산하기 복잡하지만,

 

식 (2)는 소거 행렬들의 역행렬의 곱으로서 L이 multipliers(2, 5)를 위치 그대로 반영하고 있음을 확인할 수 있다.

 

---> 즉, 행렬 L을 찾고 싶다면 multiplier들이 무엇이었는지 알아두기만 하면 된다.

 

 

 

 

 

그렇다면, A_nxn 행렬의 경우에는 몇 번의 (행을 곱하고 더하는) 작업이 필요할까?

 

 

소거법을 적용해 행렬 A를 상삼각행렬로 만들어 준다고 했을 때 약 1/3*n³번의 작업이 필요하다고 추론할 수 있으며,

 

벡터 b의 경우, 약 n²번의 작업이 필요하다고 추론할 수 있다.

 

 

 

 

 

3. Permutation

 

지금까지는 소거법을 적용할 때 행간의 교환(row exchange)은 고려하지 않았다. 행렬 A_3x3에 대해 행간 교환을 하는 방법을 알아보자.

 

그전에, 총 몇 가지의 방법이 있을지 떠올려 보면 도움이 된다.

 

 

총 6가지의 방법이 있으며 자세한 사항은 다음과 같다.

 

1) I : 교환하지 않는다. (단위행렬)

2) P₁₂ : 1행과 2행을 교환한다.

3) P₁₃ : 1행과 3행을 교환한다.

4) P₂₃ : 2행과 3행을 교환한다.

5) Cycle I : 1행 -> 3행, 2행 -> 1행, 3행 -> 2행

6) Cycle Ⅱ : 1행 -> 2행, 2행 -> 3행, 3행 -> 1행

 

위 행렬들은 다음과 같은 특이사항이 있다.

 

▶  모두 전치행렬이 곧 역행렬이다. 

▶  I, P₁₂, P₁₃, P₂₃은 자기 자신이 역행렬이다.

▶  Cycle I, Cycle Ⅱ은 서로가 서로에 대한 전치행렬이자 역행렬이다.

 

 

 

---

 

 

공부한 영상 : MIT 18.06 Linear Algebra, Spring 2005 - 4. Factorization A=LU

링크 : https://youtu.be/MsIvs_6vC38

소개 : Gilbert Strang 교수님의 MIT 선형대수학 강의(2005)

 

MIT 18.06 Linear Algebra, Spring 2005