선형대수학에서 QR 분해(영어: QR decomposition, QR factorization)는 실수 행렬을 직교 행렬과 상삼각 행렬의 곱으로 나타내는 행렬 분해이다.[1] 그람-슈미트 과정이나 하우스홀더 행렬이나 기븐스 회전을 통해 얻을 수 있으며, 선형 최소 제곱법이나 QR 알고리즘에서 쓰인다.
정의
실수체 또는 복소수체
성분의
(
) 행렬
는 다음과 같이 분해할 수 있으며, 이를
의 QR 분해라고 한다.
![{\displaystyle A=QR}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a7d3eb7a53055abd0e9112408dbb2423035dfc72)
여기서
는
성분의
유니터리 행렬이다.
는
성분의
상삼각 행렬이다.
몇 가지 특수한 경우는 다음과 같다.
일 경우,
는 직교 행렬이 된다.
가 가역 행렬일 경우,
의 열들은 항상
의 열공간의 정규 직교 기저를 이룬다. 또한
의 모든 대각 원소가 양수인 QR 분해는 유일하다.
방법
그람-슈미트 과정
벡터
이 일차독립이라 하자. 행렬
에 대해, 그람-슈미트 직교정규화를 사용하면
![{\displaystyle \mathrm {proj} _{\mathbf {e} }\mathbf {a} ={\frac {\left\langle \mathbf {e} ,\mathbf {a} \right\rangle }{\left\langle \mathbf {e} ,\mathbf {e} \right\rangle }}\mathbf {e} }](https://wikimedia.org/api/rest_v1/media/math/render/svg/660d6d7af1e3ea4eb7530b16a8ae540cc942b9c9)
인 사영 연산자를 이용해서
![{\displaystyle \mathbf {u} _{i}=\mathbf {a} _{i}-\sum _{j=1}^{i-1}\mathrm {proj} _{\mathbf {u} _{j}}\mathbf {a} _{i}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/779ab0909f48e12c76c6ae35fc3ca55aa976321a)
![{\displaystyle \mathbf {e} _{i}={\frac {\mathbf {u} _{i}}{\|\mathbf {u} _{i}\|}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/25aca1534d6e30b7f90418b5074ac0da213b42c7)
와 같이 직교정규기저
를 얻을 수 있다.
은 내적
는 노름
위 식을 다시 정리하면
![{\displaystyle \mathbf {a} _{i}=\sum _{j=1}^{i}\langle \mathbf {e} _{j},\mathbf {a} _{i}\rangle \mathbf {e} _{j}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7a207ea797c1a480d233b4215e3d09383ddbb7e9)
가 되므로,
![{\displaystyle Q=[{\begin{array}{llll}\mathbf {e} _{1}&\mathbf {e} _{2}&\cdots &\mathbf {e} _{n}\end{array}}]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/cdae9de29d50cdc79f8b2573efa3e5ee221194d1)
![{\displaystyle R={\begin{pmatrix}\langle \mathbf {e} _{1},\mathbf {a} _{1}\rangle &\langle \mathbf {e} _{1},\mathbf {a} _{2}\rangle &\langle \mathbf {e} _{1},\mathbf {a} _{3}\rangle &\ldots \\0&\langle \mathbf {e} _{2},\mathbf {a} _{2}\rangle &\langle \mathbf {e} _{2},\mathbf {a} _{3}\rangle &\ldots \\0&0&\langle \mathbf {e} _{3},\mathbf {a} _{3}\rangle &\ldots \\\vdots &\vdots &\vdots &\ddots \end{pmatrix}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/769ee0585bb75d9745c9ceecec4ecfdf9488195b)
와 같이 놓으면
이 성립한다.
예
![{\displaystyle A={\begin{pmatrix}12&-51&4\\6&167&-68\\-4&24&-41\end{pmatrix}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b580c9c1fe2c7f6abf035bc2847b46b4e1ae3c37)
정규 직교 행렬
는
의 성질을 갖고있고,
따라서,
는 다음과 같이 그람-슈미트 절차를 따라서,
![{\displaystyle U={\begin{pmatrix}u_{1}&u_{2}&u_{3}\end{pmatrix}}={\begin{pmatrix}12&-69&-58/5\\6&158&6/5\\-4&30&-33\end{pmatrix}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f131d079a94fe13587e1687907326b079fd044e1)
![{\displaystyle Q={\begin{pmatrix}{{u_{1}} \over {\|u_{1}\|}}&{{u_{2}} \over {\|u_{2}\|}}&{{u_{3}} \over {\|u_{3}\|}}\end{pmatrix}}={\begin{pmatrix}12/14&-69/175&-58/\left(5\times 35\right)\\6/14&158/175&6/\left(5\times 35\right)\\-4/14&30/175&-33/\left(1\times 35\right)\end{pmatrix}}={\begin{pmatrix}6/7&-69/175&-58/175\\3/7&158/175&6/175\\-2/7&6/35&-33/35\end{pmatrix}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/af85dffbd49ccdd83a678ae3073ffa1038f9b20a)
그리고,
![{\displaystyle Q^{T}A=Q^{T}Q\,R=R}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c8b80013d95809be131aead895cdf6d5d3861d67)
![{\displaystyle R=Q^{T}A={\begin{pmatrix}14&21&-14\\0&175&-70\\0&0&35\end{pmatrix}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/31b008f7c015ffca9da3a1f8758751fc0cf94aad)
확인해보면,
이므로, ![{\displaystyle {\begin{pmatrix}6/7&-69/175&-58/175\\3/7&158/175&6/175\\-2/7&6/35&-33/35\end{pmatrix}}\cdot {\begin{pmatrix}14&21&-14\\0&175&-70\\0&0&35\end{pmatrix}}={\begin{pmatrix}12&-51&4\\6&167&-68\\-4&24&-41\end{pmatrix}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8bda46914454126b21710ca9cfd96d6139736f6c)
이다.
분해 된다.
그러나,
분수에의한 부동소수점연산이 관계함으로 오차가 발생할 수 있다.
RQ 분해와의 관계
분해는 행렬
를 상삼각행렬
(직각 삼각형이라고도 함) 및 직교 행렬
의 곱으로 변환한다.
분해와의 유일한 차이점은 행렬의 순서이다.
분해는 첫 번째 열에서 시작된
행렬의 열의 그람-슈미트 직교화이다.
분해는 마지막 행에서 시작하는
행렬의 행의 그람-슈미트 직교화이다.
장점과 단점
그람-슈미트 프로세스는 본질적으로 수치적으로 불안정할 수 있다. 투영법의 적용에는 직교화에 대한 주요한 기하학적 유추가 있지만 직교화 자체는 수치 오류가 발생하기 쉽다. 그러나 구현의 용이함이 중요한 장점이다. 사전 작성된 선형 대수 라이브러리(library)를 사용할 수 없거나 용이하지 않은 경우, 이 알고리즘을 프로토타입(prototype)에 사용할 수 있는 유용한 알고리즘으로 적용할 수 있다.
하우스홀더 방법
하우스홀더 리플렉터(하우스홀더 변환,Householder reflection)를 이용하여 한 열씩을 상삼각행렬로 바꾸어감으로써
와
을 구할 수 있다. 이 방법은
행렬을 하우스홀더 행렬의 곱으로 구해주기 때문에, 직접
를 구할 필요가 없을 때 유용하다. 또, 그람-슈미트 방법과는 달리, 부동소수점 연산에서도 오차가 누적되지 않기 때문에, 실제로 더 많이 활용된다.
예
![{\displaystyle A={\begin{pmatrix}12&-51&4\\6&167&-68\\-4&24&-41\end{pmatrix}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b580c9c1fe2c7f6abf035bc2847b46b4e1ae3c37)
먼저 행렬
의 첫 번째 열을 벡터로 변환하는 리플렉션을 찾아야한다.
에서, - 벡터
![{\displaystyle {a}_{1}=(12,6,-4)^{T}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e6d81833361a4c38eb5e546765415de7b3809747)
![{\displaystyle {u}={x}-\alpha {e}_{1}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/de926b9fdccb7578317fc8107889a706ca807ec5)
![{\displaystyle {v}={{u} \over \|{u}\|}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5e3166cffee79cfbb91d405d1c0d8ec0a1bc0cb7)
![{\displaystyle \alpha =14}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a851988fb2463a25d0004fdc07bfe5f8ceea6757)
![{\displaystyle {x}={a}_{1}=(12,6,-4)^{T}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6c2837efffda546a7ead278de62da8ffcd154ad3)
따라서,
![{\displaystyle {u}=(-2,6,-4)^{T}=({2})(-1,3,-2)^{T}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6549d8b448f1d2039133537d286ae22acf8a9a3b)
![{\displaystyle {v}={{(-1,3,-2)^{T}} \over {\sqrt {14}}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4d7b5e1368bc86a5ce9ed88773ea3304f2274dee)
하우스홀더 행렬
에서,
![{\displaystyle Q_{1}=I-2{{\begin{pmatrix}-1\\3\\-2\end{pmatrix}} \over {\sqrt {14}}}{{\begin{pmatrix}-1&3&-2\end{pmatrix}} \over {\sqrt {14}}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/fe9b739ba5e399956479f72b0d6d472d55738abd)
![{\displaystyle Q_{1}=I-{2 \over {\sqrt {14}}{\sqrt {14}}}{\begin{pmatrix}-1\\3\\-2\end{pmatrix}}{\begin{pmatrix}-1&3&-2\end{pmatrix}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7cff7880cc61507450fbd0f69b34f8c01acbecc5)
![{\displaystyle =I-{1 \over 7}{\begin{pmatrix}1&-3&2\\-3&9&-6\\2&-6&4\end{pmatrix}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/12b640aa0bee8137d3f7d7134509f9c2a0c0ad41)
![{\displaystyle ={\begin{pmatrix}6/7&3/7&-2/7\\3/7&-2/7&6/7\\-2/7&6/7&3/7\\\end{pmatrix}}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3a8d88d1d643cdeba0e723bbf96820cc4c3a5d0d)
확인해보면,
![{\displaystyle Q_{1}A={\begin{pmatrix}14&21&-14\\0&-49&-14\\0&168&-77\end{pmatrix}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0d479c6ead3cb5f9ef058fe5b4c1163f9dbfb78a)
삼각행렬에 접근하고 있음을 알 수 있다.
행
열에서
의 성분 값을
으로 만들면 상삼각행렬을 얻게 된다.
소행렬식에서 다시 위의 절차를 반복해보면,
![{\displaystyle A'=M_{11}={\begin{pmatrix}-49&-14\\168&-77\end{pmatrix}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d3056e64005fa5fbbff6b18650925e1a82fee940)
위와 같은 방법으로 하우스홀더 변환(Householder transformation)된 행렬을 얻고,
![{\displaystyle Q_{2}={\begin{pmatrix}1&0&0\\0&-7/25&24/25\\0&24/25&7/25\end{pmatrix}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/fe893e93a3052b3bdd416adc065e982a31e8877e)
에서 각각 전치행렬을 수행한 후 프로세스가 올바르게 작동하는지 확인해보고,
그리고나서,
![{\displaystyle Q=Q_{1}^{T}Q_{2}^{T}={\begin{pmatrix}6/7&-69/175&58/175\\3/7&158/175&-6/175\\-2/7&6/35&33/35\end{pmatrix}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/462e5658cde27799aed2dc268418c364dc2d7969)
그리고,
![{\displaystyle Q=Q_{1}^{T}Q_{2}^{T}={\begin{pmatrix}0.8571&-0.3943&0.3314\\0.4286&0.9029&-0.0343\\-0.2857&0.1714&0.9429\end{pmatrix}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a8364f4c21716da67a702dbbac08b91680c1707d)
![{\displaystyle R=Q_{2}Q_{1}A=Q^{T}A={\begin{pmatrix}14&21&-14\\0&175&-70\\0&0&-35\end{pmatrix}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/626d6a0925187c65ebd980914f0d9654807027c7)
행렬
는 직교행렬이고
은 상삼각행렬이되고
로
분해된다.
기븐스 회전
기븐스 행렬은 특정위치에서 성분값을
으로 조작할 수 있는 방법으로 기븐스 회전을 제공한다.
이것은 임의의 행렬을 직교행렬과 특정위치의 성분값이
인 상삼각행렬로 분해되게 유도할 수 있게된다.
예
![{\displaystyle A={\begin{pmatrix}a_{11}&a_{12}&a_{13}\\a_{21}&a_{22}&a_{23}\\a_{31}&a_{32}&a_{33}\end{pmatrix}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/203008bd7987333945075fe9f01b562a3f19a08d)
![{\displaystyle A={\begin{pmatrix}12&-51&4\\6&167&-68\\-4&24&-41\end{pmatrix}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b580c9c1fe2c7f6abf035bc2847b46b4e1ae3c37)
![{\displaystyle \mathbf {a} _{31}=-4}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c4a949d08f911ea7db4fbe930a5a8b0a66fca2a1)
![{\displaystyle G_{1},(12,-4)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/71c5cc1259060c98fdd229946fd9fc5e2b59d6fb)
![{\displaystyle \theta =\arctan \left({-(-4) \over 12}\right)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/598fee76e75bcf6bd903f294bcf3d0306833f2a8)
![{\displaystyle G_{1}={\begin{pmatrix}\cos(\theta )&0&-\sin(\theta )\\0&1&0\\\sin(\theta )&0&\cos(\theta )\end{pmatrix}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/08d3febf8151981b06873cac6c903910eb7d186f)
![{\displaystyle ={\begin{pmatrix}0.94868...&0&-0.31622...\\0&1&0\\0.31622...&0&0.94868...\end{pmatrix}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2146155578b8a4dbc79012451a365a8424200c45)
는
으로 조작된다. ![{\displaystyle G_{1}A={\begin{pmatrix}12.64911...&-55.97231...&16.76007...\\6&167&-68\\0&6.64078...&-37.6311...\end{pmatrix}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/dc87088fd69e69b5273bf0afe293562d815f7a63)
그리고
도 이러한 절차를 반복한다.
그리고
으로 조작된다.
결과로 상삼각행렬
을 얻는다. 따라서,
![{\displaystyle G_{3}\cdot G_{2}\cdot G_{1}=Q^{T}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7b347670eb6c9a348e08762cb23073f76b0a3f0b)
![{\displaystyle G_{3}G_{2}G_{1}A=Q^{T}A=R}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3a0c1413bf48cf19130f3bc27ef5a2e06edd35b0)
![{\displaystyle \left(Q^{T}\right)^{T}=Q}](https://wikimedia.org/api/rest_v1/media/math/render/svg/830d8457592ece02217078ac1258eca0f88b6170)
직교행렬에서,
![{\displaystyle Q^{T}=Q^{-1},QQ^{T}=Q^{T}Q=I}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ac44772dd4edea7fa426b3732f84e79f3a20741d)
그리고,
이다.
로 분해된다.
같이 보기
각주
- ↑ Lay, David C. (2012). 《Linear Algebra and Its Applications》 4판. Pearson Education. ISBN 978-0-321-38517-8.
참고 문헌
- Weisstein, Eric Wolfgang. “QR decomposition”. 《Wolfram MathWorld》 (영어). Wolfram Research.