for textmining

LU factorization

|

이번 포스팅에선 LU 분해(LU factorization)에 대해 알아보도록 하겠습니다. 그에 앞서 LU factorization을 이해하기 위한 몇 가지 개념을 짚어보도록 하겠습니다. 이번 글은 고려대 박성빈 교수님한양대 이상화 교수님 강의를 참고했음을 먼저 밝힙니다. 그럼 시작하겠습니다.

확대행렬, 기본행연산, 가우스행렬, 행상등, 역행렬…

우선 선형대수학의 기초 용어 몇 가지를 정의하고 넘어가겠습니다. 아래의 경우에는 제 개인적으로도 정리용도로 남겨두는 것이니 선형대수학이 생소하신 분들은 스킵하셔도 무방할 것 같습니다.

확대행렬(augmented coefficient matrix) : 1차 연립방정식의 계수와 상수항으로 이뤄진 행렬

가우스행렬/행사다리꼴(row-echelon matrix) : 다음 세 가지를 만족하는 행렬이다. (1) 영행이 있다면 그것은 영행이 아닌 행의 아래에 있다. (2) 영행이 아닌 행의 첫번째 0이 아닌 원소를 그 행의 선도원소(leading entry)라 하고 모든 선도원소는 1이다. (3) 영행이 아닌 연속된 두 행이 있을 때 각각 i번째 행과 i+1번째 행이라 한다면 i번째 행의 선도원소는 i+1번째 행의 선도원소보다 왼쪽에 있다(역계단모양)

추축열(pivot column) : 가우스행렬의 각 행별로 선도원소에 대응하는 열을 추축열이라 한다. (pivot=non-zero) 추축열의 수와 방정식의 수가 같아야 연립방정식의 해가 유일하다. 추축열은 가우스행렬 열벡터들이 만드는 열공간의 기저가 된다.

기약가우스행렬(reduced echelon matrix) : 가우스행렬 A에 대하여 i번째 행의 선도원소가 j번째 열에 있다면 j번째 열의 다른 모든 원소는 0이다(가우스행렬이면서 선도원소 위, 아래 모든 수가 0인 행렬)

아래 예시에서 A, B는 가우스행렬, C, D는 기약가우스행렬입니다. 가우스행렬이든 기약가우스행렬이든 구하는 이유는 선도원소에 해당하는 연립방정식의 해를 바로 찾을 수 있기 때문입니다. C는 x, y, z, 상수에서 도출한 확대행렬에서 얻어진 기약가우스행렬이라고 한다면, x의 해는 4, y=7, z=-1입니다.

A에서 추축열은 1, 2열입니다. 선형대수학에서 추축열은 대단히 중요한 개념인데요, 해당 행렬의 열 벡터들이 만드는 열 공간(column space)기저(basis)가 되기 때문입니다. (열 공간과 기저는 추후에 살펴보겠습니다) A열의 추축열이 아닌 3열은 추축열인 1열을 2배한 뒤 2열을 더하면(선형결합으로) 만들어 낼 수 있습니다.

기본행연산(elementary row operation) : 임의의 확대행렬을 가우스행렬로 만드는 연산을 기본행연산이라고 한다. 기본행연산은 연립방정식의 소거법과 동일하다. 기본행연산에는 3개 방법이 있다. (1) 행 교환(row switching transformations) : 행 순서를 바꿔도 해(영공간)가 바뀌지 않는다. (2) 상수 곱셈(row-multiplying transformations) : 임의의 행 전체에 0이 아닌 상수를 곱해도 해가 바뀌지 않는다. (3) 한 행의 배수를 다른 행에 더함(row-addition transformations) : 임의의 행에 c배를 하고 이것을 다른 행에 더해도 해가 바뀌지 않는다.

행상등(row-equivalent) : 행렬 A에 기본행연산을 적용하여 행렬 B를 얻을 수 있는 경우 A와 B는 행상등이라고 한다.

단위행렬(identity matrix) : 주대각선이 전부 1이고 나머지 원소는 0을 값으로 갖는 n x n 정방행렬. 단위 행렬은 행렬곱셈의 항등원이다.

역행렬(inverse matrix) : n차 정방행렬 A에 대하여 AB=BA=I을 만족하는 행렬 B가 존재할 때 B를 A의 역행렬이라하고, 이때 A를 가역(invertible) 또는 정칙행렬이라 한다. 만일 이와 같은 B가 존재하지 않으면 A를 특이행렬(singular matrix)이라 한다.

위수(rank) : 행렬 A에 기본행연산을 적용하여 가우스행렬로 만들었을 때 영행이 아닌 행의 수를 위수라고 한다. 위수는 가우스행렬의 추축열의 수, 그리고 행렬 A의 차원(dimension) 수(기저의 수)와 일치한다.

자유변수(free variable) : 말 그대로 아무 값이나 가져도 되는 미지수. 임의의 가우스행렬 A의 위수가 열의 개수보다 작으면 자유변수가 1개 이상 존재한다.

기본행렬(elementary matrix) : 임의의 단위행렬에 대해 한 번의 기본행연산을 해서 얻어지는 행렬을 기본행렬(E)이라고 한다. 행렬 A에 E를 곱한 EA는 A에 기본행연산을 해서 얻은 행렬과 같다.

기본행렬과 관련한 예를 들어보겠습니다. 3x3 단위행렬의 첫번째 행에 3배를 해준 뒤 두번째 행에 더해준((3) 유형의 기본행 연산) 기본행렬 E는 아래와 같습니다. 이를 행렬 A에 같은 유형의 기본행연산을 한 직접 결과와 비교해 보면 정확하게 일치합니다.

이상 논의를 종합하여 정리해보겠습니다.

Thorem : 임의의 행렬 A와 B가 행상등하면 행렬 B에 대해 유한번의 기본행연산을 해서(=유한개의 기본행렬을 곱해서) A를 얻을 수 있다. 모든 기본행렬은 역행렬이 존재(가역)이고, 그 역행렬 또한 기본행렬이다. 행렬 A에 대해 유한 번의 기본행연산을 하여 단위행렬 I를 얻을 수 있을 때(=A와 I가 행상등일 때) 같은 기본행연산을 I에 대해 적용하여 A의 역행렬을 구할 수 있다. n x n 행렬 A가 가역(역행렬이 존재)이면 nx1 벡터 B에 대한 행렬방정식 AX=B는 유일한 해를 갖는다. n x n 행렬 A가 단위행렬 I와 행상등이면 AX=0의 해는 유일하다. AX=0의 해가 유일하면 행렬 A는 단위행렬 I와 행상등이다.

또한 mxn 행렬 A와 n차원 벡터 x, m차원 벡터 b로 이뤄진 ‘Ax=b’에 대하여 아래 명제들은 서로 동치(logical equivalence)입니다. 즉, 모든 명제가 동시에 참이거나 동시에 거짓입니다.

Ax=b는 유일한 해를 갖는다.

b는 계수행렬 A의 열벡터의 선형결합으로 표시된다.

계수행렬 A의 열벡터는 m차원 실수공간을 생성(span)한다.

A는 모든 행에 pivot positon을 하나 가진다.

LU 분해

LU 분해란 기본행연산에 의해 단위행렬(indentity matrix)로 변환할 수 있는 임의의 행렬 A를 아래와 같이 하삼각행렬(Lower triangular matrix)상삼각행렬(Upper triangular matrix)의 곱으로 분해하는 것입니다.

행렬 A에 대해 유한번(k)의 기본행연산을 수행해 가우스행렬로 변환한 것이 상삼각행렬 U입니다. 행렬 A에 대한 기본행연산은 A와 기본행렬의 곱으로 나타낼 수 있고, 기본행렬의 역행렬은 기본행렬이기 때문에 아래와 같이 쓸 수 있습니다.

따라서 하삼각행렬 L은 행렬 A에 대한 기본행연산의 history가 되는 것입니다. 임의의 행렬 A에 대한 LU분해 결과는 유일함이 증명되어 있습니다.

LU 분해의 이점은 무엇일까요? 만일 A가 LU로 분해될 수 있으면 Ax=b라는 방정식은 LUx=b로 변환됩니다. Ux=y로 두면 Ax=b는 Ly=b로 고쳐 풀 수 있습니다. L과 U는 이미 미지수를 구하기 편하도록 정리된 형태이기 때문에 아무리 미지수가 많더라도 빠른 시간에 방정식의 해를 구할 수 있습니다.

해의 존재성 여부나 행렬식(determinant)도 빠르게 확인 가능합니다. 상삼각행렬이든 하삼각행렬이든 삼각행렬의 행렬식은 모든 대각성분의 곱과 같습니다. 따라서 A가 LU분해가 되어 있을 경우 A의 행렬식은 L의 행렬식과 U의 행렬식을 각각 L, U의 모든 대각성분을 곱해 간단히 구할 수 있습니다. A의 행렬식이 0인지 여부로 해의 존재성 여부도 확인할 수 있습니다. 아울러 삼각행렬은 역행렬 구하기도 쉽죠. 또 LU 분해는 특이값 분해 등 각종 행렬 분해와도 깊은 연관을 지니고 있습니다.

한편 지금까지는 LU 분해는 행 교환(row interchange)을 하지 않고 기본행연산을 수행했다는 가정 하에 설명을 드렸는데요. 행 교환 또한 행렬 곱 형태로 나타낼 수 있습니다. 예컨대 1행과 2행을 교환해주는 역할을 하는 3 x 3 크기의 permutraion matrix P는 다음과 같습니다.

보시다시피 단위행렬(indentity matrix)와 거의 유사한 꼴을 지녔으나 1의 위치가 다소 다릅니다. permutation matrix의 특징은 아래와 같습니다.

  • 단위행렬과 행의 개수가 같다.
  • 모든 행과 열에 1이 단 한 개 존재한다.
  • 역행렬(=교환한 행을 원래대로 돌려놓는 역할 수행)은 그 전치행렬과 같다.

permutation matrix까지 고려하면 LU분해는 최종적으로 아래와 같이 쓸 수 있습니다.

Comments