Linear Algebra(18.06) - 4. Factorization into A=LU

이번강의 목표는 행렬 A를 L과 U의 곱으로 나타내는 방법을 배운다.

 

행렬 A와 B를 곱한 결과인 AB의 역행렬은 무엇일까? 

역행렬은 행렬의 곱 순서가 바뀌고 각 행렬을 역행렬 해주면 된다. 즉

\[(AB)^{-1} = B^{-1}A^{-1}\]

로 나타낼 수 있다.

 

역행렬은 왼쪽에 곱하나 오른쪽에 곱하나 I행렬이 나와야 하는데, 직접 오른쪽 왼쪽 각각 곱한 후,

안쪽부터 계산한후 나머지 부분을 계산해 주면 I행렬이 나온다.

 

그렇다면 역행렬의 전치행렬은 무엇일까?

전치행렬(Transpose Matrix)은 행과 열을 바꿔준 행을 말한다. 

 

위에서 보는대로 첫번째 식에서 전치를 해주면(T) 행렬 곱셈 순서가 바뀌고 각 행렬이 전치가 된다.

따라서 질문인 전치행렬의 역행렬은 빨간색으로 표시한 부분이 답이다.

 

메인 주제인 A=LU로 넘어가보자.

 

행렬 A가 다음과 같이 있을때, E행렬을 곱해 U행렬을 만드는 법을 배웠다.

그렇다면 A=LU의 형태를 만들기 위해서 어떻게 해야할까?

E21의 역행렬을 좌우변에 곱해주면 된다. 그러면 A와 U를 건드리지 않고 L을 만들 수 있다.

 

이때, 알수있는 사실은 L은 E21의 역행렬이라는 점이다.

(둘의 관계를 유심히보면 2행1열 원소인 -4가 4가 되었다, 즉 부호가 반대로 됨)

 

참고 - LU로 분해한 것을 다시 LDU'으로 분해할 수가 있다. D는 diagonal의 약자이다.

 

2 by 2 행렬을 알아봤다면, 이제 3 by 3 행렬에 대해 알아보자.

 

3 by 3 행렬은 총 3번에 걸쳐 U가 된다.

위와 마찬가지로 A=LU의 형태를 만들기 위해서 \[(E_{32}E_{22}E_{21})^{-1} = E_{21}^{-1}E_{22}^{-1}E_{32}^{-1}\]

을 좌우변에 곱해준다.

 

그렇다면 왜 EA=U보다 A=LU가 더 좋은지 살펴볼 필요가 있다.

(2 by 2 행렬 예시에서 E가 L이 될때 원소의 부호가 바뀌는 것과 관련이 있다.)

 

일반적인 방법으로는 E32, E21등의 행렬을 다 곱해 E를 만들 때, 10이라는 원소가 생긴다.

이는 상당히 불편하다.

하지만 L을 만들기 위해 역행렬들을 곱해주면 원소들을 그대로 합쳐주기만 하면 되고 10이나 다른 숫자들이 생기지 않는다.

 

길버트 교수님 "If no row exchanges, multiplier go directly into L"이라 표현하시며 설명하셨다.

 

 

그렇다면 이제 U를 만들기 위해 얼마나 많은 시간이 드는지 알아보자.

비용, 시간 즉 복잡도는 컴퓨터 전공과목중 알고리즘과 자료구조에도 나오는 개념인데 n과 관련된 함수로 나타낸다.

 

상수, n , n^2 , 2^n(지수) 등이 있다. 그래프를 그려보면 알겠지만, 지수가 가장 나쁘고, 상수가 가장 좋은 경우이다.

 

n이 100인경우에 대해 알아보자.

 

첫번째로 첫행에 적당한 수를 곱하고 빼는 과정이 원소의 개수만큼 있다 치면 100*100번만큼 연산이 실행된다.

그 다음으로 첫행과 열을 제외한 99 by 99 개의 원소에 대해, 이렇게 원소가 하나 남을때 까지 계산을 하다보면, 

 

n의 3제곱에 근접하는 연산횟수가 나온다는 사실을 알 수 있다

(급수를 이용하여 증명하지만 이번강에서는 메인이 아니기 때문에 사실만 알려주신다)

 

만약 옆에 column이 하나 더 있었다면 복잡도는 어떻게 될까?

1/3*n^3 + n^2이 되는데, n이 엄청나게 클 경우  뒤의 제곱은 무시할 수 있고, n세제곱의 복잡도를 가진다고 말한다.

 

Permutation 행렬에 대해 알아보자.

Permutation Matrix는 행을 바꿔주는 역할을 한다.

예를 들어 맨 마지막 행렬의 경우 I행렬의 1행을 2행으로, 2행을 3행으로, 3행을 1행으로 바꾼 행렬인데,

어떤 A에 곱해주면 1행이 2행, 2행이 3행, 3행이 1행으로 가게 된다.

 

P행렬의 경우 가장 중요한 성질은 역행렬이 전치행렬과 같다는 사실이다. 

즉, P에 P^T를 곱해주면 I가 된다.

 

또한 P행렬의 개수는 n!이다.