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

연립 방정식과 역행렬

중요 개념

  • 연립 방정식
  • 역행렬
  • 최소 자승 문제, 의사 역행렬

다음과 같이 $x_1, x_2, \cdots, x_M$ 이라는 $M$ 개의 미지수를 가지는 $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)을 사용하여 이 식을 쉽게 풀 수 있다.

역행렬

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

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

역행렬의 성질

  • 전치행렬의 역행렬은 역행렬의 전치행렬과 같다.
$$ (A^{T})^{-1} = (A^{-1})^{T} $$
  • 두 개 이상의 정방 행렬의 곱은 마찬가지로 같은 크기의 정방행렬이 되는데 이러한 행렬의 곱의 역행렬에 대해서는 다음 성질이 성립한다.
$$ (AB)^{-1} = B^{-1} A^{-1} $$$$ (ABC)^{-1} = C^{-1} B^{-1} A^{-1} $$
  • 또한 역행렬은 행렬식과 다음과 같은 관계를 가진다. 이 식에서 코팩터로 이루어진 행렬 $C$을 코팩터 행렬(matrix of cofactors, 또는 cofactor matrix, comatrix)이라고 한다. 또한 코팩터 행렬의 전치 행렬 $C^T$를 adjugate matrix 또는 adjoint matrix 이라고 하며 $\text{adj}(A)$로 표기하기도 한다.
$$ A^{-1} = \dfrac{1}{\det A} C^T = \dfrac{1}{\det A} \begin{bmatrix} C_{1,1} &\cdots& C_{N, 1}\\ \vdots &\ddots &\vdots\\ C_{1,N} &\cdots &C_{N,N}\\ \end{bmatrix} $$

위 식을 이용하면 임의의 정방행렬의 역행렬을 구할 수 있고 역행렬은 행렬식이 0이 아닌 경우에만 존재한다는 것을 알 수 있다.

역행렬과 연립 방정식의 해

미지수의 수와 방정식의 수가 같다면 행렬 $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:
A = np.array([[1, 3, -2], [3, 5, 6], [2, 4, 3]])
A
Out:
array([[ 1,  3, -2],
       [ 3,  5,  6],
       [ 2,  4,  3]])
In:
b = np.array([[5], [7], [8]])
b
Out:
array([[5],
       [7],
       [8]])
In:
Ainv = np.linalg.inv(A)
Ainv
Out:
array([[ 2.25,  4.25, -7.  ],
       [-0.75, -1.75,  3.  ],
       [-0.5 , -0.5 ,  1.  ]])
In:
x = np.dot(Ainv, b)
x
Out:
array([[-15.],
       [  8.],
       [  2.]])
In:
np.dot(A, x) - b
Out:
array([[ -3.55271368e-15],
       [ -1.42108547e-14],
       [ -1.42108547e-14]])
In:
x, resid, rank, s = np.linalg.lstsq(A, b)
x
Out:
array([[-15.],
       [  8.],
       [  2.]])

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

역행렬의 존재

위에서 말한 행렬식과 역행렬의 관계에서 다음을 알 수 있다.

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

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

최소 자승 문제

다음으로 미지수의 수와 방정식의 수를 고려해 볼 때 연립 방정식에는 다음과 같은 세 종류가 있을 수 있다.

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

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

그런데 데이터 분석 문제에서는 계수 행렬 $A$ 를 특징 행렬 $X$, 미지수 벡터 $x$ 를 가중치 벡터 $w$ 라고 보았을 때 데이터의 수가 가중치의 수보다 많은 경우가 즉 3번과 같은 경우가 일반적이다. 만약 데이터의 수가 가중치의 수보다 적은 경우에는 일반적으로 데이터 분석을 할 수 없다.

방정식의 수가 미지수의 수보다 많은 경우에는 정확한 해가 존재하지 않기 때문에 방정식의 우변과 좌변이 정확하게 등호를 이루기를 바라지는 않는다. 대신 좌변과 우변을 비슷하게라도 만들 수 있는 미지수를 찾을 수 있다면 아예 아무런 숫자를 찾지 못하는 것보다는 훨씬 나을 것이다.

$$ Ax \approx b $$

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

$$ e = Ax-b $$

좌변과 우변의 차이 즉 잔차를 최소화 한다는 것은 잔차 벡터의 크기 즉, 놈을 최소화 하는 것과 같다.

$$ e^Te = \Vert e \Vert^2 = (Ax-b)^T(Ax-b) $$

이 값을 최소화 하는 $x$ 값을 찾는 식은 다음과 같이 표현한다.

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

위 식에서 $ \text{arg} \min_x f(x) $ 는 함수 $f(x)$를 가장 작게 만드는 $x$ 값을 의미한다.

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

최소 자승 문제의 답을 계산할 때는 $A^TA$가 항상 정방 행렬이 된다는 점을 이용한다. 만약 정방행렬 $A^TA$의 역행렬 $(A^TA)^{-1}$이 존재한다면 다음과 같이 미지수 벡터 $x$의 값을 구한다.

$$ Ax \approx b $$

이 식의 양변에 $A^T$를 곱하면 등식이 성립한다고 가정하자.

$$ 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 $$$$ x = A^+ b $$

이 값이 최소 자승 문제의 답이 된다는 것은 나중에 행렬의 미분을 사용하여 증명할 것이다.

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

In:
A = np.array([[2, 0], [-1, 1], [0, 2]])
A
Out:
array([[ 2,  0],
       [-1,  1],
       [ 0,  2]])
In:
b = np.array([[1], [0], [-1]])
b
Out:
array([[ 1],
       [ 0],
       [-1]])
In:
Apinv = np.dot(np.linalg.inv(np.dot(A.T, A)), A.T)
Apinv
Out:
array([[ 0.41666667, -0.16666667,  0.08333333],
       [ 0.08333333,  0.16666667,  0.41666667]])
In:
x = np.dot(Apinv, b)
x
Out:
array([[ 0.33333333],
       [-0.33333333]])
In:
np.dot(A, x) - b
Out:
array([[-0.33333333],
       [-0.66666667],
       [ 0.33333333]])
In:
x, resid, rank, s = np.linalg.lstsq(A, b)
x
Out:
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의 역행렬은 존재할 수 없습니다.

미지수의 수와 방정식의 수 simf*** 2017년 2월 6일 6:32 오후

안녕하세요 박사님,

최소 자승 문제 부분에서

2. 미지수의 수가 방정식의 수보다 적다. ( N<M ) -> 너무 많은 해가 존재할 수 있다.
3. 미지수의 수가 방정식의 수보다 많다. ( N>M ) -> 모든 조건을 만족하는 해가 하나도 존재할 수 없을 수도 있다.

라고 설명되어 있는데, 반대가 되어야 하는 것 아닌가요?

답변: 미지수의 수와 방정식의 수 관리자 2017년 2월 7일 4:53 오후

잘못되었습니다. 수정하였습니다. 지적 감사드립니다.

최소 자승 문제설명중에 e가 최소인 x를 찾는것? samk*** 2017년 4월 7일 10:23 오후

최소 자승 문제설명중에 e가 최소인 x를 찾는 것은 이해가 갔습니다.
다만, 수식 유도가 이해가 어려운 부분이 있습니다.

1. e=Ax−b
2. eTe=(Ax−b)T(Ax−b)
3. x=argminxeTe=argminx(Ax−b)T(Ax−b)

1 -> 2 -> 3 순서로 유도된 것은
eTe 의 최소값이 e의 최소값과 동일하다는 뜻인지요?

답변: 최소 자승 문제설명중에 e가 최소인 x를 찾는것? 관리자 2017년 4월 11일 9:41 오후

$e^Te$ 의 최소값이 $e$의 최소값과 동일하다는 뜻이 아닙니다. 최소화하는 것은 $e^Te$ 입니다. $e=Ax-b$ l식은 $e$의 정의입니다.