П 4.3 QR-алгоритм для нахождения собственных значений матрицы

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

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

Процедура QR-разложения, рассмотренная в П 2.2, многократно используется в R-алгоритме вычисления собственных значений.

Осуществляя поочередно факторизацию и перестановку сомножителей, получаем последовательность матриц [20]

, , , (1)

где - ортогональная матрица, - верхняя треугольная матрица, .

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

Из равенства (1) получаем , отсюда . Получаем, что все матрицы подобны между собой и подобны исходной матрице А.

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

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

При этом соответствующее собственное значение принимается равным диагональному элементу данного столбца.

Каждой комплексно-сопряженной паре соответствует диагональный блок размерностью 2х2. Принципиально то, что элементы этих блоков изменяются от итерации к итерации без видимой закономерности, в то время как комплексно-сопряженные собственные значения, определяемые каждым блоком, имеют тенденцию к сходимости. Это обстоятельство необходимо учитывать при формировании критерия выхода из итерационного процесса. Если в ходе итераций прослеживается комплексно-сопряженная пара собственных значений, соответствующая блоку, образуемому элементами j -го и j+1 -го столбцов, то, несмотря на значительное изменение в ходе итераций самих этих элементов, собственные значения, соответствующие данному блоку и определяемые из решения квадратного уравнения

,

начиная с некоторого k отличаются незначительно.

Для практического QR-алгоритма нет завершенной теории сходимости. На практике алгоритм работает всегда или почти всегда [5].

Пример 1. Используя QR-алгоритм, найти собственные значения матрицы с точностью .

Решение:

Выберем вектор согласно формуле (5), рассмотренной
в П 2.2:

,

где , .

Тогда .

Построим матрицу согласно формуле (6), рассмотренной
в П 2.2:

,

.

Выберем вектор :

,

где , .

Тогда .

Построим матрицу по формуле (6) из П 2.2:

,

.

Построим матрицу Q согласно формуле (8), описанной в П 2.2:

,

.

Убедимся, что матрица Q – ортогональна.

.

Построим верхнюю треугольную матрицу R по формуле (7)
из П 2.2:

,

.

После первой итерации матрица А вычисляется по формуле и имеет вид:

.

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

Продолжая итерационный процесс, получим соответственно на 6-й и 7-й итерациях следующие матрицы:

,

.

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

.

Таким образом, окончательное решение задачи можно записать в виде: , , .

Поиск по сайту: