작은숲:공책/선형대수/Gaussian Elimination

공책 문서입니다. 독자연구성 서술이나 난해한 서술이 있을 수도 있음에 유의해주세요.

Summary (요약)

This article is about Gaussian Elimination and Gauss-Jordan Elimination. (가우스 소거법과 가우스/조르당 소거법에 관한 문서입니다.)

Object of the note (이 강의 노트의 목적)

The object of the article is explaning Gaussian Elimination and solving system of linear equations using the method. (가우스 소거법을 사용하는 방법과 이 소거법을 이용해서 선형 연립방정식을 푸는 방법을 설명한다.)

What is the system of linear equations? (선형 연립방정식이란?)

wikipedia:System_of_linear_equations, w:ko:연립 일차 방정식 문서를 참고하십시오.

The system of linear equations with $m$ equations and $n$ variables has the format.

a_{11} x_{1} + a_{12} x_{2} + a_{13} x_{3} + \dots + a_{1 n} x_{n} = b_{1}

a_{21} x_{1} + a_{22} x_{2} + a_{23} x_{3} + \dots + a_{2 n} x_{n} = b_{2}

a_{31} x_{1} + a_{32} x_{2} + a_{33} x_{3} + \dots + a_{3 n} x_{n} = b_{3}

⋮

a_{m 1} x_{1} + a_{m 2} x_{2} + a_{m 3} x_{3} + \dots + a_{m n} x_{n} = b_{m}

By the definition of multiplications of matrix, this equation can be expressed as the matrix form.

(\begin{matrix} a_{11} & a_{12} & a_{13} & \dots & a_{1 n} \\ a_{21} & a_{22} & a_{23} & \dots & a_{2 n} \\ a_{31} & a_{32} & a_{33} & \dots & a_{3 n} \\ ⋮ & ⋮ & ⋮ & ⋮ \\ a_{m 1} & a_{m 2} & a_{m 3} & \dots & a_{m n} \end{matrix}) (\begin{matrix} x_{1} \\ x_{2} \\ x_{3} \\ ⋮ \\ x_{n} \end{matrix}) = (\begin{matrix} b_{1} \\ b_{2} \\ b_{3} \\ ⋮ \\ b_{m} \end{matrix})

We can express each matrices in the above equation as $A_{m \times n} = (a_{i} j)$ , $x_{n \times 1} = (x_{i})$ , $b_{m \times 1} = (b_{i})$ 라고 하면, 연립 일차 방정식은 다음과 같이 단순하게 쓸 수 있다.

A x = b

In this case, $A$ is called the coefficient matrix(계수 행렬), $x$ called solution vector(해 벡터), and $b$ called source vector(소스 벡터). Also, the matrix adjointing coefficient matrix and source matrix $(A | b)$ is called augmented matrix(첨가 행렬).

The system of linear equations $A x = b$ is called homogeneous(동기 연립 일차 방정식) if $b = 0$ and nonhomogeneous(비동기 연립 일차 방정식) if $b \neq 0$ .

^[1]

What is Guassian Elimination? (가우스 소거법이란?)

Gaussian Elimination is a method of solving systems of linear eqautions by operating augmented matrix with row interchange, multiplication of rows and add a row to a multiple of other rows in order to simplify augmented matrix and find solutions.
가우스 소거법 - 첨가행렬을 행 교환, 상수배 혹은 선형 연립 방정식을 푸는 전략입니다.

Core strategy - Making the coefficient $a_{i} j = 0$ by subtracting other coefficients of rows. Each column should have at most one nonzero coefficients. (행의 상수배한 것을 적절히 빼서 각 열마다 기껏해야 1개를 제외하고 모두 계수를 0으로 만드는 전략입니다.) 구체적으로는 아래와 같이 시행할 것입니다.

How it works(동작 원리)

Interchanging rows does not change solutions - 행 교환은 연립방정식의 해를 바꾸지 않습니다.
Multiplication by constant does not change solutions - 행의 상수배는 연립방정식의 해를 바꾸지 않습니다. This is useful strategy in order to make nonzero leading coeffcient as 1. (각 행에서 최초로 0 아닌 계수가 1로 만드는데 유용합니다.)
Adding a multiple of one row to the other row does not change solutions - 다른 행의 상수배를 더해도 해는 보존됩니다. This is useful strategy in order to remove extraneous coefficients in other rows and make each column contain at most one nonzero coefficient. 이 전략은 첨가행렬에서 각 열마다 0 아닌 숫자가 최대 1개까지 나타나게 만들기 위한 전략입니다.

Terms (용어)

Row-echelon form (행 사다리꼴 행렬)
- Matrix $(a_{i j})$ - Each row matrix $M_{r} = (a_{r j})$ r fixed.
- Leading coefficient(선행계수) - For $M_{r}$ rth row matrix, $a_{r j (r)}$ with $j (r) = \min {j | a_{r j (r)} \neq 0}$
- Row-echelon form - A is row-echelon form if
  - rth row $M_{r} = 0$ , then for $s > r$ sth row $M_{s} = 0$
  - suppose $a_{r j (s)}$ is the leading coeffcient of rth row, then for s>r, $M_{s} = 0$ or $j (s) > j (r)$
- Reduced Row-echelon form (기약 행 사다리꼴 행렬) - A row-echelon form A is the reduced row echlon form i
  - for leading coefficient $a_{r J (r)}$ , (r=1, ... k), $j (1) < j (2) < \dots < j (k)$ - for each $j \leq j (k)$ $j$ th row has at most one nonzero coefficient.

Solution of a question (문제풀이)

Gaussian Elimination - Make augmented matrix as Row-echelon form and using back substitution.

${\begin{matrix} x & + & y & + & 2 z & = & 9 \\ 2 x & + & 4 y & - & 3 z & = & 1 \\ 3 x & + & 6 y & - & 5 z & = & 0 \end{matrix}$

Express system of linear equation as augmented matrix

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

$M_{2} \leftarrow M_{2} - 2 \times M_{1}$

$(\begin{matrix} 1 & 1 & 2 & 9 \\ 0 & 2 & - 7 & - 17 \\ 3 & 6 & - 5 & 0 \end{matrix})$

$M_{3} \leftarrow M_{3} - 3 \times M_{1}$

$(\begin{matrix} 1 & 1 & 2 & 9 \\ 0 & 2 & - 7 & - 17 \\ 0 & 3 & - 11 & - 27 \end{matrix})$

$M_{2} \leftarrow M_{2} \times 1 / 2$

$(\begin{matrix} 1 & 1 & 2 & 9 \\ 0 & 1 & - 7 / 2 & - 17 / 2 \\ 0 & 3 & - 11 & - 27 \end{matrix})$

$M_{3} \leftarrow M_{3} - M_{2} \times 3$

$(\begin{matrix} 1 & 1 & 2 & 9 \\ 0 & 1 & - 7 / 2 & - 17 / 2 \\ 0 & 0 & - 1 / 2 & - 3 / 2 \end{matrix})$

$- 1 / 2 z = - 3 / 2 \to z = 3$
$y - 7 / 2 z = y - 21 / 2 = - 17 / 2 \to y = 2$ (Back Substitution)
$x + y + 2 z = x + 8 = 9 \to x = 1$ (Back Substitution)

Gauss-Jordan Elimination - Make Augmented Matrix as Reduced Row-echelon form.

${\begin{matrix} x & + & y & + & 2 z & = & 9 \\ 2 x & + & 4 y & - & 3 z & = & 1 \\ 3 x & + & 6 y & - & 5 z & = & 0 \end{matrix}$

Express system of linear equation as augmented matrix

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

$M_{2} \leftarrow M_{2} - 2 \times M_{1}$

$(\begin{matrix} 1 & 1 & 2 & 9 \\ 0 & 2 & - 7 & - 17 \\ 3 & 6 & - 5 & 0 \end{matrix})$

$M_{3} \leftarrow M_{3} - 3 \times M_{1}$

$(\begin{matrix} 1 & 1 & 2 & 9 \\ 0 & 2 & - 7 & - 17 \\ 0 & 3 & - 11 & - 27 \end{matrix})$

$M_{2} \leftarrow M_{2} \times 1 / 2$

$(\begin{matrix} 1 & 1 & 2 & 9 \\ 0 & 1 & - 7 / 2 & - 17 / 2 \\ 0 & 3 & - 11 & - 27 \end{matrix})$

$M_{3} \leftarrow M_{3} - M_{2} \times 3$

$(\begin{matrix} 1 & 1 & 2 & 9 \\ 0 & 1 & - 7 / 2 & - 17 / 2 \\ 0 & 0 & - 1 / 2 & - 3 / 2 \end{matrix})$

$M_{3} \leftarrow M_{3} \times - 2$

$(\begin{matrix} 1 & 1 & 2 & 9 \\ 0 & 1 & - 7 / 2 & - 17 / 2 \\ 0 & 0 & 1 & 3 \end{matrix})$

$M_{1} \leftarrow M_{1} + M_{2} \times - 1$

$(\begin{matrix} 1 & 0 & 11 / 2 & 35 / 2 \\ 0 & 1 & - 7 / 2 & - 17 / 2 \\ 0 & 0 & 1 & 3 \end{matrix})$

$M_{1} \leftarrow M_{1} + M_{3} \times - 11 / 2, M_{2} \leftarrow M_{2} + M_{3} \times 7 / 2$

$(\begin{matrix} 1 & 0 & 0 & 1 \\ 0 & 1 & 0 & 2 \\ 0 & 0 & 1 & 3 \end{matrix})$

Example

General Solution
구문 분석 실패 (알 수 없는 함수 "\begin{pmatrix}"): {\displaystyle \begin{pmatrix} {a} & {b} \\ {c}& {d} \end{pmatrix} \begin{pmatrix} {x \\ y} \end{pmatrix} = \begin{pmatrix} {m} \\ {n} \end{pmatrix} }

or $(\begin{matrix} a & b & | & m \\ c & d & | & n \end{matrix})$ ( $a d - b c \neq 0$ )

has a unique pair of solution $(\begin{matrix} x \\ y \end{matrix}) = \frac{1}{a d - b c} (\begin{matrix} d m - b n \\ - c m + a n \end{matrix})$

Sources

위키백과:가우스 소거법/ Wikipedia:Gaussian Elimination
Howrd Anton, Chris Rorres, 《Elementary Linear Algebra》, 9th Edition, John Wiley & Sons, 2004.

각주

↑ 출처 : 위키백과:연립 일차 방정식

[1] 출처 : 위키백과:연립 일차 방정식

[1]