linear algebra - 가우스 소거법(Gaussian elimination)

공의 반사 각을 그리고 궁극적으로 빛이 구체에서 반사 될 때의 반사 각을 찾기 위한 여정에서 잠깐 벗어나 선형 방정식의 미지수 해를 찾는 방법인 Gaussian Elimination(가우스 소거법)을 잠시 살펴 볼 것이다. 두 직선의 방정식이 교차하는 지점을 찾는 것이 무엇이 특별하냐 할지 모르겠지만 모든 학문들이 다 그렇듯 이 단순한 특수 사례로부터 완전히 일반적인 공식을 이끌어내어 10개의 미지수 또는 100개의 미지수와 10개 또는 100개의 linear equation으로부터 미지수 해를 찾아낼 수 있기 때문에 Gaussian Elimination(가우스 소거법)은 공학에서 대단히 중요한 역할을 한다. 그리고 이 방법이 linear equation을 푸는 컴퓨터의 가장 일반적인 방식이므로 octave, matlab의 도움을 받아 문제를 풀고자 한다면 가우스 소거법을 이해할 필요가 있다.

가우스 소거법이 기원전에 연산의 기본 방법이 고안 되었다는 사실은 기본적으로 우리가 이해하는데 크게 어려움이 없다는 말과 동일하다. 그 개념 뒤의 아이디어는 간단하다. 아래의 식을 생각해 보자

	(1)
	(2)
	(3)

(1) 식의 왼쪽 항에 3을 곱한 뒤 (2)의 왼쪽 항을 더한 값의 결과는 (1)식의 오른쪽 항에 3을 곱한 뒤 (2)식의 오른쪽 항을 더한 값과 같다.

너무 당연해서 초등학생도 이해하는 식이다. 하지만 위의 결과가 나오기 위해서는 저 수들이 선형 좌표 시스템 안에 있어야 한다. linear algebra를 주제로 한 첫 연재 글에 소개한 3Blue1Brown의 영상을 보았다면 선형 좌표 시스템이란 등간격으로 배치된 좌표 시스템이란 것을 이해할 것이다. linearity에 관한 탐구는 linear algebra의 중요한 주제이고 공대생들도 또한 4년 내내 여러 곳에서 듣게 되는 용어도 linear, linear independent(선형 독립)이다. 선형성을 판별하는 대표적인 조건을 써보면

위의 식들은 임의적으로 내가 단순화해 표현한 수식이다. linear algebra에서는 vector space(벡터 공간)라는 카테고리에서 좀 더 복잡한 수식으로 조건들을 다루고 있다. vector space는 이 글의 범위를 넘어가므로 자세한 설명은 생략할 것이다.

우리가 흔히 쓰는 Cartesian coordinate system 또는 rectangular coordinate system(직교 좌표계)에서 놓인 직선의 방정식은 위의 선형 조건들을 만족한다. 따라서 다음과 같이 두 식이 주어 졌을 때

	(4)
	(5)

3*(5)+(4)를 하여 다음과 같이 해를 구할 수 있다.

이런 아이디어로 체계적으로 정리한 것이 가우스 소거법이다. 우선 (4), (5)의 식을 coefficent(계수)들로 이루어진 행렬로 표현한다.

2열에 -3을 곱한 다음 2열에서 1열을 더하면

이렇게 대각선 아래를 0으로 만드는 것을 가우스 소거법이라 부른다. 여기서 더 나아가 행렬의 대각선 위도 0으로 만드는 것을 가우스 조던 소거법(Gauss-Jordan elimination)이라고 한다. (1,1), (2,2), (3,3), (n,n)의 요소를 pivot이라고 부른다. 다음 미지수 3개가 포함된 3개의 선형 방정식을 고려해 보자.

행렬식으로 표현하면

이를 계산하면

pivot (1,1): 
Row(3) - (1)*Row(1)
A : 
1.0     1.0     -2.0    -2.0
0.0     1.0     3.0     7.0
0.0     -1.0    1.0     1.0
pivot (2,2): 
Row(3) - (-1)*Row(2)
A : 
1.0     1.0     -2.0    -2.0
0.0     1.0     3.0     7.0
0.0     0.0     4.0     8.0
pivot (3,3): 
Row(2) - (3)*Row(3)
Row(1) - (-2)*Row(3)
1.0     1.0     0.0     2.0
0.0     1.0     0.0     1.0
0.0     0.0     1.0     2.0
pivot (2,2): 
Row(1) - (1)*Row(2)
1.0     0.0     0.0     1.0
0.0     1.0     0.0     1.0
0.0     0.0     1.0     2.0

위의 연산 과정은 내가 프로그래밍한 gauss-jordan elimination 프로그램이 elimination 과정을 출력한 것이다. pivot 아래 행을 소거하기 전에 pivot 값을 미리 1로 만들어 놓기 때문에 일반적으로 손으로 푸는 것과 약간은 차이가 날 수 있지만 큰 차이는 없다. 가우스 조던 소거법으로 구한 미지수 (x, y, z)의 값은 (1,1,2)가 된다.

컴퓨터 친화적이긴 하지만 그렇다고 인간 친화적이진 않다. 대수 연산이 많이 들어가는 건 누구에게나 어렵다. 그리고 저런 산수를 하는 것은 수학이 아니다. 저런 산수를 할 시간에 공학 계산기를 프로그래밍하는 방법이나 octave, matlab 같은 프로그램을 활용해 계산하는 방법을 익히는 것은 미래를 위해서도 훨씬 효과적이다. octave나 matlab에서는 rref라는 function을 제공하는데 이 함수는  the reduced row echelon form을 리턴한다. 그것이 가우스 조던 소거법의 결과이다. 아래는 octave 프로그램을 이용해 계산하는 방법이다.

octave:8> A=[1 1 -2 -2; 0 1 3 7; 1 0 -1 -1]
A =

   1   1  -2  -2
   0   1   3   7
   1   0  -1  -1

octave:9> rref(A)
ans =

   1   0   0   1
   0   1   0   1
   0   0   1   2

행렬 A를 입력한 후 rref 함수를 호출하면 된다.

가우스 소거법의 기하학적 의미는 다음 MIT Open Course 영상에서 아주 쉽게 설명하고 있다.

위의 가우스 조던 소거법은 AX=B의 행렬 벡터 식에서 X의 벡터 값을 구하기 위해 A행렬과 B 벡터를 합하여 소거법으로 X 벡터를 구하는 방법을 나타낸 것이다. 위의 영상에도 나오지만 19세기 이전 수학자들은 역행렬 의 존재에 빠져 있었다. 즉 실수 연산에서 ax=b에서 x값을 찾을 때 x = b*(1/a) 하는 것과 마찬가지로 로 미지수 X를 구할 수 있다면 편하지 않겠냐는 것이다. 결론적인 얘기지만 저 연구는 결국 시간 낭비였음이 밝혀졌다. 시간 낭비였긴 하지만 간단히 역행렬을 구하는 방법을 소개하면 가우스 소거법을 할 때 단위 행렬(Identity matrix)를 나란히 배치하고 행렬 A에서 일어나는 소거법 연산을 똑같이 단위 행렬에 적용하면 역행렬이 구해진다. 역행렬 연구가 determinant(행렬식) 연구로 이어지는데 이것도 선형 대수 역사의 삽질 중 하나였다. 보기와는 다르게 determinant(행렬식)로 역행렬을 구하는 것은 가우스 조던 소거법보다 훨씬 더 시간 낭비였던 것이다. 역행렬을 구하는데 아무 쓸모가 없긴 하지만 determinant는 row vector들이 만드는 평형 사변형의 넓이나 부피를 구하는 식으로 사용할 수 있었다. 그리고 Eigenvalues 와 Eigenvectors 를 구하는데 이용되기도 한다. determinant를 가장 쉽게 구하는 방법은 determinant(행렬식)를 구하고자 하는 행렬 A를 가우스 소거법으로 삼각 행렬로 만든 뒤 대각선 요소들을 모두 곱하는 것이다. 결국은 가우스 소거법으로 되돌아 간다.

가우스 조던 소거법이 linear algebra를 공부하고 연구하는데 핵심적인 역할을 담당하긴 하지만 실제 미지수 벡터 X를 구하는데 이 방법이 효과적인 것은 아니다.  행과 열의 개수가 늘어남에 따라 연산량이 급격히 증가하기 때문이다. 그래서 실제로 컴퓨터 연산에 활용되는 것은 LU decomposition(LU 분해)이다. 행렬 A를 lower triangular matrix와  upper triangular matrix로 일종의 인수 분해하는 방법인데 이렇게 인수 분해를 해 놓으면 어떠한 B값도 LU factor를 활용해 backward, forward substitution으로 미지수 벡터 X값을 구할 수 있다. 재활용성이 뛰어나다. 뿐만 아니라 인수 분해에 필요한 연산이 가우스 조던 전체 연산이 아닌 가우스 소거법만을 필요로 하기 때문에 더 효과적이다. 그래서 전문 수학 라이브러리를 사용하여 미지수 벡터 X를 구하고자 한다면 찾아야 하는 라이브러리가 가우스 조던 소거법을 구현한 라이브러리가 아니라(보통 구현하지도 않는다.) LU decomposition을 구현한 라이브러리를 찾아야 한다.

아래는 c++의 거의 표준 라이브러리인 Boost 라이브러리의 LU 함수를 이용해 AX=B 식의 해를 구하는 프로그램의 일부이다.

bool CEquation::solve(CEquation &other, point_t& result)
{
    using namespace boost::numeric::ublas;
    matrix A(2, 2);
    boost::numeric::ublas::vector B(2);

    B <<= p, other.p;
    A <<= cos_theta, sin_theta,
      other.cos_theta, other.sin_theta;

    typedef permutation_matrix pmatrix;
    pmatrix pm(A.size1());
    int res = lu_factorize(A, pm);
    if (res != 0)
        return false;
    lu_substitute(A, pm, B);

    boost::geometry::set<0>(result, B[0]);
    boost::geometry::set<1>(result, B[1]);
    return true;
}

결론을 내면 linear algebra를 공부하는데 가우스 소거법이 가장 핵심을 차지하지만 실전에서 쓰이는 것은 LU decomposition이다. 가우스 소거법이든 LU decomposition이든 선형 방정식의 해를 찾는데 이용할 수 있다. 역행렬(Inverse matrix)를 찾을려고 고민하지 말도록 하자. 쓸모가 없다. 가우스 소거법을 손으로 푸는 것은 미련한 짓이다. 컴퓨터 프로그램이나 공학 계산기를 적극 활용하자.