QR Factorization은 행렬의 column들이 만드는 공간은 유지하면서, 그 공간의 Orthonormal Basis와 coordinate 정보를 분리하는 방법이다.
의 column들이 Linearly Independent하고 이라고 하자. 그러면
로 분해할 수 있다. Reduced QR에서
이며 의 column들은 Orthonormal하고 은 Upper Triangular Matrix이다.
따라서
이다.
Q와 R의 의미
라고 하자.
의 column들은 의 Orthonormal Basis이다.
의 번째 column은 를 Basis로 표현한 coordinate이다.
는 처음 개의 Orthonormal Vector로 표현되므로 대각선 아래의 coefficient는 0이다. 따라서 이 upper triangular이다.
Gram-Schmidt에서 QR 만들기
Gram-Schmidt Process를 의 column에 적용한다.
두 번째 column은
이다.
일반적으로
이다.
예제
이다.
첫 번째 column은
이다.
두 번째 column에 대해
이고
이다.
이므로
이다. 직접 곱하면 이 확인된다.
Reduced QR과 Full QR
Reduced QR은
이다.
Full QR은 의 column을 의 Orthonormal Basis가 되도록 확장한다.
Least Squares에는 Reduced QR만으로 충분하다.
QR로 Least Squares 풀기
Full Column Rank인 에서
를 생각한다. 이면
이고 Normal Equation은
이다. 이 invertible하므로
를 얻는다. Upper Triangular System이므로 Back Substitution으로 계산한다.
를 직접 만들면 condition number가 제곱되어 numerical error가 커질 수 있다. QR 방식은 Normal Equation보다 안정적이다.
Householder QR
Gram-Schmidt는 개념을 이해하기 쉽지만 실제 수치 계산에서는 Householder Reflection을 많이 사용한다.
Householder Matrix는
형태의 Orthogonal Matrix이다. column 아래의 성분을 한 번에 0으로 만들어 을 구성한다. 여러 Householder Matrix의 곱이 가 된다.
정리
- QR Factorization은 이다.
- 의 column은 의 Orthonormal Basis이다.
- 이며 Upper Triangular Matrix이다.
- Gram-Schmidt는 QR Factorization의 기본 구성 원리이다.
- Least Squares는 로 풀 수 있다.
- 실제 계산에서는 Modified Gram-Schmidt나 Householder QR이 안정적이다.
확인 문제
다음 행렬의 Reduced QR Factorization을 구한다.
풀이
이다.
따라서
이고
이다.