벡터와 직교분해

$n$-벡터는 크기와 방향을 가진 물리량
$v = (v_1, v_2, \,\cdots, \, v_n)$
$v$의 크기 : $||v|| = \sqrt{v_1^2+v_2^2+\cdots+v_n^2}$
$v$의 방향 : ${1 \over||v||}v$

두 벡터 $u$와 $v$에 대한 내적
$u \cdot v = ||u||\,||v||\cos\theta$
$u \cdot v = u_1v_1+u_2v_2+\cdots u_nv_n$

두 벡터 $u, v$ 간의 내적이 0이면 두 벡터는 직교
$u \cdot v = 0 \Leftrightarrow u\bot v$

두 벡터 $u, a$가 있을 때, 벡터 $u$를 $a$ 위에 투영한 벡터를 proj$_au$라고 하면,
proj$_au = \begin{matrix}({u \cdot a \over||a||})&({1 \over ||a||}a)\\(길이)&(방향)\end{matrix} =\begin{matrix} ({u \cdot a \over ||a||^2})a \\(기저 a에 대한 좌표값)a\end{matrix}$

proj$_au$ 길이 = $||u|| \cos \theta = {u \cdot a \over ||a||}$ ( $\because u \cdot a = ||u||\,||a||\cos\theta$ )

proj$_au$ 방향은 $a$와 방향이 같고 길이가 1이므로 ${1 \over ||a||}a$

벡터 $u$를 $a$ 위에 투영하고 남은 보완 벡터(complemetn vector)는 $u \,-$ proj$_au$

두 벡터 $u, a$가 있을 때, 투영과 보완의 개념을 이용해 직교분할할 수 있다.
proj$_au \,\bot\, (u$ - proj$_au)$
$u =$ proj$_au + (u\, - \,$ proj$_au)$

직교행렬(orthogonal matrix)
주어진 행렬의 모든 열벡터가 서로 직교하는 행렬
$\begin{bmatrix} 1 & 4 \\ -2 & 2 \end{bmatrix}$ $\begin{bmatrix} 2 & 2 & -4 \\ 2 & 1 & 7 \\ 6 & -1 & -1\end{bmatrix}$

정규직교행렬(orthonormal matrix)
주어진 행렬이 직교행렬이고 모든 열벡터의 크기가 1인 행렬
$\begin{bmatrix} 1 \over \sqrt 5 & 2 \over \sqrt 5 \\ -{2\over \sqrt5} & 1\over \sqrt5 \end{bmatrix}$ $\begin{bmatrix} 1\over \sqrt11 & 2\over \sqrt 6 & -{4\over \sqrt66 } \\ 1\over \sqrt11 & 1\over \sqrt6 & 7\over \sqrt66 \\ 3\over \sqrt11 & -{1\over \sqrt6} & -{1\over \sqrt66} \end{bmatrix}$

선형시스템 $Ax = b$에서 행렬 $A$가 직교행렬이면, 해 $x$는 역행렬 $A^{-1}$의 계산 없이 다음과 같이 구할 수 있다.
$x$의 $i$-번째 요소는 투영으로 계산할 수 있다. 벡터 $b$를 행렬 $A$의 각 열벡터 $a_i$에 투영한 연산 proj$a_ib$로부터 $x_i = {b \cdot a_i \over ||a_i||^2}$를 계산할 수 있다.
$x$의 $i$-번째 요소와 $j$-번째 요소의 계산은 독립적이므로 $x$의 계산은 병렬처리 가능하다.

만약 행렬 $A$가 정규직교행렬이면 내적을 통해 계산할 수 있다.
벡터 $b$를 행렬 $A$의 각 열벡터 $a_i$에 투영한 연산 proj$a_ib$로부터 $x_i = b \cdot a_i$를 계산할 수 있다.

QR 분해
$A = QR$
$A$를 정규직교행렬과 나머지를 분해하는 것

$Ax = b \Rightarrow (QR)x = b \Rightarrow Q(Rx) = b \Rightarrow Qy = b$
1. 내적으로 y를 구한다. $Qy = b$
2. 후방대치법으로 x를 구한다. $Rx = y$

$Q$ : 행렬 $A$에서 정규직교성을 추출한 행렬
$R$ : 행렬 $A$에서 정규직교성 추출 후 남은 상삼각행렬

선형시스템의 해를 구할 때, 정규직교행렬 $Q$를 이용한 부분은 병렬처리로 빨리 계산할 수 있다. 그러나 $R$를 이용한 계산 부분은 병렬처리할 수 없다.

$QR$ 분해 vs $LU$ 분해
$LU$ 분해의 경우, 선형시스템을 풀 때 병렬처리 할 수 없다.
$QR$ 분해의 경우, $Q$ 행렬이 꽉찬 구조를 가진 행렬이므로 메모리 사용량이 많다.