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

Получение собственных чисел и векторов симметричной вещественной матрицы с использованием бисекции и обратной итерации

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

Для вещественной матрицы A может быть поставлена как задача поиска всех собственных чисел и векторов (называемых спектром матрицы A), так и задача поиска не всего спектра, а лишь его части. В последнем случае можно использовать метод бисекции, позволяющий найти собственные числа, лежащие в указанном интервале (или собственные числа с указанными номерами), после чего при помощи метода обратной итерации получить по собственным числам соответствующие им собственные векторы. Если ищется только малая часть полного спектра матрицы, то достигается значительная экономия скорости по сравнению с QL/QR алгоритмом.

Как и в случае QL/QR алгоритма, сначала симметричная матрица приводится к трехдиагональной форме, после чего вызываются методы бисекции и обратной итерации, работающие с трехдиагональной матрицей.

Сходимость и точность

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

Следует понимать, что подобные трудности являются типичными для всех методов поиска собственных чисел, и удовлетворительное решение этой проблемы до сих пор не найдено. Тем не менее, в большинстве реальных задач этот метод успешно применим. Если же алгоритм столкнулся с вычислительной проблемой, которая ему не по силам, это обычно не остается незамеченным, и вычислительная подпрограмма возвращает False. В этом случае имеет смысл применить QR/QL-алгоритм, который характеризуется несколько более высокой устойчивостью, чем метод обратной итерации, и самостоятельно выбрать нужные векторы из найденного полного набора (разумеется, при этом затраты времени будут больше, но вы получите свое решение).

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

Для поиска собственных чисел (и соответствующих векторов), лежащих в указанном полуинтервале (A, B] можно использовать подпрограмму SMatrixEVDR. Подпрограмма SMatrixEVDI позволяет найти собственные пары с указанными порядковыми номерами (при этом спектр упорядочен в порядке возрастания собственных чисел).

Следует отметить, что алгоритм эффективен только при поиске малой части собственных пар. Если требуется найти все собственные числа (или значительное их число), то более эффективен именно QL/QR алгоритм.

Также следует отметить, что указанные алгоритмы являются не самостоятельными вычислительными подпрограммами, а всего лишь "обертками" вокруг внутренних подпрограмм InternalBisectionEigenValues и InternalDSTEIN, реализующих алгоритмы бисекции и обратной итерации. Внутренние подпрограммы характеризуются менее дружественным к программисту интерфейсом, однако в некоторых ситуациях может потребоваться работать с ними напрямую.

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

Этот алгоритм перенесен из библиотеки LAPACK.

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.