2. Elimination with Matrices

본 게시물에서는 실제 SW에서 연립 방정식을 푸는데 사용하는 Elimination에 대해 알아본다. 내용 순서는 다음과 같다.

• Elimination - Success / Failure
• Eliminatioin Matrices
• Matrix Multiplication

Elimination - Success / Failure

• Success

다음과 같은 방정식이 주어졌다고 가정하자.
$x + 2y + z = 12$
$3x + 8y + x = 12$
$4y + z = 2$

이 방정식을 풀 때 upper triangle 형태로 만들면 쉽게 unknown들을 찾을 수 있다. upper triangle을 만드는 과정은 다음과 같다.

1. 우선 A와 b를 합친 형태의 matrix를 형성한다. 이와 같이 서로 다른 matrix를 하나의 matrix로 합친 형태를 augmented matrix라고 한다.
2. Upper triangle을 만들기 위해 우선 (2,1) position 값을 0으로 만들 필요가 있다. 이를 위해 $3\cdot row1$ 을 $row2$에서 빼준다.
3. 비슷한 방식으로 (3,2) position을 0으로 만들기 위해 $2\cdot row2$를 $row3$에서 뺀다.

이렇게 생성된 matrix는 A에 위차하는 부분이 upper triangle이 되고, 앞으로 이러한 matrix를 $u$(Uppper triangle matrix), $b$에 해당하는 column은 $c$라고 지칭한다.

Matrix에서 특정 column position의 아래 값이 전부 $0$인 경우 해당 column의 $0$이 아닌 가장 아래 값을 pivot이라고 칭한다.

이렇게 생성된 $u$를 이용하면 back-substitution을 통해 아주 쉽게 unknown들을 찾을 수 있다.

• Failure

이러한 방식으로 항상 solution을 찾을 수 있는 것은 아니다.
만약 upper triangle을 형성하는 과정에서 특정 row가 모두 0이 되는 경우, 해당 연립방정식의 해는 찾을 수 없다.

Elimination Matrices

Elimination matrix는 행렬 내 특정 값을 0으로 만들기 위해 사용되는 행렬을 뜻한다. 위 그림의 과정에서 elimination matrix가 사용되는 것을 나타내면 다음과 같다.

여기서 각 $E_{row,col}$는 $row$행 $col$열에 해당하는 poisition의 value를 $0$으로 만들기 위해 사용되는 elimination matrix를 의미한다.

이와 같은 elimination matrix는 다음과 같이 나타내는 것도 가능하다.

행렬에서 mutiplication order가 바뀌지 않는다면 두번째 항과 같이 괄호 위치가 변경 가능하다.(Associative law)
따라서 elimination matrix를 하나의 행렬 형태로 나타내는 것이 가능하다.
하지만 elimination matrix 여러개를 곱하여 하나의 elimination matrix를 계산하고 이를 통해 unknown들을 찾는 방법은 비효율적이다.
이를 좀 더 효율적으로 수행하는 방법은 다음 게시물에서 소개한다.

Matrix Multiplication

여기서는 몇가지 유용한 matrix multiplication들에 대해 소개한다.

Column multiplication
각 column을 특정 multiplier로 곱해주는 경우에 사용
( 각 column에 순서대로 3, 4, 5를 곱하는 예제 )

Row multiplication
각 row를 특정 multiplier로 곱해주는 경우에 사용
( 각 row에 순서대로 1, 2, 7을 곱하는 예제 )

Permutation matrix
행렬 요소의 위치를 바꾸는데 사용되는 행렬. 각 열에는 하나의 1과 0으로만 이루어진다.

다음 두가지 사항에 대해서도 추가로 꼭 기억하자.
1. Column에 대해 연산 혹은 행렬 조작이 수행되는 경우는 Matrix 앞에 multiplier 위치
2. Row에 대해 연산 혹은 행렬 조작이 수행되는 경우는 Matrix 뒤에 multiplier 위치