§ 2. Эрмитовы матрицы

1. Метод отражения.

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

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

Рис. 31.

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

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

Это преобразование вектора можно записать в канонической форме умножения на матрицу отражения

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

Заметим, что равенства (24)-(25) в координатной форме записываются следующим образом:

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

Возведем матрицу отражения в квадрат:

Преобразуем последний член правой части, используя ассоциативность умножения матриц и условие нормировки (23):

Тогда последний член сократится с предпоследним, и мы получим

т. е. матрица отражения равна своей обратной. А сравнивая (27) и (28), убедимся, что , так что матрица отражений унитарна.

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

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

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

Покажем, что для произвольной матрицы А можно подобрать такую конечную последовательность отражений, которая приводит матрицу к верхней почти треугольной форме. Для этого очередное отражение должно уничтожать самый длинный ненулевой столбец в нижней части матрицы А. Действие первых двух отражений показано на рис. 32, где жирными точками обозначены ненулевые элементы матрицы, а кружками — нулевые; третье отражение обращает в нуль обведенные элементы третьего столбца.

Будем считать, что уже уничтожен столбец, и разобьем матрицу А на клетки, как показано на рис. .32. Квадратная клетка есть верхняя почти треугольная матрица, а в прямоугольной клетке только последний столбец отличен от нуля.

Сделаем отражение при помощи вектора , у которого первые q компонент нулевые:

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

Рис. 32.

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

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

где

остальные же элементы этой клетки равны нулю.

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

(33)

и найти, чему равна постоянная а. Заметим, что умножение вектора w на множитель не меняет матрицы отражения; тогда из (32) следует, что а также определена только с точностью до этого множителя. Его всегда можно выбрать так, чтобы а была вещественной положительной, что будем предполагать выполненным.

Из (31) следует, что

(34)

Подставляя (33)-(34) в условие нормировки (23), получим

Подстановка тех же выражений в формулу (32) дает

Последнее слагаемое в правой части этого равенства должно быть вещественным, поскольку остальные члены вещественны. Поэтому должно выполняться соотношение где k — любое целое число. Для улучшения счетной устойчивости алгоритма выгодно полагать : тогда последний член в правой части (36) будет положительным, и величина, а никогда не станет близкой к нулю. Таким образом,

Учитывая этот выбор аргумента и приравнивая друг другу правые части равенств (35) и (36), получим

Заменяя в (36) сумму при помощи равенства (38) и учитывая (37), упростим выражение для а:

Формулы (37)-(39) и (33)-(34) полностью определяют матрицу очередного отражения. Эти формулы составлены так, что для вещественной матрицы А при вычислениях не возникает комплексных величин, а формула (37) для вычисления аргумента принимает при этом вид

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

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

Основное число действий уходит на перемножение матричных клеток в формуле (30). Заметим, что клетка не меняется, а в клетке имеется только один ненулевой элемент уже вычисленный при нахождении матрицы отражения; следовательно, эти клетки не нужно специально вычислять. При нахождении остальных двух клеток умножение на матрицу отражения W надо выполнять специальным образом; например, умножим на W справа, тогда

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

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

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

Вычисления по этой формуле также надо делать экономично, выполняя каждое умножение на очередную матрицу как два умножения на вектор по формуле (24).

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

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

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