Устранение комплексно сопряженных сдвигов

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

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

Уравнение (41.4) означает, что такая вещественная матрица, что

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

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

Из (41.5) имеем

и, следовательно, ортогональная матрица, которая приводит к верхней треугольной матрице. По методу Гивенса для приведения к треугольному виду определяется в виде произведения плоских вращений Следовательно,

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

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

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

где В — верхняя матрица Хессенберга. Матрица может быть определена при помощи процессов Гивенса или Хаусхолдера. Следовательно,

и если мы обозначим то из (41.14) имеем

Так как первая строка равна то первая строка совпадает с первой строкой которая, как было показано, совпадает с первой

строкой Следовательно, В должна быть равна которая получилась бы при выполнении двух шагов QR со сдвигами Мы получили метод определения А без использования комплексной арифметики даже в случае, когда комплексные.

42. Как мы сейчас покажем, этот способ очень эффективен. Число умножений при вычислении вращений не зависит от После того как они получены, по (41.12) вычисляется и снова число умножений не зависит от . В случае имеет вид

Аннулирование элемента, обозначенного нулем, не дает никаких преимуществ. Матрица уже не будет в форме Хессенберга, так как при умножении слева и справа появились в столбцах 1 и 2 отличные от нуля элементы. Рассмотрим теперь подобное преобразование к форме Хессенберга методом Гивенса. Так как почти в форме Хессенберга, то объем работы значительно меньше, чем если бы была полной матрицей.

Как и в общем случае (гл. 6, § 2), здесь всего основных шага, причем на шаге аннулируются элементы в столбце. Мы сейчас видим, что перед началом шага имеет форму Хессенберга, за исключением ненулевых элементов в позициях . Элемент равен нулю, но это не дает никаких преимуществ. Это иллюстрируется в случае в (42.1). Предполагая, что на шаге мы имеем такую конфигурацию, умножаем слева на вращения в плоскостях так, чтобы аннулировать два подчеркнутых элемента в (42.1). Умножение слева уничтожит нуль в позиции но больше не будет введено никаких новых ненулевых элементов. Затем умножаем справа на транспонированные матрицы вращений. В результате столбцы заменятся их линейными комбинациями, аналогично столбцы их линейными комбинациями. В (42.1) мы отметили стрелками строки и столбцы которые изменяются на шаге. Очевидно, что форма точно аналогична форме

Мы описали предварительное преобразование А к так, как будто оно отлично от преобразования, которое требуется для приведения

Но, если мы припишем к еще один столбец, состоящий из элементов как показано в (42.2)

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