가우스 소거법

작성자

익명

작성일

2025.09.20

조회수

버전

가우스 소법

개요

가스 소거법(Gaussianination)은 선형 연립방정을 풀기 위한 가장 대표적인 알고리즘 중 하나로, 행렬을 기약 사다리꼴(reduced row echelon form) 또는사다리꼴row echelon form)로 변환하여 해를 구하는 방법이다. 이 방법은 독일의 수학자 카를 프리드리히 가우스의 이름을 따 명명되었으며, 선형대수학에서 행렬의 계수, 역행렬 존재 여부, 선형 독립성 판단 등 다양한 응용 분야에서 핵심적인 역할을 한다.

가우스 소거법은 기본 행 연산(elementary row operations)을 반복적으로 적용하여 주어진 연립방정식의 첨가 행렬(augmented matrix)을 단순화하는 과정을 통해 해를 도출한다. 이 방법은 계산이 체계적이며, 컴퓨터 알고리즘으로도 쉽게 구현 가능하여 수치해석 및 공학 계산에서 널리 사용된다.

기본 개념

선형 연립방정식과 행렬 표현

선형 연립방정식은 다음과 같은 형태로 표현할 수 있다:

$$ \begin{cases} 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 \\ \vdots \\ a_{m1}x_1 + a_{m2}x_2 + \cdots + a_{mn}x_n = b_m \\ \end{cases} $$

이를 행렬 형태로 나타내면:

$$ A\mathbf{x} = \mathbf{b} $$

여기서 $ A $는 계수 행렬, $ \mathbf{x} $는 미지수 벡터, $ \mathbf{b} $는 상수항 벡터이다. 가우스 소거법은 이 방정식의 첨가 행렬 $[A|\mathbf{b}]$를 다뤄서 해를 구한다.

기본 행 연산 (Elementary Row Operations)

가우스 소거법은 다음 세 가지 기본 행 연산을 사용한다:

두 행의 위치를 바꾼다 (Row swapping)
한 행에 0이 아닌 상수를 곱한다 (Scalar multiplication)
한 행에 다른 행의 스칼라 배를 더한다 (Row addition)

이 연산들은 원래 방정식의 해를 변화시키지 않으며, 행렬의 행 동치(row equivalence)를 유지한다.

알고리즘 절차

가우스 소거법은 일반적으로 두 단계로 나뉜다:

1단계: 전진 소거 (Forward Elimination)

목표: 행렬을 사다리꼴 형태(row echelon form)로 변환

주어진 행렬의 가장 왼쪽에 있는 0이 아닌 원소(선행 성분, pivot)를 찾는다.
이 성분을 포함한 행을 적절히 교환하여 위로 올린다.
아래 행들을 해당 pivot을 이용해 소거하여, pivot 아래의 모든 원소를 0으로 만든다.
다음 열로 이동하여 동일한 과정을 반복한다.

예시: $$ \begin{bmatrix} 1 & 2 & 3 & | & 6 \\ 2 & 5 & 7 & | & 15 \\ 1 & 1 & 1 & | & 3 \\ \end{bmatrix} \Rightarrow \begin{bmatrix} 1 & 2 & 3 & | & 6 \\ 0 & 1 & 1 & | & 3 \\ 0 & -1 & -2 & | & -3 \\ \end{bmatrix} \Rightarrow \begin{bmatrix} 1 & 2 & 3 & | & 6 \\ 0 & 1 & 1 & | & 3 \\ 0 & 0 & -1 & | & 0 \\ \end{bmatrix} $$

2단계: 후진입 또는 기약 사다리꼴 변환

가우스-조르당 소거법(Gauss-Jordan Elimination)을 사용하면, 전진 소거 후 기약 사다리꼴 형태로 완전히 변환한다.
각 pivot이 1이 되도록 정규화하고, pivot 위의 원소도 모두 0으로 만든다.
최종적으로 각 변수에 대한 해가 명시적으로 드러난다.

예시 (기약 사다리꼴): $$ \begin{bmatrix} 1 & 0 & 0 & | & x_1 \\ 0 & 1 & 0 & | & x_2 \\ 0 & 0 & 1 & | &_3 \\ \end{bmatrix} \Rightarrow \mathbf{x} = (x_1, x_2, x_3) $$

해 존재성과 유일성

가우스 소거법을 통해 다음과 같은 정보를 알 수 있다:

첨가 행렬의 형태	해의 특성
모든 변수에 pivot 존재	유일한 해 존재
pivot 없는 변수 존재 (자유 변수)	무수히 많은 해 (일반해)
모순된 행 발생 (예: $0 = 1$)	해 없음 (불일치)

이를 통해 연립방정식의 일관성(consistency)과 자유도(degrees of freedom)를 판단할 수 있다.

계산 복잡도와 수치적 안정성

시간 복잡도: $n \times n$ 행렬에 대해 약 $O(n^3)$의 연산이 필요.
수치적 안정성: 피벗이 0이거나 매우 작은 경우, 계산 오차가 커질 수 있다.
이를 해결하기 위해 부분 피벗(partial pivoting) 또는 완전 피벗(complete pivoting)을 사용.
부분 피벗: 현재 열에서 절댓값이 가장 큰 원소를 pivot으로 선택하여 행을 교환.

응용 분야

선형 방정식 해법: 공학, 물리, 경제 모델링 등에서 널리 사용.
행렬의 역행렬 계산: 단위행렬과 함께 확장한 후 소거.
행렬의 계수(rank) 결정: pivot의 개수로 계산.
행렬식 계산: 소거 후 대각성분의 곱 (부호 고려).
선형 독립성 판별: 벡터 집합의 행렬을 소거하여 rank 분석.

예제

다음 연립방정식을 가우스 소거법으로 풀어보자:

$$ \begin{cases} x + y + z = 6 \\ 2x + 3y + z = 13 \\ 3x + y + 2z = 11 \\ \end{cases} $$

첨가 행렬: $$ \left[\begin{array}{ccc|c} 1 & 1 & 1 & 6 \\ 2 & 3 & 1 & 13 \\ 3 & 1 & 2 & 11 \\ \end{array}\right] $$

1단계: 1행을 이용해 2행, 3행 소거
→ $R_2 = R_2 - 2R_1$, $R_3 = R_3 - 3R_1$

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

2단계: 2행을 이용해 3행 소거
→ $R_3 = R_3 + 2R_2$

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

3단계: 후진 대입
→ $z = \frac{5}{3}$, $y = 1 + z = \frac{8}{3}$, $x = 6 - y - z = 6 - \frac{8}{3} - \frac{5}{3} = \frac{5}{3}$

해: $x = \frac{5}{3}, y = \frac{8}{3}, z = \frac{5}{3}$

관련 문서 및 참고 자료

행렬의 계수
기약 사다리꼴
가우스-조르당 소거법
Gilbert Strang, Introduction to Linear Algebra, 5th Edition (2016)

가우스 소거법은 선형대수학의 기초이자 핵심 도구로, 이론적 이해와 실용적 응용 모두에서 중요한 위치를 차지한다.

📝 마크다운 원본

이 문서의 마크다운 원본 내용입니다.

가우스 소법

## 개요

**가스 소거법**(Gaussianination)은 선형 연립방정을 풀기 위한 가장 대표적인 알고리즘 중 하나로, 행렬을 **기약 사다리꼴**(reduced row echelon form) 또는사다리꼴row echelon form)로 변환하여 해를 구하는 방법이다. 이 방법은 독일의 수학자 카를 프리드리히 가우스의 이름을 따 명명되었으며, 선형대수학에서 행렬의 계수, 역행렬 존재 여부, 선형 독립성 판단 등 다양한 응용 분야에서 핵심적인 역할을 한다.

가우스 소거법은 기본 행 연산(elementary row operations)을 반복적으로 적용하여 주어진 연립방정식의 첨가 행렬(augmented matrix)을 단순화하는 과정을 통해 해를 도출한다. 이 방법은 계산이 체계적이며, 컴퓨터 알고리즘으로도 쉽게 구현 가능하여 수치해석 및 공학 계산에서 널리 사용된다.

---

## 기본 개념

### 선형 연립방정식과 행렬 표현

선형 연립방정식은 다음과 같은 형태로 표현할 수 있다:

$$
\begin{cases}
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 \\
\vdots \\
a_{m1}x_1 + a_{m2}x_2 + \cdots + a_{mn}x_n = b_m \\
\end{cases}
$$

이를 행렬 형태로 나타내면:

$$
A\mathbf{x} = \mathbf{b}
$$

여기서 $ A $는 계수 행렬, $ \mathbf{x} $는 미지수 벡터, $ \mathbf{b} $는 상수항 벡터이다. 가우스 소거법은 이 방정식의 **첨가 행렬** $[A|\mathbf{b}]$를 다뤄서 해를 구한다.

---

## 기본 행 연산 (Elementary Row Operations)

가우스 소거법은 다음 세 가지 기본 행 연산을 사용한다:

1. **두 행의 위치를 바꾼다** (Row swapping)
2. **한 행에 0이 아닌 상수를 곱한다** (Scalar multiplication)
3. **한 행에 다른 행의 스칼라 배를 더한다** (Row addition)

이 연산들은 원래 방정식의 해를 변화시키지 않으며, 행렬의 **행 동치**(row equivalence)를 유지한다.

---

## 알고리즘 절차

가우스 소거법은 일반적으로 두 단계로 나뉜다:

### 1단계: 전진 소거 (Forward Elimination)

목표: 행렬을 **사다리꼴 형태**(row echelon form)로 변환

- 주어진 행렬의 가장 왼쪽에 있는 0이 아닌 원소(선행 성분, pivot)를 찾는다.
- 이 성분을 포함한 행을 적절히 교환하여 위로 올린다.
- 아래 행들을 해당 pivot을 이용해 소거하여, pivot 아래의 모든 원소를 0으로 만든다.
- 다음 열로 이동하여 동일한 과정을 반복한다.

예시:
$$
\begin{bmatrix}
1 & 2 & 3 & | & 6 \\
2 & 5 & 7 & | & 15 \\
1 & 1 & 1 & | & 3 \\
\end{bmatrix}
\Rightarrow
\begin{bmatrix}
1 & 2 & 3 & | & 6 \\
0 & 1 & 1 & | & 3 \\
0 & -1 & -2 & | & -3 \\
\end{bmatrix}
\Rightarrow
\begin{bmatrix}
1 & 2 & 3 & | & 6 \\
0 & 1 & 1 & | & 3 \\
0 & 0 & -1 & | & 0 \\
\end{bmatrix}
$$

### 2단계: 후진입 또는 기약 사다리꼴 변환

- **가우스-조르당 소거법**(Gauss-Jordan Elimination)을 사용하면, 전진 소거 후 **기약 사다리꼴 형태**로 완전히 변환한다.
- 각 pivot이 1이 되도록 정규화하고, pivot 위의 원소도 모두 0으로 만든다.
- 최종적으로 각 변수에 대한 해가 명시적으로 드러난다.

예시 (기약 사다리꼴):
$$
\begin{bmatrix}
1 & 0 & 0 & | & x_1 \\
0 & 1 & 0 & | & x_2 \\
0 & 0 & 1 & | &_3 \\
\end{bmatrix}
\Rightarrow \mathbf{x} = (x_1, x_2, x_3)
$$

---

## 해 존재성과 유일성

가우스 소거법을 통해 다음과 같은 정보를 알 수 있다:

| 첨가 행렬의 형태 | 해의 특성 |
|------------------|----------|
| 모든 변수에 pivot 존재 | 유일한 해 존재 |
| pivot 없는 변수 존재 (자유 변수) | 무수히 많은 해 (일반해) |
| 모순된 행 발생 (예: $0 = 1$) | 해 없음 (불일치) |

이를 통해 연립방정식의 **일관성**(consistency)과 **자유도**(degrees of freedom)를 판단할 수 있다.

---

## 계산 복잡도와 수치적 안정성

- **시간 복잡도**: $n \times n$ 행렬에 대해 약 $O(n^3)$의 연산이 필요.
- **수치적 안정성**: 피벗이 0이거나 매우 작은 경우, 계산 오차가 커질 수 있다.
  - 이를 해결하기 위해 **부분 피벗**(partial pivoting) 또는 **완전 피벗**(complete pivoting)을 사용.
  - 부분 피벗: 현재 열에서 절댓값이 가장 큰 원소를 pivot으로 선택하여 행을 교환.

---

## 응용 분야

- **선형 방정식 해법**: 공학, 물리, 경제 모델링 등에서 널리 사용.
- **행렬의 역행렬 계산**: 단위행렬과 함께 확장한 후 소거.
- **행렬의 계수**(rank) 결정: pivot의 개수로 계산.
- **행렬식 계산**: 소거 후 대각성분의 곱 (부호 고려).
- **선형 독립성 판별**: 벡터 집합의 행렬을 소거하여 rank 분석.

---

## 예제

다음 연립방정식을 가우스 소거법으로 풀어보자:

$$
\begin{cases}
x + y + z = 6 \\
2x + 3y + z = 13 \\
3x + y + 2z = 11 \\
\end{cases}
$$

첨가 행렬:
$$
\left[\begin{array}{ccc|c}
1 & 1 & 1 & 6 \\
2 & 3 & 1 & 13 \\
3 & 1 & 2 & 11 \\
\end{array}\right]
$$

1단계: 1행을 이용해 2행, 3행 소거  
→ $R_2 = R_2 - 2R_1$, $R_3 = R_3 - 3R_1$

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

2단계: 2행을 이용해 3행 소거  
→ $R_3 = R_3 + 2R_2$

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

3단계: 후진 대입  
→ $z = \frac{5}{3}$, $y = 1 + z = \frac{8}{3}$, $x = 6 - y - z = 6 - \frac{8}{3} - \frac{5}{3} = \frac{5}{3}$

해: $x = \frac{5}{3}, y = \frac{8}{3}, z = \frac{5}{3}$

---

## 관련 문서 및 참고 자료

- [행렬의 계수](https://ko.wikipedia.org/wiki/행렬의_계수)
- [기약 사다리꼴](https://ko.wikipedia.org/wiki/기약_사다리꼴)
- [가우스-조르당 소거법](https://ko.wikipedia.org/wiki/가우스-조르당_소거법)
- Gilbert Strang, *Introduction to Linear Algebra*, 5th Edition (2016)

---

가우스 소거법은 선형대수학의 기초이자 핵심 도구로, 이론적 이해와 실용적 응용 모두에서 중요한 위치를 차지한다.

AI 생성 콘텐츠 안내

이 문서는 AI 모델(qwen-3-235b-a22b-instruct-2507)에 의해 생성된 콘텐츠입니다.

주의사항: AI가 생성한 내용은 부정확하거나 편향된 정보를 포함할 수 있습니다. 중요한 결정을 내리기 전에 반드시 신뢰할 수 있는 출처를 통해 정보를 확인하시기 바랍니다.

위키너와나