[2주차 - Day2] 인공지능 수학 - 미적분(1)

3. LU 분해

---

행렬분해(matrix decomposition)

대표적인 행렬분해 3가지

• LU분해 (LU Decomposition)
• QR 분해 (QR Decomposition)
• 특이값 분해 (SVD; Singular Value Decomposition)

LU 분해 -> 가우스 소거법을 행렬의 형태로 나타낸 것

 

LU 분해

주어진 행렬을 아래의 형태를 가지는 두 행렬의 곱으로 나누는 행렬분해

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

LU 분해를 이용해 \( Ax = b \) 문제를 아래와 같이 나타내면,

$$ Ax = b \Rightarrow (LU)x = b \Rightarrow L(Ux) = b $$

$$\Rightarrow L{y} = b, (단, {y} = U{x})$$

 

선형 시스템을 다음과 같이 두 단계로 간단히 해결할 수 있다.

 

1) 전방대치법(Forward0substitution)

2) 후방대치법(Back-substitution)

LU 분해는 가우스 소거법의 전방 소거법을 행렬로 코드화 한 것
\( A = PLU \)

• \(L \) : 행렬 \( A \)를 전방소거하는데 쓰인 치환(Replacement)과 스케일링(Scaling)에 대한 EROs를 기록해 둔 행렬
• \( U \) : 행렬 \( A \)를 전방소거한 후 남은 상삼각행렬(Upper triangular matrix)
• \( P \) : 행렬 \( A \)를 전방소거하는데 쓰인 교환(Interchange)에 대한 EROs를 기록해 둔 행렬(옵션)

( EROs : elementary row operations: 기본행 연산)

 

LU 분해의 활용

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

 

4. 행렬연산과 선형조합

---

행렬 표기법과 관련 용어

행렬(matrix) : 직사각형 구조에 숫자들을 담아 놓은 구조이다. 각 숫자들은 행렬의 요소(Entry)라고 한다.

$$\begin{bmatrix}
3 & 1 \\
1 & -2 \\
2 & -4
\end{bmatrix}$$

벡터(vector) : 하나의 행 혹은 하나의 열을 가지는 행렬. 행벡터(row vector)와 열벡터(column vector)가 있다.
$$\begin{bmatrix}
2 & 1 & 0 & 3 \end{bmatrix}
\begin{bmatrix}
1 \\
3 \\
\end{bmatrix}$$

스칼라(scalar) : 행과 열 모두 하나인 1 x 1 행렬
$$ \begin{bmatrix} 4 \end{bmatrix}$$

주요 표기법
$$A=\begin{bmatrix}
a_{11}&a_{11}&\dots&a_{1j}&\dots&a_{1n}\\
a_{21}&a_{22}&\dots&a_{2j}&\dots&a_{2n}\\
\vdots&\vdots&&\vdots&&\vdots\\
a_{i1}&a_{i2}&\dots&a_{ij}&\dots&a_{in}\\
\vdots&\vdots&&\vdots&&\vdots\\
a_{m1}&a_{m2}&\dots&a_{mj}&\dots&a_{mn}
\end{bmatrix}

$$

• 행렬 \( A\)의 각 \( (i, j) \)요소는 \(a_{ij} \)로 나타낸다.
• 행렬 \( A\)를 간략히 표기할 때는 \(A = \begin{bmatrix} a_{ij} \end{bmatrix} \)로 나타낸다.
• 행렬 \( A\)의 크기가 중요할 경우는 \(A = \begin{bmatrix} a_{ij} \end{bmatrix}_{m\times n} \)로 나타낸다.

 

벡터(Vector)

벡터는 아래의 x와 같이 볼드체 소문자로 표기한다.
$$\boldsymbol{x}=
\begin{bmatrix} x_1\\
x_2\\
\vdots\\
x_n
\end{bmatrix}

$$

• 벡터라고 하면 일반적으로 열벡터(column vector)를 말한다.
• \( n\)-벡터는 \( n\)개의 스칼라(scalar)로 구성된 벡터를 말한다.

 

전치행렬(Transpose Matrix)

\({m\times n} \)행렬 \(A \)에 대한 전치행렬 \(A^{T} \)는 \(A\)의 행을 열로,
\(A \)의 열을 행으로 가지는 \( {m\times n}\)행렬이다.
즉, \( (A^{T}){ij} = (A){ji} \)를 만족한다.
Ex)
$$
A = \begin{bmatrix} 1 & 2 \\ 3 & 4\\ 5 & 6 \end{bmatrix}
A^{T} = \begin{bmatrix} 1 & 3 & 5 \\ 2 & 4 & 6 \end{bmatrix}
$$

 

 

영행렬(Zero matrix)

행렬의 모든 요소가 0이면, 해당 행렬을 영행렬(Zero matrix)라 하고 \( O \)으로 표현한다.
$$ A + O = O + A = A $$
영행렬은 숫자의 0과 같은 존재로 **행렬의 합에 대한 항등원 역할을 한다.
행렬의 합 : 합과 열의 개수가 모두 같은 두 행렬 \(A\)와 \(B\)에 대해서, 각 \((i, j)\) 요소의 합으로 정의된다.

 

 

정방행렬(Square matrix)

행과 열의 갯가 모두 N인 정사각형(Square) 모양의 행렬을 N차 정방행렬(Square matrix)라 한다.

특히, \( a_{ii} ( i = 1,2, ..., n) \)를 행렬 \(A_n\)의 주대각선(main diagonal)이라 한다.

 

 

항등행렬(Identity matrix)

주대각선이 1이고, 나머지 요소는 모두 0인 N차 정방행렬을 항등행렬(Identity amtrix)라 한다.

항등행렬은 숫자의 1과 같은 존재로 행렬의 곱에 대한 항등원 역할을 한다.

 

 

행렬의 곱

\({m\times r}\) 행렬 \(A = \begin{bmatrix} a_{ij} \end{bmatrix}\)와 \({r\times n}\) 행렬 \(B = \begin{bmatrix} b_{ij} \end{bmatrix}\)가 있을 때, 두 행렬의 곱 \(AB\)는 아래와 같은 \({m\times n}\) 행렬 \(C = \begin{bmatrix} c_{ij} \end{bmatrix}\)를 정의한다.

행렬의 곱에서 반드시 숙지해야할 사항

• 행렬 \(C\)의 각 요소 \(c_{ij}\)는 '곱의 왼쪽 행렬 \(A\)의 \(i\)번째 행벡터'와 곱의 오른쪽 행렬 \(B\)의 \(j\)번째 열벡터'의 내적(inner product)이다.
  • 따라서, 두 행렬의 곱 \(AB\)에 대해 \(A\)의 열 개수와 \(B\)의 행 개수는 일치해야 한다.(\(A_{m\times r}, B_{r\times n}\))
  • 일반적으로 \(AB \not= BA \)이다. 왜냐하면 행과 열을 뽑아오는 방법이 다르기 때문에
• 행렬의 곱은 **병렬처리(parallel processing)으로 가속할 수 있다.
  (행렬 \(A\)의 각 행과 행렬 \(B\)의 각 열은 연산에 독립적이다.)

 

계층적 구조 이해하기 - 텐서

• 스칼라
• 벡터
• 행렬
• 텐서

스칼라 → 백터 → 행렬
스칼라는 숫자 하나로 구성되어 있다.
$$ 7 $$

이 스칼라를 백터로 표현하면 1개의 구성요소로 이루어진 1-벡터가 된다.
$$ \begin{bmatrix} 7 \end{bmatrix} $$

이 스칼라를 행렬로 표현하면 1개의 구성요소로 이루어진 1 x 1 행렬이 왼다.
$$ \begin{bmatrix} 7 \end{bmatrix}_{1\times 1} $$

 

---

벡터 → 행렬

벡터는 여러 숫자가 일열로 늘어선 구조이다.
$$ \begin{bmatrix}
1 \\
2 \\
3 \\
4
\end{bmatrix}
$$

이 벡터를 행렬로 표현하면 여러 모양의 행렬로 표현할 수 있다.

표현하고자 하는 행렬의 모양은 응용문제에 따라 결정한다.

 

---

행렬 → 벡터

행렬은 사각형 구조에 여러 숫자가 행과 열로 늘어선 구조이다.
$$ \begin{bmatrix}
1 & 2 & 3 \\
4 & 5 & 6
\end{bmatrix}_{2\times 3}
$$

이 행렬을 벡터로 표현하면 6-벡터로 표현할 수 있다.

​행렬을 벡터로 변환할 때, 행부터 혹은 열부터 읽을 것인지는 응용문제에 따라 결정한다.

---

텐서

텐서(tensor)는 스칼라, 벡터, 행렬을 아우르는 개념이다.

숫자가 늘어설 수 있는 방향이 k개면 k-텐서로 부른다.

• 0-텐서: 스칼라
• 1-텐서: 벡터 # 행 또는 열
• 2-텐서: 행렬 # 행과 열
  만일 아래의 \(T\)의 각 요소 \(P(i,j)\)가 벡터라면, \(T\)는 3-텐서로 볼 수 있다.

3-텐서의 대표적인 예는 컬러영상이다. \(P(i,j)\)가 3-벡터이면 RGB 영상을, 4-벡터이면 RGBA 영상을 나타낸다고 볼 수 있다.

 

4-텐서는?
→ 컬러영상이 시간을 가지는 경우가 된다. (동영상)

 

 

분할행렬(Partitioned Matrix)

행렬을 조각(partition) 단위로 분할하여 생각해도 무방하다.

이런 관점에서 본다면, 행렬은 부분행렬(submatrix)로 이루어진 직사각형 구조로 확장해서 생각할 수 있다.

두 가지 관점

• 행렬은 행백터로 이루어진 열벡터이다.
• 행렬은 열벡터로 이루어진 행벡터이다.(2번째 관점이 일반적!)

이렇게 행렬을 구조적으로 보는 방법은 분할행렬(partitioned matrix) 또는 블록행렬(block matrix)이라 한다.

 

 

분할행렬로 행렬의 곱 이해하기

• 행렬-열벡터 내적(matrix-column vector products)

 

• 행벡터-행렬 내적(row vector-matrix products)

 

선형조합(Linear Combination)

행렬 * 벡터 ⇒ 선형조합

행렬을 구조적으로 바라보는 가장 효과적인 방법은

행렬을 열벡터의 리스트로 보는 것이다.

여기서 \(a_i\)는 행 \(A\)의 \(i\)-번째 열벡터이다.

특히 각 열벡터는 \(m\)-벡터이기 때문에, \({m\times n}\) 행렬은 \(m\)-벡터가 \(n\)개 있다고 해석하면 된다.

 

\(Ax=b\) 에서

\(Ax\)는 행렬 \(A\)가 가지고 있는 열벡터의 선형조합이다.

선형대수에서는 이처럼 벡터들에 대한 가중치 합을 특히 선형조합(linear combination)이라 부른다.

 

Ax의 결과는 행렬 A가 가지고 있는 열벡터의 선형조합으로만 한계가 지어진다

가중치 합을 했는데 우항을 절대로 만들어낼 수 없다?

→ 그것을 만족하는 x가 존재하지 않는다.

 

선형시스템 Ax=b 를 선형조합 관점에서 바라보기

행렬 A의 열벡터의 가중치 합으로 선형조합할 때 벡터 b를 만들 수 있는 가중치 조합이 존재한다면,

선형시스템 \(Ax=b\) 의 해는 존재한다. 그 해는 가중치 \(x_i\)들로 구성된 \(x\)이다.

 

 

열공간(Column Space)

행렬 A의 열벡터들에 대한 가능한 모든 선형조합의 결과를 모아 집합으로 구성할 수 있을 것이다.

이것을 열공간(Column Space)라고 하고 다음과 같이 표기한다.

$$col(A)$$
선형시스템 \(Ax=b\)의 해가 존재하면(consistent), \(b \in col(A)\)를 만족한다.
선형시스템 Ax=b의 해가 없으면(inconsistent), \(b \notin col(A)\)를 만족한다.

3차원 공간에서의 예제

1. 행렬 A의 col(A)는 3-차원 공간

선형 시스템 \(Ax=b\)를 구성할 때

어떤 3-벡터 \(b\)를 이용하더라도 해당 선형시스템의 해는 존재한다.

 

2. 행렬 \(A\)의 \(col(A)\)는 \(xy\)-평면

선형시스템 \(Ax=b\)를 구성할 때

• \(xy\)-평면 상의 3-벡터 \(b\)를 이용하면, 해당 선형시스템의 해는 존재하지만,
• \(xy\)-평면을 벗어난 3-벡터 \(b\)를 이용하면, 해당 선형시스템의 해는 존재하지 않는다.