QR 분해를 왜 사용해야 할까?

QR분해 너를 왜 써야하니?

LU분해와 다르게 QR분해는 해를 구할 때 substitution을 한번만 사용하여 구하는 방법이다.

$\bf Ax = b$ 라는 행렬이 존재 하는데, 우리는 $\bf x$를 구하고 싶다고 가정해보자.

일반적인 방법은 역행렬을 이용하는 아래의 방법이다. (A는 invertable하다.)

$\bf x = A^{-1}b$

하지만 역행렬을 직접적으로 구하는 것은 차원이 커질수록 시간 복잡도도 기하급수적으로 증가하며,

수치적인 안정성 역시 떨어진다.

그래서 우리는 역행렬을 직접 구하지 않고 시간복잡도가 선형이며, 수치적으로 안정적인 LU 분해나,

QR분해를 사용한다.

QR분해를 유도 하는 과정은 그람슈미트 과정을 거쳐야 하는데, 해당 부분은 아래 링크에서

더욱 자세하게 다루었으니 관심이 있다면 찾아보는 것도 좋다.

https://angeloyeo.github.io/2020/11/23/gram_schmidt.html

QR분해는 몇가지 나이스한 성질을 갖고 있다.

특히 Q부분에서 이 분해의 특징이 아주 잘 녹아 있다.

Normal orthogonal Matrix

이 정규 직교성이 갖는 장점은 어마무시하다.

이 직교성을 이용한다면 아래처럼 해를 직접적으로 구할 수 있다.

$\bf Qy = b \;\;\;\; \rightarrow\;\;\;\; y_i = q_i\bullet b$
$\bf Q = [q_1,\;q_2,\; ... \;,q_n]$

이러한 특성은 b벡터를 벡터 $\bf q_i$ 기저에 projection한 결과가 좌표값을 의미하기 때문에 활용 가능하다. (만약 정규직교가 아니라면, $\bf ||q_i||^2$로 나눠줘야 한다.)

일반화 한다면 아래와 같은 식이 유도 가능하다.

$\bf A = QR$ 라고 할때, $\bf R^TQ^TQRx = R^TQ^Tb$ 가 성립
$\bf Q$는 직교 or 정규 직교라고 할때, $\bf Q^TQ = I$ 이므로
$\bf R^TRx = R^TQ^Tb$ 가 성립 양변에 각각 $\bf R^T$ 의 역행렬을 곱해주면
$\bf Rx = Q^Tb$ 가 성립한다.

이제 $\bf Rx = y$ 로 놓고 $\bf y = Q^Tb$를 이용하여 y를 구한 후 $\bf Rx = y$를 back subtitution을 진행하면 우리가 원하는 x를 구할 수 있다.

QR분해 vs LU분해 둘중 뭐를 써야할까?

둘의 장단점은 명확하다.

QR분해는 메모리를 더 많이 소모하지만 LU분해에 비해서 더욱 빠르게 솔루션을 도출할 수 있고,
LU분해는 더 적은 메모리로 솔루션을 제공하지만 QR분해에 비해선 속도가 느리다.
(Q는 행렬에서 모두 숫자로 가득차 있는 반면 L은 반만 차있다.)

공통적인 장점은 수치적 안정성 및 병렬적으로 솔루션을 제공한다는 점이다.