nabbla (nabbla1) wrote,
nabbla
nabbla1

Category:

LDLT-разложение: особая индийская магия!

Мы изложили "стандартный" подход к обращению симметричной положительно определённой матрицы через LDLT-разложение с последующим обращением матриц L и D, и получением итогового результата как результат умножения 3 матриц.

В итоге количество умножений получилось порядка 2/3N3, что конечно получше, чем N3 в алгоритме обращения матрицы "общего вида", но не настолько лучше, как хотелось бы. Казалось, что когда у тебя вдвое меньше "уникальных" элементов как на входе, так и на выходе, то и количество операций должно упасть почти вдвое. Но всё-таки "окольные пути" взяли своё.

Но не так давно (в 2011 году с правками в 2013) два индийских математика опубликовали статью, в которой заявили, что их метод позволяет обратить такую матрицу всего за 1/2N3 умножений, что на 1/6 лучше существующих методов. Что ещё интереснее, они проверяли работу "с фиксированной точкой" и получили, что такой метод даёт чуть меньше ошибок вычислений (так я на эту статью и вышел - искал подсказки, как это всё получше выполнить без FPU). Я, конечно, не удивлюсь, если всё это уже было у Гаусса, но пока не слышал о таком :)

Сейчас попытаюсь объяснить, что же там происходит...


Первый этап всё тот же самый, сделать LDLT-разложение:



Дальше, мы хотим решить уравнение


относительно неизвестной матрицы X. (E - это единичная матрица)

Подставляем наше разложение:



Умножаем обе части слева на L-1:



И ещё умножим обе части слева на D-1:



Это и есть то выражение, из которого мы хотим найти матрицу X, то бишь, обратную матрицу!

Кажется, что в этом нет никакого смысла: нам по-прежнему надо обращать матрицу L, а когда мы её обратим - то почему бы не посчитать X напрямую!?

В этом и состоит великая индийская хитрость. Изобразим это уравнение поэлементно:



Помножим матрицы в правой части, причём на нижнем треугольнике поставим прочерки - как оказывается, он нам не нужен!



Начинаем решать эту штуку, начиная с правого столбца:



Решаем это прямой подстановкой, снизу вверх:





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



Как будто бы значение x43 найти не удастся, а без него "посыпется" и всё остальное... Да вот только мы же знаем, что наша матрица симметричная, поэтому x43 = x34, а его мы уже нашли в прошлый раз! А зная его, можно выразить и все остальные:





"Для закрепления пройденного", выпишем следующий по счёту столбец, второй:



Теперь мы "не знаем" уже двух переменных: x42 и x32. А в действительности нашли уже обе: x42=x24 и x32=x23. Выразим оставшиеся две:




И наконец, берёмся за первый столбец:



Три нижних значения нам уже известны, это x12, x13 и x14, найденные ранее. Осталось выразить самую последнюю неизвестную:



На этом работа завершена.

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

В итоге, количество умножений на этом шаге составляет порядка N3/3, что прибавляясь к нашим исходным (на этапе LDLT - разложения) N3/6, и даёт заявленное значение N3/2.

Шикарный метод, как по мне!
Tags: tex, математика, программки, работа
Subscribe

  • Ремонт лыжных мостиков

    Вернулся с сегодняшнего субботника. Очень продуктивно: отремонтировали все ТРИ мостика! Правда, для этого надо было разделиться, благо народу…

  • Гетто-байк

    В субботу во время Великой Октябрьской резни бензопилой умудрился петуха сломать в велосипеде. По счастью, уже на следующий день удалось купить…

  • А всё-таки есть польза от ковариаций

    Вчера опробовал "сценарий", когда варьируем дальность от 1 метра до 11 метров. Получилось, что грамотное усреднение - это взять с огромными весами…

  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    default userpic

    Your IP address will be recorded 

  • 7 comments