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

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

Случаи и определения [ править ]

Квадратная матрица [ править ]

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

${\ displaystyle A = QR,}$

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

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

Если имеют п линейно независимые столбцы, то первый п столбцы Q образует ортогональный базис для столбца пространства из A . В более общем смысле, первые k столбцов Q образуют ортонормированный базис для диапазона первых k столбцов A для любого 1 ≤ k ≤ n . ^[1] Тот факт , что любой столбец к из А зависит только от первых 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 ^T 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} ^ {\textf {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}&={\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 \\0&\langle \mathbf {e} _{2},\mathbf {a} _{2}\rangle &\langle \mathbf {e} _{2},\mathbf {a} _{3}\rangle &\cdots \\0&0&\langle \mathbf {e} _{3},\mathbf {a} _{3}\rangle &\cdots \\\vdots &\vdots &\vdots &\ddots \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 разложение преобразование матрица в произведение верхней треугольной матрицы 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 -мерным вектор-столбцом такой, что для скаляра α . Если алгоритм реализован с использованием арифметики с плавающей точкой , то α должен получить противоположный знак как к -й координате , где должна быть стержень координат , после которого все записи равны 0 в матрице А ' с окончательной верхней треугольной формой, избегайте потери значимости . В сложном случае установите${\displaystyle \mathbf {x} }$${\displaystyle A}$${\displaystyle \|\mathbf {x} \|=|\alpha |}$${\displaystyle \mathbf {x} }$${\displaystyle x_{k}}$

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

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

Тогда где - вектор [1 0 ⋯ 0] ^T , || · || является евклидова нормы и является м × м единичной матрицы, набор${\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} ^{*}.}$

${\displaystyle Q}$это м матрица с размерностью м Хаусхолдер матрица и

${\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 Q=Q_{1}^{\textsf {T}}Q_{2}^{\textsf {T}}\cdots Q_{t}^{\textsf {T}},}$

${\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}1&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)\cdot \det(R).}$

Так как Q является унитарным, . Таким образом,${\displaystyle \left|\det(Q)\right|=1}$

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

где хранятся записи по диагонали R .${\displaystyle r_{ii}}$

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

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

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

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

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

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

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

Из свойств SVD и определителя матрицы имеем

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

где - особые значения .${\displaystyle \sigma _{i}}$${\displaystyle A}$

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

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

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

Вращение столбца [ править ]

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

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

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

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

По сравнению с прямой обратной матрицей, обратные решения, использующие QR-разложение, более численно стабильны, о чем свидетельствуют их уменьшенные числа обусловленности [Parker, Geophysical Inverse Theory, Ch1.13].

Для решения Недоопределенные ( )${\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), Matrix Computations (3-е изд.), Johns Hopkins, ISBN 978-0-8018-5414-9.
• Хорн, Роджер А .; Джонсон, Чарльз Р. (1985), Матричный анализ , Cambridge University Press, ISBN 0-521-38632-2. Раздел 2.8.
• Нажмите, WH; Теукольский, С.А. Феттерлинг, Вашингтон; Фланнери, Б.П. (2007), «Раздел 2.10. QR-разложение» , Численные рецепты: Искусство научных вычислений (3-е изд.), Нью-Йорк: Cambridge University Press, ISBN. 978-0-521-88068-8
• Стоер, Йозеф; Булирш, Роланд (2002), Введение в численный анализ (3-е изд.), Springer, ISBN 0-387-95452-X.

Внешние ссылки [ править ]

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