가우스 소거법: 두 판 사이의 차이
내용 삭제됨 내용 추가됨
편집 요약 없음 |
|||
2번째 줄:
== 정의 ==
[[체 (수학)|체]] <math>K</math>에 대하여, <math>n
:<math>Mx=0</math>
이 주어졌다고 하자. 여기서
:<math>M=\begin{pmatrix}
M_{11}&M_{12}&\cdots&M_{
\vdots&\vdots&\ddots&\vdots\\M_{m1}&M_{m2}&\cdots&M_{
은 주어진 <math>m\times
:<math>x=\begin{pmatrix}x_1\\x_2\\\vdots\\
은 <math>n
:<math>M_{11}x_1+M_{12}x_2+\cdots+M_{1,n-1}
:<math>M_{21}x_1+M_{22}x_2+\cdots+M_{2,n-1}
::::::::<math>\vdots</math>
:<math>M_{m1}x_1+M_{m2}x_2+\cdots+M_{m,n-1}
=== 기본행연산 ===
{{본문|기본 행렬}}
이 경우, 이 연립방정식에 다음과 같은 세 가지 연산을 가할 수 있다. 이들을 '''기본행연산'''(基本行演算, {{llang|en|elementary row operation}})이라고 한다.
* (행의 치환) <math>M</math>의 <math>i</math>번째 행과 <math>j</math>번째 행을 서로 바꾼다.
::<math>\begin{pmatrix}
M_{11}&M_{12}&\cdots&M_{
M_{i1}&M_{i2}&\cdots&M_{
M_{j1}&M_{j2}&\cdots&M_{
M_{m1}&M_{m2}&\cdots&M_{
\implies\begin{pmatrix}
M_{11}&M_{12}&\cdots&M_{
M_{j1}&M_{j2}&\cdots&M_{
M_{i1}&M_{i2}&\cdots&M_{
M_{m1}&M_{m2}&\cdots&M_{
* (행의 상수곱) <math>i</math>번째 행을 0이 아닌 임의의 상수 <math>a\in K\setminus\{0\}</math>으로 곱한다.
::<math>\begin{pmatrix}
M_{11}&M_{12}&\cdots&M_{
M_{i1}&M_{i2}&\cdots&M_{
M_{m1}&M_{m2}&\cdots&M_{
\implies\begin{pmatrix}
M_{11}&M_{12}&\cdots&M_{
aM_{i1}&aM_{i2}&\cdots&aM_{
M_{m1}&M_{m2}&\cdots&M_{
* (행의 합) 임의의 상수 <math>a\in K</math>에 대하여, <math>i</math>번째 행의 <math>a</math>배를 <math>j</math>번째 행에 더한다.
::<math>\begin{pmatrix}
M_{11}&M_{12}&\cdots&M_{
M_{i1}&M_{i2}&\cdots&M_{
M_{j1}&M_{j2}&\cdots&M_{
M_{m1}&M_{m2}&\cdots&M_{
\implies\begin{pmatrix}
M_{11}&M_{12}&\cdots&M_{
M_{i1}&M_{i2}&\cdots&M_{
aM_{i1}+M_{j1}&aM_{i2}+M_{j2}&\cdots&aM_{
M_{m1}&M_{m2}&\cdots&M_{
===
<math>m\times
<math>m\times
* 만약 <math>0=M_{i1}=\cdots=M_{
* 만약 <math>i<i'</math>이며 <math>j_0(i)</math>와 <math>j_0(i')</math>가 존재한다면, <math>j_0(i)<j_0(i')</math>이다.
<math>m\times
* <math>M</math>은 행사다리꼴행렬이다.
* <math>j_0(i)</math>가 존재한다면, <math>M_{i,j_0(i)}=1</math>이며, 모든 <math>i'\ne i</math>에 대하여 <math>M_{i',j_0(i)}=0</math>이다.
즉, 행사다리꼴행렬은 행렬의
예를 들어, 다음과 같은 행렬은 행사다리꼴행렬이다.
줄 78 ⟶ 79:
=== 가우스 소거법 ===
'''가우스 소거법'''은 <math>m\times n</math> 행렬 <math>M</math>을 기본행연산을 가하여 행사다리꼴행렬로 만드는 알고리즘이며, 다음과 같다. 먼저 첫번째 행을 다음과 같이 처리한다.
# 선행 계수가 위치하는 가장 작은 열수 <math>j_1\le n
# <math>M_{1j_0}=0</math>이라면, 첫번째 행을 <math>M_{i_1j_1}\ne0</math>인 어떤 <math>i_1>1</math>번째 행과 치환한다.
# 모든 <math>i>1</math>번째 행에 첫번째 행의 <math>-M_{ij_1}/M_{1j_1}</math>배를 더해, <math>M_{1j_1}</math> 밑의 항들을 0으로 만든다.
그 뒤, 두번째 행을 다음과 같이 처리한다.
# 어떤 <math>i\ge2</math>번째 행의 선행 계수가 위치하는 가장 작은 열수 <math>j_2\le n
# <math>M_{2j_2}=0</math>이라면, 두번째 행을 <math>M_{i_2j_2}\ne0</math>인 어떤 <math>i_2>2</math>번째 행과 치환한다.
# 모든 <math>i>2</math>번째 행에 두번째 행의 <math>-M_{ij_2}/M_{2j_2}</math>배를 더해, <math>M_{2j_2}</math> 밑의 항들을 0으로 만든다.
뒤에 오는 다른 행에 대하여, 순차적으로 위와 같이 처리한다. 일반적으로, <math>k</math>번째 행은 다음과 같이 처리한다.
# 어떤 <math>i\ge k</math>번째 행의 선행 계수가 위치하는 가장 작은 열수 <math>j_k\le n
# <math>M_{kj_k}=0</math>이라면, <math>k</math>번째 행을 <math>M_{i_kj_k}\ne0</math>인 어떤 <math>i_k>k</math>번째 행과 치환한다.
# 모든 <math>i>k</math>번째 행에 <math>k</math>번째 행의 <math>-M_{ij_k}/M_{kj_k}</math>배를 더해, <math>M_{kj_k}</math> 밑의 항들을 0으로 만든다.
만약 어떤 <math>j_{r+1}\le n</math>가 존재하지 않는다면, <math>r</math>번째 행에서 멈춘다. 만약 항상 <math>j_k\le n
기약행사다리꼴행렬을 원한다면, 찾았던 모든 <math>j_k=j_r,j_{r-2},\ldots,j_1</math>에 대하여 순차적으로 다음과 같은 단계를 추가로 거친다.
# <math>k</math>번째 행에 <math>1/M_{kj_k}</math>를 곱해, <math>M_{kj_k}</math>를 1로 만든다.
# 모든 <math>i<k</math>번째 행에 <math>k</math>번째 행의 <math>-M_{ij_k}</math>배를 더해, <math>M_{kj_k}</math> 위의 항들을 0으로 만든다.
여기서 <math>r\le m</math>이며 <math>r\le n</math>인 데 주의하자. 사실, 이는 행렬의 [[계수 (선형대수학)|계수]]이다.
== 성질 ==
줄 102 ⟶ 105:
세 가지 기본행연산은 모두 [[가역 함수|가역 연산]]이다.
* 행의 치환의 역연산은, 자기 자신이다.
* 행의 상수곱의 역연산은, 그 행에 그
* 어떤 행에 다른 행의 배수를 더하는 것의 역연산은, 더하는 대신 빼는 것이다.
두 연립일차방정식의 [[첨가 행렬]]이 하나에 기본행연산을 가하여 다른 하나를 얻을 수 있다면, [[행동치]]
[[기본 행렬]]은 [[단위 행렬]]에 기본행연산을 한 번 가하여 얻는 행렬이다. 이에 따라, 세 가지 기본행연산은 기본 행렬 곱셈과
=== 행사다리꼴행렬 ===
가우스 소거법 알고리즘에서 알 수 있듯, 모든 연립일차방정식의 [[첨가 행렬]]은 그와 같은 해를 갖는 행사다리꼴행렬 및 기약행사다리꼴행렬로 변환할 수 있다. 따라서, 연립일차방정식의 풀이는 행사다리꼴행렬 및 기약행사다리꼴에 대한 풀이로 귀결된다.
<math>m\times
* 해가 존재한다.
*
* 해가 유일하다.
* <math>r=n</math>. 즉, 0행이 아닌 행의 개수는 미지수의 개수와 같다. 즉, 선행 계수가 없는 열이 계수 행렬에 존재하지 않는다.
달리 말해, 해가 존재하는 <math>Rx=0</math>의 경우, 다음 두 조건이 서로 [[동치]]이다.
* 해가 유일하지 않다. ([[체의 표수]]가 0이라면, 이는 해가 무한히 많은 것과 동치이다.)
* <math>r<n</math>. 즉, 0행이 아닌 행의 개수는 미지수의 개수보다 적다. 즉, 선행 계수가 없는 열이 계수 행렬에 존재한다.
=== 행렬식의 계산 ===
가우스 소거법을 사용하여 [[
* 기본행연산을 가하면, 행렬식은 "상수배" 변화한다. 즉,
** 행을 치환하면, 행렬식은 -1배가 된다.
** 행에 상수곱을 하면, 행렬식은 그 상수의 역수배가 된다.
** 어떤 행에 다른 어떤 행의 상수배를 더하면, 행렬식은 변하지 않는다.
* 가우스 소거법을 사용하여, <math>M</math>을 행사다리꼴행렬로 변환할 수 있다. 특히, 정사각행렬이므로, 이는 0행(즉 모든 항이 0인 행)을 갖거나, [[
* 0행을 갖는 정사각행렬의 행렬식은 0이다.
*
=== 역행렬의 계산 ===
가우스 소거법을 사용하여 [[
:<math>\begin{pmatrix}M_{1,1}&\cdots&M_{1,n}&1&\cdots&0\\
\vdots&\ddots&\vdots&\vdots&\ddots&\vdots\\
줄 143 ⟶ 148:
로 만든다면, 행렬 <math>\tilde M</math>은 <math>M^{-1}</math>과 같다.
:<math>\tilde M=M^{-1}</math>
=== 계수 계산 ===
가우스 소거법을 사용하여 행렬의 [[계수 (선형대수학)|계수]]를 계산할 수 있다. <math>m\times n</math> 행렬 <math>M</math>의 계수는 가우스 소거법을 가하여 얻는 행사다리꼴행렬에서 0이 아닌 행의 계수(즉, 선행 계수의 개수) <math>r</math>이다.
== 예 ==
| |||