[2주차 - Day5] 인공지능 수학

선형 시스템

 

연립일차방정식은 linear system(선형시스템)입니다.

 

Gauss 소거법(2X3 liner systme)

3x + y + z = 4

  x - 2y - z = 5

변수 하나씩 소거하면서 계산

 

이 방정식들을 각각 linear equation(선형방정식)이라 합니다.

선형대수(linear algebra)의 목표는 어떤 연립일차방정식 문제라도 정형적인 방법으로 표현하고, 해결하는 방법을 배우는 것입니다.

 

Ax = b로 표현하기

1. 선형시스템의 unknowns(미지수)를 모아 column vector(열벡터) x로 표현합니다.

2. 선형시스템의 linear equation(선형방정식)에 대해 다음을 수행합니다.

  ● coefficients(계수)를 모아 A의 row vector(행벡터)로 표현합니다.

  ● constant(상수)를 모아 b에 표현합니다.

 

선형시스템

3x1 + x2 = 2

x1 - 2x2 = 3

2x1 - 4x2 = 6

 

m x n 선형시스템의 Ax = b 표현을 정리하면 다음과 같습니다.

  ● 식은 행이고, 행은 식입니다. (linear equation ↔ row)

  ● m은 linear equation(선형방정식)의 개수입니다.

  ● n은 unknown(미지수)의 개수입니다.

  ● A은 m x n 행렬입니다.

  ● x는 n-벡터입니다.

  ● b는 m-벡터입니다.

 

선형대수(NumPy 실습)

 

행렬과 벡터의 코딩 및 연산

import numpy as np

# 행렬 코딩
A = np.array([[3, 1, 1], [1, -2, -1], [1, 1, 1]])

print(A)
print(np.shape(A))

 

 

[[ 3  1  1]
 [ 1 -2 -1]
 [ 1  1  1]]
(3, 3)

 

# 벡터 코딩
b = np.array([4, 1, 2])

print(b)
print(np.shape(b))

 

[4 1 2]
(3,)

 

# 역행렬 구하기
A_inv = np.linalg.inv(A)

print(A_inv)
print(np.shape(A_inv))

 

[[ 5.00000000e-01 -7.40148683e-17 -5.00000000e-01]
 [ 1.00000000e+00 -1.00000000e+00 -2.00000000e+00]
 [-1.50000000e+00  1.00000000e+00  3.50000000e+00]]
(3, 3)

 

# 역행렬을 이용한 선형시스템 Ax=b의 해 구하기
# x = np.matmul(A_inv, b)
x = A_inv @ b

print(x)
print(np.shape(x))

 

[ 1. -1.  2.]
(3,)

## 결과 검증
# bb = np.matmul(A, x)
bb = A @ x

print(np.shape(bb))
print(bb)

if np.linalg.norm(b - bb) < 1e-3:
    print("Ok")
else:
    print("something wrong")

 

(3,)
[4. 1. 2.]
Ok

 

가우스 소거법(Gauss elimination)

 

선형시스템의 해(Solutions of a Linear System)

해가 하나인 경우(unique solution)

3x = 6

 

해가 없는 경우(no solution)

0x = 6

 

해가 여러 개인 경우(infinitely many solutions)

0x = 0

 

● a = 0이면 특이하다.

      ● ax = b의 해가 곧바로 나오지 않습니다.

      ● a의 역수(inverse)가 존재하지 않는 경우, a가 특이(singular)하다고 합니다.

● 해가 있으면 선형시스템이 consistent 하다고 한다.

● 해가 없으면 선형시스템이 inconsistent하다고 한다.

 

Gauss elimination은 임의의 m x n 선형시스템의 해를 구하는 가장 대표적인 방법입니다.

Gauss elimination은 다음의 두 단계로 수행됩니다.

1. Forward elimination(전방소거법): 주어진 선형시스템을 아래로 갈수록 더 단순한 형태의 선형방정식을 가지도록 변형합니다.

2. back-substitution(후방대입법): 아래에서부터 위로 미지수를 실제값으로 대체합니다. 

 

Gauss elimination에서 forward elimination의 가치

  ● 주어진 선형시스템을 가장 풀기 쉬운 꼴로 변형해줍니다.

  ● 주어진 선형시스템의 rank(랭크)를 알려줍니다.

  ● 선형시스템이 해가 있는지(consistent) 아니면 해가 없는지(inconsistent) 알려줍니다.

 

Upper triangular form(상삼각형태)

Forward elimination(전방소거법)은 EROs(기본행 연산)을 활용하여 주어진 선형시스템 Ax = b에서 행렬 A를 upper triangular form으로 만드는 작업을 수행합니다.

 

LU 분해(LU decomposition)

 

인수분해가 쓸모 있는 경우

  ● 분수의 약분

  ● 두 수의 최대공약수 구하기

  ● 두 수의 최소공배수 구하기

 

주어진 행렬을 행렬분해한 상태로 가지고 있으면 계산이 편해지는 경우가 많은데, 대표적으로 행렬분해가 있습니다.

  ● LU 분해(LU decomposition)

  ● 분수의 약분(QR decomposition)

  ● 분수의 약분(SVD, Singular Value Decomposition)

 

LU 분해는 가우스 소거법을 행렬 형태로 계산한 걸 의미합니다.

LU 분해를 이용해 Ax = b 문제를 아래와 같이 나타내면

Ax = b → (LU) x = b → L(Ux) = b

            → Ly = b(단, Ux = y)

 

LU 분해는 가우스 소거법의 forward elimination(전방소거법)을 행렬로 코드화한 것입니다.

  ● L: 행렬 A를 전방소거하는데 쓰인 replacement와 scaling에 대한 EROs를 기록해 둔 행렬

  ● U: 행렬 A를 전방소거한 후 남은 upper triangular matrix(상삼각행렬)

  ● P: 행렬 A를 전방소거하는데 쓰인 interchagnge에 대한 EROs를 기록해 둔 행렬(옵션)

LU 분해가 가우스 소거법의 forward elimination(전방소거법)와 의미가 거의 같습니다.

 

LU 분해의 활용

  ● 수치적 안정성: 선형시스템 Ax = b의 해를 역행렬 A의 역행렬을 이용해 직접 구하는 것보다 PLU 분해를 이용하는 것이 수치적으로 안정적입니다.

  ● b가 자주 업데이트되는 경우: 선형시스템 Ax = b에서 행렬 A는 고정되어 있고, b가 자주 변하는 문제가 종종 있는데, 행렬 A를 미리 PLU로 분해해 둔다면, b가 업데이트될 때마다 선형시스템의 해 x를 실시간으로 구할 수 있습니다.