5.4. QR법 / 5.5. 역반복법

5.4.1. QR법의 원리

 

QR법의 반복

• 고윳값을 구하고 싶은 행렬을 QR 분해한다.
• 분해한 결과를 역순으로 곱한다.
• 곱한 결과를 또 QR 분해한다.
• 분해한 결과를 역순으로 곱한다.
• 이를 반복하면 A_k는 A_0의 고윳값을 대각성분으로 지니는 우상삼각행렬에 가까워진다.

 

QR법의 반복은 닮음 변환

• 행렬을 QR 분해하여 역순으로 곱하는 것은 행렬을 QR 분해하여 얻은 직교행렬을 닮음변환하는 것이다.
• 고윳값은 변하지 않는다.

 

왜 우상삼각행렬로 향하는가

• QR법과 거듭제곱법의 모든 고윳값을 구하는 경우에서 단위행렬을 초깃값으로 한 경우는 k스텝의 값 A_k는 같다.

 

 

5.4.2. 헤센버그 행렬

 

우선 닮음변환으로 해센버그(Hessenberg) 행렬이라는 형태로 변환하고 나서 QR 반복을 시행

• 헤센버그 행렬은 QR 반복을 시행해도 헤센버그 행렬 그대로이다.
• 따라서 계산량을 줄일 수 있다.
• 우상삼각행렬의 대각성분보다 하나 아래 위치까지 0이 아닌 성분이 있는 정방행렬

 

 

5.4.3. 하우스홀더 법

 

거울변환

• 공간의 임의의 점 x를 원점을 지니는 초평면에 대해 대칭인 점 x'로 옮기는 변환

• H도 대칭행렬이다.
• H^2 = I, H가 자기 자신의 역행렬이다.
• H는 직교행렬이다.

 

4x4 행렬의 경우로 생각한다.

• 4x4 행렬의 경우 2열까지 헤센버그 상태가 되면 헤센버그 행렬이므로 2스텝에서 종료

 

 

5.4.4. 헤센버그 행렬의 QR 반복

• 실제 QR법의 반복계산에서는 그람-슈미트 방법에 기초한 QR 분해 계산은 하지 않는다.

 

 

5.4.5. 원점이동, 감차

 

원점이동

• 고윳값의 추정값을 준비하고, A - 추정값*I 에 대해 QR 법을 반복 시행한다.

 

감차

• 마지막 행과 마지막 열을 제외한 3x3 godfufdp eogks rPtksdmf thrgod

 

순서를 반복하여 최종적으로 모든 고윳값을 구할 수 있다.

 

 

 

5.4.6. 대칭행렬의 경우

 

일반 대칭행렬에 대해 하우스홀더법을 적용하면 대칭인 헤센버그 행렬, 즉 삼중대각행렬이 된다.

• 여기에 QR법을 반복 시행하면 대칭인 우상삼각행렬, 즉 대각행렬에 가까워진다.
• 이때의 대각성분이 고윳값이다.

 

 

5.5. 역반복법

 

• A는 고윳값에 대응하는 고유벡터를 구하고, 이를 토대로 고윳값 추정치보다 정밀도가 높은 고윳값을 구할 수 있다.

 

 

 

출처: 히라오카 카즈유키, 호리 겐, 『프로그래머를 위한 선형대수』, 이창신, 길벗, 2017.