QR-разложение - QR decomposition

В линейная алгебра, а QR-разложение, также известный как QR-факторизация или же QU факторизация это разложение из матрица А в продукт А = QR из ортогональная матрица Q и верхнетреугольная матрица р. QR-разложение часто используется для решения линейный метод наименьших квадратов проблема и является основой для конкретной алгоритм собственных значений, то QR-алгоритм.

Случаи и определения

Квадратная матрица

Любая настоящая квадратная матрица А может быть разложен как

${\displaystyle A=QR,\,}$

куда Q является ортогональная матрица (его столбцы ортогональный единичные векторы смысл ${\displaystyle Q^{\textsf {T}}Q=QQ^{\textsf {T}}=I}$) и р это верхний треугольная матрица (также называется прямоугольной матрицей, отсюда и название). Если А является обратимый, то факторизация единственна, если нам потребуются диагональные элементы р быть позитивным.

Если вместо этого А является комплексной квадратной матрицей, то существует разложение А = QR куда Q это унитарная матрица (так ${\displaystyle Q^{*}Q=QQ^{*}=I}$).

Если А имеет п линейно независимый столбцы, затем первый п столбцы Q для мужчин ортонормированный базис для пространство столбца из А. В более общем плане первый k столбцы Q образуют ортонормированный базис для охватывать из первых k столбцы А для любого 1 ≤k ≤ п.^[1] Дело в том, что любой столбец k из А зависит только от первого k столбцы Q отвечает за треугольную формур.^[1]

Прямоугольная матрица

В более общем плане мы можем разложить на множители сложные м×п матрица А, с м ≥ п, как продукт м×м унитарная матрица Q и м×п верхнетреугольная матрица р. Как внизу (м−п) ряды м×п верхнетреугольная матрица полностью состоит из нулей, часто бывает полезно разбить р, или оба р и Q:

${\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},}$

куда р₁ является п×п верхнетреугольная матрица, 0 является (м − п)×п нулевая матрица, Q₁ является м×п, Q₂ является м×(м − п), и Q₁ и Q₂ оба имеют ортогональные столбцы.

Голуб и Ван Лоан (1996), §5.2) вызов Q₁р₁ в тонкая QR-факторизация из А; Трефетен и Бау называют это уменьшенная QR-факторизация.^[1] Если А полный классифицировать п и потребуем, чтобы диагональные элементы р₁ положительны тогда р₁ и Q₁ уникальны, но в целом Q₂ не является. р₁ тогда равна верхнему треугольному множителю Разложение Холецкого из А* А (= А^ТА если А реально).

QL, RQ и LQ разложения

Аналогичным образом мы можем определить разложения QL, RQ и LQ с L быть ниже треугольная матрица.

Вычисление QR-разложения

Существует несколько методов реального вычисления QR-разложения, например, с помощью Процесс Грама – Шмидта, Преобразования домовладельцев, или же Гивенса вращения. У каждого есть ряд преимуществ и недостатков.

Использование процесса Грама – Шмидта

Дальнейшая информация: Грам – Шмидт § Численная устойчивость.

Рассмотрим Процесс Грама – Шмидта применяется к столбцам полной матрицы рангов столбцов ${\displaystyle A=\left[\mathbf {a} _{1},\ldots ,\mathbf {a} _{n}\right]}$, с внутренний продукт ${\displaystyle \langle \mathbf {v} ,\mathbf {w} \rangle =\mathbf {v} ^{\textsf {T}}\mathbf {w} }$ (или же ${\displaystyle \langle \mathbf {v} ,\mathbf {w} \rangle =\mathbf {v} ^{*}\mathbf {w} }$ для сложного случая).

Определить проекция:

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

тогда:

${\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}-\operatorname {proj} _{\mathbf {u} _{1}}\,\mathbf {a} _{2},&\mathbf {e} _{2}&={\mathbf {u} _{2} \over \|\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}&={\mathbf {u} _{3} \over \|\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}&={\mathbf {u} _{k} \over \|\mathbf {u} _{k}\|}\end{aligned}}}$

Теперь мы можем выразить ${\displaystyle \mathbf {a} _{i}}$s над нашим недавно вычисленным ортонормированным базисом:

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

куда ${\displaystyle \left\langle \mathbf {e} _{i},\mathbf {a} _{i}\right\rangle =\left\|\mathbf {u} _{i}\right\|}$. Это можно записать в матричной форме:

${\displaystyle A=QR}$

куда:

${\displaystyle Q=\left[\mathbf {e} _{1},\ldots ,\mathbf {e} _{n}\right]}$

и

${\displaystyle 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}}.}$

Пример

Рассмотрим разложение

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

Напомним, что ортонормированная матрица ${\displaystyle Q}$ имеет свойство

${\displaystyle Q^{\textsf {T}}\,Q=I.}$

Тогда мы можем вычислить ${\displaystyle Q}$ с помощью Грама – Шмидта следующим образом:

${\displaystyle {\begin{aligned}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}}.\end{aligned}}}$

Таким образом, мы имеем

${\displaystyle {\begin{aligned}Q^{\textsf {T}}A&=Q^{\textsf {T}}Q\,R=R;\\R&=Q^{\textsf {T}}A={\begin{pmatrix}14&21&-14\\0&175&-70\\0&0&35\end{pmatrix}}.\end{aligned}}}$

Связь с разложением RQ

Разложение RQ преобразует матрицу А в произведение верхнетреугольной матрицы р (также известная как прямоугольная) и ортогональная матрица Q. Единственное отличие от QR-разложения - это порядок этих матриц.

QR-разложение - это ортогонализация по Граму – Шмидту столбцов А, начиная с первого столбца.

RQ-разложение - это ортогонализация по Граму – Шмидту строк А, начиная с последнего ряда.

Преимущества и недостатки

Процесс Грама-Шмидта по своей природе численно нестабилен. Хотя применение проекций имеет привлекательную геометрическую аналогию с ортогонализацией, сама ортогонализация подвержена числовым ошибкам. Однако существенным преимуществом является простота реализации, что делает этот алгоритм полезным для использования при создании прототипов, если заранее созданная библиотека линейной алгебры недоступна.

Использование отражений Хаусхолдера

Отражение Хаусхолдера для QR-разложения: цель - найти линейное преобразование, изменяющее вектор ${\displaystyle x}$ в вектор такой же длины, который коллинеарен ${\displaystyle e_{1}}$. Мы могли бы использовать ортогональную проекцию (Грама-Шмидта), но это будет численно нестабильно, если векторы ${\displaystyle x}$ и ${\displaystyle e_{1}}$ близки к ортогональным. Вместо этого отражение Хаусхолдера отражается через пунктирную линию (выбранную, чтобы разделить угол между ${\displaystyle x}$ и ${\displaystyle e_{1}}$). Максимальный угол при этом преобразовании составляет 45 градусов.

А Отражение домохозяина (или же Преобразование домохозяина) - это преобразование, которое берет вектор и отражает его относительно некоторого самолет или же гиперплоскость. Мы можем использовать эту операцию для вычисления QR факторизация м-к-п матрица ${\displaystyle A}$ с м ≥ п.

Q может использоваться для отражения вектора таким образом, что все координаты, кроме одной, исчезают.

Позволять ${\displaystyle \mathbf {x} }$ быть произвольным реальным м-мерный вектор-столбец ${\displaystyle A}$ такой, что ${\displaystyle \|\mathbf {x} \|=|\alpha |}$ для скаляра α. Если алгоритм реализован с использованием арифметика с плавающей запятой, тогда α должен получить знак, противоположный знаку k-я координата ${\displaystyle \mathbf {x} }$, куда ${\displaystyle x_{k}}$ должна быть центральной координатой, после которой все элементы в матрице равны 0 А'окончательная форма верхнего треугольника, чтобы избежать потеря значимости. В сложном случае установите

${\displaystyle \alpha =-e^{i\arg x_{k}}\|\mathbf {x} \|}$

(Stoer & Bulirsch, 2002 г., п. 225) и заменить транспонирование сопряженным транспонированием при построении Q ниже.

Тогда где ${\displaystyle \mathbf {e} _{1}}$ - вектор (1 0… 0)^Т, || · || это Евклидова норма и ${\displaystyle I}$ является м-к-м единичная матрица, набор

${\displaystyle {\begin{aligned}\mathbf {u} &=\mathbf {x} -\alpha \mathbf {e} _{1},\\\mathbf {v} &={\mathbf {u} \over \|\mathbf {u} \|},\\Q&=I-2\mathbf {v} \mathbf {v} ^{\textsf {T}}.\end{aligned}}}$

Или если ${\displaystyle A}$ сложно

${\displaystyle Q=I-2\mathbf {v} \mathbf {v} ^{*}.}$

${\displaystyle Q}$ является м-к-м Матрица домовладельцев и

${\displaystyle Q\mathbf {x} ={\begin{pmatrix}\alpha &0&\cdots &0\end{pmatrix}}^{\textsf {T}}.\,}$

Это можно использовать для постепенного преобразования м-к-п матрица А к верхнему треугольный форма. Сначала умножаем А с матрицей Хаусхолдера Q₁ мы получаем, когда выбираем первый столбец матрицы для Икс. В результате получается матрица Q₁А с нулями в левом столбце (кроме первой строки).

${\displaystyle Q_{1}A={\begin{bmatrix}\alpha _{1}&\star &\dots &\star \\0&&&\\\vdots &&A'&\\0&&&\end{bmatrix}}}$

Это можно повторить для А' (получен из Q₁А удалив первую строку и первый столбец), в результате получится матрица Хаусхолдера Q′₂. Обратите внимание, что Q′₂ меньше чем Q₁. Поскольку мы хотим, чтобы он действительно работал на Q₁А вместо А′ Нам нужно развернуть его в верхний левый угол, заполнив 1, или в общем:

${\displaystyle Q_{k}={\begin{pmatrix}I_{k-1}&0\\0&Q_{k}'\end{pmatrix}}.}$

После ${\displaystyle t}$ итерации этого процесса, ${\displaystyle t=\min(m-1,n)}$,

${\displaystyle R=Q_{t}\cdots Q_{2}Q_{1}A}$

- верхнетреугольная матрица. Итак, с

${\displaystyle Q=Q_{1}^{\textsf {T}}Q_{2}^{\textsf {T}}\cdots Q_{t}^{\textsf {T}},}$

${\displaystyle A=QR}$ является QR-разложением ${\displaystyle A}$.

У этого метода больше числовая стабильность чем вышеописанный метод Грама – Шмидта.

В следующей таблице указано количество операций в k-й шаг QR-разложения с помощью преобразования Хаусхолдера, предполагающий квадратную матрицу размером п.

Операция	Количество операций в k-й шаг
Умножения	${\displaystyle 2(n-k+1)^{2}}$
Дополнения	${\displaystyle (n-k+1)^{2}+(n-k+1)(n-k)+2}$
Разделение	${\displaystyle 1}$
Квадратный корень	${\displaystyle 1}$

Суммируя эти числа по п - 1 шаг (для квадратной матрицы размером п) сложность алгоритма (с точки зрения умножения с плавающей запятой) определяется выражением

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

Пример

Вычислим разложение

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

Во-первых, нам нужно найти отражение, которое преобразует первый столбец матрицы А, вектор ${\displaystyle \mathbf {a} _{1}={\begin{pmatrix}12&6&-4\end{pmatrix}}^{\textsf {T}}}$, в ${\displaystyle \left\|\mathbf {a} _{1}\right\|\;\mathbf {e} _{1}={\begin{pmatrix}1&0&0\end{pmatrix}}^{\textsf {T}}.}$

Сейчас же,

${\displaystyle \mathbf {u} =\mathbf {x} -\alpha \mathbf {e} _{1},}$

и

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

Здесь,

${\displaystyle \alpha =14}$ и ${\displaystyle \mathbf {x} =\mathbf {a} _{1}={\begin{pmatrix}12&6&-4\end{pmatrix}}^{\textsf {T}}}$

Следовательно

${\displaystyle \mathbf {u} ={\begin{pmatrix}-2&6&-4\end{pmatrix}}^{\textsf {T}}={\begin{pmatrix}2\end{pmatrix}}{\begin{pmatrix}-1&3&-2\end{pmatrix}}^{\textsf {T}}}$ и ${\displaystyle \mathbf {v} ={1 \over {\sqrt {14}}}{\begin{pmatrix}-1&3&-2\end{pmatrix}}^{\textsf {T}}}$, а потом

${\displaystyle {\begin{aligned}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}}.\end{aligned}}}$

Теперь обратите внимание:

${\displaystyle Q_{1}A={\begin{pmatrix}14&21&-14\\0&-49&-14\\0&168&-77\end{pmatrix}},}$

так что у нас уже есть почти треугольная матрица. Нам нужно только обнулить запись (3, 2).

Возьмите (1, 1) незначительный, а затем снова примените процесс к

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

Тем же способом, что и выше, получаем матрицу преобразования Хаусхолдера

${\displaystyle Q_{2}={\begin{pmatrix}1&0&0\\0&-7/25&24/25\\0&24/25&7/25\end{pmatrix}}}$

после выполнения прямого суммирования с 1, чтобы убедиться, что следующий шаг в процессе работает правильно.

Теперь мы находим

${\displaystyle Q=Q_{1}^{\textsf {T}}Q_{2}^{\textsf {T}}={\begin{pmatrix}6/7&-69/175&58/175\\3/7&158/175&-6/175\\-2/7&6/35&33/35\end{pmatrix}}}$

Или, до четырех десятичных цифр,

${\displaystyle {\begin{aligned}Q&=Q_{1}^{\textsf {T}}Q_{2}^{\textsf {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^{\textsf {T}}A={\begin{pmatrix}14&21&-14\\0&175&-70\\0&0&-35\end{pmatrix}}.\end{aligned}}}$

Матрица Q ортогонален и р верхний треугольник, поэтому А = QR - искомое QR-разложение.

Преимущества и недостатки

Использование преобразований Хаусхолдера по своей сути является наиболее простым из численно устойчивых алгоритмов QR-разложения из-за использования отражений в качестве механизма для получения нулей в р матрица. Однако алгоритм отражения Хаусхолдера требует большой полосы пропускания и не может быть распараллелен, поскольку каждое отражение, которое создает новый нулевой элемент, полностью изменяет оба Q и р матрицы.

Использование вращений Гивенса

QR разложения также могут быть вычислены с помощью серии Гивенса вращения. Каждый поворот обнуляет элемент в поддиагонали матрицы, образуя р матрица. Конкатенация всех вращений Гивенса образует ортогональную Q матрица.

На практике вращения Гивенса фактически не выполняются путем построения всей матрицы и выполнения матричного умножения. Вместо этого используется процедура вращения Гивенса, которая выполняет эквивалент умножения разреженных матриц Гивенса, без дополнительной работы по обработке разреженных элементов. Процедура вращения Гивенса полезна в ситуациях, когда требуется обнулить только относительно небольшое количество недиагональных элементов, и ее легче распараллелить, чем Преобразования домовладельцев.

Пример

Вычислим разложение

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

Во-первых, нам нужно сформировать матрицу вращения, которая обнулит самый нижний левый элемент, ${\displaystyle \mathbf {a} _{31}=-4}$. Мы формируем эту матрицу, используя метод вращения Гивенса, и называем матрицу ${\displaystyle G_{1}}$. Сначала мы повернем вектор ${\displaystyle {\begin{pmatrix}12&-4\end{pmatrix}}}$, чтобы указать на Икс ось. Этот вектор имеет угол ${\displaystyle \theta =\arctan \left({-(-4) \over 12}\right)}$. Мы создаем ортогональную матрицу вращения Гивенса, ${\displaystyle G_{1}}$:

${\displaystyle {\begin{aligned}G_{1}&={\begin{pmatrix}\cos(\theta )&0&-\sin(\theta )\\0&1&0\\\sin(\theta )&0&\cos(\theta )\end{pmatrix}}\\&\approx {\begin{pmatrix}0.94868&0&-0.31622\\0&1&0\\0.31622&0&0.94868\end{pmatrix}}\end{aligned}}}$

И результат ${\displaystyle G_{1}A}$ теперь имеет ноль в ${\displaystyle \mathbf {a} _{31}}$ элемент.

${\displaystyle G_{1}A\approx {\begin{pmatrix}12.64911&-55.97231&16.76007\\6&167&-68\\0&6.64078&-37.6311\end{pmatrix}}}$

Аналогичным образом мы можем составить матрицы Гивенса ${\displaystyle G_{2}}$ и ${\displaystyle G_{3}}$, который обнулит субдиагональные элементы ${\displaystyle a_{21}}$ и ${\displaystyle a_{32}}$, образуя треугольную матрицу ${\displaystyle R}$. Ортогональная матрица ${\displaystyle Q^{\textsf {T}}}$ формируется из произведения всех матриц Гивенса ${\displaystyle Q^{\textsf {T}}=G_{3}G_{2}G_{1}}$. Таким образом, мы имеем ${\displaystyle G_{3}G_{2}G_{1}A=Q^{\textsf {T}}A=R}$, а QR разложение ${\displaystyle A=QR}$.

Преимущества и недостатки

QR-разложение с помощью вращений Гивенса является наиболее сложным для реализации, поскольку порядок строк, необходимых для полного использования алгоритма, определить нетривиально. Однако у него есть существенное преимущество в том, что каждый новый нулевой элемент ${\displaystyle a_{ij}}$ влияет только на строку с обнуляемым элементом (i) и строку выше (j). Это делает алгоритм вращения Гивенса более эффективным и распараллеливаемым, чем метод отражения Хаусхолдера.

Связь с определителем или произведением собственных значений

Мы можем использовать QR-разложение, чтобы найти абсолютное значение детерминант квадратной матрицы. Предположим, что матрица разлагается как ${\displaystyle A=QR}$. Тогда у нас есть

${\displaystyle \det(A)=\det(Q)\cdot \det(R).}$

С Q унитарен, ${\displaystyle |\det(Q)|=1}$. Таким образом,

${\displaystyle \left|\det(A)\right|=\left|\det(R)\right|=\left|\prod _{i}r_{ii}\right|,}$

куда ${\displaystyle r_{ii}}$ записи на диагонали р.

Кроме того, поскольку определитель равен произведению собственных значений, мы имеем

${\displaystyle \left|\prod _{i}r_{ii}\right|=\left|\prod _{i}\lambda _{i}\right|,}$

куда ${\displaystyle \lambda _{i}}$ собственные значения ${\displaystyle A}$.

Мы можем распространить указанные выше свойства на неквадратную комплексную матрицу ${\displaystyle A}$ путем введения определения QR-разложения для неквадратной комплексной матрицы и замены собственных значений сингулярными значениями.

Предположим, что QR-разложение для неквадратной матрицы А:

${\displaystyle A=Q{\begin{pmatrix}R\\O\end{pmatrix}},\qquad Q^{*}Q=I,}$

куда ${\displaystyle O}$ - нулевая матрица и ${\displaystyle Q}$ является унитарной матрицей.

Из свойств СВД и определитель матрицы, имеем

${\displaystyle \left|\prod _{i}r_{ii}\right|=\prod _{i}\sigma _{i},}$

куда ${\displaystyle \sigma _{i}}$ являются сингулярными значениями ${\displaystyle A}$.

Отметим, что сингулярные значения ${\displaystyle A}$ и ${\displaystyle R}$ идентичны, хотя их комплексные собственные значения могут быть разными. Однако если А является квадратным, верно следующее:

${\displaystyle {\prod _{i}\sigma _{i}}=\left|{\prod _{i}\lambda _{i}}\right|.}$

В заключение, QR-разложение можно эффективно использовать для вычисления произведения собственных значений или сингулярных значений матрицы.

Вращение колонны

Свернутый QR отличается от обычного Грама-Шмидта тем, что он занимает самый большой оставшийся столбец в начале каждого нового шага - поворот столбца - ^[2] и таким образом вводит матрица перестановок п:

${\displaystyle AP=QR\quad \iff \quad A=QRP^{\textsf {T}}}$

Вращение столбца полезно, когда А (почти) не имеющий ранга, или подозревается в этом. Это также может улучшить числовую точность. п обычно выбирается так, чтобы диагональные элементы р не возрастают: ${\displaystyle \left|r_{11}\right|\geq \left|r_{22}\right|\geq \ldots \geq \left|r_{nn}\right|}$. Это может быть использовано для определения (числового) ранга А при меньших вычислительных затратах, чем разложение по сингулярным числам, составляющих основу так называемых ранжирующие QR-алгоритмы.

Использование для решения линейных обратных задач

По сравнению с прямой обратной матрицей, обратные решения, использующие QR-разложение, более численно устойчивы, о чем свидетельствует их уменьшенная числа условий [Паркер, Геофизическая обратная теория, глава 1.13].

Чтобы решить недоопределенные (${\displaystyle m<n}$) линейная задача ${\displaystyle Ax=b}$ где матрица ${\displaystyle A}$ имеет размеры ${\displaystyle m\times n}$ и ранг ${\displaystyle m}$, сначала найдите QR-факторизацию транспонированной ${\displaystyle A}$: ${\displaystyle A^{\textsf {T}}=QR}$, где Q - ортогональная матрица (т.е. ${\displaystyle Q^{\textsf {T}}=Q^{-1}}$), а R имеет специальный вид: ${\displaystyle R={\begin{bmatrix}R_{1}\\0\end{bmatrix}}}$. Здесь ${\displaystyle R_{1}}$ это квадрат ${\displaystyle m\times m}$ прямоугольная матрица, а нулевая матрица имеет размерность ${\displaystyle (n-m)\times m}$. После некоторой алгебры можно показать, что решение обратной задачи может быть выражено как: ${\displaystyle x=Q{\begin{bmatrix}\left(R_{1}^{\textsf {T}}\right)^{-1}b\\0\end{bmatrix}}}$ где можно найти ${\displaystyle R_{1}^{-1}}$ к Гауссово исключение или вычислить ${\displaystyle \left(R_{1}^{\textsf {T}}\right)^{-1}b}$ непосредственно прямая замена. Последний метод отличается большей числовой точностью и меньшим объемом вычислений.

Чтобы найти решение ${\displaystyle {\hat {x}}}$ сверхдетерминированным (${\displaystyle m\geq n}$) проблема ${\displaystyle Ax=b}$ что минимизирует норму ${\displaystyle \|A{\hat {x}}-b\|}$, сначала найдите QR-факторизацию ${\displaystyle A}$: ${\displaystyle A=QR}$. Тогда решение может быть выражено как ${\displaystyle {\hat {x}}=R_{1}^{-1}\left(Q_{1}^{\textsf {T}}b\right)}$, куда ${\displaystyle Q_{1}}$ является ${\displaystyle m\times n}$ матрица, содержащая первый ${\displaystyle n}$ столбцы полного ортонормированного базиса ${\displaystyle Q}$ и где ${\displaystyle R_{1}}$ как и раньше. Эквивалентно недоопределенному случаю, обратная замена можно использовать, чтобы быстро и точно найти это ${\displaystyle {\hat {x}}}$ без явного инвертирования ${\displaystyle R_{1}}$. (${\displaystyle Q_{1}}$ и ${\displaystyle R_{1}}$ часто предоставляются числовыми библиотеками как "экономичное" QR-разложение.)

Обобщения

Разложение Ивасавы обобщает QR-разложение на полупростые группы Ли.

Смотрите также

• Полярное разложение
• Разложение на собственные значения
• Спектральное разложение
• LU разложение
• Разложение по сингулярным числам

Рекомендации

1. Л. Н. Трефетен и Д. Бау, Числовая линейная алгебра (СИАМ, 1997).
2. Стрэнг, Гилберт (2019). Линейная алгебра и обучение на основе данных (1-е изд.). Уэллсли: Wellesley Cambridge Press. п. 143. ISBN  978-0-692-19638-0.

дальнейшее чтение

• Голуб, Джин Х.; Ван Лоан, Чарльз Ф. (1996), Матричные вычисления (3-е изд.), Джонс Хопкинс, ISBN  978-0-8018-5414-9.
• Хорн, Роджер А .; Джонсон, Чарльз Р. (1985), Матричный анализ, Издательство Кембриджского университета, ISBN  0-521-38632-2. Раздел 2.8.
• Нажмите, WH; Теукольский С.А.; Феттерлинг, штат Вашингтон; Фланнери, BP (2007), «Раздел 2.10. QR-разложение», Числовые рецепты: искусство научных вычислений (3-е изд.), Нью-Йорк: Издательство Кембриджского университета, ISBN  978-0-521-88068-8
• Стоер, Йозеф; Булирш, Роланд (2002), Введение в численный анализ (3-е изд.), Springer, ISBN  0-387-95452-X.

внешняя ссылка

• Онлайн-калькулятор матрицы Выполняет QR-разложение матриц.
• LAPACK руководство пользователя дает подробную информацию о подпрограммах для расчета QR-разложения
• Руководство пользователя Mathematica дает подробную информацию и примеры процедур для расчета QR-разложения
• АЛГЛИБ включает частичный перенос LAPACK на C ++, C #, Delphi и т. д.
• Eigen :: QR Включает реализацию QR-разложения на C ++.