[Linalg] 선형시스템 및 가우스소거법 (Numpy Code 추가)

(프로그래머스 2주차 Day1 수업정리)
선형시스템 및 가우스 소거법

기초부터 튼튼히 기초부터 튼튼히

- 중,고등학교때 배웠던 연립방정식이 선형시스템(linear system) 이다.

그런데 , 문제는 변수가 훨씬 더 많이지는 등의 어려운 점이 발생한다면, 중고등학교때 배운 가감법으로는 무리일 것이다.

오늘의 목표

(1) 선형시스템, 즉 Ax = b의 정형적 풀이법을 알아보자.
(2) 가우스 소거법에 대해 알아보자
(3) 이에 대한 코드 구현법을 알아보자.

선형 시스템 -> 행렬 표현

우선 이를  위해서는 일반적인 연립 방정식을 행렬 형태로 표현해야 한다.
이는 다음과 같은 식으로 한다.

 

계수는 계수끼리, 상수는 상수끼리 모아서 행렬로 표현하면 된다.

- 식은 행이다.
- 식이 m개고, 미지수가 n개일 경우
- A : m * n 행렬
- x : 미지수 벡터( n * 1 ) 행렬
- b : 상수항 벡터(m * 1) 행렬

반대로 행렬 -> 선형시스템 형태는 역으로 행렬 곱셈을 하면 된다. Simple?

Tip. 미지수가 헷갈리지 않도록 선형시스템 작성시 같은 미지수별로 줄을 맞춰주자.

해의 다양성

linear system의 해가 있으면 consistent, 없으면 inconsistent라고 한다.
특히, inverse matrix가 없는 경우, singular한 상황이다. (예시, ax = b 에서 a = 0 인 경우)
(정사각 행렬일 경우 singular <=> det(A) = 0)

 

 

Gauss Elimination(가우스 소거법)

Gauss Elimination의 경우는 가감법을 일반화 한 형태로 m * n 선형시스템의 해를 구하는 방법.

가장 중요한 핵심 아이디어는, 주어진 A 행렬을 계단형 형태 matrix로 바꾸게 가감법을 하는 것이다.(사실은, 조금 더 나아가서 reduced row echlon form을 취하게 된다)

행렬를 가감법을 통해 상삼각행렬 형태로 바꿀 경우, 마지막 행부터 올라가면서 해를 순서대로 구하면 답을 얻을 수 있을 것이다. 여기서 사용되는 기본연산은 3가지이다.

- 행의 치환 : 기준행에 상수배를 한 후 가감을 통해 행을 변경
- 행끼리 교환 : 서로 다른 두 행을 바꾼다.
- 행의 스케일링 : 특정 행을 상수배하여 계수 조절.

* Remark.> Reduced row echlon form
이것의 경우는 다음과 같은 형태를 가진다.

각 행이 모두 0이 아닐 경우, 최초로 0이 아닌 값은 1로 고정(선두 계수를 1로 맞춤)
그리고 선두로 나온 1 위의 행의 계수 또한 0으로 맞춰 버리는 형태이다.

 

Rank

행렬의 Rank(Dimension)을 얻기 위해서는 Gauss Elimination을 통해, RREF로 변경 후
0이 아닌 수가 있는 행(열)의 개수가 행렬의 rank가 된다.
(Dimension의 원래 정의는 기저(basis)의 원소의 개수이나, rank의 값과 동일하게 된다)

 

코드 구현

A = N * N 행렬인 경우, 즉 정방 행렬인 경우에 대한 풀이로,
코드는 github 링크로 대체한다.

github.com/SeongwonTak/-KDT-_AI_2_Notes/blob/main/Linalg/0426_Linear_System.ipynb