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

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

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

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

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

${ Displaystyle А = QR, ,}$

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

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

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

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

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

${ displaystyle A = QR = Q { begin {bmatrix} R_ {1} 0 end {bmatrix}} = { begin {bmatrix} Q_ {1}, Q_ {2} end {bmatrix}} { begin {bmatrix} R_ {1} 0 end {bmatrix}} = Q_ {1} R_ {1},}$

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

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

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

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

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

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

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

Рассмотрим Процесс Грама – Шмидта применяется к столбцам полной матрицы рангов столбцов ${ displaystyle A = left [ mathbf {a} _ {1}, ldots, mathbf {a} _ {n} right]}$, с внутренний продукт ${ Displaystyle langle mathbf {v}, mathbf {w} rangle = mathbf {v} ^ { extf {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 {align} mathbf {u} _ {1} & = mathbf {a} _ {1}, & mathbf {e} _ {1} & = { mathbf {u} _ { 1} over | mathbf {u} _ {1} |} mathbf {u} _ {2} & = mathbf {a} _ {2} - operatorname {proj} _ { mathbf {u} _ {1}} , mathbf {a} _ {2}, & mathbf {e} _ {2} & = { mathbf {u} _ {2} over | mathbf {u } _ {2} |} mathbf {u} _ {3} & = mathbf {a} _ {3} - operatorname {proj} _ { mathbf {u} _ {1}} , mathbf {a} _ {3} - operatorname {proj} _ { mathbf {u} _ {2}} , mathbf {a} _ {3}, & mathbf {e} _ {3} & = { mathbf {u} _ {3} over | mathbf {u} _ {3} |} & vdots && vdots mathbf {u} _ {k} & = mathbf {a} _ {k} - sum _ {j = 1} ^ {k-1} operatorname {proj} _ { mathbf {u} _ {j}} , mathbf {a} _ {k} , & mathbf {e} _ {k} & = { mathbf {u} _ {k} over | mathbf {u} _ {k} |} end {align}}}$

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

${ displaystyle { begin {align} mathbf {a} _ {1} & = langle mathbf {e} _ {1}, mathbf {a} _ {1} rangle mathbf {e} _ { 1} mathbf {a} _ {2} & = langle mathbf {e} _ {1}, mathbf {a} _ {2} rangle mathbf {e} _ {1} + langle mathbf {e} _ {2}, mathbf {a} _ {2} rangle mathbf {e} _ {2} mathbf {a} _ {3} & = langle mathbf {e} _ {1}, mathbf {a} _ {3} rangle mathbf {e} _ {1} + langle mathbf {e} _ {2}, mathbf {a} _ {3} rangle mathbf {e} _ {2} + langle mathbf {e} _ {3}, mathbf {a} _ {3} rangle mathbf {e} _ {3} & vdots mathbf {a} _ {k} & = sum _ {j = 1} ^ {k} langle mathbf {e} _ {j}, mathbf {a} _ {k} rangle mathbf {e} _ {j} end {align}}}$

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

${ displaystyle A = QR}$

куда:

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

и

${ displaystyle R = { begin {pmatrix} langle mathbf {e} _ {1}, mathbf {a} _ {1} rangle & langle mathbf {e} _ {1}, mathbf { a} _ {2} rangle & langle mathbf {e} _ {1}, mathbf {a} _ {3} rangle & ldots 0 & langle mathbf {e} _ {2}, mathbf {a} _ {2} rangle & langle mathbf {e} _ {2}, mathbf {a} _ {3} rangle & ldots 0 & 0 & langle mathbf {e} _ { 3}, mathbf {a} _ {3} rangle & ldots vdots & vdots & vdots & ddots end {pmatrix}}.}$

Пример

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

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

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

${ Displaystyle Q ^ { extf {T}} , Q = I.}$

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

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

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

${ Displaystyle { begin {выровнено} Q ^ { extf {T}} A & = Q ^ { extf {T}} Q , R = R; R & = Q ^ { extf {T}} A = { begin {pmatrix} 14 & 21 & -14 0 & 175 & -70 0 & 0 & 35 end {pmatrix}}. end {align}}}$

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

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

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

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

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

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

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

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

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

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

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

${ Displaystyle альфа = -e ^ {я arg x_ {k}} | mathbf {x} |}$

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

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

${ displaystyle { begin {align} mathbf {u} & = mathbf {x} - alpha mathbf {e} _ {1}, mathbf {v} & = { mathbf {u} над | mathbf {u} |}, Q & = I-2 mathbf {v} mathbf {v} ^ { extf {T}}. end {выравнивается}}}$

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

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

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

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

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

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

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

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

После ${ displaystyle t}$ итерации этого процесса, ${ Displaystyle т = мин (м-1, п)}$,

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

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

${ Displaystyle Q = Q_ {1} ^ { extf {T}} Q_ {2} ^ { extf {T}} cdots Q_ {t} ^ { extf {T}},}$

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

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

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

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

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

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

Пример

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

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

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

Сейчас же,

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

и

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

Здесь,

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

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

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

${ displaystyle { begin {align} Q_ {1} = {} & I- {2 over { sqrt {14}} { sqrt {14}}} { begin {pmatrix} -1 3 -2 end {pmatrix}} { begin {pmatrix} -1 & 3 & -2 end {pmatrix}} = {} & I- {1 over 7} { begin {pmatrix} 1 & -3 & 2 - 3 & 9 & -6 2 & -6 & 4 end {pmatrix}} = {} & { begin {pmatrix} 6/7 & 3/7 & -2 / 7 3/7 & -2 / 7 & 6/7 - 2 / 7 и 6/7 и 3/7 end {pmatrix}}. End {align}}}$

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

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

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

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

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

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

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

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

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

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

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

${ displaystyle { begin {align} Q & = Q_ {1} ^ { extf {T}} Q_ {2} ^ { extf {T}} = { begin {pmatrix} 0,8571 & -0,3943 & 0,3314 0.4286 & 0.9029 & -0.0343 - 0.2857 & 0.1714 & 0.9429 end {pmatrix}} R & = Q_ {2} Q_ {1} A = Q ^ { extf {T}} A = { begin {pmatrix} 14 & 21 & -14 0 & 175 & -70 0 & 0 & -35 end {pmatrix}}. end {выравнивается}}}$

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

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

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

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

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

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

Пример

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

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

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

${ displaystyle { begin {align} G_ {1} & = { begin {pmatrix} cos ( theta) & 0 & - sin ( theta) 0 & 1 & 0 sin ( theta) & 0 & cos ( theta) end {pmatrix}} & приблизительно { begin {pmatrix} 0,94868 & 0 & -0,31622 0 & 1 & 0 0,31622 & 0 & 0,94868 end {pmatrix}} end {выровнено}}}$

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

${ displaystyle G_ {1} A приблизительно { begin {pmatrix} 12.64911 & -55.97231 & 16.76007 6 & 167 & -68 0 & 6.64078 & -37.6311 end {pmatrix}}}$

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

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

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

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

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

${ Displaystyle Det (A) = Det (Q) CDOT Det (R).}$

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

${ Displaystyle left | Det (A) right | = left | Det (R) right | = left | prod _ {i} r_ {ii} right |,}$

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Обобщения

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

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

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

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

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

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

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

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