§ 3. Неэрмитовы матрицы

1. Метод элементарных преобразований.

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

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

Первый ход. На его шаге для преобразования подобия используется матрица следующего вида:

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

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

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

(58)

Поэтому, чтобы обратить в нуль все элементы клетки кроме углового элемента , надо положить

Последняя формула определяет матрицу искомого элементарного преобразования.

Она существенно проще, чем формулы для нахождения нужной матрицы отражения в п. 2.

Само преобразование (57) очень несложно. Благодаря специальной структуре матрицы N умножение на нее выполняется так же быстро, как умножение на вектор. Например, поэлементно перемножая матрицы, найдем клетку

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

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

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

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

и перестановкой строк делают его ведущим. Тогда будет выполняться неравенство и погрешность практически не будет нарастать.

Формально перестановку двух строк можно записать как умножение слева на матрицу перестановки Р:

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

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

Отсюда видно, что после перестановки строк надо умножить полученную матрицу справа на Р. Поэлементным перемножением легко убедиться, что умножение справа на Р есть просто перестановка соответствующих столбцов матрицы А (перестановка выполняется на ЭВМ быстрее, чем арифметические действия).

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

Важно помнить, что если перемножение этих матриц проводить в строго определенном порядке

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

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

Второй ход. Сначала заметим, что если матрица А была нижней почти треугольной (т. е. при ), то при преобразовании подобия (57) с матрицей N она останется нижней почти треугольной.

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

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

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

Рис. 35.

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

Все формулы второго хода легко получить, применяя описанное выше транспонирование к формулам первого хода. Например, пусть аннулированы первые строк, и надо аннулировать строку. Тогда подбор элементов Аскомого преобразования производится аналогично формуле (59):

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

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

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

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