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}}
). Найбільший можливий кут у такій трансформації становить 45 градусів.
Перетворення Хаусхолдера — це трансформація, яка приймає вектор і відбиває його від певної площини або гіперплощини. Ми можемо використати цю операцію для обчислення 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}}
є вектором (1,0,...,0)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}
є 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}
and
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}}
and
v
=
1
14
(
− − -->
1
,
3
,
− − -->
2
)
T
{\displaystyle \mathbf {v} ={1 \over {\sqrt {14}}}(-1,3,-2)^{T}}
, and then
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-розкладом.
Див. також
Джерела