가우스 소거법

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요

가우스 소거법은 주어진 연립 일차 방정식의 해를 구하기 위해 사용되는 알고리즘으로, 행렬을 사다리꼴 형태로 변환하여 해를 구하는 방법이다. 기본 행 연산을 통해 행렬을 변환하며, 전진 소거와 후퇴 대입 단계를 거쳐 해를 계산한다. 가우스 소거법은 행렬식, 역행렬, 계수 계산 등 다양한 분야에 응용되며, 고대 중국의 구장산술에서 그 기원을 찾을 수 있다. 계산 효율성은 O(n³)의 시간 복잡도를 가지며, 수치적 안정성을 위해 피벗 선택을 사용한다. 또한 실수뿐만 아니라 임의의 체에서도 수행될 수 있으며, 다항 방정식계로 일반화되기도 한다.

가우스 소거법

📚 더 읽어볼만한 페이지

수치선형대수학 - LINPACK
LINPACK은 부동소수점 연산 성능을 평가하는 벤치마크 프로그램이자 FORTRAN 라이브러리로, 슈퍼컴퓨터 성능 측정 기준으로 사용되는 HPLinpack 벤치마크의 기반이 되었으며, TOP500 목록에서 고성능 컴퓨터 순위를 결정하는 데 기여한다.
수치선형대수학 - 줄리아 (프로그래밍 언어)
줄리아는 2012년에 공개된 고수준 프로그래밍 언어로, 다중 디스패치, 동적 타입 시스템, C와 유사한 성능을 제공하며, 수치 계산, 과학 기술 계산 등에 활용된다.

1. 개요
2. 정의
3. 성질
4. 응용
5. 예제
6. 역사
7. 계산 효율성
8. 수치적 안정성
9. 일반화
10. 의사 코드

2. 정의

체 K에 대하여, n개의 미지수에 대한 m개의 방정식으로 구성된 연립일차방정식은 다음과 같이 표현된다.

: $Mx=0$

여기서 M은 주어진 $m\times(n+1)$ 행렬이고, x는 n개의 미지수를 포함하는 열벡터이다.

: $M=\begin{pmatrix}M_{11}&M_{12}&\cdots&M_{1,n+1}\\M_{21}&M_{22}&\cdots&M_{2,n+1}\\\vdots&\vdots&\ddots&\vdots\\M_{m1}&M_{m2}&\cdots&M_{m,n+1}\end{pmatrix}$

: $x=\begin{pmatrix}x_1\\x_2\\\vdots\\x_n\\1\end{pmatrix}$

이를 풀어서 쓰면 다음과 같다.

: $M_{11}x_1+M_{12}x_2+\cdots+M_{1,n}x_n+M_{1,n+1}=0$
: $M_{21}x_1+M_{22}x_2+\cdots+M_{2,n}x_n+M_{2,n+1}=0$
:::::::: $\vdots$
: $M_{m1}x_1+M_{m2}x_2+\cdots+M_{m,n}x_n+M_{m,n+1}=0$

2.1. 기본 행 연산

연립일차방정식에 적용할 수 있는 세 가지 기본 행 연산은 다음과 같다. 이 연산들은 연립방정식의 해집합을 바꾸지 않는다.

* 행의 치환: 두 행을 서로 바꾼다.
* 행의 상수곱: 한 행에 0이 아닌 상수를 곱한다.
* 행의 합: 한 행의 상수배를 다른 행에 더한다.

이 세 가지 기본 행 연산은 모두 가역 연산이다. 즉, 원래 상태로 되돌릴 수 있는 연산이다.

* 행의 치환의 역연산은 자기 자신이다. (같은 행을 다시 바꾸면 원래대로 돌아온다.)
* 행의 상수곱의 역연산은 그 행에 곱했던 상수의 역수를 곱하는 것이다.
* 행의 합의 역연산은 더했던 행의 상수배를 다시 빼는 것이다.

두 연립일차방정식의 첨가 행렬에 대해, 한 행렬에 기본 행 연산을 적용하여 다른 행렬을 얻을 수 있다면 두 행렬은 행동치라고 한다. 첨가 행렬이 행동치이면, 두 연립일차방정식의 해는 서로 같다.

단위 행렬에 기본 행 연산을 한 번 적용하여 얻는 행렬을 기본 행렬이라고 한다. 따라서, 세 가지 기본 행 연산은 기본 행렬을 곱하는 것과 같다.

2.2. 행사다리꼴행렬

사다리꼴행렬(Echelon matrix,에쉴론 메트릭스)은 각 행의 선행 계수(0이 아닌 첫 번째 항)가 아래 행의 선행 계수보다 왼쪽에 위치하며, 0으로만 구성된 행은 행렬의 가장 아래쪽에 위치하는 형태의 행렬이다.

행사다리꼴행렬은 다음 조건을 만족시킨다.
* $0=M_{i1}=\cdots=M_{in}$ 이라면, 모든 $i\le i'$ 에 대하여 $0=M_{i'1}=\cdots=M_{i'n}$ 이다.
* $i 이며 j_0(i) 와 j_0(i') 가 존재한다면, j_0(i) 이다.$

즉, 행사다리꼴행렬은 행렬의 항들이 대략 위에는 사다리꼴, 밑에는 0인 형태의 행렬이다.

예를 들어, 다음과 같은 행렬은 행사다리꼴행렬이다.
: $\begin{pmatrix}1 & a_0 & a_1 & a_2 & a_3 \\0 & 0 & 2 & a_4 & a_5 \\0 & 0 & 0 & 1 & a_6\end{pmatrix}$

다음 행렬은 행사다리꼴 형태의 예시이다.
: $\begin{bmatrix}0 & \color{red}{\mathbf{2}} & 1 & -1 \\0 & 0 & \color{red}{\mathbf{3}} & 1 \\0 & 0 & 0 & 0\end{bmatrix}.$
0 행이 아래에 있고, 두 번째 행의 선행 계수(세 번째 열)가 첫 번째 행의 선행 계수(두 번째 열)보다 오른쪽에 있기 때문에 사다리꼴 형태이다.

기약행사다리꼴행렬은 행사다리꼴행렬의 조건을 만족하면서, 추가적으로 각 선행 계수가 1이고, 선행 계수를 포함하는 열의 다른 항은 모두 0인 행렬이다.

예를 들어, 다음과 같은 행렬은 기약행사다리꼴행렬이다.
: $\begin{pmatrix}1 & 0 & a_1 & 0 & a_2 \\0 & 1 & a_3 & 0 & a_4 \\0 & 0 & 0 & 1 & a_5\end{pmatrix}$

가우스 소거법을 통해 모든 연립일차방정식의 첨가 행렬은 행사다리꼴행렬 및 기약행사다리꼴행렬로 변환할 수 있다.

2.3. 가우스 소거법

가우스 소거법은 기본행연산을 가하여 행렬을 행사다리꼴행렬로 만드는 알고리즘이며, 다음과 같다.

먼저 첫번째 행을 다음과 같이 처리한다.
# 선행 계수가 위치하는 가장 작은 열수 $j_1\le n$ 을 찾는다.
# $M_{1j_1}=0$ 이라면, 첫번째 행을 $M_{i_1j_1}\ne0$ 인 어떤 $i_1>1$ 번째 행과 치환한다.
# 모든 $i>1$ 번째 행에 첫번째 행의 $-M_{ij_1}/M_{1j_1}$ 배를 더해, $M_{1j_1}$ 밑의 항들을 0으로 만든다.

그 뒤, 두번째 행을 다음과 같이 처리한다.
# 어떤 $i\ge2$ 번째 행의 선행 계수가 위치하는 가장 작은 열수 $j_2\le n$ 을 찾는다.
# $M_{2j_2}=0$ 이라면, 두번째 행을 $M_{i_2j_2}\ne0$ 인 어떤 $i_2>2$ 번째 행과 치환한다.
# 모든 $i>2$ 번째 행에 두번째 행의 $-M_{ij_2}/M_{2j_2}$ 배를 더해, $M_{2j_2}$ 밑의 항들을 0으로 만든다.

뒤에 오는 다른 행에 대하여, 순차적으로 위와 같이 처리한다. 일반적으로, $k$ 번째 행은 다음과 같이 처리한다.
# 어떤 $i\ge k$ 번째 행의 선행 계수가 위치하는 가장 작은 열수 $j_k\le n$ 을 찾는다.
# $M_{kj_k}=0$ 이라면, $k$ 번째 행을 $M_{i_kj_k}\ne0$ 인 어떤 $i_k>k$ 번째 행과 치환한다.
# 모든 $i>k$ 번째 행에 $k$ 번째 행의 $-M_{ij_k}/M_{kj_k}$ 배를 더해, $M_{kj_k}$ 밑의 항들을 0으로 만든다.

만약 어떤 $j_{r+1}\le n$ 가 존재하지 않는다면, $r$ 번째 행에서 멈춘다. 만약 항상 $j_k\le n$ 를 찾을 수 있다면, 모든 $k=1,2,\ldots,m$ 번째 행에 대하여 순차적으로 위와 같이 처리하며, $r=n$ 으로 둔다.

기약행사다리꼴행렬을 원한다면, 찾았던 모든 $j_k=j_r,j_{r-2},\ldots,j_1$ 에 대하여 순차적으로 다음과 같은 단계를 추가로 거친다.
# $k$ 번째 행에 $1/M_{kj_k}$ 를 곱해, $M_{kj_k}$ 를 1로 만든다.
# 모든 $i 번째 행에 k 번째 행의 -M_{ij_k} 배를 더해, M_{kj_k} 위의 항들을 0으로 만든다.$

여기서 $r\le m$ 이며 $r\le n$ 인 데 주의한다. 사실, 이는 행렬의 계수이다.
*기약행사다리꼴행렬의 과정을 특히 요르단이 제시한 "가우스-요르단 소거법"으로 부른다.

행렬의 소거 과정은 기본 행 연산을 이용하며, 두 부분으로 나눌 수 있다. 첫 번째 부분(전진 소거라고도 함)은 주어진 시스템을 행 사다리꼴 형태로 축소하여 해가 없거나 유일한 해가 있거나 무한히 많은 해가 있는지 판단할 수 있게 한다. 두 번째 부분(후진 대입이라고도 함)은 행 연산을 계속하여 해를 찾을 때까지 진행한다. 즉, 행렬을 축소된 행 사다리꼴 형태로 만든다.

다른 관점에서는 알고리즘을 분석하는 데 매우 유용한데, 행렬 소거는 원래 행렬의 행렬 분해를 생성한다. 기본 행 연산은 원래 행렬의 왼쪽에 기본 행렬을 곱하는 것으로 볼 수 있다. 또는 단일 행을 줄이는 일련의 기본 연산은 프로베니우스 행렬에 의한 곱셈으로 볼 수 있다. 그러면 알고리즘의 첫 번째 부분은 LU 분해를 계산하고, 두 번째 부분은 원래 행렬을 유일하게 결정되는 가역 행렬과 유일하게 결정되는 축소된 행 사다리꼴 행렬의 곱으로 나타낸다.

다음과 같은 n개의 미지수를 갖는 m개의 연립 일차 방정식을 생각해 보자. 오른쪽의 행렬은 이 방정식의 확대 계수 행렬이다.

: $\begin{align}&a_{11}x_1 + a_{12}x_2 +\cdots+ a_{1n}x_n = b_1 \\&a_{21}x_1 + a_{22}x_2 + \cdots + a_{2n}x_n = b_2 \\&\qquad\vdots \\&a_{m1}x_1 + a_{m2}x_2 + \cdots + a_{mn}x_n= b_m\end{align} \qquad \left[\begin{array}{cccc|c}a_{11} &a_{12} &\cdots &a_{1n} &b_1 \\a_{21} &a_{22} &\cdots &a_{2n} &b_2 \\\vdots &\vdots &\ddots &\vdots &\vdots \\a_{m1} &a_{m2} &\cdots &a_{mn} &b_m\end{array}\right]$

이 방정식이 $x_1 = c_1+d_{11}\lambda_1+\cdots+d_{1s}\lambda_s, x_2=c_2+d_{21}\lambda_1+\cdots+d_{2s}\lambda_s, \cdots, x_r=c_r+d_{r1}\lambda_1+\cdots+d_{rs}\lambda_s, x_{r+1}=\lambda_1,\ldots, x_n=\lambda_s$ ( $n=r{+}s$ 이고 $\lambda_1,..., \lambda_s$ 는 임의의 상수)라는 해를 갖는다고 하면, 이 식들은 다음과 같은 연립 일차 방정식을 간략하게 나타낸 것으로 볼 수 있다. 단, 아래에 나열된 좌변의 모든 계수가 0인 식은 $m{-}r$ 개 있다.
마찬가지로 오른쪽의 행렬은 이 방정식의 확대 계수 행렬이다.

: $\begin{align}&1x_1 + 0x_2 + \cdots + 0x_r - d_{11}x_{r+1} -\cdots- d_{1s}x_n = c_1\\&0x_1 + 1x_2 + \cdots + 0x_r - d_{21}x_{r+1} -\cdots- d_{2s}x_n = c_2\\&\qquad\vdots \\&0x_1 + 0x_2 + \cdots + 1x_r - d_{r1}x_{r+1} -\cdots- d_{rs}x_n= c_r \\&0x_1 + 0x_2 + \cdots + 0x_r + 0x_{r+1} +\cdots+ 0x_n = 0 \\&\qquad\vdots \\&0x_1 + 0x_2 + \cdots + 0x_r + 0x_{r+1} +\cdots+ 0x_n = 0\end{align} \qquad \left[ \begin{array}{ccccccc|c}1 &0 &\cdots &0 &-d_{11} &\cdots &-d_{1s} &c_1 \\0 &1 &\cdots &0 &-d_{21} &\cdots &-d_{2s} &c_2 \\\vdots &\vdots &\ddots &\vdots &\vdots & &\vdots &\vdots \\0 &0 &\cdots &1 &-d_{r1} &\cdots &-d_{rs} &c_r \\0 &0 &\cdots &0 &0 &\cdots &0 &0 \\\vdots &\vdots & &\vdots &\vdots &\ddots &\vdots &\vdots \\0 &0 &\cdots &0 &0 &\cdots &0 &0\end{array} \right]$

처음 확대 계수 행렬을 위의 확대 계수 행렬 형태로 변환하려면, 대각 성분에 주목하여 기본 행 변환을 통해 행사다리꼴행렬 형태로 변환한다. 단순화를 위해, 변수의 번호를 바꾸지 않고 주성분이 모두 대각선에 있다고 가정한다. 그러나 일반적으로 이러한 가정하에 작업을 해도 다음과 같은 형태의 행사다리꼴행렬 형태로만 변환할 수 있다. (가장 오른쪽 열의 $r{+}2$ 번째 성분 이하는 모두 0)

: $\left[ \begin{array}{ccccccc|c}1 &0 &\cdots &0 &-d_{11} &\cdots &-d_{1s} &c_1 \\0 &1 &\cdots &0 &-d_{21} &\cdots &-d_{2s} &c_2 \\\vdots &\vdots &\ddots &\vdots &\vdots & &\vdots &\vdots \\0 &0 &\cdots &1 &-d_{r1} &\cdots &-d_{rs} &c_r \\0 &0 &\cdots &0 &0 &\cdots &0 &c_{r+1} \\\vdots &\vdots & &\vdots &\vdots &\ddots &\vdots &\vdots \\0 &0 &\cdots &0 &0 &\cdots &0 &0\end{array} \right]$

이 시점에서 주어진 연립 일차 방정식이 해를 갖는 필요충분조건은 $c_{r+1}=0$ 임을 알 수 있다. 실제로 $c_{r+1}=0$ 이면 위 형태의 해가 역으로 얻어지는 것은 명확하다. 보다 현실적인 해법으로는, 미지수 k개가 정해지면 나머지 k+1개의 미지수를 포함하는 식이 풀리므로, $x_1$ 부터 $x_r$ 까지 모든 변수를 고립시킬 필요는 없다.

이것을 행렬의 언어로 말하면, 확대 계수 행렬을 행사다리꼴행렬 형태로 변환하지 않고 중간에 멈추는 것이 더 현실적이라는 것이다. 즉, 확대 계수 행렬이 다음과 같은 형태의 행사다리꼴행렬 형태로 변환되는 시점에서 그 이상의 간략화를 멈추는 것이다. 이때, 대응하는 연립 일차 방정식은 오른쪽 형태로 나타낼 수 있다.

: $\left[ \begin{array}{ccccccc|c}1 &m_{12} &\cdots &m_{1r} &-d'_{11} &\cdots &-d'_{1s} &c'_1 \\0 &1 &\cdots &m_{2r} &-d'_{21} &\cdots &-d'_{2s} &c'_2 \\\vdots &\vdots &\ddots &\vdots &\vdots & &\vdots &\vdots \\0 &0 &\cdots &1 &-d'_{r1} &\cdots &-d'_{rs} &c'_r \\0 &0 &\cdots &0 &0 &\cdots &0 &0 \\\vdots &\vdots & &\vdots &\vdots &\ddots &\vdots &\vdots \\0 &0 &\cdots &0 &0 &\cdots &0 &0\end{array}\right]\qquad\begin{align}&1x_1 + m_{12}x_2 +\cdots+ m_{1r}x_r - d'_{11}x_{r+1} -\cdots- d'_{1s}x_{n} = c'_1 \\&0x_1 + 1x_2 + \cdots + m_{2r}x_r - d'_{21}x_{r+1} -\cdots- d'_{2s}x_{n} = c'_2 \\&\qquad\vdots \\&0x_1 + 0x_2 + \cdots + 1x_r - d'_{r1}x_{r+1} -\cdots- d'_{rs}x_{n} = c'_r \\&0x_1 + 0x_2 + \cdots + 0x_r + 0x_{r+1} +\cdots+ 0x_{n} = 0 \\&\qquad\vdots \\&0x_1 + 0x_2 + \cdots + 0x_r + 0x_{r+1} +\cdots+ 0x_{n} = 0\end{align}$

따라서, 임의 상수 $\lambda_1, \ldots, \lambda_s$ 를 이용하여 $r{+}1$ 번째 이후의 s개의 변수를 $x_{r+1}=\lambda_1, x_{r+2}=\lambda_2,..., x_{n}=\lambda_s$ 로 두고, 우변으로 이항하여 아래에서부터 차례로 값을 대입함으로써 모든 해를 구할 수 있다.

다음 연립 일차 방정식의 해를 확대 계수 행렬을 사용하지 않고 가우스 소거법 알고리즘으로 구해 보자. 식의 개수가 고정되어 있다는 점과, 식의 순서를 바꾸는 것도 하나의 연산이라는 점에 유의해야 한다.

: $\begin{align}&2x_1 &+ &4x_2 &+ &2x_3 &+ &2x_4 & &=8 \\&4x_1 &+ &10x_2 &+ &3x_3 &+ &3x_4 & &=17 \\&2x_1 &+ &6x_2 &+ &x_3 &+ & x_4 & &=9 \\&3x_1 &+ &7x_2 &+ &x_3 &+ &4x_4 & &=11\end{align}$

# 먼저 전진 소거를 한다.
## 1번째 방정식을 1/2배 한다.
##: $\begin{align}& x_1 &+ & 2x_2 &+ & x_3 &+ & x_4 & &=4 \\&4x_1 &+ &10x_2 &+ &3x_3 &+ &3x_4 & &=17 \\&2x_1 &+ & 6x_2 &+ & x_3 &+ & x_4 & &=9 \\&3x_1 &+ & 7x_2 &+ & x_3 &+ &4x_4 & &=11\end{align}$
## 2번째 방정식에 1번째 방정식의 -4배를 더한다. 3번째 방정식에 1번째 방정식의 -2배를 더한다. 4번째 방정식에 1번째 방정식의 -3배를 더한다.
##: $\begin{align}&x_1 &+ &2x_2 &+ & x_3 &+ &x_4 & &=4 \\& & &2x_2 &- & x_3 &- &x_4 & &=1 \\& & &2x_2 &- & x_3 &- &x_4 & &=1 \\& & & x_2 &- &2x_3 &+ &x_4 & &=-1\end{align}$
## 2번째 방정식을 1/2배 한다.
##: $\begin{align}&x_1 &+ &2x_2 &+ & x_3 &+ &x_4 & &=4 \\& & & x_2 &- &\frac{1}{2}x_3 &- &\frac{1}{2}x_4 & &=\frac{1}{2} \\& & &2x_2 &- & x_3 &- &x_4 & &=1 \\& & & x_2 &- &2x_3 &+ &x_4 & &=-1\end{align}$
## 3번째 방정식에 2번째 방정식의 -2배를 더한다. 4번째 방정식에 2번째 방정식의 -1배를 더한다.
##: $\begin{align}&x_1 &+ &2x_2 &+ &x_3 &+ &x_4 & &=4 \\& & &x_2 &- &\frac{1}{2}x_3 &- &\frac{1}{2}x_4 & &=\frac{1}{2} \\& & & & & & &0 & &=0 \\& & & &- &\frac{3}{2}x_3 &+ &\frac{3}{2}x_4 & &=-\frac{3}{2}\end{align}$
## 3번째 방정식과 4번째 방정식을 바꾼다.
##: $\begin{align}&x_1 &+ &2x_2 &+ &x_3 &+ &x_4 & &=4 \\& & & x_2 &- &\frac{1}{2}x_3 &- &\frac{1}{2}x_4 & &=\frac{1}{2} \\& & & &- &\frac{3}{2}x_3 &+ &\frac{3}{2}x_4 & &=-\frac{3}{2} \\& & & & & & &0 & &=0\end{align}$

# 다음으로 후퇴 대입을 한다.
## 3번째 방정식을 $-\frac{2}{3}$ 배 한다.
##: $\begin{align}&x_1 &+ &2x_2 &+ &x_3 &+ &x_4 &=4 \\& & & x_2 &- &\frac{1}{2}x_3 &- &\frac{1}{2}x_4 &=\frac{1}{2} \\& & & & &x_3 &- &x_4 &=1 \\& & & & & & &0 &=0\end{align}$
## $x_3 = 1 + x_4$ 를 2번째 방정식에 대입한다.
##: $\begin{align}&x_1 &+ &2x_2 &+ &x_3 &+ &x_4 &=4 \\& & & x_2 & & &- &x_4 &=1 \\& & & & &x_3 &- &x_4 &=1 \\& & & & & & &0 &=0\end{align}$
## $x_3 = 1 + x_4$ 와 $x_2 = 1 + x_4$ 를 1번째 방정식에 대입한다.
##: $\begin{align}x_1 + 4x_4 &=1 \\x_2 - x_4 &=1 \\x_3 - x_4 &=1 \\0 &=0\end{align}$
그러므로, $x_4=c$ (c는 임의의 상수)라고 하면,
: $\begin{align}x_1 &=-4c+1 \\x_2 &= c+1 \\x_3 &= c+1 \\x_4 &= c\end{align}$
이로써 모든 해를 구했다.

3. 성질

기본 행 연산은 모두 가역 연산이다. 기본 행 연산의 역연산은 다음과 같다.

* 행의 치환: 역연산은 자기 자신이다.
* 행의 상수곱: 역연산은 그 행에 그 상수의 역수를 곱하는 것이다.
* 행의 합: 역연산은 더하는 대신 빼는 것이다.

두 연립일차방정식의 첨가 행렬이 하나에 기본 행 연산을 가하여 다른 하나를 얻을 수 있다면, 행동치라고 한다. 첨가 행렬이 행동치라면, 연립방정식의 해는 서로 같다.

가우스 소거법을 통해 모든 행렬은 행사다리꼴 행렬 및 기약행사다리꼴 행렬로 변환할 수 있다.

$m\times(n+1)$ 행사다리꼴 행렬 $R$ 에 대한 연립일차방정식 $Rx=0$ 에 대하여, 다음 두 조건은 서로 동치이다.

* 해가 존재한다.
* 상수항이 0이 아닌 행이 존재하지 않는다. (상수항은 $n+1$ 번째 열의 항, 0행은 선행 계수가 없는 행을 뜻한다.)

해가 존재하는 $Rx=0$ 의 경우, 다음 두 조건이 서로 동치이다.

* 해가 유일하다.
* $r=n$ . 즉, 0행이 아닌 행의 개수는 미지수의 개수와 같다. 즉, 선행 계수가 없는 열이 계수 행렬에 존재하지 않는다.

달리 말해, 해가 존재하는 $Rx=0$ 의 경우, 다음 두 조건이 서로 동치이다.

* 해가 유일하지 않다. (체의 표수가 0이라면, 이는 해가 무한히 많은 것과 동치이다.)
* $r . 즉, 0행이 아닌 행의 개수는 미지수의 개수보다 적다. 즉, 선행 계수가 없는 열이 계수 행렬에 존재한다.$

4. 응용

가우스 소거법은 행렬식, 역행렬, 계수를 계산하는 데 사용된다.

행렬식 계산

가우스 소거법을 활용하여 정사각행렬의 행렬식을 계산할 수 있다. 기본행연산을 통해 행렬식을 상수배로 변화시킬 수 있으며, 이 상수배는 기본행연산의 종류에 따라 결정된다.

* 행을 서로 바꾸면 행렬식의 부호가 바뀐다. (-1 곱)
* 행에 상수를 곱하면 행렬식은 그 상수의 역수배가 된다.
* 한 행에 다른 행의 상수배를 더하면 행렬식은 변하지 않는다.

가우스 소거법으로 행렬을 상삼각행렬 또는 0행(모든 원소가 0)을 갖는 행렬로 변환할 수 있다. 0행을 갖는 정사각행렬의 행렬식은 0이고, 상삼각행렬의 행렬식은 주대각선 원소들의 곱과 같다.

정방 행렬 A에 가우스 소거법을 적용하여 행사다리꼴 행렬 B를 얻었다면, 행렬식에 곱해진 스칼라들의 곱을 d라고 할 때, A의 행렬식은 다음과 같이 계산된다.

: $\operatorname{det}(A) = \frac{\prod\operatorname{diag}(B)}{d}.$

n × n 행렬의 경우 이 방법은 O(n³)의 연산만 필요하다.

역행렬 계산

가우스-조르단 소거법을 활용하면 정사각행렬의 역행렬을 구할 수 있다. 행렬 A의 역행렬을 구하기 위해, A에 n × n 단위 행렬을 추가하여 n × 2n 행렬 [A | I]를 만든다. 이 행렬에 기본행연산을 적용하여 기약행사다리꼴행렬로 만들면, 왼쪽 블록이 단위 행렬 I가 될 때 오른쪽 블록은 A^-1이 된다. 만약 왼쪽 블록을 I로 만들 수 없다면, A는 가역적이지 않다.

예를 들어, 다음 행렬의 역행렬을 구해보자.

: $A = \begin{bmatrix}2 & -1 & 0 \\-1 & 2 & -1 \\0 & -1 & 2\end{bmatrix}.$

단위 행렬을 추가하여 확장하면 다음과 같다.

: $[ A | I ] = \left[\begin{array}{ccc|ccc}2 & -1 & 0 & 1 & 0 & 0 \\-1 & 2 & -1 & 0 & 1 & 0 \\0 & -1 & 2 & 0 & 0 & 1\end{array}\right].$

행 연산을 통해 기약행사다리꼴행렬을 구하면 다음과 같다.

: $[ I | B ] = \left[\begin{array}{rrr|rrr}1 & 0 & 0 & \frac34 & \frac12 & \frac14 \\0 & 1 & 0 & \frac12 & 1 & \frac12 \\0 & 0 & 1 & \frac14 & \frac12 & \frac34\end{array}\right].$

따라서, A의 역행렬은 B이다.

계수(Rank) 계산

가우스 소거법을 통해 행렬의 계수를 계산할 수 있다. 행렬에 가우스 소거법을 적용하여 얻은 행사다리꼴행렬에서 0이 아닌 행의 개수가 바로 행렬의 계수이다.

예를 들어, 6 × 9 행렬을 행사다리꼴행렬로 변환하면 다음과 같을 수 있다.

: $T=\begin{bmatrix}a & * & * & *& * & * & * & * & * \\0 & 0 & b & * & * & * & * & * & * \\0 & 0 & 0 & c & * & * & * & * & * \\0 & 0 & 0 & 0 & 0 & 0 & d & * & * \\0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & e \\0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\end{bmatrix},$

여기서 별표(*)는 임의의 성분이고, a, b, c, d, e는 0이 아닌 성분이다. 이 행렬 T는 0이 아닌 행이 5개이므로, 원래 행렬의 계수는 5이다.

5. 예제

다음은 가우스 소거법을 사용하여 주어진 연립 일차 방정식을 푸는 과정을 단계별로 설명한다.

예제 1: 해가 유일한 경우

다음 연립 방정식을 보자.

: $\begin{matrix}2u &+& v &+& w &=& 5 \\4u &-& 6v && &=& -2 \\-2u &+& 7v &+& 2w &=& 9\end{matrix}$

이 방정식을 풀기 위해 가우스 소거법을 적용하면 다음과 같다.

1. 전진 소거:
* 첫째 식의 -2배를 둘째 식에 더한다.
* 첫째 식의 1배를 셋째 식에 더한다.

: $\begin{matrix} 2u &+& v &+& w &=& 5 \\ &-& 8v &-& 2w &=& -12 \\ && 8v &+& 3w &=& 14 \end{matrix}$

* 둘째 식의 1배를 셋째 식에 더한다.

: $\begin{matrix} 2u &+& v &+& w &=& 5 \\ &-& 8v &-& 2w &=& -12 \\ && && w &=& 2 \end{matrix}$

2. 후방 대입:
* `w = 2`
* `-8v - 2w = -12` 에 `w = 2` 를 대입하면, `v = 1`
* `2u + v + w = 5` 에 `w = 2`, `v = 1` 를 대입하면, `u = 1`

따라서 이 연립 방정식의 해는 `u = 1`, `v = 1`, `w = 2` 이다.

예제 2: 해가 유일한 경우 (다른 풀이)

$\begin{alignat}{4}2x &{}+{}& y &{}-{}& z &{}={}& 8 & \qquad (L_1) \\-3x &{}-{}& y &{}+{}& 2z &{}={}& -11 & \qquad (L_2) \\-2x &{}+{}& y &{}+{}& 2z &{}={}& -3 & \qquad (L_3)\end{alignat}$

위 연립 방정식과 그에 해당하는 증강 행렬에 대한 행렬 변환 과정은 아래 표와 같다.

👆

좌우로 밀어서 보기

연립 방정식	행 연산	증강 행렬



행렬이 이제 사다리꼴 형태이다.

위 표에서 가우스 소거법은 전진 소거와 후방 대입 단계를 거친다.* 전진 소거: 사다리꼴 형태를 만든다.* 후방 대입: 각 미지수의 값을 구한다.위 예시에서,* `z = -1`* `y = 3`* `x = 2`따라서 이 연립 방정식은 유일한 해 `x = 2`, `y = 3`, `z = -1` 을 갖는다.예제 3: 해가 유일하지 않은 경우다음 연립 일차 방정식의 해를 구하는 예시이다.전진 소거:

\begin{align}& x_1 &+ & 2x_2 &+ & x_3 &+ & x_4 & &=4 \\&4x_1 &+ &10x_2 &+ &3x_3 &+ &3x_4 & &=17 \\&2x_1 &+ & 6x_2 &+ & x_3 &+ & x_4 & &=9 \\&3x_1 &+ & 7x_2 &+ & x_3 &+ &4x_4 & &=11\end{align}

# 1번째 방정식을 1/2배 한다.
#:*

\begin{align}& x_1 &+ & 2x_2 &+ & x_3 &+ & x_4 & &=4 \\&4x_1 &+ &10x_2 &+ &3x_3 &+ &3x_4 & &=17 \\&2x_1 &+ & 6x_2 &+ & x_3 &+ & x_4 & &=9 \\&3x_1 &+ & 7x_2 &+ & x_3 &+ &4x_4 & &=11\end{align}

# 2번째 방정식에 1번째 방정식의 -4배를 더한다. 3번째 방정식에 1번째 방정식의 -2배를 더한다. 4번째 방정식에 1번째 방정식의 -3배를 더한다.
#:*

\begin{align}&x_1 &+ &2x_2 &+ & x_3 &+ &x_4 & &=4  \\&    &  &2x_2 &- & x_3 &- &x_4 & &=1  \\&    &  &2x_2 &- & x_3 &- &x_4 & &=1  \\&    &  & x_2 &- &2x_3 &+ &x_4 & &=-1\end{align}

# 2번째 방정식을 1/2배 한다.
#:*

\begin{align}&x_1 &+ &2x_2 &+ & x_3           &+ &x_4            & &=4 \\&    &  & x_2 &- &\frac{1}{2}x_3 &- &\frac{1}{2}x_4 & &=\frac{1}{2} \\&    &  &2x_2 &- & x_3           &- &x_4            & &=1 \\&    &  & x_2 &- &2x_3           &+ &x_4            & &=-1\end{align}

# 3번째 방정식에 2번째 방정식의 -2배를 더한다. 4번째 방정식에 2번째 방정식의 -1배를 더한다.
#:*

\begin{align}&x_1 &+ &2x_2 &+ &x_3            &+ &x_4            & &=4 \\&    &  &x_2  &- &\frac{1}{2}x_3 &- &\frac{1}{2}x_4 & &=\frac{1}{2} \\&    &  &     &  &               &  &0              & &=0 \\&    &  &     &- &\frac{3}{2}x_3 &+ &\frac{3}{2}x_4 & &=-\frac{3}{2}\end{align}

# 3번째 방정식과 4번째 방정식을 바꾼다.
#:*

\begin{align}&x_1 &+ &2x_2 &+ &x_3            &+ &x_4            & &=4 \\&    &  & x_2 &- &\frac{1}{2}x_3 &- &\frac{1}{2}x_4 & &=\frac{1}{2} \\&    &  &     &- &\frac{3}{2}x_3 &+ &\frac{3}{2}x_4 & &=-\frac{3}{2} \\&    &  &     &  &               &  &0              & &=0\end{align}

후퇴 대입

# 3번째 방정식을

-\frac{2}{3}

배 한다.
#:*

\begin{align}&x_1 &+ &2x_2 &+ &x_3            &+ &x_4            &=4 \\&    &  & x_2 &- &\frac{1}{2}x_3 &- &\frac{1}{2}x_4 &=\frac{1}{2} \\&    &  &     &  &x_3            &- &x_4            &=1 \\&    &  &     &  &               &  &0              &=0\end{align}

x_3 = 1 + x_4

를 2번째 방정식에 대입한다.
#:*

\begin{align}&x_1 &+ &2x_2 &+ &x_3 &+ &x_4 &=4 \\&    &  & x_2 &  &    &- &x_4 &=1 \\&    &  &     &  &x_3 &- &x_4 &=1 \\&    &  &     &  &    &  &0   &=0\end{align}

x_3 = 1 + x_4

와

x_2 = 1 + x_4

를 1번째 방정식에 대입한다.
#:*

\begin{align}x_1 + 4x_4 &=1 \\x_2 -  x_4 &=1 \\x_3 -  x_4 &=1 \\0          &=0\end{align}

x_4=c

(c는 임의의 상수)라고 하면, 다음과 같이 모든 해를 구할 수 있다.

:

\begin{align}x_1 &=-4c+1 \\x_2 &=  c+1 \\x_3 &=  c+1 \\x_4 &=  c\end{align}

예제 4: 역행렬 계산

가우스 소거법을 사용하여 정사각행렬의 역행렬을 계산할 수 있다.

1.

n \times n

행렬

M

에

n \times n

단위행렬을 추가하여

n \times 2n

행렬로 만든다.
2. 이 행렬에 기본행연산을 가하여 왼쪽 블록을 단위 행렬로 만든다.
3. 행렬

\tilde M

은

M^{-1}

과 같다.

예제:

다음과 같은 행렬

M

의 역행렬을 계산해보자.
:

M = \begin{pmatrix}-1 & 1 & 2  \\3 & -1 & 1  \\-1 & 3 & 4\end{pmatrix}

기본행연산을 가하면, 다음과 같다.
:

\begin{align}\begin{pmatrix}\ A &\vert& I\end{pmatrix}  &\to \left( \left. \begin{matrix}-1 & 1 & 2  \\3 & -1 & 1  \\-1 & 3 & 4  \\\end{matrix} \ \ \right| \ \ \begin{matrix}1 & 0 & 0  \\0 & 1 & 0  \\0 & 0 & 1  \\\end{matrix} \right)\\&\to\left(\left. \begin{matrix}-1 & 1 & 2  \\0 & 2 & 7  \\0 & 2 & 2  \\\end{matrix} \right| \begin{matrix}1 & 0 & 0  \\3 & 1 & 0  \\-1 & 0 & 1  \\\end{matrix} \right)\\&\to\left(\left. \begin{matrix}-1 & 1 & 2  \\0 & 2 & 7  \\0 & 0 & -5  \\\end{matrix} \right| \begin{matrix}1 & 0 & 0  \\3 & 1 & 0  \\-4 & -1 & 1  \\\end{matrix}\right)\\&\to\left( \left. \begin{matrix}1 & -1 & -2  \\0 & 1 & 3.5  \\0 & 0 & 1  \\\end{matrix} \right| \begin{matrix}-1 & 0 & 0  \\1.5 & 0.5 & 0  \\0.8 & 0.2 & -0.2  \\\end{matrix} \right)\\&\to\left( \left. \begin{matrix}1 & -1 & 0  \\0 & 1 & 0  \\0 & 0 & 1  \\\end{matrix} \ \ \right| \ \ \begin{matrix}0.6 & 0.4 & -0.4  \\-1.3 & -0.2 & 0.7  \\0.8 & 0.2 & -0.2  \\\end{matrix} \right) \\& \to \left( \left. \begin{matrix}1 & 0 & 0  \\0 & 1 & 0  \\0 & 0 & 1  \\\end{matrix} \ \ \right| \ \ \begin{matrix}-0.7 & 0.2 & 0.3  \\-1.3 & -0.2 & 0.7  \\0.8 & 0.2 & -0.2  \\\end{matrix} \right)\end{align}

따라서

M^{-1}

은 다음과 같다.
:

M^{-1}=\begin{pmatrix}-0.7 & 0.2 & 0.3  \\-1.3 & -0.2 & 0.7  \\0.8 & 0.2 & -0.2\end{pmatrix}

5.1. 해가 유일한 연립 선형 방정식

주어진 연립 선형 방정식의 해를 구하기 위해 가우스 소거법을 적용하는 과정을 살펴보자. 가우스 소거법은 주어진 방정식을 사다리꼴 형태로 변환한 후, 후방대입을 통해 해를 구하는 방법이다.

다음과 같은 연립 선형 방정식을 예시로 들어보자.

: $\begin{matrix}2u &+& v &+& w &=& 5 \\4u &-& 6v && &=& -2 \\-2u &+& 7v &+& 2w &=& 9\end{matrix}$

먼저, 첫 번째 식을 이용하여 두 번째와 세 번째 식의 `u` 항을 소거한다.

* 첫째 식의 -2배를 둘째 식에 더한다.
* 첫째 식의 1배를 셋째 식에 더한다.

그 결과는 다음과 같다.

: $\begin{matrix}2u &+& v &+& w &=& 5 \\&-& 8v &-& 2w &=& -12 \\&& 8v &+& 3w &=& 14\end{matrix}$

이제 두 번째 식을 이용하여 세 번째 식의 `v` 항을 소거한다.

* 둘째 식의 1배를 셋째 식에 더한다.

그러면 다음과 같은 사다리꼴 형태의 방정식을 얻는다.

: $\begin{matrix}2u &+& v &+& w &=& 5 \\&-& 8v &-& 2w &=& -12 \\&& && w &=& 2\end{matrix}$

이제 후방대입을 통해 각 미지수의 값을 구할 수 있다. 후방대입은 가장 아래의 식부터 시작하여 위로 올라가면서 각 미지수를 구하는 방법이다.

* `w = 2`
* `-8v - 2w = -12` 에 `w = 2` 를 대입하면, `v = 1`
* `2u + v + w = 5` 에 `w = 2`, `v = 1` 를 대입하면, `u = 1`

따라서 이 연립 방정식의 해는 `u = 1`, `v = 1`, `w = 2` 이다.

---

다른 예시를 통해 가우스 소거법의 적용 과정을 더 자세히 살펴보자.

$\begin{alignat}{4}2x &{}+{}& y &{}-{}& z &{}={}& 8 & \qquad (L_1) \\-3x &{}-{}& y &{}+{}& 2z &{}={}& -11 & \qquad (L_2) \\-2x &{}+{}& y &{}+{}& 2z &{}={}& -3 & \qquad (L_3)\end{alignat}$

아래 표는 연립 방정식과 그에 해당하는 증강 행렬에 동시에 적용된 행렬 변환 과정을 보여준다. 실제로는 방정식 형태보다 컴퓨터 처리에 더 적합한 증강 행렬을 사용한다.

👆

좌우로 밀어서 보기

연립 방정식	행 연산	증강 행렬



행렬이 이제 사다리꼴 형태(또는 삼각형 형태)이다.

위 표에서 볼 수 있듯이, 가우스 소거법은 다음과 같은 단계로 진행된다.1. 전진 소거: 첫 번째 방정식을 이용하여 아래 방정식들의 첫 번째 미지수를 소거하고, 두 번째 방정식을 이용하여 아래 방정식들의 두 번째 미지수를 소거하는 과정을 반복하여 사다리꼴 형태를 만든다.2. 후방 대입: 사다리꼴 형태의 가장 아래 식부터 위로 올라가면서 각 미지수의 값을 구한다.위 예시에서,* `z = -1`* `y = 3`* `x = 2`따라서 이 연립 방정식은 유일한 해 `x = 2`, `y = 3`, `z = -1` 을 갖는다.행렬을 사다리꼴 형태로 만드는 데서 멈추지 않고, 위 표의 마지막처럼 축소된 사다리꼴 형태(기약 사다리꼴 형태)가 될 때까지 행렬 변환을 계속하는 방법을 가우스-조르단 소거법이라고 한다.

5.2. 해가 유일하지 않거나 없는 연립 선형 방정식

행렬이 정칙(Nonsingular)인지 비정칙(Singular)인지에 따라 해가 유일하지 않거나 없을 수 있다.정칙 행렬의 경우, 식 2와 3을 바꾸어 해결하는 예시는 다음과 같다.:

\begin{cases}10u + 2v + -1w & = \ 27 \\-3u + -6v + 2w & = \ -61.5 \\u + v + 5w & = \ -21.5\end{cases}

비정칙 행렬의 경우, 해가 없는 경우는 다음과 같다.
:

\begin{cases}u + v + w & = \ ? \\2u + 2v + 5w & = \ ? \\4u + 4v + 8w & = \ ? \\\end{cases}

\begin{cases}u + v + w & = \ ? \\3w & = \ ? \\4w & = \ ?\end{cases}

다음은 연립 일차 방정식의 해를 구하는 과정을 증강 행렬을 사용하여 나타낸 표이다.

👆

좌우로 밀어서 보기

연립 방정식	행 연산	증강 행렬



행렬이 이제 사다리꼴 형태(또는 삼각형 형태)이다.

위 표에서 두 번째 열은 수행된 행 연산을 나타낸다. 행렬이 사다리꼴 형태가 되면 알고리즘의 첫 번째 부분이 완료된다. 이후 역대입을 통해 각 미지수를 풀면, z=-1, y=3, x=2 임을 알 수 있다. 따라서 원래 연립 방정식은 유일한 해를 갖는다.행렬을 축소된 사다리꼴 형태까지 변환하는 과정을 가우스-조르단 소거법이라고 한다.다음은 확대 계수 행렬을 사용하지 않고 가우스 소거법으로 연립 일차 방정식의 해를 구하는 예시이다.전진 소거# 1번째 방정식을 1/2배 한다.#:*

\begin{align}& x_1 &+ & 2x_2 &+ & x_3 &+ & x_4 & &=4 \\&4x_1 &+ &10x_2 &+ &3x_3 &+ &3x_4 & &=17 \\&2x_1 &+ & 6x_2 &+ & x_3 &+ & x_4 & &=9 \\&3x_1 &+ & 7x_2 &+ & x_3 &+ &4x_4 & &=11\end{align}

# 2번째 방정식에 1번째 방정식의 -4배를 더한다. 3번째 방정식에 1번째 방정식의 -2배를 더한다. 4번째 방정식에 1번째 방정식의 -3배를 더한다.
#:*

\begin{align}&x_1 &+ &2x_2 &+ & x_3 &+ &x_4 & &=4  \\&    &  &2x_2 &- & x_3 &- &x_4 & &=1  \\&    &  &2x_2 &- & x_3 &- &x_4 & &=1  \\&    &  & x_2 &- &2x_3 &+ &x_4 & &=-1\end{align}

# 2번째 방정식을 1/2배 한다.
#:*

\begin{align}&x_1 &+ &2x_2 &+ & x_3           &+ &x_4            & &=4 \\&    &  & x_2 &- &\frac{1}{2}x_3 &- &\frac{1}{2}x_4 & &=\frac{1}{2} \\&    &  &2x_2 &- & x_3           &- &x_4            & &=1 \\&    &  & x_2 &- &2x_3           &+ &x_4            & &=-1\end{align}

# 3번째 방정식에 2번째 방정식의 -2배를 더한다. 4번째 방정식에 2번째 방정식의 -1배를 더한다.
#:*

\begin{align}&x_1 &+ &2x_2 &+ &x_3            &+ &x_4            & &=4 \\&    &  &x_2  &- &\frac{1}{2}x_3 &- &\frac{1}{2}x_4 & &=\frac{1}{2} \\&    &  &     &  &               &  &0              & &=0 \\&    &  &     &- &\frac{3}{2}x_3 &+ &\frac{3}{2}x_4 & &=-\frac{3}{2}\end{align}

# 3번째 방정식과 4번째 방정식을 바꾼다.
#:*

\begin{align}&x_1 &+ &2x_2 &+ &x_3            &+ &x_4            & &=4 \\&    &  & x_2 &- &\frac{1}{2}x_3 &- &\frac{1}{2}x_4 & &=\frac{1}{2} \\&    &  &     &- &\frac{3}{2}x_3 &+ &\frac{3}{2}x_4 & &=-\frac{3}{2} \\&    &  &     &  &               &  &0              & &=0\end{align}

후퇴 대입
# 3번째 방정식을

-\frac{2}{3}

배 한다.
#:*

\begin{align}&x_1 &+ &2x_2 &+ &x_3            &+ &x_4            &=4 \\&    &  & x_2 &- &\frac{1}{2}x_3 &- &\frac{1}{2}x_4 &=\frac{1}{2} \\&    &  &     &  &x_3            &- &x_4            &=1 \\&    &  &     &  &               &  &0              &=0\end{align}

x_3 = 1 + x_4

를 2번째 방정식에 대입한다.
#:*

\begin{align}&x_1 &+ &2x_2 &+ &x_3 &+ &x_4 &=4 \\&    &  & x_2 &  &    &- &x_4 &=1 \\&    &  &     &  &x_3 &- &x_4 &=1 \\&    &  &     &  &    &  &0   &=0\end{align}

x_3 = 1 + x_4

와

x_2 = 1 + x_4

를 1번째 방정식에 대입한다.
#:*

\begin{align}x_1 + 4x_4 &=1 \\x_2 -  x_4 &=1 \\x_3 -  x_4 &=1 \\0          &=0\end{align}

x_4=c

(c는 임의의 상수)라고 하면, 다음과 같이 모든 해를 구할 수 있다.
:

\begin{align}x_1 &=-4c+1 \\x_2 &=  c+1 \\x_3 &=  c+1 \\x_4 &=  c\end{align}

5.3. 역행렬의 계산

가우스 소거법을 사용하여 정사각행렬의 역행렬을 계산할 수 있다. $n \times n$ 행렬 $M$ 의 역행렬은 다음과 같이 계산한다.

1. $M$ 에 $n \times n$ 단위행렬을 추가하여 $n \times 2n$ 행렬로 만든다.
: $\begin{pmatrix}M_{1,1}&\cdots&M_{1,n}&1&\cdots&0\\\vdots&\ddots&\vdots&\vdots&\ddots&\vdots\\M_{n,1}&\cdots&M_{n,n}&0&\cdots&1\end{pmatrix}$

2. 이 행렬에 기본행연산을 가하여 아래와 같은 형태로 만든다.
: $\begin{pmatrix}1&\cdots&0&\tilde M_{11}&\cdots&\tilde M_{1,n}\\\vdots&\ddots&\vdots&\ddots&\vdots&\ddots\\0&\cdots&1&\tilde M_{n,1}&\cdots&\tilde M_{n,n}\end{pmatrix}$

3. 행렬 $\tilde M$ 은 $M^{-1}$ 과 같다.
: $\tilde M=M^{-1}$

예제 1:

다음과 같은 행렬 $M$ 의 역행렬을 계산해보자.
: $M = \begin{pmatrix}-1 & 1 & 2 \\3 & -1 & 1 \\-1 & 3 & 4\end{pmatrix}$

기본행연산을 가하면, 다음과 같다.
: $\begin{align}\begin{pmatrix}\ A &\vert& I\end{pmatrix} &\to \left( \left. \begin{matrix}-1 & 1 & 2 \\3 & -1 & 1 \\-1 & 3 & 4 \\\end{matrix} \ \ \right| \ \ \begin{matrix}1 & 0 & 0 \\0 & 1 & 0 \\0 & 0 & 1 \\\end{matrix} \right)\\&\to\left(\left. \begin{matrix}-1 & 1 & 2 \\0 & 2 & 7 \\0 & 2 & 2 \\\end{matrix} \right| \begin{matrix}1 & 0 & 0 \\3 & 1 & 0 \\-1 & 0 & 1 \\\end{matrix} \right)\\&\to\left(\left. \begin{matrix}-1 & 1 & 2 \\0 & 2 & 7 \\0 & 0 & -5 \\\end{matrix} \right| \begin{matrix}1 & 0 & 0 \\3 & 1 & 0 \\-4 & -1 & 1 \\\end{matrix}\right)\\&\to\left( \left. \begin{matrix}1 & -1 & -2 \\0 & 1 & 3.5 \\0 & 0 & 1 \\\end{matrix} \right| \begin{matrix}-1 & 0 & 0 \\1.5 & 0.5 & 0 \\0.8 & 0.2 & -0.2 \\\end{matrix} \right)\\&\to\left( \left. \begin{matrix}1 & -1 & 0 \\0 & 1 & 0 \\0 & 0 & 1 \\\end{matrix} \ \ \right| \ \ \begin{matrix}0.6 & 0.4 & -0.4 \\-1.3 & -0.2 & 0.7 \\0.8 & 0.2 & -0.2 \\\end{matrix} \right) \\& \to \left( \left. \begin{matrix}1 & 0 & 0 \\0 & 1 & 0 \\0 & 0 & 1 \\\end{matrix} \ \ \right| \ \ \begin{matrix}-0.7 & 0.2 & 0.3 \\-1.3 & -0.2 & 0.7 \\0.8 & 0.2 & -0.2 \\\end{matrix} \right)\end{align}$
따라서 $M^{-1}$ 은 다음과 같다.
: $M^{-1}=\begin{pmatrix}-0.7 & 0.2 & 0.3 \\-1.3 & -0.2 & 0.7 \\0.8 & 0.2 & -0.2\end{pmatrix}$

예제 2:

가우스-조르단 소거법은 가우스 소거법의 변형으로, 행렬의 역행렬을 구하는 데 사용될 수 있다(역행렬이 존재하는 경우). $n \times n$ 크기의 정방 행렬 $A$ 가 주어졌을 때, 행렬의 기본 변환을 사용하여 역행렬(가역 행렬)을 계산할 수 있다.

1. $n \times n$ 단위 행렬을 $A$ 의 오른쪽에 추가하여 $[A | I]$ 형태의 $n \times 2n$ 블록 행렬을 만든다.
2. 기본 행 연산을 적용하여 이 $n \times 2n$ 행렬의 기약 행 사다리꼴 형태를 구한다.
3. 행렬 $A$ 는 왼쪽 블록을 단위 행렬 $I$ 로 줄일 수 있는 경우에만 가역적이다. 이 경우 최종 행렬의 오른쪽 블록은 $A^{-1}$ 이다. 알고리즘이 왼쪽 블록을 $I$ 로 줄일 수 없으면 $A$ 는 가역적이지 않다.

예를 들어, 다음 행렬을 고려해보자.
: $A =\begin{bmatrix}2 & -1 & 0 \\-1 & 2 & -1 \\0 & -1 & 2\end{bmatrix}.$

이 행렬의 역행렬을 구하려면 단위 행렬을 추가한 다음 3 × 6 행렬로 행렬을 확장한다.
: $[ A | I ] =\left[\begin{array}{ccc|ccc}2 & -1 & 0 & 1 & 0 & 0 \\-1 & 2 & -1 & 0 & 1 & 0 \\0 & -1 & 2 & 0 & 0 & 1\end{array}\right].$

행 연산을 수행하여 이 확장 행렬의 기약 행 사다리꼴 형태가 다음과 같음을 확인할 수 있다.
: $[ I | B ] =\left[\begin{array}{rrr|rrr}1 & 0 & 0 & \frac34 & \frac12 & \frac14 \\0 & 1 & 0 & \frac12 & 1 & \frac12 \\0 & 0 & 1 & \frac14 & \frac12 & \frac34\end{array}\right].$

각 행 연산을 기본 행렬의 왼쪽 곱으로 생각할 수 있다. $B$ 를 이러한 기본 행렬들의 곱으로 나타내면, 왼쪽에서 $BA = I$ 임을 보였으므로 $B = A^{-1}$ 이다. 오른쪽에서는 $BI = B$ 를 기록했는데, 이는 원하는 역행렬이다. 이 역행렬을 구하는 절차는 모든 크기의 정방 행렬에 적용할 수 있다.

6. 역사

가우스 소거법은 고대 중국의 수학책인 구장산술의 8장 "직사각형 배열"에서 처음 등장한다. 이 책에서는 2개에서 5개의 방정식을 가진 18개의 문제를 가우스 소거법으로 풀이한다. 이 책은 서기 179년에 처음 언급되었지만, 일부 내용은 기원전 150년경에 쓰여진 것으로 추정된다. 3세기에 유휘가 이 책에 주석을 달았다.

유럽에서는 아이작 뉴턴의 연구에서 가우스 소거법이 비롯되었다. 1670년, 뉴턴은 당시 알려진 대수학 책에는 연립 방정식을 푸는 방법이 없다고 지적하며 가우스 소거법을 제시했다. 케임브리지 대학교는 뉴턴이 학계를 떠난 후 오랜 시간이 지난 1707년에 그의 연구를 아리트메티카 유니버살리스라는 책으로 출판했다. 이 책은 널리 모방되었고, 18세기 말에는 대수학 교과서의 표준적인 내용이 되었다.

1810년, 칼 프리드리히 가우스는 대칭 소거를 위한 표기법을 고안했다. 이 표기법은 19세기에 최소 제곱법의 정규 방정식을 푸는 데 사용되었다. 고등학교에서 가르치는 알고리즘은 1950년대에 가우스의 이름을 따서 명명되었는데, 이는 이 주제의 역사에 대한 혼란 때문이었다.

일부 저자들은 행렬이 사다리꼴 형태가 될 때까지만을 "가우스 소거법"이라 하고, 축차소거형태가 될 때까지를 가우스-조르단 소거법이라고 한다. 가우스-조르단 소거법은 1888년 빌헬름 조르단이 설명한 가우스 소거법의 변형이다. 그러나 이 방법은 같은 해에 클라센이라는 사람의 논문에도 등장한다. 조르단과 클라센은 가우스-조르단 소거법을 독립적으로 발견했을 가능성이 있다.

7. 계산 효율성

가우스 소거법의 계산 효율을 측정하는 방법 중 하나는 필요한 산술 연산의 수를 세는 것이다. 예를 들어, n개의 미지수를 가진 n개의 연립 일차 방정식을 풀기 위해 행렬을 사다리꼴 형태로 만들고, 역순으로 각 미지수를 풀면, n(n+1)/2번의 나눗셈, (2n³ + 3n² - 5n)/6번의 곱셈, (2n³ + 3n² - 5n)/6번의 뺄셈이 필요하다. 따라서 총 약 2n³/3번의 연산이 필요하며, 이는 O(n³)의 시간 복잡도를 갖는다.

계수가 부동 소수점 수나 유한체로 표현될 때는 각 연산 시간이 거의 일정하므로 이 복잡도가 전체 계산 시간을 잘 나타낸다. 그러나 계수가 정수나 정확하게 표현된 유리수인 경우, 중간 계산 결과가 매우 커질 수 있어 비트 복잡도는 더 커질 수 있다.

Bareiss 알고리즘은 이러한 중간 항의 증가를 방지하는 가우스 소거법의 변형이다. 이 알고리즘은 O(n³)의 산술적 복잡도를 유지하면서, 비트 복잡도는 O(n⁵)를 갖는다.

가우스 소거법은 수천 개의 방정식과 미지수를 가진 시스템에 사용할 수 있지만, 수백만 개의 방정식을 가진 시스템에서는 비용이 너무 커진다. 이러한 대규모 시스템은 주로 반복적 방법으로 해결한다.

8. 수치적 안정성

가우스 소거법은 대각우세 행렬 또는 양정부호 행렬에 대해 수치적으로 안정적이다. 일반적인 행렬의 경우, 부분 피벗 선택을 사용할 때 가우스 소거법은 일반적으로 안정적인 것으로 간주되지만, 불안정한 안정적인 행렬의 예도 존재한다.

대각 성분이 0이 되는 경우에는, 피벗 선택이라고 하는 식의 교환을 수행할 필요가 있다. 대각 성분이 0이 되는 경우 외에도, 대각 성분의 절댓값이 최대인 계수가 되도록 피벗 선택을 하는 편이 해의 반올림 오차를 줄일 수 있다. 단, 이는 행렬 요소의 절댓값이 거의 같은 크기일 경우에만 성립하며, 스케일링(전처리로서 방정식에 적절한 정칙 대각 행렬을 곱하여 등가적인 방정식으로 변환하는 것)을 하지 않고 피벗 선택을 하면 오히려 정확도가 저하되는 경우도 있으므로 주의가 필요하다.

피벗 선택에는 부분 선택법과 완전 선택법이 있다. 절댓값이 최대인 계수를 탐색하는 범위가 부분 선택법은 소거 열(아래 방향)뿐인 반면, 완전 선택법은 모든 항목(오른쪽 및 아래 방향)이다. 완전 선택법이 계산 정확도는 높지만 계산 속도 및 알고리즘의 복잡성 면에서 불리하기 때문에, 완전 선택법의 채용은 현실적으로 적다.

9. 일반화

가우스 소거법은 실수뿐만 아니라 임의의 체에서 수행될 수 있다.

부흐베르거 알고리즘은 가우스 소거법을 다항 방정식계로 일반화한 것이다. 이 일반화는 단항식 순서의 개념에 크게 의존한다. 변수에 대한 순서의 선택은 이미 가우스 소거법에 암시적으로 나타나 있으며, 피벗 위치를 선택할 때 왼쪽에서 오른쪽으로 작업하도록 선택하는 것으로 나타난다.

2차 이상의 텐서의 계수를 계산하는 것은 NP-hard 문제이다. 따라서 P ≠ NP라면 고차 텐서(행렬은 배열로 표현된 2차 텐서이다)에 대한 가우스 소거법의 다항 시간 유사 알고리즘은 존재할 수 없다.

10. 의사 코드

다음 의사 코드에서 `A[i, j]`는 행렬의 행, 열 원소를 나타내며, 인덱스는 1부터 시작한다. 이 변환은 '제자리에서' 수행되어 원래 행렬은 행 사다리꼴 형태로 대체된다.

```
h := 1 /* 피벗 행 초기화 */
k := 1 /* 피벗 열 초기화 */

while h ≤ m and k ≤ n
/* k번째 피벗 찾기: */
i_max := 최댓값 인덱스 (i = h ... m, abs(A[i, k]))
if A[i_max, k] = 0
/* 이 열에 피벗이 없으면 다음 열로 이동 */
k := k + 1
else
행 바꾸기(h, i_max)
/* 피벗 아래 모든 행에 대해 수행: */
for i = h + 1 ... m:
f := A[i, k] / A[h, k]
/* 피벗 열의 아래쪽을 0으로 채우기: */
A[i, k] := 0
/* 현재 행의 나머지 모든 원소에 대해 수행: */
for j = k + 1 ... n:
A[i, j] := A[i, j] - A[h, j] * f
/* 피벗 행과 열 증가 */
h := h + 1
k := k + 1
```

이 알고리즘은 절댓값이 가장 큰 피벗을 선택하는 부분 피벗 선택을 사용한다. 이는 피벗 위치의 원소가 0인 경우 필요하며, 부동 소수점을 사용할 때 알고리즘의 수치적 안정성을 향상시킨다.

이 절차가 완료되면 행렬은 행 사다리꼴 형태가 되고, 해당 연립 일차 방정식은 역대입을 통해 풀 수 있다.