В линейной алгебре , А преобразование хаусхолдер (также известный как отражение Хаусхолдер или элементарный отражатель ) представляет собой линейное преобразование , которое описывает отражение о плоскости или гиперплоскости , содержащее начало. Преобразование Хаусхолдера было использовано в статье Олстона Скотта Хаусхолдера 1958 года . [1]
Его аналогом над общими внутренними пространствами продукта является оператор Хаусхолдера .
Определение [ править ]
Трансформация [ править ]
Гиперплоскость отражения может быть определена единичным вектором (вектором длины ), который ортогонален гиперплоскости. Отражением точки относительно этой гиперплоскости является линейное преобразование :
где задается как единичный вектор-столбец с эрмитовым транспонированием .
Матрица домохозяев [ править ]
Матрица, построенная на основе этого преобразования, может быть выражена через внешний продукт как:
известна как матрица Хаусхолдера , где - единичная матрица
Свойства [ править ]
Матрица Хаусхолдера имеет следующие свойства:
- это эрмиты : ,
- это унитарное : ,
- следовательно , это инволютивное : .
- Матрица Хаусхолдера имеет собственные значения . Чтобы увидеть это, обратите внимание, что if ортогонален вектору, который использовался для создания отражателя, то , то есть, является собственным значением кратности , поскольку существуют независимые векторы, ортогональные к . Также обратите внимание , как и собственное значение с кратностью .
- Определитель отражателя Хаусхолдер это , так как определитель матрицы является продуктом его собственных значений, в этом случае один из которых с остальным (как и в предыдущем пункте).
Приложения [ править ]
Геометрическая оптика [ править ]
В геометрической оптике зеркальное отражение может быть выражено в терминах матрицы Хаусхолдера (см. Зеркальное отражение § Формулировка вектора ).
Числовая линейная алгебра [ править ]
Преобразования Хаусхолдера широко используются в числовой линейной алгебре для выполнения QR-разложения и являются первым шагом QR-алгоритма . Они также широко используются для преобразования в форму Гессенберга . Для симметричных или эрмитовых матриц симметрия может сохраняться, что приводит к трехдиагонализации . [2]
QR-разложение [ править ]
Домовладелец отражение может быть использовано для вычисления QR - разложения , отражая первый один столбец матрицы на кратный стандартный базисный вектор, вычисление матрицы преобразования, умножив его с исходной матрицей , а затем рекурсии вниз несовершеннолетних этим продуктом.
Трехдиагонализация [ править ]
Эта процедура представлена в «Численном анализе по Burden and Faires». [3] На первом этапе, чтобы сформировать матрицу Хаусхолдера на каждом этапе, нам необходимо определить и , а именно:
Из и построить вектор :
где , и
- для каждого
Затем вычислите:
После нахождения и вычисления процесс повторяется для следующего:
Продолжая таким образом, формируется трехдиагональная и симметричная матрица.
Примеры [ править ]
В этом примере, также из Burdern and Faires [3], данная матрица преобразуется в аналогичную трехдиагональную матрицу A 3 с использованием метода Хаусхолдера.
Следуя этим шагам в методе Хаусхолдера, мы получаем:
Первая матрица Хаусхолдера:
Используется для формирования
Как видим, конечный результат представляет собой трехдиагональную симметричную матрицу, аналогичную исходной. Процесс завершается после двух шагов.
Вычислительная и теоретическая связь с другими унитарными преобразованиями [ править ]
Преобразование Хаусхолдера - это отражение гиперплоскости с единичным вектором нормали , как было сказано ранее. An матрицу с размерностью унитарного преобразования удовлетворяет . Взятие определителя ( -й степени среднего геометрического) и следа (пропорционального среднему арифметическому) унитарной матрицы показывает, что ее собственные значения имеют единичный модуль. Это можно увидеть прямо и быстро:
Поскольку средние арифметические и геометрические равны, если переменные постоянны (см. Неравенство средних арифметических и геометрических ), мы устанавливаем требование единичного модуля.
Для случая вещественнозначных унитарных матриц получают ортогональные матрицы , . Из этого довольно легко следует (см. Ортогональную матрицу ), что любая ортогональная матрица может быть разложена на произведение 2 на 2 вращения, называемых вращениями Гивенса и отражениями Хаусхолдера. Это интуитивно привлекательно, поскольку умножение вектора на ортогональную матрицу сохраняет длину этого вектора, а вращения и отражения исчерпывают набор геометрических операций (с действительным знаком), которые делают длину вектора неизменной.
Было показано, что преобразование Хаусхолдера взаимно однозначно связано с каноническим разложением смежных классов унитарных матриц, определенных в теории групп, которое может использоваться для очень эффективной параметризации унитарных операторов. [4]
Наконец, отметим, что одно преобразование Хаусхолдера, в отличие от отдельного преобразования Гивенса, может воздействовать на все столбцы матрицы и, как таковое, демонстрирует наименьшие вычислительные затраты для QR-разложения и трехдиагонализации. Наказанием за эту «вычислительную оптимальность» является, конечно, то, что операции Хаусхолдера не могут быть столь глубоко или эффективно распараллелены. Таким образом, Хаусхолдер предпочтительнее для плотных матриц на последовательных машинах, в то время как Гивенс предпочтительнее для разреженных матриц и / или параллельных машин.
Ссылки [ править ]
- Перейти ↑ Householder, AS (1958). «Унитарная триангуляция несимметричной матрицы» (PDF) . Журнал ACM . 5 (4): 339–342. DOI : 10.1145 / 320941.320947 . Руководство по ремонту 0111128 .
- ^ Шабауэр, Ханнес; Пачер, Кристоф; Сандерленд, Эндрю Дж .; Ганстерер, Уилфрид Н. (01.05.2010). «К параллельному решателю для обобщенных сложных симметричных задач на собственные значения» . Процедуры информатики . 1 (1): 437–445. DOI : 10.1016 / j.procs.2010.04.047 .
- ^ а б Бэрден, Ричард; Faires, Дуглас (10 декабря 2004 г.). Численный анализ (8-е изд.). Томсон Брукс / Коул. ISBN 9780534392000.
- ^ Ренан Кабрера; Трэйси Строхеккер; Гершель Рабиц (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. Cite journal requires
|journal=
(help) (Здесь Преобразование Хаусхолдера упоминается как топ-10 алгоритмов этого века) - Нажмите, WH; Теукольский С.А.; Феттерлинг, штат Вашингтон; Фланнери, ВР (2007). «Раздел 11.3.2. Метод Хаусхолдера» . Числовые рецепты: искусство научных вычислений (3-е изд.). Нью-Йорк: Издательство Кембриджского университета. ISBN 978-0-521-88068-8.