작성자: admin 작성일시: 2016-09-26 22:11:35 조회수: 178 다운로드: 36
카테고리: 기초 수학 태그목록:

연립방정식과 역행렬

다음과 같이 $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 $$

역행렬 계산

R에는 역행렬을 구하는 solve 라는 명령어가 존재한다.

In [1]:
A <- matrix(c(1, 3, -2, 3, 5, 6, 2, 4, 3), nrow=3, byrow=T)
A
1 3 -2
3 5 6
2 4 3
In [3]:
b <- c(5, 7, 8)
b
  1. 5
  2. 7
  3. 8
In [6]:
Ainv <- solve(A)
Ainv
2.25 4.25-7
-0.75-1.75 3
-0.50-0.50 1
In [7]:
x <- Ainv %*% b
x
-15
8
2
In [8]:
A %*% x - b
-1.065814e-14
-3.907985e-14
-2.664535e-14

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

행렬식

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

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

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

In [9]:
det(A)
-4

최소 자승 문제

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

  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 $$

MASS 패키지의 ginv 명령을 쓰면 의사 역행렬을 바로 구할 수 있다.

In [18]:
A <- matrix(c(2, 0, -1, 1, 0, 2), nrow=3, byrow=T)
A
20
-11
02
In [19]:
b <- c(1, 0, -1)
b
  1. 1
  2. 0
  3. -1
In [20]:
Apinv <- solve(t(A) %*% A) %*% t(A)
Apinv
0.41666667-0.16666670.08333333
0.08333333 0.16666670.41666667
In [21]:
x <- Apinv %*% b
x
0.3333333
-0.3333333
In [22]:
A %*% x - b
-0.3333333
-0.6666667
0.3333333
In [24]:
library(MASS)
ginv(A)
0.41666667-0.16666670.08333333
0.08333333 0.16666670.41666667

질문/덧글

아직 질문이나 덧글이 없습니다. 첫번째 글을 남겨주세요!