[Linear_Algebra] Gaussian elimination and LU factorization

Gaussian elimination(GE)를 이용해 linear equation의 해를 구할 수 있다.

하지만, 이 과정을 컴퓨터 프로그래밍으로 계산하기 위해서는 행렬로 표현할 수 있어야 한다. 이때 사용하는 방법을 알아보자.

 

 

1. Elementary matrix

Let A be the original matrix. 이런 조건에서 첫 번째 행을 상수배하여 두 번째 행에 더하거나 빼는 과정을 하게 된다. 이러한 연산 과정을 행렬로 나타낸 것을 E21이라고 한다. E21은 identity matrix에서 (2,1) 위치에 상수를 넣어 만든 행렬이다. 또 다른 예시로는 E32가 있다. 이 행렬은 identity matrix의 (3,2) 위치에 coefficient를 넣은 행렬이다.

Elementary matrix를 통해 우리는 GE의 과정을 행렬로 표현할 수 있게 되었다. 따라서, GE 과정을 다음과 같이 표현할 수 있다.

E32 × E21 × A = U

여기서 U는 upper triangular matrix다. GE 과정이 끝나면 matrix의 대각선을 기준으로 아래 값들이 모두 0이기 때문에 U 형태가 된다.

 

 

2. A = LU factorization

U라는 matrix를 GE를 통해 구했다고 가정하자. 이 경우 본래 행렬인 A를 찾으려면 어떻게 해야 하는가?

그 답은 U matrix에 (E32 × E21)^(-1)을 곱해줌으로써 original matrix를 찾을 수 있게 된다. 이를 직관적으로 이해하기 위해서는 다음과 같이 생각할 수 있다.

L은 lower triangular matrix인데, 이는 기존의 elementary matrix들의 역행렬 곱으로 나타난다. 따라서,

L = E21^(-1) × E32^(-1)

와 같이 표현할 수 있다. 이때 E21^(-1)은 E21의 (2,1) 원소의 부호만 반대로 바꾼 것이다. 따라서, GE 과정을 통해 수행되었던 연산을 거꾸로 되돌리는 과정이라고 생각하면 된다.

 

 

3. Permutation matrix

GE 과정을 하는 도중에 pivoting(row를 바꾸는 과정)이 필요할 때가 있다. 이 과정도 행렬로 나타낼 필요가 있다. 이때 사용하는 것이 permutation matrix다.

Permutation matrix를 만드는 방법은 identity matrix를 변형시켜서 만든다. 예를 들어 i번째와 j번째 row를 서로 바꾸고 싶다면, identity matrix에서 i행과 j행을 통째로 맞바꾸면 된다. 이렇게 만들어진 행렬이 permutation matrix이며, 해당 행렬을 A에 곱하면 두 행이 서로 바뀌게 된다.

 

 

4. 정리

따라서, GE 과정을 행렬로 표현하면 다음과 같다.

E32 × E31 × P23 × E21 × A = E32 × E31 × P23 × E21 × B