[Linear Algebra] 선형대수학(4강) - 가우스 소거법을 활용해 연립방정식의 해 구하기

• 수식이 제대로 보이지 않는다면, 새로고침(F5)을 해주시기 바랍니다.

이번 포스팅에서는 행렬을 이용하여 연립 선형 방정식을 푸는 방법을 알아보겠습니다. 어렵지 않으니 글을 따라 직접 계산해보시면 쉽게 이해하실 수 있습니다!

Gaussian Elimination

연립방정식 푸는 방법은 이미 다 알고 계실 것이라 생각합니다. 가감법 또는 대입법을 활용하여, 미지수를 없애가며 결국은 모든 변수에 대한 해를 찾게 됩니다.
이 과정을 행렬로도 표현할 수 있는데요, 이를 체계적으로 정리한 것이 바로 가우스 소거법(Gaussian Elimination)입니다.

가우스 소거법은 연립선형방정식을 행렬로 나타내고, 행 연산(row operation)을 통해 해를 구하는 방법입니다.

elementary row operation

가우스 소거법을 사용할 때는 다음 세 가지의 기본 행 연산만 사용 가능합니다. elementary row operation이라는 용어 및 이 세 가지의 연산 방법은 꼭 기억하시고, 아래 예제에서 어떻게 이를 활용하는지 참고하시길 바랍니다.

1. 두 행을 맞바꾼다
2. 한 행에 0이 아닌 상수를 곱한다
3. 한 행에 다른 행의 상수배를 더한다

Example

연립선형방정식을 풀이하는 예를 한 번 보겠습니다. 다음 연립방정식을 생각해 봅시다.

\[\begin{cases} x + 2y + z = 6 \\ 2x + 3y + 3z = 14 \\ x + y + z = 8 \end{cases}\]

위 연립방정식을 다음과 같은 확대 행렬(augmented matrix)로 나타낼 수 있습니다. 위 연립방정식의 계수만 따와서 행렬에 넣은 것을 보실 수 있습니다.

\[\left[ \begin{array}{ccc|c} 1 & 2 & 1 & 6 \\ 2 & 3 & 3 & 14 \\ 1 & 1 & 1 & 8 \end{array} \right]\]

이제 이 행렬을 가우스 소거법을 사용해 계단형(row echelon form)으로 바꿔야 합니다. 그렇다면 row echelon form은 무엇일까요?

Row Echelon Form

계단형 행렬(row echelon form)이란, 다음 조건을 만족하는 행렬을 말합니다.

1. 각 행의 첫 번째 0이 아닌 원소(leading entry)는, 그 위 행의 leading entry보다 오른쪽에 있어야 한다.
2. leading entry 아래에는 모두 0이 있어야 한다.
3. 모든 0으로만 이루어진 행은 행렬의 맨 아래에 위치한다.

---

예를 들어, 아래 행렬은 row echelon form입니다.

\[\begin{bmatrix} 1 & 2 & -1 & 3 \\ 0 & 1 & 5 & -2 \\ 0 & 0 & 4 & 7 \end{bmatrix}\]

• 첫 번째 행의 leading entry는 $1$ (열 1)
• 두 번째 행의 leading entry는 $1$ (열 2)
• 세 번째 행의 leading entry는 $4$ (열 3)

각 leading entry는 행이 아래로 내려갈수록 오른쪽으로 이동하며, 아래에 있는 항들은 모두 $0$이므로 조건을 만족합니다.

이러한 모양을 만들면 가우스 소거법을 통해 역방향 대입(back substitution)으로 해를 구할 수 있습니다.
row echelon form을 알아보았으니, 처음 문제의 행렬을 다시 보겠습니다.

\[\left[ \begin{array}{ccc|c} 1 & 2 & 1 & 6 \\ 2 & 3 & 3 & 14 \\ 1 & 1 & 1 & 8 \end{array} \right]\]

이제 이 행렬을 row echelon form으로 만들어보겠습니다.

1단계: 첫 번째 피벗을 기준으로 아래 항 제거
(첫 번째 열의 아래쪽 항을 0으로 만들기)

• $R_2 \leftarrow R_2 - 2R_1$
• $R_3 \leftarrow R_3 - R_1$

\[\left[ \begin{array}{ccc|c} 1 & 2 & 1 & 6 \\ 0 & -1 & 1 & 2 \\ 0 & -1 & 0 & 2 \end{array} \right]\]

2단계: 두 번째 피벗을 기준으로 아래 항 제거

• $R_3 \leftarrow R_3 - R_2$

\[\left[ \begin{array}{ccc|c} 1 & 2 & 1 & 6 \\ 0 & -1 & 1 & 2 \\ 0 & 0 & -1 & 0 \end{array} \right]\]

이제 row echelon form이 만들어졌습니다. 마지막으로 Back Substitution을 하여 해를 구해보겠습니다.

• $-z = 0 \Rightarrow z = 0$
• $-y + z = 2 \Rightarrow y = -2$
• $x + 2y + z = 6 \Rightarrow x + 2(-2) + 0 = 6 \Rightarrow x = 10$

따라서 최종 해는 다음과 같습니다.

\[x = 10,\quad y = -2,\quad z = 0\]

위의 문제는 연립방정식을 풀었을 때 해가 하나로 결정됐습니다. 그러나 연립방정식을 풀 때 해가 하나로 결정되는 경우도 있지만 해가 없거나 무수히 많은 경우도 있다는 것을 알고 계실겁니다. 두 경우도 모두 살펴보겠습니다.

Case: No Solution

연립방정식을 가우스 소거법을 활용해 풀었을 때, 해가 없는 경우엔 어떻게 나오는 지 살펴보겠습니다.
해가 없는 경우는 모순된 행(row)이 등장할 때 발생합니다. 예시 행렬을 한 번 살펴볼까요?

Example

다음 연립방정식을 생각해 봅시다.

\[\begin{cases} x + y + z = 1 \\ 2x + 2y + 2z = 2 \\ x + y + z = 3 \end{cases}\]

이 연립방정식을 augmented matrix로 나타내면 다음과 같습니다.

\[\left[ \begin{array}{ccc|c} 1 & 1 & 1 & 1 \\ 2 & 2 & 2 & 2 \\ 1 & 1 & 1 & 3 \end{array} \right]\]

이제 가우스 소거법을 수행하겠습니다.

• $R_2 \leftarrow R_2 - 2R_1$
• $R_3 \leftarrow R_3 - R_1$

\[\left[ \begin{array}{ccc|c} 1 & 1 & 1 & 1 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 2 \end{array} \right]\]

이 때 세 번째 행을 보면 다음과 같은 방정식을 의미합니다:

\[0x + 0y + 0z = 2 \Rightarrow 0 = 2\]

모순이 발생했죠? 따라서 이 연립방정식의 해는 존재하지 않습니다. (No Solution)

Case: Infinite Solutions

가우스 소거법을 수행했을 때, 방정식이 어떤 해에도 모순되지 않지만 변수를 정하는 조건이 충분하지 않을 때, 해가 무수히 많아지게 됩니다. 이 경우에는 하나 이상의 자유 변수(free variable)가 등장하며, 그에 따라 해가 무한히 많아지게 됩니다. free variable에 대한 설명은 예시에서 함께 드리도록 하겠습니다.

Example

다음 연립방정식을 살펴봅시다.

\[\begin{cases} x + y + z = 2 \\ 2x + 2y + 2z = 4 \\ \end{cases}\]

이를 augmented matrix로 나타내면 다음과 같습니다.

\[\left[ \begin{array}{ccc|c} 1 & 1 & 1 & 2 \\ 2 & 2 & 2 & 4 \end{array} \right]\]

이제 가우스 소거법을 수행해보겠습니다.

• $R_2 \leftarrow R_2 - 2R_1$

\[\left[ \begin{array}{ccc|c} 1 & 1 & 1 & 2 \\ 0 & 0 & 0 & 0 \end{array} \right]\]

두 번째 행은 항상 성립하는 항등식 $0 = 0$이므로 무시해도 됩니다.
결국 다음 방정식 하나만 남습니다:

\[x + y + z = 2\]

free variable

변수는 3개($x$, $y$, $z$)인데 식은 1개뿐입니다. 따라서 2개의 변수를 자유롭게 정할 수 있습니다. 예를 들어 다음처럼 표현할 수 있습니다.

• $y = s$, $z = t$라고 두면,
• $x = 2 - y - z = 2 - s - t$

즉, 모든 해는 다음과 같은 형태로 표현됩니다.

\[\begin{bmatrix} x \\ y \\ z \end{bmatrix} = \begin{bmatrix} 2 - s - t \\ s \\ t \end{bmatrix}, \quad s, t \in \mathbb{R}\]

Consistency

가우스 소거법을 통해 연립선형방정식을 분석할 때, 해가 존재하는지 여부에 따라 그 시스템이 일관적인지(consistent), 아닌지(inconsistent) 판단할 수 있습니다. system이 일관적이다라는 말은 그 연립방정식이 적어도 하나의 해를 갖는다는 의미입니다.
아래 표를 참고하여 용어의 정의를 살펴보세요.

해의 개수	일관성 (Consistency)	설명
유일한 해 1개	Consistent	해가 하나 존재함
무수히 많은 해	Consistent	해가 무한히 존재함
해 없음	Inconsistent	모순이 발생하여 해가 존재하지 않음

맨 처음 살펴본 예시는 해가 오직 하나로 결정되었기 때문에 consistent한 경우입니다. 두 번째 예시에서는 해가 없었죠? Inconsistent한 경우입니다. 마지막으로 살펴본 예시에서는 해가 무수히 많았습니다. 이는 Consistent한 경우입니다.
추가로, 가우스 소거법을 통해 consistency를 빠르게 판단할 수 있습니다. Gaussian Elimination을 모두 한 후에, 아래의 행에서부터 살펴보시면 바로 판단하실 수 있습니다. 예를 들어, augmented matrix에서 좌변과 우변이 모두 $0$이면 항등식이 생긴 것이겠죠? 반면 좌변은 모두 $0$이지만, 우변은 $0$이 아닌 숫자라면 모순이 발생한 것입니다.
이런 방식으로 consistency를 쉽게 판단하실 수 있습니다. 또한 맨 아래 행뿐만 아니라 여러 개의 행에 항등식이 생길 수도 있습니다. 여러 case가 존재할 수 있는데요, 연습 문제를 통해 직접 계산하며 이를 생각해보시면 좋을 것 같습니다.

Conclusion

지금까지 Gaussian Elimination을 활용하여 연립선형방정식을 풀어서 해를 구하는 방법을 알아보았습니다. 또한 consistent와 inconsistent에 대해서도 알아보았습니다. 이번 파트는 크게 어려운 내용이기 보다는 계산이 주된 내용이기 때문에, 연습 문제를 직접 계산해보시면서 gaussian elimination을 하는 방법을 체득하시는 관점으로 공부하시면 좋을 것 같습니다. 이번 강의는 여기서 마치겠습니다.

---

Practice

Q1. 다음 연립방정식을 Gaussian Elimination을 사용하여 푸시오.

\[\begin{cases} x + y + z = 6 \\ 2x + 3y + z = 14 \\ x + 2y + 3z = 14 \end{cases}\]

Q2. 다음 연립방정식이 consistent한지, inconsistent한지 판단하시오.

\[\begin{cases} x + 2y + 3z = 4 \\ 5x + 6y + 7z = 8 \\ 9x + 10y + 11z = 12 \end{cases}\]

Q3. 아래 설명을 참고하여 $\mathbf{x}$를 구하시오.

연립선형방정식은 다음과 같이 행렬의 곱으로 표현할 수 있다.

\[A \mathbf{x} = \mathbf{b}\]

다음과 같은 행렬 $A$와 벡터 $\mathbf{b}$가 주어졌을 때, 가우스 소거법을 사용하여 $\mathbf{x}$를 구하시오.

\[A = \begin{bmatrix} 1 & 2 & 3 \\ 4 & 5 & 6 \\ 7 & 8 & 10 \end{bmatrix}, \quad \mathbf{b} = \begin{bmatrix} 6 \\ 15 \\ 25 \end{bmatrix}\]

Answer

추후에 업로드 예정