가우스 소거법 Gauss Elimination & 가우스-조르단 소거법 Gauss-Jordan Elimination
-
- *.78.140.87
- 2024.11.01 - 13:53 2015.03.26 - 13:15 2270 2
가우스 소거법(Gaussian Elimination)은 여러 개의 선형 방정식을 풀기 위해 사용되는 방법으로, 행렬을 간단한 형태로 변형하여 방정식의 해를 구하는 과정입니다.
이 방법은 주어진 방정식 시스템을 계수 행렬로 표현한 후, 행렬의 행들을 적절히 조작해 해를 구하는 방식입니다.
가우스 소거법의 단계
1. 방정식 시스템을 행렬로 변환
주어진 선형 방정식 시스템을 행렬로 표현합니다. 예를 들어, 아래와 같은 방정식 시스템을 생각해봅시다.
\[
\begin{aligned}
2x + 3y + z &= 1 \\
4x + y + 2z &= 2 \\
3x + 2y + 3z &= 3
\end{aligned}
\]
이 시스템을 계수 행렬로 변환하면 다음과 같이 표현할 수 있습니다:
\[
\begin{bmatrix}
2 & 3 & 1 & | & 1 \\
4 & 1 & 2 & | & 2 \\
3 & 2 & 3 & | & 3
\end{bmatrix}
\]
2. 전방 소거 단계 (앞으로 소거)
가우스 소거법의 첫 번째 단계는 계수 행렬을 위 삼각형(Upper Triangle) 형태로 만드는 것입니다. 즉, 행렬의 왼쪽 하단 부분을 0으로 만들어 나갑니다.
- 첫 번째 열을 기준으로 첫 번째 행을 사용하여 두 번째, 세 번째 행을 소거합니다. 첫 번째 행의 첫 번째 값을 이용해 두 번째와 세 번째 행에서 첫 번째 열의 값을 0으로 만듭니다.
\[
\text{두 번째 행} = \text{두 번째 행} - 2 \times \text{첫 번째 행}
\]
\[
\text{세 번째 행} = \text{세 번째 행} - \frac{3}{2} \times \text{첫 번째 행}
\]
이후, 두 번째 행을 기준으로 세 번째 행의 두 번째 열을 0으로 만듭니다. 이렇게 하면 행렬이 아래와 같은 형태가 됩니다:
\[
\begin{bmatrix}
2 & 3 & 1 & | & 1 \\
0 & -5 & 0 & | & 0 \\
0 & 0 & 2.5 & | & 1.5
\end{bmatrix}
\]
3. 후방 대입 단계 (뒤로 대입)
앞으로 소거를 완료한 후, 위 삼각형 형태의 행렬에서 해를 구하기 위해 역방향으로 대입해 나갑니다.
- 세 번째 행에서 \( z \)의 값을 구합니다:
\[
2.5z = 1.5 \implies z = \frac{1.5}{2.5} = 0.6
\]
- 두 번째 행에서 \( y \)의 값을 구합니다:
\[
-5y = 0 \implies y = 0
\]
- 첫 번째 행에서 \( x \)의 값을 구합니다:
\[
2x + 3y + z = 1 \implies 2x + 0 + 0.6 = 1 \implies 2x = 0.4 \implies x = 0.2
\]
따라서 해는 \( x = 0.2 \), \( y = 0 \), \( z = 0.6 \)입니다.
요약
가우스 소거법은 선형 방정식을 계수 행렬로 변환한 후, 전방 소거를 통해 행렬을 위 삼각형 형태로 만들고, 후방 대입을 통해 해를 구하는 방식입니다. 이 과정은 여러 변수를 포함한 방정식 시스템을 효율적으로 풀 수 있는 강력한 방법입니다.
참고
https://allcalc.org/14534 - 연립방정식의 풀이법 (System of linear equations)
https://allcalc.org/16404 - [TI-nspire] 연립방정식 풀기 - 역행렬 / RREF / linsolve
https://ko.wikipedia.org/wiki/%EA%B0%80%EC%9A%B0%EC%8A%A4_%EC%86%8C%EA%B1%B0%EB%B2%95 - 위키 가우스 소거법
댓글 2
-
-
-
-
-
가우스 소거법과 REF(Row Echelon Form) 및 RREF(Reduced Row Echelon Form) 사이의 관계
이들 간의 관계를 이해하려면, 각각의 개념을 간단히 정의하고 가우스 소거법이 행렬을 어떻게 변형하는지 살펴보는 것이 중요합니다.
1. 가우스 소거법 (Gaussian Elimination)
가우스 소거법은 선형 방정식 시스템을 풀기 위한 방법으로, 행렬을 조작하여 해를 구하는 과정입니다.이 방법은 기본적으로 전방 소거와 후방 대입을 통해 행렬을 더 단순한 형태로 변형합니다. 이 과정에서 행렬은 점진적으로 아래로 이동하면서 상삼각형 형태로 변형됩니다.
가우스 소거법은 REF 형태의 행렬을 만드는 과정과 밀접한 관계가 있습니다.
2. REF (Row Echelon Form, 행 사다리꼴 형태)
REF는 행렬을 특정 규칙을 따르는 형태로 변환한 상태로, 다음과 같은 조건을 만족합니다:- 각 행의 첫 번째 비영(0이 아닌) 원소는 그 행에서 가장 왼쪽에 위치하며, 이를 피벗(pivot)이라고 합니다.
- 피벗은 해당 행의 모든 왼쪽에 있는 원소보다 오른쪽에 위치합니다.
- 피벗을 포함하는 열의 모든 값은 피벗 아래에 있는 경우 0이어야 합니다.
- 행이 0으로만 이루어져 있다면, 그 행은 행렬의 맨 아래에 배치됩니다.즉, 행렬이 삼각형 형태로 나타나게 됩니다. 예를 들어, 다음은 REF의 예입니다:
\[
\begin{bmatrix}
1 & 2 & 3 & 4 \\
0 & 1 & 5 & 6 \\
0 & 0 & 1 & 7
\end{bmatrix}
\]가우스 소거법은 전방 소거 단계를 통해 행렬을 REF로 변환하는 과정입니다. 이 단계에서 각 행의 피벗이 왼쪽에서 오른쪽으로 이동하면서, 하단의 원소들은 0으로 만들어집니다.
3. RREF (Reduced Row Echelon Form, 가우스-조르단 소거법, 기약 행 사다리꼴 형태)
RREF는 REF보다 더 엄격한 형태로, 다음 조건을 만족해야 합니다:- REF의 모든 조건을 만족합니다.
- 각 피벗은 1이어야 합니다 (즉, 각 행의 첫 번째 비영 원소가 1이어야 함).
- 각 피벗을 포함하는 열의 나머지 모든 원소는 0이어야 합니다 (즉, 피벗 위아래의 원소가 모두 0이어야 함).예를 들어, 다음은 RREF의 예입니다:
\[
\begin{bmatrix}
1 & 0 & 0 & 2 \\
0 & 1 & 0 & 3 \\
0 & 0 & 1 & 4
\end{bmatrix}
\]RREF는 가우스-조르단 소거법(Gaussian-Jordan Elimination)을 통해 얻어집니다.
가우스 소거법에서 전방 소거를 통해 REF를 얻은 후, 후방 소거(back substitution) 단계를 추가하여 행렬의 피벗 위쪽 원소도 0으로 만들어 RREF로 변환합니다.
4. 가우스 소거법, REF, RREF의 관계
- 가우스 소거법은 행렬을 REF로 변환하는 과정입니다. 전방 소거를 통해 피벗이 있는 열에서 아래쪽 원소들을 0으로 만들어 행렬을 상삼각형 형태로 변형합니다.
- REF는 가우스 소거법을 통해 얻은 행렬의 형태로, 피벗 아래의 원소가 모두 0인 상삼각형 행렬입니다.- RREF는 REF에서 한 단계 더 나아가, 피벗 위쪽의 원소들도 모두 0으로 만들어 더 간단한 형태로 변환된 행렬입니다. 이를 위해 후방 소거가 추가로 이루어집니다.
- REF는 해를 구할 수 있는 상태로 만들지만, RREF는 행렬을 해석하기 쉽게 만드는 추가 단계를 포함하여, 해가 더 명확하게 드러나도록 합니다.
이처럼 REF는 가우스 소거법의 중간 결과이며, RREF는 가우스-조르단 소거법을 통해 얻는 최종 결과입니다. RREF로 변환하면 방정식의 해를 쉽게 찾을 수 있습니다.
-
미지수의 개수보다 방정식의 개수가 적을 경우,
이를 미정 방정식 또는 해가 무한한 방정식이라고 합니다. 이러한 시스템은 자유 변수를 포함하며, 일반적으로 무한히 많은 해를 가질 수 있습니다. 이를 가우스 소거법으로 처리하는 방식은 다음과 같습니다.
1. 방정식 시스템이 미지수보다 적을 때
미지수의 개수가 방정식의 개수보다 많은 경우, 방정식의 해가 정확히 하나로 결정되지 않고, 여러 해가 존재할 가능성이 있습니다. 이 경우, 시스템은 자유 변수를 포함하여 해를 무한히 가질 수 있습니다.
예를 들어, 두 개의 방정식과 세 개의 미지수를 포함하는 다음 시스템을 생각해봅시다:
\[
\begin{aligned}
x + y + z &= 2 \\
2x + 3y + z &= 5
\end{aligned}
\]
이를 계수 행렬로 표현하면 다음과 같습니다:
\[
\begin{bmatrix}
1 & 1 & 1 & | & 2 \\
2 & 3 & 1 & | & 5
\end{bmatrix}
\]
2. 가우스 소거법을 적용
전방 소거 과정을 거치면, 첫 번째 행을 기준으로 두 번째 행을 소거할 수 있습니다.
- 첫 번째 행을 기준으로 두 번째 행에서 첫 번째 변수를 제거합니다:
\[
\text{두 번째 행} = \text{두 번째 행} - 2 \times \text{첫 번째 행}
\]
이후 얻은 행렬은 다음과 같습니다:
\[
\begin{bmatrix}
1 & 1 & 1 & | & 2 \\
0 & 1 & -1 & | & 1
\end{bmatrix}
\]
이제 두 번째 행에서 \( y \)와 \( z \)의 관계를 알 수 있습니다. 후방 대입 과정을 통해 \( y \)와 \( z \)의 관계를 구한 후, 자유 변수를 설정하여 나머지 변수를 구할 수 있습니다.
3. 자유 변수 설정
자유 변수는 특정 값에 제한을 두지 않고, 임의의 값을 가질 수 있는 변수를 의미합니다. 예를 들어, 위 행렬에서 \( z \)를 자유 변수로 선택할 수 있습니다. 그러면 다음과 같은 관계를 얻습니다:
- 두 번째 행에서:
\[
y - z = 1 \implies y = z + 1
\]
- 첫 번째 행에서:
\[
x + y + z = 2 \implies x + (z + 1) + z = 2 \implies x = 1 - 2z
\]
따라서, \( z \)를 자유 변수로 두면 \( x \), \( y \), \( z \)의 값은 다음과 같이 표현됩니다:
\[
x = 1 - 2z, \quad y = z + 1, \quad z = z
\]
이 경우 해는 무한히 많은 해를 가지며, \( z \)에 대한 값이 달라짐에 따라 \( x \)와 \( y \)의 값도 변화합니다.
4. 요약
- 미지수의 개수보다 방정식의 개수가 적을 경우, 시스템은 무한히 많은 해를 가질 수 있습니다.
- 가우스 소거법을 통해 행렬을 간단한 형태로 만들고, 남은 변수에 대해 자유 변수를 설정하여 해를 구합니다.
- 자유 변수에 대해 임의의 값을 선택할 수 있으며, 그에 따라 나머지 변수의 값을 구하게 됩니다.
이러한 시스템은 보통 무한 해 또는 일반해를 가지며, 이를 통해 특정 조건 하에서 해를 구하거나 무한히 많은 해를 표현할 수 있습니다.