Разложение Холецкого

[Suvorov.as]

Кто-нибудь знает почему все математические пакеты делают разложение Холецкого лишь для положительно определенной матрицы?

[ewert]

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

[Suvorov.as]

А почему там должно возникнуть деление на ноль? Например у матрицы [0.5, -1; -1, 0.5] в маткад можно символьно вычислить разложение Холецкого получится [sqrt(2)/2, 0; -sqrt(2), sqrt(6)*i/2], а при попытке численного вычислить холецкого той же матрицы возникнет сообщение об ошибке.

[ewert]

Suvorov.as в сообщении #544811 писал(а):

можно символьно вычислить разложение Холецкого получится [sqrt(2)/2, 0; -sqrt(2), sqrt(6)*i/2],

Не вижу Холецкого.

[Suvorov.as]

В смысле?

-- 03.03.2012, 15:17 --

Вы хотите сказать, что [sqrt(2)/2, 0; -sqrt(2), sqrt(6)*i/2]*[sqrt(2)/2, -sqrt(2); 0, sqrt(6)*i/2] не равно [0.5, -1; -1, 0.5]?

[ewert]

Suvorov.as в сообщении #544818 писал(а):

Вы хотите сказать, что [sqrt(2)/2, 0; -sqrt(2), sqrt(6)*i/2]*[sqrt(2)/2, -sqrt(2); 0, sqrt(6)*i/2] не равно [0.5, -1; -1, 0.5]?

Я хочу сказать, что, во-первых, читать Вас совершенно невозможно. Используйте ТеХ, например: $\begin{pmatrix} 1 & 2 \\ \sqrt{3} & 4 \end{pmatrix}$

$\begin{pmatrix} 1 & 2 \\ \sqrt{3} & 4 \end{pmatrix}$

А то и до Карантина недалеко.

Во-вторых: ну допустим и равно; только при чём тут Холецкий-то?... Это -- просто $LU$-разложение. А метод Холецкого -- это "метод квадратного корня", т.е. конкретно $L\,L^*$-разложение. У вас же вторая матрица не является сопряжённой к первой; естественно -- она и не может являться, т.к. собственные числа разных знаков.

[Suvorov.as]

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

[Евгений Машеров]

Вопрос распадается на два подвопроса: почему Холецкий не считается для матрицы, не являющейся неотрицательно определённой, и почему Холецкий не считается для неотрицательно определённой, но не положительно определённой матрицы.
1. Потому, что это "метод квадратного корня". Если у матрицы отрицательные с.ч. - то действительного квадратного корня нет. Это факт "чистой математики".
2. Потому, что в вычислительной математике нулей не бывает. Бывают малые числа, и там, где должен быть ноль, сидит какое-нибудь $10^{-17}$, причём знак выбран случайно. Можно доработать алгоритм, и там, где вычисляется корень, проверять в случае малого отрицательного подкоренного и вместо корня принудительно ставить 0. Можно заранее прибавить к диагонали малую константу. Но для выбора порога в первом случае и константы во втором надо что-то знать о сути решаемой задачи. Поэтому в программах, выкладываемых на общее пользование, такого не делают, а просто оговаривают положительную определённость входной матрицы.

[Suvorov.as]

Спасибо. Те матрицы с которыми я работаю не относятся ко второму подвопросу.

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

[g______d]

Потому что в большинстве приложений изначально нужна не $LL^T$, а $LL^*$. В случае вещественных матриц $L^*=L^T$. Если мы допускаем комплексные элементы, то и транспонирование придется заменить на сопряжение.

Я знаю несколько ситуаций, где в комплексном случае нужно именно транспонирование, а не сопряжение, но все они мне кажутся довольно экзотическими.

[Suvorov.as]

Моя область - численное решение задач шумоизлучения подводных аппаратов. При этом конечно-элементные матрицы описывающие данные акустические процессы являются разреженными, комплексными (из-за наличия демпфирования и потерь на излучение звука), симметричными (именно симметричными, а не сопряженными). При этом все решатели почему-то используют LU преобразование, хотя можно было бы сделать LLt (на худой конец LDLt) и сократить память в два раза.

[g______d]

Возможно, я был неправ относительно приложений.

По поводу корня может помочь следующий комментарий. Сначала тривиальная вещь: есть естественное однозначное понятие корня из положительного числа, а из отрицательного или комплексного --- нет, т. к. есть неоднозначность в выборе ветви (разумеется, для положительного числа тоже можно выбирать знак, но положительный явно выделен по сравнению с отрицательным).

Теперь про матрицы. Из неотрицательной матрицы (т. е. самосопряженной с неотрицательными собственными числами) есть естественно определенный квадратный корень (это единственная неотрицательная матрица, дающая в квадрате исходную). Если у нас появляются отрицательные собственные числа или матрица перестает быть самосопряженной, то выделенного определения уже нет.

-- 03.03.2012, 18:34 --

Кажется, выше примерно это и было сказано.

[Suvorov.as]

Согласен, но позволю привести вот такой пример:
Матрица А=[4 1;1 1.25] положительно определенная

Матрица L разложения Холецкого в этом случае будет равна [2 0;0.5 1]

При этом LLt=A

Но, если я запишу
M=[-2 0;-0.5 1], то так же будет выполняться MMt=A.

Как видно матрицы M и L разные но их квадраты дают одинаковый результат. Так о какой же единственности в разложении Холецкого при этом можно говорить? Или я что, то упускаю?

[ewert]

g______d в сообщении #544898 писал(а):

Из неотрицательной матрицы (т. е. самосопряженной с неотрицательными собственными числами) есть естественно определенный квадратный корень (это единственная неотрицательная матрица, дающая в квадрате исходную).

Оно-то конечно. Только это совсем в другом смысле корень. В этом смысле он действительно единственен. А вот в методе Холецкого в вырожденном случае возникает принципиальная неоднозначность типа возникновения уравнений вида $0x=0$. Т.е. гораздо более грубая неоднозначность, чем

Suvorov.as в сообщении #544902 писал(а):

Так о какой же единственности в разложении Холецкого при этом можно говорить?

А её и нет, естественно. Ясно, что разложение $L\,L^T=A$ всегда можно заменить на $\widetilde L\,\widetilde L^T=A$, где $\widetilde L=LD$, где, в свою очередь, $D$ -- диагональная матрица с плюс-минус единичками на диагонали. Но к этому весь произвол и сводится, если матрица строго положительна (в комплексном случае он чуток расширяется, но непринципиально). Поэтому в методе Холецкого по определению диагональные элементы треугольной матрицы берутся положительными -- и тогда разложение единственно.

Suvorov.as в сообщении #544871 писал(а):

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

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

[g______d]

Suvorov.as в сообщении #544902 писал(а):

Или я что, то упускаю?

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

-- 03.03.2012, 21:24 --

ewert в сообщении #544927 писал(а):

А её и нет, естественно. Ясно, что разложение $L\,L^T=A$ всегда можно заменить на $\widetilde L\,\widetilde L^T=A$, где $\widetilde L=LD$, где, в свою очередь, $D$ -- диагональная матрица с плюс-минус единичками на диагонали. Но к этому весь произвол и сводится, если матрица строго положительна (в комплексном случае он чуток расширяется, но непринципиально). Поэтому в методе Холецкого по определению диагональные элементы треугольной матрицы берутся положительными -- и тогда разложение единственно.

Ну вообще-то произвол гораздо больше. В качестве $D$ можно взять любую унитарную (в вещественном случае ортогональную) матрицу. Или что-то еще говорится про треугольность $L$? Во всяком случае, TC приводит пример без треугольности.

-- 03.03.2012, 21:28 --

Не поленился и посмотрел в википедию. Действительно, $L$ нижнетреугольная с положительными диагональными элементами.