(번역) QR decomposition

Original article: w:QR decomposition

 

선형 대수(linear algebra)에서, QR 분해(QR decomposition, 역시 QR factorization 또는 QU factorization라고 알려져 있음)는 행렬 A를 직교정규 행렬 Q와 위쪽 삼각 행렬 R의 곱 A = QR로의 분해입니다. QR 분해는 종종 선형 최소 제곱(linear least squares) 문제를 해결하기 위해 사용되고 특정 고윳값 알고리즘(eigenvalue algorithm), QR 알고리즘의 기초입니다.

Cases and definitions

Square matrix

임의의 실수 정사각 행렬(square matrix) A는 다음으로 분해될 수 있습니다:

${\displaystyle A=QR,}$

여기서 Q는 직교 행렬 (그 열은 ${\displaystyle Q^{\mathsf{\text{T}}}=Q^{-1}}$을 의미하는 직교 단위 벡터임)이고 R은 위쪽 삼각 행렬 (직각 삼각 행렬이라고도 함)입니다. 만약 A가 역가능이면, 인수분해는 R의 대각선 원소가 양수여야 한다면 고유합니다.

만약 대신 A가 복소수 정사각 행렬이면, 분해 A = QR이 있으며 여기서 Q는 유니태리 행렬 (따라서 ${\displaystyle Q^{†}=Q^{-1}}$)입니다.

만약 A가 n개의 선형적으로 독립(linearly independent) 열을 가지면, Q의 처음 n개 열은 A의 열 공간(column space)에 대한 직교정규 기저(orthonormal basis)를 형성합니다. 보다 일반적으로, Q의 처음 k개의 열은 임의의 1 ≤ k ≤ n에 대해 A의 처음 k개의 열의 스팬(span)에 대한 직교정규 기저를 형성합니다. A의 임의의 열 k가 Q의 처음 k개의 열에만 의존한다는 사실은 R의 삼각 형식에 해당합니다.

Rectangular matrix

보다 일반적으로, 우리는 m ≥ n을 갖는 복소수 m×n 행렬 A를 m×m 유니태리 행렬(unitary matrix) Q와 m×n 위쪽 삼각 행렬 R의 곱으로 인수분해할 수 있습니다. m×n 위쪽 삼각 행렬이 완전히 영들로 구성되어 있으면, R 또는 R과 Q 둘 다를 분할하는 것이 종종 유용합니다:

${\displaystyle A=QR=Q\left[\begin{array}{c}{R}_1\\ 0\end{array}\right]=\left[\begin{array}{cc}{Q}_1& Q_2\end{array}\right]\left[\begin{array}{c}{R}_1\\ 0\end{array}\right]=Q_1{R}_1,}$

여기서 $R_1$은 n×n 위쪽 삼각 행렬, ${\displaystyle 0}$은 (m − n)×n 영 행렬, $Q_1$은 m×n, $Q_2$는 m×(m − n)이고, $Q_1$과 $Q_2$ 둘 다는 대각 열을 가집니다.

Golub & Van Loan (1996, §5.2)는 $Q_1{R}_1$을 A의 얇은 QR 인수분해(thin QR factorization)라고 부릅니다; Trefethen 및 Bau는 이것을 감소된 QR 인수분해(reduced QR factorization)라고 부릅니다. 만약 A가 완전한 랭크(rank) n을 가지고 $R_1$의 대각선 원소는 양수여야 하면, $R_1$과 $Q_1$은 고유하지만, 일반적으로 $Q_2$는 그렇지 않습니다. 그런-다음 $R_1$은 $A^{\ast }A$ (= $A^{\text{T}}A$, A가 실수이면)의 숄레스키 분해(Cholesky decomposition)의 위쪽 삼각 인수와 같습니다.

QL, RQ and LQ decompositions

유사하게, L이 아래쪽 삼각 행렬과 함께, QL, RQ, 및 LQ 분해를 정의할 수 있습니다.

Computing the QR decomposition

실제로 예를 들어 그람–슈미트 과정(Gram–Schmidt process), 하우스홀더 변환(Householder transformations), 또는 기븐스 회전(Givens rotations)을 수단으로 QR 분해를 계산하는 여러 방법이 있습니다. 각각에는 여러 가지 장점과 단점이 있습니다.

Using the Gram–Schmidt process

안의 곱 ${\displaystyle ⟨\mathbf{v},\mathbf{w}⟩={\mathbf{v}}^{\mathsf{\text{T}}}\mathbf{w}}$ (또는 복소수 경우에 대해 ${\displaystyle ⟨\mathbf{v},\mathbf{w}⟩={\mathbf{v}}^{†}\mathbf{w}}$)를 갖는 전체 열 랭크 행렬 ${\displaystyle A=\left[\begin{array}{ccc}{\mathbf{a}}_1& \cdots & {\mathbf{a}}_n\end{array}\right]}$의 열에 적용되는 그람-슈미트 과정을 생각해 보십시오.

다음 투영(projection)을 정의합니다:

${\displaystyle {\mathrm{proj}}_{\mathbf{u}}\mathbf{a}=\frac{⟨\mathbf{u},\mathbf{a}⟩}{⟨\mathbf{u},\mathbf{u}⟩}\mathbf{u}}$

그런-다음:

${\displaystyle \begin{array}{rlrl}{\mathbf{u}}_1& ={\mathbf{a}}_1,& {\mathbf{e}}_1& =\frac{{\mathbf{u}}_1}{\Vert {\mathbf{u}}_1\Vert }\\ {\mathbf{u}}_2& ={\mathbf{a}}_2-{\mathrm{proj}}_{{\mathbf{u}}_1}{\mathbf{a}}_2,& {\mathbf{e}}_2& =\frac{{\mathbf{u}}_2}{\Vert {\mathbf{u}}_2\Vert }\\ {\mathbf{u}}_3& ={\mathbf{a}}_3-{\mathrm{proj}}_{{\mathbf{u}}_1}{\mathbf{a}}_3-{\mathrm{proj}}_{{\mathbf{u}}_2}{\mathbf{a}}_3,& {\mathbf{e}}_3& =\frac{{\mathbf{u}}_3}{\Vert {\mathbf{u}}_3\Vert }\\ & ⋮& & ⋮\\ {\mathbf{u}}_k& ={\mathbf{a}}_k-\sum _{j=1}^{k-1}{\mathrm{proj}}_{{\mathbf{u}}_j}{\mathbf{a}}_k,& {\mathbf{e}}_k& =\frac{{\mathbf{u}}_k}{\Vert {\mathbf{u}}_k\Vert }\end{array}}$

이제 새로 계산된 직교정규 기저에 걸쳐 ${\displaystyle {\mathbf{a}}_i}$를 표현할 수 있습니다:

${\displaystyle \begin{array}{rl}{\mathbf{a}}_1& =⟨{\mathbf{e}}_1,{\mathbf{a}}_1⟩{\mathbf{e}}_1\\ {\mathbf{a}}_2& =⟨{\mathbf{e}}_1,{\mathbf{a}}_2⟩{\mathbf{e}}_1+⟨{\mathbf{e}}_2,{\mathbf{a}}_2⟩{\mathbf{e}}_2\\ {\mathbf{a}}_3& =⟨{\mathbf{e}}_1,{\mathbf{a}}_3⟩{\mathbf{e}}_1+⟨{\mathbf{e}}_2,{\mathbf{a}}_3⟩{\mathbf{e}}_2+⟨{\mathbf{e}}_3,{\mathbf{a}}_3⟩{\mathbf{e}}_3\\ & ⋮\\ {\mathbf{a}}_k& =\sum _{j=1}^k⟨{\mathbf{e}}_j,{\mathbf{a}}_k⟩{\mathbf{e}}_j\end{array}}$

여기서 ${\displaystyle ⟨{\mathbf{e}}_i,{\mathbf{a}}_i⟩=\Vert {\mathbf{u}}_i\Vert }$. 이것은 행렬 형식에서 쓸 수 있습니다:

${\displaystyle A=QR}$

여기서:

${\displaystyle Q=\left[\begin{array}{ccc}{\mathbf{e}}_1& \cdots & {\mathbf{e}}_n\end{array}\right]}$

및

${\displaystyle R=\left[\begin{array}{ccccc}⟨{\mathbf{e}}_1,{\mathbf{a}}_1⟩& ⟨{\mathbf{e}}_1,{\mathbf{a}}_2⟩& ⟨{\mathbf{e}}_1,{\mathbf{a}}_3⟩& \cdots & ⟨{\mathbf{e}}_1,{\mathbf{a}}_n⟩\\ 0& ⟨{\mathbf{e}}_2,{\mathbf{a}}_2⟩& ⟨{\mathbf{e}}_2,{\mathbf{a}}_3⟩& \cdots & ⟨{\mathbf{e}}_2,{\mathbf{a}}_n⟩\\ 0& 0& ⟨{\mathbf{e}}_3,{\mathbf{a}}_3⟩& \cdots & ⟨{\mathbf{e}}_3,{\mathbf{a}}_n⟩\\ ⋮& ⋮& ⋮& \ddots & ⋮\\ 0& 0& 0& \cdots & ⟨{\mathbf{e}}_n,{\mathbf{a}}_n⟩\end{array}\right].}$

Example

다음의 합성을 생각해 보십시오:

${\displaystyle A=\left[\begin{array}{ccc}12& -51& 4\\ 6& 167& -68\\ -4& 24& -41\end{array}\right].}$

직교정규 행렬 ${\displaystyle Q}$는 ${\displaystyle Q^{\mathsf{\text{T}}}Q=I}$ 속성을 갖는다는 것을 기억해 내십시오.

그런-다음, 다음처럼 그람-슈미트를 수단으로 ${\displaystyle Q}$를 계산할 수 있습니다:

${\displaystyle \begin{array}{rl}U=\left[\begin{array}{ccc}{\mathbf{u}}_1& {\mathbf{u}}_2& {\mathbf{u}}_3\end{array}\right]& =\left[\begin{array}{ccc}12& -69& -58/5\\ 6& 158& 6/5\\ -4& 30& -33\end{array}\right];\\ Q=\left[\begin{array}{ccc}\frac{{\mathbf{u}}_1}{\Vert {\mathbf{u}}_1\Vert }& \frac{{\mathbf{u}}_2}{\Vert {\mathbf{u}}_2\Vert }& \frac{{\mathbf{u}}_3}{\Vert {\mathbf{u}}_3\Vert }\end{array}\right]& =\left[\begin{array}{ccc}6/7& -69/175& -58/175\\ 3/7& 158/175& 6/175\\ -2/7& 6/35& -33/35\end{array}\right].\end{array}}$

따라서, 다음을 가집니다:

${\displaystyle \begin{array}{rl}{Q}^{\mathsf{\text{T}}}A& =Q^{\mathsf{\text{T}}}QR=R;\\ R& =Q^{\mathsf{\text{T}}}A=\left[\begin{array}{ccc}14& 21& -14\\ 0& 175& -70\\ 0& 0& 35\end{array}\right].\end{array}}$

Relation to RQ decomposition

RQ 분해는 행렬 A를 위쪽 삼각 행렬 R (직각 삼각 행렬이라고도 함)과 직교 행렬 Q의 곱으로 변환합니다. QR 분해와의 유일한 차이점은 이들 행렬의 순서입니다.

QR 분해는 첫 번째 열부터 시작하여 A의 열의 그람-슈미트 직교화입니다.

RQ 분해는 마지막 행부터 시작하여 A의 행의 그람-슈미트 직교화입니다.

Advantages and disadvantages

그람-슈미트 과정은 본질적으로 수치적으로 불안정합니다. 투영의 적용은 직교화에 대한 매력적인 기하학적 비유를 갖고 있지만, 직교화 자체는 수치적 오류가 발생하기 쉽습니다. 중요한 장점은 구현이 쉽다는 것입니다.

Using Householder reflections

하우스홀더 반사(Householder reflection, 또는 하우스홀더 변환)는 벡터를 취하고 그것을 평면이나 초평면에 대해 반사하는 변환입니다. 이 연산을 사용하여 m ≥ n을 갖는 m×n 행렬 ${\displaystyle A}$의 QR 분해를 계산할 수 있습니다.

Q는 하나를 제외한 모든 좌표가 사라지는 방법으로 벡터를 반사하기 위해 사용될 수 있습니다.

${\displaystyle \mathbf{x}}$를 스칼라 α에 대해 ${\displaystyle \Vert \mathbf{x}\Vert =|\alpha |}$임을 만족하는 ${\displaystyle A}$의 임의적인 실수 m-차원 열 벡터로고 놓습니다. 만약 알고리즘이 부동-점 산술(floating-point arithmetic)을 사용하여 구현되면, α는 ${\displaystyle \mathbf{x}}$의 k-번째 좌표와 반대 부호를 얻어야 하며, 여기서 ${\displaystyle x_k}$는, 중요성의 상실(loss of significance)을 피하기 위해, 행렬 ${\displaystyle A}$의 마지막 위쪽 삼각 형식에서 모든 엔트리가 0이 되는 피벗 좌표입니다. 복소수 경우에서, 다음을 설정하고

${\displaystyle \alpha =-e^{i\arg x_k}\Vert \mathbf{x}\Vert }$

아래 Q의 구성에서 켤레 전치로 전치를 대체합니다.

그런다음, 여기서 ${\displaystyle {\mathbf{e}}_1}$는 벡터 $[10\cdots 0{]}^{\text{T}}$, ||·||는 유클리드 노름(Euclidean norm)이고 ${\displaystyle I}$는 m×m 항등 행렬이며, 다음이라고 설정합니다:

${\displaystyle \begin{array}{rl}\mathbf{u}& =\mathbf{x}-\alpha {\mathbf{e}}_1,\\ \mathbf{v}& =\frac{\mathbf{u}}{\Vert \mathbf{u}\Vert },\\ Q& =I-2\mathbf{v}{\mathbf{v}}^{\mathsf{\text{T}}}.\end{array}}$

또는, 만약 ${\displaystyle A}$가 복소수이면,

${\displaystyle Q=I-2\mathbf{v}{\mathbf{v}}^{†}.}$

${\displaystyle Q}$는 m×m 하우스홀더 행렬이며, 이는 대칭과 직교 둘 다 (복소수  경우에서 에르미트와 유니태리)이고, 다음입니다:

${\displaystyle Q\mathbf{x}=\left[\begin{array}{c}\alpha \\ 0\\ ⋮\\ 0\end{array}\right].}$

이것은 m×m 행렬 A를 위쪽 삼각 형식으로 점진적으로 변환하기 위해 사용될 수 있습니다. 먼저, x에 대한 첫 번째 행렬 열을 선택할 때 얻은 하우스홀더 행렬 $Q_1$을 A에 곱합니다. 그 결과 왼쪽 열에 영들이 있는 행렬 $Q_{1}A$가 생성됩니다 (첫 번째 행 제외):

${\displaystyle Q_{1}A=\left[\begin{array}{cccc}{\alpha }_1& \star & \cdots & \star \\ 0& & & \\ ⋮& & A^{\prime }& \\ 0& & & \end{array}\right]}$

이것은 A′ (첫 번째 행과 첫 번째 열을 삭제함으로써 $Q_{1}A$에서 얻음)에 대해 반복될 수 있으며, 그 결과 하우스홀더 행렬 ${Q^{\prime }}_2$가 생성됩니다. ${Q^{\prime }}_2$는 $Q_1$보다 작음에 주목하십시오. 우리는 A′ 대신 $Q_{1}A$에서 실제로 작동하기를 원하기 때문에, 왼쪽 위쪽으로 확장하여, 1을 채워야 하거나, 일반적으로 다음입니다:

${\displaystyle Q_k=\left[\begin{array}{cc}{I}_{k-1}& 0\\ 0& Q_k^{\prime }\end{array}\right].}$

이 과정의 ${\displaystyle t}$번 반복한 후, ${\displaystyle t=min(m-1,n)}$,

${\displaystyle R=Q_t\cdots Q_2{Q}_{1}A}$

위는 위쪽 삼각 행렬입니다. 따라서, 다음과 함께,

${\displaystyle \begin{array}{rl}{Q}^{\mathsf{\text{T}}}& =Q_t\cdots Q_2{Q}_1,\\ Q& =Q_1^{\mathsf{\text{T}}}{Q}_2^{\mathsf{\text{T}}}\cdots Q_t^{\mathsf{\text{T}}},\\ & =Q_1{Q}_2\cdots Q_t,\end{array}}$

${\displaystyle A=QR}$는 ${\displaystyle A}$의 QR 분해입니다.

이 방법은 위의 그람-슈미트 방법보다 더 높은 수치적 안정성(numerical stability)을 가집니다.

다음 테이블은 크기 n을 갖는 정사각 행렬을 가정하여 하우스홀더 변환에 의한 QR-분해의 k-번째 단계에서 수행되는 연산의 개수를 나타냅니다.

(크기 n의 정사각 행렬에 대해) n − 1 단계에 걸쳐 이들 숫자를 합산하여, (부동 소수점 곱셈 측면에서) 알고리즘의 복잡도는 다음에 의해 계산됩니다:

${\displaystyle \frac{2}{3}{n}^3+n^2+\frac{1}{3}n-2=O\left(n^3\right).}$

Example

다음의 분해를 계산해 보십시오:

${\displaystyle A=\left[\begin{array}{ccc}12& -51& 4\\ 6& 167& -68\\ -4& 24& -41\end{array}\right].}$

먼저, 행렬 A의 첫 번째 열, 벡터 ${\displaystyle {\mathbf{a}}_1={\left[\begin{array}{ccc}12& 6& -4\end{array}\right]}^{\mathsf{\text{T}}}}$를 ${\displaystyle \Vert {\mathbf{a}}_1\Vert {\mathbf{e}}_1={\left[\begin{array}{ccc}\alpha & 0& 0\end{array}\right]}^{\mathsf{\text{T}}}}$로 변환하는 반사를 찾아야 합니다:

이제,

${\displaystyle \mathbf{u}=\mathbf{x}-\alpha {\mathbf{e}}_1,}$

그리고

${\displaystyle \mathbf{v}=\frac{\mathbf{u}}{\Vert \mathbf{u}\Vert }.}$

여기서,

${\displaystyle \alpha =14}$ and ${\displaystyle \mathbf{x}={\mathbf{a}}_1={\left[\begin{array}{ccc}12& 6& -4\end{array}\right]}^{\mathsf{\text{T}}}}$

그러므로

${\displaystyle \mathbf{u}={\left[\begin{array}{ccc}-2& 6& -4\end{array}\right]}^{\mathsf{\text{T}}}=2{\left[\begin{array}{ccc}-1& 3& -2\end{array}\right]}^{\mathsf{\text{T}}}}$ and ${\displaystyle \mathbf{v}=\frac{1}{\sqrt{14}}{\left[\begin{array}{ccc}-1& 3& -2\end{array}\right]}^{\mathsf{\text{T}}}}$, 그리고 그런-다음

${\displaystyle \begin{array}{rl}{Q}_1=& I-\frac{2}{\sqrt{14}\sqrt{14}}\left[\begin{array}{c}-1\\ 3\\ -2\end{array}\right]\left[\begin{array}{ccc}-1& 3& -2\end{array}\right]\\ =& I-\frac{1}{7}\left[\begin{array}{ccc}1& -3& 2\\ -3& 9& -6\\ 2& -6& 4\end{array}\right]\\ =& \left[\begin{array}{ccc}6/7& 3/7& -2/7\\ 3/7& -2/7& 6/7\\ -2/7& 6/7& 3/7\end{array}\right].\end{array}}$

이제 다음을 관찰하십시오:

${\displaystyle Q_{1}A=\left[\begin{array}{ccc}14& 21& -14\\ 0& -49& -14\\ 0& 168& -77\end{array}\right],}$

그래서 우리는 이미 거의 삼각형 행렬을 가지고 있습니다. 우리는 (3, 2) 엔트리만 영으로 설정하면 됩니다.

(1, 1) 소행렬식(minor)을 취하고, 그런-다음 다음에 그 과정을 다시 적용합니다:

${\displaystyle A^{\prime }=M_{11}=\left[\begin{array}{cc}-49& -14\\ 168& -77\end{array}\right].}$

위에서 처럼 같은 방법에 의해, 우리는 하우스홀더 변환의 행렬을 얻습니다:

${\displaystyle Q_2=\left[\begin{array}{ccc}1& 0& 0\\ 0& -7/25& 24/25\\ 0& 24/25& 7/25\end{array}\right]}$

과정에서 다음 단계가 제대로 작동하는지 확인하기 위해 1로 직접 합계를 수행한 후.

이제, 다음을 찾습니다:

${\displaystyle Q=Q_1^{\mathsf{\text{T}}}{Q}_2^{\mathsf{\text{T}}}=\left[\begin{array}{ccc}6/7& -69/175& 58/175\\ 3/7& 158/175& -6/175\\ -2/7& 6/35& 33/35\end{array}\right].}$

또는, 네 개의 십진 자릿수로,

${\displaystyle \begin{array}{rl}Q& =Q_1^{\mathsf{\text{T}}}{Q}_2^{\mathsf{\text{T}}}=\left[\begin{array}{ccc}0.8571& -0.3943& 0.3314\\ 0.4286& 0.9029& -0.0343\\ -0.2857& 0.1714& 0.9429\end{array}\right]\\ R& =Q_2{Q}_{1}A=Q^{\mathsf{\text{T}}}A=\left[\begin{array}{ccc}14& 21& -14\\ 0& 175& -70\\ 0& 0& -35\end{array}\right].\end{array}}$

행렬 Q는 직교이고 R은 위쪽 삼각 행렬이므로, A = QR이 필요한 QR 분해입니다.

Advantages and disadvantages

하우스홀더 변환의 용도는 본질적으로 R 행렬에서 영들을 생성하는 데 메커니즘으로 반사의 사용으로 인해 수치적으로 안정적인 QR 분해 알고리즘 중 가장 간단합니다. 어쨌든, 하우스홀더 반사 알고리즘은 새로운 영 원소를 생성하는 모든 각 반사가 Q 및 R 행렬의 전체성을 변경하므로 대역폭이 무겁고 병렬화가 불가능합니다.

Using Givens rotations

QR 분해는 기븐스 회전(Givens rotations)의 수열로 계산될 수도 있습니다. 각 회전은 행렬의 하위대각선에 있는 원소를 영으로 조정하여, R 행렬을 형성합니다. 모든 기븐스 회전의 연쇄는 직교 Q 행렬을 형성됩니다.

실제로, 기븐스 회전은 전체 행렬을 만들고 행렬 곱셈을 수행함으로써 실제로 수행되지 않습니다. 희소 원소를 다루는 여분의 작업 없이 희소 기븐스 행렬 곱셈과 동등한 연산을 수행하는 기븐스 회전 절차가 대신 사용됩니다. 기븐스 회전 절차는 상대적으로 적은 수의 비-대각선 원소만 영으로 설정해야 하는 상황에서 유용하고, 하우스홀더 변환(Householder transformations)보다 더 쉽게 병렬화됩니다.

Example

다음의 분해를 계산해 보십시오:

${\displaystyle A=\left[\begin{array}{ccc}12& -51& 4\\ 6& 167& -68\\ -4& 24& -41\end{array}\right].}$

먼저, 가장 왼쪽 아래 원소, ${\displaystyle a_{31}=-4}$를 영으로 만드는 회전 행렬을 형성해야 합니다. 기븐스 회전 방법을 사용하여 이 행렬을 형성하고, 행렬 ${\displaystyle G_1}$을 호출합니다. 먼저 X축을 따라 가리키도록 벡터 ${\displaystyle \left[\begin{array}{cc}12& -4\end{array}\right]}$를 회전합니다. 이 벡터는 각도 ${\displaystyle \theta =\arctan \left(\frac{-(-4)}{12}\right)}$를 가집니다. 직교 기븐스 회전 행렬, ${\displaystyle G_1}$을 만듭니다:

${\displaystyle \begin{array}{rl}{G}_1& =\left[\begin{array}{ccc}\cos (\theta )& 0& -\sin (\theta )\\ 0& 1& 0\\ \sin (\theta )& 0& \cos (\theta )\end{array}\right]\\ & \approx \left[\begin{array}{ccc}0.94868& 0& -0.31622\\ 0& 1& 0\\ 0.31622& 0& 0.94868\end{array}\right]\end{array}}$

그리고 ${\displaystyle G_{1}A}$의 결과는 이제 ${\displaystyle a_{31}}$ 원소에 영을 가집니다.

${\displaystyle G_{1}A\approx \left[\begin{array}{ccc}12.64911& -55.97231& 16.76007\\ 6& 167& -68\\ 0& 6.64078& -37.6311\end{array}\right]}$

유사하게 기븐스 행렬 ${\displaystyle G_2}$와 ${\displaystyle G_3}$을 형성할 수 있으며, 이는 하위-대각선 원소 ${\displaystyle a_{21}}$과 ${\displaystyle a_{32}}$를 영으로 만들어, 삼각 행렬 ${\displaystyle R}$을 형성합니다. 직교 행렬 ${\displaystyle Q^{\mathsf{\text{T}}}}$는 모든 기븐스 행렬 ${\displaystyle Q^{\mathsf{\text{T}}}=G_3{G}_2{G}_1}$의 곱으로 형성됩니다. 따라서, ${\displaystyle G_3{G}_2{G}_{1}A=Q^{\mathsf{\text{T}}}A=R}$를 가지고, QR 분해는 ${\displaystyle A=QR}$입니다.

Advantages and disadvantages

알고리즘을 완전히 활용하는 데 필요한 행의 순서화는 결정하기에 자명하지 않기 때문에 기븐스 회전을 통한 QR 분해가 구현에 가장 복잡합니다. 어쨌든, 그것은 각각의 새로운 영 원소 ${\displaystyle a_{ij}}$가 영이 되는 원소를 갖는 행 (i)과 그 위의 행 (j)에만 영향을 미친다는 점에서 상당한 이점을 가집니다. 이것은 기븐스 회전 알고리즘을 하우스홀더 반사 기술보다 더 대역폭 효율적이고 병렬화 가능하게 만듭니다.

Connection to a determinant or a product of eigenvalues

우리는 정사각 행렬의 행렬식(determinant)을 찾기 위해 QR 분해를 사용할 수 있습니다. 행렬이 ${\displaystyle A=QR}$로 분해된다고 가정합니다. 그런-다음 다음을 가집니다:

$QdetR.$

${\displaystyle Q}$는 ${\displaystyle detQ=1}$임을 만족하도록 선택될 수 있습니다. 따라서,

${\displaystyle detA=detR=\prod _i{r}_{ii}}$

여기서 ${\displaystyle r_{ii}}$는 ${\displaystyle R}$의 대각선 위의 엔트리입니다. 게다가, 행렬식은 고윳값의 곱과 같기 때문에, 다음을 가집니다:

${\displaystyle \prod _i{r}_{ii}=\prod _i{\lambda }_i}$

여기서 ${\displaystyle {\lambda }_i}$는 ${\displaystyle A}$의 고윳값입니다.

비-정사각 복소 행렬에 대한 QR 분해의 정의를 도입하고 고윳값을 특이값으로 대체함으로써 위의 속성을 비-정사각 복소 행렬 ${\displaystyle A}$로 확장할 수 있습니다.

비-정사각 행렬 ${\displaystyle A}$에 대한 QR 분해로 시작합니다:

${\displaystyle A=Q\left[\begin{array}{c}R\\ 0\end{array}\right],Q^{†}Q=I}$

여기서 ${\displaystyle 0}$은 영 행렬을 나타내고 ${\displaystyle Q}$는 유니태리 행렬입니다.

SVD의 속성과 행렬의 행렬식으로부터, 다음을 가집니다:

${\displaystyle |\prod _i{r}_{ii}|=\prod _i{\sigma }_i,}$

여기서 ${\displaystyle {\sigma }_i}$는 ${\displaystyle A}$의 특이값입니다.

${\displaystyle A}$와 ${\displaystyle R}$의 특이값은 동일하지만, 그것들의 복소 고윳값은 다를 수 있음에 주목하십시오. 어쨌든, ${\displaystyle A}$가 정사각이면, 다음입니다:

${\displaystyle \prod _i{\sigma }_i=|\prod _i{\lambda }_i|.}$

따라서 QR 분해는 행렬의 고윳값 또는 특이값의 곱을 효율적으로 계산하기 위해 사용될 수 있습니다.

Column pivoting

피벗된 QR은 각각의 새로운 단계—열 피벗팅—가 시작에서 가장 큰 남아있는 열을 취하고 따라서 순열 행렬(permutation matrix) P를 도입한다는 점에서 일반적인 그람-슈미트와 다릅니다:

${\displaystyle AP=QR⟺A=QR{P}^{\mathsf{\text{T}}}}$

열 피벗팅은 ${\displaystyle A}$가 (거의) 랭크 부족일 때, 또는 그럴 것으로 의심될 때 유용합니다. 그것은 역시 수치 정확도를 향상시킬 수 있습니다. P는 보통 R의 대각선 원소가 비-증가하도록 선택됩니다: ${\displaystyle \left|r_{11}\right|\ge \left|r_{22}\right|\ge \cdots \ge \left|r_{nn}\right|}$. 이것은 특이값 분해보다 낮은 계산 비용으로 ${\displaystyle A}$의 (수치적) 랭크를 찾기 위해 사용될 수 있으며, 소위 랭크-공개 QR 알고리즘(rank-revealing QR algorithms)의 기초를 형성합니다.

Using for solution to linear inverse problems

직접 행렬 역과 비교하여, QR 분해를 사용하는 역 해는 그것들의 감소된 조건 숫자(condition numbers)에 의해 알 수 있듯이 수치적으로 더 안정적입니다.

행렬 ${\displaystyle A}$가 차원 ${\displaystyle m\times n}$을 가지고 랭크 ${\displaystyle m}$을 가지는 미달결정된 ${\displaystyle m<n}$)) 선형 문제 ${\displaystyle A\mathbf{x}=\mathbf{b}}$를 풀기 위해, 먼저 ${\displaystyle A}$의 전치의 QR 인수분해를 구합니다: ${\displaystyle A^{\mathsf{\text{T}}}=QR}$, 여기서 Q는 직교 행렬 (즉, ${\displaystyle Q^{\mathsf{\text{T}}}=Q^{-1}}$)이고, R은 ${\displaystyle R=\left[\begin{array}{c}{R}_1\\ 0\end{array}\right]}$이라는 특별한 형식을 가집니다. 여기서 ${\displaystyle R_1}$은 정사각 ${\displaystyle m\times m}$ 직각 삼각 행렬이고, 영 행렬은 차원 ${\displaystyle (n-m)\times m}$을 가집니다. 일부 대수 후에, 역 문제에 대한 해는 ${\displaystyle \mathbf{x}=Q\left[\begin{array}{c}{\left(R_1^{\mathsf{\text{T}}}\right)}^{-1}\mathbf{b}\\ 0\end{array}\right]}$으로 표현될 수 있음을 알 수 있으며, 여기서 ${\displaystyle R_1^{-1}}$을 가우스 소거법(Gaussian elimination)으로 찾거나 전방 대입(forward substitution)에 의해 직접 ${\displaystyle {\left(R_1^{\mathsf{\text{T}}}\right)}^{-1}\mathbf{b}}$를 계산할 수 있습니다. 후자의 기술은 수치 정확도가 더 높고 계산량이 더 적습니다.

노름 ${\displaystyle \Vert A\hat{\mathbf{x}}-\mathbf{b}\Vert }$를 최소화하는 초과결정된 ${\displaystyle m\ge n}$) 문제 ${\displaystyle A\mathbf{x}=\mathbf{b}}$에 대한 해 ${\displaystyle \hat{\mathbf{x}}}$를 찾기 위해, 먼저 ${\displaystyle A}$의 QR 분해를 구합니다: ${\displaystyle A=QR}$. 그런-다음 해는 ${\displaystyle \hat{\mathbf{x}}=R_1^{-1}\left(Q_1^{\mathsf{\text{T}}}\mathbf{b}\right)}$로 표현될 수 있으며, 여기서 ${\displaystyle Q_1}$은 전체 직교정규 기저 ${\displaystyle Q}$의 처음 ${\displaystyle n}$ 열을 포함하는 ${\displaystyle m\times n}$ 행렬이고 ${\displaystyle m\times n}$은 이전과 같습니다. 미달결정된 경우와 동등하게, 후방 대입(back substitution)은 ${\displaystyle R_1}$을 명시적으로 반전시키지 않고도 이 ${\displaystyle \hat{\mathbf{x}}}$를 빠르고 정확하게 찾기 위해 사용될 수 있습니다. (${\displaystyle Q_1}$과 ${\displaystyle R_1}$은 종종 수치 라이브러리에 의해 "경제적인" QR 분해로 제공됩니다.)

Generalizations

이와사와 분해(Iwasawa decomposition)는 QR 분해를 반-단순 리 그룹으로 일반화합니다.

See also

• Polar decomposition
• Eigenvalue decomposition
• Spectral decomposition
• LU decomposition
• Singular value decomposition

References

 

• Trefethen, Lloyd N.; Bau, David III (1997). Numerical linear algebra. Philadelphia, PA: Society for Industrial and Applied Mathematics. ISBN 978-0-898713-61-9.
• Stoer, Josef; Bulirsch, Roland (2002), Introduction to Numerical Analysis (3rd ed.), Springer, p. 225, ISBN 0-387-95452-X
• Strang, Gilbert (2019). Linear Algebra and Learning from Data (1st ed.). Wellesley: Wellesley Cambridge Press. p. 143. ISBN 978-0-692-19638-0.
• Parker, Robert L. (1994). Geophysical Inverse Theory. Princeton, N.J.: Princeton University Press. Section 1.13. ISBN 978-0-691-20683-7. OCLC 1134769155.

Further reading

• Golub, Gene H.; Van Loan, Charles F. (1996), Matrix Computations (3rd ed.), Johns Hopkins, ISBN 978-0-8018-5414-9.
• Horn, Roger A.; Johnson, Charles R. (1985), Matrix Analysis, Cambridge University Press, sec. 2.8, ISBN 0-521-38632-2
• Press, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007), "Section 2.10. QR Decomposition", Numerical Recipes: The Art of Scientific Computing (3rd ed.), New York: Cambridge University Press, ISBN 978-0-521-88068-8

External links

• Online Matrix Calculator Performs QR decomposition of matrices.
• LAPACK users manual gives details of subroutines to calculate the QR decomposition
• Mathematica users manual gives details and examples of routines to calculate QR decomposition
• ALGLIB includes a partial port of the LAPACK to C++, C#, Delphi, etc.
• Eigen::QR Includes C++ implementation of QR decomposition.