Преобразование домохозяина

В линейной алгебре, А преобразование хаусхолдер (также известный как отражение Хаусхолдер или элементарный отражатель) представляет собой линейное преобразование, которое описывает отражение о плоскости или гиперплоскости, содержащее начало. Преобразование Хаусхолдера было использовано в статье Олстона Скотта Хаусхолдера 1958 года.

Его аналогом над общими внутренними пространствами продукта является оператор Хаусхолдера.

СОДЕРЖАНИЕ

• 1 Определение
  • 1.1 Преобразование
  • 1.2 Матрица домовладельцев
    • 1.2.1 Свойства
• 2 Приложения
  • 2.1 Геометрическая оптика
  • 2.2 Числовая линейная алгебра
    • 2.2.1 QR-разложение
    • 2.2.2 Тридиагонализация
    • 2.2.3 Примеры
• 3 Вычислительная и теоретическая связь с другими унитарными преобразованиями
• 4 ссылки

Определение

Трансформация

Гиперплоскость отражения может быть определена ее нормальным вектором, единичным вектором (вектором длины), который ортогонален гиперплоскости. Отражением точки относительно этой гиперплоскости является линейное преобразование : ${\ textstyle v}$${\ textstyle 1}$ ${\ textstyle x}$

${\ displaystyle x-2 \ langle x, v \ rangle v = x-2v \ left (v ^ {\textf {H}} x \ right),}$

где задается как единичный вектор-столбец с эрмитовым транспонированием. ${\ textstyle v}$ ${\ textstyle v ^ {\textf {H}}}$

Матрица домовладельцев

Матрица, построенная на основе этого преобразования, может быть выражена через внешний продукт как:

${\ Displaystyle P = I-2vv ^ {\textf {H}}}$

известна как матрица Хаусхолдера, где - единичная матрица ${\ textstyle I}$

Характеристики

Матрица Хаусхолдера имеет следующие свойства:

• это эрмиты :,${\ textstyle P = P ^ {\textf {H}}}$
• это унитарное :,${\ textstyle P ^ {- 1} = P ^ {\textf {H}}}$
• следовательно, это инволютивное :.${\ textstyle P = P ^ {- 1}}$
• Матрица Хаусхолдера имеет собственные значения. Чтобы увидеть это, обратите внимание, что if ортогонален вектору, который использовался для создания отражателя, то, то есть, является собственным значением кратности, поскольку существуют независимые векторы, ортогональные к. Также обратите внимание, как и собственное значение с кратностью.${\ textstyle \ pm 1}$${\ textstyle u}$${\ textstyle v}$${\ textstyle Pu = u}$${\ textstyle 1}$${\ textstyle n-1}$${\ textstyle n-1}$${\ textstyle v}$${\ textstyle Pv = -v}$${\ textstyle -1}$${\ textstyle 1}$
• Определитель отражателя Хаусхолдер это, так как определитель матрицы является продуктом его собственных значений, в этом случае один из которых с остальным (как и в предыдущем пункте).${\ textstyle -1}$${\ textstyle -1}$${\ textstyle 1}$

Приложения

Геометрическая оптика

В геометрической оптике зеркальное отражение может быть выражено в терминах матрицы Хаусхолдера (см. « Зеркальное отражение» § Формулировка вектора ).

Числовая линейная алгебра

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

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

Домовладелец отражение может быть использовано для вычисления QR - разложения, отражая первый один столбец матрицы на кратный стандартный базисный вектор, вычисление матрицы преобразования, умножив его с исходной матрицей, а затем рекурсии вниз несовершеннолетних этим продуктом. ${\ textstyle (я, я)}$

Тридиагонализация

Основная статья: Трехдиагональная матрица

Эта процедура представлена ​​в «Численном анализе по Burden and Faires». На первом этапе, чтобы сформировать матрицу Хаусхолдера на каждом этапе, нам необходимо определить и, которые: ${\ textstyle \ alpha}$${\ textstyle r}$

${\ displaystyle {\ begin {align} \ alpha amp; = - \ operatorname {sgn} \ left (a_ {21} \ right) {\ sqrt {\ sum _ {j = 2} ^ {n} a_ {j1} ^ {2}}}; \\ r amp; = {\ sqrt {{\ frac {1} {2}} \ left (\ alpha ^ {2} -a_ {21} \ alpha \ right)}}; \ end {выровнено }}}$

Из и построить вектор: ${\ textstyle \ alpha}$${\ textstyle r}$${\ textstyle v}$

${\ Displaystyle v ^ {(1)} = {\ begin {bmatrix} v_ {1} \\ v_ {2} \\\ vdots \\ v_ {n} \ end {bmatrix}},}$

где, и ${\ textstyle v_ {1} = 0}$${\ textstyle v_ {2} = {\ frac {a_ {21} - \ alpha} {2r}}}$

${\ displaystyle v_ {k} = {\ frac {a_ {k1}} {2r}}}$ для каждого ${\ Displaystyle к = 3,4 \ ldots п}$

Затем вычислите:

${\ Displaystyle {\ begin {align} P ^ {1} amp; = I-2v ^ {(1)} \ left (v ^ {(1)} \ right) ^ {\textf {T}} \\ A ^ {(2)} amp; = P ^ {1} AP ^ {1} \ end {align}}}$

После нахождения и вычисления процесс повторяется для следующего: ${\ textstyle P ^ {1}}$${\ textstyle A ^ {(2)}}$${\ textstyle к = 2,3, \ ldots, n-2}$

${\ displaystyle {\ begin {align} \ alpha amp; = - \ operatorname {sgn} \ left (a_ {k + 1, k} ^ {k} \ right) {\ sqrt {\ sum _ {j = k + 1 } ^ {n} \ left (a_ {jk} ^ {k} \ right) ^ {2}}} \\ r amp; = {\ sqrt {{\ frac {1} {2}} \ left (\ alpha ^ { 2} -a_ {k + 1, k} ^ {k} \ alpha \ right)}} \\ v_ {1} ^ {k} amp; = v_ {2} ^ {k} = \ cdots = v_ {k} ^ {k} = 0 \\ v_ {k + 1} ^ {k} amp; = {\ frac {a_ {k + 1, k} ^ {k} - \ alpha} {2r}} \\ v_ {j} ^ {k} amp; = {\ frac {a_ {jk} ^ {k}} {2r}} {\ text {for}} j = k + 2, \ k + 3, \ \ ldots, \ n \\ P ^ {k} amp; = I-2v ^ {(k)} \ left (v ^ {(k)} \ right) ^ {\textf {T}} \\ A ^ {(k + 1)} amp; = P ^ {k} A ^ {(k)} P ^ {k} \ end {align}}}$

Продолжая таким образом, формируется трехдиагональная и симметричная матрица.

Примеры

В этом примере, также из Burden and Faires, данная матрица преобразуется в аналогичную трехдиагональную матрицу A 3 с использованием метода Хаусхолдера.

${\ displaystyle \ mathbf {A} = {\ begin {bmatrix} 4 amp; 1 amp; -2 amp; 2 \\ 1 amp; 2 amp; 0 amp; 1 \\ - 2 amp; 0 amp; 3 amp; -2 \\ 2 amp; 1 amp; -2 amp; -1 \ end {bmatrix}},}$

Следуя этим шагам в методе Хаусхолдера, мы получаем:

Первая матрица Хаусхолдера:

${\ displaystyle {\ begin {align} Q_ {1} amp; = {\ begin {bmatrix} 1 amp; 0 amp; 0 amp; 0 \\ 0 amp; -1 / 3 amp; 2/3 amp; -2 / 3 \\ 0 amp; 2/3 amp; 2/3 amp; 1/3 \\ 0 amp; -2 / 3 amp; 1/3 amp; 2/3 \ end {bmatrix}}, \\ A_ {2} = Q_ {1} AQ_ {1} amp; = {\ begin {bmatrix} 4 amp; -3 amp; 0 amp; 0 \\ - 3 amp; 10/3 amp; 1 amp; 4/3 \\ 0 amp; 1 amp; 5 / 3 amp; -4 / 3 \\ 0 amp; 4/3 amp; -4 / 3 amp; -1 \ end {bmatrix}}, \ end {align}}}$

Используется для формирования ${\ textstyle A_ {2}}$

${\ displaystyle {\ begin {align} Q_ {2} amp; = {\ begin {bmatrix} 1 amp; 0 amp; 0 amp; 0 \\ 0 amp; 1 amp; 0 amp; 0 \\ 0 amp; 0 amp; -3 / 5 amp; -4 / 5 \\ 0 amp; 0 amp; -4 / 5 amp; 3/5 \ end {bmatrix} }, \\ A_ {3} = Q_ {2} A_ {2} Q_ {2} amp; = {\ begin {bmatrix} 4 amp; -3 amp; 0 amp; 0 \\ - 3 amp; 10/3 amp; -5 / 3 amp; 0 \\ 0 amp; -5 / 3 amp; - 33/25 и 68/75 \\ 0 и 0 и 68/75 и 149/75 \ end {bmatrix}}, \ end {align}}}$

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

Вычислительная и теоретическая связь с другими унитарными преобразованиями

Смотрите также: Вращение (математика)

Преобразование Хаусхолдера - это отражение гиперплоскости с единичным вектором нормали, как было сказано ранее. An матрицу с размерностью унитарного преобразования удовлетворяет. Взятие определителя ( -й степени среднего геометрического) и следа (пропорционального среднему арифметическому) унитарной матрицы показывает, что ее собственные значения имеют единичный модуль. Это можно увидеть прямо и быстро: ${\ textstyle v}$${\ textstyle N}$${\ textstyle N}$ ${\ textstyle U}$${\ textstyle UU ^ {\textf {H}} = I}$${\ textstyle N}$${\ textstyle \ lambda _ {я}}$

${\ displaystyle {\ frac {\ operatorname {Trace} \ left (UU ^ {\textf {H}} \ right)} {N}} = {\ frac {\ sum _ {j = 1} ^ {N} \ left | \ lambda _ {j} \ right | ^ {2}} {N}} = 1, \ quad \ operatorname {det} \ left (UU ^ {\textf {H}} \ right) = \ prod _ { j = 1} ^ {N} \ left | \ lambda _ {j} \ right | ^ {2} = 1.}$

Поскольку средние арифметические и геометрические равны, если переменные постоянны (см. Неравенство средних арифметических и геометрических ), мы устанавливаем требование единичного модуля.

Для случая вещественнозначных унитарных матриц получают ортогональные матрицы,. Из этого довольно легко следует (см. Ортогональную матрицу ), что любую ортогональную матрицу можно разложить на произведение 2 на 2 вращения, называемых вращениями Гивенса и отражениями Хаусхолдера. Это интуитивно привлекательно, поскольку умножение вектора на ортогональную матрицу сохраняет длину этого вектора, а вращения и отражения исчерпывают набор (действительных) геометрических операций, которые делают длину вектора неизменной. ${\ textstyle UU ^ {\textf {T}} = I}$

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

Наконец, отметим, что одно преобразование Хаусхолдера, в отличие от отдельного преобразования Гивенса, может воздействовать на все столбцы матрицы и, как таковое, демонстрирует наименьшие вычислительные затраты на QR-разложение и трехдиагонализацию. Наказанием за эту «вычислительную оптимальность» является, конечно, то, что операции Хаусхолдера не могут быть столь глубоко или эффективно распараллелены. Таким образом, Хаусхолдер предпочтительнее для плотных матриц на последовательных машинах, в то время как Гивенс предпочтительнее для разреженных матриц и / или параллельных машин.

использованная литература

1. Перейти ↑ Householder, AS (1958). "Унитарная треугольная форма несимметричной матрицы" (PDF). Журнал ACM. 5 (4): 339–342. DOI : 10.1145 / 320941.320947. Руководство по ремонту   0111128.
2. ^ Табога, Марко. «Матрица Хаусхолдера. Лекции по матричной алгебре».
3. ^ Шабауэр, Ханнес; Пачер, Кристоф; Сандерленд, Эндрю Дж.; Ганстерер, Уилфрид Н. (01.05.2010). «К параллельному решателю для обобщенных сложных симметричных задач на собственные значения». Процедуры информатики. 1 (1): 437–445. DOI : 10.1016 / j.procs.2010.04.047.
4. ^ ^{а б} Бэрден, Ричард; Faires, Дуглас (10 декабря 2004 г.). Численный анализ (8-е изд.). Томсон Брукс / Коул. ISBN   9780534392000.
5. ^ Ренан Кабрера; Трэйси Строхеккер; Гершель Рабиц (2010). «Каноническое разложение смежных классов унитарных матриц с помощью преобразований Хаусхолдера». Журнал математической физики. 51 (8): 082101. arXiv : 1008.2477. Bibcode : 2010JMP.... 51h2101C. DOI : 10.1063 / 1.3466798.

• ЛаБудд, CD (1963). «Приведение произвольной действительной квадратной матрицы к трехдиагональной форме с помощью преобразований подобия». Математика вычислений. Американское математическое общество. 17 (84): 433–437. DOI : 10.2307 / 2004005. JSTOR   2004005. Руководство по ремонту   0156455.
• Моррисон, Д. Д. (1960). «Замечания об унитарной триангуляризации несимметричной матрицы». Журнал ACM. 7 (2): 185–186. DOI : 10.1145 / 321021.321030. Руководство по ремонту   0114291.
• Ципра, Барри А. (2000). «Лучшее из ХХ века: редакция назвала 10 лучших алгоритмов». 33 (4): 1. Цитировать журнал требует |journal=( помощь ) (Здесь Преобразование Хаусхолдера упоминается как 10 лучших алгоритмов этого века)
• Нажмите, WH; Теукольский, С.А.; Феттерлинг, штат Вашингтон; Фланнери, ВР (2007). «Раздел 11.3.2. Метод Хаусхолдера». Числовые рецепты: искусство научных вычислений (3-е изд.). Нью-Йорк: Издательство Кембриджского университета. ISBN   978-0-521-88068-8.