행렬 분해(Decomposition) - QR 분해

 

 

성균관대학교 행렬이론 연구실

 

Made by Sang-Gu Lee with MyungGuk Baik

 

2. QR분해

 

정의 2.1 다음과 같은 형태의 행렬을 Householder 행렬이라 한다.

        (벡터 는 벡터가 아님)

 

보조정리 2.1 벡터 에 대하여 가 의 상수배가 되는 Householder 행렬 는 항상 존재한다.

 

증명) 를 다음과 같이 정의하면 가 의 상수배가 되는 것을 알 수 있다.

       , 라고 하면,

       이 되므로 는

       이 된다.

 

Algorithm 2.1

       Householder 행렬을 이용해 일부 벡터성분을 으로 만드는 법

   ,

 

Step 1 : , = 1, 2, ... ,

Step 2 : , = 1, 2, ... ,

Step 3 :

Step 4 :

Step 5 :

 

예제 2.1 행렬 가 다음과 같을 때,  

가 되는 를 찾아라.

(가   일 경우)

 

Sol) =4, =1.0308, =1, =0.25 그래서 =(1.0308, 1, 0.25), =-4.1232  따라서

 

 

2.1 Householder 행렬과 QR 분해(Factorization)

 

정리 2.1 (Householder QR 분해 정리)

주어진 × 행렬 에 대하여, = 이 되는 직교(orthogonal) 행렬 와 상삼각 행렬 이 존재한다. 행렬 는 다음과 같다.

(는 Householder 행렬). 이러한 분해를 행렬 의 QR분해 라 하다.

 

다음은 Householder행렬을 사용하여 행렬 를 분해 하는 방법이다.

 

Step 1: Householder행렬 은 의 첫 번째 열에서 (1, 1) 성분의 아래가 이 되도록 하는 행렬이라 하자.

즉,

이고  은 다음과 같은 행렬이다,

   그러면 이라 하고,

 

 

Step 2: Householder행렬 은 의 두 번째 열에서 (2, 2) 성분의 아래가 이 되도록 하는 행렬이라 하자.

 

  

는 다음과 같이 구할 수 있다. 우선 Householder행렬   

 =그리고

  그러면 이라 할 수 있다.

 

Step : 번째 단계에서의 다음과 같이 차수(order)가 ()인 Householder 행렬은

,

 

Step -1 : (-1)단계에서의, 는 상삼각 행렬 이 된다.  왜냐면,

, = -1, ... , 2

라 하자. 각 Householder 행렬 는 직교(orthogonal) 행렬 이므로  도 직교행렬이 된다.

 

그러므로 이 되어 =로 분해된다.  

 

 

 

예제 2.2  다음을 QR 분해 해 보자.

 

Step1 : = 1

은 다음을 만족한다.

,

 =

  따라서,

 

Step2 : = 2

,

, ,   

   : 상삼각(upper triangle) 행렬

: 직교(orthogonal) 행렬

 

2.2 Givens 행렬과 QR 분해의 응용

 

정의 2.2 다음과 같은 형태의 행렬을 Givens 행렬이라 한다.

  여기서

 

만약 라고 하면 Given 행렬은 로 나타낼 수 있다.

일반적으로 를 ( , ) 평면에서의 Givens rotation 또는 plane rotation 이라 부른다. 그리고 이므로 이 된다.

 

예제 2.3

이면 와 는 다음과 같다.

, 이고,

이 된다.

 

Algorithm 2.2 Givens 회전(Rotations)을 사용하여 행렬의 특정위치에 0을 만드는 법

 

Step 1 : 다음을 만족하는 을 구한다.

            

 

Step 2 : 로 를 대체 ; = 1,2,3, ... ,

           

           

          

           

 

예제 2.4

이라 할 때,   을 이용하여 (2, 1) 위치에 0을 만들어라.

 

Step 1: 우선 , 를 구하도록 한다.

 ,

 

Step 2 : 는 다음과 같다.

이므로

이 된다.

 

정리 2.2 (Givens QR 분해정리)

주어진  × 행렬 에 대하여, 직교행렬(orthogonal matrices),  s = (, -1)가 존재한다.

여기서 이다. 이라 하면 =이 된다.

 

정리 2.3 (QR의 유일성 정리)

행렬 A가 일차독립인 열을(linearly independent column) 갖는 × 행렬이라 하자. 그러면 = 형태를 만족하는 × 직교행렬 와 대각성분이 양인(positive diagonal) 상삼각 × 행렬 이 각각 유일하게 존재한다.

 

예제 2.5

의 분해중 상삼각 행렬 을 구하여라.

 

Step 1: 우선 , 를 구하도록 한다.

, =0, =1

 

또 다음과 같은 , 를 구하도록 한다.

, ,

Step 2 : 다음과 같은 , 를 구하도록 한다.

, ,

여기서 얻은 상삼각 행렬은 앞에서의 Householder 방법(예제 2.2)에 의해서 얻은 값과 비교해 첫 번째와 세 번째 행의 부호만 다르다.

 

 References

 

Biswa Nath Datta, Numerical Linear Algebra and Applications, An International Thomson Publishing Company, (1995)

 

Horn & Johnson, Matrix Analysis, Cambridge Univ. Press, 1993,

 

Golub and Van Loan, Matrix Computations,