行列分解
線形代数 において 、 QR 分解( QR 因数分解 または QU 因数分解 とも呼ばれる) は、行列 A を正規直交行列 Q と上三角行列 R の積 A = QR に分解することです 。QR 分解 は 、 線形 最小 二乗 ( LLS ) 問題 を 解く ため に よく使用され、特定の 固有値アルゴリズム である QR アルゴリズム の基礎となります 。
事例と定義
正方行列 任意の実 正方行列 Aは 次のように分解できる。
あ = 質問 R 、
{\displaystyle A=QR,}
ここで、 Q は 直交行列 （列は 直交 単位ベクトル 、つまり ） であり、 R は 上 三角行列 （直角三角行列とも呼ばれる）です。A が可逆 である場合 、 R の 対 角要素が正であることを条件に因数分解は一意です 。
質問
T
=
質問
− 1
{\displaystyle Q^{\textsf {T}}=Q^{-1}}
代わりに A が 複素正方行列である場合、分解 A = QR が存在します。ここで、 Qは ユニタリ行列 です (つまり、 共役転置 )。
質問
†
=
質問
− 1
{\displaystyle Q^{\dagger }=Q^{-1}}
A が n 個 の線形独立な 列を持つ 場合 、 Q の最初の n列は A の 列空間 の 正規直交基底 を形成します 。より一般的には、 Q の最初の k 列は、任意の 1 ≤ k ≤ n に対して、 A の最初の k 列の 範囲 の正規直交基底を形成します 。 [1] A の任意の列 k が Q の最初の k 列のみに依存する という事実は、 R の三角形形式に対応します 。 [1]
長方形マトリックス より一般的には、 m ≥ n の複素 m × n 行列 A を、 m × m ユニタリ行列 Q と m × n 上三角行列 R の積として因数分解することができます。 m × n 上三角行列の一番下の ( m − n ) 行はすべてゼロで構成されているため、 R 、または R と Q の両方を 分割すると便利なことがよくあります 。
あ = 質問 R = 質問
[
R
1
0
]
=
[
質問
1
質問
2
]
[
R
1
0
]
=
質問
1
R
1
、
{\displaystyle A=QR=Q{\begin{bmatrix}R_{1}\\0\end{bmatrix}}={\begin{bmatrix}Q_{1}&Q_{2}\end{bmatrix}}{\begin{bmatrix}R_{1}\\0\end{bmatrix}}=Q_{1}R_{1},}
ここで、 R 1 は n × n の上三角行列、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 分解 と呼び 、 Trefethen と Bau はこれを 簡約 QR 分解 と呼んでいます。 [1] A がフル ランク n で、 R 1 の対角要素が正である ことを要求すると、 R 1 と Q 1 は 一意ですが、一般に Q 2 は 一意ではありません。 R 1 は、 A * A ( A が実数の場合は A T A )の コレスキー分解 の上三角因子に等しくなります 。
QL、RQ、LQ分解 同様に、 Lが 下 三角行列である QL、RQ、LQ 分解を定義できます 。
QR分解の計算 QR 分解を実際に計算する方法は、 グラム・シュミット過程 、 ハウスホルダー変換 、 ギブンズ回転 などいくつかあります。それぞれに長所と短所があります。
グラム・シュミット法の使用 内積を持つ （ または 複素数の場合は）
完全な列ランク 行列 の列に グラム・シュミット過程 を適用することを考えます。
あ =
[
1つの
1
⋯
1つの
ん
]
{\displaystyle A={\begin{bmatrix}\mathbf {a} _{1}&\cdots &\mathbf {a} _{n}\end{bmatrix}}}
⟨
ヴ
、
わ
⟩ =
ヴ
T
わ
{\displaystyle \langle \mathbf {v} ,\mathbf {w} \rangle =\mathbf {v} ^{\textsf {T}}\mathbf {w} }
⟨
v
,
w
⟩
=
v
†
w
{\displaystyle \langle \mathbf {v} ,\mathbf {w} \rangle =\mathbf {v} ^{\dagger }\mathbf {w} }
投影 を定義します :
proj
u
a
=
⟨
u
,
a
⟩
⟨
u
,
u
⟩
u
{\displaystyle \operatorname {proj} _{\mathbf {u} }\mathbf {a} ={\frac {\left\langle \mathbf {u} ,\mathbf {a} \right\rangle }{\left\langle \mathbf {u} ,\mathbf {u} \right\rangle }}{\mathbf {u} }}
それから：
u
1
=
a
1
,
e
1
=
u
1
‖
u
1
‖
u
2
=
a
2
−
proj
u
1
a
2
,
e
2
=
u
2
‖
u
2
‖
u
3
=
a
3
−
proj
u
1
a
3
−
proj
u
2
a
3
,
e
3
=
u
3
‖
u
3
‖
⋮
⋮
u
k
=
a
k
−
∑
j
=
1
k
−
1
proj
u
j
a
k
,
e
k
=
u
k
‖
u
k
‖
{\displaystyle {\begin{aligned}\mathbf {u} _{1}&=\mathbf {a} _{1},&\mathbf {e} _{1}&={\frac {\mathbf {u} _{1}}{\|\mathbf {u} _{1}\|}}\\\mathbf {u} _{2}&=\mathbf {a} _{2}-\operatorname {proj} _{\mathbf {u} _{1}}\mathbf {a} _{2},&\mathbf {e} _{2}&={\frac {\mathbf {u} _{2}}{\|\mathbf {u} _{2}\|}}\\\mathbf {u} _{3}&=\mathbf {a} _{3}-\operatorname {proj} _{\mathbf {u} _{1}}\mathbf {a} _{3}-\operatorname {proj} _{\mathbf {u} _{2}}\mathbf {a} _{3},&\mathbf {e} _{3}&={\frac {\mathbf {u} _{3}}{\|\mathbf {u} _{3}\|}}\\&\;\;\vdots &&\;\;\vdots \\\mathbf {u} _{k}&=\mathbf {a} _{k}-\sum _{j=1}^{k-1}\operatorname {proj} _{\mathbf {u} _{j}}\mathbf {a} _{k},&\mathbf {e} _{k}&={\frac {\mathbf {u} _{k}}{\|\mathbf {u} _{k}\|}}\end{aligned}}}
新しく計算された正規直交基底上の s を
次のように表現できます。
a
i
{\displaystyle \mathbf {a} _{i}}
a
1
=
⟨
e
1
,
a
1
⟩
e
1
a
2
=
⟨
e
1
,
a
2
⟩
e
1
+
⟨
e
2
,
a
2
⟩
e
2
a
3
=
⟨
e
1
,
a
3
⟩
e
1
+
⟨
e
2
,
a
3
⟩
e
2
+
⟨
e
3
,
a
3
⟩
e
3
⋮
a
k
=
∑
j
=
1
k
⟨
e
j
,
a
k
⟩
e
j
{\displaystyle {\begin{aligned}\mathbf {a} _{1}&=\left\langle \mathbf {e} _{1},\mathbf {a} _{1}\right\rangle \mathbf {e} _{1}\\\mathbf {a} _{2}&=\left\langle \mathbf {e} _{1},\mathbf {a} _{2}\right\rangle \mathbf {e} _{1}+\left\langle \mathbf {e} _{2},\mathbf {a} _{2}\right\rangle \mathbf {e} _{2}\\\mathbf {a} _{3}&=\left\langle \mathbf {e} _{1},\mathbf {a} _{3}\right\rangle \mathbf {e} _{1}+\left\langle \mathbf {e} _{2},\mathbf {a} _{3}\right\rangle \mathbf {e} _{2}+\left\langle \mathbf {e} _{3},\mathbf {a} _{3}\right\rangle \mathbf {e} _{3}\\&\;\;\vdots \\\mathbf {a} _{k}&=\sum _{j=1}^{k}\left\langle \mathbf {e} _{j},\mathbf {a} _{k}\right\rangle \mathbf {e} _{j}\end{aligned}}}
ここで 、 これは行列形式で書くことができます。
⟨
e
i
,
a
i
⟩
=
‖
u
i
‖
{\displaystyle \left\langle \mathbf {e} _{i},\mathbf {a} _{i}\right\rangle =\left\|\mathbf {u} _{i}\right\|}
A
=
Q
R
{\displaystyle A=QR}
どこ：
Q
=
[
e
1
⋯
e
n
]
{\displaystyle Q={\begin{bmatrix}\mathbf {e} _{1}&\cdots &\mathbf {e} _{n}\end{bmatrix}}}
そして
R
=
[
⟨
e
1
,
a
1
⟩
⟨
e
1
,
a
2
⟩
⟨
e
1
,
a
3
⟩
⋯
⟨
e
1
,
a
n
⟩
0
⟨
e
2
,
a
2
⟩
⟨
e
2
,
a
3
⟩
⋯
⟨
e
2
,
a
n
⟩
0
0
⟨
e
3
,
a
3
⟩
⋯
⟨
e
3
,
a
n
⟩
⋮
⋮
⋮
⋱
⋮
0
0
0
⋯
⟨
e
n
,
a
n
⟩
]
.
{\displaystyle R={\begin{bmatrix}\langle \mathbf {e} _{1},\mathbf {a} _{1}\rangle &\langle \mathbf {e} _{1},\mathbf {a} _{2}\rangle &\langle \mathbf {e} _{1},\mathbf {a} _{3}\rangle &\cdots &\langle \mathbf {e} _{1},\mathbf {a} _{n}\rangle \\0&\langle \mathbf {e} _{2},\mathbf {a} _{2}\rangle &\langle \mathbf {e} _{2},\mathbf {a} _{3}\rangle &\cdots &\langle \mathbf {e} _{2},\mathbf {a} _{n}\rangle \\0&0&\langle \mathbf {e} _{3},\mathbf {a} _{3}\rangle &\cdots &\langle \mathbf {e} _{3},\mathbf {a} _{n}\rangle \\\vdots &\vdots &\vdots &\ddots &\vdots \\0&0&0&\cdots &\langle \mathbf {e} _{n},\mathbf {a} _{n}\rangle \\\end{bmatrix}}.}
例 分解を考えてみましょう
A
=
[
12
−
51
4
6
167
−
68
−
4
24
−
41
]
.
{\displaystyle A={\begin{bmatrix}12&-51&4\\6&167&-68\\-4&24&-41\end{bmatrix}}.}
正規直交行列には という 性質があることを思い出してください 。
Q
{\displaystyle Q}
Q
T
Q
=
I
{\displaystyle Q^{\textsf {T}}Q=I}
次に、グラム・シュミットの法則を使って次のように
計算します。
Q
{\displaystyle Q}
U
=
[
u
1
u
2
u
3
]
=
[
12
−
69
−
58
/
5
6
158
6
/
5
−
4
30
−
33
]
;
Q
=
[
u
1
‖
u
1
‖
u
2
‖
u
2
‖
u
3
‖
u
3
‖
]
=
[
6
/
7
−
69
/
175
−
58
/
175
3
/
7
158
/
175
6
/
175
−
2
/
7
6
/
35
−
33
/
35
]
.
{\displaystyle {\begin{aligned}U={\begin{bmatrix}\mathbf {u} _{1}&\mathbf {u} _{2}&\mathbf {u} _{3}\end{bmatrix}}&={\begin{bmatrix}12&-69&-58/5\\6&158&6/5\\-4&30&-33\end{bmatrix}};\\Q={\begin{bmatrix}{\frac {\mathbf {u} _{1}}{\|\mathbf {u} _{1}\|}}&{\frac {\mathbf {u} _{2}}{\|\mathbf {u} _{2}\|}}&{\frac {\mathbf {u} _{3}}{\|\mathbf {u} _{3}\|}}\end{bmatrix}}&={\begin{bmatrix}6/7&-69/175&-58/175\\3/7&158/175&6/175\\-2/7&6/35&-33/35\end{bmatrix}}.\end{aligned}}}
したがって、
Q
T
A
=
Q
T
Q
R
=
R
;
R
=
Q
T
A
=
[
14
21
−
14
0
175
−
70
0
0
35
]
.
{\displaystyle {\begin{aligned}Q^{\textsf {T}}A&=Q^{\textsf {T}}Q\,R=R;\\R&=Q^{\textsf {T}}A={\begin{bmatrix}14&21&-14\\0&175&-70\\0&0&35\end{bmatrix}}.\end{aligned}}}
RQ分解との関係 RQ 分解は、行列 Aを上三角行列 R (直角三角とも呼ばれる) と直交行列 Q の積に変換します 。QR 分解との唯一の違いは、これらの行列の順序です。
QR分解は、最初の列から始まる
A の列のグラム・シュミット直交化です。
RQ分解は、最後の行から始まる
A の行のグラム・シュミット直交化です。
利点と欠点 グラム・シュミット法は本質的に数値的に不安定です。投影法の適用は直交化と幾何学的に類似していますが、直交化自体は数値誤差が生じやすい傾向があります。大きな利点は実装が簡単なことです。
世帯主の反射を利用する QR 分解のハウスホルダー反射: 目標は、ベクトルを と同じ長さで と同一直線上のベクトルに変換する線形変換を見つけることです。直交投影 (グラム・シュミット) を使用することもできますが、ベクトル と が直交に近い 場合は数値的に不安定になります 。代わりに、ハウスホルダー反射は点線 ( と の間の角度を二等分するように選択 ) を反射します。 この変換の最大角度は 45 度です。
x
{\displaystyle \mathbf {x} }
e
1
{\displaystyle \mathbf {e} _{1}}
x
{\displaystyle \mathbf {x} }
e
1
{\displaystyle \mathbf {e} _{1}}
x
{\displaystyle \mathbf {x} }
e
1
{\displaystyle \mathbf {e} _{1}}
ハウス ホルダー反射 （または ハウスホルダー変換）は、ベクトルをある 平面 または 超平面 に反射させる変換です。この操作を使用して、 m ≥ n の m 行 n 列の行列 の QR 分解を計算できます 。
A
{\displaystyle A}
Q は 、1 つの座標を除くすべての座標が消えるようにベクトルを反転するために使用できます。
を任意の実数 m 次元列ベクトルとし、 スカラー α に対してとなるもの と する 。アルゴリズムが 浮動小数点演算 を用いて実装される場合、 α はの k 番目の座標 と反対の符号を取得する必要があり 、 ここで は、 有意性の喪失を回避するために、行列 A の 最終的な上三角形式でそれ以降のすべての要素が 0 になるピボット座標となる 。複素数の場合、 [2]と設定する。
x
{\displaystyle \mathbf {x} }
A
{\displaystyle A}
‖
x
‖
=
|
α
|
{\displaystyle \|\mathbf {x} \|=|\alpha |}
x
{\displaystyle \mathbf {x} }
x
k
{\displaystyle x_{k}}
α
=
−
e
i
arg
x
k
‖
x
‖
{\displaystyle \alpha =-e^{i\arg x_{k}}\|\mathbf {x} \|}
そして、以下のQ の構築では、転置を共役転置に置き換えます 。
そして、 ベクトル [1 0 ⋯ 0] T 、 || · || はユークリッド ノルム 、 m × m の単位行列
であり、
e
1
{\displaystyle \mathbf {e} _{1}}
I
{\displaystyle I}
u
=
x
−
α
e
1
,
v
=
u
‖
u
‖
,
Q
=
I
−
2
v
v
T
.
{\displaystyle {\begin{aligned}\mathbf {u} &=\mathbf {x} -\alpha \mathbf {e} _{1},\\\mathbf {v} &={\frac {\mathbf {u} }{\|\mathbf {u} \|}},\\Q&=I-2\mathbf {v} \mathbf {v} ^{\textsf {T}}.\end{aligned}}}
または、 複雑な
場合は
A
{\displaystyle A}
Q
=
I
−
2
v
v
†
.
{\displaystyle Q=I-2\mathbf {v} \mathbf {v} ^{\dagger }.}
Q
{\displaystyle Q}
は、対称かつ直交（複素数の場合はエルミートかつユニタリ）な
m 行 m 列のハウスホルダー行列であり、
Q
x
=
[
α
0
⋮
0
]
.
{\displaystyle Q\mathbf {x} ={\begin{bmatrix}\alpha \\0\\\vdots \\0\end{bmatrix}}.}
これを使用して、 m 行 n 列の行列 A を 徐々に上 三角形 式に変換できます。まず、 行列の最初の列 x を 選択したときに得られるハウスホルダー行列 Q 1 を A に掛けます。これにより、左の列 (最初の行を除く) がゼロの
行列 Q 1 Aが生成されます。
Q
1
A
=
[
α
1
⋆
⋯
⋆
0
⋮
A
′
0
]
{\displaystyle Q_{1}A={\begin{bmatrix}\alpha _{1}&\star &\cdots &\star \\0&&&\\\vdots &&A'&\\0&&&\end{bmatrix}}}
これをA ′ （ Q 1 A から最初の行と最初の列を削除して取得） に対して繰り返すと、ハウスホルダー行列 Q ′ 2が得られます。 Q ′ 2 は Q 1 よりも小さいこと に注意してください。実際には A ′ではなく Q 1 A に対して動作させたいので 、左上に拡張して 1 を埋める必要があります。一般的には次のようになります。
Q
k
=
[
I
k
−
1
0
0
Q
k
′
]
.
{\displaystyle Q_{k}={\begin{bmatrix}I_{k-1}&0\\0&Q_{k}'\end{bmatrix}}.}
このプロセスを繰り返した 後 、
t
{\displaystyle t}
t
=
min
(
m
−
1
,
n
)
{\displaystyle t=\min(m-1,n)}
R
=
Q
t
⋯
Q
2
Q
1
A
{\displaystyle R=Q_{t}\cdots Q_{2}Q_{1}A}
は上三角行列です。
Q
T
=
Q
t
⋯
Q
2
Q
1
,
Q
=
Q
1
T
Q
2
T
⋯
Q
t
T
,
=
Q
1
Q
2
⋯
Q
t
,
{\displaystyle {\begin{aligned}Q^{\textsf {T}}&=Q_{t}\cdots Q_{2}Q_{1},\\Q&=Q_{1}^{\textsf {T}}Q_{2}^{\textsf {T}}\cdots Q_{t}^{\textsf {T}},\\&=Q_{1}Q_{2}\cdots Q_{t},\end{aligned}}}
A
=
Q
R
{\displaystyle A=QR}
は の QR 分解です 。
A
{\displaystyle A}
この方法は、 上記のグラム・シュミット法よりも
数値安定性に優れています。
次の表は、サイズがn の正方行列を想定して、ハウスホルダー変換による QR 分解の k 番目のステップでの演算数を示しています 。
これらの数値を n − 1ステップ（サイズ n の正方行列の場合 ）で合計すると、アルゴリズムの複雑さ（浮動小数点乗算の観点から）は次のように表される。
2
3
n
3
+
n
2
+
1
3
n
−
2
=
O
(
n
3
)
.
{\displaystyle {\frac {2}{3}}n^{3}+n^{2}+{\frac {1}{3}}n-2=O\left(n^{3}\right).}
例 分解を計算してみましょう
A
=
[
12
−
51
4
6
167
−
68
−
4
24
−
41
]
.
{\displaystyle A={\begin{bmatrix}12&-51&4\\6&167&-68\\-4&24&-41\end{bmatrix}}.}
まず、行列Aの最初の列で ある ベクトル を に 変換する反射を見つける必要があります 。
a
1
=
[
12
6
−
4
]
T
{\displaystyle \mathbf {a} _{1}={\begin{bmatrix}12&6&-4\end{bmatrix}}^{\textsf {T}}}
‖
a
1
‖
e
1
=
[
α
0
0
]
T
{\displaystyle \left\|\mathbf {a} _{1}\right\|\mathbf {e} _{1}={\begin{bmatrix}\alpha &0&0\end{bmatrix}}^{\textsf {T}}}
今、
u
=
x
−
α
e
1
,
{\displaystyle \mathbf {u} =\mathbf {x} -\alpha \mathbf {e} _{1},}
そして
v
=
u
‖
u
‖
.
{\displaystyle \mathbf {v} ={\frac {\mathbf {u} }{\|\mathbf {u} \|}}.}
ここ、
α
=
14
{\displaystyle \alpha =14}
そして
x
=
a
1
=
[
12
6
−
4
]
T
{\displaystyle \mathbf {x} =\mathbf {a} _{1}={\begin{bmatrix}12&6&-4\end{bmatrix}}^{\textsf {T}}}
したがって
u
=
[
−
2
6
−
4
]
T
=
2
[
−
1
3
−
2
]
T
{\displaystyle \mathbf {u} ={\begin{bmatrix}-2&6&-4\end{bmatrix}}^{\textsf {T}}=2{\begin{bmatrix}-1&3&-2\end{bmatrix}}^{\textsf {T}}}
そして 、 そして
v
=
1
14
[
−
1
3
−
2
]
T
{\displaystyle \mathbf {v} ={\frac {1}{\sqrt {14}}}{\begin{bmatrix}-1&3&-2\end{bmatrix}}^{\textsf {T}}}
Q
1
=
I
−
2
14
14
[
−
1
3
−
2
]
[
−
1
3
−
2
]
=
I
−
1
7
[
1
−
3
2
−
3
9
−
6
2
−
6
4
]
=
[
6
/
7
3
/
7
−
2
/
7
3
/
7
−
2
/
7
6
/
7
−
2
/
7
6
/
7
3
/
7
]
.
{\displaystyle {\begin{aligned}Q_{1}={}&I-{\frac {2}{{\sqrt {14}}{\sqrt {14}}}}{\begin{bmatrix}-1\\3\\-2\end{bmatrix}}{\begin{bmatrix}-1&3&-2\end{bmatrix}}\\={}&I-{\frac {1}{7}}{\begin{bmatrix}1&-3&2\\-3&9&-6\\2&-6&4\end{bmatrix}}\\={}&{\begin{bmatrix}6/7&3/7&-2/7\\3/7&-2/7&6/7\\-2/7&6/7&3/7\\\end{bmatrix}}.\end{aligned}}}
次に観察します:
Q
1
A
=
[
14
21
−
14
0
−
49
−
14
0
168
−
77
]
,
{\displaystyle Q_{1}A={\begin{bmatrix}14&21&-14\\0&-49&-14\\0&168&-77\end{bmatrix}},}
つまり、ほぼ三角行列ができあがったことになります。(3, 2) 要素をゼロにするだけで済みます。
(1, 1) マイナー を取り、このプロセスを再度適用して
A
′
=
M
11
=
[
−
49
−
14
168
−
77
]
.
{\displaystyle A'=M_{11}={\begin{bmatrix}-49&-14\\168&-77\end{bmatrix}}.}
上記と同じ方法で、ハウスホルダー変換の行列を得る。
Q
2
=
[
1
0
0
0
−
7
/
25
24
/
25
0
24
/
25
7
/
25
]
{\displaystyle Q_{2}={\begin{bmatrix}1&0&0\\0&-7/25&24/25\\0&24/25&7/25\end{bmatrix}}}
1 との直和を実行して、プロセスの次のステップが適切に機能することを確認します。
さて、私たちは
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}^{\textsf {T}}Q_{2}^{\textsf {T}}={\begin{bmatrix}6/7&-69/175&58/175\\3/7&158/175&-6/175\\-2/7&6/35&33/35\end{bmatrix}}.}
または、小数点4桁で、
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
]
R
=
Q
2
Q
1
A
=
Q
T
A
=
[
14
21
−
14
0
175
−
70
0
0
−
35
]
.
{\displaystyle {\begin{aligned}Q&=Q_{1}^{\textsf {T}}Q_{2}^{\textsf {T}}={\begin{bmatrix}0.8571&-0.3943&0.3314\\0.4286&0.9029&-0.0343\\-0.2857&0.1714&0.9429\end{bmatrix}}\\R&=Q_{2}Q_{1}A=Q^{\textsf {T}}A={\begin{bmatrix}14&21&-14\\0&175&-70\\0&0&-35\end{bmatrix}}.\end{aligned}}}
行列 Q は 直交行列であり、 R は上三角行列であるため、 必要な QR 分解は
A = QRです。
利点と欠点 ハウスホルダー変換の使用は、 R 行列にゼロを生成するメカニズムとして反射を使用するため、数値的に安定した QR 分解アルゴリズムの中で本質的に最も単純です。ただし、ハウスホルダー反射アルゴリズムは帯域幅が重く、並列化できません。これは、新しいゼロ要素を生成するすべての反射が、 Q 行列と R 行列の両方の全体を変更するためです 。
ギブンズ回転の使用 QR 分解は、一連の ギブンズ回転 で計算することもできます。各回転は、行列の副対角要素をゼロにして、 R 行列を形成します。すべてのギブンズ回転を連結すると、直交 Q 行列が形成されます。
実際には、ギブンズ回転は、行列全体を構築して行列の乗算を行うことによって実行されるわけではありません。代わりに、スパース要素を処理する余分な作業なしで、スパースギブンズ行列の乗算と同等のことを実行するギブンズ回転手順が使用されます。ギブンズ回転手順は、比較的少数の非対角要素のみをゼロにする必要がある状況で役立ち、 ハウスホルダー変換 よりも簡単に並列化できます。
例 分解を計算してみましょう
A
=
[
12
−
51
4
6
167
−
68
−
4
24
−
41
]
.
{\displaystyle A={\begin{bmatrix}12&-51&4\\6&167&-68\\-4&24&-41\end{bmatrix}}.}
まず、左下の要素 をゼロにする回転行列 を形成する必要があります 。 この行列はギブンズ回転法を使用して形成し、行列 と呼びます 。まず、ベクトル を回転させて 、 X 軸に沿うようにします 。このベクトルの角度は です 。 直交ギブンズ回転行列 を作成します 。
a
31
=
−
4
{\displaystyle a_{31}=-4}
G
1
{\displaystyle G_{1}}
[
12
−
4
]
{\displaystyle {\begin{bmatrix}12&-4\end{bmatrix}}}
θ
=
arctan
(
−
(
−
4
)
12
)
{\textstyle \theta =\arctan \left({\frac {-(-4)}{12}}\right)}
G
1
{\displaystyle G_{1}}
G
1
=
[
cos
(
θ
)
0
−
sin
(
θ
)
0
1
0
sin
(
θ
)
0
cos
(
θ
)
]
≈
[
0.94868
0
−
0.31622
0
1
0
0.31622
0
0.94868
]
{\displaystyle {\begin{aligned}G_{1}&={\begin{bmatrix}\cos(\theta )&0&-\sin(\theta )\\0&1&0\\\sin(\theta )&0&\cos(\theta )\end{bmatrix}}\\&\approx {\begin{bmatrix}0.94868&0&-0.31622\\0&1&0\\0.31622&0&0.94868\end{bmatrix}}\end{aligned}}}
そして、現在の結果では、要素 にゼロが含まれます 。
G
1
A
{\displaystyle G_{1}A}
a
31
{\displaystyle a_{31}}
G
1
A
≈
[
12.64911
−
55.97231
16.76007
6
167
−
68
0
6.64078
−
37.6311
]
{\displaystyle G_{1}A\approx {\begin{bmatrix}12.64911&-55.97231&16.76007\\6&167&-68\\0&6.64078&-37.6311\end{bmatrix}}}
同様に、ギブンズ行列 および を形成して 、 下対角要素 および をゼロにし 、 三角 行列 を形成すること もできます 。 直交行列 は、 すべてのギブンズ行列 の積から形成されます 。 したがって、 が得られ 、 QR 分解は です 。
G
2
{\displaystyle G_{2}}
G
3
{\displaystyle G_{3}}
a
21
{\displaystyle a_{21}}
a
32
{\displaystyle a_{32}}
R
{\displaystyle R}
Q
T
{\displaystyle Q^{\textsf {T}}}
Q
T
=
G
3
G
2
G
1
{\displaystyle Q^{\textsf {T}}=G_{3}G_{2}G_{1}}
G
3
G
2
G
1
A
=
Q
T
A
=
R
{\displaystyle G_{3}G_{2}G_{1}A=Q^{\textsf {T}}A=R}
A
=
Q
R
{\displaystyle A=QR}
利点と欠点 ギブンズ回転による QR 分解は、アルゴリズムを最大限に活用するために必要な行の順序を決定するのが簡単ではないため、実装が最も複雑です。ただし、新しいゼロ要素はそれぞれ、 ゼロにする要素がある行 ( i ) とその上の行 ( j ) にのみ影響するという大きな利点があります。これにより、ギブンズ回転アルゴリズムは、ハウスホルダー反射法よりも帯域幅効率が高く、並列化が容易になります。
a
i
j
{\displaystyle a_{ij}}
行列式または固有値の積への接続 QR分解を使って正方行列の行列式 を求めることができます 。行列が 次のように分解されるとします。
A
=
Q
R
{\displaystyle A=QR}
det
A
=
det
Q
det
R
.
{\displaystyle \det A=\det Q\det R.}
Q
{\displaystyle Q}
となるように選ぶことができる 。したがって、
det
Q
=
1
{\displaystyle \det Q=1}
det
A
=
det
R
=
∏
i
r
i
i
{\displaystyle \det A=\det R=\prod _{i}r_{ii}}
ここで、 は の対角要素です 。さらに、行列式は固有値の積に等しいので、
r
i
i
{\displaystyle r_{ii}}
R
{\displaystyle R}
∏
i
r
i
i
=
∏
i
λ
i
{\displaystyle \prod _{i}r_{ii}=\prod _{i}\lambda _{i}}
ここで は の固有値です 。
λ
i
{\displaystyle \lambda _{i}}
A
{\displaystyle A}
非正方複素行列の QR 分解の定義を導入し、固有値を特異値に置き換えることで、
上記の特性を非正方複素行列に拡張できます。
A
{\displaystyle A}
非正方行列 A の QR 分解から始めます。
A
=
Q
[
R
0
]
,
Q
†
Q
=
I
{\displaystyle A=Q{\begin{bmatrix}R\\0\end{bmatrix}},\qquad Q^{\dagger }Q=I}
ここで は ゼロ行列を表し、 は ユニタリ行列です。
0
{\displaystyle 0}
Q
{\displaystyle Q}
特異値分解 （SVD）と行列の行列式
の性質から、
|
∏
i
r
i
i
|
=
∏
i
σ
i
,
{\displaystyle {\Big |}\prod _{i}r_{ii}{\Big |}=\prod _{i}\sigma _{i},}
ここで、 は の特異値です 。
σ
i
{\displaystyle \sigma _{i}}
A
{\displaystyle A}
と の特異値は 同一であるが、複素固有値は異なる場合があることに注意する。しかし、 A が正方行列である場合、
A
{\displaystyle A}
R
{\displaystyle R}
∏
i
σ
i
=
|
∏
i
λ
i
|
.
{\displaystyle {\prod _{i}\sigma _{i}}={\Big |}\prod _{i}\lambda _{i}{\Big |}.}
したがって、QR 分解を使用すると、行列の固有値または特異値の積を効率的に計算できます。
列ピボット ピボットQR法は、通常のグラム・シュミット法とは異なり、各ステップの開始時に残っている最大の列（列ピボット）を取り 、 置換行列 P を導入する。
[3]
A
P
=
Q
R
⟺
A
=
Q
R
P
T
{\displaystyle AP=QR\quad \iff \quad A=QRP^{\textsf {T}}}
列ピボットは、 A が（ほぼ） ランク落ちである か、その疑いがある 場合に便利です。また、数値精度を向上させることもできます。P は通常、 Rの 対 角要素が増加しない ように選択されます。これを使用すると、 特異値分解 よりも低い計算コストで A の（数値）ランクを見つけることができ 、いわゆる ランク開示 QR アルゴリズム の基礎となります。
|
r
11
|
≥
|
r
22
|
≥
⋯
≥
|
r
n
n
|
{\displaystyle \left|r_{11}\right|\geq \left|r_{22}\right|\geq \cdots \geq \left|r_{nn}\right|}
線形逆問題の解法に使用 直接行列逆行列と比較すると、QR分解を用いた逆行列解は 条件数 が減少することからもわかるように数値的に安定している。 [4]
行列 が次元 、階数である 劣決定 ( )
m
<
n
{\displaystyle m<n}
線形問題を解くには 、 まず の転置行列の QR 分解を求めます 。 ここで 、 Q は 直交行列 (つまり ) であり、 R は 特殊 な形式 です。 ここでは は正方三角行列 で 、零行列の次元は です 。 代数計算を行うと、逆問題の解は次のように表せることが示されます。ここで、 は ガウス消去法 で 求めることも、 前方代入 で直接 計算することもできます 。後者の手法の方が数値精度が高く、計算量が少なくて済みます。
A
x
=
b
{\displaystyle A\mathbf {x} =\mathbf {b} }
A
{\displaystyle A}
m
×
n
{\displaystyle m\times n}
m
{\displaystyle m}
A
{\displaystyle A}
A
T
=
Q
R
{\displaystyle A^{\textsf {T}}=QR}
Q
T
=
Q
−
1
{\displaystyle Q^{\textsf {T}}=Q^{-1}}
R
=
[
R
1
0
]
{\displaystyle R=\left[{\begin{smallmatrix}R_{1}\\0\end{smallmatrix}}\right]}
R
1
{\displaystyle R_{1}}
m
×
m
{\displaystyle m\times m}
(
n
−
m
)
×
m
{\displaystyle (n-m)\times m}
x
=
Q
[
(
R
1
T
)
−
1
b
0
]
{\displaystyle \mathbf {x} =Q\left[{\begin{smallmatrix}\left(R_{1}^{\textsf {T}}\right)^{-1}\mathbf {b} \\0\end{smallmatrix}}\right]}
R
1
−
1
{\displaystyle R_{1}^{-1}}
(
R
1
T
)
−
1
b
{\displaystyle \left(R_{1}^{\textsf {T}}\right)^{-1}\mathbf {b} }
ノルム を最小化する 過剰決定 ( ) 問題の 解を求めるには 、 まず の QR 分解を求めます 。 この解は と表すことができます 。 ここ で は 完全な正規直交基底の 最初の列を含む行列 で 、 は 前と同じです。不足決定の場合と同等ですが、 を 明示的に反転せずに、 バック代入を 使用してこれを迅速かつ正確に求めることができます 。 ( これらは、 数値ライブラリによって「経済的な」QR 分解として提供されることがよくあります。)
x
^
{\displaystyle {\hat {\mathbf {x} }}}
m
≥
n
{\displaystyle m\geq n}
A
x
=
b
{\displaystyle A\mathbf {x} =\mathbf {b} }
‖
A
x
^
−
b
‖
{\displaystyle \left\|A{\hat {\mathbf {x} }}-\mathbf {b} \right\|}
A
{\displaystyle A}
A
=
Q
R
{\displaystyle A=QR}
x
^
=
R
1
−
1
(
Q
1
T
b
)
{\displaystyle {\hat {\mathbf {x} }}=R_{1}^{-1}\left(Q_{1}^{\textsf {T}}\mathbf {b} \right)}
Q
1
{\displaystyle Q_{1}}
m
×
n
{\displaystyle m\times n}
n
{\displaystyle n}
Q
{\displaystyle Q}
R
1
{\displaystyle R_{1}}
x
^
{\displaystyle {\hat {\mathbf {x} }}}
R
1
{\displaystyle R_{1}}
Q
1
{\displaystyle Q_{1}}
R
1
{\displaystyle R_{1}}
一般化 岩澤分解は、 QR 分解を半単純リー群に一般化します。
参照
参考文献
さらに読む ゴルブ、ジーン H. ; ヴァン・ローン、チャールズ F. (1996)、 マトリックス計算 (第 3 版)、ジョンズ・ホプキンス、 ISBN 978-0-8018-5414-9 。 ホーン、ロジャー A.; ジョンソン、チャールズ R. (1985)、 マトリックス分析 、ケンブリッジ大学出版局、第 2.8 節、 ISBN 0-521-38632-2 Press, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007)、「セクション 2.10. QR 分解」、 Numerical Recipes: The Art of Scientific Computing (第 3 版)、ニューヨーク: Cambridge University Press、 ISBN 978-0-521-88068-8
外部リンク オンライン行列計算機は行列の QR 分解を実行します。 LAPACKユーザーマニュアルには、QR分解を計算するためのサブルーチンの詳細が記載されています。 Mathematicaのユーザーマニュアルには、QR分解を計算するルーチンの詳細と例が記載されています。 ALGLIB には、C++、C#、Delphi などへの LAPACK の部分的な移植が含まれています。 Eigen::QR には、QR 分解の C++ 実装が含まれています。
![{\displaystyle R=\left[{\begin{smallmatrix}R_{1}\\0\end{smallmatrix}}\right]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/fb4d266be10a42e839c578471b30e32f0792b1b9)
![{\displaystyle \mathbf {x} =Q\left[{\begin{smallmatrix}\left(R_{1}^{\textsf {T}}\right)^{-1}\mathbf {b} \\0\end{smallmatrix}}\right]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/dae03449352d09b8f06843a44680f4e9353c2d8a)
