QR-розклад матриці

Матеріал з Вікіпедії — вільної енциклопедії.
(Перенаправлено з QR розклад матриці)
Перейти до: навігація, пошук

QR-розклад матриці — представлення матриці у вигляді добутку унітарної та правої трикутної матриці.

Матриця A розміру m×n може бути представлена у вигляді

\ A = QR,

де Q — унітарна матриця розміру m×m, R — верхня трикутна матриця розміру m×n.

Також можливі представлення QL, RQ, та LQ (де L — нижня трикутна матриця).

Для m×n матриці A, з m ≥ n нижні (mn) рядків m×n верхньої трикутної матриці усі нульові, тому часто буває корисно розбити R, або R і Q:


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,

де R1 — це n×n верхня трикутна матриця, 0 — це (m − nn нульова матриця, Q1 — це m×n, Q2 — це m×(m − n) і Q1 та Q2 обидві мають ортогональні стовпчики.

Обчислення[ред.ред. код]

Розклад матриці може отримуватись за допомогою різних методів:

Використовуючи процес Грама — Шмідта[ред.ред. код]

Розглянемо процес Грама — Шмідта застосований до стовпчиків матриці A=[\mathbf{a}_1, \cdots, \mathbf{a}_n] з повним стовпчиковим рангом, де \langle\mathbf{v},\mathbf{w}\rangle = \mathbf{v}^\top \mathbf{w} (або \langle\mathbf{v},\mathbf{w}\rangle = \mathbf{v}^* \mathbf{w} у комплексному випадку).

Визначимо проекцію вектора як:

\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}

тоді:


\begin{align}
 \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{align}

Тепер ми можемо виразити \mathbf{a}_i через ново обчислений ортонормальний базис:


\begin{align}
 \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{align}

де \langle\mathbf{e}_i,\mathbf{a}_i \rangle = \|\mathbf{u}_i\|. Це можна записати у матричній формі:

 A = Q R

де:

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 = 
\begin{pmatrix}
12 & -51 & 4 \\
6 & 167 & -68 \\
-4 & 24 & -41
\end{pmatrix}
.

Згадаймо, що ортонормальна матриця Q має таку властивість


\begin{matrix}
 Q^T \,Q = I.
\end{matrix}

Тоді, ми можемо обчислити Q із застосувавши процес Грама — Шмідта так:


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 = 
\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}.

Отже, ми маємо


\begin{matrix}
 Q^{T} A = Q^{T}Q\,R = R;
\end{matrix}

\begin{matrix}
 R = Q^{T}A =
\end{matrix}
\begin{pmatrix}
    14  &  21          &            -14 \\
     0  & 175          &           -70 \\
     0  &   0          &          35
\end{pmatrix}.

Використовуючи перетворення Хаусхолдера[ред.ред. код]

Відбиття Хаусхалдера для QR-розкладу: Ціллю є знаходження лінійного перетворення, що переводить вектор x у вектор такої ж довжини колінеарний з e_1. Ми могли б використати ортогональну проекцію (Грам-Шмідт), але це було б чисельно нестабільно якщо вектори x і e_1 майже ортогональні. Натомість, відбиття Хаусхолдера віддзеркалює щодо пунктирної лінії (обраної так, щоб розсікати навпіл кут між x і e_1). Найбільший можливий кут у такій трансформації становить 45 градусів.

Перетворення Хаусхолдера — це трансформація, яка приймає вектор і відбиває його від певної площини або гіперплощини. Ми можемо використати цю операцію для обчислення QR-розкладу m-на-n матриці A з m ≥ n.

Q можна використати, щоб відбивати вектор таким чином, щоб всі координати окрім однієї зникали.

Нехай \mathbf{x} буде довільним дійсним m-вимірним вектором стовпчиком A таким, що \|\mathbf{x}\| = |\alpha| для скаляра α. Якщо алгоритм втілюється із використанням арифметики з рухомою комою, тоді потрібно надати α знак протилежний до знаку k-ї координати \mathbf{x}, де x_k є опорною координатою після якої усі елементи дорівнюють нулю в кінцевій верхній трикутній формі матриці A, задля уникнення втрати розрядів. У комплексному випадку, встановіть

 \alpha = - \mathrm{e}^{\mathrm{i} \arg x_k} \|\mathbf{x}\|

і замініть транспонування на спряжене транспонування під час побудови Q далі.

Тоді, \mathbf{e}_1 є вектором (1,0,...,0)T, ||·|| є Евклідовою нормою і I є m-by-m одиничною матрицею, встановимо

\mathbf{u} = \mathbf{x} - \alpha\mathbf{e}_1,
\mathbf{v} = {\mathbf{u}\over\|\mathbf{u}\|},
Q = I - 2 \mathbf{v}\mathbf{v}^T.

Або, якщо A комплексна

Q = I - (1+w)\mathbf{v}\mathbf{v}^H, де w = \mathbf{x}^H\mathbf{v}\mathbf{/}\mathbf{v}^H\mathbf{x}
де \mathbf{x}^H — це ермітово-спряжений \mathbf{x}

Q є m-на-m матриця Хаусхолдера і

Q\mathbf{x} = (\alpha, 0, \cdots, 0)^T.\,

Це можна використати, щоб поступово трансформувати m-на-n матрицю A у верхню трикутну форму. Спершу ми множимо A на матрицю Хаусхолдера Q1 яку ми отримали для першого стовпчика. Це нам дає матрицю Q1A з нулями в першому стовпчику окрім першого рядка.

Q_1A = \begin{bmatrix}
                   \alpha_1&\star&\dots&\star\\
                      0    &     &    &    \\
                   \vdots  &     &  A' &    \\
                      0    &     &     & \end{bmatrix}

Це можна повторити для A′ (Q1A без першого рядка і першого стовпчика), в результаті маємо матрицю Хаусхолдера Q2. Зауважте, що Q2 менше ніж Q1. Оскільки ми бажаємо, щоб вона діяла на Q1A, а не на A′ нам потрібно розширити її додавши у верхній лівий кут 1, узагальнюючи:

Q_k = \begin{pmatrix}
                  I_{k-1} & 0\\
                   0  & Q_k'\end{pmatrix}.

Після t ітерацій цього процесу, t = \min(m-1, n),

 R = Q_t \cdots Q_2Q_1A

є верхньою трикутною матрицею. Отже, з

 Q = Q_1^T Q_2^T \cdots Q_t^T,

A = QR є QR-розкладом A.

Цей метод має більшу числову стійкість ніж метод Грама-Шмідта.

Наступна таблиця наводить кількість операцій на k-му кроці QR-розкладення із використанням перетворення Хаусхолдера, припускаючи квадратну матрицю розміру n.

Операція Кількість на k-му кроці
множення 2(n-k+1)^2
додавання  (n-k+1)^2+(n-k+1)(n-k)+2
ділення 1
взяття кореня 1

Додаючи ці числа для усіх n − 1 кроків (для квадратної матриці розміру n), складність алгоритму (кількість множень з рухомою комою) задається

\frac{2}{3}n^3+n^2+\frac{1}{3}n-2=O(n^3).

Приклад[ред.ред. код]

Обчислимо розклад для

A = \begin{pmatrix}
12 & -51 & 4 \\
6 & 167 & -68 \\
-4 & 24 & -41 \end{pmatrix}.

Перше, нам потрібно знайти відбиття, що перетворює перший стовпчик матриці A, вектор \mathbf{a}_1 = (12, 6, -4)^T, у \|\mathbf{a}_1\| \;\mathrm{e}_1 = (14, 0, 0)^T.

Тепер,

\mathbf{u} = \mathbf{x} + \alpha\mathbf{e}_1,

і

\mathbf{v} = {\mathbf{u}\over\|\mathbf{u}\|}.

Тут,

\alpha = -14 and \mathbf{x} = \mathbf{a}_1 = (12, 6, -4)^T

Отже

\mathbf{u} = (-2, 6, -4)^T=({2})(-1, 3, -2)^T and \mathbf{v} = {1 \over \sqrt{14}}(-1, 3, -2)^T, and then
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 \over 7}\begin{pmatrix}
1 & -3  & 2 \\
-3 & 9 & -6 \\
2  & -6  & 4
\end{pmatrix}
 = \begin{pmatrix}
6/7 & 3/7   &  -2/7 \\
3/7  &-2/7  &  6/7 \\
-2/7 & 6/7  &   3/7 \\
\end{pmatrix}.

Спостережемо що:

Q_1A = \begin{pmatrix}
14 & 21 & -14 \\
0 & -49 & -14 \\
0 & 168 & -77 \end{pmatrix},

Отже, ми вже маємо майже трикутну матрицю. Нам лише потрібен нуль у чарунці (3, 2).

Візьмемо мінор (1, 1) і знову застосуємо процес до

A' = M_{11} = \begin{pmatrix}
-49 & -14 \\
168 & -77 \end{pmatrix}.

Таким саме методом як і вище, отримуємо матрицю перетворення Хаусхолдера

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=\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=\begin{pmatrix}
0.8571 & -0.3943 & 0.3314 \\
0.4286 &  0.9029 & -0.0343 \\
-0.2857 & 0.1714 & 0.9429 \end{pmatrix}
R=Q_2Q_1A=Q^T A=\begin{pmatrix}
14 & 21 & -14 \\
0 & 175 & -70 \\
0 & 0 & -35 \end{pmatrix}.

Матриця Q є ортогональною і R є верхньою трикутною, отже A = QR і є шуканим QR-розкладом.

Джерела[ред.ред. код]