LU 분해
LU 분해란? 아래의 형태를 갖는 두 행렬의 곱으로 나누는 행렬분해
A = L U
| * * * | | * 0 0 | | * * * |
| * * * | = | * * 0 | | 0 * * |
| * * * | | * * * | | 0 0 * |
Ax = b 문제를 LU 분해를 이용해 나타내면
Ax = b => (LU)x = b => L(Ux) = b => Ly = b (단, Ux= y)
1) Forward-substitution(전방대치법) : y 구하기
| * 0 0 | | y₁ | | * |
| * * 0 | | ... | = | * |
| * * * | | yn | | * |
* x y₁ + 0 + 0 + 0 + ... + 0 = *
2) Back-substitution(후방대치법) : x 구하기
| * * * | | x₁ | | y₁ |
| 0 * * | | ... | = | ... |
| 0 0 * | | xn | | yn |
LU 분해는 가우스 소거법의 forward elimination(전방소거법)을 행렬로 코드화 한 것이다.
L : 행렬 A를 전방소거하는데 쓰인 replacement와 scaling에 대한 EROs를 기록해 둔 행렬
U : 행렬 A를 전방소거한 후 남은 upper triangular matrix(상삼각행렬)
P : 행렬 A를 전방소거하는데 쓰인 interchange에 대한 EROs를 기록해 둔 행렬 (옵션)
LU 분해가 활용되는 이유
- 수치적 안정성 : 선형시스템 Ax = b의 해를 역행렬 A^-1를 이용해 직접 구하는 것보다 PLU 분해를 이용하는 것이 좀 더 수치적으로 안정적이다.
- b가 자주 업데이트되는 경우 : 선형 시스템 Ax = b에서 행렬 A는 고정되어 있고 b가 자주 변하는 문제가 종종 있다. 이런 경우, 행렬 A를 미리 PLU로 분해해 둔다면, b가 업데이트될 때마다 선형시스템의 해 x를 실시간으로 구할 수 있다.
행렬 표기법과 관련 용어
행렬(matrix)은 직사각형 구조에 숫자들을 담아 놓은 구조이다. 각 숫자들은 행렬의 요소(entry)라 부른다.
하나의 행 혹은 하나의 열을 가지는 특별한 행렬을 각각 행벡터(row vector), 열벡터(column vector)라 한다.
1x1 행렬은 스칼라(scalar)와 같다.
행렬의 주요 표기법
- 행렬 A의 각 (i, j) - 요소는 aij로 나타낸다.
- 행렬 A를 간략히 표기할 때는 A = [aij]로 나타낸다.
- 행렬 A의 크기가 중요할 경우는 A = [aij]mxn로 나타낸다.
전치행렬
m x n 행렬 A에 대한 transpose matrix(정치행렬) A^T는 A의 행을 열로, A의 열을 행으로 가지는 n x m 행렬이다. 즉, (A^T)ij = (A)ji를 만족한다.
벡터 표기법
벡터는 볼드체 소문자로 표기한다.
| x₁ |
x = | x₂ |
| ... |
- 벡터는 일반적으로 열벡터(column vector)를 말한다.
- n-벡터는 n개의 스칼라(scalar)로 구성된 벡터를 말한다.
영행렬 (Zero Matrices)
행렬의 모든 요소가 0이면, 해당 행렬을 영행렬(zero matrix)라고 하고 O로 표기한다.
A + O = O + A = A
n x n 행렬 : Square Matrix (정방행렬)
행과 열의 개수가 모두 n인 정사각형 모양의 행렬을 n차 정방행렬이라고 한다.
Identity Matrices (항등행렬)
주대각선(main diagonal)이 1이고 나머지 요소는 모두 0인 n차 정방행렬을 항등행렬이라 한다.
| 1 0 0 0 0 |
| 0 1 0 0 0 |
| 0 0 1 0 0 |
| 0 0 0 1 0 |
| 0 0 0 0 1 |
★ 행렬의 곱
ex)
| 1 2 | | 9 12 15 |
| 3 4 | | 1 2 3 | = | 19 26 33 |
| 5 6 | | 4 5 6 | | 29 40 51 |
A B
행렬의 곱에서 반드시 숙지해야할 사항
- 행렬 C의 각 요소 cij는 '곱의 왼쪽 행렬 A의 i번째 행벡터'와 '곱의 오른쪽 행렬 B의 j번째 열벡터'의 내적(inner product)이다.
- 따라서, 두 행렬 곱 AB에 대해 A의 열 개수와 B의 행 개수는 일치해야 한다.
- 일반적으로 AB ≠ BA이다. 왜냐하면 행과 열을 뽑아오는 방법이 다르기 때문이다.
- 행렬곱은 병렬처리(parallel processing)로 가속할 수 있다.
스칼라, 벡터, 행렬, 그리고 텐서 : 계층적 구조 이해하기
스칼라
숫자 하나로 구성되어 있다.
7
이 스칼라를 벡터로 표현하면 아래와 같이 1개의 구성요소로 이뤄진 1-벡터가 된다.
[7]
이 스칼라를 행렬로 표현하면 아래와 같이 1개의 구성요소로 이뤄진 1x1 행렬이 된다.
벡터
벡터는 여러 숫자가 일열로 늘어선 구조이다.
이 벡터를 행렬로 표현하면 다음과 같이 여러 모양의 행렬로 표현할 수 있다.
행렬
행렬은 사각형 구조에 여러 숫자가 행과 열로 늘어선 구조이다.
이 행렬은 다음과 같이 6-벡터로 표현할 수 있다.
텐서(Tensor)
텐서는 스칼라, 벡터, 행렬을 아우르는 개념이다. 숫자가 늘어설 수 있는 방향이 k개면 k-텐서로 부른다.
- 0-텐서 : 스칼라
- 1-텐서 : 벡터
- 2-텐서 : 행렬
만일 아래의 T의 각 요소 P(i,j)가 벡터라면, T는 3-텐서로 볼 수 있다.
3-텐서의 대표적인 예 = 컬러영상
P(i,j)가 3-벡터면 RGB 영상, 4-벡터면 RGBA 영상을 나타낸다고 볼 수 있음.
분할행렬(Partitioned Matrix)
행렬을 조각(partiton) 단위로 분할하여 생각해도 무방하다.
행렬은 부분행렬(submatrix)로 이뤄진 직사각형 구조로 확장해서 생각할 수 있다.
이렇게 행렬을 구조적으로 보는 방법을 분할행렬(partitoned matrix) 또는 블록행렬(block matrix)이라 한다.
분할행렬로 행렬의 곱 이해하기
두 행렬 곱 AB = C를 아래와 같이 matrix-column vector products로 볼 수 있다.
AB = A [ b₁ b₂ ... bn ] = [ Ab₁ Ab₂ ... Abn ] = C
ex)
| * * * | | * * | | * * |
| * * * | | * * | = | * * |
| * * |
A [ b₁ b₂ ] = [ Ab₁ Ab₂ ]
두 행렬의 곱 AB = C를 아래와 같이 row vector-matrix products로도 볼 수 있다.
| a₁ | | a₁B |
AB = | a₂ | B = | a₂B | = C
| ... | | ... |
| an | | anB |
| * * * | | * * | | * * |
| * * * | | * * | = | * * |
| * * |
| a₁ | B = | a₁B |
| a₂ | | a₂B |
선형조합(Linear Combination) : Ax는 A의 열벡터에 대한 선형조합
행렬은 열벡터의 리스트이다.
각 열벡터는 m-벡터이기 때문에, m x n 행렬은 m-벡터가 n개 있다 해석하면 된다.
행렬 @ 벡터
Ax는 행렬 A가 가지고 있는 열벡터의 선형조합이다.
선형대수에서는 이처럼 벡터들에 대한 가중치 합을 선형조합(linear combination)이라 부른다.
Column Space(열공간)
행렬 A의 열벡터들에 대한 가능한 모든 선형조합의 결과를 모아 집합으로 구성할 때, 이 집합을 column space(열공간)이라 하고 다음과 같이 표기한다.
col(A)
선형시스템 Ax = b가 해를 가지면(consistent), 다음을 만족한다.
b∈col(A)
선형시스템 Ax = b가 해가 없으면(inconsistent), 다음을 만족한다.
좌표계 변환 (Change of Basis)
벡터의 표현
벡터의 물리적 표현 (좌표계 없는 표현)
벡터 v를 화살표로 표현
- v의 크기 : 화살표의 길이
- v의 방향 : 화살표의 방향
벡터의 수학적 표현 (좌표계 있는 표현)
좌표계를 도입한 후, 벡터의 시작점을 원점맞추고 끝점의 위치를 벡터 v의 수학적 표현으로 정의한다.
- v의 크기 : 화살표의 길이를 계산
- v의 방향 : 화살표의 방향을 벡터로 표현
다음과 같이 2-벡터 v가 주어졌다고 하자.
이 벡터는 xy 평면 상 원점 (0,0)에서 시작하여 (a,b)에서 끝나는 벡터를 의미한다.
v = | a | = | 1 0 | | a | = a | 1 | + b | 0 |
| b | | 0 1 | | b | | 0 | | 1 |
x축으로 y축으로
내린 내린
수선의 발 수선의 발
두 벡터 v₁과 v₂를 이용해 새롭게 좌표계를 만들면 v의 좌표값은?
그림출처 : 프로그래머스 스쿨
새롭게 좌표계를 만든다는 말은 어떤 v에 도착하기 까지의 과정을 오롯이 v₁과 v₂를 몇 번 사용해 도착했는지 표현한다는 의미이다.
즉, v의 좌표값은 (4,3)이라고 한다.
4v₁ + 3v₂ = v
이 과정을 행렬로 표현하면 다음과 같다.
| v₁ v₂ | | 4 | = | 1 0 | | v | = | a |
| 3 | | 0 1 | | b |
v₁을 4번 써서 전진하고,
v₂를 3번 써서 전진했을 때
v라는 지점에 도착했다.
| v₁ v₂ | | 4 | = | e₁ e₂ | | a |
| 3 | | b |
우항 : e₁과 e₂를 기저(basis)로 가지는 표준좌표계(standard coordinate system)(x축과 y축)에서 벡터 v의 좌표값은 (a, b)이다.
좌항 : v₁과 v₂를 기저로 가지는 좌표계(coordinate system)에서 동리한 벡터 v의 좌표값은 (4, 3)이다.
선형시스템 문제를 좌표계 변환으로 바라보기
Ax = b
좌항 : A의 열벡터들을 기저로 가지는 좌표계에서는 동일 벡터의 좌표값은 x이다.
우항 : 표준좌표계에서 어떤 벡터의 좌표값은 b이다.
역행렬을 이용해 선형 시스템의 해를 구하는 문제를 좌표계 변환으로 바라보기
x = (A^-1)b
좌항 : 표준 좌표계에서 어떤 벡터의 좌표값은 x이다.
우항 : A^-1의 열벡터들을 기저로 갖는 좌표계에서는 동일 벡터의 좌표값은 b이다.
즉, 임의의 벡터(좌표값)는 다양한 좌표계에서 표현될 수 있다. (좌표계에 따라 다르게 표현될 수 있다.)
선형변환 (Linear Transformation)
함수(Functions)란?
초등 교과과정에서의 개념
상자(함)에 입력(input)이 들어가면 어떤 기능을 수행한 후 출력을 뱉어내는 블랙박스(black box)이다.
그림출처 : ko.wikipedia.org/wiki/%ED%95%A8%EC%88%98
중등 교과과정에서의 개념
함수는 두 집합 간의 맵핑룰(mapping rule)이다.
그림출처 : ko.wikipedia.org/wiki/%ED%95%A8%EC%88%98
왼쪽에 입력이 정의되는 집합을 D, domain(정의역)이라 한다. 출력이 정의되는 집합을 C, codomain(공역)이라 하며, codomain 중 실제 함수의 출력이 나오는 부분 집합은 range(치역)이라 한다.
함수 f는 아래 그림과 같이 D의 각 원소 x가 C의 한 원소 y(=f(x))에 대응되는 매핑룰이다. ( f : D -> C )
선형함수(linear function)
만일 함수 f가 아래 두 가지 조건을 만족하면 함수 f를 선형함수라 한다. (굳이 그리지 않아도 알 수 있다)
f(x+y) = f(x) + f(y)
f(cx) = cf(x) (단, c는 임의의 스칼라)
- 임의의 두 입력에 대해 ' + 연산을 먼저 수행한 결과를 함수 입력으로 넣고 함수를 수행한 결과'와 '각 입력에 대해 함수를 수행한 후 나온 결과에 대해 + 연산을 수행한 결과'는 같다.
- 임의의 입력에 대해, '스칼라 곱셈 연산을 먼저 수행한 다음 함수를 수행한 결과'와 '입력에 대해 함수를 수행한 후 나온 결과에 대해 스칼라 곱셈 연산을 수행한 결과'는 같다.
선형변환(linear transformation)
함수의 입력이 n벡터이고 출력이 m벡터인 함수 T가 있다고 하자.
이처럼 함수의 입출력이 벡터인 함수를 변환(transformation)이라 한다.
T : R^n -> R^m
n=m인 경우, 해당 변환을 연산자(operator)라 한다.
ex) MNIST 손글씨 인식
28x28 해상도의 손글씨 숫자영상을 그레이스케일로 받아, 0부터 9까지 어떤 숫자가 적혀있는지 알아내는 MNIST 손글씨 인식 문제는 다음과 같은 (비선형) 변환이다.
T : R^28 -> R^10
m x n 행렬 A에 대해 Ax는 n벡터를 입력으로 받아 m벡터를 출력으로 내는 변환
로 볼 수 있다. 이 변환은 행렬이 정의하기 때문에 행렬변환(matrix transformation)이라고 한다.
그런데 행렬변환은 선형함수 성질을 모두 만족하기 때문에 선형변환(linear transformation)이다.
단, x, y ∈ R^n이고 c는 임의의 스칼라다.
정리하자면, 임의의 선형변환은 행렬로 표현 가능하다. 즉, 행렬은 선형변환의 구현체이다.
행렬변환 코딩하기
- 구현하고자 하는 기능(function)의 입력과 출력이 벡터로 정의되는지 확인한다.
- 구현하고자 하는 기능이 선형인지 확인한다.
- 입력이 n벡터이고 출력이 m벡터이면 m x n 표준행렬(standard matrix)을 구성한다.
표준행렬(standard matrices) 구하기
- n차원 표준기저벡터 { e₁, e₂, ..., en }를 생각한다.
- 각 n차원 표준기저벡터 ei에 대해 우리가 원하는 기능을 동작시켜 얻은 결과인 m차원 벡터 T(ei)를 표준행렬의 각 열에 적는다.
ex) 2차원 벡터를 입력으로 받아, 해당 벡터를 x축에 프로젝션하는 기능을 구현하기 (가령, (3,2)를 지나는 벡터를 x축에 프로젝션한다고 하면 결과값으로 (3, 0)이 나오게 하도록 한다.)
첫 번째, 입력과 출력이 벡터로 정의되는가? ( O )
두 번째, 구현하고자 하는 기능이 선형인가? ( O )
세 번째, 입력이 2벡터이고 출력이 2벡터이다. 따라서 2x2 표준행렬이 구성 가능하다.
즉, | 1 0 | 이 선형변환 코딩의 함수 코드라는 것이다.
| 0 0 |
ex) 2차원 벡터를 입력으로 받아, 해당 벡터를 반시계방향으로 Θ만큼 회전하는 기능을 구현해 보자.
이처럼 내가 원하는 행렬을 표준행렬로 구할 수 있다.
'AI > KDT 인공지능' 카테고리의 다른 글
| [04/29] 인공지능 수학 - 확률과 확률분포 (0) | 2021.04.29 |
|---|---|
| [04/28] 인공지능 수학 - 자료의 정리 (0) | 2021.04.28 |
| [04/26] 인공지능 수학 - 가우스 소거법 (0) | 2021.04.27 |
| [04/26] 인공지능 수학 - 선형 시스템 (0) | 2021.04.26 |
| [4/26] 주피터 노트북 (0) | 2021.04.26 |
