가우스-요르단 소거법

가우스-요르단 소거법

gaussian elimination

정의1

첨가행렬이 다음의 조건을 만족하면 행사다리꼴echelon form이라 한다.

  • $0$이 아닌 성분이 있는 행에서 가장 처음 나오는 $0$이 아닌 수가 $1$이다. 이를 선도 1leading 1이라 한다.

  • 모든 성분가 $0$인 행은 가장 아래에 적는다.

  • $0$이 아닌 원소가 있는 행이 연속될 때 윗행의 선도 1이 아랫행의 선도 1보다 왼쪽에 있어야 한다.

행사다리꼴 행렬이 추가적으로 아래의 조건까지 만족시키면 기약 행사다리꼴reduced echelon form이라 한다.

  • 선도 1이 있는 열의 나머지 성분이 모두 $0$이다.

다음의 행렬들은 기약 행사다리꼴이다.

$$ \begin{bmatrix} 1 & 0 & 0 & 3 \\ 0 & 1 & 0 & 7 \\ 0 & 0 & 1 & -1 \end{bmatrix},\quad \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix},\quad \begin{bmatrix} 0 & 1 & -2 & 0 & 1 \\ 0 & 0 & 0 & 1 & 3 \\ 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \end{bmatrix},\quad \begin{bmatrix} 0 & 0 \\ 0 & 0 \end{bmatrix} $$

다음의 행렬들은 행사다리꼴이지만 기약 행사다리꼴이 아닌 행렬이다.

$$ \begin{bmatrix} 1 & 4 & -3 & 7 \\ 0 & 1 & 6 & 2 \\ 0 & 0 & 1 & 5 \end{bmatrix},\quad \begin{bmatrix} 1 & 1 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 0 \end{bmatrix},\quad \begin{bmatrix} 0 & 1 & 2 & 6 & 0 \\ 0 & 0 & 1 & -1 & 0 \\ 0 & 0 & 0 & 0 & 1 \end{bmatrix} $$

주어진 선형 시스템의 첨가행렬을 기본 행 연산으로 기약 행사다리꼴로 만드는 과정을 가우스-요르단 소거법Gauss-Jordan elimination이라 한다. 기약 행사다리꼴을 구하는 과정에서 선도 1의 아랫부분을 모두 $0$으로 만드는 것을 전진forward, 윗부분을 모두 $0$으로 만드는 것을 후진backword라고 한다.

성질

  • 모든 행렬은 유일한 기약 행사다리꼴을 가진다. 다시 말해서 기본 행 연산을 어떤 순서로 하든 간에 같은 기약 행사다리꼴 행렬을 얻는다.

  • 행사다리꼴은 유일하지 않다. 즉 기본 행 연산의 순서에 따라서 다르게 얻을 수 있다.

  • 행사다리꼴의 모든 원소가 $0$인 행의 개수는 서로 같으며 선도 1의 위치도 서로 같다. 이 위치를 피벗pivot 위치라 한다.

일반해2

선형 시스템이 무수히 많은 해를 가질 때, 매개변수를 대입하여 해를 얻을 수 있는 매개변수 방정식들의 집합을 선형 시스템의 일반해general solution라고 한다.

가령 어떤 선형 시스템의 첨가행렬을 기본 행 연산으로 다음과 같은 기약 행사다리꼴로 만들었다고 해보자.

$$ \begin{bmatrix} 1 & 0 & 3 & -1 \\ 0 & 1 & -4 & 2 \\ 0 & 0 & 0 & 0 \end{bmatrix} $$

그러면 매개변수 방정식은 다음과 같다.

$$ x = -1 -3t,\quad y = 2 + 4t, \quad z = t $$

이때 선도 1에 대응되는 변수 $x,y$를 선도변수leading variable, 그 외의 변수 $z$를 자유변수free variable라 한다.


  1. Howard Anton, Elementary Linear Algebra: Aplications Version (12th Edition, 2019), p11 ↩︎

  2. Howard Anton, Elementary Linear Algebra: Aplications Version (12th Edition, 2019), p115 ↩︎

댓글