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

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

Вещественное число λ и вектор z называются собственной парой матрицы A, если они удовлетворяют следующему условию: Az = λz. При этом для вещественной матрицы A может быть поставлена задача поиска только собственных чисел, или как собственных чисел, так и векторов.

В случае, если вещественная матрица A размером NxN симметрична, у неё есть N собственных чисел (не обязательно различных) и N соответствующих им собственных векторов, образующих ортонормированный собственный базис (в общем случае собственные векторы не ортогональны, причем их может быть и меньше, чем N).

Обзор существующих алгоритмов решения задачи собственных значений

Первым алгоритмом, решающим задачу собственных значений для симметричной матрицы размером NxN, был алгоритм Якоби, приводящий матрицу к диагональной форме ортогональными преобразованиями. По мере осуществления преобразований исходной матрицы, элементы за пределами главной диагонали уменьшались, а на главной диагонали - увеличивались. Естественным результатом этого процесса является матрица, у которой внедиагональные элементы равны нолю, а на диагонали находятся собственные значения.

Алгоритм Якоби прост в реализации, но неэффективен, поскольку осуществляет операции над полной матрицей A, даже тогда, когда большинство её элементов сошлись к нолю. Практически все последующие алгоритмы решения симметричной задачи собственных значений предварительно приводят матрицу к трехдиагональной форме (эта операция осуществляется неитеративным алгоритмом за конечное число шагов) и в дальнейшем работают уже с трехдиагональной матрицей.

Наиболее распространенным на данный момент является семейство алгоритмов, основанных на QL/QR-итерации, применяемой к трехдиагональной матрице. В рамках данного семейства можно выделить алгоритм из LINPACK, реализующий простейший QL-вариант (различные подпрограммы, родственные этому алгоритму, можно найти в ряде источников), и более современную версию из LAPACK (подпрограмма xSTEQR), которая использует неявные сдвиги и может переключаться между QL и QR вариантами итерации в зависимости от того, какой из них быстрее и точнее диагонализирует переданную матрицу. Алгоритм из LAPACK несколько объемнее, но является более надежным и точным, и лег в основу исходного кода, доступного на этой странице.

Также библиотека LAPACK предлагает несколько других алгоритмов для поиска собственных пар трехдиагональной симметричной матрицы, из которых следует особо выделить алгоритм "разделяй и властвуй" и RRR-алгоритм, которые позволяют значительно ускорить поиск собственных пар большой трехдиагональной симметричной матрицы. Для трехдиагональной матрицы ускорение может достигать нескольких десятков раз, для симметричной матрицы (более частый случай) с учетом затрат на приведение к трехдиагональной форме степень ускорения снижается до более скромных двух-четырех раз, но и такое ускорение не будет лишним. Однако, из-за высокой сложности эти алгоритмы пока не вошли в состав ALGLIB. Если скорость нахождения собственных пар больших симметричных матриц критична, то имеет смысл обратиться к LAPACK.

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

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

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

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

Этот алгоритм использует программы из библиотеки LAPACK 3.0

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.