§ 13. Решение полной проблемы собственных значений при помощи QR-алгоритма

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

Пусть А — произвольная вещественная матрица. Согласно лемме из § 2 ее можно представить в виде , где — ортогональная, а — правая треугольная матрицы. Запишем это равенство в виде

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

Представим исходную матрицу А в виде , где А —правая каноническая форма Жордана, т.е. при собственные значения матрицы равны нулю или 1. Всегда можно подобрать матрицу Q так, чтобы диагональные элементы матрицы были упорядочены в порядке невозрастания модуля

Теорема (без доказательства). Пусть в разложении матрицы А все диагональные миноры матрицы Q не вырождены. Тогда последовательность матриц при сходится по форме к клеточному правому треугольному виду А.

Имеется в виду, что после некоторой перестановки строк и одновременно такой же перестановки столбцов матрицы А будут выполняться соотношения: если или , то .

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

Если требуется найти не только собственные значения матрицы А, но и ее собственные и присоединенные векторы, то в процессе построения последовательности матриц следует запоминать ортогональные матрицы , вычисляемые по рекуррентной формуле .

Задача 1. Доказать, что каждый шаг QR-алгоритма требует арифметических операций.

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

Матрица А называется правой почти треугольной, если при .

Алгоритм преобразования матрицы А в правую почти треугольную матрицу заключается в последовательном построении матриц таких, что первые столбцов матрицы имеют вид первых столбцов правой почти треугольной матрицы, т.е. , если . По элементам столбца матрицы построим матрицу отражения (см. § 2) так, чтобы в матрице элементы были те же, что у матрицы , а элементы были нулевыми. Положим . Умножение справа на матрицу не меняет первых столбцов матрицы В, поэтому матрица является матрицей требуемого вида. После получения правой почти треугольной матрицы применяют QR-алгоритм в его первоначальной форме.

Задача 2. Доказать, что в этом случае каждый шаг -алгоритма требует арифметических операций.

Для еще большего ускорения сходимости применяется вариант -алгоритма со сдвигом. А именно, строится последовательность ортогональных матриц и правых треугольных матриц по рекуррентным формулам

Матрицы подобны матрице за счет введения «сдвигов» удается добиться ускорения сходимости. Вопрос о наиболее целесообразном выборе параметров мы рассматривать не будем.

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

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

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

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

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