2. Метод вращений Якоби решения симметричной полной проблемы собственных значений

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

, (1.4)

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

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

(1.5)

Она получается из единичной матрицы заменой двух единиц и двух нулей на пересечениях i-x и j-x строк и столбцов числами с и , как показано в (1.5), такими, что

1. . (1.6)

Условие нормировки (1.6) позволяет интерпретировать числа c и s как косинус и синус некоторого угла , и, так как умножение любой матрицы на матрицу изменяет у нее только две строки и два столбца по формулам поворота на угол в плоскости, отделяемой выбранной парой индексов i и j, то это объясняет название матрицы .

Матрица ортогональна при любых , и значит, матрица

(1.7)

подобна А, т.е. имеет тот же набор собственных чисел, что и матрица А.

Классический итерационный метод вращений, предложенный Якоби (1846 г.), предполагает построение последовательности матриц

с помощью преобразований типа (1.7)

(1.8)

такой, что на -м шаге обнуляется максимальный по модулю элемент матрицы предыдущего шага (а значит, и симметричный ему элемент). Эта стратегия определяет способ фиксирования пары индексов i, j, задающих позиции , , , «существенных» элементов в матрице вращения , и угол поворота , конкретизирующий значения этих элементов: . _. и . На каждом шаге таких преобразований пересчитываются только две строки (или два столбца, что неважно в силу симметрии) матрицы предыдущего шага.

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

, ,

а через – такую же подматрицу матрицы :

.

Очевидно, что равенство (1.7), записанное для матриц А, В, , будет верным и для их подматриц , , . Рассчитаем с его помощью элементы матрицы :

.

Очевидно, что , если т.е. если

.

Учитывая тригонометрическую интерпретацию чисел и , в соответствии с чем можно считать

, ,

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

.

(для определенности считают ).

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

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

Пользуясь проделанными рассуждениями, запишем последовательность действий, определяющих один шаг метода вращений Якоби (каждый шаг состоит в расчёте матрицы на основе при помощи соотношения (1.8)):

1. Выбирается ключевой элемент матрицы (стратегия его выбора рассматривается ниже).

2. Вычисляется , , .

3. Вычисляются значения и : Если то , , (если то лучше ), если же q=0, то .

4. Вычисляются новые диагональные элементы матрицы :

5. Внедиагональные элементы и полагаются равными 0 (для контроля точности их значения можно вычислить по формуле: );

6. При таких, что , вычисляются изменяющиеся внедиагональные элементы:

7. Для всех остальных пар индексов принимается .

Вернёмся теперь к стратегии выбора ключевого элемента . На практике наиболее распространены два подхода:

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

.

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

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

В завершение, остается вспомнить, что в соответствии со свойствами 6, 7 из предыдущего раздела и проведенными рассуждениями за собственные векторы , , …, матрицы А (имеющие единичную евклидову норму) могут быть приближенно приняты столбцы результирующей матрицы, получающейся справа от А в цепочке преобразований подобия:

т.е. матрицы при некотором .

Критерием окончания процесса вращений Якоби может служить, например, достаточная малость модуля ключевого элемента на -ом шаге: , где – некоторое малое число, определяющее допустимую погрешность вычислений метода.