위키백과

가우스 소거법: 두 판 사이의 차이

입체적으로 역사 찾아보기
← 이전 편집다음 편집 →
내용 삭제됨 내용 추가됨
시각위키텍스트
편집 요약 없음
편집 요약 없음
14번째 줄:
은 주어진 <math>m\times n</math> 행렬이고,
:<math>\mathbf x=\begin{pmatrix}x_1\\x_2\\\vdots\\x_{n-1}\\1\end{pmatrix}</math>
은 <math>n-1</math>개의 미지수를 포함하는 열벡터이다. 보통, 유일한 해를 가진 일차 연립 방정식의 경우 방정식의 수는 미지수의 수와 같으며, 즉 <math>m=n-1</math>이다. 그러나 해가 유일하지 못한 경우나, 해가 없는 경우, 방정식이 중복되는 경우 등에서는이는 <math>m\ne풀어서 n-1</math>일쓰면 수다음과 있다같다.
:<math>M_{11}x_1+M_{12}x_2+\cdots+M_{1,n-1}x_{n-1}+M_{1n}=0</math>
:<math>M_{21}x_1+M_{22}x_2+\cdots+M_{2,n-1}x_{n-1}+M_{2n}=0</math>
:<math>\vdots</math>
:<math>M_{m1}x_1+M_{m2}x_2+\cdots+M_{m,n-1}x_{n-1}+M_{mn}=0</math>
보통, 유일한 해를 가진 일차 연립 방정식의 경우 방정식의 수는 미지수의 수와 같으며, 즉 <math>m=n-1</math>이다. 그러나 해가 유일하지 못한 경우나, 해가 없는 경우, 방정식이 중복되는 경우 등에서는 <math>m\ne n-1</math>일 수 있다.
 
=== 기본행연산 ===
줄 98 ⟶ 103:
\end{pmatrix}
</math>
 
=== 가우스 소거법 알고리즘 ===
'''가우스 소거법'''은 <math>m\times n</math> 행렬 <math>M</math>을 기본행연산을 가하여 사다리꼴로 만드는 알고리즘이며, [[의사코드]]로는 다음과 같다. <math>M</math>의 각 열벡터들을 <math>M_1,\dots,M_m</math>이라고 쓰자.
:for <math>i_0=1,\dots,m</math>:
::<math>j_0(i_0)=\min\{j|j>j_0(i_0-1),\;\exists i\ge i_0\colon M_{ij}\ne0\}</math> (<math>j_0(i_0)</math>은 <math>i_0</math>번째 행의 선행계수의 위치)
::if <math>M_{i_0j_0(i_0)}=0</math>: (만약 선행계수가 0이라면)
:::<math>i_0'</math>가 <math>M_{i_0'j}\ne0</math>인 임의의 행이라고 하자. 만약 이러한 행이 없다면 다음 <math>i_0</math>으로 넘어간다.
:::<math>(M_{i_0},M_{i_0'})\leftarrow(M_{i_0'},M_{i_0})</math> (<math>i_0</math>번째 행과 <math>i_0'</math>번째 행을 치환)
::(*) <math>M_{i_0}\leftarrow M_{i_0}/M_{i_0j_0(i_0)}</math>
::for <math>i=i_0+1,\dots,m</math>:
:::<math>M_i\leftarrow M_i-M_{i_0}(M_{ij_0(i_0)}/M_{i_0j_0(i_0)})</math> (<math>i</math>번째 행에 <math>i_0</math>번째 행의 <math>-M_{ij_0}/M_{j_0j_0}</math>배를 더한다)
::(*) for <math>i=1,\dots,i_0-1</math>:
:::<math>M_i\leftarrow M_i-M_{i_0}(M_{ij_0(i_0)}/M_{i_0j_0(i_0)})</math> (<math>i</math>번째 행에 <math>i_0</math>번째 행의 <math>-M_{ij_0}/M_{j_0j_0}</math>배를 더한다)
이 [[의사코드]]는 행렬을 기약행 사다리꼴로 만든다. 만약 기약행 사다리꼴 대신 그냥 사다리꼴로 족하다면, 앞에 (*)이 붙은 단계들은 생략할 수 있다.
 
== 예 ==
다음과 같은 선형 방정식이 주어졌다고 하자.
=== 전진 소거법(Forward elimination) ===
* :<math>\begin{matrix}
\left\{ \begin{matrix} ▼
2u &+& v &+& w &=& 5 \\
4u &-& 6v && &=& -2 \\
-2u &+& 7v &+& 2w &=& 9
\end{matrix} \right. </math>
첫 번째 열을 사다리꼴로 놓기 위해, 다음과 같은 기본행연산을 가한다.
</math>
*# 첫째 식의 1배를-2배를 셋째둘째 식에 더한다.▼
 
*# 첫째 식의 -2배를1배를 둘째셋째 식에 더한다.
그렇다면 다음과 같다.
▲*# 첫째 식의 1배를 셋째 식에 더한다.
▲\left\{ :<math>\begin{matrix}
 
* <math>
\left\{ \begin{matrix}
2u &+& v &+& w &=& 5 \\
&-& 8v &-& 2w &=& -12 \\
&& 8v &+& 3w &=& 14
\end{matrix} \right.
</math>
두 번째 열을 사다리꼴로 놓기 위해, 다음과 같은 기본행연산을 가한다.
 
*#<li value=3> 둘째 식의 1배를 셋째 식에 더한다.
그러면 다음과 같다.
 
* :<math>\begin{matrix}
\left\{ \begin{matrix}
2u &+& v &+& w &=& 5 \\
&-& 8v &-& 2w &=& -12 \\
&& && w &=& 2
\end{matrix} \right. </math>
이제 행렬이 사다리꼴이 되었다.
</math>
 
그렇다면, 이제 미지수들을 가장 밑의 행으로부터 순서대로 대입하여 계산할 수 있다.
=== 후진 대입법(Backward substitution) ===
* :<math>w=2</math>
:<math>v-2w=-12\implies v=-1</math>
\left\{ \begin{matrix}
:<math>2u+v+w=5\implies u=1</math>
2u &+& v &+& w &=& 5 \\
&-& 8v &-& 2w &=& -12 \\
&& && w &=& 2
\end{matrix} \right.
</math>
 
=== 풀기 곤란한 경우 ===▼
*# 셋째 식이 w = 2임을 말한다.
=== ;정칙(Nonsingular) 행렬일 경우의 예 ===▼
*# w를 둘째 식에 대입하여 v를 구하면 v = 1이다.
*# 마찬가지로 v, w를 첫째 식에 대입하여 u를 구하면 u = 1이다.
 
각 식 앞에 있는 <math>2u, -8v, w</math>의 [[계수]]인 2, -8, 1을 [[피벗]](pivot)이라고 부른다.
 
▲== 풀기 곤란한 경우 ==
▲=== 정칙(Nonsingular) 행렬일 경우의 예 ===
(식 2와 3을 바꾸어 해결한다)
 
* <math>
\begin{cases}
줄 157 ⟶ 161:
</math>
 
=== ;비정칙(Singular) 행렬일 경우의 예 ===
(해가 없는 경우도 있다.)
 
원본 주소 "https://ko.wikipedia.org/wiki/가우스_소거법"