[LA] Gauss-Jordan Elimination

System of linear equations (연립방정식)의 solution를 구하는 가장 표준적인 방법.
Gauss Elimination을 좀더 보강한 방법
(컴퓨터 없이 연립일차방정식 계산할 경우 가장 일반적으로 사용됨)

• System의 Augmented Matrix에 Elementary Row Operations을 적용하여 Row Reduction(=행소거, 또는 Elimination으로 볼 수 있음)을 수행.
• Row reduction에 의해 Augmented Matrix는 Row Echelon Form (REF)이 됨. (← forward phase종료)
• 이 REF를 backward phase를 수행하여 Reduced Row Echelon Form(RREF)으로 변경하여 solution을 구함.

---

Row Echelon Form

$$\begin{bmatrix}
\blacksquare & * & * & * \\
0 & \blacksquare & * & * \\
0 & 0 & 0 &0
\end{bmatrix}$$

• $\blacksquare$ is a leading entry. (pivot position)
• 1,2 column이 바로 pivot column임.

Reduced Row Echelon Form

$$\begin{bmatrix}
\blacksquare & 0 & * & * \\
0 & \blacksquare & * & * \\
0 & 0 & 0 &0
\end{bmatrix}$$

• $\blacksquare$ is a leading entry. (pivot position)
• 1,2 column이 바로 pivot column임.

---

Example

아래와 같은 augmented matrix가 있다고 하자. 여기에 Gauss-Jordan Elmination Method를 적용하라.

$$\begin{bmatrix}
0 & 2 & 1 \\
1 & 1 & 2 \\
2 & 1 & 1
\end{bmatrix} \begin{bmatrix} x_1 \\ x_2 \\ x_3 \end{bmatrix} = \begin{bmatrix} 4 \\ 6 \\ 7 \end{bmatrix}
\rightarrow
\begin{bmatrix}
0 & 2 & 1 & 4 \\
1 & 1 & 2 & 6 \\
2 & 1 & 1 &7
\end{bmatrix}$$

Solution

1. interchange 수행 ($\text{row}_1$과 $\text{row}_3$를 교체)

$$\begin{bmatrix}
2 & 1 & 1 &7 \\
1 & 1 & 2 & 6 \\
0 & 2 & 1 & 4
\end{bmatrix}$$

2. replacement 수행 ($\text{row}_2= \text{row}_2-\frac{1}{2}\text{row}_1$)

$$\begin{bmatrix}
2 & 1 & 1 &7 \\
0 & 1/2 & 3/2 & 5/2 \\
0 & 2 & 1 & 4
\end{bmatrix}$$

3. 편의를 위해 scaling 수행 ($\text{row}_2= 2\text{row}_2$)

$$\begin{bmatrix}
2 & 1 & 1 &7 \\
0 & 1 & 3 & 5 \\
0 & 2 & 1 & 4
\end{bmatrix}$$

4. replacement 수행 ($\text{row}_3= \text{row}_3 -2\text{row}_2$)

$$\begin{bmatrix}
2 & 1 & 1 &7 \\
0 & 1 & 3 & 5 \\
0 & 0 & -5 & -6
\end{bmatrix}$$

5. backworad pahse 시작 : replacement 수행 ($\text{row}_2= \text{row}_2 +\frac{3}{5}\text{row}_3$)

$$\begin{bmatrix}
2 & 1 & 1 &7 \\
0 & 1 & 0 & 7/5 \\
0 & 0 & -5 & -6
\end{bmatrix}$$

6. replacement 수행 ($\text{row}_1= \text{row}_1 +\frac{1}{5}\text{row}_3$)

$$\begin{bmatrix}
2 & 1 & 0 & 29/5 \\
0 & 1 & 0 & 7/5 \\
0 & 0 & -5 & -6
\end{bmatrix}$$

7. replacement 수행 ($\text{row}_1= \text{row}_1 -\text{row}_2$)

$$\begin{bmatrix}
2 & 0 & 0 & 22/5 \\
0 & 1 & 0 & 7/5 \\
0 & 0 & -5 & -6
\end{bmatrix}$$

8. scaling 수행 ($\text{row}_1= \frac{1}{2}\text{row}_1$)

$$\begin{bmatrix}
1 & 0 & 0 & 11/5 \\
0 & 1 & 0 & 7/5 \\
0 & 0 & -5 & -6
\end{bmatrix}$$

9. scaling 수행 ($\text{row}_3= \frac{-1}{5}\text{row}_3$)

$$\begin{bmatrix}
1 & 0 & 0 & 11/5 \\
0 & 1 & 0 & 7/5 \\
0 & 0 & 1 & 6/5
\end{bmatrix}$$

위에서 구한 matrix는 RREF이며, 쉽게 solution을 구할 수 있음.
$$
x_1 = 11/5, x_2=7/5, x_3=6/5 \blacksquare
$$

---

Gauss-Jordan Elimination Method의 사용처

1. Solution 구하기.
2. inverse matrix구하기.
   Gauss-Jordan Elimination Method를 통해 solution 구할 수 있다는 애기는 coefficient matrix의 inverse를 구하는데에도 사용가능하다는 것을 의미한다.
3. rank계산 및 linear indepedent한 row vector 구하기
   all-zero row의 경우 linearly dependent하므로 coefficient matrix의 rank 를 계산하는데 이용가능함.

---

추가로,

• REF를 구한 이후, Back substituion (후진 대입법)을 통해 해를 구하는 것이 Gauss Elimination Method (위의 예제에서 step4까지)이고,
• RREF까지 구하여 해를 구할 경우 Gauss-Jordan Elimination Method라고 함.
• REF는 element row operation들을 어떤 순서로 적용하느냐에 따라 다르므로 유일하게 결정되지 않으나, RREF는 유일(unique)하다. 때문에 library들에서 RREF는 함수로 제공되지만, REF는 아니다.
• 굳이 REF를 얻고 싶다면, LU decomposition 등으로 구할 수는 있음 (REF는 unique하진 않음을 명심.).

2022.09.02 - [Linear Algebra] - [LA] sympy로 Reduced Row Echelon Matrix 구하기.

[LA] sympy로 Reduced Row Echelon Matrix 구하기.

 

참고로, Gauss Elimination은 B.C. 250년 당시 중국에서 사용되었고, 서구권에서는 19세기의 Gauss에 의해 사용되기 시작했다고 한다.

---

 

같이 보면 좋은 URLs

https://angeloyeo.github.io/2019/09/09/Gauss_Jordan.html

가우스-조던 행렬 소거법의 기하학적 의미 - 공돌이의 수학정리노트 (Angelo's Math Notes)