선형대수 - 역문제 1

프로그래머를 위한 선형대수을 읽고 정리한 내용입니다. 혹시라도 책의 내용을 정리하는 것이 문제가 된다면 연락바랍니다.

이 책에서는 Ruby로 예제코드를 제공해주고 Ruby 언어를 읽을 줄 모르는 것은 아니지만 선형대수학을 간단하게 정리해보고 싶어서 개념만을 정리하기로 했습니다. 프로그래머를 위한 선형대수의 예제코드는 GitHub 레포지토리로 존재합니다.

역문제

많은 문제들은 같은 형태로 입력 가 주어지면 출력 가 나오는 문제들이 많이 존재한다. 하지만, 결과(출력)만을 알고 있고, 원인(입력)을 추측해야 하는 때가 있는데, 그러한 문제가 바로 역문제이다. 이와 달리 원인을 알고 결과를 추측하는 경우는 순문제이다.

노이즈가 없는 경우

$$y = Ax$$

위와 같은 경우를 놓고 살펴보겠다.

x와 y의 차원이 같은 경우 (정칙행렬)

이 경우는 가 정방행렬이고, 일 경우 로 간단히 둘 수 있다. 이걸로 결과 에서 원인 를 알 수 있다. 이 경우 행렬 정칙행렬이라고 한다.

이 경우 해답을 크게 세가지 방법으로 구할 수 있는데, 그 방법의 목록을 아래와 같다.

  • 연립방정식
  • 역행렬
  • 블록행렬

역행렬의 경우에는 프로그래머를 위한 선형대수 1에서 설명했듯이 와 같은 방식으로 구해서 양 변에 곱하는 방법이다. 연립방정식의 경우는 진짜 손으로 식 하나하나 써서 변수 하나하나 소거해가는 단순 반복이므로 더 이상 서술하지 않는다.

이고, , , 라고 적을 때 블록행렬로 푸는 방법은 아래와 같다.

우선 위 식을 아래처럼 표현한다.

$$\pmatrix{\begin{array}{cc|c}2&3&1\\4&5&2\end{array}} \pmatrix{x_1 \\x_2 \\-1} = \pmatrix{0\\0}$$

그리고 나서 왼쪽의 행렬을 단위 행렬로 만드는 것이 목표이다. 먼저 1행 1열을 1로 만들어주고, 그 아래 행들의 1열을 0으로 만들어준다.

$$\pmatrix{\begin{array}{cc|c}1 & \frac{3}{2} & \frac 1 2 \\\hline4&5&2\end{array}}\pmatrix{x_1 \\ x_2 \\ -1} = \pmatrix{0\\0}$$

$$\pmatrix{\begin{array}{cc|c}1 & \frac{3}{2} & \frac 1 2 \\\hline0&-1&0\end{array}}\pmatrix{x_1 \\ x_2 \\ -1} = \pmatrix{0\\0}$$

$$\pmatrix{\begin{array}{cc|c}1 & \frac{3}{2} & \frac 1 2 \\\hline0&1&0\end{array}}\pmatrix{x_1 \\ x_2 \\ -1} = \pmatrix{0\\0}$$

$$\pmatrix{\begin{array}{cc|c}1 & 0 & \frac 1 2 \\\hline0&1&0\end{array}}\pmatrix{x_1 \\ x_2 \\ -1} = \pmatrix{0\\0}$$

즉, 이다. 위를 간단하게 정리하면 다음과 같다.

위 식을 변형하여 아래처럼 만든다.

이 형태가 되면, 답은 이다.


하지만 이때, 단위행렬로 만들기 위한 n번째 열이 이미 0인 경우가 있다. 그 때는 행끼리 순서를 바꾸어 줄 수 있다. 즉,

이다. 이를 피보팅(pivoting)이라고 한다.

나중에 이어서

July 3, 2018 에 작성
Tags: linear algebra