QR-розклад матриці — представлення матриці у вигляді добутку унітарної та правої трикутної матриці .
Матриця A розміру m×n може бути представлена у вигляді
A
=
Q
R
,
{\displaystyle \ A=QR,}
де Q — унітарна матриця розміру m×m, R — верхня трикутна матриця розміру m×n.
Також можливі представлення QL, RQ, та LQ (де L — нижня трикутна матриця).
Для m ×n матриці A , з m ≥ n нижні (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 обидві мають ортогональні стовпчики.
Розклад матриці може отримуватись за допомогою різних методів:
Розглянемо процес Грама — Шмідта застосований до стовпчиків матриці
A
=
[
a
1
,
⋯
,
a
n
]
{\displaystyle A=[\mathbf {a} _{1},\cdots ,\mathbf {a} _{n}]}
⟨
v
,
w
⟩
=
v
⊤
w
{\displaystyle \langle \mathbf {v} ,\mathbf {w} \rangle =\mathbf {v} ^{\top }\mathbf {w} }
⟨
v
,
w
⟩
=
v
∗
w
{\displaystyle \langle \mathbf {v} ,\mathbf {w} \rangle =\mathbf {v} ^{*}\mathbf {w} }
Визначимо проєкцію вектора як:
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
1
=
a
1
,
e
1
=
u
1
‖
u
1
‖
u
2
=
a
2
−
p
r
o
j
u
1
a
2
,
e
2
=
u
2
‖
u
2
‖
u
3
=
a
3
−
p
r
o
j
u
1
a
3
−
p
r
o
j
u
2
a
3
,
e
3
=
u
3
‖
u
3
‖
⋮
⋮
u
k
=
a
k
−
∑
j
=
1
k
−
1
p
r
o
j
u
j
a
k
,
e
k
=
u
k
‖
u
k
‖
{\displaystyle {\begin{aligned}\mathbf {u} _{1}&=\mathbf {a} _{1},&\mathbf {e} _{1}&={\mathbf {u} _{1} \over \|\mathbf {u} _{1}\|}\\\mathbf {u} _{2}&=\mathbf {a} _{2}-\mathrm {proj} _{\mathbf {u} _{1}}\,\mathbf {a} _{2},&\mathbf {e} _{2}&={\mathbf {u} _{2} \over \|\mathbf {u} _{2}\|}\\\mathbf {u} _{3}&=\mathbf {a} _{3}-\mathrm {proj} _{\mathbf {u} _{1}}\,\mathbf {a} _{3}-\mathrm {proj} _{\mathbf {u} _{2}}\,\mathbf {a} _{3},&\mathbf {e} _{3}&={\mathbf {u} _{3} \over \|\mathbf {u} _{3}\|}\\&\vdots &&\vdots \\\mathbf {u} _{k}&=\mathbf {a} _{k}-\sum _{j=1}^{k-1}\mathrm {proj} _{\mathbf {u} _{j}}\,\mathbf {a} _{k},&\mathbf {e} _{k}&={\mathbf {u} _{k} \over \|\mathbf {u} _{k}\|}\end{aligned}}}
Тепер ми можемо виразити
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}&=\langle \mathbf {e} _{1},\mathbf {a} _{1}\rangle \mathbf {e} _{1}\\\mathbf {a} _{2}&=\langle \mathbf {e} _{1},\mathbf {a} _{2}\rangle \mathbf {e} _{1}+\langle \mathbf {e} _{2},\mathbf {a} _{2}\rangle \mathbf {e} _{2}\\\mathbf {a} _{3}&=\langle \mathbf {e} _{1},\mathbf {a} _{3}\rangle \mathbf {e} _{1}+\langle \mathbf {e} _{2},\mathbf {a} _{3}\rangle \mathbf {e} _{2}+\langle \mathbf {e} _{3},\mathbf {a} _{3}\rangle \mathbf {e} _{3}\\&\vdots \\\mathbf {a} _{k}&=\sum _{j=1}^{k}\langle \mathbf {e} _{j},\mathbf {a} _{k}\rangle \mathbf {e} _{j}\end{aligned}}}
де
⟨
e
i
,
a
i
⟩
=
‖
u
i
‖
{\displaystyle \langle \mathbf {e} _{i},\mathbf {a} _{i}\rangle =\|\mathbf {u} _{i}\|}
A
=
Q
R
{\displaystyle A=QR}
де:
Q
=
[
e
1
,
⋯
,
e
n
]
and
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 Q=\left[\mathbf {e} _{1},\cdots ,\mathbf {e} _{n}\right]\qquad {\text{and}}\qquad 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
=
(
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 {\begin{matrix}Q^{T}\,Q=I.\end{matrix}}}
Тоді, ми можемо обчислити
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}\mathbf {u} _{1}&\mathbf {u} _{2}&\mathbf {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
‖
)
=
(
6
/
7
−
69
/
175
−
58
/
175
3
/
7
158
/
175
6
/
175
−
2
/
7
6
/
35
−
33
/
35
)
.
{\displaystyle Q={\begin{pmatrix}{\frac {\mathbf {u} _{1}}{\|\mathbf {u} _{1}\|}}&{\frac {\mathbf {u} _{2}}{\|\mathbf {u} _{2}\|}}&{\frac {\mathbf {u} _{3}}{\|\mathbf {u} _{3}\|}}\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 {\begin{matrix}Q^{T}A=Q^{T}Q\,R=R;\end{matrix}}}
R
=
Q
T
A
=
(
14
21
−
14
0
175
−
70
0
0
35
)
.
{\displaystyle {\begin{matrix}R=Q^{T}A=\end{matrix}}{\begin{pmatrix}14&21&-14\\0&175&-70\\0&0&35\end{pmatrix}}.}
Відбиття Хаусхалдера для QR-розкладу: Ціллю є знаходження лінійного перетворення, що переводить вектор
x
{\displaystyle x}
e
1
{\displaystyle e_{1}}
x
{\displaystyle x}
e
1
{\displaystyle e_{1}}
x
{\displaystyle x}
e
1
{\displaystyle e_{1}}
Перетворення Хаусхолдера — це трансформація, яка приймає вектор і відбиває його від певної площини або гіперплощини. Ми можемо використати цю операцію для обчислення QR -розкладу m -на-n матриці
A
{\displaystyle A}
m ≥ n .
Q можна використати, щоб відбивати вектор таким чином, щоб всі координати окрім однієї зникали.
Нехай
x
{\displaystyle \mathbf {x} }
m -вимірним вектором стовпчиком
A
{\displaystyle A}
‖
x
‖
=
|
α
|
{\displaystyle \|\mathbf {x} \|=|\alpha |}
α . Якщо алгоритм втілюється із використанням арифметики з рухомою комою , тоді потрібно надати α знак протилежний до знаку k -ї координати
x
{\displaystyle \mathbf {x} }
x
k
{\displaystyle x_{k}}
A , задля уникнення втрати розрядів. У комплексному випадку, встановіть
α
=
−
e
i
arg
x
k
‖
x
‖
{\displaystyle \alpha =-\mathrm {e} ^{\mathrm {i} \arg x_{k}}\|\mathbf {x} \|}
і замініть транспонування на спряжене транспонування під час побудови Q далі.
Тоді,
e
1
{\displaystyle \mathbf {e} _{1}}
T , ||·|| є Евклідовою нормою і
I
{\displaystyle I}
m -by-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 \mathbf {x} }
Q
{\displaystyle Q}
m -на-m матриця Хаусхолдера і
Q
x
=
(
α
,
0
,
⋯
,
0
)
T
.
{\displaystyle Q\mathbf {x} =(\alpha ,0,\cdots ,0)^{T}.\,}
Це можна використати, щоб поступово трансформувати m -на-n матрицю A у верхню трикутну форму. Спершу ми множимо A на матрицю Хаусхолдера Q 1 яку ми отримали для першого стовпчика. Це нам дає матрицю Q 1 A з нулями в першому стовпчику окрім першого рядка.
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 ′ (Q 1 A без першого рядка і першого стовпчика), в результаті маємо матрицю Хаусхолдера Q ′2 . Зауважте, що Q ′2 менше ніж Q 1 . Оскільки ми бажаємо, щоб вона діяла на Q 1 A , а не на A ′ нам потрібно розширити її додавши у верхній лівий кут 1, узагальнюючи:
Q
k
=
(
I
k
−
1
0
0
Q
k
′
)
.
{\displaystyle Q_{k}={\begin{pmatrix}I_{k-1}&0\\0&Q_{k}'\end{pmatrix}}.}
Після
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
=
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}
Цей метод має більшу числову стійкість ніж метод Грама-Шмідта.
Наступна таблиця наводить кількість операцій на k -му кроці QR-розкладення із використанням перетворення Хаусхолдера, припускаючи квадратну матрицю розміру n .
Операція
Кількість на k -му кроці
множення
2
(
n
−
k
+
1
)
2
{\displaystyle 2(n-k+1)^{2}}
додавання
(
n
−
k
+
1
)
2
+
(
n
−
k
+
1
)
(
n
−
k
)
+
2
{\displaystyle (n-k+1)^{2}+(n-k+1)(n-k)+2}
ділення
1
{\displaystyle 1}
взяття кореня
1
{\displaystyle 1}
Додаючи ці числа для усіх 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(n^{3}).}
Обчислимо розклад для
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 , вектор
a
1
=
(
12
,
6
,
−
4
)
T
{\displaystyle \mathbf {a} _{1}=(12,6,-4)^{T}}
‖
a
1
‖
e
1
=
(
14
,
0
,
0
)
T
.
{\displaystyle \|\mathbf {a} _{1}\|\;\mathrm {e} _{1}=(14,0,0)^{T}.}
Тепер,
u
=
x
+
α
e
1
,
{\displaystyle \mathbf {u} =\mathbf {x} +\alpha \mathbf {e} _{1},}
і
v
=
u
‖
u
‖
.
{\displaystyle \mathbf {v} ={\mathbf {u} \over \|\mathbf {u} \|}.}
Тут,
α
=
−
14
{\displaystyle \alpha =-14}
x
=
a
1
=
(
12
,
6
,
−
4
)
T
{\displaystyle \mathbf {x} =\mathbf {a} _{1}=(12,6,-4)^{T}}
Отже
u
=
(
−
2
,
6
,
−
4
)
T
=
(
2
)
(
−
1
,
3
,
−
2
)
T
{\displaystyle \mathbf {u} =(-2,6,-4)^{T}=({2})(-1,3,-2)^{T}}
v
=
1
14
(
−
1
,
3
,
−
2
)
T
{\displaystyle \mathbf {v} ={1 \over {\sqrt {14}}}(-1,3,-2)^{T}}
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, 2).
Візьмемо мінор (1, 1) і знову застосуємо процес до
A
′
=
M
11
=
(
−
49
−
14
168
−
77
)
.
{\displaystyle A'=M_{11}={\begin{pmatrix}-49&-14\\168&-77\end{pmatrix}}.}
Таким саме методом як і вище, отримуємо матрицю перетворення Хаусхолдера
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
=
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 є ортогональною і R є верхньою трикутною, отже A = QR і є шуканим QR-розкладом.
![{\displaystyle A=[\mathbf {a} _{1},\cdots ,\mathbf {a} _{n}]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6824116d015e9599acde43bcfe0bfc286f331c92)
![{\displaystyle Q=\left[\mathbf {e} _{1},\cdots ,\mathbf {e} _{n}\right]\qquad {\text{and}}\qquad 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/f6c03b414c06cbc293519a41cfcab0ca4084171c)
