위키득계정 ↗
과학

QR 반복법

QR 반복법과학
영문명
QR iteration
분해 단계
A(k) = Q(k)R(k)
갱신 단계
A(k+1) = R(k)Q(k)
보존하는 값
고유값
QR 반복법은 행렬을 QR로 분해한 뒤 두 인자의 순서를 바꿔 곱하는 과정을 반복하는 고유값 계산법이다. 기본형은 A(k) = Q(k)R(k), A(k+1) = R(k)Q(k)로 쓴다. 각 단계는 고유값을 보존하는 닮음 변환이다.

순서를 바꿔도 고유값이 남는 이유

Q가 유니터리 행렬이면 Q* A(k) Q = RQ다. 따라서 다음 행렬은 원래 행렬과 닮음 관계다. 행렬의 원소는 바뀌지만 같은 고유값 문제를 다른 좌표계에서 다루는 것이다.

한 번 갱신해 보기

두 행이 (2,1), (1,2)인 행렬을 생각하자. Q를 두 행이 (2,-1)/√5, (1,2)/√5인 행렬로 두고 R의 두 행을 (√5,4/√5), (0,3/√5)로 두면 QR가 원래 행렬이다. RQ의 두 행은 (14/5,3/5), (3/5,6/5)가 된다.

대각 원소가 곧 답은 아니다

예제의 원래 고유값은 3과 1이다. 한 번 갱신한 대각 원소 14/5와 6/5는 아직 그 값과 같지 않다. 하지만 대각 원소의 합은 여전히 4이고 행렬식은 3이다. 중간 단계의 대각 원소를 최종 고유값이라고 단정할 수 없다.

기본 반복만으로 충분하지 않은 경우

두 행이 (0,-1), (1,0)인 회전 행렬은 Q를 그 행렬, R을 단위행렬로 잡을 수 있다. 그러면 RQ가 그대로여서 이 선택의 기본 반복은 변하지 않는다. 모든 행렬이 이 단순한 반복으로 대각행렬에 수렴한다고 기대하면 안 된다. 일반 실수 행렬의 슈어 형식에는 이차 블록이 남을 수도 있다.

관련 문서

QR 분해 / 슈어 분해 / 고유값 / 행렬식 / 대각화 / 직교행렬 / 헤센베르크 행렬