가우스 소거법

위키백과, 우리 모두의 백과사전.
이동: 둘러보기, 검색

선형대수학에서, 가우스 소거법(Gauß消去法, 영어: Gaussian elimination, 약자 GE)은 일차연립방정식을 풀기 위한 알고리즘이다. 한 방정식을 첫 변수에 대해 푼 다음, 이 식을 나머지 방정식에 넣어 연립 선형방정식을 푸는 방식이다. 위의 결과는 방정식과 변수의 개수가 원래 연립방정식보다 하나 적은 새로운 연립방정식이 된다. 같은 과정을 2번째 변수에 적용하고, 방정식이 하나만 남을 때까지 다른 변수들에 이 과정을 되풀이한다. 하나 남은 방정식에서는 마지막 변수만 미지변수이다. 이 방정식의 해로 바로 앞에서 얻은 미지수가 2개인 방정식의 해를 구한다. 이 과정은 모든 미지수의 값을 구할 때까지 계속된다.

정의[편집]

어떤 K에 대하여, 다음과 같은 꼴의, n-1개의 미지수에 대한 m개의 방정식으로 구성된 일차연립방정식이 주어졌다고 하자.

M\mathbf x=0

여기서

M=\begin{pmatrix}
M_{11}&M_{12}&\cdots&M_{1n}\\
M_{21}&M_{22}&\cdots&M_{2n}\\
\vdots&\vdots&\ddots&\vdots\\
M_{m1}&M_{m2}&\cdots&M_{mn}
\end{pmatrix}

은 주어진 m\times n 행렬이고,

\mathbf x=\begin{pmatrix}x_1\\x_2\\\vdots\\x_{n-1}\\1\end{pmatrix}

n-1개의 미지수를 포함하는 열벡터이다. 즉, 이는 풀어서 쓰면 다음과 같다.

M_{11}x_1+M_{12}x_2+\cdots+M_{1,n-1}x_{n-1}+M_{1n}=0
M_{21}x_1+M_{22}x_2+\cdots+M_{2,n-1}x_{n-1}+M_{2n}=0
\vdots
M_{m1}x_1+M_{m2}x_2+\cdots+M_{m,n-1}x_{n-1}+M_{mn}=0

보통, 유일한 해를 가진 일차 연립 방정식의 경우 방정식의 수는 미지수의 수와 같으며, 즉 m=n-1이다. 그러나 해가 유일하지 못한 경우나, 해가 없는 경우, 방정식이 중복되는 경우 등에서는 m\ne n-1일 수 있다.

기본행연산[편집]

이 경우, 이 연립 방정식에 다음과 같은 세 가지 연산을 가할 수 있다. 이들을 기본행연산(基本行演算, 영어: elementary row operation)이라고 한다.

  • (행의 치환) Mi번째 행과 j번째 행을 서로 바꾼다.
\begin{pmatrix}
M_{11}&M_{12}&\cdots&M_{1n}\\
\vdots&\vdots&&\vdots\\
M_{i1}&M_{i2}&\cdots&M_{in}\\
\vdots&\vdots&&\vdots\\
M_{j1}&M_{j2}&\cdots&M_{jn}\\
\vdots&\vdots&&\vdots\\
M_{m1}&M_{m2}&\cdots&M_{mn}
\end{pmatrix}\mathbf x=0
\implies\begin{pmatrix}
M_{11}&M_{12}&\cdots&M_{1n}\\
\vdots&\vdots&&\vdots\\
M_{j1}&M_{j2}&\cdots&M_{jn}\\
\vdots&\vdots&&\vdots\\
M_{i1}&M_{i2}&\cdots&M_{in}\\
\vdots&\vdots&&\vdots\\
M_{m1}&M_{m2}&\cdots&M_{mn}
\end{pmatrix}\mathbf x=0
  • (행의 상수곱) i번째 행을 0이 아닌 임의의 상수 a\in K\setminus\{0\}으로 곱한다.
\begin{pmatrix}
M_{11}&M_{12}&\cdots&M_{1n}\\
\vdots&\vdots&&\vdots\\
M_{i1}&M_{i2}&\cdots&M_{in}\\
\vdots&\vdots&&\vdots\\
M_{m1}&M_{m2}&\cdots&M_{mn}
\end{pmatrix}\mathbf x=0
\implies\begin{pmatrix}
M_{11}&M_{12}&\cdots&M_{1n}\\
\vdots&\vdots&&\vdots\\
aM_{i1}&aM_{i2}&\cdots&aM_{in}\\
\vdots&\vdots&&\vdots\\
M_{m1}&M_{m2}&\cdots&M_{mn}
\end{pmatrix}\mathbf x=0
  • (행의 합) 임의의 상수 a\in K에 대하여, i번째 행의 a배를 j번째 행에 더한다.
\begin{pmatrix}
M_{11}&M_{12}&\cdots&M_{1n}\\
\vdots&\vdots&&\vdots\\
M_{i1}&M_{i2}&\cdots&M_{in}\\
\vdots&\vdots&&\vdots\\
M_{j1}&M_{j2}&\cdots&M_{jn}\\
\vdots&\vdots&&\vdots\\
M_{m1}&M_{m2}&\cdots&M_{mn}
\end{pmatrix}\mathbf x=0
\implies\begin{pmatrix}
M_{11}&M_{12}&\cdots&M_{1n}\\
\vdots&\vdots&&\vdots\\
M_{i1}&M_{i2}&\cdots&M_{in}\\
\vdots&\vdots&&\vdots\\
aM_{i1}+M_{j1}&aM_{i2}+M_{j2}&\cdots&aM_{in}+M_{jn}\\
\vdots&\vdots&&\vdots\\
M_{m1}&M_{m2}&\cdots&M_{mn}
\end{pmatrix}\mathbf x=0

사다리꼴 행렬[편집]

가우스 소거법의 기본적인 목표는 행렬을 기본행연산을 적용하여 사다리꼴 행렬(사다리꼴行列, 영어: échelon matrix)로 만드는 것이다. m\times n 행렬 M이 다음 조건을 만족시키면, M사다리꼴 행렬이라고 한다.

  • 만약 M_{ij}=0이라면, 모든 i\le i'에 대하여 M_{i'j}=0이다.
  • j_0(i)=\min\{j\colon M_{ij}\ne0\}이라고 하면, M_{i,j_0(i)}i번째 행의 선행계수(영어: leading coefficient)라고 한다. 만약 i<i'라면, j_0(i)<j_0(i')이다.

m\times n 행렬 M이 다음 조건을 만족시키면, M기약행 사다리꼴 행렬(旣約行사다리꼴行列, 영어: reduced-row échelon matrix)이라고 한다.

  • M은 사다리꼴이다.
  • M_{i,j_0(i)}i번째 행의 선행계수라고 하자. 그렇다면 M_{i,j_0(i)}=1이며, 모든 j\ne j_0(i)에 대하여 M_{ij}=0이다.

즉, 사다리꼴 행렬은 행렬의 원소들이 대략 위에는 사다리꼴, 밑에는 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{pmatrix}
1 & 0 & a_1 & 0 & a_2 \\
0 & 1 & a_3 & 0 & a_4 \\
0 & 0 & 0 & 1 & a_5
\end{pmatrix}

가우스 소거법 알고리즘[편집]

가우스 소거법m\times n 행렬 M을 기본행연산을 가하여 사다리꼴로 만드는 알고리즘이며, 대략 다음과 같다. 각 행에 대하여, 첫 번째 행부터 각각 사다리꼴로 놓을 수 있다. 즉, i번째 행을 처리한다고 하자.

  1. 우선 선행계수가 j번째 열에 위치해 있지만 M_{ij}=0이라면, 선행계수가 0이지 않게 하기 위해 그 밑에 있는 다른 열과 치환한다.
  2. 그 뒤, i번째 행의 밑에 있는 다른 모든 행의 원소들을 i번째 행의 배수를 더해 0으로 만든다.
  3. 만약 기약행 사다리꼴을 원한다면, 다음과 같은 두 단계를 추가로 거친다.
    1. i번째 행 자체를, M_{ij}=1로 놓기 위해 상수로 곱한다.
    2. 또한, i번째 행 위에 있는 다른 행들 또한 i번째 행의 배수를 더해 0으로 만든다.

이는 의사코드로는 다음과 같다. M의 각 열벡터들을 M_1,\dots,M_m이라고 쓰자.

for i_0=1,\dots,m:
j_0\leftarrow\min\{j|\exists i_0'\ge i_0\colon M_{i_0'j}\ne0\} (j_0i_0번째 행의 선행계수의 위치. 만약 이러한 j_0이 없다면, 알고리즘을 종료시킨다.)
i_0'\in\{i_0'<i_0|M_{i_0'j}\ne0\} (i_0'i_0'>i_0이며 M_{i_0'j}\ne0인 임의의 행이라고 하자)
(M_{i_0},M_{i_0'})\leftarrow(M_{i_0'},M_{i_0}) (i_0번째 행과 i_0'번째 행을 치환)
(*) M_{i_0}\leftarrow M_{i_0}/M_{i_0j_0}
for i=i_0+1,\dots,m:
M_i\leftarrow M_i-M_{i_0}(M_{ij_0}/M_{i_0j_0}) (i번째 행에 i_0번째 행의 -M_{ij_0}/M_{j_0j_0}배를 더한다)
(*) for i=1,\dots,i_0-1:
M_i\leftarrow M_i-M_{i_0}(M_{ij_0}/M_{i_0j_0}) (i번째 행에 i_0번째 행의 -M_{ij_0}/M_{j_0j_0}배를 더한다)

의사코드는 행렬을 기약행 사다리꼴로 만든다. 만약 기약행 사다리꼴 대신 그냥 사다리꼴로 족하다면, 앞에 (*)이 붙은 단계들은 생략할 수 있다.

[편집]

다음과 같은 선형 방정식이 주어졌다고 하자.

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

첫 번째 열을 사다리꼴로 놓기 위해, 다음과 같은 기본행연산을 가한다.

  1. 첫째 식의 -2배를 둘째 식에 더한다
  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}

이제 행렬이 사다리꼴이 되었다. 그렇다면, 이제 미지수들을 가장 밑의 행으로부터 순서대로 대입하여 계산할 수 있다.

w=2
-8v-2w=-12\implies v=1
2u+v+w=5\implies u=1

풀기 곤란한 경우[편집]

정칙(Nonsingular) 행렬일 경우의 예

(식 2와 3을 바꾸어 해결한다)

  • 
\begin{cases}
10u + 2v + -1w & = \ 27 \\
-3u + -6v + 2w & = \ -61.5 \\
u + v + 5w & = \ -21.5
\end{cases}
비정칙(Singular) 행렬일 경우의 예

(해가 없는 경우도 있다.)

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

바깥 고리[편집]