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

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

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

Определение

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

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

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

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

Матрица домохозяев

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

$P=I-2vv^{*}$

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

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

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

• это эрмитово : ${\textstyle P=P^{*}}$,
• оно унитарно : ${\textstyle P^{-1}=P^{*}}$,
• следовательно, оно инволютивно : ${\textstyle P=P^{-1}}$.
• Матрица Хаусхолдера имеет собственные значения. ${\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 (i,i)}$ несовершеннолетние этого продукта. Для этого эрмитова унитарная матрица Q ищется , которая переводит комплексный вектор x в комплексное кратное комплексному вектору e . Для QR-разложения e будет единичным координатным вектором, скажем, для k-й координаты. Комплексная матрица Q, имеющая форму Q = I - uu * с u * u = 2, обладает желаемым свойством быть эрмитовой унитарной. Здесь * обозначает сопряженное транспонирование. Поскольку задействованы только два вектора — это x и e , вектор u должен иметь форму u = a x + b e , где a и b — комплексные коэффициенты, которые необходимо определить. Поскольку общий фазовый коэффициент для u не имеет значения, коэффициент a можно выбрать положительным действительным. Теперь Q x = x (1 – a ( u * x )) - e ( b ( u * x )). Чтобы коэффициент вектора x был равен нулю, два члена в u * x должны иметь одинаковую фазу в пределах, кратных 180 градусам, поэтому мы должны иметь arg(b) = arg( e * x ) в пределах, кратных 180. градусов. Есть два решения в зависимости от того, выбрано четное или нечетное кратное 180 градусам. Итак, для комплексного коэффициента вектора чтобы x было равно нулю, необходимо решить два линейных уравнения относительно модулей a и b. Фазы a и b уже определены. Предположим , что e — k-й единичный координатный вектор, так что e * e = 1 и x _k = e * x , и пусть | х |= sqrt( х * х ). Тогда a и b могут быть выражены просто либо как a =1/sqrt (| x | (| x |+ |x _k |)) и b = a | х | exp(i*arg(x _k )) или как a =1/sqrt (| x | (| x |- |x _k |)) и b = - a | х | exp(i*arg(x _k )). Множитель e равен -b/a для обоих решений. Первое решение лучше, поскольку знаменатель не может быть близок к нулю по сравнению с | х |.

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

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

Эта процедура представлена ​​в «Численном анализе» Бердена и Фейра. Он использует слегка измененный $\operatorname {sgn}$ функция с $\operatorname {sgn} (0)=1$. На первом этапе для формирования матрицы Хаусхолдера на каждом этапе нам необходимо определить ${\textstyle \alpha }$ и ${\textstyle r}$, которые:

${\begin{aligned}\alpha &=-\operatorname {sgn} \left(a_{21}\right){\sqrt {\sum _{j=2}^{n}a_{j1}^{2}}};\\r&={\sqrt {{\frac {1}{2}}\left(\alpha ^{2}-a_{21}\alpha \right)}};\end{aligned}}$

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

$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}}}$, и

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

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

${\begin{aligned}P^{1}&=I-2v^{(1)}\left(v^{(1)}\right)^{\textsf {T}}\\A^{(2)}&=P^{1}AP^{1}\end{aligned}}$

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

${\begin{aligned}\alpha &=-\operatorname {sgn} \left(a_{k+1,k}^{k}\right){\sqrt {\sum _{j=k+1}^{n}\left(a_{jk}^{k}\right)^{2}}}\\[2pt]r&={\sqrt {{\frac {1}{2}}\left(\alpha ^{2}-a_{k+1,k}^{k}\alpha \right)}}\\[2pt]v_{1}^{k}&=v_{2}^{k}=\cdots =v_{k}^{k}=0\\[2pt]v_{k+1}^{k}&={\frac {a_{k+1,k}^{k}-\alpha }{2r}}\\v_{j}^{k}&={\frac {a_{jk}^{k}}{2r}}{\text{ for }}j=k+2,\ k+3,\ \ldots ,\ n\\P^{k}&=I-2v^{(k)}\left(v^{(k)}\right)^{\textsf {T}}\\A^{(k+1)}&=P^{k}A^{(k)}P^{k}\end{aligned}}$

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

Примеры

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

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

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

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

${\begin{aligned}Q_{1}&={\begin{bmatrix}1&0&0&0\\0&-{\frac {1}{3}}&{\frac {2}{3}}&-{\frac {2}{3}}\\0&{\frac {2}{3}}&{\frac {2}{3}}&{\frac {1}{3}}\\0&-{\frac {2}{3}}&{\frac {1}{3}}&{\frac {2}{3}}\end{bmatrix}},\\A_{2}=Q_{1}AQ_{1}&={\begin{bmatrix}4&-3&0&0\\-3&{\frac {10}{3}}&1&{\frac {4}{3}}\\0&1&{\frac {5}{3}}&-{\frac {4}{3}}\\0&{\frac {4}{3}}&-{\frac {4}{3}}&-1\end{bmatrix}},\end{aligned}}$

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

${\begin{aligned}Q_{2}&={\begin{bmatrix}1&0&0&0\\0&1&0&0\\0&0&-{\frac {3}{5}}&-{\frac {4}{5}}\\0&0&-{\frac {4}{5}}&{\frac {3}{5}}\end{bmatrix}},\\A_{3}=Q_{2}A_{2}Q_{2}&={\begin{bmatrix}4&-3&0&0\\-3&{\frac {10}{3}}&-{\frac {5}{3}}&0\\0&-{\frac {5}{3}}&-{\frac {33}{25}}&{\frac {68}{75}}\\0&0&{\frac {68}{75}}&{\frac {149}{75}}\end{bmatrix}},\end{aligned}}$

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

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

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

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

${\begin{aligned}{\frac {\operatorname {Trace} \left(UU^{*}\right)}{N}}&={\frac {\sum _{j=1}^{N}\left|\lambda _{j}\right|^{2}}{N}}=1,&\operatorname {det} \left(UU^{*}\right)&=\prod _{j=1}^{N}\left|\lambda _{j}\right|^{2}=1.\end{aligned}}$

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

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

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

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

См. также

• Блок отражателя
• Ротация Гивенса
• Вращение Якоби

Ссылки

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