가우스 소거법

틀:위키데이터 속성 추적 선형대수학에서 가우스 소거법(Gauß消去法, 틀:Llang)이란, 연립일차방정식을 풀이하는 알고리즘이다. 풀이 과정에서, 일부 미지수가 차츰 소거되어 결국 남은 미지수에 대한 선형 결합으로 표현되면서 풀이가 완성된다. 가우스 소거법은 보통 행렬을 사용하며, 첨가 행렬을 그와 풀이가 같은 더 간단한 행렬로 변환하여 풀이를 완성한다. 가우스 소거법은 행렬식과 역행렬의 계산에도 응용된다.

정의

체 $K$ 에 대하여, $n$ 개의 미지수에 대한 $m$ 개의 방정식으로 구성된 연립일차방정식

M x = 0

이 주어졌다고 하자. 여기서

M = (\begin{matrix} M_{11} & M_{12} & \dots & M_{1, n + 1} \\ M_{21} & M_{22} & \dots & M_{2, n + 1} \\ ⋮ & ⋮ & ⋱ & ⋮ \\ M_{m 1} & M_{m 2} & \dots & M_{m, n + 1} \end{matrix})

은 주어진 $m \times (n + 1)$ 행렬이고,

x = (\begin{matrix} x_{1} \\ x_{2} \\ ⋮ \\ x_{n} \\ 1 \end{matrix})

은 $n$ 개의 미지수를 포함하는 열벡터이다. 즉, 이는 풀어서 쓰면 다음과 같다.

M_{11} x_{1} + M_{12} x_{2} + \dots + M_{1, n} x_{n} + M_{1, n + 1} = 0

M_{21} x_{1} + M_{22} x_{2} + \dots + M_{2, n} x_{n} + M_{2, n + 1} = 0

⋮

M_{m 1} x_{1} + M_{m 2} x_{2} + \dots + M_{m, n} x_{n} + M_{m, n + 1} = 0

기본 행 연산

틀:본문 이 경우, 이 연립방정식에 다음과 같은 세 가지 연산을 가할 수 있다. 이들을 기본 행 연산(基本行演算, 틀:Llang)이라고 한다.

(행의 치환) $M$ 의 $i$ 번째 행과 $j$ 번째 행을 서로 바꾼다.

(\begin{matrix} M_{11} & M_{12} & \dots & M_{1, n + 1} \\ ⋮ & ⋮ & ⋮ \\ M_{i 1} & M_{i 2} & \dots & M_{i, n + 1} \\ ⋮ & ⋮ & ⋮ \\ M_{j 1} & M_{j 2} & \dots & M_{j, n + 1} \\ ⋮ & ⋮ & ⋮ \\ M_{m 1} & M_{m 2} & \dots & M_{m, n + 1} \end{matrix}) x = 0 ⟹ (\begin{matrix} M_{11} & M_{12} & \dots & M_{1, n + 1} \\ ⋮ & ⋮ & ⋮ \\ M_{j 1} & M_{j 2} & \dots & M_{j, n + 1} \\ ⋮ & ⋮ & ⋮ \\ M_{i 1} & M_{i 2} & \dots & M_{i, n + 1} \\ ⋮ & ⋮ & ⋮ \\ M_{m 1} & M_{m 2} & \dots & M_{m, n + 1} \end{matrix}) x = 0

(행의 상수곱) $i$ 번째 행을 0이 아닌 임의의 상수 $a \in K ∖ {0}$ 으로 곱한다.

(\begin{matrix} M_{11} & M_{12} & \dots & M_{1, n + 1} \\ ⋮ & ⋮ & ⋮ \\ M_{i 1} & M_{i 2} & \dots & M_{i, n + 1} \\ ⋮ & ⋮ & ⋮ \\ M_{m 1} & M_{m 2} & \dots & M_{m, n + 1} \end{matrix}) x = 0 ⟹ (\begin{matrix} M_{11} & M_{12} & \dots & M_{1, n + 1} \\ ⋮ & ⋮ & ⋮ \\ a M_{i 1} & a M_{i 2} & \dots & a M_{i, n + 1} \\ ⋮ & ⋮ & ⋮ \\ M_{m 1} & M_{m 2} & \dots & M_{m, n + 1} \end{matrix}) x = 0

(행의 합) 임의의 상수 $a \in K$ 에 대하여, $i$ 번째 행의 $a$ 배를 $j$ 번째 행에 더한다.

(\begin{matrix} M_{11} & M_{12} & \dots & M_{1, n + 1} \\ ⋮ & ⋮ & ⋮ \\ M_{i 1} & M_{i 2} & \dots & M_{i, n + 1} \\ ⋮ & ⋮ & ⋮ \\ M_{j 1} & M_{j 2} & \dots & M_{j, n + 1} \\ ⋮ & ⋮ & ⋮ \\ M_{m 1} & M_{m 2} & \dots & M_{m, n + 1} \end{matrix}) x = 0 ⟹ (\begin{matrix} M_{11} & M_{12} & \dots & M_{1, n + 1} \\ ⋮ & ⋮ & ⋮ \\ M_{i 1} & M_{i 2} & \dots & M_{i, n + 1} \\ ⋮ & ⋮ & ⋮ \\ a M_{i 1} + M_{j 1} & a M_{i 2} + M_{j 2} & \dots & a M_{i, n + 1} + M_{j, n + 1} \\ ⋮ & ⋮ & ⋮ \\ M_{m 1} & M_{m 2} & \dots & M_{m, n + 1} \end{matrix}) x = 0

행사다리꼴행렬

일반적으로 사다리꼴행렬(Echelon matrix,에쉴론 메트릭스, 또는 행사다리꼴행렬)은,

$m \times (n + 1)$ 행렬 $M$ 에 대하여, $j_{0} (i) = \min {j \leq n : M_{i j} \neq 0}$ 이라고 하면, $M_{i, j_{0} (i)}$ 를 $i$ 번째 행의 선행 계수(先行係數, 틀:Llang)라고 한다. 선행 계수는 존재하지 않을 수 있다.

$m \times (n + 1)$ 행렬 $M$ 이 다음 조건을 만족시키면, $M$ 을 행사다리꼴행렬(사다리꼴行列, 틀:Llang)이라고 한다.

만약 $0 = M_{i 1} = \dots = M_{i n}$ 이라면, 모든 $i \leq i^{'}$ 에 대하여 $0 = M_{i^{'} 1} = \dots = M_{i^{'} n}$ 이다.
만약 $i < i^{'}$ 이며 $j_{0} (i)$ 와 $j_{0} (i^{'})$ 가 존재한다면, $j_{0} (i) < j_{0} (i^{'})$ 이다.

$m \times (n + 1)$ 행렬 $M$ 이 다음 조건을 만족시키면, $M$ 을 기약행사다리꼴행렬(旣約行사다리꼴行列, 틀:Llang)이라고 한다.

$M$ 은 행사다리꼴행렬이다.
$j_{0} (i)$ 가 존재한다면, $M_{i, j_{0} (i)} = 1$ 이며, 모든 $i^{'} \neq i$ 에 대하여 $M_{i^{'}, j_{0} (i)} = 0$ 이다.

즉, 행사다리꼴행렬은 행렬의 항들이 대략 위에는 사다리꼴, 밑에는 0인 형태의 행렬이다. 기약행사다리꼴행렬 조건은 행사다리꼴행렬 조건보다 더 강한 조건이다.

예를 들어, 다음과 같은 행렬은 행사다리꼴행렬이다.

(\begin{matrix} 1 & a_{0} & a_{1} & a_{2} & a_{3} \\ 0 & 0 & 2 & a_{4} & a_{5} \\ 0 & 0 & 0 & 1 & a_{6} \end{matrix})

다음과 같은 행렬은 기약행사다리꼴행렬이다.

(\begin{matrix} 1 & 0 & a_{1} & 0 & a_{2} \\ 0 & 1 & a_{3} & 0 & a_{4} \\ 0 & 0 & 0 & 1 & a_{5} \end{matrix})

가우스 소거법

가우스 소거법은 $m \times n$ 행렬 $M$ 을 기본행연산을 가하여 행사다리꼴행렬로 만드는 알고리즘이며, 다음과 같다. 먼저 첫번째 행을 다음과 같이 처리한다.

선행 계수가 위치하는 가장 작은 열수 $j_{1} \leq n$ 을 찾는다.
$M_{1 j_{1}} = 0$ 이라면, 첫번째 행을 $M_{i_{1} j_{1}} \neq 0$ 인 어떤 $i_{1} > 1$ 번째 행과 치환한다.
모든 $i > 1$ 번째 행에 첫번째 행의 $- M_{i j_{1}} / M_{1 j_{1}}$ 배를 더해, $M_{1 j_{1}}$ 밑의 항들을 0으로 만든다.

그 뒤, 두번째 행을 다음과 같이 처리한다.

어떤 $i \geq 2$ 번째 행의 선행 계수가 위치하는 가장 작은 열수 $j_{2} \leq n$ 을 찾는다.
$M_{2 j_{2}} = 0$ 이라면, 두번째 행을 $M_{i_{2} j_{2}} \neq 0$ 인 어떤 $i_{2} > 2$ 번째 행과 치환한다.
모든 $i > 2$ 번째 행에 두번째 행의 $- M_{i j_{2}} / M_{2 j_{2}}$ 배를 더해, $M_{2 j_{2}}$ 밑의 항들을 0으로 만든다.

뒤에 오는 다른 행에 대하여, 순차적으로 위와 같이 처리한다. 일반적으로, $k$ 번째 행은 다음과 같이 처리한다.

어떤 $i \geq k$ 번째 행의 선행 계수가 위치하는 가장 작은 열수 $j_{k} \leq n$ 을 찾는다.
$M_{k j_{k}} = 0$ 이라면, $k$ 번째 행을 $M_{i_{k} j_{k}} \neq 0$ 인 어떤 $i_{k} > k$ 번째 행과 치환한다.
모든 $i > k$ 번째 행에 $k$ 번째 행의 $- M_{i j_{k}} / M_{k j_{k}}$ 배를 더해, $M_{k j_{k}}$ 밑의 항들을 0으로 만든다.틀:Sfn

만약 어떤 $j_{r + 1} \leq n$ 가 존재하지 않는다면, $r$ 번째 행에서 멈춘다. 만약 항상 $j_{k} \leq n$ 를 찾을 수 있다면, 모든 $k = 1, 2, \dots, m$ 번째 행에 대하여 순차적으로 위와 같이 처리하며, $r = n$ 으로 둔다. 기약행사다리꼴행렬을 원한다면, 찾았던 모든 $j_{k} = j_{r}, j_{r - 2}, \dots, j_{1}$ 에 대하여 순차적으로 다음과 같은 단계를 추가로 거친다.

$k$ 번째 행에 $1 / M_{k j_{k}}$ 를 곱해, $M_{k j_{k}}$ 를 1로 만든다.
모든 $i < k$ 번째 행에 $k$ 번째 행의 $- M_{i j_{k}}$ 배를 더해, $M_{k j_{k}}$ 위의 항들을 0으로 만든다.

여기서 $r \leq m$ 이며 $r \leq n$ 인 데 주의하자. 사실, 이는 행렬의 계수이다.

기약행사다리꼴행렬의 과정을 특히 조단이 제시한 "가우스 조단 소거법"으로 부른다.

성질

기본행연산

세 가지 기본행연산은 모두 가역 연산이다.

행의 치환의 역연산은, 자기 자신이다.
행의 상수곱의 역연산은, 그 행에 그 상수 대신 역수를 곱하는 것이다.
어떤 행에 다른 행의 배수를 더하는 것의 역연산은, 더하는 대신 빼는 것이다.

두 연립일차방정식의 첨가 행렬이 하나에 기본행연산을 가하여 다른 하나를 얻을 수 있다면, 행동치라고 한다. 첨가 행렬이 행동치라면, 연립방정식의 풀이는 서로 같다.

기본 행렬은 단위 행렬에 기본행연산을 한 번 가하여 얻는 행렬이다. 이에 따라, 세 가지 기본행연산은 기본 행렬 곱셈과 같다.

행사다리꼴행렬

가우스 소거법 알고리즘에서 알 수 있듯, 모든 연립일차방정식의 첨가 행렬은 그와 같은 해를 갖는 행사다리꼴행렬 및 기약행사다리꼴행렬로 변환할 수 있다. 따라서, 연립일차방정식의 풀이는 행사다리꼴행렬 및 기약행사다리꼴에 대한 풀이로 귀결된다.

$m \times (n + 1)$ 행사다리꼴행렬 $R$ 에 대한 연립일차방정식 $R x = 0$ 에 대하여, 다음 두 조건이 서로 동치이다.

해가 존재한다.
상수항이 0이 아닌 행이 존재하지 않는다. (상수항은 $n + 1$ 번째 열의 항, 0행은 선행 계수가 없는 행을 뜻한다.)

해가 존재하는 $R x = 0$ 의 경우, 다음 두 조건이 서로 동치이다.

해가 유일하다.
$r = n$ . 즉, 0행이 아닌 행의 개수는 미지수의 개수와 같다. 즉, 선행 계수가 없는 열이 계수 행렬에 존재하지 않는다.

달리 말해, 해가 존재하는 $R x = 0$ 의 경우, 다음 두 조건이 서로 동치이다.

해가 유일하지 않다. (체의 표수가 0이라면, 이는 해가 무한히 많은 것과 동치이다.)
$r < n$ . 즉, 0행이 아닌 행의 개수는 미지수의 개수보다 적다. 즉, 선행 계수가 없는 열이 계수 행렬에 존재한다.

행렬식의 계산

가우스 소거법을 사용하여 정사각행렬의 행렬식을 계산할 수 있다. 이는 정사각행렬에 대하여 다음 사실들이 성립하기 때문이다.

기본행연산을 가하면, 행렬식은 "상수배" 변화하며, 주어진 기본행연산이 행렬식을 변화시키는 배수는 자명하다. 즉,
- 행을 치환하면, 행렬식은 -1배가 된다.
- 행에 상수곱을 하면, 행렬식은 그 상수의 역수배가 된다.
- 어떤 행에 다른 어떤 행의 상수배를 더하면, 행렬식은 변하지 않는다.
가우스 소거법을 통해 행렬을 행사다리꼴행렬로 변환할 수 있다. 특히 정사각행렬이므로, 이는 0행(즉 모든 항이 0인 행)을 갖거나, 상삼각행렬이다.
0행을 갖는 정사각행렬의 행렬식은 0이다.
상삼각행렬의 행렬식은 모든 대각항의 곱이다.

역행렬의 계산

가우스 소거법을 사용하여 정사각행렬의 역행렬을 계산할 수 있다. $n \times n$ 행렬 $M$ 의 역행렬은 다음과 같이 계산한다. $M$ 에 $n \times n$ 단위행렬을 추가하여 $n \times 2 n$ 행렬로 만든다.

(\begin{matrix} M_{1, 1} & \dots & M_{1, n} & 1 & \dots & 0 \\ ⋮ & ⋱ & ⋮ & ⋮ & ⋱ & ⋮ \\ M_{n, 1} & \dots & M_{n, n} & 0 & \dots & 1 \end{matrix})

이 행렬에 기본행연산을 가하여

(\begin{matrix} 1 & \dots & 0 & {\tilde{M}}_{11} & \dots & {\tilde{M}}_{1, n} \\ ⋮ & ⋱ & ⋮ & ⋱ & ⋮ & ⋱ \\ 0 & \dots & 1 & {\tilde{M}}_{n, 1} & \dots & {\tilde{M}}_{n, n} \end{matrix})

로 만든다면, 행렬 $\tilde{M}$ 은 $M^{- 1}$ 과 같다.

\tilde{M} = M^{- 1}

계수 계산

가우스 소거법을 사용하여 행렬의 계수를 계산할 수 있다. $m \times n$ 행렬 $M$ 의 계수는 가우스 소거법을 가하여 얻는 행사다리꼴행렬에서 0이 아닌 행의 계수(즉, 선행 계수의 개수) $r$ 이다.

예

[\begin{matrix} 1 & 3 & 1 & 9 \\ 1 & 1 & - 1 & 1 \\ 3 & 11 & 5 & 35 \end{matrix}] \to [\begin{matrix} 1 & 3 & 1 & 9 \\ 0 & - 2 & - 2 & - 8 \\ 0 & 2 & 2 & 8 \end{matrix}] \to [\begin{matrix} 1 & 3 & 1 & 9 \\ 0 & - 2 & - 2 & - 8 \\ 0 & 0 & 0 & 0 \end{matrix}] \to [\begin{matrix} 1 & 0 & - 2 & - 3 \\ 0 & 1 & 1 & 4 \\ 0 & 0 & 0 & 0 \end{matrix}]

해가 유일한 연립 선형 방정식

다음과 같은 선형 방정식이 주어졌다고 하자.

\begin{matrix} 2 u & + & v & + & w & = & 5 \\ 4 u & - & 6 v & = & - 2 \\ - 2 u & + & 7 v & + & 2 w & = & 9 \end{matrix}

첫 번째 열을 사다리꼴로 놓기 위해, 다음과 같은 기본행연산을 가한다.

첫째 식의 -2배를 둘째 식에 더한다
첫째 식의 1배를 셋째 식에 더한다.

그렇다면 다음과 같다.

\begin{matrix} 2 u & + & v & + & w & = & 5 \\ - & 8 v & - & 2 w & = & - 12 \\ 8 v & + & 3 w & = & 14 \end{matrix}

두 번째 열을 사다리꼴로 놓기 위해, 다음과 같은 기본행연산을 가한다.

둘째 식의 1배를 셋째 식에 더한다. 그러면 다음과 같다.

\begin{matrix} 2 u & + & v & + & w & = & 5 \\ - & 8 v & - & 2 w & = & - 12 \\ w & = & 2 \end{matrix}

이제 행렬이 사다리꼴이 되었다. 그렇다면, 이제 미지수들을 가장 밑의 행으로부터 순서대로 대입하여 계산할 수 있다. 이것을 후방대입(back substitution)이라 한다.틀:Sfn

w = 2

- 8 v - 2 w = - 12 ⟹ v = 1

2 u + v + w = 5 ⟹ u = 1

해가 유일하지 않거나 없는 연립 선형 방정식

정칙(Nonsingular) 행렬일 경우의 예

(식 2와 3을 바꾸어 해결한다)

${\begin{matrix} 10 u + 2 v + - 1 w & = 27 \\ - 3 u + - 6 v + 2 w & = - 61.5 \\ u + v + 5 w & = - 21.5 \end{matrix}$

비정칙(Singular) 행렬일 경우의 예

(해가 없는 경우도 있다.)

${\begin{matrix} u + v + w & = ? \\ 2 u + 2 v + 5 w & = ? \\ 4 u + 4 v + 8 w & = ? \end{matrix}$

${\begin{matrix} u + v + w & = ? \\ 3 w & = ? \\ 4 w & = ? \end{matrix}$

역행렬의 계산

다음과 같은 행렬 $M$ 의 역행렬을 계산한다고 하자.

M = (\begin{matrix} - 1 & 1 & 2 \\ 3 & - 1 & 1 \\ - 1 & 3 & 4 \end{matrix})

기본행연산을 가하면, 다음과 같다.

\begin{matrix} (\begin{matrix} A & | & I \end{matrix}) & \to (\begin{matrix} - 1 & 1 & 2 \\ 3 & - 1 & 1 \\ - 1 & 3 & 4 \end{matrix} | \begin{matrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{matrix}) \\ \to (\begin{matrix} - 1 & 1 & 2 \\ 0 & 2 & 7 \\ 0 & 2 & 2 \end{matrix} | \begin{matrix} 1 & 0 & 0 \\ 3 & 1 & 0 \\ - 1 & 0 & 1 \end{matrix}) \\ \to (\begin{matrix} - 1 & 1 & 2 \\ 0 & 2 & 7 \\ 0 & 0 & - 5 \end{matrix} | \begin{matrix} 1 & 0 & 0 \\ 3 & 1 & 0 \\ - 4 & - 1 & 1 \end{matrix}) \\ \to (\begin{matrix} 1 & - 1 & - 2 \\ 0 & 1 & 3.5 \\ 0 & 0 & 1 \end{matrix} | \begin{matrix} - 1 & 0 & 0 \\ 1.5 & 0.5 & 0 \\ 0.8 & 0.2 & - 0.2 \end{matrix}) \\ \to (\begin{matrix} 1 & - 1 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{matrix} | \begin{matrix} 0.6 & 0.4 & - 0.4 \\ - 1.3 & - 0.2 & 0.7 \\ 0.8 & 0.2 & - 0.2 \end{matrix}) \\ \to (\begin{matrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{matrix} | \begin{matrix} - 0.7 & 0.2 & 0.3 \\ - 1.3 & - 0.2 & 0.7 \\ 0.8 & 0.2 & - 0.2 \end{matrix}) \end{matrix}

따라서 $M^{- 1}$ 은 다음과 같다.

M^{- 1} = (\begin{matrix} - 0.7 & 0.2 & 0.3 \\ - 1.3 & - 0.2 & 0.7 \\ 0.8 & 0.2 & - 0.2 \end{matrix})

같이 보기

외부 링크

각주

틀:각주

참고 문헌

틀:서적 인용

틀:선형대수학

틀:전거 통제

가우스 소거법

목차

정의

기본 행 연산

행사다리꼴행렬

가우스 소거법

성질

기본행연산

행사다리꼴행렬

행렬식의 계산

역행렬의 계산

계수 계산

예

해가 유일한 연립 선형 방정식

해가 유일하지 않거나 없는 연립 선형 방정식

역행렬의 계산

같이 보기

외부 링크

각주

참고 문헌

둘러보기 메뉴

가우스 소거법

정의

기본 행 연산

행사다리꼴행렬

가우스 소거법

성질

기본행연산

행사다리꼴행렬

행렬식의 계산

역행렬의 계산

계수 계산

예

해가 유일한 연립 선형 방정식

해가 유일하지 않거나 없는 연립 선형 방정식

역행렬의 계산

같이 보기

외부 링크

각주

참고 문헌

둘러보기 메뉴

검색