Главная       Скачать       Коммерческая поддержка       FAQ       Forum       О нас       Английская версия

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

Содержание

    1 Определение
    2 Применение
    3 Реализация в ALGLIB
    4 Подпрограммы
    5 Manual entries

Определение

Разложение Холецкого, наравне с LU-разложением, является одной из наиболее популярных треугольных факторизаций. Разложение Холецкого симметричной положительно определенной (либо Эрмитовой) матрицы во многом аналогично LU-разложению: матрица A представляется в виде A = LL H (или в виде A = U HU, что по сути одно и то же). Однако можно видеть и отличия: не осуществляется выбор ведущего элемента (и не смотря на это разложение Холецкого устойчиво) и отсутствует матрица перестановок. Также вместо двух матриц L и U мы получаем в результате только одну матрицу, умножаемую на саму себя (из-за чего это разложение иногда называют квадратным корнем матрицы). Оба этих свойства стали возможны за счет положительной определенности и симметричности матрицы. Ещё одним полезным свойством разложения Холецкого является то, что оно требует примерно в два раза меньше операций, чем LU-разложение.

Замечание #1
Фактическое преимущество в скорости может быть ещё выше, т.к. одним из недостатков LU-разложения является необходимость осуществлять перестановки строк, что мешает эффективному использованию кэша процессора.

Применение

Разложение Холецкого главным образом применяется при решении систем линейных уравнений, либо при обращении симметричных/Эрмитовых положительно определенных матриц матриц.

Реализация в ALGLIB

В пакете ALGLIB реализована рекурсивная версия разложения Холецкого, сводящая разложение исходной матрицы к серии разложений матриц меньшего размера. Рекурсия прерывается, когда размер матрицы достигает пороговой величины (маленькая матрица, гарантированно помещающаяся в L1-кэш современных процессоров), после которой происходит переключение на нерекурсивную версию. Использование рекурсии имеет следующие преимущества:

Изложенные выше преимущества позволяют использовать процессор с той эффективностью, с которой это допускают язык/компилятор. Однако следует отметить, что различные языки позволяют достигать различного быстродействия. Что касается алгоритмов линейной алгебры, максимальным быстродействием обладает версия на C++ (и интерфейсы к ней). Версии ALGLIB на других языках в разы уступают ей в быстродействии.

Подпрограммы

Разложение Холецкого вычисляется подпрограммами spdmatrixcholesky и hpdmatrixcholesky, вычисляющими разложения вещественных и комплексных матриц соответственно. С учетом того, что матрица A симметрична, подпрограммы требуют задания не всей матрицы, а только верхней или нижней части. Соответственно, в результате разложения получается либо матрица L, либо матрица U.

Manual entries

C++ trfac subpackage   
C# trfac subpackage   

This article is intended for personal use only.

Скачать ALGLIB

C#

Исходный код на C#

Downloads page

 

C++

Исходный код на C++

Downloads page

 

C++, арифметика высокой точности

Исходный код на C++, использующий библиотеки MPFR/GMP.

Исходный код GMP доступен на сайте gmplib.org. Исходный код MPFR доступен на сайте www.mpfr.org.

Downloads page

 

FreePascal

Исходный код на Free Pascal.

Downloads page

 

Delphi

Исходный код на Delphi.

Downloads page

 

VB.NET

Исходный код на VB.NET.

Downloads page

 

VBA

Исходный код на VBA.

Downloads page

 

Python

Исходный код на Python (CPython и IronPython).

Downloads page

 

 

ALGLIB® - numerical analysis library, 1999-2017.
ALGLIB is registered trademark of the ALGLIB Project.