[선형대수] 행 축소와 LU 분해

 행 축소와 LU분해는 이전 글인 QR분해와 함께 행렬을 두개의 행렬로 분해하는 방법이다. 이들은 선형대수에서  최소제곱모델, 연립방정식, 역행렬 계산 등에서 활용되며 상대적으로 수치 안정적인 방법을 제공한다. QR분해는 다음 글을 참고하자.(https://iridescentboy.tistory.com/163)

 

 본 페이지에서는 LU 분해와 관련 개념인 행 축소를 다룬다. 행 축소를 다루기 위해 먼저, 행렬연립방정식을 보자. 

---

행렬방정식

2개 이상의 방정식은 행렬을 사용해 표현할 수 있다. 예를 들어, 아래 왼쪽의 2개 방정식은 x, y 변수로 구성되어 있다. 이를 행렬 방정식으로 변경하면 오른쪽과 같다. 행렬방정식을 먼저 제시한 이유는, 행 축소와 LU 분해가 행렬 방정식을 수치 안정적으로 푸는데 도움이 되기 때문이다. 그럼 이번 글의 메인 주제 설명을 시작하자.

---

행 축소

행 축소의 목적은 행렬을 상삼각 행렬로 변환하는 것이다. 상삼각 행렬은 행렬의 사다리꼴 형태를 의미한다. 행 축소는 행렬의 항에 스칼라 곱셈과 덧셈을 반복 적용하여,아래 2가지 사항을 만족시킨다.

1. 기준 원소 (pivot, 각 행에서 가장 왼쪽에 있는 숫자 중 0이 아닌 숫자)가 바로 윗 행의 기준 원소 오른쪽에 있음
2. 모든 원소가 0인 행은 0이 아닌 원소를 포함한 행 아래에 있음

행 축소로 상삼각 행렬을 만드는 예시는 아래와 같다.

 

행 축소는 선형 변환 과정이다. 각 행의 스칼라 곱셈과 덧셈을 수행하기 때문이다. 따라서 선형 변환 과정은 아래와 같은 행렬 식으로 표현 가능하다.

즉, 행 축소는 행렬을 상삼각 행렬로 변환하는 작업인데, 이는 선형 변환 과정을 거치기 때문에 변환 형렬을 좌측에 곱해주는 것과 같다. 주어진 행렬을 A, 선형 변환 행렬을 L-1, 둘을 곱한 상삼각행렬은 U로 표현했다. 위 식은 LU 분해의 표현인데, 이는 아래 LU 분해에서 추가 설명하겠다.

 

상삼각행렬인 사다리꼴 형태는 고유하지 않다. 하지만 몇가지 제약조건을 추가하면 고유한 형태를얻을 수 있다. 예를 들어, L 행렬의 대각 원소가 1인 선형 변환 행렬을 구한다와 같은 것이다. 이를 reduced row echelon form (RREF) 하며 LU 분해의 L 행렬이다. 이는 아래 LU 분해에서 확인해 보자.

---

가우스 소거법 (Gaussian Elimination)

 가우스 소거법은 행 축소 개념을 사용해 연립 방정식을 푸는 방법으로 다음 순서를 따른다. 연립방정식의 행렬을 계수행렬, 우측의 벡터를 상수벡터로 지칭하겠다.

1. 계수 행렬에 상수 벡터를 최우측 열로 추가한다.
2. 행을 사다리꼴 형태로 축소한다.
3. 역치환(값을 구한 계수 값을 이용해, 다른 계수 값을 구하는 것)으로 계수 값을 구한다.

위 예를 기준으로, 우측의 상수 벡터를 계수 행렬의 최우측 열로 추가한다. 그리고 두번째 행의 첫번째 열 원소를 0으로 만들어 사다리꼴 형태로 축소한다. 이후 y 값을 구한 뒤, x 값을 계산한다.

---

가우스 조던 소거법 (Gaussian Jordan Elimination)

 가우스 조던 소거법은 가우스 소거법에서 몇가지 사항이 추가된다. 먼저, 기준 원소를 1로 만든다. 그리고 기준 원소와 상수 열 벡터를 제외하고 모두 0으로 만든다. (그럼 역치환 필요 없이, 각 변수의 값을 계산할 수 있다.)

 위 가우스 소거법의 가장 마지막 행렬에서 추가 계산을 진행한다.

 가우스 조던 소거법으로 구한 사다리꼴 행렬을 RREF 라고 한다. (Reduced Row Echelon Form) RREF는 하나의 행렬 연립방정식에서 하나만 구할 수 있는 고유한 행렬이다.

---

가우스 조던 소거법을 이용한 역행렬 계산

 특정 행렬이 주어졌을 때, 가우스 조던 소거법을 사용해 역행렬을 계산할 수 있다. (참고로, 지금까지 포스팅한 내용 중에서 역행렬을 계산하는 방법은 총 2가지였다. 첫번째는 클래식하게 수식으로 계산하는 법, 두번째는 QR 분해를 이용하는 법이다.)

 

 특정 2 x 2 행렬이 주어졌다고 가정하자. 각 원소는 a, b, c, d 이다. 이때 아래 행렬 방정식의 해 x, y 를 계산한다고 가정해보자. 이때 상수 벡터 1, 0은 단위 행렬의 첫번째 열이다. 즉, x, y는 역행렬의 첫번째 열 벡터의 값임을 알 수 있다.

 그렇다면 상수 벡터가 0, 1 일대는 x, y가 역행렬의 두번째 열 벡터 값임을 알 수 있다.

 즉, 두번의 연립방정식을 품으로서 역행렬을 계산할 수 있다. 이때 연립방정식을 풀때는 가우스 조던 소거법을 이용할 수 있다. 위 과정을 수식으로 표현하면 다음과 같다. 주어진 행렬에서 단위 행렬을 최우측 벡터로 추가한 후, rref를 계산하면 역행렬 요소를 구할 수 있다.

---

LU분해 (LU Decomposition)

 이제 가장 중요한 LU 분해이다. 본 글에서 언급한 행 축소, 가우스 소거법, 가우스 조던 소거법 모두 LU분해를 이해하기 위한 준비 자료들이었다. LU분해는 행렬을 하삼각행렬과 상삼각행렬로 분해하는 것으로 두 행렬을 각각 Lower 과 Upper의 첫자를 따서 LU라고 지칭한다.

 

 LU 분해의 예시는 다음과 같다. 행렬 A를 각각 하삼각행렬과 상삼각행렬로 분해한다.

 

 위 분해는 어떤 과정으로 이루어질까? 그것은 바로 위에서 공부한 행축소이다. 연립방정식을 풀기 위해 특정 행렬을 선형변환을 통해 상삼각행렬로 만들었던 방법 말이다. 행 축소는 아래 수식과 같이 표현할 수 있다.

 이때, 상삼각 행렬(사다리꼴 형태)는 고유하지 않음을 배웠다.  따라서 LU 분해의 두 행렬 또한 고유하지 않다. 이때, L 행렬의 대각요소가 1이라는 제약 조건을 추가하면, 고유한 LU분해 행렬을 얻을 수 있다.

 

 

금일 공부한 LU분해 및 행축소는 행렬 연립 방정식을 풀때나, 최소제곱법 계산에서 유용하게 사용되는 개념이다. 나도 포인트 집합을 다항식으로 Fitting 하는 함수들에서 최소제곱법 및 행렬 연립방정식을 적용하고 LU분해를 사용하는 케이스들을 보았다. 잘 공부해놓자.