How to solve linear system

1차 연립방정식을 풀기 위한 일종의 알고리듬이다.
흔히 아는 연립방정식의 형태를 행렬식으로 표시해보자.

$A x = b$

$A \in {\mathbb R}^{m \times n}$ , $b \in {\mathbb R}^{m \times 1}$
이때 $b$ 를 계수 행렬 $A$ 의 한 열로 편입한 형태를 augmented form이라고 부른다. 즉,

$\begin{bmatrix} A ~\vert ~ b \end{bmatrix} \in {\mathbb R}^{m \times (n +1)}$

해가 존재하면 일치성이 있다고 말하고 해가 존재하지 않으면 일치성이 없다고 말한다.

Row Echelon Form Matrix (REF)

‘열 사다리꼴’ 행렬이라고 부른다. 정의는 다음과 같다 .
각 행에 0이 아닌 첫번째 원소를 “선행 원소” 혹은 피벗이라고 부른다.
- 선행원소 1을 조건으로 두는 경우가 있다. 이는 행 내에서 스케일링의 문제이므로 큰 문제는 아니다.
컬럼에서 각 선행원소는 앞선 행의 선행 원소보다 오른편에 위치해야 한다.
모든 행이 0인 행은 0이 아닌 행을 포함한 행보다 뒤쪽에 위치해야 한다.

Reduced Row Echelon Form Matrix (RREF)

RREF가 되기 위한 조건은 다음과 같다.
- REF다.
- 각 행의 선행 원소는 해당 열에서 유일한 0이 아닌 원소다.
아래의 예를 확인하자.

$\begin{bmatrix} 1 & \ast & \ast & \ast & \ast & \ast & \ast & \ast & \ast \\ 0 & 1 & \ast & \ast & \ast & \ast & \ast & \ast & \ast \\ 0 & 0 & 0 & 1 & \ast & \ast & \ast & \ast & \ast \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & \ast & \ast \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & \ast \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \end{bmatrix}$

Matrix Operation

연립방정식을 구하는 과정으로 여기면 쉽게 이해할 수 있다.
- 연립방정식이 주어졌을 때 해당 식의 순서를 바꾼다고 문제가 되지 않는다.
- 같은 행에서 일정한 수를 곱해도 무방하다 .
- 한 행을 상수배 하여 다른 행에 더한다.

사실 우리가 중고등학교 때 배워왔던 방정식의 해를 구하는 알고리듬 그대로다.

Solution

이렇게 구했을 때 RREF 행렬의 선행 원소, 즉 피벗은 그대로 맨 왼쪽 열의 가산된 항목을 해를 지닌다.
- 열로 생각해보자. RREF에서 피벗 열은 1인 한 개를 제외하면 모두 0이다. 따라서 해를 그대로 가중치로 지니게 된다.
피벗이 아닌 경우는 어떤 값이 와도 상관 없다.

Inverse Matrix

가우스-조르단 방법으로 역 행렬도 구할 수 있다.
앞서 매트릭스 연산을 행렬로 나타낸 행렬을 기본 행렬(elementary matrix)라고 한다.

$AX = I$

이때 $X = A^{-1}$ 로 둘 수 있다. 식의 양변에 동시에 기본 행렬 연산 $r$ 번을 전개한다고 하자.

$\underbrace{E_r E_{r-1} \dotsb E_1}_{(*)} A X = E_r E_{r-1} \dotsb E_1 I$

이때 이 연산의 결과 식의 좌변이 $IX$ 로 바뀐다고 하자. 이는 다시 아래와 같다.

$E_r E_{r-1} \dotsb E_1 A X = E_r E_{r-1} \dotsb E_1 I = IX$

$X = E_r E_{r-1} \dotsb E_1$ 이 되고, 이것이 곧 역행렬이다.

Reference

https://en.wikipedia.org/wiki/Gaussian_elimination

🏠lostineconomics.com | Jun Sok Huhh