LDLT разложение

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

При LDLT-разложении матрица A представляется в виде A = L·D·L ^T или A = U·D·U ^T. Отличий от разложения Холецкого два. Во-первых, появилась матрица D - блочно-диагональная матрица с блоками размером 1x1 или 2x2. Во-вторых, матрицы L и U являются не треугольными матрицами, а произведениями треугольных матриц и матриц перестановок:

Здесь v - столбец, ширина s которого равна ширине k-ого блока на диагонали матрицы D (1 или 2), а высота - k-s для матрицы U_k , n-k-s+1 - для матрицы L_k .

Можно видеть, что структура LDLT-разложения значительно сложнее, чем у разложения Холецкого или LU-разложения, но это разложение позволяет факторизовать любую симметричную матрицу (в отличие от разложения Холецкого), и выполняется быстрее, чем более общее LU-разложение. Следует отметить, что LDLT-разложение по скорости находится между разложением Холецкого и LU-разложением, так что если есть возможность применить разложение Холецкого, то оно все же является предпочтительным вариантом.

Описание подпрограммы

Разложение матрицы осуществляется подпрограммой SMatrixLDLT, которая принимает матрицу A, заданную верхним или нижним треугольником, и замещает её матрицами L и D (или U и D), хранящимися в компактной форме (описанной в комментариях к программе).

Алгоритмы обращения матриц и решения систем линейных уравнений работают с матрицами, заданными именно в компактной форме, а сами по себе матрицы L или U обычно не представляют интереса, так что подпрограмм для их "распаковки" не предусмотрено. Подробное описание структуры матриц L и U есть в комментариях к подпрограммам, так что в случае необходимости программист может самостоятельно произвести "распаковку" матриц.

Этот алгоритм перенесен из библиотеки LAPACK.

Manual entries

This article is intended for personal use only.

Скачать ALGLIB