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

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

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

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

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

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

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

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

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

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

Для поиска собственных чисел и векторов доступны две подпрограммы: подпрограмма SMatrixTDEVDR позволяет найти собственные числа, лежащие в указанном интервале, и соответствующие им собственные векторы (если требуется), а подпрограмма SMatrixTDEVDI позволяет найти собственные числа с указанными индексами (и соответствующие им собственные векторы).

Следует отметить, что указанные алгоритмы являются не самостоятельными вычислительными подпрограммами, а всего лишь "обертками" вокруг внутренних подпрограмм 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.