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

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

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

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

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

$A=QR,$

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

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

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

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

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

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

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

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

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

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

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

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

Дополнительная информация: Грамм – Шмидт § Численная стабильность.

Рассмотрим процесс Грама – Шмидта , примененный к столбцам матрицы полного ранга столбца. $A={\begin{bmatrix}\mathbf {a} _{1}&\cdots &\mathbf {a} _{n}\end{bmatrix}}$, с внутренним продуктом $\langle \mathbf {v} ,\mathbf {w} \rangle =\mathbf {v} ^{\textsf {T}}\mathbf {w}$ (или $\langle \mathbf {v} ,\mathbf {w} \rangle =\mathbf {v} ^{\dagger }\mathbf {w}$ для сложного случая).

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

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

затем:

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

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

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

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

$A=QR$

где:

$Q={\begin{bmatrix}\mathbf {e} _{1}&\cdots &\mathbf {e} _{n}\end{bmatrix}}$

и

$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}}.$

Пример

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Или, если $A$ сложный

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

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

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

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

$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, или вообще:

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

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

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

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

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

$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\left(n^{3}\right).$

Пример

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

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

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

Сейчас,

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

и

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

Здесь,

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

Поэтому

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

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

Теперь наблюдайте:

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

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

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

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

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

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

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

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

$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}}.$

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

${\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. матрицу

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

Пример

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

где $0$ обозначает нулевую матрицу и $Q$ является унитарной матрицей.

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

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

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

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

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

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

Колонна поворотная

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

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

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

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

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

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

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

Обобщения

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

См. также

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

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

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

Внешние ссылки

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