이번 포스팅에선 A=LU 분해(LU Decomposition)에 대해 알아보겠다. (LU Factorization이라고도 불린다. 그러나 앞으로 LU Decomposition이라 표현하겠다)
쉽게 말해 어떤 행렬 A가 있을 때, 이를 하삼각 행렬(Lower triangular matrix)과 상삼각 행렬(Upper triangular matrix)의 곱으로 분해하여 나타내는 것을 의미한다. A=LU에서 L과 U는 바로 Lower와 Upper의 처음 이니셜만 따서 표현한 것이다.
LU Decomposition은 가우스 소거(Gauss Elimination)에 의한 Elimination 행렬 형태로 볼 수 있으며, 때때로 치환행렬(permutation matrix, ※Lecture 2 참조)을 포함하기도 한다. 컴퓨터는 square 형태의 선형 방정식을 계산할 때 이 LU Decomposition을 사용하며, 역행렬(Inverse Matrix)을 계산하거나 행렬식(determinant)을 계산할 때 필요한 주요 과정이다.
1. 행렬곱셈의 Inverse
LU Decomposition을 알아보기 전에 먼저 행렬곱셈의 Inverse에 대해 잠깐 살펴보고 가도록 하자. LU Decomposition의 이해를 돕기 위함이다.
어떤 행렬 A가 있고 그의 역행렬을 알고 있을 때, 우리는 이 역행렬을 곱하면 단위행렬이 되는 것을 알고 있다. 이때 역행렬을 A의 왼쪽, 혹은 오른쪽에 곱해도 그 결과는 같다.
그렇다면 아래와 같이 non-singular이고 정방행렬(square matrix)인 A와 B가 있다고 가정하자. 이 두 행렬의 곱셈 AB의 뒤에 역행렬을 곱해 단위 행렬(Identity matrix)을 얻고자 할 때, 우리는 빈 칸에 들어갈 역행렬을 어떻게 곱해야 하는가? 식(1)과 같이 역행렬을 순서대로 곱해야 하는가?
정답은 반대의 순서로 역행렬을 곱해줘야 한다. 즉 B의 역행렬을 먼저 곱해주고 그 다음 A의 역행렬을 곱해줘야 한다. 아래 식 (3)-1을 보자. B와 B의 역행렬이 먼저 곱해져서 단위 행렬이 만들어진다. 이때 단위 행렬은 어디에 곱해도 결과는 변하지 않으므로 무시해도 된다. 결국 A와 A의 역행렬과의 곱이 되고 답은 단위행렬이 만들어진다. 식 (3)-2와 같이 순서가 바뀌어도 결과는 마찬가지다.
결국 단위행렬을 만들기위해 역행렬을 곱해줄 때에는 각 행렬의 역행렬이 본래 자신의 행렬과 붙을 수 있게, 즉 원래 행렬 곱셈의 반대 순서로 역행렬을 곱해주면 된다.
- Transpose:
이번엔 행렬 곱셈에 대한 전치(Transpose)에 대해 알아보자. 이후에 더 자세히 다루겠지만 transpose라는 것은 row의 원소들이 column이 되고, column의 원소들이 row의 원소가 되는 것이다. 쉽게 말해 식(4)와 같이 대각선을 중심축으로 행렬을 180도 돌려서 뒤집는 것이다.
그렇다면 행렬 곱셈에 이러한 transpose를 적용하면 어떻게 될까? 아래와 같이 정방행렬인 A와 A의 역행렬을 곱해서 단위 행렬을 만드는 식이 있을 때, 이 식을 transpose시켰다고 했을 때 결과는 식(5)의 마지막 줄과 같이 행렬 곱셈의 순서가 뒤바뀌게 된다.
우변의 I는 그대로 I가 되고 좌변의 A와 A inverse는 곱하는 순서가 반대로 된다.
또한 식(5)의 마지막 줄에서 A의 역행렬의 transpose는 => A의 transpose의 역행렬로 바꿔 쓸 수 있다. 단 이 규칙은 각각의 단일 행렬에 대해서만 적용된다. 식 (6)을 참고하자.
2. LU Decomposition
- What and why Decomposition?:
Decomposition(Factorization)이라는 것은 말 그대로 분해하는 것을 의미한다. 쉽게 말해 어떤 시스템 혹은 데이터를 표현한 행렬 A를 인수분해 한다는 뜻이다. 우리가 중고등학교때 배우던 그 인수분해처럼 말이다. 위키 사전에는 이 행렬 분해(Matrix Decomposition)의 정의를 다음과 같이 정리하였다.
선형대수에서 Matrix Decomposition은 어떤 행렬(Matrix)을 여러 행렬들의 곱으로 표현하는 것을 의미한다.
출처: (https://en.wikipedia.org/wiki/Matrix_decomposition)
그렇다면 이러한 Matrix Decomposition은 왜 하는 것일까? 그 해답은 바로 우리가 중학교때 배웠던 인수분해를 하는 이유와 같은 맥락이다. 우리가 어떤 방정식을 인수분해 하는 이유는 바로 그 방정식의 해를 구하기 위해서다. 혹은 해를 좀 더 쉽게 구하기 위해서, 방정식을 좀 더 알아보기 쉽게 하기 위해서, 특수한 상황에서 문제를 풀기 쉽게 하도록 하기 위해서 등이다.
Matrix Decomposition도 마찬가지이다. (http://www.ece.northwestern.edu/~mya671/files/Matrix_YM_.pdf) 에선 Matrix Decomposition의 목적을 크게 두 가지라고 하였다. 첫 번째는 계산의 편리함(computational convenience), 두 번째는 분석적 용이성(analytic simplicity)을 위함이다. 결국 Matrix Decomposition을 하는 이유는 계산을 좀 더 편리하게 하고 어려운 문제를 쉽게 풀기위해, 시스템 행렬을 단순화시켜 표현하여 분석을 용이하게 하기 위함이다.
행렬 분해는 다양한 방법들이 존재한다. SVD(Singular Value Decomposition), QR Decomposition 등등 다양한 방법들이 존재하며, 각 방법들은 각자 고유의 분해 특성들을 가지며 다양한 문제를 푸는데 사용된다. 여기서 우리는 행렬 분해 방법들 중 가장 기본적인 형태인 LU Decomposition에 대해 알아보자.
- LU Decomposition(Factorization):
어떤 행렬 A가 있고 이 행렬은 역행렬을 가질 수 있는 정방행렬이고, 역행렬을 구하기 위해 소거를 하는 과정에서 Row exchange도 필요 없는 아주 좋은 형태의 행렬이 있다고 가정해보자.
우리는 A에 소거법을 적용해서 최종적으로 U행렬을 만드는 것을 지난 포스팅(Lecture 2)에서 배웠다. 여기서 우리는 A와 U사이의 연결 고리를 알아야 한다. 즉 A가 U와 어떻게 연결이 되는지 말이다. 식으로부터 짐작하신 분들도 있겠지만, 바로 L행렬이 이 연결고리가 된다.
이 연결고리인 L행렬이 어떻게 만들어 지는지 실제 계산을 통해 알아보자.
아래와 같이 2x2크기인 비 특이행렬(non-singular Matrix) A가 있다.
자 이제 A행렬을 소거하여 만들어지는 상삼각행렬(Upper Triangular Matrix)인 U행렬을 만들기 위해 E21행렬을 만들어보자. (E21은 A의 row2, column1의 원소인 8을 제거하기 위한 Elementary or Elimination Matrix라는 의미다)
E21행렬은 어떻게 만드는가? 일단 A에서 pivot은 2이다. 이 pivot의 column에서 바로 아래에 있는 원소 8을 제거해야 하는데 바로 위의 pivot인 2와 딱 4배 차이가 난다. 따라서 row1[2 1]에 4를 곱한다음 row2[8 7]에서 row1을 뺀 결과값을 row2에 대입하면 될 것이다. 즉 아래 식과 같다.
그렇다면 이렇게 되기 위해선 E21행렬의 원소들이 어떻게 배치되어야 할까?
pivot이 있는 A의 row1은 그대로 유지되어야 한다. E21의 row1은 그렇다면 1*[2 1] + 0*[8 7]이므로 [1 0]이 되어야 한다.
E21의 row2는 어떻게 되어야 할까? -4*[2 1] + 1*[8 7] 이므로 [-4 1]이 되어야 할 것이다. 결국 식 (9)와 같이 E21이 만들어 질 것이다.
(※소거와 관련된 내용은 Lecture 2참고)
자 이렇게 만들고 보니 처음에 구하고자 했던 A=LU와는 다른 형태지만 어떤 처리를 하면 뭔가 나올 것만 같다. 눈치 채셨는가?
그렇다. 그것은 바로 좌변과 우변의 왼쪽에 E21의 역행렬을 각각 곱해주면 될 것이다. 즉
결국 소거행렬(Elimination Matrix) E21의 역행렬이 L행렬인 것이다. 이때 L은 하삼각행렬(Lower Triangular Matrix)의 형태를 띄게 된다.
이제 E21역행렬을 구하면 된다. E21의 역행렬은? 바로 -4의 부호만 +로 바꿔주면 된다. 역행렬이라는 것이 곱해서 단위행렬을 만들어야 하기 때문이란 것을 안다면 쉽게 유추할 수 있다. 방금 전 E21을 만들 때와 같이 -4를 소거하여 0으로 만들 방법을 생각하면 쉽게 만들 수 있다.
이렇게 구한 E21의 역행렬은 결국 L이 되고 L과 U를 실제로 곱해보면 A가 나오는 것을 확인할 수 있다. 식 (11)은 A=LU를 나타낸 것이다.
- LDU Decomposition:
어떤 경우에 이 Pivot들만 따로 떼어서 분해해야 하고 싶을 때도 있다. U행렬은 대각선으로 두 개의 pivot인 2와 3을 가지고 있다. 첫 번째 pivot이 2, 두 번째 pivot이 3이다. 만약 이 pivot들만 따로 분리하여 행렬을 만들고 싶을 때 우리는 다음과 같이 할 수 있다.
U행렬에서 각 pivot이 속해있는 row를 해당 pivot으로 나누어준다. 그 결과값을 새로운 U의 각 row에 넣고 pivot들만 대각선으로 나열되어 있는 행렬을 써주면 된다. 즉 아래 그림과 같이 하면 된다.
연산 자체가 간단하기 때문에 따로 부연설명은 하지 않겠다.
이렇게 해서 만들어진 행렬의 조합을 우리는 LDU Decomposition Matrix라 한다. 여기서 D는 Diagonal Matrix의 뜻이며 대각선 방향의 원소만 가지고 있는 대각 행렬을 의미한다. 왼쪽엔 하삼각행렬(Lower Triangular Matrix), 가운데는 Pivot들만 있는 대각행렬(Diagonal Matrix), 우측엔 상삼각행렬(Upper Triangular Matrix)이 위치해있는 형태이다.
- 3x3 case:
이제 3x3크기의 3차원 행렬을 생각해보자. 3x3크기의 행렬 A가 있다고 가정해보자. 이 행렬을 소거하기 위해 먼저 곱해야 할 E행렬은 E21일 것이다. 그 다음으로 E31, E32순으로 곱해서 소거를 해야 한다는 것을 이미 배웠다. 이때 Row exchange는 필요 없는 이상적인 경우로 가정한다. 이를 식으로 나타내면 아래와 같을 것이다.
그 다음 단계는 왼쪽의 E행렬들을 없애서 A=의 꼴로 만들어야 한다. 식 (10)을 참고하여 식 (13)의 왼쪽에 E32, E31, E21순으로 역행렬들을 곱하여 아래와 같은 식으로 만들어준다. 결국 식의 우변은 E21*E31*E32의 역행렬들의 곱이 L이 된다.
우리는 식 (13)에 각 E의 역행렬들을 곱하여 식 (14)의 A=LU형태의 식을 만들었다. 즉 행렬 A와 U간의 연결고리인 L을 만들어 낸 것인데, 사실 (13)의 앞에 곱해진 E도 A와 U의 연결고리라고 볼 수 있다. 결국 U를 만들기위한 방법은 E와 L 두 가지가 있는 셈인데, 결론적으로 보면 이 두 가지 방법중 L이 더 좋은 형태라고 볼 수 있다.
다시말하면
의 형태보다
의 형태가 더 좋은 형태이다.
지금부터 왜 두 번째 형태가 더 나은지 설명하겠다.
위에서 살펴봤던 2x2인 경우에는 E행렬이 단 한개라서 별다른 문제는 없다. 그러나 3x3은 다르다. 다음 A행렬을 보자.
Linear Algebra Lecture 2를 참고하여 A 소거법을 적용해보자. 결과는 아래 식 (16)과 같아진다. 여기서 E31은 단위행렬이 되는데, 이렇게 되면 E31은 곱셈에서 무시해도 무방하다. 참고로 소거법의 특성상 E행렬들은 언제나 하삼각행렬의 형태이다. 이렇게 나오는 이유는 소거 과정에서 pivot의 row는 소거하지 않기 때문에 이와 같은 형태가 나오는 것이다.
어쨋든 E행렬을 살펴보자. E32의 -5, E21의 -2는 E행렬에서 각자의 위치에 그대로 위치해있고 E행렬의 row3, column1의 자리에 10이라는 새로운 숫자가 생겨났다. 이것이 의미하는 것이 무엇일까? (-5와 -2는 소거 과정에서 pivot row에 곱해지는 multiplier임을 기억하자.)
그 다음으로 L을 살펴보자. E21 역행렬의 2, E32 역행렬의 5가 L에서 각자 위치에 그대로 위치해 있고 따로 추가되는 숫자는 없다. 이것이 의미하는것이 무엇일까?
행렬 E를 A에 곱하게 되면 E의 10은 A의 row1에 곱해지게 된다. 즉 10이라는 숫자가 A의 row1에 커다란 영향을 미친다는 것이다. 물론 답은 U가 그대로 나오게 된다. 그러나 그 연산 과정에서 A에 뭔가 큰 영향을 미치게 된다.
반면 L의 경우엔 따로 추가되는 숫자 없이 2와 5가 각자의 자리에 위치한 상태로 L이 계산된다. 즉 10과 같이 뭔가 방해를 하는 숫자를 만들어내지 않는다는 것이다. EA=U와 달리 A=LU는 A를 신경쓰지 않아도 되는 것이다. 결국 A와 U의 연결고리로써 E보다는 L이 좀 더 나은 표현이다.
A=LU Decomposition에서
만약 행 교환(row exchanges)이 없다면, 소거에 사용되는 multiplier들은 L행렬의 각자 위치에 그대로 들어간다.
- Permutations:
지난 포스팅에서 잠깐 다룬적이 있던 치환행렬(Permutation Matrix)을 다시 살펴보자. 지금까지는 행 교환(row exchanges)이 필요 없는 경우를 가정하고 LU Decomposition을 설명했다. 그러나 행 교환이 필요한 경우가 반드시 생긴다. 이렇게 행 교환이 필요한 경우 사용하는 방법이 치환행렬을 곱해주는 것이다.
3x3 치환행렬을 살펴보자.
비록 아무런 변화가 없긴 하지만 단위행렬도 치환행렬의 한 종류이다. n=3인 정방행렬일 때 치환행렬의 종류는 어떤 것들이 있을까?
먼저 P12를 생각해볼 수 있다. P는 Permutation의 P를 따온 것이고 12는 row1와 row2를 교환한다는 뜻이다.
P13, P23을 어렵지않게 생각할 수 있는데, 이것 말고도 조합이 더 있다. 아래 식 (16)을 보자.
P23에 P13을 곱한 행렬, 그리고 P23에 P12를 곱한 행렬을 생각할 수 있다. 각 치환 행렬을 row로 봤을 때, 각 row가 단위 행렬과 비교해서 몇 번째 줄에 위치했는지를 살펴보면 어느 row로 바뀌는지 쉽게 유추할 수 있다.
이러한 치환 행렬의 조합의 개수는 어떻게 계산할 수 있을까? 바로 n!(factorial)로 계산한다. 즉 n=3일 경우, 3x2x1=6가지의 조합이 나오는 것이다.
치환 행렬은 앞서 말했듯 row를 바꿔주는 역할을 하는 것이다. 그렇다면 다시 원래대로 되돌려 놓으려면 어떻게 해야 할까? 바로 역행렬을 곱해주면 되는데, 사실 원래 행렬과 역행렬은 같다. 왜냐하면 P12가 row1과 row2를 바꾸는 치환 행렬일 때 다시 원래대로 돌려 놓으려면 똑같이 row1과 row2를 바꿔주면 되기 때문에 다시 P12를 곱해주면 된다. 실제 계산해봐도 같은 결과가 나오는데, 이는 치환 행렬 자체가 대각 원소들을 기준으로 좌우가 대칭이기 때문이다. 이런 좌우 대칭인 경우 역행렬은 전치(Transpose)로 구할 수 있다.
또한 P13P23은 P12P23과 역행렬 혹은 전치 관계인 것을 알 수 있다.
우리는 행 교환이 필요한 A=LU Decomposition을 할 때 이러한 치환 행렬을 곱하여 PA=LU와 같은 꼴로 Decomposition을 할 수 있다.
3. MATLAB 활용법
LU Decomposition을 MATLAB을 이용해 간단히 구할 수 있다. 아래는 위의 식 (15)를 MATLAB으로 구현한 코드이다.
위 코드를 실행시키면 아래와 같은 결과가 나온다.
위 결과에서 ans는 앞에서 계산한 L과 U를 곱하여 나온 결과 행렬이다. 원래의 A행렬과 똑같이 나오는 것을 볼 수 있다.
MATLAB에서는 LU Decomposition을 위한 함수를 제공한다. 아래 코드는 MATLAB에서 제공하는 함수를 이용해 LU Decomposition을 수행하는 코드이다.
함수 이름은 lu()이고 괄호안에 Decomposition을 할 함수를 파라미터로 넣으면 된다. 이때 좌변에 대괄호를 이용하여 출력 인수들을 정의해 줘야 한다. 첫 번째 방법은 L과 U만 출력 인수로 정의해준 것이다. 이에 대한 결과는 아래와 같다.
결과를 보면 L의 경우 하삼각행렬 형태가 아닐 것이다. 왜 이렇게 나오는지에 대해서 이해하기 위해선 우선 다음의 정의를 이해해야 한다. 선형 시스템(Linear System)의 표현은 유일하지 않다. 아래 식을 보자.
위의 식에서 첫 번째 식과 두 번째 식은 완전히 똑같은 시스템을 표현하고 있다. 여기서 좌변의 행렬의 행이 바뀌면 우변의 결과 벡터도 똑같은 순서로 행이 교환된다는 것을 기억하자.
위의 개념을 생각했을 때, LU Decomposition은 사실 일반적으로 PA=LU와 같이 표현할 수 있다. 여기서 P는 치환 행렬(Permutation Matrix)를 의미한다. MATLAB에서 [L U] = lu(A)와 같이 L과 U만 출력인수로 정할 경우, L은 아래 식과 같이 정의 되어 나오는 것이다.
(P는 대칭 행렬(Symmetric Matrix)이기에 역행렬은 전치(Transpose)와 같다)
즉 [L U] = lu(A)로 구한 L은 사실은 P'L인 것이다. 이는 L과 U를 곱했을 때 원래의 A행렬 형태가 나오도록 만들기 위해 치환 행렬을 L에 미리 곱해준 것이라 생각하면 된다. ans는 lu()함수로 구한 L과 U를 곱해서 나온 결과이고 원래의 A와 정확히 일치하는 것을 볼 수 있다.
출력 인수를 [L U P] = lu(A)와 같이 L, U, P 세 개로 정의할 경우, L은 우리가 생각하는 하삼각행렬의 형태, 즉 P의 역행렬이 곱해지지 않은 형태로 L이 계산된다. 아래는 이에 대한 결과이다.
L은 하삼각행렬, U는 상삼각행렬, P는 치환행렬이다. 즉 PA=LU형태로 계산 결과가 나오는 것이다. 이렇게 계산된 결과값을 이용해서 PA와 LU를 실제로 비교해보자. 정확히 같은 값이 나오는 것을 알 수 있다.
그런데 우리가 손으로 계산한 결과들과는 실제로 값이 다르다. 이는 내부 계산과정에서 수치적으로 최적화된 계산 알고리즘을 통해 Decomposition을 하기 때문에 알고리즘마다 값이 약간씩 다르게 나올 수 있다. 어쨋든 결과적으로는 맞게 분해가 된 것이 맞다.
MATLAB에서 제공하는 LU Decomposition함수는 이 외에도 다양한 파라미터들을 설정할 수 있다. 자세한 내용이 궁금하다면 구글에 검색을 해보거나 help명령어, 혹은 MATLAB 스크립트의 lu()함수에 마우스 커서를 놓고 Ctrl+D를 누르면 상세한 도움말을 볼 수 있다.
4. 마치며
이번 포스팅에선 어떤 시스템 행렬 A를 L(Lower Triangular Matrix)과 U(Upper Triangular Matrix)로 분해(Decomposition)하는 방법을 배웠다. 이를 통해 A와 U사이의 관계를 이어주는 L행렬을 정의할 수 있었고 L과 소거 행렬 E와의 관계를 확인할 수 있었다. 또한 Row exchange가 필요한 경우 사용되는 치환행렬(Permutation Matrix)을 공부했고 이에 대한 전치(Transpose)도 공부하였다. 다음 포스팅에선 이 치환 행렬과 전치에 대해 좀 더 알아보도록 하자.