線性代數
A
=
[
1
2
3
4
]
{\displaystyle \mathbf {A} ={\begin{bmatrix}1&2\\3&4\end{bmatrix}}}
向量 · 向量空間 · 基底 · 行列式 · 矩陣
QR分解法 是一種將矩陣分解 的方式。這種方式,把矩陣 分解成一個正交矩陣 與一個上三角矩陣 的積。QR分解經常用來解線性最小平方法 問題。QR分解也是特定特徵值算法 即QR算法 的基礎。
任何方塊矩陣 A都可以分解為
A
=
Q
R
{\displaystyle A=QR}
其中Q 是正交矩陣 (意味着Q T Q = I )而R 是上三角矩陣 。如果A 是非奇異 的,且限定R 的對角線元素為正,則這個因數分解是唯一的。
更一般的說,我們可以因數分解複數
m
{\displaystyle m}
×
n
{\displaystyle n}
矩陣(有着m ≥ n )為
m
{\displaystyle m}
×
n
{\displaystyle n}
么正矩陣 (在Q ∗ Q = I 的意義上,不需要是方陣)和
n
{\displaystyle n}
×
n
{\displaystyle n}
上三角矩陣的乘積。對m<n的情況,在Q 是
m
{\displaystyle m}
×
m
{\displaystyle m}
方陣,而R則是
m
{\displaystyle m}
×
n
{\displaystyle n}
矩陣。
更一般地,我們可以將m ×n 的A 矩陣,其中m ≥ n ,分解成m ×m 么正矩陣 Q 和m ×n 三角矩陣R 的成積。由於m ×n 上三角矩陣的底部(m −n )行完全由零組成,因此對R 或R 和Q 進行分解通常很有用:
A
=
Q
R
=
Q
[
R
1
0
]
=
[
Q
1
Q
2
]
[
R
1
0
]
=
Q
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) call Q 1 R 1 the thin QR factorization of A ; Trefethen and Bau call this the reduced QR factorization .[ 1] If A is of full rank n and we require that the diagonal elements of R 1 are positive then R 1 and Q 1 are unique, but in general Q 2 is not. R 1 is then equal to the upper triangular factor of the Cholesky decomposition of A * A (= A T A if A is real).
類似的,我們可以定義A的QL,RQ和LQ分解。其中L是下三角矩陣。
QR分解的實際計算有很多方法,例如Givens旋轉 、Householder轉換 ,以及Gram-Schmidt正交化 等等。每一種方法都有其優點和不足。
Householder轉換 將一個向量關於某個平面 或者超平面 進行反射。我們可以利用這個操作對
m
×
n
(
m
≧
n
)
{\displaystyle m\times n(m\geqq n)}
的矩陣
A
{\displaystyle A}
進行QR分解。
矩陣
Q
{\displaystyle Q}
可以被用於對一個向量以一種特定的方式進行反射轉換,使得它除了一個維度以外的其他所有分量都化為0。
令
x
{\displaystyle \mathbf {x} }
為矩陣
A
{\displaystyle A}
的任一m 維實列向量,且有
‖
x
‖
=
|
α
|
{\displaystyle \|\mathbf {x} \|=|\alpha |}
(其中
α
{\displaystyle \alpha }
為純量)。若該算法是通過浮點數 實現的,則
α
{\displaystyle \alpha }
應當取和
x
{\displaystyle \mathbf {x} }
的第
k
{\displaystyle k}
維相反的符號(其中
x
k
{\displaystyle x_{k}}
是要保留不為0的項),這樣做可以避免精度缺失。對於複數的情況,令
α
=
−
e
i
arg
x
k
‖
x
‖
{\displaystyle \alpha =-\mathrm {e} ^{\mathrm {i} \arg x_{k}}\|\mathbf {x} \|}
(Stoer & Bulirsch 2002 ,p.225),並且在接下來矩陣
Q
{\displaystyle Q}
的構造中要將矩陣轉置替換為共軛轉置。
接下來,設
e
1
{\displaystyle \mathbf {e} _{1}}
為單位向量
(
1
,
0
,
⋯
,
0
)
T
{\displaystyle (1,0,\cdots ,0)^{T}}
,||·||為歐幾里德範數 ,
I
{\displaystyle I}
為
m
×
m
{\displaystyle m\times m}
單位矩陣,令
u
=
x
−
α
e
1
{\displaystyle \mathbf {u} =\mathbf {x} -\alpha \mathbf {e} _{1}}
,
v
=
u
‖
u
‖
{\displaystyle \mathbf {v} ={\mathbf {u} \over \|\mathbf {u} \|}}
,
Q
=
I
−
2
v
v
T
{\displaystyle Q=I-2\mathbf {v} \mathbf {v} ^{T}}
。
或者,若
A
{\displaystyle A}
為複矩陣,則
Q
=
I
−
(
1
+
w
)
v
v
H
{\displaystyle Q=I-(1+w)\mathbf {v} \mathbf {v} ^{H}}
,其中
w
=
x
H
v
/
v
H
x
{\displaystyle w=\mathbf {x} ^{H}\mathbf {v} \mathbf {/} \mathbf {v} ^{H}\mathbf {x} }
式中
x
H
{\displaystyle \mathbf {x} ^{H}}
是
x
{\displaystyle x}
的共軛轉置 (亦稱埃爾米特共軛 或埃爾米特轉置 )。
則
Q
{\displaystyle Q}
為一個
m
×
m
{\displaystyle m\times m}
的Householder矩陣,它滿足
Q
x
=
(
α
,
0
,
⋯
,
0
)
T
{\displaystyle Q\mathbf {x} =(\alpha ,0,\cdots ,0)^{T}\ }
利用Householder矩陣,可以將一個
m
×
n
{\displaystyle m\times n}
的矩陣
A
′
{\displaystyle A'}
轉換為上三角矩陣。
首先,我們將A左乘通過選取矩陣的第一列得到列向量
x
{\displaystyle x}
的Householder矩陣
Q
1
{\displaystyle Q_{1}}
。這樣,我們得到的矩陣
Q
1
A
{\displaystyle Q_{1}A}
的第一列將全部為0(第一行除外):
Q
1
A
=
[
α
1
⋆
…
⋆
0
⋮
A
′
0
]
{\displaystyle Q_{1}A={\begin{bmatrix}\alpha _{1}&\star &\dots &\star \\0&&&\\\vdots &&A'&\\0&&&\end{bmatrix}}}
這個過程對於矩陣
A
′
{\displaystyle A'}
(即
Q
1
A
{\displaystyle Q_{1}A}
排除第一行和第一列之後剩下的方陣)還可以繼續做下去,從而得到另一個Householder矩陣
Q
2
{\displaystyle Q_{2}}
。注意到
Q
2
{\displaystyle Q_{2}}
其實比
Q
1
{\displaystyle Q_{1}}
要小,因為它是在
Q
1
A
{\displaystyle Q_{1}A}
而非
A
{\displaystyle A}
的基礎上得到的。因此,我們需要在
Q
2
{\displaystyle Q_{2}}
的左上角補上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}
其中R為一個上三角矩陣。因此,令
Q
=
Q
1
T
Q
2
T
⋯
Q
t
T
,
{\displaystyle Q=Q_{1}^{T}Q_{2}^{T}\cdots Q_{t}^{T},}
則
A
=
Q
R
{\displaystyle A=QR}
為矩陣
A
{\displaystyle A}
的一個QR分解。
相比與Gram-Schmidt正交化,使用Householder轉換具有更好的數值穩定性 。
現在要用Householder轉換求解矩陣
A
{\displaystyle A}
的
Q
R
{\displaystyle QR}
分解。
A
=
[
0
3
1
0
4
−
2
2
1
1
]
{\displaystyle A={\begin{bmatrix}0&3&1\\0&4&-2\\2&1&1\\\end{bmatrix}}}
因為
α
1
=
[
0
,
0
,
2
]
T
{\displaystyle \alpha _{1}=[0,\ 0,\ 2]^{T}}
, 令
a
1
=
|
|
α
1
|
|
2
=
2
{\displaystyle a_{1}=||\alpha _{1}||_{2}=2}
,則
ω
1
=
α
1
−
a
1
e
1
|
|
α
1
−
a
1
e
1
|
|
2
=
1
2
[
−
1
,
0
,
1
]
T
{\displaystyle \omega _{1}={\frac {\alpha _{1}-a_{1}e_{1}}{||\alpha _{1}-a_{1}e_{1}||_{2}}}={\frac {1}{\sqrt {2}}}[-1,\ 0,\ 1]^{T}}
則有
H
1
=
I
−
2
ω
1
ω
1
H
=
[
0
0
1
0
1
0
1
0
0
]
{\displaystyle H_{1}=I-2\omega _{1}\omega _{1}^{H}={\begin{bmatrix}0&0&1\\0&1&0\\1&0&0\\\end{bmatrix}}}
從而,
H
1
A
=
[
2
1
1
0
4
−
2
0
3
1
]
{\displaystyle H_{1}A={\begin{bmatrix}2&1&1\\0&4&-2\\0&3&1\\\end{bmatrix}}}
記
β
=
[
4
,
3
]
T
{\displaystyle \beta =[4,\ 3]^{T}}
, 則
b
1
=
|
|
β
2
|
|
2
=
5
{\displaystyle b_{1}=||\beta _{2}||_{2}=5}
。令
ω
2
=
β
2
−
b
1
e
1
|
|
β
2
−
b
1
e
1
|
|
2
=
1
10
[
−
1
,
3
]
T
{\displaystyle \omega _{2}={\frac {\beta _{2}-b_{1}e_{1}}{||\beta _{2}-b_{1}e_{1}||_{2}}}={\frac {1}{\sqrt {10}}}[-1,\ 3]^{T}}
H
2
^
=
I
−
2
ω
2
ω
H
=
1
5
[
4
3
3
−
4
]
{\displaystyle {\hat {H_{2}}}=I-2\omega _{2}\omega ^{H}={\frac {1}{5}}{\begin{bmatrix}4&3\\3&-4\\\end{bmatrix}}}
記,
H
2
=
[
1
0
T
0
H
2
^
]
=
[
1
0
0
0
4
5
3
5
0
3
5
−
4
5
]
{\displaystyle H_{2}={\begin{bmatrix}1&0^{T}\\0&{\hat {H_{2}}}\\\end{bmatrix}}={\begin{bmatrix}1&0&0\\0&{\frac {4}{5}}&{\frac {3}{5}}\\0&{\frac {3}{5}}&-{\frac {4}{5}}\\\end{bmatrix}}}
則,
R
=
H
2
(
H
1
A
)
=
[
2
1
1
0
5
−
1
0
0
−
2
]
{\displaystyle R=H_{2}(H_{1}A)={\begin{bmatrix}2&1&1\\0&5&-1\\0&0&-2\\\end{bmatrix}}}
那麼
Q
=
H
1
H
2
=
1
5
[
0
3
−
4
0
4
3
5
0
0
]
{\displaystyle Q=H_{1}H_{2}={\frac {1}{5}}{\begin{bmatrix}0&3&-4\\0&4&3\\5&0&0\\\end{bmatrix}}}
吉文斯旋轉表示為如下形式的矩陣
G
(
i
,
j
,
θ
)
=
[
1
⋯
0
⋯
0
⋯
0
⋮
⋱
⋮
⋮
⋮
0
⋯
c
⋯
−
s
⋯
0
⋮
⋮
⋱
⋮
⋮
0
⋯
s
⋯
c
⋯
0
⋮
⋮
⋮
⋱
⋮
0
⋯
0
⋯
0
⋯
1
]
{\displaystyle G(i,j,\theta )={\begin{bmatrix}1&\cdots &0&\cdots &0&\cdots &0\\\vdots &\ddots &\vdots &&\vdots &&\vdots \\0&\cdots &c&\cdots &-s&\cdots &0\\\vdots &&\vdots &\ddots &\vdots &&\vdots \\0&\cdots &s&\cdots &c&\cdots &0\\\vdots &&\vdots &&\vdots &\ddots &\vdots \\0&\cdots &0&\cdots &0&\cdots &1\end{bmatrix}}}
這裏的 c = cos(θ ) 和 s = sin(θ ) 出現在第 i 行和第 j 行與第 i 列和第 j 列的交叉點上。就是說,吉文斯旋轉矩陣的所有非零元素定義如下::
g
k
k
=
1
for
k
≠
i
,
j
g
i
i
=
c
g
j
j
=
c
g
i
j
=
s
g
j
i
=
−
s
{\displaystyle {\begin{aligned}g_{k\,k}&{}=1\qquad {\text{for}}\ k\neq i,\,j\\g_{i\,i}&{}=c\\g_{j\,j}&{}=c\\g_{i\,j}&{}=s\\g_{j\,i}&{}=-s\end{aligned}}}
乘積 G (i , j , θ )x 表示向量 x 在 (i ,j )平面中的逆時針旋轉 θ 弧度。
對於一個向量
A
=
[
a
b
]
{\displaystyle {\begin{array}{lcl}A&=&{\begin{bmatrix}a\\b\\\end{bmatrix}}\\\end{array}}}
如果,
r
=
a
2
+
b
2
{\displaystyle r={\sqrt {a^{2}+b^{2}}}}
,
c
=
a
r
{\displaystyle c={\frac {a}{r}}}
,
s
=
−
b
r
{\displaystyle s=-{\frac {b}{r}}}
,
那麼,就存在旋轉矩陣G,使
A
{\displaystyle A}
底部轉成0。
A
2
_
S
u
b
=
[
c
−
s
s
c
]
[
a
b
]
=
[
r
0
]
{\displaystyle A_{2\_Sub}={\begin{bmatrix}c&-s\\s&c\\\end{bmatrix}}{\begin{bmatrix}a\\b\\\end{bmatrix}}={\begin{bmatrix}r\\0\\\end{bmatrix}}}
每一次的旋轉,吉文斯旋轉都可以將一個元素化成0,直到將原始矩陣轉成一個上三角矩陣,則完成分解。
A
=
Q
R
{\displaystyle A=QR}
Q
=
G
1
T
G
2
T
⋯
G
k
T
{\displaystyle Q=G_{1}^{T}G_{2}^{T}\cdots G_{k}^{T}}
A
1
=
[
6
5
0
5
1
4
0
4
3
]
{\displaystyle A_{1}={\begin{bmatrix}6&5&0\\5&1&4\\0&4&3\\\end{bmatrix}}}
r
=
6
2
+
5
2
≈
7.8102
{\displaystyle r={\sqrt {6^{2}+5^{2}}}\approx 7.8102}
c
=
6
/
r
≈
0.7682
{\displaystyle c=6/r\approx 0.7682}
s
=
−
5
/
r
≈
−
0.6402
{\displaystyle s=-5/r\approx -0.6402}
A
2
=
G
1
A
1
=
[
c
−
s
0
s
c
0
0
0
1
]
[
6
5
0
5
1
4
0
4
3
]
≈
[
7.8102
4.4813
2.5607
0
−
2.4327
3.0729
0
4
3
]
{\displaystyle A_{2}=G_{1}A_{1}={\begin{bmatrix}c&-s&0\\s&c&0\\0&0&1\\\end{bmatrix}}{\begin{bmatrix}6&5&0\\5&1&4\\0&4&3\\\end{bmatrix}}\approx {\begin{bmatrix}7.8102&4.4813&2.5607\\0&-2.4327&3.0729\\0&4&3\\\end{bmatrix}}}
對於:
A
2
{\displaystyle A_{2}}
子矩陣 :
A
2
_
S
u
b
{\displaystyle A_{2\_Sub}}
A
2
_
S
u
b
=
[
−
2.4327
3.0729
4
3
]
{\displaystyle A_{2\_Sub}={\begin{bmatrix}-2.4327&3.0729\\4&3\\\end{bmatrix}}}
r
=
(
−
2.4327
)
2
+
4
2
≈
4.6817
{\displaystyle r={\sqrt {(-2.4327)^{2}+4^{2}}}\approx 4.6817}
c
=
−
2.4327
/
r
≈
−
0.5196
{\displaystyle c=-2.4327/r\approx -0.5196}
s
=
−
5
/
r
≈
−
0.8544
{\displaystyle s=-5/r\approx -0.8544}
G
2
A
2
=
[
1
0
0
0
c
−
s
0
s
c
]
[
7.8102
4.4813
2.5607
0
−
2.4327
3.0729
0
4
3
]
≈
[
7.8102
4.4813
2.5607
0
4.6817
0.9664
0
0
−
4.1843
]
{\displaystyle G_{2}A_{2}={\begin{bmatrix}1&0&0\\0&c&-s\\0&s&c\\\end{bmatrix}}{\begin{bmatrix}7.8102&4.4813&2.5607\\0&-2.4327&3.0729\\0&4&3\\\end{bmatrix}}\approx {\begin{bmatrix}7.8102&4.4813&2.5607\\0&4.6817&0.9664\\0&0&-4.1843\\\end{bmatrix}}}
R
=
G
2
A
2
=
G
2
G
1
A
1
{\displaystyle R=G_{2}A_{2}=G_{2}G_{1}A_{1}}
Q
=
G
1
T
G
2
T
=
[
0.7682
0.3327
0.5470
0.6402
−
0.3992
−
0.6564
0
0.8544
−
0.5196
]
{\displaystyle Q=G_{1}^{T}G_{2}^{T}={\begin{bmatrix}0.7682&0.3327&0.5470\\0.6402&-0.3992&-0.6564\\0&0.8544&-0.5196\\\end{bmatrix}}}
圖1
v
{\displaystyle {\boldsymbol {v}}}
在
V
2
{\displaystyle {\boldsymbol {V}}^{2}}
上投影,構造
V
3
{\displaystyle {\boldsymbol {V}}^{3}}
上的正交基
β
{\displaystyle {\boldsymbol {\beta }}}
格拉姆-施密特正交化的基本想法,是利用投影原理 在已有正交基的基礎上構造一個新的正交基。
設
v
∈
V
n
{\displaystyle {\boldsymbol {v}}\in {\boldsymbol {V^{n}}}}
。
V
k
{\displaystyle {\boldsymbol {V}}^{k}}
是
V
n
{\displaystyle {\boldsymbol {V}}^{n}}
上的
k
{\displaystyle k}
維子空間,其標準正交基為
{
η
1
,
…
,
η
k
}
{\displaystyle \{{\boldsymbol {\eta }}_{1},\ldots ,{\boldsymbol {\eta }}_{k}\}}
,且
v
{\displaystyle {\boldsymbol {v}}}
不在
V
k
{\displaystyle {\boldsymbol {V}}^{k}}
上。由投影原理知,
v
{\displaystyle {\boldsymbol {v}}}
與其在
V
k
{\displaystyle {\boldsymbol {V}}^{k}}
上的投影
p
r
o
j
V
k
v
{\displaystyle \mathrm {proj} _{\boldsymbol {V^{k}}}{\boldsymbol {v}}}
之差
β
=
v
−
∑
i
=
1
k
p
r
o
j
η
i
v
=
v
−
∑
i
=
1
k
⟨
v
,
η
i
⟩
η
i
{\displaystyle {\boldsymbol {\beta }}={\boldsymbol {v}}-\sum _{i=1}^{k}\mathrm {proj} _{{\boldsymbol {\eta }}_{i}}\,{\boldsymbol {v}}={\boldsymbol {v}}-\sum _{i=1}^{k}\langle {\boldsymbol {v}},{\boldsymbol {\eta }}_{i}\rangle {\boldsymbol {\eta }}_{i}}
是正交於子空間
V
k
{\displaystyle {\boldsymbol {V}}^{k}}
的,亦即
β
{\displaystyle {\boldsymbol {\beta }}}
正交於
V
k
{\displaystyle {\boldsymbol {V}}^{k}}
的正交基
η
i
{\displaystyle {\boldsymbol {\eta }}_{i}}
。因此只要將
β
{\displaystyle {\boldsymbol {\beta }}}
單位化,即
η
k
+
1
=
β
‖
β
‖
=
β
⟨
β
,
β
⟩
{\displaystyle {\boldsymbol {\eta }}_{k+1}={\frac {\boldsymbol {\beta }}{\|{\boldsymbol {\beta }}\|}}={\frac {\boldsymbol {\beta }}{\sqrt {\langle {\boldsymbol {\beta }},{\boldsymbol {\beta }}\rangle }}}}
那麼
{
η
1
,
…
,
η
k
,
η
k
+
1
}
{\displaystyle \{{\boldsymbol {\eta }}_{1},\ldots ,{\boldsymbol {\eta }}_{k},{\boldsymbol {\eta }}_{k+1}\}}
就是
V
k
{\displaystyle {\boldsymbol {V}}^{k}}
在
v
{\displaystyle {\boldsymbol {v}}}
上擴展的子空間
s
p
a
n
{
v
,
η
1
,
.
.
.
,
η
k
}
{\displaystyle \mathrm {span} \{{\boldsymbol {v}},{\boldsymbol {\eta }}_{1},...,{\boldsymbol {\eta }}_{k}\}}
的標準正交基。
根據上述分析,對於向量組
{
v
1
,
…
,
v
m
}
{\displaystyle \{{\boldsymbol {v}}_{1},\ldots ,{\boldsymbol {v}}_{m}\}}
張成的空間
V
m
{\displaystyle {\boldsymbol {V}}^{m}}
(
m
<
n
{\displaystyle m<n}
),只要從其中一個向量(不妨設為
v
1
{\displaystyle {\boldsymbol {v}}_{1}}
)所張成的一維子空間
s
p
a
n
{
v
1
}
{\displaystyle \mathrm {span} \{{\boldsymbol {v}}_{1}\}}
開始(注意到
v
1
{\displaystyle {\boldsymbol {v}}_{1}}
就是
s
p
a
n
{
v
1
}
{\displaystyle \mathrm {span} \{{\boldsymbol {v}}_{1}\}}
的正交基),重複上述擴展構造正交基的過程,就能夠得到
V
n
{\displaystyle {\boldsymbol {V}}^{n}}
的一組正交基。這就是格拉姆-施密特正交化 。
首先需要確定已有基底向量的順序,不妨設為
{
v
1
,
…
,
v
n
}
{\displaystyle \{{\boldsymbol {v}}_{1},\ldots ,{\boldsymbol {v}}_{n}\}}
。Gram-Schmidt正交化的過程如下:
β
1
=
v
1
,
{\displaystyle {\boldsymbol {\beta }}_{1}={\boldsymbol {v}}_{1},}
η
1
=
β
1
‖
β
1
‖
{\displaystyle {\boldsymbol {\eta }}_{1}={{\boldsymbol {\beta }}_{1} \over \|{\boldsymbol {\beta }}_{1}\|}}
β
2
=
v
2
−
⟨
v
2
,
η
1
⟩
η
1
,
{\displaystyle {\boldsymbol {\beta }}_{2}={\boldsymbol {v}}_{2}-\langle {\boldsymbol {v}}_{2},{\boldsymbol {\eta }}_{1}\rangle {\boldsymbol {\eta }}_{1},}
η
2
=
β
2
‖
β
2
‖
{\displaystyle {\boldsymbol {\eta }}_{2}={{\boldsymbol {\beta }}_{2} \over \|{\boldsymbol {\beta }}_{2}\|}}
β
3
=
v
3
−
⟨
v
3
,
η
1
⟩
η
1
−
⟨
v
3
,
η
2
⟩
η
2
,
{\displaystyle {\boldsymbol {\beta }}_{3}={\boldsymbol {v}}_{3}-\langle {\boldsymbol {v}}_{3},{\boldsymbol {\eta }}_{1}\rangle {\boldsymbol {\eta }}_{1}-\langle {\boldsymbol {v}}_{3},{\boldsymbol {\eta }}_{2}\rangle {\boldsymbol {\eta }}_{2},}
η
3
=
β
3
‖
β
3
‖
{\displaystyle {\boldsymbol {\eta }}_{3}={{\boldsymbol {\beta }}_{3} \over \|{\boldsymbol {\beta }}_{3}\|}}
⋮
{\displaystyle \vdots }
⋮
{\displaystyle \vdots }
β
n
=
v
n
−
∑
i
=
1
n
−
1
⟨
v
n
,
η
i
⟩
η
i
,
{\displaystyle {\boldsymbol {\beta }}_{n}={\boldsymbol {v}}_{n}-\sum _{i=1}^{n-1}\langle {\boldsymbol {v}}_{n},{\boldsymbol {\eta }}_{i}\rangle {\boldsymbol {\eta }}_{i},}
η
n
=
β
n
‖
β
n
‖
{\displaystyle {\boldsymbol {\eta }}_{n}={{\boldsymbol {\beta }}_{n} \over \|{\boldsymbol {\beta }}_{n}\|}}
這樣就得到
s
p
a
n
{
v
1
,
…
,
v
n
}
{\displaystyle \mathrm {span} \{{\boldsymbol {v}}_{1},\ldots ,{\boldsymbol {v}}_{n}\}}
上的一組正交基
{
β
1
,
…
,
β
n
}
{\displaystyle \{{\boldsymbol {\beta }}_{1},\ldots ,{\boldsymbol {\beta }}_{n}\}}
,以及相應的標準正交基
{
η
1
,
…
,
η
n
}
{\displaystyle \{{\boldsymbol {\eta }}_{1},\ldots ,{\boldsymbol {\eta }}_{n}\}}
。
現在要用格拉姆-施密特轉換求解矩陣
A
{\displaystyle A}
的
Q
R
{\displaystyle QR}
分解。
A
=
[
1
2
4
0
0
5
0
3
6
]
{\displaystyle A={\begin{bmatrix}1&2&4\\0&0&5\\0&3&6\\\end{bmatrix}}}
令,
a
=
[
1
,
0
,
0
]
{\displaystyle a=[1,0,0]}
q
1
=
a
|
|
a
|
|
=
[
1
0
0
]
{\displaystyle q_{1}={\frac {a}{||a||}}={\begin{bmatrix}1\\0\\0\\\end{bmatrix}}}
q
2
^
=
b
−
(
b
∗
q
1
)
q
1
=
[
2
0
3
]
−
2
[
1
0
0
]
=
[
0
0
3
]
{\displaystyle {\hat {q_{2}}}=b-(b*q_{1})q_{1}={\begin{bmatrix}2\\0\\3\\\end{bmatrix}}-2{\begin{bmatrix}1\\0\\0\\\end{bmatrix}}={\begin{bmatrix}0\\0\\3\\\end{bmatrix}}}
q
2
=
q
2
^
|
|
q
2
^
|
|
=
[
0
0
1
]
{\displaystyle q_{2}={\frac {\hat {q_{2}}}{||{\hat {q_{2}}}||}}={\begin{bmatrix}0\\0\\1\\\end{bmatrix}}}
q
3
^
=
c
−
(
c
∗
q
1
)
q
1
−
(
c
∗
q
2
)
q
2
=
[
4
5
6
]
−
4
[
1
0
0
]
−
6
[
0
0
1
]
=
[
0
5
0
]
{\displaystyle {\hat {q_{3}}}=c-(c*q_{1})q_{1}-(c*q_{2})q_{2}={\begin{bmatrix}4\\5\\6\\\end{bmatrix}}-4{\begin{bmatrix}1\\0\\0\\\end{bmatrix}}-6{\begin{bmatrix}0\\0\\1\\\end{bmatrix}}={\begin{bmatrix}0\\5\\0\\\end{bmatrix}}}
q
3
=
q
3
^
|
|
q
3
^
|
|
=
[
0
1
0
]
{\displaystyle q_{3}={\frac {\hat {q_{3}}}{||{\hat {q_{3}}}||}}={\begin{bmatrix}0\\1\\0\\\end{bmatrix}}}
那麼可知,
Q
=
[
1
0
0
0
0
1
0
1
0
]
{\displaystyle Q={\begin{bmatrix}1&0&0\\0&0&1\\0&1&0\\\end{bmatrix}}}
由
A
=
Q
R
{\displaystyle A=QR}
,可知,
R
=
[
1
2
4
0
3
6
0
0
5
]
{\displaystyle R={\begin{bmatrix}1&2&4\\0&3&6\\0&0&5\\\end{bmatrix}}}
MATLAB以qr函數來執行QR分解法,其語法為
[
Q
,
R
]
=
q
r
(
A
)
{\displaystyle [Q,R]=qr(A)}
其中Q代表正規正交矩陣,
而R代表上三角形矩陣。
此外,原矩陣A不必為正方矩陣;
如果矩陣A大小為
m
×
n
{\displaystyle m\times n}
,則矩陣Q大小為
m
×
m
{\displaystyle m\times m}
,矩陣R大小為
m
×
n
{\displaystyle m\times n}
。
對於直接求解線性方程組的逆,用QR分解的方法求解會更具有數據的穩定性。
對於求解一個線性系統
A
x
=
b
{\displaystyle Ax=b}
, 這裏
A
{\displaystyle A}
的維度是
m
×
n
{\displaystyle m\times n}
。
如果
m
≤
n
{\displaystyle m\leq n}
, 那麼
A
T
=
Q
R
{\displaystyle A^{T}=QR}
,這裏
Q
T
=
Q
−
1
{\displaystyle Q^{T}=Q^{-1}}
)。
R
{\displaystyle R}
的形式是
R
=
[
R
1
0
]
{\displaystyle R={\begin{bmatrix}R_{1}\\0\end{bmatrix}}}
,
R
1
{\displaystyle R_{1}}
是
R
{\displaystyle R}
上不為0的部分。
那麼對於
x
=
Q
[
(
R
1
T
)
−
1
b
0
]
{\displaystyle x=Q{\begin{bmatrix}\left(R_{1}^{\textsf {T}}\right)^{-1}b\\0\end{bmatrix}}}
如果
m
>
n
{\displaystyle m>n}
, 那麼
A
=
Q
R
{\displaystyle A=QR}
,這裏
Q
T
=
Q
−
1
{\displaystyle Q^{T}=Q^{-1}}
)。本質是最小化
|
|
A
x
^
−
b
|
|
{\displaystyle ||A{\hat {x}}-b||}
x
^
=
R
1
−
1
(
Q
1
T
b
)
{\displaystyle {\hat {x}}=R_{1}^{-1}\left(Q_{1}^{\textsf {T}}b\right)}