수치 선형 대수(numerical linear algebra)에서, QR 알고리듬(QR algorithm) 또는 QR 반복(QR iteration)은 고윳값 알고리듬(eigenvalue algorithm)입니다: 즉, 행렬의 고윳값과 고유벡터를 계산하는 절차입니다. QR 알고리듬은 1950년대 후반 John G. F. Francis와 Vera N. Kublanovskaya에 의해 독립적으로 연구하여 개발되었습니다. 기본 아이디어는 QR 분해(QR decomposition)를 수행하여, 행렬을 직교 행렬(orthogonal matrix)과 위쪽 삼각 행렬(triangular matrix)의 곱으로 쓰고, 인수를 반대 순서로 곱하고, 반복하는 것입니다.
The practical QR algorithm
형식적으로, A를 고윳값을 계산하기를 원하는 실수 행렬로 놓고, \(A_0:=A\)로 놓습니다. k-번째 단계 (k = 0으로 시작)에서, QR 분해 \(A_k=Q_k R_k\)를 계산하며, 여기서 \(Q_k\)는 직교 행렬 (즉, \(Q^{\text{T}} = Q^{-1}\))이고 Rk는 위쪽 삼각 행렬입니다. 그런-다음 \(A_{k+1}=R_k Q_k\)를 형성합니다. 다음임을 주목하십시오:
\(\quad\displaystyle A_{k+1} = R_k Q_k = Q_k^{-1} Q_k R_k Q_k = Q_k^{-1} A_k Q_k = Q_k^{\mathsf{T}} A_k Q_k, \)
따라서 모든 \(A_k\)는 닮은 것이고 따라서 같은 고윳값을 가집니다. 알고리듬은 직교 닮음 변환에 의해 진행되므로 수치적으로 안정적입니다.
특정 조건 아래에서, 행렬 \(A_k\)는 A의 슈어 형식(Schur form), 삼각 행렬로 수렴합니다. 삼각 행렬의 고윳값은 대각선에 나열되고, 고윳값 문제가 해결됩니다. 수렴에 대한 테스트에서, 정확한 영들을 요구하는 것은 비실용적이지만, 게르시고린 원 정리(Gershgorin circle theorem)는 오차에 대한 경계를 제공합니다.
이 조잡한 형식에서, 반복이 상대적으로 비용이 많이 듭니다. 이것은 먼저 행렬 A를 양-측 QR 분해와 약간 같은 직교 닮음 변환의 유한 수열과 함께 위쪽 헤센베르크 형식(Hessenberg form, 이는 하우스홀더 감소에 기반을 둔 기술을 사용하여 \(\displaystyle \begin{matrix}\frac{10}{3}\end{matrix} n^3 + \mathcal{O}(n^2)\) 산술 연산 비용이 듭니다)으로 가져옴으로써 완화될 수 있습니다. (QR 분해에 대해, 하우스홀더 반사기는 왼쪽에만 곱해지지만, 헤센베르크 경우에 대해 그것들은 왼쪽과 오른쪽 모두 곱해집니다.) 위쪽 헤센베르크 행렬의 QR 분해를 결정하는 것은 \(\displaystyle 6 n^2 + \mathcal{O}(n)\) 산술 연산 비용이 듭니다. 더욱이, 헤센베르크 형식은 이미 거의 위쪽-삼각이므로 (그것은 각 대각선 아래에 단지 하나의 비-영 엔트리를 가짐), 이를 시작점으로 사용하면 QR 알고리듬의 수렴에 필요한 단계의 숫자가 줄어듭니다.
만약 원래 행렬이 대칭(symmetric)이면, 위쪽 헤센베르크 행렬도 대칭이고 따라서 삼중대각(tridiagonal)이고 모든 \(A_k\)도 마찬가지입니다. 이 절차는 하우스홀더 감소를 기반으로 둔 기술을 사용하여 \(\displaystyle \begin{matrix}\frac{4}{3}\end{matrix} n^3 + \mathcal{O}(n^2)\) 산술 연산 비용이 듭니다. 대칭 삼중대각 행렬의 QR 분해를 결정하는 것은 \(\displaystyle \mathcal{O}(n)\) 연산 비용이 듭니다.
수렴의 율은 고윳값 사이의 분리에 따라 달라지므로, 실제 알고리듬은 명시적 또는 암시적 이동을 사용하여 분리를 늘리고 수렴을 가속화합니다. 전형적인 대칭 QR 알고리듬은 한두 번의 반복만으로 각 고윳값을 분리하며 (그때에 행렬의 크기를 줄어듬), 알고리듬을 효율적이면서 견고하게 만듭니다.
Visualization
기본 QR 알고리듬은 A가 양수-한정 대칭 행렬인 경우에 시각화될 수 있습니다. 이 경우에서, A는 2차원에서 타원(ellipse)으로, 또는 더 높은 차원에서 타원면체(ellipsoid)로 묘사될 수 있습니다. 알고리듬에 대한 입력과 단일 반복 사이의 관계가 그런-다음 그림 1과 같이 묘사될 수 있습니다 (애니메이션을 보려면 클릭하십시오). LR 알고리듬은 QR 알고리듬과 나란히 표시됨에 주목하십시오.
단일 반복으로 인해 타원이 x-축 방향을 향해 기울어지거나 "떨어집니다". 타원의 큰 반-축(semi-axis)이 x-축과 평행한 경우에서, QR을 한 번 반복해도 아무 일도 일어나지 않습니다. 알고리듬이 "아무것도 하지 않는" 또 다른 상황은 큰 반-축이 x-축 대신 y-축과 평행할 때입니다. 해당 경우에서, 타원은 어느 방향으로도 떨어지지 않고 위태롭게 균형을 이루고 있는 것으로 생각될 수 있습니다. 두 상황 모두에서, 행렬은 대각입니다. 알고리듬의 반복이 "아무것도 하지 않는" 상황은 고정된 점(fixed point)이라고 불립니다. 알고리듬에 의해 사용되는 전략은 고정된-점을 향한 반복입니다. 한 고정된 점은 안정적이고 반면 나머지 다른 것은 불안정하다는 것을 관찰하십시오. 만약 타원이 불안정한 고정된 점에서 아주 작은 양만큼 기울어졌으면, QR을 한 번 반복하면 타원이 고정된 점을 향하는 대신 고정된 점에서 멀어지는 방향으로 기울게 됩니다. 결국 알고리듬은 다른 고정된 점으로 수렴되지만, 시간이 오래 걸립니다.
Finding eigenvalues versus finding eigenvectors
대칭 행렬의 단일 고유벡터를 찾는 것도 계산할 수 없다는 점을 지적할 가치가 있습니다 (계산-가능 분석의 정의에 따른 정확한 실수 산술에서). 이 어려움은 행렬의 고윳값의 중복도를 알 수 없을 때마다 존재합니다. 다른 한편으로, 고윳값을 찾는 데에는 같은 문제가 존재하지 않습니다. 행렬의 고윳값은 항상 계산 가능합니다.
이제 이들 어려움이 기본 QR 알고리듬에서 어떻게 나타나는지 논의할 것입니다. 이것은 그림 2에 묘사되어 있습니다. 타원은 양수-한정 대칭 행렬을 나타냄을 상기하십시오. 입력 행렬의 두 고윳값이 서로 가까워질 때, 입력 타원이 원으로 변경됩니다. 원은 단위 행렬의 배수에 해당합니다. 가까운-원은 그 고윳값이 행렬의 대각선 엔트리와 거의 같은 항등 행렬의 거의-배수에 해당합니다. 그러므로 해당 경우에서 고윳값을 근사적으로 찾는 문제는 쉬운 것으로 나타납니다. 그러나 타원의 반-축에 무슨 일이 일어나는지 주목하십시오. QR (또는 LR)의 반복은 입력 타원이 원에 가까워짐에 따라 반-축을 점점 더 적게 기울입니다. 고유벡터는 반-축이 x-축 및 y-축과 평행할 때만 알 수 있습니다. 입력 타원이 원형에 가까워질수록 거의 평행성을 달성하는 데 필요한 반복 횟수는 경계 없이 증가합니다.
임의적인 대칭 행렬의 고유분해(eigendecomposition)를 계산하는 것은 불가능할 수 있지만, 행렬을 임의적으로 작은 양으로 교란하고 결과 행렬의 고유분해를 계산하는 것은 항상 가능합니다. 행렬이 가까운-원으로 표현되는 경우에서, 행렬은 완전 원으로 표현되는 행렬로 대체될 수 있습니다. 해당 경우에서, 행렬은 항등 행렬의 배수이고, 고유분해는 즉각적입니다. 하지만 결과 고유기저(eigenbasis)가 원래 고유기저와 상당히 멀리 떨어져 있을 수 있다는 점에 유의하십시오.
Speeding up: Shifting and deflation
타원이 더 원형이 될 때 속도가 느려지는 것은 반대입니다: 타원이 더 많이 늘어나고 원형이 줄어들면 타원의 회전이 더 빨라지는 것으로 나타났습니다. 그러한 뻗기는 타원이 나타내는 행렬 \(\displaystyle M\)이 \(\displaystyle M-\lambda I\)로 대체될 때 유도될 수 있으며, 여기서 \(\displaystyle \lambda\)는 근사적으로 \(\displaystyle M\)의 가장 작은 고윳값입니다. 이 경우에서, 타원의 두 반-축의 비율은 \(\displaystyle \infty\)에 접근합니다. 더 높은 차원에서, 이와 같이 이동하는 것은 타원면체의 가장 작은 반-축의 길이를 다른 반-축에 비해 작아지고, 이로 인해 가장 작은 고윳값으로의 수렴 속도가 빨라지지만, 다른 고윳값으로의 수렴 속도는 빨라지지 않습니다. 이것은 가장 작은 고윳값이 완전히 결정될 때 쓸모가 없으므로, 그 행렬은 그때에 수축(deflated)되어야 하며, 이는 단순히 마지막 행과 열을 제거하는 것을 의미합니다.
불안정한 고정된 점을 갖는 문제도 해결되어야 합니다. 이동 휴리스틱은 종종 이 문제도 처리하도록 설계됩니다: 실제 이동은 종종 불연속적이고 무작위적입니다. 우리가 시각화하고 있는 것과 같은 대칭 행렬에 매우 적합한 윌킨슨의 이동은 특히 불연속적입니다.
The implicit QR algorithm
현대의 계산 실습에서, QR 알고리듬은 암시적 버전으로 수행되며, 이는 다중 이동의 사용을 더 쉽게 도입하도록 만듭니다. 행렬은 먼저 명시적 버전에서와 같이 위쪽 헤센베르크 형식 \(\displaystyle A_0=QAQ^{\mathsf{T}}\)로 가져옵니다; 그런 다음, 각 단계에서, \(\displaystyle A_k\)의 첫 번째 열은 작은-크기 하우스홀더 닮음 변환을 통해 \(\displaystyle p(A_k)\) (또는 \(\displaystyle p(A_k)e_1\))의 첫 번째 열로 변환되며, 여기서, 차수 \(\displaystyle r\)의, \(\displaystyle p(A_k)e_1\)는 이동 전략을 정의하는 다항식이며 (종종 \(\displaystyle p(x)=(x-\lambda)(x-\bar\lambda)\), 여기서 \(\displaystyle \lambda\)와 \(\displaystyle \bar\lambda\)는 \(\displaystyle A_k\)의 후행 \(\displaystyle 2 \times 2\) 주요 부분행렬의 두 고윳값이며, 소위 암시적 이중-이동(implicit double-shift)입니다). 그런-다음 작업 행렬 \(\displaystyle A_k\)를 위쪽 헤센베르크 형식으로 반환하기 위해 크기 \(\displaystyle r+1\)의 연속적인 하우스홀더 변환이 수행됩니다. 이 연산은 알고리듬의 단계에 따른 행렬의 비-영 엔트리의 독특한 모양으로 인해 부풀림 추적(bulge chasing)으로 알려져 있습니다. 첫 번째 버전에서와 마찬가지로, \(\displaystyle A_k\)의 하위-대각선 엔트리 중 하나가 충분히 작자마자 수축이 수행됩니다.
Renaming proposal
최신 암시적 버전의 절차에서는 QR 분해(QR decompositions)가 명시적으로 수행되지 않기 때문에, Watkins와 같은 일부 저자는 이름을 Francis algorithm으로 변경할 것을 제안했습니다. Golub과 Van Loan은 Francis QR step이라는 용어를 사용합니다.
Interpretation and convergence
QR 알고리듬은 기본 "거듭제곱" 고윳값 알고리듬의 보다 정교한 변형으로 볼 수 있습니다. 거듭제곱 알고리듬은 A에 단일 벡터를 반복적으로 곱하여, 각 반복 후에 정규화한다는 점을 기억하십시오. 벡터는 가장 큰 고윳값의 고유벡터로 수렴합니다. 대신, QR 알고리듬은 QR 분해를 사용하여 재정규화 (및 직교화)하는 벡터의 완전한 기저로 작동합니다. 대칭 행렬 A에 대해, 수렴 시 AQ = QΛ이며, 여기서 Λ는 A가 수렴한 고윳값의 대각 행렬이고, Q는 거기에 도달하는 데 필요한 모든 직교 닮음 변환의 합성입니다. 따라서 Q의 열은 고유벡터입니다.
History
QR 알고리듬은 QR 분해 대신 LU 분해를 사용하는 LR 알고리듬이 선행되었습니다. QR 알고리듬은 더 안정적이므로, 요즘에는 LR 알고리듬이 거의 사용되지 않습니다. 어쨌든, 그것은 QR 알고리듬 개발에서 중요한 단계를 나타냅니다.
LR 알고리듬은 당시 ETH 취리히에서 Eduard Stiefel의 연구 조교로 일했던 Heinz Rutishauser에 의해 1950년대 초에 개발되었습니다. Stiefel은 Rutishauser가 A의 고윳값을 찾기 위해 일련의 순간 \(y_0^{\text{T}}A^k x_0\), k = 0, 1, … (여기서 \(x_0\)와 \(y_0\)은 임의적인 벡터임)을 사용할 것을 제안했습니다. Rutishauser는 이 임무를 위해 Alexander Aitken의 알고리듬을 취하고 그것을 quotient–difference algorithm 또는 qd algorithm으로 개발했습니다. 적절한 모양으로 계산을 배열한 후, 그는 qd 알고리듬이 실제로 삼중대각 행렬에 적용된 반복 \(A_k = L_k U_k\) (LU 분해), \(A_{k+1}=U_k L_k\)이며, 이로부터 LR 알고리듬이 이어진다는 것을 발견했습니다.
Other variants
QR 알고리듬의 변형 중 하나, Golub-Kahan-Reinsch 알고리듬은 일반 행렬을 이중대각 행렬로 줄이는 것부터 시작합니다. 특이값 계산을 위한 QR 알고리듬의 변형은 Golub & Kahan (1965)에 의해 처음 설명되었습니다. LAPACK 서브루틴 DBDSQR은 특이값이 매우 작은 경우를 처리하기 위해 일부 수정을 통해 이 반복 방법을 구현합니다 (Demmel & Kahan 1990). 하우스홀더 반사와, 적절하다면, QR 분해를 사용하는 첫 번째 단계와 함께, 이것은 특이값 분해의 계산을 위한 DGESVD 루틴을 형성합니다. QR 알고리듬은 해당 수렴 결과를 갖는 무한 차원으로 구현될 수도 있습니다.
Sources
- Demmel, James; Kahan, William (1990). "Accurate singular values of bidiagonal matrices". SIAM Journal on Scientific and Statistical Computing. 11 (5): 873–912. CiteSeerX 10.1.1.48.3740. doi:10.1137/0911052.
- Golub, Gene H.; Kahan, William (1965). "Calculating the singular values and pseudo-inverse of a matrix". Journal of the Society for Industrial and Applied Mathematics, Series B: Numerical Analysis. 2 (2): 205–224. Bibcode:1965SJNA....2..205G. doi:10.1137/0702016. JSTOR 2949777.
External links
- Eigenvalue problem at PlanetMath.org.
- Notes on orthogonal bases and the workings of the QR algorithm by Peter J. Olver
- Module for the QR Method
- C++ Library
