[전산수학I] Solving Systems of Linear Equation

1.1 Systems of Linear Equation

1) Linear Equation

${x}_1, ... {x}_n 은 변수이고 {a}_1, ... {a}_n 이 실수일 때$ linear equation 은 다음과 같이 표현할 수 있다.

$${a}_1{x}_1 + {a}_1{x}_1 + \cdots + {a}_n{x}_n = {b}$$

 

2) Solution / Solution Set

Solution: 연립 방정식에 속한 모든 식을 만족하는 해 => 1개 

Solution Set: Solution 들의 집합 = 해들의 집합 => 여러개

 

Linear Equation 은 3가지 형태의 Solution 을 갖는다.

1. 단 한 개의 해   2. 해 없음   3. 무수히 많음 

 

 

 

 

3) Matrix

1. 표기법

$$A \in \mathbb{R}^{n * m}$$ 

위와 같이 정의했을 때 n by m 행렬 혹은 n행 m열인 행렬 이라고 부른다.

 

2.  Coefficient / Augmented Matrix

Coefficient Matrix : 변수를 제외한 계수 「Coefficient」 만을 나타낸 행렬

Augmented Matrix : Coefficient Matrix 오른쪽에 결과 값까지 나타낸 행

 

1.2 Row Reduction and Echelon Forms

1) Elementary Row Operations

1. Replacement    ex) R1 -> R1 + 2R2

2. Interchange      ex) R1<->R2

3. Scaling              ex) kA

 

기본 행 연산을 통해 만들 수 있는 모든 행렬은 row evqivalent 즉 the same solution set 을 의미한다.

2) Nonzero / Leading entry / Pivot position

Nonzero : 전부 0이 아닌 행 또는 열

 = contains at least one nonzero entry

 

leading entry : nonzero row에서의 의미는 0이 아닌 값 중 가장 왼쪽의 값 

= leftmost nonzero entry in a nonezero row

 

Pivot position : 각 행의 leading entry의 위치

-> 보통 EF에서 확인합니다.

3) EF, REF

사다리꼴 행렬「EF」 의 조건

1. 모든 Nonzero row들이 0들 보다 위에 있어야 한다.

2. 각 행의 leading entry가 행이 증가할 수록 더 오른쪽에 존재해야 한다.

3. 각 열에서 leading entry보다 아래 있는 값들은 전부 0 이여야 한다. 

ㄴ> Not Unique

 

감소된 사다리꼴 행렬「REF」 의 조건

1. EF에 속한다.

2. nonzero row의 leading entry 값은 1이다.

3. 각 열의 leading entry에 대하여 그 위와 아래는 모두 0이다. 

 

4) Existence and Uniqueness

Existence 조건 

A linear system is consistent if and only if the rightmost column of the augmented matrix is not a pivot position.

"해가 존재한다" 는 말은 "가장 오른쪽 열이 pivot position이 아니다" 라는 말과 같다.

$$[0,0, ... , 0, {b}], {b} ≠ 0$$

 

Uniqueness 조건

Free variables이 적어도 1개 이상 존재할 경우 해당 식은 매개 변수로 나타낼 수 있으며 이 때 선형방정식은 Unique하지 않다. Free variables이 아닌 변수들은 basic variables이라고 부른다.