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

Системы линейных уравнений

Системы линейных уравнений Ax=b можно поделить на два класса. Первый класс - это системы с квадратной невырожденной матрицей A, имеющие единственное решение. Вторым классом являются системы с прямоугольной матрицей A произвольного размера, возможно вырожденной. Эти системы обычно решаются с минимизацией квадрата невязки. Пакет ALGLIB предлагает подпрограммы для поиска решений обеих проблем.

Содержание

    1 Невырожденные системы: матрица общего вида
    2 Невырожденные системы: симметричная/Эрмитова положительно определенная матрица
    3 Возможно вырожденные системы
    4 Быстродействие
    5 Итеративное улучшение
    6 Manual entries

Невырожденные системы: матрица общего вида

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

Подпрограммы могут быть поделены на следующие группы:

Последнее нуждается в уточнении:

Невырожденные системы: симметричная/Эрмитова положительно определенная матрица

Для решения систем с симметричной/Эрмитовой положительно определенной матрицей общего вида могут быть использованы следующие подпрограммы:

Соглашения об именах те же, что и в предыдущем разделе. Однако следует отметить, что подпрограммы этого раздела не поддерживают итеративное улучшение.

Возможно вырожденные системы

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

rmatrixsolvels solves systems with rectangular possibly degenerate matrix. Is system matrix is rank deficient, solution in a least squares sense is searched for. Subroutine supports iterative refinement. Current version of ALGLIB doesn't include complex version of this subroutine or version which accept multiple right-hand parts.

Быстродействие

На быстродействие линейного солвера влияет несколько факторов:

Итеративное улучшение

Итеративное улучшение - это метод, позволяющий улучшить качество решения системы линейных уравнений, имея одновременно матрицу системы A и её треугольную факторизацию. После того, как система решена и получено решение x, мы вычисляем остаток r=b-Ax и используем его для уточнения решения: Ad=r, x=x+d Операция может повторяться несколько раз. В пакете ALGLIB используется двухпроходное улучшение.

Замечание #1
Итеративное улучшение позволяет уменьшить ошибки, возникающие из-за округления, и сделать решение настолько точным, насколько это позволяет обусловленность матрицы A. Однако качество полученного результата зависит от того, с какой точностью вычисляется b-Ax. Для того, чтобы итеративное улучшение оказалось стоящим усилий, требуется вычислять эту разность с существенно более высокой точностью, чем используемая при решении системы. В пакете ALGLIB для итеративного улучшения используется переносимый матричный мультипликатор, позволяющий вычислять b-Ax с максимальной точностью, имеющей смысл при наличии в A и b ошибок величиной не более 1 ulp. "Переносимый" в данном контексте обозначает, что он не использует специфичных для той или иной архитектуры расширений (например, 80-битных расширений в архитектуре Intel) и не содержит низкоуровневых ассемблерных вставок.

Manual entries

C++ densesolver subpackage   
C# densesolver 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.