선형연립방정식
선형연립방정식이란?
일반적으로, 미지수 x1, x2, ..., xn에 관한 유한개의 선형방정식의 모임
만일 상수항이 모두 0이면 이 선형연립방정식(system of linear equations)을 동차선형연립방정식(homogeneous system of linear equations)이라 한다.
선형연립방정식의 해
선형연립방정식의 미지수에 x1, x2, ..., xn에 어떤 수를 각각 대입하였을 때, 각 방정식이 모두 성립하면 (s1, s2, ..., sn)을 이 선형연립방정식의 해(solution)라고 한다.
일반적으로 선형연립방정식의 해가 존재하는 경우를 consistnet(일관된)한 연립방정식이라고 하고, 해가 존재하지 않는 연립방정식은 inconsistent한 연립방정식이라 한다.
선형연립방정식의 조건
일반적으로, 주어진 선형연립방정식은 다음 중 하나만을 만족한다.
- 유일한 해를 갖는다.
- 무수히 많은 해를 갖는다.
- 해를 갖지 않는다. (inconsistent한 선형연립방적식)
선형연립방정식은 왜 위의 조건 중 하나만 만족할까? 같은 해가 2-3개의 방정식을 충족하는 경우는 없는가?
선형방정식은 기하적으로 보면 직선/평면/초평면이기 때문에. 직선 두개의 관계로 생각해 보면 세 가지 경우뿐이다.
- 한 점에서 만남 - 해 1개
- 평행 -> 만나지 않음 -> 해 없음
- 완전히 같은 직선 -> 무한히 많은 교점
만약 2개 이상의 방정식을 충족한다고 하며 그것은 3번과 같은 경우가 되며, 그렇지 않으려면 선형방정식이 아니라 비선형 방정식의 경우가 그럴 수 있다.
계수 행렬(coefficient matrix)
행렬 A를 선형연립방정식의 계수행렬(coefficient matrix)라고 한다.
첨가 행렬(augmented matrix)
sagemath
A = matrix([[1,1,2], [2,4,-3], [3,6,-5]]) #3x3 행렬
b = vector([9, 1, 0]) #상수항 벡터
print( A.augment(b) ) #첨가행렬
[ 1 1 2 9]
[ 2 4 -3 1]
[ 3 6 -5 0]Gauss 소거법과 Gauss-Jordan 소거법
(소거법을 이용한 선형연립방정식 풀이)
기본행 연산
1) 두 식을 교환한다.
2) 한 식에 0이 아닌 실수를 곱한다.
3) 한 식에 0이 아닌 실수배를 하여 다른 식에 더한다.
이를 기본행 연산(ERO, Elementary Row Operations) 이라 한다.
1) 의 예
행 사다리꼴(REF)
REF는 행렬이 계단 모양이 된 상태로 m x n 행렬 E가 다음 3가지 성질을 만족할 때, 행 사다리꼴(row echelon form, REF)이라고 한다.
1) 성분이 모두 0인 행이 존재하면 그 행은 행렬의 맨 아래에 위치한다.
2) 각 행에서 처음으로 나타나는 0이 아닌 성분은 1이다. 이 때 이 1을 그 행의 선행 성분(leading entry, leading 1)이라고 한다.
3) i행과 (i+1)행 모두에 선행성분이 존재하면 (i+1)행의 선행성분은 i행의 선행성분보다 오른쪽에 위치한다.
간단버전:
- 0이 아닌 행이 위에 있음
- 각 행의 leading entry가 오른쪽으로 이동
- pivot 아래는 0
이 모습이 계단처럼 생겼기 때문에 echelon이라고 한다.
예)
REF가 되면 좋은 이유
뒤에서 부터 해를 구할 수 있음 (back substitution)
그러나 REF는 한 개가 아니고 여러개이다. 그래서 RREF가 등장.
기약 행 사다리꼴(RREF)
위의 3가지 조건을 만족하고 다음의 조건)까지 만족하면 RREF
4) 선행성분(Leading entry in row)을 포함하는 열의 선행성분 외의 성분은 모두 0이다.
간단버전:
- REF 조건 만족
- pivot = 1
- pivot 위아래가 모두 0
예) 
RREF가 중요한 이유
- RREF는 항상 유일
- 어떤 방법으로 소거해도 같은 RREF가 나온다
- 해의 구조, 자유변수, 랭크(rank)를 한 번에 보여줌
REF/RRFF는 왜 등장했나?
REF(Row Echelon Form) 와 RREF(Reduced Row Echelon Form) 은 단순히 계산 규칙이 아니라, 선형연립방정식의 구조를 드러내기 위해 등장한 형태이다.
핵심은 방정식을 단계적으로 단순한 형태로 바꾸면 해의 구조가 보인다 는 것.
연립방정식의 형태로는 아래를 잘 알 수가 없다.
- 어떤 변수가 자유변수인지
- 해가 하나인지
- 무한히 많은지
그렇기 때문에 소거법을 사용하여 REF, RREF로 만든다.
REF는 계산을 쉽게 하기 위해서이고, RREF는 해의 구조를 완전히 드러내기 위함이다.
- REF의 경우 소거법에 따라 여러 형태가 존재하기 때문에 특징을 찾아내거나 비교를 하기 위해서는 표준화된 구조가 필요하다. 그렇기 때문에 RREF가 필요.
REF/RREF sagemath
계수행렬 A, 의 RREF를 구하는 예제.
A = matrix([[1,1,1,4,4],
[2,3,4,9,16],
[-2,0,3,-7,11]])
print( "A=" )
print(A)
print()
print( "RREF(A) = " )
print( A.rref() )
Share
A=
[ 1 1 1 4 4]
[ 2 3 4 9 16]
[-2 0 3 -7 11]
RREF(A) =
[ 1 0 0 2 -1]
[ 0 1 0 3 2]
[ 0 0 1 -1 3]Gauss 소거법과 Gauss-Jordan 소거법
선형연립방정식을 첨가행렬로 표현했을 때 행동치, 즉 두 행렬이 행 연산(row operations)으로 서로 변환 가능하면** 두 선형연립방정식은 동치이다. (즉, 해집합이 같다)
Gauss 소거법: 선형연립방정식의 첨가행렬을 REF로 변형하여 푸는 방법
Gauss-Jordan 소거법: 선형연립방정식의 첨가행렬을 RREF로 변형하여 푸는 방법
sagematgh 예제
Gauss-Jordan 소거법을 이용하여 연립방정식의 해를 구하여라.
2x + 4y + 6z = 18
2x - y + x = 8
3x - z = 3
A = matrix([[2,4,6],
[2,-1,1],
[3,0,-1]])
b = vector([18,8,3])
print( "A:b" )
print(A.augment(b))
print()
print( "RREF(A:b) = " )
print( A.augment(b).rref() ) # 행렬 A와 벡터 b의 첨가행렬의 RREF 구하기
print()
print( "x= ",A.solve_right(b) ) # .solve_right()를 이용하여 구할 수도 있음
A:b
[ 2 4 6 18]
[ 2 -1 1 8]
[ 3 0 -1 3]
RREF(A:b) =
[ 1 0 0 2]
[ 0 1 0 -1]
[ 0 0 1 3]
x= (2, -1, 3)sagemath에서 상수항은 왜 벡터인가?
연립방정식은 각 방정식이 변수벡터와 계수벡터의 내적이기 때문에
전체 시스템을 행렬 × 벡터 형태 Ax=b 로 표현
SageMath에서도 상수항을 vector로 표현
sagemath 예제 2
A = matrix([[1,-2,1],
[2,-2,1],
[3,1,-5],
[0,-1,2],
[-6,0,7]])
b = vector([7,5,0,-4,-10])
A.augment(b).rref()
[1 0 0 0]
[0 1 0 0]
[0 0 1 0]
[0 0 0 1]
[0 0 0 0]해가 없는 경우에는
위의 예제 처럼 [0, 0, 0 | 0이 아닌 상수] 의 형태를 보인다.
만약 solve_right()을 쓰면,
ValueError: matrix equation has no solutions
라는 에러를 출력함
sagemath 예제 3
A = matrix([[1,3,-2,0,2,0],
[2,6,-5,-2,4,-3],
[0,0,5,10,0,15],
[2,6,0,8,4,18]])
b = vector([0,-1,5,6])
print( "[A:b] =" )
print(A.augment(b))
print()
print( "RREF([A:b])=" )
print( A.augment(b).rref() )
print()
print("x= ", A.solve_right(b))
[A:b] =
[ 1 3 -2 0 2 0 0]
[ 2 6 -5 -2 4 -3 -1]
[ 0 0 5 10 0 15 5]
[ 2 6 0 8 4 18 6]
RREF([A:b])=
[ 1 3 0 4 2 0 0]
[ 0 0 1 2 0 0 0]
[ 0 0 0 0 0 1 1/3]
[ 0 0 0 0 0 0 0]
x= (0, 0, 0, 0, 0, 1/3)x는 하나의 해이다. RREF의 마지막 행이 영이면 무수히 많은 해가 존재한다.
무수히 많은 해를 갖는 선형연립방정식인 경우에 A.solve_right(b) 명령어는 모든 자유변수에 0을 대입한 해를 찾아준다.
자유변수 찾기:
1. 기본변수 (pivot 을 찾는다)
1행 -> 처음에 1이 있으므로 x1
2행 -> 3번째가 1이므로 x3
3행 -> 6번째가 1이므로 x6
pivot이 있는 변후 x1, x3, x6 => 기본 변수
- pivot이 없는 열이 자유변수
2열 -> x2
4열 -> x4
5열 -> x5
