[선형대수학#6] 가우스 소거법 (Gaussian Elimination)

Gaussian Elimination

Augmented matrix $ [A \mid \mathbf{b}] $에 elementry row operation을 반복 적용해서 RREF로 변환한 뒤 해를 읽어내는 방법이다. 핵심 아이디어는 elementry row operation이 방정식의 해를 바꾸지 않는다는 것이다. 즉 원래 연립방정식과 RREF로 변환된 연립방정식은 같은 해를 가진다.

 

이제 위 설명 내 개념들을 하나씩 알아보록 하자.

 

Augmented Matrix

연립 방정식 $Ax = b$를 풀 때, 계수(Coefficient) 행렬 $A$와 상수 벡터 $b$를 하나로 합친 것을 augmented matrix라 한다.

 

$$\begin{pmatrix} a_{11} & \cdots & a_{1n} \\ \vdots & \ddots & \vdots \\ a_{m1} & \cdots & a_{mn} \end{pmatrix} \mathbf{x} = \begin{pmatrix} b_1 \\ \vdots \\ b_m \end{pmatrix} \Rightarrow [A \mid \mathbf{b}] = \begin{pmatrix} a_{11} & \cdots & a_{1n} & b_1 \\ \vdots & \ddots & \vdots & \vdots \\ a_{m1} & \cdots & a_{mn} & b_m \end{pmatrix}$$

 

$A$와 $b$를 분리해서 다룰 필요 없이 $ [A \mid \mathbf{b}] $ 하나에 행 연산을 적용하면 된다.

 

Elementray Row Operations

Augmented matrix에 적용할 수 있는 연산은 세 가지다. 이 연산들은 방정식의 해를 바꾸지 않는다.

 

• 행 교환: $i$번째 행과 $j$번째 행을 맞바꾼다.
• 스칼라 곱: $i$번째 행 전체에 $c \neq 0$를 곱한다.
• 행 덧셈: $j$번째 행의 $c$배를 $i$번째 행에 더한다.

 

Reduced Row Echelon Form(RREF)

행 연산의 목표 형태이다. 다음 네 가지 조건을 모두 만족해야 한다.

 

• 모든 성분이 0인 행은 맨 아래에 위치한다.
• 각 행의 첫 번째 0이 아닌 성분은 1이다. → 이를 leading one이라 한다.
• 아래 행의 leading one은 위 행의 leading one보다 오른쪽에 위치한다. (계단식)
• leading one이 있는 열의 나머지 성분은 모두 0이다.

 

예를 들어 아래와 같은 형태다.

 

 

예시

 

$$ 2x_1 + x_2 - x_3 = 8 $$

$$ -3x_1 - x_2 + 2x_3 = -11 $$

$$ -2x_1 + x_2 + 2x_3 = -3 $$

 

Augmented matrix로 쓰면:

 

$$[A \mid \mathbf{b}] = \begin{pmatrix} 2 & 1 & -1 & 8 \\ -3 & -1 & 2 & -11 \\ -2 & 1 & 2 & -3 \end{pmatrix}$$

$R_1 \leftarrow \frac{1}{2} R_1$:

$$\begin{pmatrix} 1 & 1/2 & -1/2 & 4 \\ -3 & -1 & 2 & -11 \\ -2 & 1 & 2 & -3 \end{pmatrix}$$

$R_2 \leftarrow R_2 + 3R_1, \quad R_3 \leftarrow R_3 + 2R_1$:

$$\begin{pmatrix} 1 & 1/2 & -1/2 & 4 \\ 0 & 1/2 & 1/2 & 1 \\ 0 & 2 & 1 & 5 \end{pmatrix}$$

$R_2 \leftarrow 2R_2$:

$$\begin{pmatrix} 1 & 1/2 & -1/2 & 4 \\ 0 & 1 & 1 & 2 \\ 0 & 2 & 1 & 5 \end{pmatrix}$$

$ R_1 \leftarrow R_1 - \frac{1}{2}R_2, \quad R_3 \leftarrow R_3 - 2R_2 $:

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

$R_3 \leftarrow -R_3$:

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

$R_1 \leftarrow R_1 + R_3, \quad R_2 \leftarrow R_2 - R_3$:

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

 

RREF에 도달했다. 따라서 $x_1 = 2, x_2 = 3, x_3 = -1$이다.

 

해가 없는 경우

행 연산 도중 아래와 같은 행이 나타나면 해가 존재하지 않는다.

 

$$\begin{pmatrix} 0 & 0 & 0 & 3 \end{pmatrix}$$

 

이는 $0 = 3$을 의미하므로 모순이다. 이런 연립방정식을 inconsistent이라 한다.

 

해가 무수히 많은 경우

RREF로 변환했을 때 leading one의 개수가 변수의 개수보다 적으면 free variable이 생긴다.

 

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

 

$x_3$에 대한 leading one이 없으므로 $x_3$는 free variable이다. $x_3 = t$로 놓으면 $x_1 = 3 - 2t, x_2 = 1 + t$로 해가 무수히 많아진다.

 

Gaussian Elimination과 역행렬의 관계

이전 포스팅 중 역행렬을 구하는 방식에 대해 언급한 적이 있다. 이 외에도 gaussian elimination을 사용해 역행렬을 구할 수 있다.

2025.09.22 - [Mathematics] - [선형대수학#5] 역행렬

 

$A$가 $n \times n$ 정방행렬일 때 다음 세 명제는 동치다.

• A는 nonsingular
• $ [A \mid \mathbf{b}]  $를 RREF로 만들면 $[I_n \mid \mathbf{b}']$형태가 된다.
• $det(A) \neq 0$

 

즉 $A$를 $I_n$으로 만들 수 있다는 것 자체가 $A$가 invertible 하다는 증거다. 왜냐하면 row operations를 통해 $A$가 $I_n$이 되었다는 건 $A$를 $I_n$으로 변환하는 행렬들의 곱 $E_k \cdots E_2E_1$이 존재한다는 뜻이다. 역행렬의 정의 $BA = I_n$에 의해 이는 곧 $A^{-1} = E_k \cdots E_2E_1$임을 의미하기 때문이다.

 

반대로 $A$가 nonsingular하면 row operations을 아무리 적용해도 왼쪽을 $I_n$으로 만들 수 없다. 

 

예시

 

$$A = \begin{pmatrix} 2 & 1 \\ 5 & 3 \end{pmatrix}$$

$[A \mid I_2]$: 

$$\begin{pmatrix} 2 & 1 & 1 & 0 \\ 5 & 3 & 0 & 1 \end{pmatrix}$$

$R_1 \leftarrow \frac{1}{2}R_1$:

$$\begin{pmatrix} 1 & 1/2 & 1/2 & 0 \\ 5 & 3 & 0 & 1 \end{pmatrix}$$

$R_2 \leftarrow R_2 - 5R_1$:

$$\begin{pmatrix} 1 & 1/2 & 1/2 & 0 \\ 0 & 1/2 & -5/2 & 1 \end{pmatrix}$$

$R_2 \leftarrow 2R_2$:

$$\begin{pmatrix} 1 & 1/2 & 1/2 & 0 \\ 0 & 1 & -5 & 2 \end{pmatrix}$$

$R_1 \leftarrow R_1 - \frac{1}{2}R_2$:

$$\begin{pmatrix} 1 & 0 & 3 & -1 \\ 0 & 1 & -5 & 2 \end{pmatrix}$$

왼쪽이 $I_2$가 됐으므로 오른쪽이 $A^{-1}$이다.

$$A^{-1} = \begin{pmatrix} 3 & -1 \\ -5 & 2 \end{pmatrix}$$

 

검증: $AA^{-1} = \begin{pmatrix} 2 & 1 \\ 5 & 3 \end{pmatrix} \begin{pmatrix} 3 & -1 \\ -5 & 2 \end{pmatrix} = \begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix} = I_2$

 

 

선형회귀의 정규 방정식 $\hat{\mathbf{x}} = (A^T A)^{-1} A^T \mathbf{b}$을 풀 때 역행렬을 직접 계산하는 대신 gaussian elimination 기반의 수치 알고리즘을 사용한다. 실제로 Numpy의 np.linalg.solve(A, b)가 내부적으로 LU decomposition을 사용하는데, 이는 gaussian elimination을 행렬 형태로 분해한 것이다. 역행렬을 명시적으로 구하는 것보다 수치적으로 훨씬 안정적이고 빠르기 때문에 ML 라이브러리에서 이 방식을 채택하고 있다.

 

https://numpy.org/doc/stable/reference/generated/numpy.linalg.solve.html

numpy.linalg.solve — NumPy v2.4 Manual