1.4 Матрица плоских  вращений

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

                                                                         (1.5)

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

                                           (1.6)

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

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

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

 

2 ОПИСАНИЕ МЕТОДА  ВРАЩЕНИЙ ЯКОБИ

    2.1 Идея метода вращений

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

                                            

                                                (1.8)

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

    2.2 Необходимые формулы

    Определив идею метода вращений, рассмотрим теперь его несколько подробней.

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

    Очевидно, что равенство (1.7), записанное для матриц A, B, , будет верным и для их подматриц , , . Пользуясь этим, подсчитаем элементы матрицы , выполняя умножение в правой части двумерного аналога (1.7): .

    Отсюда  видим, что  , если , т.е. если .

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

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

    2.3 Алгоритм для одного  шага метода вращений  Якоби

    Проделав  соответствующие элементарные выкладки и возвратившись к n-мерному случаю, запишем теперь совокупность формул, определяющую один шаг метода вращений Якоби. Для того, чтобы не перегружать эти формулы лишними индексами, будем считать что преобразуется матрица A в матрицу B согласно (1.7), хотя на самом деле на k-м шаге должно применятся преобразование (1.8) к матрице с результатом .

    Итак, пусть  - ключевой элемент преобразуемой матрицы А. Матрица В, подобная А, формируется следующим образом:

1. Вычисляют .
2. Если , то ( если , то лучше ), если же q=0, то .
3. Вычисляют новые диагональные элементы: .
4. Полагают (или для контроля вычисляют ).
5. При m=1,2,…,n таких, что , вычисляют изменяющиеся внедиагональные элементы: .                   (1.9)
6. Для всех остальных пар индексов m,l принимают .

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

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

    2.4 Доказательство сходимости

    Для доказательства сходимости последовательности к используем норму Фробениуса .

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

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

    Аналогичные суммы квадратов j-й строки и i-го столбца, в силу симметрии, дадут такое же выражение. Это означает, что если полученное равенство удвоить и дополнить левую и правую части суммой квадратов всех остальных внедиагональных элементов матрицы A (служащих соответствующими элементами матрицы B), то в левой части будет стоять сумма квадратов всех внедиагональных элементов матрицы A, кроме , . Следовательно, справедливо равенство

                                  

 ,                       (1.10)

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

    2.5 Быстрота сходимости

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

3 ПРИМЕР, РЕШЕНИЕ,  АНАЛИЗ

    3.1 Условие примера

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

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

    3.2 Ход решения

     Этап 1-й. Выбираем ключевой элемент (максимальный в условленной части матрицы), следовательно, фиксируем индексы i=3, j=1. Вычисляем . Далее находим элементы новой матрицы   ,

и при  m=2   .

Следовательно, ~ .

    Этап 2-й. Полученную на предыдущем этапе матрицу B считаем матрицей A, т.е. будем считать по тем же формулам, положив A:=B. Ключевой элемент здесь , т.е. i=3, j=2. Согласно алгоритму, имеем: (замечаем, что pq<0), Зная числа s и c, определяющие преобразования вращения, вычисляем   и далее при m=1 Таким образом, уже после второго этапа (это не норма, а, будем считать, везение) получена диагональная матрица , подобная исходной матрице A, в силу чего можно утверждать, что собственными значениями матрицы A являются числа

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

    3.3 Анализ

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

ЗАКЛЮЧЕНИЕ

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

БИБЛИОГРАФИЧЕСКИЙ СПИСОК

1. Вержбицкий В.М. Основы численных методов. – М.: Высшая школа, 2002.
2. Воеводин В.В. Вычислительные основы линейной алгебры. – М.: Наука, 1977.
3. Парлетт Б. Симметричная проблема собственных значений. – М.: Мир, 1983.
4. Уилкинсон Дж.Х. Алгебраическая проблема собственных значений. – М.: Наука, 1970
5. Бут Э.Д. Численные методы. – М.: Физматгиз, 1959.
6. Волков Б.А. Численные методы. – М.: Наука, 1979
7. Бахвалов Н.С., Жидков Н.П., Кобельков Г.М. Численные методы. – М.: Наука, 1987.
8. Демидович Б.П., Марон И.А. Основы вычислительной математики. – М.: Наука, 1970.
9. Марчук Г.И. Методы вычислительной математики. – М.: Наука, 1977.
10. Самарский А.А. Введение в численные методы. – М.: Наука, 1987