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

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

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

${\displaystyle A=QR,}$

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

Если же A — комплексная квадратная матрица, то существует разложение A = QR , где Q — унитарная матрица (то есть сопряженная транспонированная матрица ).${\displaystyle Q^{\dagger}=Q^{-1}}$

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

В более общем случае мы можем разложить комплексную матрицу A размером m × n , где m ≥ n , на множители как произведение унитарной матрицы Q размером m × m и верхней треугольной матрицы R размером m × n . Поскольку нижние ( m − n ) строк верхней треугольной матрицы размером m × n состоят полностью из нулей, часто бывает полезно разбить R или и R , и 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},}$

где R ₁ — верхняя треугольная матрица размера n × n , 0 — нулевая матрица размера ( m − n ) × n , Q ₁ — это m × n , Q ₂ — это m ×( m − n ) , а Q ₁ и Q ₂ имеют ортогональные столбцы.

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

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

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

Рассмотрим процесс Грама–Шмидта , примененный к столбцам полной матрицы рангов столбцов , со внутренним произведением (или для сложного случая).${\displaystyle A={\begin{bmatrix}\mathbf {a} _{1}&\cdots &\mathbf {a} _{n}\end{bmatrix}}}$ ${\displaystyle \langle \mathbf {v} ,\mathbf {w} \rangle =\mathbf {v} ^{\textsf {T}}\mathbf {w} }$${\displaystyle \langle \mathbf {v} ,\mathbf {w} \rangle =\mathbf {v} ^{\dagger }\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}&={\frac {\mathbf {u} _{1}}{\|\mathbf {u} _{1}\|}}\\\mathbf {u} _{2}&=\mathbf {a} _{2}-\operatorname {proj} _{\mathbf {u} _{1}}\mathbf {a} _{2},&\mathbf {e} _{2}&={\frac {\mathbf {u} _{2}}{\|\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}&={\frac {\mathbf {u} _{3}}{\|\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}&={\frac {\mathbf {u} _{k}}{\|\mathbf {u} _{k}\|}}\end{aligned}}}$

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

${\displaystyle {\begin{aligned}\mathbf {a} _{1}&=\left\langle \mathbf {e} _{1},\mathbf {a} _{1}\right\rangle \mathbf {e} _{1}\\\mathbf {a} _{2}&=\left\langle \mathbf {e} _{1},\mathbf {a} _{2}\right\rangle \mathbf {e} _{1}+\left\langle \mathbf {e} _{2},\mathbf {a} _{2}\right\rangle \mathbf {e} _{2}\\\mathbf {a} _{3}&=\left\langle \mathbf {e} _{1},\mathbf {a} _{3}\right\rangle \mathbf {e} _{1}+\left\langle \mathbf {e} _{2},\mathbf {a} _{3}\right\rangle \mathbf {e} _{2}+\left\langle \mathbf {e} _{3},\mathbf {a} _{3}\right\rangle \mathbf {e} _{3}\\&\;\;\vdots \\\mathbf {a} _{k}&=\sum _{j=1}^{k}\left\langle \mathbf {e} _{j},\mathbf {a} _{k}\right\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={\begin{bmatrix}\mathbf {e} _{1}&\cdots &\mathbf {e} _{n}\end{bmatrix}}}$

и

${\displaystyle R={\begin{bmatrix}\langle \mathbf {e} _{1},\mathbf {a} _{1}\rangle &\langle \mathbf {e} _{1},\mathbf {a} _{2}\rangle &\langle \mathbf {e} _{1},\mathbf {a} _{3}\rangle &\cdots &\langle \mathbf {e} _{1},\mathbf {a} _{n}\rangle \\0&\langle \mathbf {e} _{2},\mathbf {a} _{2}\rangle &\langle \mathbf {e} _{2},\mathbf {a} _{3}\rangle &\cdots &\langle \mathbf {e} _{2},\mathbf {a} _{n}\rangle \\0&0&\langle \mathbf {e} _{3},\mathbf {a} _{3}\rangle &\cdots &\langle \mathbf {e} _{3},\mathbf {a} _{n}\rangle \\\vdots &\vdots &\vdots &\ddots &\vdots \\0&0&0&\cdots &\langle \mathbf {e} _{n},\mathbf {a} _{n}\rangle \\\end{bmatrix}}.}$

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

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

Напомним, что ортонормированная матрица обладает свойством .${\displaystyle Q}$${\displaystyle Q^{\textsf {T}}Q=I}$

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

${\displaystyle {\begin{aligned}U={\begin{bmatrix}\mathbf {u} _{1}&\mathbf {u} _{2}&\mathbf {u} _{3}\end{bmatrix}}&={\begin{bmatrix}12&-69&-58/5\\6&158&6/5\\-4&30&-33\end{bmatrix}};\\Q={\begin{bmatrix}{\frac {\mathbf {u} _{1}}{\|\mathbf {u} _{1}\|}}&{\frac {\mathbf {u} _{2}}{\|\mathbf {u} _{2}\|}}&{\frac {\mathbf {u} _{3}}{\|\mathbf {u} _{3}\|}}\end{bmatrix}}&={\begin{bmatrix}6/7&-69/175&-58/175\\3/7&158/175&6/175\\-2/7&6/35&-33/35\end{bmatrix}}.\end{aligned}}}$

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

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

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

Разложение QR представляет собой ортогонализацию Грама–Шмидта столбцов матрицы A , начиная с первого столбца.

Разложение RQ представляет собой ортогонализацию Грама–Шмидта строк матрицы A , начиная с последней строки.

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

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

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

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

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

и замените транспозицию сопряженной транспозицией в конструкции Q ниже.

Тогда, где - вектор [1 0 ⋯ 0] ^T , || · || - евклидова норма и - единичная матрица размером m × m , заданная${\displaystyle \mathbf {e} _{1}}$${\displaystyle I}$

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

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

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

${\displaystyle Q}$представляет собой матрицу Хаусхолдера размером m на m , которая является как симметричной, так и ортогональной (эрмитовой и унитарной в комплексном случае), и

${\displaystyle Q\mathbf {x} ={\begin{bmatrix}\alpha \\0\\\vdots \\0\end{bmatrix}}.}$

Это можно использовать для постепенного преобразования матрицы A размером m на n в верхнюю треугольную форму. Сначала мы умножаем A на матрицу Хаусхолдера Q _{1 ,} которую получаем, когда выбираем первый столбец матрицы для x . Это приводит к матрице Q ₁ A с нулями в левом столбце (за исключением первой строки).

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

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

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

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

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

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

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

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

Этот метод имеет большую численную устойчивость , чем метод Грама–Шмидта, описанный выше.

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

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

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

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

Давайте вычислим разложение

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

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

Сейчас,

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

и

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

Здесь,

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

Поэтому

${\displaystyle \mathbf {u} ={\begin{bmatrix}-2&6&-4\end{bmatrix}}^{\textsf {T}}=2{\begin{bmatrix}-1&3&-2\end{bmatrix}}^{\textsf {T}}}$и , а затем${\displaystyle \mathbf {v} ={\frac {1}{\sqrt {14}}}{\begin{bmatrix}-1&3&-2\end{bmatrix}}^{\textsf {T}}}$

${\displaystyle {\begin{aligned}Q_{1}={}&I-{\frac {2}{{\sqrt {14}}{\sqrt {14}}}}{\begin{bmatrix}-1\\3\\-2\end{bmatrix}}{\begin{bmatrix}-1&3&-2\end{bmatrix}}\\={}&I-{\frac {1}{7}}{\begin{bmatrix}1&-3&2\\-3&9&-6\\2&-6&4\end{bmatrix}}\\={}&{\begin{bmatrix}6/7&3/7&-2/7\\3/7&-2/7&6/7\\-2/7&6/7&3/7\\\end{bmatrix}}.\end{aligned}}}$

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

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

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

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

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

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

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

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

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

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

Или, с точностью до четырех десятичных знаков,

${\displaystyle {\begin{aligned}Q&=Q_{1}^{\textsf {T}}Q_{2}^{\textsf {T}}={\begin{bmatrix}0.8571&-0.3943&0.3314\\0.4286&0.9029&-0.0343\\-0.2857&0.1714&0.9429\end{bmatrix}}\\R&=Q_{2}Q_{1}A=Q^{\textsf {T}}A={\begin{bmatrix}14&21&-14\\0&175&-70\\0&0&-35\end{bmatrix}}.\end{aligned}}}$

Матрица Q ортогональна, а R — верхняя треугольная, поэтому A = QR — требуемое QR-разложение.

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

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

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

Давайте вычислим разложение

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

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

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

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

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

Аналогично мы можем сформировать матрицы Гивенса и , которые обнулят поддиагональные элементы и , образуя треугольную матрицу . Ортогональная матрица формируется из произведения всех матриц Гивенса . Таким образом, имеем , а QR- разложение равно .${\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}$${\displaystyle A=QR}$

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

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

${\displaystyle Q}$можно выбрать так, что . Таким образом,${\displaystyle \det Q=1}$$${\displaystyle \det A=\det R=\prod _{i}r_{ii}}$$

где — элементы на диагонали . Кроме того, поскольку определитель равен произведению собственных значений, мы имеем${\displaystyle r_{ii}}$${\displaystyle R}$$${\displaystyle \prod _{i}r_{ii}=\prod _{i}\lambda _{i}}$$

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

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

Начнем с QR-разложения неквадратной матрицы A :

${\displaystyle A=Q{\begin{bmatrix}R\\0\end{bmatrix}},\qquad Q^{\dagger }Q=I}$

где обозначает нулевую матрицу, а — унитарная матрица.${\displaystyle 0}$${\displaystyle Q}$

Из свойств разложения по сингулярным числам (SVD) и определителя матрицы имеем

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

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

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

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

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

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

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

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

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

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

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

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

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

• Голуб, Джин Х.; Ван Лоан, Чарльз Ф. (1996), Матричные вычисления (3-е изд.), Джонс Хопкинс, ISBN 978-0-8018-5414-9.
• Хорн, Роджер А.; Джонсон, Чарльз Р. (1985), Матричный анализ , Cambridge University Press, раздел 2.8, ISBN 0-521-38632-2
• Press, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007), «Раздел 2.10. QR-разложение», Numerical Recipes: The Art of Scientific Computing (3-е изд.), Нью-Йорк: Cambridge University Press, ISBN 978-0-521-88068-8

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