선형대수학 에서 QR 분해 (영어 : QR decomposition, QR factorization )는 실수 성분 정사각 행렬 을 직교 행렬 와 상삼각 행렬 의 곱으로 나타내는 행렬 분해
M
=
Q
R
{\displaystyle M=QR}
[ 1] 그람-슈미트 과정 이나 하우스홀더 행렬 이나 기븐스 회전 을 통해 얻을 수 있으며, 선형 최소 제곱법 이나 QR 알고리즘 따위에서 쓰인다.
실수체 또는 복소수체
K
{\displaystyle \mathbb {K} }
m
×
n
{\displaystyle m\times n}
M
{\displaystyle M}
M
{\displaystyle M}
(두꺼운) QR 분해 (영어 : (thick) QR decomposition )라고 한다.[ 2] :246, Theorem 5.2.1
M
=
Q
R
{\displaystyle M=QR}
여기서
Q
{\displaystyle Q}
K
{\displaystyle \mathbb {K} }
m
×
m
{\displaystyle m\times m}
정사각 행렬 이며,
Q
{\displaystyle Q}
선형 생성 의 정규 직교 기저 를 이룬다. 즉,
Q
{\displaystyle Q}
K
=
R
{\displaystyle \mathbb {K} =\mathbb {R} }
직교 행렬 ,
K
=
C
{\displaystyle \mathbb {K} =\mathbb {C} }
유니터리 행렬 이다.
R
{\displaystyle R}
K
{\displaystyle \mathbb {K} }
m
×
n
{\displaystyle m\times n}
i
>
j
{\displaystyle i>j}
R
i
j
=
0
{\displaystyle R_{ij}=0}
상삼각 행렬 이다.실수체 또는 복소수체
K
{\displaystyle \mathbb {K} }
m
×
n
{\displaystyle m\times n}
M
{\displaystyle M}
m
≥
n
{\displaystyle m\geq n}
M
{\displaystyle M}
M
{\displaystyle M}
얇은 QR 분해 (영어 : thin QR decomposition, reduced QR decomposition )라고 한다.[ 2] :248, Theorem 5.2.3
M
=
Q
′
R
′
{\displaystyle M=Q'R'}
여기서
Q
′
{\displaystyle Q'}
K
{\displaystyle \mathbb {K} }
m
×
n
{\displaystyle m\times n}
Q
′
{\displaystyle Q'}
선형 생성 의 정규 직교 기저 를 이룬다. 그러나, 정사각 행렬 일 필요가 없으므로 직교 행렬 이나 유니터리 행렬 이 아닐 수 있다.
R
′
{\displaystyle R'}
K
{\displaystyle \mathbb {K} }
n
×
n
{\displaystyle n\times n}
상삼각 행렬 이다.물론, 정사각 행렬 의 경우 (
m
=
n
{\displaystyle m=n}
m
≥
n
{\displaystyle m\geq n}
M
=
Q
R
{\displaystyle M=QR}
Q
′
{\displaystyle Q'}
Q
{\displaystyle Q}
n
{\displaystyle n}
m
×
n
{\displaystyle m\times n}
R
′
{\displaystyle R'}
R
{\displaystyle R}
n
{\displaystyle n}
n
×
n
{\displaystyle n\times n}
Q
=
(
Q
′
Q
″
)
{\displaystyle Q={\begin{pmatrix}Q'&Q''\end{pmatrix}}}
R
=
(
R
′
0
)
{\displaystyle R={\begin{pmatrix}R'\\0\end{pmatrix}}}
이므로
M
=
Q
R
=
(
Q
′
Q
″
)
(
R
′
0
)
=
Q
′
R
′
+
Q
″
0
=
Q
′
R
′
{\displaystyle M=QR={\begin{pmatrix}Q'&Q''\end{pmatrix}}{\begin{pmatrix}R'\\0\end{pmatrix}}=Q'R'+Q''0=Q'R'}
이며, 이는
M
{\displaystyle M}
다음 두 조건이 서로 동치 이다.
rank
M
=
n
{\displaystyle \operatorname {rank} M=n}
rank
{\displaystyle \operatorname {rank} }
계수 이다.
M
{\displaystyle M}
선형 독립 집합 을 이룬다.또한, 이 조건은
m
≥
n
{\displaystyle m\geq n}
m
=
n
{\displaystyle m=n}
동치 이다.
M
{\displaystyle M}
가역 행렬 이다.만약
rank
M
=
n
{\displaystyle \operatorname {rank} M=n}
Q
{\displaystyle Q}
M
{\displaystyle M}
선형 생성 의 정규 직교 기저 를 이룬다. 보다 일반적으로,
k
=
1
,
…
,
n
{\displaystyle k=1,\dots ,n}
Q
{\displaystyle Q}
k
{\displaystyle k}
M
{\displaystyle M}
k
{\displaystyle k}
선형 생성 의 정규 직교 기저 를 이룬다.
M
{\displaystyle M}
j
{\displaystyle j}
Q
{\displaystyle Q}
j
{\displaystyle j}
선형 결합 인 사실은
R
{\displaystyle R}
상삼각성 에 대응한다.
Q
{\displaystyle Q}
n
+
1
{\displaystyle n+1}
m
{\displaystyle m}
M
{\displaystyle M}
선형 생성 의 직교 여공간 의 정규 직교 기저 를 이룬다.
i
=
1
,
…
,
n
{\displaystyle i=1,\dots ,n}
R
i
i
≠
0
{\displaystyle R_{ii}\neq 0}
R
′
{\displaystyle R'}
가역 행렬 이다.
R
i
i
>
0
{\displaystyle R_{ii}>0}
i
=
1
,
…
,
n
{\displaystyle i=1,\dots ,n}
R
{\displaystyle R}
R
′
{\displaystyle R'}
Q
′
{\displaystyle Q'}
R
′
{\displaystyle R'}
A
†
A
{\displaystyle A^{\dagger }A}
숄레스키 분해 의 상삼각 성분과 같다. 그러나
Q
″
{\displaystyle Q''}
이에 따라, QR 분해는 일반적으로 유일하지 않으며,
rank
M
=
n
{\displaystyle \operatorname {rank} M=n}
m
>
n
{\displaystyle m>n}
rank
M
=
n
{\displaystyle \operatorname {rank} M=n}
M
{\displaystyle M}
가역 행렬 의 QR 분해는 유일하다.
벡터
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}
그러나,
분수 에의한 부동소수점 연산이 관계함으로 오차가 발생할 수 있다.
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}
또, 그람-슈미트 방법은 컴퓨터를 활용하여 계산할 때 0으로 계산되어야 하는 R의 성분이 0이 아닌 값들을 가지는 경우가 많다. 이는 그람-슈미트 방법은 분수의 연산을 수반하고 이에 따른 부동소수점 연산의 오차가 발생하기 때문이다. 크기가 작은 행렬에서는 이 문제가 크게 작용하지 않으나, 크기가 커질수록 오차도 커지게 된다. 때문에 오차를 줄이기 위해서 하우스홀더 변환을 사용하며 본질적으로 이 변환은
R
{\displaystyle R}
Q
{\displaystyle Q}
R
{\displaystyle R}
대역폭 이 넓고 병렬화가 불가능하다는 단점이 있다.
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}
이 부분의 본문은 그람-슈미트 과정입니다.
![{\displaystyle A=[{\begin{array}{llll}\mathbf {a} _{1}&\mathbf {a} _{2}&\cdots &\mathbf {a} _{n}\end{array}}]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/325a406d40122d443a59a687dc180994dd443754)
![{\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)
