[선형대수] 2. Solving Systems of Linear Equations(Cont'd)

Nonzero

어떠한 matrix의 nonzero row 또는 nonzero column이란? 0이 아닌 entry를 적어도 하나 포함하는 row 또는 column이다.

Leading entry

어떠한 nonzero row에서, 그것의 leading entry란? 0이 아닌 entry 중 가장 왼쪽에 있는 entry를 의미한다.

Echelon Form(EF)

Echelon Form(사다리꼴)이려면 다음 세 조건을 만족해야 한다.

1. Zero rows(nonzero가 아닌 rows. 모든 entry가 0)는 모두 bottom에 있다. 즉 nonzero rows는 반드시 zero rows의 위에 위치한다.
2. 어떠한 row의 leading entry는, 그 위에 있는 rows의 leading entries보다 오른쪽 column에 있다.
3. 어떠한 leading entry가 위치한 column에서, 그 밑에 있는 entries는 모두 0이다.

Reduced Echelon Form(REF)

Reduced Echelon Form이려면 EF의 세 조건 + 다음 두 조건을 만족해야 한다.

4. Nonzero rows의 leading entries는 모두 1이다.
5. 모든 Leading 1(조건 4에서 말하는 그 1)은 위치한 column에서 유일한 nonzero이다. 그 column에서 나머지 entries는 모두 0이다.

이렇게 되면, augmented matrix에서 variables의 값을 쉽게 알 수 있다. 위의 예시에서는, $x_1 = 5$, $x_2 = -6$, $x_3 = 12$ 라는 것을 쉽게 도출 가능.

Echelon Forms

EF인 matrix를 echelon matrix, REF인 matrix를 reduced echelon matrix라고 한다.

어떠한 nonzero matrix(0이 아닌 entry를 적어도 하나 가지는 matrix)는 3가지 elementary row operations를 통해 EF로 row reduced될 수 있다. 이때 EF는 여러 개일 수 있다.

반면, 어떠한 nonzero matrix에서 얻어지는 REF는 반드시 하나이다(unique). 즉, 어떠한 matrix와 row equivalent한 reduced echelon matrix는 반드시 하나이다.

Matrix A가 echelon matrix U와 row equivalent하다면? U is an echelon form of A.
이때 U가 reduced echelon form이라면? U is the reduced echelon form of A.

Pivot position, Pivot column

어떠한 matrix A와 그것의 reduced echelon form인 U가 있다고 하자.

이때, A의 pivot position이란? U의 leading 1들의 location에 해당하는 위치.
Pivot column이란? Pivot position을 포함하고 있는 columns.

어떠한 matrix A가 주어졌을 때 그것의 pivot positions와 columns를 구하려면? 우선 A를 row reduce한다(EF로 만들기). 그런 다음 leading entries의 위치를 찾으면 된다.

Row Reduction Algorithm

지금까지 REF를 구하는 방식의 시스템적 way이다.

STEP 1:
Leftmost nonzero column에서 시작한다. 걔는 pivot column이 될 것이고, pivot position은 그것의 top에 위치할 것이다.

STEP 2:
만약 그 entry가 zero라면 interchange를 통해 해당 entry를 nonzero로 만들어준다. 이때 어떤 row와 interchange할지는 상관 없으나, 컴퓨터 프로그램의 성능을 위해 partial pivoting으로 결정할 수도 있다. Partial pivoting은, 절댓값이 가장 큰 값을 가지는 row와 interchange한다는 것이다.

STEP 3:
Replacement를 통해 pivot position 밑의 entries를 zero로 만들어준다.

STEP 4:
이렇게 만든 pivot position과 그것이 속한 row & column을 cover한다. 그리고 나머지 submatrix에 대해 STEP 1~3을 iterative하게 적용한다.

STEP 5:
Nonzero row가 더 이상 없거나 only one row만 남는 등 STEP 1~3을 더 이상 적용할 수 없는 경우, 이제 EF는 만들어진 것이고 REF를 만들어야 한다. Rightmost pivot에서 시작해서, 해당 pivot의 값을 1로 만들고(scaling) 그 위아래 entries를 0으로 만들어준다(replacement).

STEP 5까지 끝나면 이제 REF를 얻게 되었다. 이것이 RRA(Row Reduction Algorithm)이다.

STEP 1~4는 forward phase라고 부르며, 끝나면 EF를 얻게 된다.
STEP 5는 backward phase라고 부르며, 끝나면 REF를 얻게 된다.

주어진 augmented matrix에 RRA를 적용하면 해당 linear system의 solution set에 대한 explicit description을 얻을 수 있다.

Basic variable, Free variable

이러한 REF가 나왔다면, solution은 다음과 같다.

$\begin{cases} x_1-5x_3=1 \\ x_2+x_3=4 \\ 0=0 \end{cases}$

즉,

$\begin{cases} x_1=1+5x_3 \\ x_2=4-x_3 \\ x_3=x_3 \end{cases}$

$x_3$를 다양하게 정할 수 있는데 그에 따라, $x_1$과 $x_2$이 정해진다.

이때 $x_1$과 $x_2$는 basic variables이라고 한다.
$x_3$는 free variable이라고 한다.

즉 free variable은 자유롭게 정해질 수 있고, basic variable은 그에 따라 정해지는 것이다.

어떠한 system이 consistent하다면? 그것의 solution set은 free variables에 대한 basic variables의 연립방정식으로 표현될 수 있다.

Parametric description

$\begin{cases} x_1=... \\ x_2=... \\ \end{cases}$
같은 형태로 표현하는 것. 어떠한 system이 consistent하고 free variable이 있다면, 다양한 parametric description이 존재한다. 하지만 일반적으로 basic variables를 free variables에 대해 표현한다.

Existence and Uniqueness Theorem

어떠한 linear system은 다음 조건을 만족할 때만(iff) consistent하다.

• Augmented matrix의 rightmost column은 pivot column이 아니다.

즉, 해당 augmented matrix의 echelon form은 [0, 0, ..., b]와 같은 row를 가지지 않아야 한다(b != 0일 때).
만약 그런 row를 가질 경우, $0x_1+...+0x_n=b$ 를 만족해야 하는데, 이걸 만족하는 해는 없기 때문.

어떤 linear system이 consistent할 경우,

• free variable이 없다면 -> unique solution
• free variable이 있다면 -> infinitely many solutions

Row Reduction to solve a linear system

Linear system을 solve하기 위해 row reduction을 사용하는 과정

1. 해당 system의 augmented matrix를 구한다.
2. Row reduction algorithm을 적용하여 EF를 구하고, system이 consistent한지 판단한다. Not consistent(해가 없음)할 경우 중단한다.
3. REF를 구한다.
4. 그것에 해당하는 연립방정식을 구한다.
5. Parametric description을 구하여 basic variables를 free variables에 대해 표현하여 해를 구한다.