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 и верхней треугольной матрицы размера m × n R . Поскольку нижние ( 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 1 _R 1 _тонкой QR -факторизацией A ; Трефетен и Бау называют это сокращенной QR-факторизацией . ^[1] Если A имеет полный ранг n и мы требуем, чтобы диагональные элементы R ₁ были положительными, тогда R ₁ и Q ₁ уникальны, но в общем случае Q ₂ нет. Тогда R ₁ равен верхнему треугольному множителю разложения Холецкого A * A ( =  AT A, ^если A вещественное ).

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

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

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

Существует несколько методов фактического вычисления 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

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

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

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

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

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

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

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

Отражение Хаусхолдера ( или преобразование Хаусхолдера ) — это преобразование, которое принимает вектор и отражает его относительно некоторой плоскости или гиперплоскости . Мы можем использовать эту операцию для вычисления 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 ₁ , которую получаем, когда выбираем первый столбец матрицы для 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 .

Суммируя эти числа за 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}}}$

И результат теперь имеет ноль в элементе. ${\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}$

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

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

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

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

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

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

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

Повернутый 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-разложение
• Разложение по сингулярным значениям

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

1. Трефетен, Ллойд Н .; Бау, Дэвид III (1997). Численная линейная алгебра . Филадельфия, Пенсильвания: Общество промышленной и прикладной математики . ISBN 978-0-898713-61-9.
2. Стер, Йозеф; Булирш, Роланд (2002), Введение в численный анализ (3-е изд.), Springer, стр. 225, ISBN 0-387-95452-Х
3. Стрэнг, Гилберт (2019). Линейная алгебра и обучение на данных (1-е изд.). Уэлсли: Уэлсли Кембридж Пресс. п. 143. ИСБН 978-0-692-19638-0.
4. Паркер, Роберт Л. (1994). Геофизическая обратная теория. Принстон, Нью-Джерси: Издательство Принстонского университета. Раздел 1.13. ISBN 978-0-691-20683-7. ОСЛК  1134769155.

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

• Голуб, Джин Х .; Ван Лоан, Чарльз Ф. (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++.