[알고리즘 구현으로 배우는 선형대수] #4. 선형 시스템

---

#4. 선형 시스템 

 

정의

선형 방정식이 다수 존재할 때의 선형 방정식의 집합(=연립1차방정식) 

특징

오직 하나의 해만 갖거나(직선 교차), 무한개의 해를 갖거나 (직선 일치) 해가 존재하지 않음(평행) 

동차 선형 시스템

• 선형 시스템의 우변(b부분)이 모두 0인 선형시스템
• 절편이 없으므로, 모두 원점을 지나는 직선이며 이에 오직 하나의 해만 같거나 무한개의 해를 가진다

첨가행렬 

선형 시스템의 상수부분만 모아서 행렬 형태로 나타낸 것 (우변은 구분 위해 별도 표기하였으며 행렬곱이 아님) 

 

기본행 연산

첨가행렬을 이용하여 기본행 연산을 수행하면 선형시스템의 해를 구할 수 있음 

1. 한 행에 0 이 아닌 상수를 곱한다 (b에 해당하는 행까지 모두)
2. 두 행을 교환한다
3. 한 행에 n을 곱한 후 이를 다른 행에 더한다 

→ 일반 행렬을 가우스행렬, 기약가우스 행렬 형태로 변경하여 선형 시스템의 해를 구할 때 사용함 

 

가우스 행렬과 기약 가우스 행렬

• 가우스 행렬 : 각 행의 첫 원소는 1이고, 1 아래에 위치하는 원소는 모두 0인 행렬(행렬의 구성원소가 사다리꼴 형태)

• 기약 가우스 행렬(reduced Gauss matrix) : 첫 원소가 1인 열에 대해 1을 제외한 나머지 모든 행 원소가 0인 행렬  

 

가우스 조르단 소거법

첨가행렬을 기약 가우스 행렬로 변형하여 해를 구하는 방법 

가우스 소거법

첨가행렬을 가우스 행렬로 변형하여 해를 구하는 방법 

 

가우스조르단 소거법 구현 

def zero_mat(n,p):
  Z=[]
  for i in range(0,n):
    row=[]
    for j in range(0,p):
      row.append(0)
    Z.append(row)
  return Z

def deepcopy(A):
  if type(A[0]) == list:   #A가 행렬인 경우(첫번째 요소도 리스트이면 행렬)
    n=len(A)
    p=len(A[0])
    res = zero_mat(n,p)    #깊은 복사 후 붙여 넣을 영행렬
    for i in range(0,n):
      for j in range(0,p):
        res[i][j] = A[i][j]
    return res 
  else:                   #A가 리스트일 경우 
    n = len(A)
    res = []
    for i in range(0,n):
      res.append(A[i])
    return res 
    
    
def solve(A,b): #A,b:첨가행렬
  X = deepcopy(A)
  sol = deepcopy(b)

  n=len(X)

  for i in range(0,n):
    x_row = X[i]          #행에 해당하는 원소들을 리스트로 설정 
    y_val = sol[i]

    #행의 첫번째 원소를 1로 만든다. 
    if x_row[i] !=0:
      tmp = 1/x_row[i]     #tmp : 첫행 원소의 역수 
    else : tmp = 0

    x_row = [element*tmp for element in x_row]
    y_val = y_val*tmp

    X[i] = x_row     #역수를 곱한 값을 저장 
    sol[i] = y_val

    #대각 원소 외의 행 원소를 0으로 만든다 
    for j in range(0,n):
      if i==j:         #같은 행 번호를 지정할 때엔 패스 
        continue
      #i와 다른 행일 경우 
      x_next = X[j]   
      y_next = sol[j]
      #x_next에 음수를 취한 값을 x_row에 곱함 (y도 동일)
      x_tmp = [element*-x_next[i] for element in x_row]
      y_tmp = y_val*(-x_next[i])
      #이를 기존 x_next에 더해줌 
      for k in range(0,len(x_row)):
        x_next[k] = x_tmp[k] + x_next[k]
      y_next = y_tmp + y_next

      X[j] = x_next
      sol[j] = y_next
  return sol 
  
  
X=[[3,1,2],[2,6,-1],[4,0,-1]]
y = [5,1,3]

sol = solve(X,y)
print(sol)
#[1.0, -1.1102230246251565e-16, 0.9999999999999998]

 

넘파이로 더 쉽게 구현

import numpy as np

sol = np.linalg.solve(X,y)
print(sol)

#[1. 0. 1.]