작은숲:공책/선형대수/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}+\cdots +a_{1n}x_{n}=b_{1}

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

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

\vdots

a_{m1}x_{1}+a_{m2}x_{2}+a_{m3}x_{3}+\cdots +a_{mn}x_{n}=b_{m}

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

{\begin{pmatrix}a_{11}&a_{12}&a_{13}&\cdots &a_{1n}\\a_{21}&a_{22}&a_{23}&\cdots &a_{2n}\\a_{31}&a_{32}&a_{33}&\cdots &a_{3n}\\\vdots &\vdots &\vdots &&\vdots \\a_{m1}&a_{m2}&a_{m3}&\cdots &a_{mn}\\\end{pmatrix}}{\begin{pmatrix}x_{1}\\x_{2}\\x_{3}\\\vdots \\x_{n}\end{pmatrix}}={\begin{pmatrix}b_{1}\\b_{2}\\b_{3}\\\vdots \\b_{m}\end{pmatrix}}

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})$ 라고 하면, 연립 일차 방정식은 다음과 같이 단순하게 쓸 수 있다.

Ax=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 $Ax=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개까지 나타나게 만들기 위한 전략입니다.

구문 분석 실패 (SVG를 사용하되 미지원 시 PNG 사용 (브라우저 플러그인을 통해 MathML 활성화 가능): "https://wikimedia.org/api/rest_v1/" 서버에서 잘못된 응답 ('Math extension cannot connect to Restbase.'):): {\displaystyle }

Terms (용어)

Row-echelon form (행 사다리꼴 행렬)
- Matrix 구문 분석 실패 (SVG를 사용하되 미지원 시 PNG 사용 (브라우저 플러그인을 통해 MathML 활성화 가능): "https://wikimedia.org/api/rest_v1/" 서버에서 잘못된 응답 ('Math extension cannot connect to Restbase.'):): {\displaystyle (a_{ij})} - Each row matrix 구문 분석 실패 (SVG를 사용하되 미지원 시 PNG 사용 (브라우저 플러그인을 통해 MathML 활성화 가능): "https://wikimedia.org/api/rest_v1/" 서버에서 잘못된 응답 ('Math extension cannot connect to Restbase.'):): {\displaystyle M_r= (a_{rj})} r fixed.
- Leading coefficient(선행계수) - For 구문 분석 실패 (SVG를 사용하되 미지원 시 PNG 사용 (브라우저 플러그인을 통해 MathML 활성화 가능): "https://wikimedia.org/api/rest_v1/" 서버에서 잘못된 응답 ('Math extension cannot connect to Restbase.'):): {\displaystyle M_r} rth row matrix, 구문 분석 실패 (SVG를 사용하되 미지원 시 PNG 사용 (브라우저 플러그인을 통해 MathML 활성화 가능): "https://wikimedia.org/api/rest_v1/" 서버에서 잘못된 응답 ('Math extension cannot connect to Restbase.'):): {\displaystyle a_{r j(r)} } with 구문 분석 실패 (SVG를 사용하되 미지원 시 PNG 사용 (브라우저 플러그인을 통해 MathML 활성화 가능): "https://wikimedia.org/api/rest_v1/" 서버에서 잘못된 응답 ('Math extension cannot connect to Restbase.'):): {\displaystyle j(r)=\min \{j | a_{r j(r)} \neq 0 \}}
- Row-echelon form - A is row-echelon form if
  - rth row 구문 분석 실패 (SVG를 사용하되 미지원 시 PNG 사용 (브라우저 플러그인을 통해 MathML 활성화 가능): "https://wikimedia.org/api/rest_v1/" 서버에서 잘못된 응답 ('Math extension cannot connect to Restbase.'):): {\displaystyle M_r=0} , then for 구문 분석 실패 (SVG를 사용하되 미지원 시 PNG 사용 (브라우저 플러그인을 통해 MathML 활성화 가능): "https://wikimedia.org/api/rest_v1/" 서버에서 잘못된 응답 ('Math extension cannot connect to Restbase.'):): {\displaystyle s>r} sth row 구문 분석 실패 (SVG를 사용하되 미지원 시 PNG 사용 (브라우저 플러그인을 통해 MathML 활성화 가능): "https://wikimedia.org/api/rest_v1/" 서버에서 잘못된 응답 ('Math extension cannot connect to Restbase.'):): {\displaystyle M_s = 0}
  - suppose 구문 분석 실패 (SVG를 사용하되 미지원 시 PNG 사용 (브라우저 플러그인을 통해 MathML 활성화 가능): "https://wikimedia.org/api/rest_v1/" 서버에서 잘못된 응답 ('Math extension cannot connect to Restbase.'):): {\displaystyle a_{rj(s)}} is the leading coeffcient of rth row, then for s>r, 구문 분석 실패 (SVG를 사용하되 미지원 시 PNG 사용 (브라우저 플러그인을 통해 MathML 활성화 가능): "https://wikimedia.org/api/rest_v1/" 서버에서 잘못된 응답 ('Math extension cannot connect to Restbase.'):): {\displaystyle M_s=0} or 구문 분석 실패 (SVG를 사용하되 미지원 시 PNG 사용 (브라우저 플러그인을 통해 MathML 활성화 가능): "https://wikimedia.org/api/rest_v1/" 서버에서 잘못된 응답 ('Math extension cannot connect to Restbase.'):): {\displaystyle j(s)>j(r)}
- Reduced Row-echelon form (기약 행 사다리꼴 행렬) - A row-echelon form A is the reduced row echlon form i
  - for leading coefficient 구문 분석 실패 (SVG를 사용하되 미지원 시 PNG 사용 (브라우저 플러그인을 통해 MathML 활성화 가능): "https://wikimedia.org/api/rest_v1/" 서버에서 잘못된 응답 ('Math extension cannot connect to Restbase.'):): {\displaystyle a_{r J(r)}} , (r=1, ... k), 구문 분석 실패 (SVG를 사용하되 미지원 시 PNG 사용 (브라우저 플러그인을 통해 MathML 활성화 가능): "https://wikimedia.org/api/rest_v1/" 서버에서 잘못된 응답 ('Math extension cannot connect to Restbase.'):): {\displaystyle j(1)<j(2)<\cdots<j(k)} - for each 구문 분석 실패 (SVG를 사용하되 미지원 시 PNG 사용 (브라우저 플러그인을 통해 MathML 활성화 가능): "https://wikimedia.org/api/rest_v1/" 서버에서 잘못된 응답 ('Math extension cannot connect to Restbase.'):): {\displaystyle j\leq j(k)} 구문 분석 실패 (SVG를 사용하되 미지원 시 PNG 사용 (브라우저 플러그인을 통해 MathML 활성화 가능): "https://wikimedia.org/api/rest_v1/" 서버에서 잘못된 응답 ('Math extension cannot connect to Restbase.'):): {\displaystyle 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.

구문 분석 실패 (SVG를 사용하되 미지원 시 PNG 사용 (브라우저 플러그인을 통해 MathML 활성화 가능): "https://wikimedia.org/api/rest_v1/" 서버에서 잘못된 응답 ('Math extension cannot connect to Restbase.'):): {\displaystyle \begin{cases} x & + & y & + & 2z &= & 9 \\ 2x & + & 4y & - & 3z &= & 1 \\ 3x & + & 6y & - & 5z &= & 0 \end{cases} }

Express system of linear equation as augmented matrix

구문 분석 실패 (SVG를 사용하되 미지원 시 PNG 사용 (브라우저 플러그인을 통해 MathML 활성화 가능): "https://wikimedia.org/api/rest_v1/" 서버에서 잘못된 응답 ('Math extension cannot connect to Restbase.'):): {\displaystyle \begin{pmatrix} 1 & 1 & 2 & 9 \\ 2 & 4& -3 & 1 \\ 3 & 6& -5 & 0 \end{pmatrix}}

구문 분석 실패 (SVG를 사용하되 미지원 시 PNG 사용 (브라우저 플러그인을 통해 MathML 활성화 가능): "https://wikimedia.org/api/rest_v1/" 서버에서 잘못된 응답 ('Math extension cannot connect to Restbase.'):): {\displaystyle M_2 \leftarrow M_2 - 2\times M_1}

구문 분석 실패 (SVG를 사용하되 미지원 시 PNG 사용 (브라우저 플러그인을 통해 MathML 활성화 가능): "https://wikimedia.org/api/rest_v1/" 서버에서 잘못된 응답 ('Math extension cannot connect to Restbase.'):): {\displaystyle \begin{pmatrix} 1 & 1 & 2 & 9 \\ 0 & 2& -7 & -17 \\ 3 & 6& -5 & 0 \end{pmatrix}}

구문 분석 실패 (SVG를 사용하되 미지원 시 PNG 사용 (브라우저 플러그인을 통해 MathML 활성화 가능): "https://wikimedia.org/api/rest_v1/" 서버에서 잘못된 응답 ('Math extension cannot connect to Restbase.'):): {\displaystyle M_3 \leftarrow M_3 - 3\times M_1}

구문 분석 실패 (SVG를 사용하되 미지원 시 PNG 사용 (브라우저 플러그인을 통해 MathML 활성화 가능): "https://wikimedia.org/api/rest_v1/" 서버에서 잘못된 응답 ('Math extension cannot connect to Restbase.'):): {\displaystyle \begin{pmatrix} 1 & 1 & 2 & 9 \\ 0 & 2& -7 & -17 \\ 0 & 3& -11 & -27 \end{pmatrix}}

구문 분석 실패 (SVG를 사용하되 미지원 시 PNG 사용 (브라우저 플러그인을 통해 MathML 활성화 가능): "https://wikimedia.org/api/rest_v1/" 서버에서 잘못된 응답 ('Math extension cannot connect to Restbase.'):): {\displaystyle M_2 \leftarrow M_2 \times 1/2 }

구문 분석 실패 (SVG를 사용하되 미지원 시 PNG 사용 (브라우저 플러그인을 통해 MathML 활성화 가능): "https://wikimedia.org/api/rest_v1/" 서버에서 잘못된 응답 ('Math extension cannot connect to Restbase.'):): {\displaystyle \begin{pmatrix} 1 & 1 & 2 & 9 \\ 0 & 1& -7/2 & -17/2 \\ 0 & 3& -11 & -27 \end{pmatrix}}

구문 분석 실패 (SVG를 사용하되 미지원 시 PNG 사용 (브라우저 플러그인을 통해 MathML 활성화 가능): "https://wikimedia.org/api/rest_v1/" 서버에서 잘못된 응답 ('Math extension cannot connect to Restbase.'):): {\displaystyle M_3 \leftarrow M_3 - M_2 \times 3 }

구문 분석 실패 (SVG를 사용하되 미지원 시 PNG 사용 (브라우저 플러그인을 통해 MathML 활성화 가능): "https://wikimedia.org/api/rest_v1/" 서버에서 잘못된 응답 ('Math extension cannot connect to Restbase.'):): {\displaystyle \begin{pmatrix} 1 & 1 & 2 & 9 \\ 0 & 1& -7/2 & -17/2 \\ 0 & 0& -1/2 & -3/2 \end{pmatrix}}

구문 분석 실패 (SVG를 사용하되 미지원 시 PNG 사용 (브라우저 플러그인을 통해 MathML 활성화 가능): "https://wikimedia.org/api/rest_v1/" 서버에서 잘못된 응답 ('Math extension cannot connect to Restbase.'):): {\displaystyle -1/2 z = -3/2 \rightarrow z=3}
구문 분석 실패 (SVG를 사용하되 미지원 시 PNG 사용 (브라우저 플러그인을 통해 MathML 활성화 가능): "https://wikimedia.org/api/rest_v1/" 서버에서 잘못된 응답 ('Math extension cannot connect to Restbase.'):): {\displaystyle y-7/2z = y-21/2 = -17/2 \rightarrow y=2} (Back Substitution)
구문 분석 실패 (SVG를 사용하되 미지원 시 PNG 사용 (브라우저 플러그인을 통해 MathML 활성화 가능): "https://wikimedia.org/api/rest_v1/" 서버에서 잘못된 응답 ('Math extension cannot connect to Restbase.'):): {\displaystyle x+y+2z= x+8 =9 \rightarrow x=1} (Back Substitution)

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

구문 분석 실패 (SVG를 사용하되 미지원 시 PNG 사용 (브라우저 플러그인을 통해 MathML 활성화 가능): "https://wikimedia.org/api/rest_v1/" 서버에서 잘못된 응답 ('Math extension cannot connect to Restbase.'):): {\displaystyle \begin{cases} x & + & y & + & 2z &= & 9 \\ 2x & + & 4y & - & 3z &= & 1 \\ 3x & + & 6y & - & 5z &= & 0 \end{cases} }

Express system of linear equation as augmented matrix

구문 분석 실패 (SVG를 사용하되 미지원 시 PNG 사용 (브라우저 플러그인을 통해 MathML 활성화 가능): "https://wikimedia.org/api/rest_v1/" 서버에서 잘못된 응답 ('Math extension cannot connect to Restbase.'):): {\displaystyle \begin{pmatrix} 1 & 1 & 2 & 9 \\ 2 & 4& -3 & 1 \\ 3 & 6& -5 & 0 \end{pmatrix}}

구문 분석 실패 (SVG를 사용하되 미지원 시 PNG 사용 (브라우저 플러그인을 통해 MathML 활성화 가능): "https://wikimedia.org/api/rest_v1/" 서버에서 잘못된 응답 ('Math extension cannot connect to Restbase.'):): {\displaystyle M_2 \leftarrow M_2 - 2\times M_1}

구문 분석 실패 (SVG를 사용하되 미지원 시 PNG 사용 (브라우저 플러그인을 통해 MathML 활성화 가능): "https://wikimedia.org/api/rest_v1/" 서버에서 잘못된 응답 ('Math extension cannot connect to Restbase.'):): {\displaystyle \begin{pmatrix} 1 & 1 & 2 & 9 \\ 0 & 2& -7 & -17 \\ 3 & 6& -5 & 0 \end{pmatrix}}

구문 분석 실패 (SVG를 사용하되 미지원 시 PNG 사용 (브라우저 플러그인을 통해 MathML 활성화 가능): "https://wikimedia.org/api/rest_v1/" 서버에서 잘못된 응답 ('Math extension cannot connect to Restbase.'):): {\displaystyle M_3 \leftarrow M_3 - 3\times M_1}

구문 분석 실패 (SVG를 사용하되 미지원 시 PNG 사용 (브라우저 플러그인을 통해 MathML 활성화 가능): "https://wikimedia.org/api/rest_v1/" 서버에서 잘못된 응답 ('Math extension cannot connect to Restbase.'):): {\displaystyle \begin{pmatrix} 1 & 1 & 2 & 9 \\ 0 & 2& -7 & -17 \\ 0 & 3& -11 & -27 \end{pmatrix}}

구문 분석 실패 (SVG를 사용하되 미지원 시 PNG 사용 (브라우저 플러그인을 통해 MathML 활성화 가능): "https://wikimedia.org/api/rest_v1/" 서버에서 잘못된 응답 ('Math extension cannot connect to Restbase.'):): {\displaystyle M_2 \leftarrow M_2 \times 1/2 }

구문 분석 실패 (SVG를 사용하되 미지원 시 PNG 사용 (브라우저 플러그인을 통해 MathML 활성화 가능): "https://wikimedia.org/api/rest_v1/" 서버에서 잘못된 응답 ('Math extension cannot connect to Restbase.'):): {\displaystyle \begin{pmatrix} 1 & 1 & 2 & 9 \\ 0 & 1& -7/2 & -17/2 \\ 0 & 3& -11 & -27 \end{pmatrix}}

구문 분석 실패 (SVG를 사용하되 미지원 시 PNG 사용 (브라우저 플러그인을 통해 MathML 활성화 가능): "https://wikimedia.org/api/rest_v1/" 서버에서 잘못된 응답 ('Math extension cannot connect to Restbase.'):): {\displaystyle M_3 \leftarrow M_3 - M_2 \times 3 }

구문 분석 실패 (SVG를 사용하되 미지원 시 PNG 사용 (브라우저 플러그인을 통해 MathML 활성화 가능): "https://wikimedia.org/api/rest_v1/" 서버에서 잘못된 응답 ('Math extension cannot connect to Restbase.'):): {\displaystyle \begin{pmatrix} 1 & 1 & 2 & 9 \\ 0 & 1& -7/2 & -17/2 \\ 0 & 0& -1/2 & -3/2 \end{pmatrix}}

구문 분석 실패 (SVG를 사용하되 미지원 시 PNG 사용 (브라우저 플러그인을 통해 MathML 활성화 가능): "https://wikimedia.org/api/rest_v1/" 서버에서 잘못된 응답 ('Math extension cannot connect to Restbase.'):): {\displaystyle M_3 \leftarrow M_3 \times -2 }

구문 분석 실패 (SVG를 사용하되 미지원 시 PNG 사용 (브라우저 플러그인을 통해 MathML 활성화 가능): "https://wikimedia.org/api/rest_v1/" 서버에서 잘못된 응답 ('Math extension cannot connect to Restbase.'):): {\displaystyle \begin{pmatrix} 1 & 1 & 2 & 9 \\ 0 & 1& -7/2 & -17/2 \\ 0 & 0& 1 & 3 \end{pmatrix}}

구문 분석 실패 (SVG를 사용하되 미지원 시 PNG 사용 (브라우저 플러그인을 통해 MathML 활성화 가능): "https://wikimedia.org/api/rest_v1/" 서버에서 잘못된 응답 ('Math extension cannot connect to Restbase.'):): {\displaystyle M_1 \leftarrow M_1+M_2 \times -1 }

구문 분석 실패 (SVG를 사용하되 미지원 시 PNG 사용 (브라우저 플러그인을 통해 MathML 활성화 가능): "https://wikimedia.org/api/rest_v1/" 서버에서 잘못된 응답 ('Math extension cannot connect to Restbase.'):): {\displaystyle \begin{pmatrix} 1 & 0 & 11/2 & 35/2 \\ 0 & 1& -7/2 & -17/2 \\ 0 & 0& 1 & 3 \end{pmatrix}}

구문 분석 실패 (SVG를 사용하되 미지원 시 PNG 사용 (브라우저 플러그인을 통해 MathML 활성화 가능): "https://wikimedia.org/api/rest_v1/" 서버에서 잘못된 응답 ('Math extension cannot connect to Restbase.'):): {\displaystyle M_1 \leftarrow M_1+M_3 \times -11/2, M_2 \leftarrow M_2+ M_3 \times 7/2 }

구문 분석 실패 (SVG를 사용하되 미지원 시 PNG 사용 (브라우저 플러그인을 통해 MathML 활성화 가능): "https://wikimedia.org/api/rest_v1/" 서버에서 잘못된 응답 ('Math extension cannot connect to Restbase.'):): {\displaystyle \begin{pmatrix} 1 & 0 & 0 & 1 \\ 0 & 1& 0 & 2 \\ 0 & 0& 1 & 3 \end{pmatrix}}

Example

General Solution
구문 분석 실패 (SVG를 사용하되 미지원 시 PNG 사용 (브라우저 플러그인을 통해 MathML 활성화 가능): "https://wikimedia.org/api/rest_v1/" 서버에서 잘못된 응답 ('Math extension cannot connect to Restbase.'):): {\displaystyle \begin{pmatrix} {a} & {b} \\ {c}& {d} \end{pmatrix} \begin{pmatrix} {x \\ y} \end{pmatrix} = \begin{pmatrix} {m} \\ {n} \end{pmatrix} }

or 구문 분석 실패 (SVG를 사용하되 미지원 시 PNG 사용 (브라우저 플러그인을 통해 MathML 활성화 가능): "https://wikimedia.org/api/rest_v1/" 서버에서 잘못된 응답 ('Math extension cannot connect to Restbase.'):): {\displaystyle \begin{pmatrix} {a} & {b} & {|} & {m} \\ {c} & {d} & {|} & {n} \end{pmatrix} } (구문 분석 실패 (SVG를 사용하되 미지원 시 PNG 사용 (브라우저 플러그인을 통해 MathML 활성화 가능): "https://wikimedia.org/api/rest_v1/" 서버에서 잘못된 응답 ('Math extension cannot connect to Restbase.'):): {\displaystyle ad-bc \neq 0 } )

has a unique pair of solution 구문 분석 실패 (SVG를 사용하되 미지원 시 PNG 사용 (브라우저 플러그인을 통해 MathML 활성화 가능): "https://wikimedia.org/api/rest_v1/" 서버에서 잘못된 응답 ('Math extension cannot connect to Restbase.'):): {\displaystyle \begin{pmatrix} x \\ y \end{pmatrix} = \frac{1}{ad-bc} \begin{pmatrix} {dm-bn} \\ {-cm+ an} \end{pmatrix} }

Sources

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

각주

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

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

[1]