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

Собственные числа и собственные векторы матрицы общего вида

Несимметричная задача собственных значений имеет две разные постановки: поиск таких векторов x, что Ax = λx, и поиск таких векторов y, что y HA = λy H (здесь y H обозначает комплексно-сопряженное транспонирование y). Вектор x называется правым собственным вектором, а вектор y - левым собственным вектором, соответствующим собственному значению λ (одинаковому для обоих собственных векторов).

В отличие от симметричной задачи, собственные векторы несимметричной матрицы не образуют ортогональную систему. Более того, собственные векторы могут даже не образовать линейно-независимой системы векторов (такое возможно, хотя и не обязательно, если у матрицы есть кратные собственные значения - значению кратности k может соответствовать собственное подпространство размерности меньшей, чем k).

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

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

Описание алгоритма

Решение несимметричной задачи собственных значений осуществляется в несколько этапов. На первом этапе матрица приводится ортогональным преобразованием к верхней форме Хессенберга. На втором этапе, занимающем больше всего времени, матрица приводится ортогональным преобразованием к верхней форме Шура. Если требуются только собственные значения, то этого достаточно, т.к. собственные числа матрицы располагаются в диагональных блоках квазитреугольной матрицы из каконической формы Шура. Если же требуются собственные векторы, то они могут быть получены по векторам Шура и квазитреугольной матрице путем обратной подстановки (фактически - решения системы линейных уравнений; сам процесс обратной подстановки занимает незначительную часть времени работы алгоритма, но необходимость накапливать проводимые над матрицей преобразования для применения их к собственным векторам замедляет алгоритм более чем в два раза).

Разложение Шура, на которое тратится больше всего времени, осуществляется с использованием QR-алгоритма с множественными сдвигами, взятого из пакета LAPACK 3.0. Этот алгоритм является блочно-матричным аналогом обычного QR-алгоритма с двойным сдвигом. Следует отметить, что как и все блочно-матричные алгоритмы, он требует настройки для достижения оптимального быстродействия.

Настройке подвергается величина NS - внутренний параметр подпрограммы InternalSchurDecomposition, определяющий число сдвигов за одну итерацию алгоритма. С ростом числа сдвигов быстродействие алгоритма растет, достигая максимума при NS находящемся между 4 и 16, после чего быстродействие заметно падает. На разных системах границы этого интервала могут различаться, однако в целом тенденция одна и та же. По умолчанию NS установлено в значение, которое достаточно хорошо на большинстве систем, однако если важен даже небольшой прирост быстродействия, имеет смысл провести ручную калибровку этого параметра. Следует отметить, что оптимальное значение параметра зависит как от характеристик системы, так и от свойств обрабатываемых алгоритмом матриц.

Описание модуля

Подпрограмма RMatrixEVD позволяет получить собственные числа и, опционально, собственные векторы (правые и/или левые) матрицы общего вида. На входе подпрограмма получает матрицу A, на выход возвращает массив собственных чисел (вещественные и мнимые части) и массив собственных векторов (структура массива подпробно описана в комментариях к подпрограмме).

Manual entries

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