Метод Гивенса

22. Метод Якоби по существу носит итерационный характер. Следующие два метода, которые мы опишем, предназначены для приведения исходной матрицы к более простому виду и дают с помощью ортогональных подобных преобразований симметричную трехдиагональную матрицу (гл. 3, § 13). Такое приведение может быть выполнено неитерационными методами и, следовательно, оно требует намного меньше вычислений. Так как собственные значения симметричной трехдиагональной матрицы определяются сравнительно просто, эти методы весьма эффективны.

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

21

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

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

Для каждого значения от до выполняем шаги от (i) до (iv):

(i) Вычисляем .

(ii) Вычисляем (Если то берем и можем опустить (iii) и (iv).) Записываем на

место на место на место причем х в этих позициях есть правильное новое значение элементов.

(iii) Для каждого значения от до вычисляем и записываем их соответственно на место

(iv) Для каждого значения от до вычисляем записываем их соответственно на место

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

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