가우스 소거법 문서 원본 보기

[[분류:수치 해석]]
[[선형대수학]]에서, '''가우스 소거법'''은 [[연립일차방정식]]을 풀이하는 [[알고리즘]]이다. 풀이 과정에서, 일부 미지수가 차츰 소거되어 결국 남은 미지수에 대한 [[선형 결합]]으로 표현되면서 풀이가 완성된다. 가우스 소거법은 보통 [[행렬]]을 사용하며, [[첨가 행렬]]을 그와 풀이가 같은 더 간단한 행렬로 변환하여 풀이를 완성한다. 가우스 소거법은 [[행렬식]]과 [[역행렬]]의 계산에도 응용된다.

== 정의 ==
[[체 (수학)|체]] <math>K</math>에 대하여, <math>n</math>개의 미지수에 대한 <math>m</math>개의 방정식으로 구성된 [[연립일차방정식]]
:<math>Mx=0</math>
이 주어졌다고 하자. 여기서
:<math>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}</math>
은 주어진 <math>m\times(n+1)</math> 행렬이고,
:<math>x=\begin{pmatrix}x_1\\x_2\\\vdots\\x_n\\1\end{pmatrix}</math>
은 <math>n</math>개의 미지수를 포함하는 열벡터이다. 즉, 이는 풀어서 쓰면 다음과 같다.
:<math>M_{11}x_1+M_{12}x_2+\cdots+M_{1,n}x_n+M_{1,n+1}=0</math>
:<math>M_{21}x_1+M_{22}x_2+\cdots+M_{2,n}x_n+M_{2,n+1}=0</math>
::::::::<math>\vdots</math>
:<math>M_{m1}x_1+M_{m2}x_2+\cdots+M_{m,n}x_n+M_{m,n+1}=0</math>

=== 기본 행 연산 ===
이 경우, 이 연립방정식에 다음과 같은 세 가지 연산을 가할 수 있다. 이들을 '''기본 행 연산'''이라고 한다.
* (행의 치환) <math>M</math>의 <math>i</math>번째 행과 <math>j</math>번째 행을 서로 바꾼다.

* (행의 상수곱) <math>i</math>번째 행을 0이 아닌 임의의 상수 <math>a\in K\setminus\{0\}</math>으로 곱한다.

* (행의 합) 임의의 상수 <math>a\in K</math>에 대하여, <math>i</math>번째 행의 <math>a</math>배를 <math>j</math>번째 행에 더한다.

=== 행사다리꼴행렬 ===
일반적으로 [[사다리꼴행렬]](Echelon matrix,에쉴론 메트릭스, 또는 행사다리꼴행렬)은,

<math>m\times(n+1)</math> 행렬 <math>M</math>에 대하여, <math>j_0(i)=\min\{j\le n\colon M_{ij}\ne0\}</math>이라고 하면, <math>M_{i,j_0(i)}</math>를 <math>i</math>번째 행의 '''선행 계수'''(先行係數, {{llang|en|leading coefficient}})라고 한다. 선행 계수는 존재하지 않을 수 있다.

<math>m\times(n+1)</math> 행렬 <math>M</math>이 다음 조건을 만족시키면, <math>M</math>을 '''행사다리꼴행렬'''(사다리꼴行列, {{llang|en|échelon matrix}})이라고 한다.
* 만약 <math>0=M_{i1}=\cdots=M_{in}</math>이라면, 모든 <math>i\le i'</math>에 대하여 <math>0=M_{i'1}=\cdots=M_{i'n}</math>이다.
* 만약 <math>i<i'</math>이며 <math>j_0(i)</math>와 <math>j_0(i')</math>가 존재한다면, <math>j_0(i)<j_0(i')</math>이다.
<math>m\times(n+1)</math> 행렬 <math>M</math>이 다음 조건을 만족시키면, <math>M</math>을 '''기약행사다리꼴행렬'''(旣約行사다리꼴行列, {{llang|en|reduced-row échelon matrix}})이라고 한다.
* <math>M</math>은 행사다리꼴행렬이다.
* <math>j_0(i)</math>가 존재한다면, <math>M_{i,j_0(i)}=1</math>이며, 모든 <math>i'\ne i</math>에 대하여 <math>M_{i',j_0(i)}=0</math>이다.
즉, 행사다리꼴행렬은 행렬의 항들이 대략 위에는 사다리꼴, 밑에는 0인 형태의 행렬이다. 기약행사다리꼴행렬 조건은 행사다리꼴행렬 조건보다 더 강한 조건이다.

예를 들어, 다음과 같은 행렬은 행사다리꼴행렬이다.
:<math>\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}
</math>
다음과 같은 행렬은 기약행사다리꼴행렬이다.
:<math>\begin{pmatrix}
1 & 0 & a_1 & 0 & a_2 \\
0 & 1 & a_3 & 0 & a_4 \\
0 & 0 & 0 & 1 & a_5
\end{pmatrix}
</math>

=== 가우스 소거법 ===
'''가우스 소거법'''은 <math>m\times n</math> 행렬 <math>M</math>을 기본행연산을 가하여 행사다리꼴행렬로 만드는 알고리즘이며, 다음과 같다. 먼저 첫번째 행을 다음과 같이 처리한다.
# 선행 계수가 위치하는 가장 작은 열수 <math>j_1\le n</math>을 찾는다.
# <math>M_{1j_1}=0</math>이라면, 첫번째 행을 <math>M_{i_1j_1}\ne0</math>인 어떤 <math>i_1>1</math>번째 행과 치환한다.
# 모든 <math>i>1</math>번째 행에 첫번째 행의 <math>-M_{ij_1}/M_{1j_1}</math>배를 더해, <math>M_{1j_1}</math> 밑의 항들을 0으로 만든다.

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

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

만약 어떤 <math>j_{r+1}\le n</math>가 존재하지 않는다면, <math>r</math>번째 행에서 멈춘다. 만약 항상 <math>j_k\le n</math>를 찾을 수 있다면, 모든 <math>k=1,2,\ldots,m</math>번째 행에 대하여 순차적으로 위와 같이 처리하며, <math>r=n</math>으로 둔다.
기약행사다리꼴행렬을 원한다면, 찾았던 모든 <math>j_k=j_r,j_{r-2},\ldots,j_1</math>에 대하여 순차적으로 다음과 같은 단계를 추가로 거친다.
# <math>k</math>번째 행에 <math>1/M_{kj_k}</math>를 곱해, <math>M_{kj_k}</math>를 1로 만든다.
# 모든 <math>i<k</math>번째 행에 <math>k</math>번째 행의 <math>-M_{ij_k}</math>배를 더해, <math>M_{kj_k}</math> 위의 항들을 0으로 만든다.

여기서 <math>r\le m</math>이며 <math>r\le n</math>인 데 주의하자. 사실, 이는 행렬의 [[계수 (선형대수학)|계수]]이다.
*기약행사다리꼴행렬의 과정을 특히 [[빌헬름 요르단|조단]]이 제시한 "가우스 조단 소거법"으로 부른다.

== 성질 ==
=== 기본행연산 ===
세 가지 기본행연산은 모두 [[가역 함수|가역 연산]]이다.
* 행의 치환의 역연산은, 자기 자신이다.
* 행의 상수곱의 역연산은, 그 행에 그 상수 대신 [[역수]]를 곱하는 것이다.
* 어떤 행에 다른 행의 배수를 더하는 것의 역연산은, 더하는 대신 빼는 것이다.

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

[[기본 행렬]]은 [[단위 행렬]]에 기본행연산을 한 번 가하여 얻는 행렬이다. 이에 따라, 세 가지 기본행연산은 기본 행렬 곱셈과 같다.

=== 행사다리꼴행렬 ===
가우스 소거법 알고리즘에서 알 수 있듯, 모든 연립일차방정식의 [[첨가 행렬]]은 그와 같은 해를 갖는 행사다리꼴행렬 및 기약행사다리꼴행렬로 변환할 수 있다. 따라서, 연립일차방정식의 풀이는 행사다리꼴행렬 및 기약행사다리꼴에 대한 풀이로 귀결된다.

<math>m\times(n+1)</math> 행사다리꼴행렬 <math>R</math>에 대한 연립일차방정식 <math>Rx=0</math>에 대하여, 다음 두 조건이 서로 [[동치]]이다.
* 해가 존재한다.
* 상수항이 0이 아닌 행이 존재하지 않는다. (상수항은 <math>n+1</math>번째 열의 항, 0행은 선행 계수가 없는 행을 뜻한다.)
해가 존재하는 <math>Rx=0</math>의 경우, 다음 두 조건이 서로 [[동치]]이다.
* 해가 유일하다.
* <math>r=n</math>. 즉, 0행이 아닌 행의 개수는 미지수의 개수와 같다. 즉, 선행 계수가 없는 열이 계수 행렬에 존재하지 않는다.
달리 말해, 해가 존재하는 <math>Rx=0</math>의 경우, 다음 두 조건이 서로 [[동치]]이다.
* 해가 유일하지 않다. ([[체의 표수]]가 0이라면, 이는 해가 무한히 많은 것과 동치이다.)
* <math>r<n</math>. 즉, 0행이 아닌 행의 개수는 미지수의 개수보다 적다. 즉, 선행 계수가 없는 열이 계수 행렬에 존재한다.

=== 행렬식의 계산 ===
가우스 소거법을 사용하여 [[정사각행렬]]의 [[행렬식]]을 계산할 수 있다. 이는 정사각행렬에 대하여 다음 사실들이 성립하기 때문이다.
* 기본행연산을 가하면, 행렬식은 "상수배" 변화하며, 주어진 기본행연산이 행렬식을 변화시키는 배수는 자명하다. 즉,
** 행을 치환하면, 행렬식은 -1배가 된다.
** 행에 상수곱을 하면, 행렬식은 그 상수의 역수배가 된다.
** 어떤 행에 다른 어떤 행의 상수배를 더하면, 행렬식은 변하지 않는다.
* 가우스 소거법을 통해 행렬을 행사다리꼴행렬로 변환할 수 있다. 특히 정사각행렬이므로, 이는 0행(즉 모든 항이 0인 행)을 갖거나, [[상삼각행렬]]이다.
* 0행을 갖는 정사각행렬의 행렬식은 0이다.
* 상삼각행렬의 행렬식은 모든 대각항의 곱이다.

=== 역행렬의 계산 ===
가우스 소거법을 사용하여 [[정사각행렬]]의 [[역행렬]]을 계산할 수 있다. <math>n\times n</math> 행렬 <math>M</math>의 역행렬은 다음과 같이 계산한다. <math>M</math>에 <math>n\times n</math> [[단위행렬]]을 추가하여 <math>n\times 2n</math> 행렬로 만든다.
:<math>\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}</math>
이 행렬에 기본행연산을 가하여
:<math>\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}</math>
로 만든다면, 행렬 <math>\tilde M</math>은 <math>M^{-1}</math>과 같다.
:<math>\tilde M=M^{-1}</math>

=== 계수 계산 ===
가우스 소거법을 사용하여 행렬의 [[계수 (선형대수학)|계수]]를 계산할 수 있다. <math>m\times n</math> 행렬 <math>M</math>의 계수는 가우스 소거법을 가하여 얻는 행사다리꼴행렬에서 0이 아닌 행의 계수(즉, 선행 계수의 개수) <math>r</math>이다.

== 예 ==
:<math>\left[\begin{array}{rrr|r}
1 & 3 & 1 & 9 \\
1 & 1 & -1 & 1 \\
3 & 11 & 5 & 35
\end{array}\right]\to
\left[\begin{array}{rrr|r}
1 & 3 & 1 & 9 \\
0 & -2 & -2 & -8 \\
0 & 2 & 2 & 8
\end{array}\right]\to
\left[\begin{array}{rrr|r}
1 & 3 & 1 & 9 \\
0 & -2 & -2 & -8 \\
0 & 0 & 0 & 0
\end{array}\right]\to
\left[\begin{array}{rrr|r}
1 & 0 & -2 & -3 \\
0 & 1 & 1 & 4 \\
0 & 0 & 0 & 0
\end{array}\right] </math>

=== 해가 유일한 연립 선형 방정식 ===
다음과 같은 선형 방정식이 주어졌다고 하자.
:<math>\begin{matrix}
2u  &+& v   &+& w  &=& 5 \\
4u  &-& 6v   &&    &=& -2 \\
-2u &+& 7v &+& 2w &=& 9
\end{matrix}</math>
첫 번째 열을 사다리꼴로 놓기 위해, 다음과 같은 기본행연산을 가한다.
# 첫째 식의 -2배를 둘째 식에 더한다
# 첫째 식의 1배를 셋째 식에 더한다.
그렇다면 다음과 같다.
:<math>\begin{matrix}
2u &+& v &+& w &=& 5 \\
   &-& 8v &-& 2w &=& -12 \\
    && 8v &+& 3w &=& 14
\end{matrix}
</math>
두 번째 열을 사다리꼴로 놓기 위해, 다음과 같은 기본행연산을 가한다.
<li value="3"> 둘째 식의 1배를 셋째 식에 더한다.
그러면 다음과 같다.
:<math>\begin{matrix}
2u &+& v &+& w  &=&  5 \\
   &-& 8v &-& 2w  &=&  -12 \\
   &&     &&  w   &=&  2
\end{matrix}</math>
이제 행렬이 사다리꼴이 되었다.

=== 해가 유일하지 않거나 없는 연립 선형 방정식 ===
;정칙(Nonsingular) 행렬일 경우의 예
(식 2와 3을 바꾸어 해결한다)
* <math>
\begin{cases}
10u + 2v + -1w & = \ 27 \\
-3u + -6v + 2w & = \ -61.5 \\
u + v + 5w & = \ -21.5
\end{cases}
</math>

;비정칙(Singular) 행렬일 경우의 예
(해가 없는 경우도 있다.)

* <math>
\begin{cases}
u + v + w & = \ ? \\
2u + 2v + 5w & = \ ? \\
4u + 4v + 8w & = \ ? \\
\end{cases}
</math>

* <math>
\begin{cases}
u + v + w & = \ ? \\
3w & = \ ? \\
4w & = \ ?
\end{cases}
</math>

=== 역행렬의 계산 ===
다음과 같은 행렬 <math>M</math>의 역행렬을 계산한다고 하자.
:<math>M = \begin{pmatrix}
   -1 & 1 & 2  \\
   3 & -1 & 1  \\
   -1 & 3 & 4
\end{pmatrix} </math>
기본행연산을 가하면, 다음과 같다.
:<math>\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}</math>
따라서 <math>M^{-1}</math>은 다음과 같다.
:<math>M^{-1}=\begin{pmatrix}
   -0.7 & 0.2 & 0.3  \\
   -1.3 & -0.2 & 0.7  \\
   0.8 & 0.2 & -0.2
\end{pmatrix}</math>