작성자: admin 작성일시: 2016-05-16 23:14:40 조회수: 912 다운로드: 42
카테고리: 기초 수학 태그목록:

연립방정식과 역행렬

다음과 같이 $x_1, x_2, \cdots, x_n$ 이라는 $n$ 개의 미지수를 가지는 방정식을 연립 방정식(system of equations)이라고 한다.

$$ \begin{matrix} a_{11} x_1 & + \;& a_{12} x_2 &\; + \cdots + \;& a_{1M} x_M &\; = \;& b_1 \\ a_{21} x_1 & + \;& a_{22} x_2 &\; + \cdots + \;& a_{2M} x_M &\; = \;& b_2 \\ \vdots\;\;\; & & \vdots\;\;\; & & \vdots\;\;\; & & \;\vdots \\ a_{N1} x_1 & + \;& a_{N2} x_2 &\; + \cdots + \;& a_{NM} x_M &\; = \;& b_N \\ \end{matrix} $$

행렬의 곱셈을 이용하면 이 연립 방정식은 다음과 같이 간단하게 쓸 수 있다. $$ Ax = b $$

이 식에서 $A, x, b$ 는 다음과 같이 정의한다.

$$ A = \begin{bmatrix} a_{11} & a_{12} & \cdots & a_{1M} \\ a_{21} & a_{22} & \cdots & a_{2M} \\ \vdots & \vdots & \ddots & \vdots \\ a_{N1} & a_{N2} & \cdots & a_{NM} \\ \end{bmatrix} $$$$ x = \begin{bmatrix} x_1 \\ x_2 \\ \vdots \\ x_M \end{bmatrix} $$$$ b= \begin{bmatrix} b_1 \\ b_2 \\ \vdots \\ b_N \end{bmatrix} $$$$ Ax = b \;\;\;\;\; \rightarrow \;\;\;\;\; \begin{bmatrix} a_{11} & a_{12} & \cdots & a_{1M} \\ a_{21} & a_{22} & \cdots & a_{2M} \\ \vdots & \vdots & \ddots & \vdots \\ a_{N1} & a_{N2} & \cdots & a_{NM} \\ \end{bmatrix} \begin{bmatrix} x_1 \\ x_2 \\ \vdots \\ x_M \end{bmatrix} = \begin{bmatrix} b_1 \\ b_2 \\ \vdots \\ b_N \end{bmatrix} $$

예를 들어 다음과 같은 연립 방정식은

$$ \begin{alignat}{7} 3x_1 &&\; + \;&& 2x_2 &&\; - \;&& x_3 &&\; = \;&& 1 & \\ 2x_1 &&\; - \;&& 2x_2 &&\; + \;&& 4x_3 &&\; = \;&& -2 & \\ -x_1 &&\; + \;&& \tfrac{1}{2} x_2 &&\; - \;&& x_3 &&\; = \;&& 0 & \end{alignat} $$

다음과 같이 쓸 수 있다.

$$ Ax = b, \;\;\;\; A = \begin{bmatrix} 3 & 2 & -1 \\ 2 & -2 & 4 \\ -1 & \tfrac{1}{2} & 1 \\ \end{bmatrix}, \;\;\; b = \begin{bmatrix} 1 \\ -2 \\ 0 \end{bmatrix} $$

만약 $A, x, b$가 행렬이 아닌 실수라면 이 식은 나눗셈을 사용하여 다음과 같이 쉽게 풀 수 있을 것이다.

$$ x = \dfrac{b}{A} $$

그러나 행렬은 나눗셈이 정의되지 않으므로 이 식은 사용할 수 없다. 대신 역행렬(inverse)을 사용하여 이 식을 쉽게 풀 수 있다.

역행렬

정방 행렬(square matrix) $A\;(A \in \mathbb{R}^{M \times M}) $ 에 대한 역행렬은 $A^{-1}$ 이란 기호로 표시한다.

역행렬 $A^{-1}$은 원래의 행렬 $A$와 다음 관계를 만족하는 정방 행렬을 말한다. $I$는 단위 행렬(identity matrix)이다.

$$ A^{-1} A = A A^{-1} = I $$

두 개 이상의 정방 행렬의 곱은 마찬가지로 같은 크기의 정방행렬이 되는데 이러한 행렬의 곱의 역행렬에 대해서는 다음 성질이 성립한다.

$$ (AB)^{-1} = B^{-1} A^{-1} $$$$ (ABC)^{-1} = C^{-1} B^{-1} A^{-1} $$

역행렬과 연립 방정식의 해

미지수의 수와 방정식의 수가 같다면 행렬 $A$ 는 정방 행렬이 된다.

만약 행렬 $A$의 역행렬 $ A^{-1} $ 이 존재한다면 역행렬의 정의에서 연립 방정식의 해는 다음과 같이 구해진다.

$$ Ax = b $$$$ A^{-1}Ax = A^{-1}b $$$$ Ix = A^{-1}b $$$$ x = A^{-1}b $$

NumPy의 역행렬 계산

NumPy의 linalg 서브패키지에는 역행렬을 구하는 inv 라는 명령어가 존재한다. 그러나 실제 계산시에는 수치해석 상의 여러가지 문제로 inv 명령어 보다는 lstsq (least square) 명령어를 사용한다.

In [1]:
A = np.array([[1, 3, -2], [3, 5, 6], [2, 4, 3]])
A
Out[1]:
array([[ 1,  3, -2],
       [ 3,  5,  6],
       [ 2,  4,  3]])
In [2]:
b = np.array([[5], [7], [8]])
b
Out[2]:
array([[5],
       [7],
       [8]])
In [4]:
Ainv = np.linalg.inv(A)
Ainv
Out[4]:
array([[ 2.25,  4.25, -7.  ],
       [-0.75, -1.75,  3.  ],
       [-0.5 , -0.5 ,  1.  ]])
In [5]:
x = np.dot(Ainv, b)
x
Out[5]:
array([[-15.],
       [  8.],
       [  2.]])
In [6]:
np.dot(A, x) - b
Out[6]:
array([[ -3.55271368e-15],
       [ -1.42108547e-14],
       [ -1.42108547e-14]])
In [12]:
x, resid, rank, s = np.linalg.lstsq(A, b)
x
Out[12]:
array([[-15.],
       [  8.],
       [  2.]])

위 해결 방법에는 두 가지 의문이 존재한다. 우선 역행렬이 존재하는지 어떻게 알 수 있는가? 또 두 번째 만약 미지수의 수와 방정식의 수가 다르다면 어떻게 되는가?

행렬식

행렬식과 역행렬 사이에는 다음의 관계가 있다.

행렬식의 값이 0이 아니면 역행렬이 존재한다. 반대로 역행렬이 존재하면 행렬식의 값은 0이 아니다.

따라서 행렬식의 값을 계산하여 역행렬의 존재 여부를 알아낸다.

최소 자승 문제

연립 방정식은 다음과 같은 세 종류가 있다.

  1. 미지수의 수가 방정식의 수와 같다. ($N = M$)
  2. 미지수의 수가 방정식의 수보다 적다. ($N < M$)
  3. 미지수의 수가 방정식의 수보다 많다. ($N > M$)

1번의 경우는 앞에서 다루었다. 2번의 경우에는 너무 많은 해가 존재할 수 있다. 3번의 경우에는 2번과 반대로 모든 조건을 만족하는 해가 하나도 존재할 수 없을 수도 있다.

그런데 데이터 분석 문제에서는 $A$ 를 feature matrix, $x$ 를 가중치 벡터 $w$ 라고 보았을 때 데이터의 수가 가중치의 갯수보다 많은 경우가 일반적이다. 다만 이 때는 방정식이 정확하게 등호를 이루기를 바라지는 않는다. 즉, 대략적으로만 좌변과 우변이 비슷하면 되는 경우이다.

$$ Ax \approx b $$

이 경우에는 좌변과 우변의 차이를 최소화하는 문제로 바꾸어 풀 수 있다.

$$ e = Ax-b $$$$ e^Te = (Ax-b)^T(Ax-b) $$$$ x = \text{arg} \min_x e^Te = \text{arg} \min_x \; (Ax-b)^T(Ax-b) $$

이러한 문제를 최소 자승(Least Square) 문제라고 한다.

최소 자승 문제의 답은 $A^TA$ 는 항상 정방행렬이 된다는 점을 사용하여 다음과 같이 풀 수 있다.

$$ Ax = b $$$$ A^TAx = A^Tb $$$$ (A^TA)x = A^Tb $$$$ x = (A^TA)^{-1}A^T b $$$$ x = ((A^TA)^{-1}A^T) b $$

이 값이 최소 자승 문제의 답이 된다는 것은 추후에 행렬의 미분을 사용하여 증명할 수 있다. 여기에서 행렬 $(A^TA)^{-1}A^T$ 를 행렬 $A$ 의 의사 역행렬(pseudo inverse)라고 하며 다음과 같이 $ A^{+}$ 로 표기하기도 한다.

$$ A^{+} = (A^TA)^{-1}A^T $$

NumPy의 lstsq 명령은 사실 이러한 최소 자승 문제를 푸는 명령이다.

In [15]:
A = np.array([[2, 0], [-1, 1], [0, 2]])
A
Out[15]:
array([[ 2,  0],
       [-1,  1],
       [ 0,  2]])
In [16]:
b = np.array([[1], [0], [-1]])
b
Out[16]:
array([[ 1],
       [ 0],
       [-1]])
In [17]:
Apinv = np.dot(np.linalg.inv(np.dot(A.T, A)), A.T)
Apinv
Out[17]:
array([[ 0.41666667, -0.16666667,  0.08333333],
       [ 0.08333333,  0.16666667,  0.41666667]])
In [18]:
x = np.dot(Apinv, b)
x
Out[18]:
array([[ 0.33333333],
       [-0.33333333]])
In [19]:
np.dot(A, x) - b
Out[19]:
array([[-0.33333333],
       [-0.66666667],
       [ 0.33333333]])
In [20]:
x, resid, rank, s = np.linalg.lstsq(A, b)
x
Out[20]:
array([[ 0.33333333],
       [-0.33333333]])

질문/덧글

행렬의 곱을 할때마다 np.dot( )을 계속 써주어야 하나요? todh*** 2016년 9월 6일 8:34 오후

np.dot을 계속하려니 다소 번거롭기도한데 np.dot()을 한번만 써서 여러 행렬을 곱할 수 있나요?

답변: 행렬의 곱을 할때마다 np.dot( )을 계속 써주어야 하나요? 관리자 2016년 9월 7일 9:49 오전

현재는 곱을 할때마다 np.dot( )을 계속 써주어야 합니다.
추후 버전에는 numpy.linalg.multi_dot 명령이 추가될 예정이고 ( https://github.com/numpy/numpy/pull/4977 )
지금은 reduce 등을 사용하여 multiple dot 을 구현하실 수 있습니다. ( http://stackoverflow.com/questions/11838352/multiply-several-matrices-in-numpy )

수학 질문 crys*** 2016년 10월 19일 6:53 오후

pseudo inverse를 역행렬의 성질과 결합법칙을 이용하여
이렇게 풀어도 되는 것인지 아니면 어느 부분에서 잘못했는지 궁금합니다.

Apinv = inv(A.T × A) × A.T
= inv(A) × inv(A.T) × A.T ---> 역행렬의 성질
= ( inv(A) × ( inv(A.T) ) × A.T
= inv(A) × ( inv(A.T) × A.T ) ---> 결합법칙
= inv(A) × I ---> 단위행렬

답변: 수학 질문 관리자 2016년 10월 20일 4:01 오후

A가 정방행렬이 아니므로 A의 역행렬은 존재할 수 없습니다.