가우스 소거법: 두 판 사이의 차이
내용 삭제됨 내용 추가됨
Osteologia (토론 | 기여) 편집 요약 없음 |
Osteologia (토론 | 기여) 편집 요약 없음 |
||
2번째 줄:
[[선형대수학]]에서, '''가우스 소거법'''(Gauß消去法, {{llang|en|Gaussian elimination}}, 약자 GE)은 [[일차연립방정식]]을 풀기 위한 [[알고리즘]]이다. 한 방정식을 첫 변수에 대해 푼 다음, 이 식을 나머지 방정식에 넣어 연립 선형방정식을 푸는 방식이다. 위의 결과는 방정식과 변수의 개수가 원래 연립방정식보다 하나 적은 새로운 연립방정식이 된다. 같은 과정을 2번째 변수에 적용하고, 방정식이 하나만 남을 때까지 다른 변수들에 이 과정을 되풀이한다. 하나 남은 방정식에서는 마지막 변수만 미지변수이다. 이 방정식의 해로 바로 앞에서 얻은 미지수가 2개인 방정식의 해를 구한다. 이 과정은 모든 미지수의 값을 구할 때까지 계속된다.
== 정의 ==
어떤 [[체 (수학)|체]] <math>K</math>에 대하여, 다음과 같은 꼴의, ''n''개의 방정식으로 구성된 [[일차연립방정식]]이 주어졌다고 하자.
:<math>M\begin{pmatrix}x_1\\x_2\\\vdots\\x_n\end{pmatrix}=0</math>
여기서
:<math>M=\begin{pmatrix}
M_{11}&M_{12}&\cdots&M_{1n}\\
M_{21}&M_{22}&\cdots&M_{2n}\\
\vdots&\vdots&\ddots&\vdots\\
M_{m1}&M_{m2}&\cdots&M_{mn}
\end{pmatrix}</math>
은 주어진 <math>m\times n</math> 행렬이고, <math>x_1,\dots,x_n</math>은 <math>n</math>개의 미지수이다. 보통, 유일한 해를 가진 일차 연립 방정식의 경우 <math>m=n</math>이며, 따라서 <math>M</math>은 정사각행렬을 이룬다. 그러나 해가 유일하지 못한 경우나, 해가 없는 경우, 방정식이 중복되는 경우 등에서는 <math>m\ne n</math>일 수 있다.
=== 기본행연산 ===
이 경우, 이 연립 방정식에 다음과 같은 세 가지 연산을 가할 수 있다. 이들을 '''기본행연산'''({{llang|en|elementary row operation}})이라고 한다.
* (행의 치환) <math>M</math>의 <math>i</math>번째 행과 <math>j</math>번째 행을 서로 바꾼다.
::<math>\begin{pmatrix}
M_{11}&M_{12}&\cdots&M_{1n}\\
\vdots&\vdots&&\vdots\\
M_{i1}&M_{i2}&\cdots&M_{in}\\
\vdots&\vdots&&\vdots\\
M_{j1}&M_{j2}&\cdots&M_{jn}\\
\vdots&\vdots&&\vdots\\
M_{m1}&M_{m2}&\cdots&M_{mn}
\end{pmatrix}\begin{pmatrix}x_1\\\vdots\\x_i\\\vdots\\x_j\\\vdots\\x_n\end{pmatrix}=0
\implies\begin{pmatrix}
M_{11}&M_{12}&\cdots&M_{1n}\\
\vdots&\vdots&&\vdots\\
M_{j1}&M_{j2}&\cdots&M_{jn}\\
\vdots&\vdots&&\vdots\\
M_{i1}&M_{i2}&\cdots&M_{in}\\
\vdots&\vdots&&\vdots\\
M_{m1}&M_{m2}&\cdots&M_{mn}
\end{pmatrix}\begin{pmatrix}x_1\\\vdots\\x_i\\\vdots\\x_j\\\vdots\\x_n\end{pmatrix}=0
</math>
* (행의 상수곱) <math>i</math>번째 행을 0이 아닌 상수 <math>a\ne0</math>으로 곱한다.
::<math>\begin{pmatrix}
M_{11}&M_{12}&\cdots&M_{1n}\\
\vdots&\vdots&&\vdots\\
M_{i1}&M_{i2}&\cdots&M_{in}\\
\vdots&\vdots&&\vdots\\
M_{m1}&M_{m2}&\cdots&M_{mn}
\end{pmatrix}\begin{pmatrix}x_1\\\vdots\\x_i\\\vdots\\x_n\end{pmatrix}=0
\implies\begin{pmatrix}
M_{11}&M_{12}&\cdots&M_{1n}\\
\vdots&\vdots&&\vdots\\
aM_{i1}&aM_{i2}&\cdots&aM_{in}\\
\vdots&\vdots&&\vdots\\
M_{m1}&M_{m2}&\cdots&M_{mn}
\end{pmatrix}\begin{pmatrix}x_1\\\vdots\\x_i\\\vdots\\x_n\end{pmatrix}=0
</math>
* (행의 합) <math>i</math>번째 행을 <math>j</math>번째 행에 더한다.
::<math>\begin{pmatrix}
M_{11}&M_{12}&\cdots&M_{1n}\\
\vdots&\vdots&&\vdots\\
M_{i1}&M_{i2}&\cdots&M_{in}\\
\vdots&\vdots&&\vdots\\
M_{j1}&M_{j2}&\cdots&M_{jn}\\
\vdots&\vdots&&\vdots\\
M_{m1}&M_{m2}&\cdots&M_{mn}
\end{pmatrix}\begin{pmatrix}x_1\\\vdots\\x_i\\\vdots\\x_j\\\vdots\\x_n\end{pmatrix}=0
\implies\begin{pmatrix}
M_{11}&M_{12}&\cdots&M_{1n}\\
\vdots&\vdots&&\vdots\\
M_{i1}&M_{i2}&\cdots&M_{in}\\
\vdots&\vdots&&\vdots\\
M_{i1}+M_{j1}&M_{i2}+M_{j2}&\cdots&M_{in}+M_{jn}\\
\vdots&\vdots&&\vdots\\
M_{m1}&M_{m2}&\cdots&M_{mn}
\end{pmatrix}\begin{pmatrix}x_1\\\vdots\\x_i\\\vdots\\x_j\\\vdots\\x_n\end{pmatrix}=0
</math>
=== 사다리꼴 행렬 ===
가우스 소거법의 기본적인 목표는 행렬을 기본행연산을 적용하여 '''사다리꼴 행렬'''({{llang|en|échelon matrix}})로 만드는 것이다. <math>m\times n</math> 행렬 <math>M</math>이 다음 조건을 만족시키면, <math>M</math>을 '''사다리꼴 행렬'''이라고 한다.
* 만약 <math>M_{ij}=0</math>이라면, 모든 <math>i\le i'</math>에 대하여 <math>M_{i'j}=0</math>이다.
* <math>j_0(i)=\min\{j\colon M_{ij}\ne0\}</math>이라고 하면, <math>M_{i,j_0(i)}</math>를 <math>i</math>번째 행의 '''선행계수'''({{llang|en|leading coefficient}})라고 한다. 만약 <math>i<i'</math>라면, <math>j_0(i)<j_0(i')</math>이다.
<math>m\times n</math> 행렬 <math>M</math>이 다음 조건을 만족시키면, <math>M</math>을 '''기약행 사다리꼴 행렬'''({{llang|en|reduced-row échelon matrix}})이라고 한다.
* <math>M</math>은 사다리꼴이다.
* <math>M_{i,j_0(i)}</math>가 <math>i</math>번째 행의 선행계수라고 하자. 그렇다면 <math>M_{i,j_0(i)}=1</math>이며, 모든 <math>j\ne j_0(i)</math>에 대하여 <math>M_{ij}=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>
== 예 ==
=== 전진 소거법(Forward elimination) ===
* <math>
| |||