행렬 $A \in \mathbb{R}^{m \times n}$에 대하여
- $i$번째 행에서 처음으로 $0$이 아닌 $a_{ij}$를 행렬 $A$의 $i$-행에 대한 선행계수(leading coefficient)라 한다.
- $A$가 다음 두 조건
- 모든 성분이 $0$인 행들은 $0$이 아닌 성분을 포함하는 행들의 아래에 위치한다.
- $0$이 아닌 성분을 포함하는 두 행에 대하여, 아래쪽 행에 있는 선행계수가 위쪽 행에 있는 선행계수보다 오른쪽에 위치한다.
을 모두 만족하면, $A$를 행사다리꼴(row echelon form, REF)이라 한다.
- $A$가 행사다리꼴이고 추가적으로 다음 조건
- $0$아닌 성분을 포함하는 행의 선행계수는 $1$이다.
- 각 행의 선행계수들의 위에 있는 성분들은 모두 $0$이다.
까지 만족하면, $A$를 기약행사다리꼴(reduced row echelon form, RREF)이라 한다. 주어진 행렬과 닮은 기약행사다리꼴 행렬은 유일하다.
$ $
다음 행렬들은 기약행사다리꼴의 예이다. \[ \begin{align*} & \begin{bmatrix} 1 & \ast & 0 & 0 & \ast & \ast \\ 0 & 0 & 1 & 0 & \ast & \ast \\ 0 & 0 & 0 & 1 & \ast & \ast \\ 0 & 0 & 0 & 0 & 0 & 0 \end{bmatrix}\!, \quad \begin{bmatrix} 1 & \ast & 0 & 0 & \ast & 0 \\ 0 & 0 & 1 & 0 & \ast & 0 \\ 0 & 0 & 0 & 1 & \ast & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 \end{bmatrix}\!. \end{align*} \]
$ $
예제 1.3.1.
Q. 다음 첨가행렬을 기본행연산을 이용하여 행사다리꼴인 행렬로 변환하여라.
\[ [ A \,|\, \mathbf{b} ] = \left[ \, \begin{array}{rrr|r}
1 & 2 & 3 & 2 \\
2 & 3 & 3 & 1 \\
2 & 1 & 2 & 0
\end{array} \, \right] \]
A. 기본행연산을 이용하여 행사다리꼴로 변환하는 방법은 다양하다. 예를 들어
\begin{align*}
\left[ \, \begin{array}{rrr|r}
1 & 2 & 3 & 2 \\
2 & 3 & 3 & 1 \\
2 & 1 & 2 & 0
\end{array} \, \right]
& \sim \left[ \, \begin{array}{rrr|r}
1 & 2 & 3 & 2 \\
0 & -1 & -3 & -3 \\
0 & -3 & -4 & -4
\end{array} \, \right]
& \begin{aligned}
R_2 \leftarrow R_2 - 2 R_1 \\
R_3 \leftarrow R_3 - 2R_1 \end{aligned} \\[1ex]
& \sim \left[ \, \begin{array}{rrr|r}
1 & 2 & 3 & 2 \\
0 & -1 & -3 & -3 \\
0 & 0 & 5 & 5
\end{array} \, \right]
& R_3 \leftarrow R_3 - 3R_2
\end{align*}
를 얻는다.$ $
$ $
예제 1.3.2.
Q. 다음 첨가행렬을 기본행연산을 이용하여 행사다리꼴인 행렬로 변환하여라.
\[ [ A \,|\, \mathbf{b} ] = \left[ \, \begin{array}{rrr|r}
1 & 2 & 3 & 2 \\
2 & 3 & 3 & 1 \\
2 & 1 & 2 & 0
\end{array} \, \right] \]
A. 앞서 예제 1.3.1에서 계산했던 $A$와 닮음인 행사다리꼴 행렬에서 시작하자.
\begin{align*}
\left[ \, \begin{array}{rrr|r}
1 & 2 & 3 & 2 \\
0 & -1 & -3 & -3 \\
0 & 0 & 5 & 5
\end{array} \, \right]
& \sim \left[ \, \begin{array}{rrr|r}
1 & 2 & 3 & 2 \\
0 & 1 & 3 & 3 \\
0 & 0 & 1 & 1
\end{array} \, \right]
& \begin{aligned}
R_2 \leftarrow -R_2 \\
R_3 \leftarrow \tfrac{1}{5} R_3 \end{aligned} \\[1ex]
& \sim \left[ \, \begin{array}{rrr|r}
1 & 2 & 0 & -1 \\
0 & 1 & 0 & 0 \\
0 & 0 & 1 & 1
\end{array} \, \right]
& \begin{aligned}
R_2 \leftarrow R_2 - 3R_3 \\
R_1 \leftarrow R_1 - 3R_3 \end{aligned} \\[1ex]
& \sim \left[ \, \begin{array}{rrr|r}
1 & 0 & 0 & -1 \\
0 & 1 & 0 & 0 \\
0 & 0 & 1 & 1
\end{array} \, \right]
& R_1 \leftarrow R_1 - 2R_2
\end{align*}
를 얻는다.$ $
$ $
주어진 선형연립방정식에 대응되는 첨가행렬 $[ A \,|\, \mathbf{b} ]$가 있을 때, 이 행렬에 기본행연산을 반복 적용하여 계수행렬 $A$부분을 행사다리꼴인 행렬로 변환하고, 그 후에 후진대입법(back substitution)을 이용하여 해를 구하는 방법을 가우스 소거법(Gaussian elimination)이라 한다. 또한 계수행렬 $A$부분을 기약행사다리꼴인 행렬로 변환하여 해를 구하는 방법을 가우스-조단 소거법(Gauss-Jordan elimination)이라 한다.
$ $
가우스 소거법을 이용하여 다음과 같은 방법으로 역행렬을 구할 수 있다.
- 주어진 정사각행렬 $A \in \mathbb{R}^{n \times n}$에 단위행렬을 첨가한 $n \times 2n$ 행렬 $[ A \,|\, I ]$를 만든다.
- 위 첨가행렬 $[ A \,|\, I ]$에 가우스 소거법을 적용하여 기약행사다리꼴로 변환한다.
- 위에서 구한 기약행사다리꼴이 $[ I \,|\, B ]$ 꼴로 주어지면 $A$의 역행렬이 존재하고 $A^{-1} = B$이다. 만약 그렇지 않다면 $A$의 역행렬은 존재하지 않는다.
$ $
예제 1.3.3.
Q. 가우스 소거법을 이용하여 다음 행렬 $A$의 역행렬을 구하여라.
\[ A = \begin{bmatrix}
1 & 2 & 3 \\
2 & 3 & 3 \\
2 & 1 & 2
\end{bmatrix} \]
A. 첨가행렬 $[ A \,|\, I ]$에 가우스 소거법을 적용하자.
\begin{align*}
& \left[ \, \begin{array}{rrr|rrr}
1 & 2 & 3 & 1 & 0 & 0 \\
2 & 3 & 3 & 0 & 1 & 0 \\
2 & 1 & 2 & 0 & 0 & 1
\end{array} \, \right] \\[1ex]
& \qquad \sim \left[ \, \begin{array}{rrr|rrr}
1 & 2 & 3 & 1 & 0 & 0 \\
0 & -1 & -3 & -2 & 1 & 0 \\
0 & -3 & -4 & -2 & 0 & 1
\end{array} \, \right]
& \begin{aligned}
R_2 \leftarrow R_2 - 2 R_1 \\
R_3 \leftarrow R_3 - 2R_1 \end{aligned} \\[1ex]
& \qquad \sim \left[ \, \begin{array}{rrr|rrr}
1 & 2 & 3 & 1 & 0 & 0 \\
0 & -1 & -3 & -2 & 1 & 0 \\
0 & 0 & 5 & 4 & -3 & 1
\end{array} \, \right] & R_3 \leftarrow R_3 - 3R_2 \\[1ex]
& \qquad \sim \left[ \, \begin{array}{rrr|rrr}
1 & 2 & 3 & 1 & 0 & 0 \\
0 & 1 & 3 & 2 & -1 & 0 \\
0 & 0 & 1 & 4/5 & -3/5 & 1/5
\end{array} \, \right]
& \begin{aligned}
R_2 \leftarrow -R_2 \\
R_3 \leftarrow \tfrac{1}{5} R_3 \end{aligned} \\[1ex]
& \qquad \sim \left[ \, \begin{array}{rrr|rrr}
1 & 2 & 0 & -7/5 & 9/5 & -3/5 \\
0 & 1 & 0 & -2/5 & 4/5 & -3/5 \\
0 & 0 & 1 & 4/5 & -3/5 & 1/5
\end{array} \, \right]
& \begin{aligned}
R_2 \leftarrow R_2 - 3R_3 \\
R_1 \leftarrow R_1 - 3R_3 \end{aligned} \\[1ex]
& \qquad \sim \left[ \, \begin{array}{rrr|rrr}
1 & 0 & 0 & -3/5 & 1/5 & -3/5 \\
0 & 1 & 0 & -2/5 & 4/5 & -3/5 \\
0 & 0 & 1 & 4/5 & -3/5 & 1/5
\end{array} \, \right]
& R_1 \leftarrow R_1 - 2R_2
\end{align*}
를 얻는다.$ $
$ $
가우스 방법은 마무리오차에 의해서 매우 큰 오차를 유발할 수 있다. 다음 예를 통해 알아보자.
$ $
예제 1.3.4.
유효숫자가 $3$개이고 $10$진법을 사용하는 컴퓨터를 가정하고, 다음 선형연립방정식을 (일반적인) 가우스 소거법으로 구해보자.
\[ \left\{ \begin{array}{rcrcr}
0.0001x & + & y & = & 2 \\[1ex]
x & + & y & = & 3
\end{array} \right. \]
첫째 식에 $-10000$을 곱하여 둘째 식에 더하면
\[ -9999y = -19997 \]
이어야 하지만, 유효숫자가 $3$개가 되도록 반올림을 하여
\[ -10000y = -20000 \]
을 얻게 된다. 이 식에 후진대입법을 통해 얻을 수 있는 해인 $x=0$, $y=2$는 실제 해인 $x \approx 1.0001$, $y \approx 1.9999$와 비교하면 적당한 해가 아님을 알 수 있다.
$ $
반면에 위 선형연립방정식의 순서를 바꾸어 \[ \left\{ \begin{array}{rcrcr} x & + & y & = & 3 \\[1ex] 0.0001x & + & y & = & 2 \end{array} \right. \] 를 가우스 소거법으로 구해보자. 먼저 첫째 식에 $-0.0001$을 곱하여 둘째 식에 더하면 \[ 0.9999y = 1.9997 \] 이므로 유효숫자가 $3$개가 되도록 반올림을 하여 \[ y = 2 \] 를 얻게 된다. 이 식에 후진대입법을 통해 얻을 수 있는 해인 $x=1$, $y=2$는 실제 해에 아주 좋은 근사값이 된다.$ $
$ $
위와 같이 같은 열에 존재하는 선행계수 중에서 절댓값이 가장 큰 선행계수를 포함한 행을 찾아 그 행을 위쪽으로 올린 후에 소거법을 실행하면 계산 과정에서의 오차를 줄일 수 있다. 이렇게 오차를 줄이는 방법을 부분적 추축 가우스 소거법(partial pivoting Gaussian elimination)이라 한다.
예제 1.3.5.
Q. 다음 첨가행렬을 기본행연산을 이용하여 행사다리꼴인 행렬로 변환하여라.
\[ [ A \,|\, \mathbf{b} ] = \left[ \, \begin{array}{rrr|r}
1 & 2 & 3 & 2 \\
2 & 3 & 3 & 1 \\
2 & 1 & 2 & 0
\end{array} \, \right] \]
A. 첫번째 열에서 절대값이 가장 큰 선행계수는 두번째 행의 $2$이므로 (세번째 행도 선행계수가 $2$이므로 아무거나 택해주어도 상관은 없다.) 우선 두번째 행을 첫번째 행과 교환한다.
\begin{align*}
\left[ \, \begin{array}{rrr|r}
1 & 2 & 3 & 2 \\
2 & 3 & 3 & 1 \\
2 & 1 & 2 & 0
\end{array} \, \right]
& \sim \left[ \, \begin{array}{rrr|r}
2 & 3 & 3 & 1 \\
1 & 2 & 3 & 2 \\
2 & 1 & 2 & 0
\end{array} \, \right] & R_2 \leftrightarrow R_1 \\[1ex]
& \sim \left[ \, \begin{array}{rrr|r}
2 & 3 & 3 & 1 \\
0 & 0.5 & 1.5 & 1.5 \\
0 & -2 & -1 & -1
\end{array} \, \right]
& \begin{aligned}
R_2 \leftarrow R_2 - 0.5R_1 \\
R_3 \leftarrow R_3 - R_1 \end{aligned} \\[1ex]
& \sim \left[ \, \begin{array}{rrr|r}
2 & 3 & 3 & 1 \\
0 & -2 & -1 & -1 \\
0 & 0.5 & 1.5 & 1.5
\end{array} \, \right] & R_3 \leftrightarrow R_2 \\[1ex]
& \sim \left[ \, \begin{array}{rrr|r}
1 & 2 & 3 & 2 \\
0 & -1 & -3 & -3 \\
0 & 0 & 1.25 & 1.25
\end{array} \, \right] & R_3 \leftarrow R_3 + 0.25R_2
\end{align*}
를 얻는다. 따라서 마지막 첨가행렬을 후진대입법을 통해 해를 구하면, $x=-1$, $y=0$, $z=1$을 얻는다.$ $
$ $