💽선형시스템

📚배운 강의 내용

• 선형시스템 개념 복습
• $Ax + b$ 연립일차방정식의 대수적 표현
• 가우스 소거법 : 선형시스템을 푸는 방법
• LU 분해: 가우스 소거법 과정을 행렬로 표현
• 행렬연산과 선형 변환

---

📌선형시스템의 개념

선형시스템의 개념은 초, 중학교 때 배웠던 일차방정식, 연립일차방정식을 떠올리면 된다.

$3x = 6$
👉$x = 2$

---

$3x + y = 2$
$x - 2y = 3$

👉$x = 1, y = -1$

---

$3x + y + z = 4$
$x - 2y - z = 1$
$x + y + z = 2$

👉 $x = 1, y = -1, z = 2$

그런데... 변수가 더 많아진다면?

---

📌선형시스템의 목표

선형시스템의 목표는 어떤 연립일차방정식이라도 정형적인 방법으로 표현하고 해결하는 방법을 배우기 위함이라고 할 수 있다.

$3x + y + z = 4$
$x - 2y - z = 1$
$x + y + z = 2$

이런 식이 있다고 할 때 각각의 방정식을 linear equation(선형방정식) 라고 표현한다.
이 때의 미지수 $x, y, z$를 각각 unknown(or variable)이라고 한다.

이 때의 3개의 linear equation과 3개의 unknown로 구성된 연립일차방정식을
3 x 3 linear system
이라고 한다.

$2 \times 3$ linear system

$3x + y + z = 4$
$x - 2y - z = 1$

$1 \times 2$ linear system

$2x + y = 3$

$3 \times 2$ linear system

$3x + y = 2$
$x - 2y = 3$
$2x - 4y = 6$

non-linear equation (비선형방정식)

$sin x + y = 2$

non-linear equation (비선형방정식)

$3x + y^3 = 2$

이런 형태를 따라 아래와 같은 방정식은 변수와 변수를 곱함으로 곡선 그래프를 그리기 때문에 비선형방정식으로 취급한다.

$xy + z = 3$

---

📌$Ax = b$ 연립일차방정식의 대수적 표현

그렇다면 선형시스템을 어떻게 $Ax = b$로 표현할 수 있을까?
다음과 같은 두가지 방법을 따른다.

1. 선형시스템의 unknown(미지수)를 모아 column vector(열벡터) $x$로 표현한다.
2. 선형시스템의 linear equation에 대해 다음을 수행한다.
   • coefficients(계수)를 모아 $A$의 row vector(행벡터)로 표현한다.
   • constant(상수)를 모아 $b$에 표현한다.

예를 들어, 다음과 같은 선형시스템은 이렇게 표현할 수 있다.

$3x_1 + x_2 + x_3 = 4$
$x_1 - 2x_2 - x_3 = 1$

$A \times X = b$
$\begin{bmatrix}3&1&1\\1&-2&-1\\\end{bmatrix}$       $\begin{bmatrix}x_1\\x_2\\x_3\\\end{bmatrix}$  =    $\begin{bmatrix}4\\1\\ \end{bmatrix}$

$m \times n$ 선형시스템의 $Ax = b$ 표현을 정리하면 다음과 같다.

• 식은 행이고, 행은 식이다. (linear equation <-> row )
• $m$은 linear equation의 개수이다.
• $n$은 unknown의 개수이다.
• $A$는 $m \times n$ 행렬이다.
• $x$는 $n$-벡터이다.
• $b$는 $m$-벡터이다.
    
• $A$의 역행렬(inverse matrix)가 존재하지 않을 때, $A$가 특이(singular)하다고 한다.
• 해가 있으면 시스템이 consistent하다고 한다.
• 해가 없으면 시스템이 inconsistent하다고 한다.

  ---

📌파이썬에서의 선형시스템

파이썬에서는 간단하게 numpy패키지를 추가하는 것으로 선형시스템을 사용할 수 있다.

import numpy as np

A = np.array([[3,1,1],[1,-2,-1],[1,1,1]])
print(A)
print(A.shape)

$\begin{bmatrix}3&1&1\\1&-2&-1\\1&1&1\end{bmatrix}$
 (3, 3)

역행렬을 구하는 법도 간단하다.

A_inv = np.linalg.inv(A)

따라서 $Ax = b$의 해를 구하고 싶다면 역행렬을 한 후, 행렬곱을 통해 계산해주면 된다.
행렬곱을 하는 식은 다음과 같다.

x = np.matmul(A_inv, b)
x = A_inv @ b

---

📌가우스 소거법

가우스 소거법 (Gauss elimination)은 임의의 $m \times n$ 선형시스템의 해를 구하는데 대표적이다. 다음의 두 단계를 따라 가우스 소거법을 행할 수 있다.

1. Forward elimination(전방 소거법) : 주어진 선형시스템을 아래로 갈수록 더 단순한 형태의 선형방정식을 가지도록 변형한다.
2. back-substitution(후방 대입법) : 아래에서부터 위로 미지수를 실제값으로 대체한다.

Forward elimination 전

$\begin{bmatrix}1&2&1\\1&2&3\\2&3&-1\end{bmatrix}$ $\begin{bmatrix}x_1\\x_2\\x_3\\\end{bmatrix}$ $\begin{bmatrix}1\\3\\-3\\\end{bmatrix}$

Forward elimination 후
=>
$\begin{bmatrix}1&2&1\\0&1&3\\0&0&1\end{bmatrix}$ $\begin{bmatrix}x_1\\x_2\\x_3\\\end{bmatrix}$ $\begin{bmatrix}1\\5\\1\\\end{bmatrix}$

이제 Back-substitution을 이용하여 아래에서부터 미지수를 실제값으로 대체하여 구할 수 있다.

$\begin{bmatrix}1&2&1\\0&1&3\\0&0&1\end{bmatrix}$ $\begin{bmatrix}x_1\\x_2\\x_3\\\end{bmatrix}$ $\begin{bmatrix}1\\5\\1\\\end{bmatrix}$

Back-substitution 후
=>
$\begin{bmatrix}1&2&1\\0&1&3\\0&0&1\end{bmatrix}$ $\begin{bmatrix} \\ \\ \\ &\end{bmatrix}$ $\begin{bmatrix}1\\5\\1\\\end{bmatrix}$

Gauss elimination에서 forward elimination의 가치는 다음과 같다.

• 주어진 선형시스템을 가장 풀기 쉬운 꼴로 변형해 준다.
• 주어진 선형시스템의 rank를 알려준다.
• 선형시스템이 해가 있는지(consistent) 아니면 해가 없는지(inconsistent) 알려준다.

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

---

📌$LU$ 분해

행렬을 분해하는 방법으로는 대표적으로 3가지가 있다.

• $LU$분해($LU$ decomposition)
• $QR$분해($QR$ decomposition)
• 특이값 분해(SVD, Singular Value Decomposition)

이 중 $LU$분해는

• $L$ : lower triangular matrix (하삼각행렬)
• $U$ : upper triangular matrix (상삼각행렬)

를 의미한다. 다시 말해, $LU$분해는 가우스 소거법의 forward elimination을 행렬로 코드화 한 것이라고 할 수 있다.

• $L$ : 행렬 $A$를 전방소거하는데 쓰인 replacement와 scaling에 대한 EROs를 기록해 둔 행렬
• $U$ : 행렬 $A$를 전방소거한 후 남은 upper triangular matrix(상삼각행렬)
• $P$ : 행렬 $A$를 전방소거하는데 쓰인 interchange에 대한 EROs를 기록해 둔 행렬(Optional)

$LU$분해는 2가지 이유로 활용된다.

1. 수치적 안정성: 선형시스템 $Ax = b$의 해를 역행렬 $A^{-1}$를 이용해 직접 구하는 것보다 $PLU$분해를 이용하는 것이 좀 더 수치적으로 안정적이다.
2. $b$가 자주 업데이트되는 경우: 선형시스템 $Ax = b$에서 행렬 $A$는 고정되어 있고 $b$가 자주 변하는 문제가 있다. 이런 경우, 행렬 $A$를 미리 $PLU$로 분해해 둔다면, $b$가 업데이트될 때마다 선형시스템의 해 $x$를 실시간으로 구할 수 있다.

---

📌행렬연산과 선형변환

텐서(tensor)는 스칼라, 벡터, 행렬을 아우르는 개념이다. 숫자가 늘어설 수 있는 방향이 $k$개면 $k$-텐서로 부른다.

• 0-텐서: 스칼라
• 1-텐서: 벡터
• 2-텐서: 행렬

만일 아래의 $T$의 각 요소 $P_{(i,j)}$가 벡터라면, $T$는 $3$-텐서로 볼 수 있다.

$T = \begin{bmatrix}P_{(1,1)}&P_{(1,2)}&P_{(1,3)}&P_{(1,4)}\\P_{(2,1)}&P_{(2,2)}&P_{(2,3)}&P_{(2,4)}\\P_{(3,1)}&P_{(3,2)}&P_{(3,3)}&P_{(3,4)}\\P_{(4,1)}&P_{(4,2)}&P_{(4,3)}&P_{(4,4)}\end{bmatrix}$

행렬을 구조적으로 바라보는 가장 효과적인 방법은 행렬을 열벡터의 리스트로 바라보는 것이다. 따라서 $m \times n$행렬은 $m$-벡터가 $n$개 있다고 해석할 수 있다.

함수의 입력이 $n$-벡터이고 출력이 $m$-벡터인 함수 $T$가 있다고 할 때 이와 같이 함수의 입출력이 벡터인 함수를 변환(transformation)이라고 한다.

$T : ℝ^n \rightarrow ℝ^m$

특별히 $n = m$인 경우, 해당 변환을 연산자(operator)라고 한다.

변환의 예: MNIST 손글씨 인식 문제
$28 \times 28$ 해상도의 손글씨 숫자영상을 grayscale로 받아, 0~9까지 어떤 숫자가 적혀있는지 알아내는 손글씨 인식 문제는 다음과 같은 (비선형) 변환이다.

$T : ℝ^{28 \times28} \rightarrow ℝ^{10}$

$m \times n$ 행렬 $Ax$는 $n$-벡터를 입력으로 받아 $m$-벡터를 출력으로 내는 변환 $T_A(x) = Ax$로 볼 수 있다. 이 변환은 행렬이 정의하기 때문에 행렬변환(matrix transformation)이라고 한다.

$T_A : ℝ^n \rightarrow ℝ^m$

그런데 행렬변환은 다음의 선형함수 성질을 모두 만족하기 때문에 선형변환(linear transformation)이다.

$T_A(x+y) : T_A(x) + T_A(y),$
$T_A(cx) = cT_A(x),$
(단, $x,y \in ℝ^n$이고, $c$는 임의의 스칼라)

정리
$m \times n$ 행렬은 $n$-벡터를 입력으로 받아 $m$-벡터를 출력으로 내는선형변환이며, 임의의 선형변환은 행렬로 표현가능하다. 즉, 행렬은 선형변환의 구현체이다.

Q. 2차원 벡터를 입력으로 받아 해당 벡터를 반시계방향으로 $\theta$만큼 회전하는 기능을 구현해 보자.

$A_{2\times2} = \begin{bmatrix}x_1&y_1\\x_2&y_2\end{bmatrix} \times\begin{bmatrix}\cos\theta&\sin\theta\\\sin\theta&\cos\theta\end{bmatrix}$

---