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

LU-разложение

Содержание

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

Определение

LU-разложение прямоугольной матрицы A размером MxN - это представление матрицы A в виде произведения матрицы перестановок P, нижнетреугольной/нижнеетрапециидальной матрицы L с единичной главной диагональю и верхнетреугольной/ верхнетрапециидальной матрицы U: A = PLU.

Применение

Основными применениями LU разложения являются решение систем линейных уравнений, вычисление обратной матрицы и другие задачи.

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

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

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

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

LU-разложение матрицы вычисляется подпрограммами RMatrixLU и CMatrixLU, вычисляющими разложения вещественных и комплексных матриц соответственно. Результатом работы являются таблица перестановок, сохраненная в массиве P (i-ый элемент массива кодирует перестановку строк с номерами I и P[I]), и матрицы L и U в упакованном виде (замещают матрицу A). Например, в результате вызова подпрограммы для матрицы размером 4x3, мы получим:

A11 A12 A13   =>    U11 U12 U13
A21 A22 A23   =>    L21 U22 U23
A31 A32 A33   =>    L31 L32 U33
A41 A42 A43   =>    L41 L42 L43

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.