그람-슈미트 과정 벡터 a 1 , a 2 , ⋯ , a n ∈ R m {\displaystyle \mathbf {a} _{1},\mathbf {a} _{2},\cdots ,\mathbf {a} _{n}\in \mathbb {R} ^{m}} 이 일차독립 이라 하자. 행렬 A = [ a 1 a 2 ⋯ a n ] {\displaystyle A=[{\begin{array}{llll}\mathbf {a} _{1}&\mathbf {a} _{2}&\cdots &\mathbf {a} _{n}\end{array}}]} 에 대해, 그람-슈미트 직교정규화를 사용하면
p r o j e a = ⟨ e , a ⟩ ⟨ e , e ⟩ e {\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} } 인 사영 연산자를 이용해서
u i = a i − ∑ j = 1 i − 1 p r o j u j a i {\displaystyle \mathbf {u} _{i}=\mathbf {a} _{i}-\sum _{j=1}^{i-1}\mathrm {proj} _{\mathbf {u} _{j}}\mathbf {a} _{i}} e i = u i ‖ u i ‖ {\displaystyle \mathbf {e} _{i}={\frac {\mathbf {u} _{i}}{\|\mathbf {u} _{i}\|}}} 와 같이 직교정규기저 { e 1 , e 2 , ⋯ , e n } {\displaystyle \{\mathbf {e} _{1},\mathbf {e} _{2},\cdots ,\mathbf {e} _{n}\}} 를 얻을 수 있다.
⟨ ⋅ , ⋅ ⟩ {\displaystyle {\langle \cdot ,\cdot \rangle }} 은 내적 , ‖ ‖ {\displaystyle ,\;\;{\|{}\|}} 는 노름 위 식을 다시 정리하면
a i = ∑ j = 1 i ⟨ e j , a i ⟩ e j {\displaystyle \mathbf {a} _{i}=\sum _{j=1}^{i}\langle \mathbf {e} _{j},\mathbf {a} _{i}\rangle \mathbf {e} _{j}} 가 되므로,
Q = [ e 1 e 2 ⋯ e n ] {\displaystyle Q=[{\begin{array}{llll}\mathbf {e} _{1}&\mathbf {e} _{2}&\cdots &\mathbf {e} _{n}\end{array}}]} R = ( ⟨ e 1 , a 1 ⟩ ⟨ e 1 , a 2 ⟩ ⟨ e 1 , a 3 ⟩ … 0 ⟨ e 2 , a 2 ⟩ ⟨ e 2 , a 3 ⟩ … 0 0 ⟨ e 3 , a 3 ⟩ … ⋮ ⋮ ⋮ ⋱ ) {\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}}} 와 같이 놓으면 A = Q R {\displaystyle A=QR} 이 성립한다.
예 A = ( 12 − 51 4 6 167 − 68 − 4 24 − 41 ) {\displaystyle A={\begin{pmatrix}12&-51&4\\6&167&-68\\-4&24&-41\end{pmatrix}}} 정규 직교 행렬 Q {\displaystyle Q} 는 Q T Q = I {\displaystyle Q^{T}\,Q=I} 의 성질을 갖고있고,
따라서, Q {\displaystyle Q} 는 다음과 같이 그람-슈미트 절차를 따라서,
U = ( u 1 u 2 u 3 ) = ( 12 − 69 − 58 / 5 6 158 6 / 5 − 4 30 − 33 ) {\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}}} Q = ( u 1 ‖ u 1 ‖ u 2 ‖ u 2 ‖ u 3 ‖ u 3 ‖ ) = ( 12 / 14 − 69 / 175 − 58 / ( 5 × 35 ) 6 / 14 158 / 175 6 / ( 5 × 35 ) − 4 / 14 30 / 175 − 33 / ( 1 × 35 ) ) = ( 6 / 7 − 69 / 175 − 58 / 175 3 / 7 158 / 175 6 / 175 − 2 / 7 6 / 35 − 33 / 35 ) {\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}}} 그리고,
Q T A = Q T Q R = R {\displaystyle Q^{T}A=Q^{T}Q\,R=R} R = Q T A = ( 14 21 − 14 0 175 − 70 0 0 35 ) {\displaystyle R=Q^{T}A={\begin{pmatrix}14&21&-14\\0&175&-70\\0&0&35\end{pmatrix}}} 확인해보면,
A = Q R {\displaystyle A=QR} 이므로, ( 6 / 7 − 69 / 175 − 58 / 175 3 / 7 158 / 175 6 / 175 − 2 / 7 6 / 35 − 33 / 35 ) ⋅ ( 14 21 − 14 0 175 − 70 0 0 35 ) = ( 12 − 51 4 6 167 − 68 − 4 24 − 41 ) {\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}}} Q R = A {\displaystyle QR=A} 이다. Q R {\displaystyle QR} 분해 된다.그러나,
분수 에의한 부동소수점 연산이 관계함으로 오차가 발생할 수 있다.
RQ 분해와의 관계 R Q {\displaystyle RQ} 분해는 행렬 A {\displaystyle A} 를 상삼각행렬 R {\displaystyle R} (직각 삼각형이라고도 함) 및 직교 행렬 Q {\displaystyle Q} 의 곱으로 변환한다. Q R {\displaystyle QR} 분해와의 유일한 차이점은 행렬의 순서이다.
Q R {\displaystyle QR} 분해는 첫 번째 열에서 시작된 A {\displaystyle A} 행렬의 열의 그람-슈미트 직교화이다.
R Q {\displaystyle RQ} 분해는 마지막 행에서 시작하는 A {\displaystyle A} 행렬의 행의 그람-슈미트 직교화이다.
장점과 단점 그람-슈미트 프로세스는 본질적으로 수치적으로 불안정할 수 있다. 투영법의 적용에는 직교화에 대한 주요한 기하학적 유추가 있지만 직교화 자체는 수치 오류가 발생하기 쉽다. 그러나 구현의 용이함이 중요한 장점이다. 사전 작성된 선형 대수 라이브러리(library)를 사용할 수 없거나 용이하지 않은 경우, 이 알고리즘을 프로토타입(prototype)에 사용할 수 있는 유용한 알고리즘으로 적용할 수 있다.
하우스홀더 방법 하우스홀더 리플렉터 (하우스홀더 변환,Householder reflection)를 이용하여 한 열씩을 상삼각행렬 로 바꾸어감으로써 Q {\displaystyle Q} 와 R {\displaystyle R} 을 구할 수 있다. 이 방법은 Q {\displaystyle Q} 행렬을 하우스홀더 행렬의 곱으로 구해주기 때문에, 직접 Q {\displaystyle Q} 를 구할 필요가 없을 때 유용하다. 또, 그람-슈미트 방법과는 달리, 부동소수점 연산에서도 오차가 누적되지 않기 때문에, 실제로 더 많이 활용된다.
예 A = ( 12 − 51 4 6 167 − 68 − 4 24 − 41 ) {\displaystyle A={\begin{pmatrix}12&-51&4\\6&167&-68\\-4&24&-41\end{pmatrix}}} 먼저 행렬 A {\displaystyle A} 의 첫 번째 열을 벡터로 변환하는 리플렉션을 찾아야한다.
‖ a 1 ‖ e 1 = ( 14 , 0 , 0 ) T {\displaystyle \|{a}_{1}\|\;{e}_{1}=(14,0,0)^{T}} 에서,벡터 a 1 = ( 12 , 6 , − 4 ) T {\displaystyle {a}_{1}=(12,6,-4)^{T}} u = x − α e 1 {\displaystyle {u}={x}-\alpha {e}_{1}} v = u ‖ u ‖ {\displaystyle {v}={{u} \over \|{u}\|}} α = 14 {\displaystyle \alpha =14} x = a 1 = ( 12 , 6 , − 4 ) T {\displaystyle {x}={a}_{1}=(12,6,-4)^{T}} 따라서,
u = ( − 2 , 6 , − 4 ) T = ( 2 ) ( − 1 , 3 , − 2 ) T {\displaystyle {u}=(-2,6,-4)^{T}=({2})(-1,3,-2)^{T}} v = ( − 1 , 3 , − 2 ) T 14 {\displaystyle {v}={{(-1,3,-2)^{T}} \over {\sqrt {14}}}} 하우스홀더 행렬 Q = I − 2 v v T 1 {\displaystyle Q=I-2{{vv^{T}} \over {1}}} 에서,
Q 1 = I − 2 ( − 1 3 − 2 ) 14 ( − 1 3 − 2 ) 14 {\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}}}} Q 1 = I − 2 14 14 ( − 1 3 − 2 ) ( − 1 3 − 2 ) {\displaystyle Q_{1}=I-{2 \over {\sqrt {14}}{\sqrt {14}}}{\begin{pmatrix}-1\\3\\-2\end{pmatrix}}{\begin{pmatrix}-1&3&-2\end{pmatrix}}} = I − 1 7 ( 1 − 3 2 − 3 9 − 6 2 − 6 4 ) {\displaystyle =I-{1 \over 7}{\begin{pmatrix}1&-3&2\\-3&9&-6\\2&-6&4\end{pmatrix}}} = ( 6 / 7 3 / 7 − 2 / 7 3 / 7 − 2 / 7 6 / 7 − 2 / 7 6 / 7 3 / 7 ) . {\displaystyle ={\begin{pmatrix}6/7&3/7&-2/7\\3/7&-2/7&6/7\\-2/7&6/7&3/7\\\end{pmatrix}}.} 확인해보면,
Q 1 A = ( 14 21 − 14 0 − 49 − 14 0 168 − 77 ) {\displaystyle Q_{1}A={\begin{pmatrix}14&21&-14\\0&-49&-14\\0&168&-77\end{pmatrix}}} 삼각행렬에 접근하고 있음을 알 수 있다. 3 {\displaystyle 3} 행 2 {\displaystyle 2} 열에서 ( 3 , 2 ) {\displaystyle (3,2)} 의 성분 값을 0 {\displaystyle 0} 으로 만들면 상삼각행렬 을 얻게 된다.
( 1 , 1 ) {\displaystyle (1,1)} 소행렬식 에서 다시 위의 절차를 반복해보면,
A ′ = M 11 = ( − 49 − 14 168 − 77 ) {\displaystyle A'=M_{11}={\begin{pmatrix}-49&-14\\168&-77\end{pmatrix}}} 위와 같은 방법으로 하우스홀더 변환(Householder transformation)된 행렬을 얻고,
Q 2 = ( 1 0 0 0 − 7 / 25 24 / 25 0 24 / 25 7 / 25 ) {\displaystyle Q_{2}={\begin{pmatrix}1&0&0\\0&-7/25&24/25\\0&24/25&7/25\end{pmatrix}}} Q 1 , Q 2 {\displaystyle Q_{1},Q_{2}} 에서 각각 전치행렬 을 수행한 후 프로세스가 올바르게 작동하는지 확인해보고, Q 1 = Q 1 T , Q 2 = Q 2 T {\displaystyle Q_{1}=Q_{1}^{T},Q_{2}=Q_{2}^{T}} 그리고나서,
Q = Q 1 T Q 2 T = ( 6 / 7 − 69 / 175 58 / 175 3 / 7 158 / 175 − 6 / 175 − 2 / 7 6 / 35 33 / 35 ) {\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}}} 그리고,
Q = Q 1 T Q 2 T = ( 0.8571 − 0.3943 0.3314 0.4286 0.9029 − 0.0343 − 0.2857 0.1714 0.9429 ) {\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}}} R = Q 2 Q 1 A = Q T A = ( 14 21 − 14 0 175 − 70 0 0 − 35 ) {\displaystyle R=Q_{2}Q_{1}A=Q^{T}A={\begin{pmatrix}14&21&-14\\0&175&-70\\0&0&-35\end{pmatrix}}} 행렬 Q {\displaystyle Q} 는 직교행렬 이고 R {\displaystyle R} 은 상삼각행렬 이되고 Q R = A {\displaystyle QR=A} 로 Q R {\displaystyle QR} 분해된다.
기븐스 회전 기븐스 행렬 은 특정위치에서 성분값을 0 {\displaystyle 0} 으로 조작할 수 있는 방법으로 기븐스 회전 을 제공한다.
이것은 임의의 행렬을 직교행렬 과 특정위치의 성분값이 0 {\displaystyle 0} 인 상삼각행렬 로 분해되게 유도할 수 있게된다.
예 A = ( a 11 a 12 a 13 a 21 a 22 a 23 a 31 a 32 a 33 ) {\displaystyle A={\begin{pmatrix}a_{11}&a_{12}&a_{13}\\a_{21}&a_{22}&a_{23}\\a_{31}&a_{32}&a_{33}\end{pmatrix}}} A = ( 12 − 51 4 6 167 − 68 − 4 24 − 41 ) {\displaystyle A={\begin{pmatrix}12&-51&4\\6&167&-68\\-4&24&-41\end{pmatrix}}} a 31 = − 4 {\displaystyle \mathbf {a} _{31}=-4} G 1 , ( 12 , − 4 ) {\displaystyle G_{1},(12,-4)} θ = arctan ( − ( − 4 ) 12 ) {\displaystyle \theta =\arctan \left({-(-4) \over 12}\right)} G 1 = ( cos ( θ ) 0 − sin ( θ ) 0 1 0 sin ( θ ) 0 cos ( θ ) ) {\displaystyle G_{1}={\begin{pmatrix}\cos(\theta )&0&-\sin(\theta )\\0&1&0\\\sin(\theta )&0&\cos(\theta )\end{pmatrix}}} = ( 0.94868... 0 − 0.31622... 0 1 0 0.31622... 0 0.94868... ) {\displaystyle ={\begin{pmatrix}0.94868...&0&-0.31622...\\0&1&0\\0.31622...&0&0.94868...\end{pmatrix}}} G 1 ⋅ A {\displaystyle G_{1}\cdot A} 는 a 31 = 0 {\displaystyle \mathbf {a} _{31}=0} 으로 조작된다. G 1 A = ( 12.64911... − 55.97231... 16.76007... 6 167 − 68 0 6.64078... − 37.6311... ) {\displaystyle G_{1}A={\begin{pmatrix}12.64911...&-55.97231...&16.76007...\\6&167&-68\\0&6.64078...&-37.6311...\end{pmatrix}}} G 2 {\displaystyle G_{2}} 그리고 G 3 {\displaystyle G_{3}} 도 이러한 절차를 반복한다.
a 21 = 0 {\displaystyle a_{21}=0} 그리고 a 32 = 0 {\displaystyle a_{32}=0} 으로 조작된다.결과로 상삼각행렬 R {\displaystyle R} 을 얻는다.따라서,
G 3 ⋅ G 2 ⋅ G 1 = Q T {\displaystyle G_{3}\cdot G_{2}\cdot G_{1}=Q^{T}} G 3 G 2 G 1 A = Q T A = R {\displaystyle G_{3}G_{2}G_{1}A=Q^{T}A=R} ( Q T ) T = Q {\displaystyle \left(Q^{T}\right)^{T}=Q} 직교행렬에서,
Q T = Q − 1 , Q Q T = Q T Q = I {\displaystyle Q^{T}=Q^{-1},QQ^{T}=Q^{T}Q=I} 그리고, Q R = A {\displaystyle QR=A} 이다.
A = Q R {\displaystyle A=QR} 로 분해된다.