Собственные значения и собственные векторы матриц. Часть 1. Теоретические аспекты: Методические указания по дисциплине ''Компьютерные методы современного естествознания''

Министерство образования и науки Российской Федерации Федеральное агентство по образованию Государственное образовательное учреждение высшего профессионального образования «РОСТОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ»

МЕТОДИЧЕСКИЕ УКАЗАНИЯ по дисциплине «Компьютерные методы современного естествознания» для студентов второго курса физического факультета РГУ

«Собственные значения и собственные векторы матриц» Часть 1: Теоретические аспекты

Ростов-на-Дону 2006

Методические указания разработаны на кафедре теоретической и вычислительной физики кандидатом физико-математических наук, доцентом Г. М. Чечиным и ассистентом М. Ю. Зехцером.

Ответственный редактор

д. ф.-м. н., профессор В. П. Саченко.

Компьютерный набор и верстка М. Ю. Зехцера.

Печатается в соответствии с решением кафедры теоретической и вычислительной физики физического факультета РГУ, протокол № 17 от 7 марта 2006 г.

Содержание 1 Введение

4

2 Математическая постановка задачи

5

3 Диагонализация матрицы

8

4 Ортогональные преобразования и матрицы плоских вращений

14

5 Суть метода Якоби

18

6 Алгоритм метода Якоби

20

7 Доказательство сходимости метода Якоби

26

8 Дополнения к методу Якоби

29

9 Понятие о некоторых других методах нахождения СЗ и СВ матриц 31 10 Глоссарий

32

11 Контрольные вопросы и задания для самостоятельной работы студентов 33

3

1

Введение

Задача нахождения собственных значений и собственных векторов матриц (СЗВМ) является одной из основных задач для многих разделов физики. С такой вычислительной проблемой приходится сталкиваться, например, при исследовании собственных колебаний различных механических систем, колебательных и электронных спектров молекул и кристаллов. Совершенно принципиальное значение эта проблема приобрела после создания в тридцатых годах прошлого века квантовой механики, которая стала базовой дисциплиной исследования микромира. Действительно, согласно одному из основных положений квантовой механики, все наблюдаемые величины (т.е. величины, которые могут быть измерены в результате проведения конкретных физических экспериментов) суть собственные значения некоторых бесконечномерных эрмитовых матриц (эрмитовых операторов). А такое понятие, как «диагонализация гамильтониана» (оператора энергии), непосредственным образом связанное с нахождением собственных значений этого оператора, стало обыденным выражением языка современной физики. В настоящих методических указаниях рассматриваются некоторые математические, вычислительные и физические аспекты проблемы нахождения СЗВМ. Фактически, это пособие состоит из двух частей. В первой части даётся весьма подробное и доступное (как это представляется авторам!) изложение метода Якоби. Будучи одним из самых первых1 практических методов диагонализации матриц (в результате его применения находятся как собственные значения, так и собственные векторы исходной матрицы), этот метод не потерял своего значения и в настоящее время. И хотя в распоряжении вычислителя сейчас имеются куда более эффективные алгоритмы, понимание заложенных в методе Якоби идей позволяет начинающему специалисту более ясно и просто понять существо более современных методов нахождения СЗВМ. Во второй части настоящих методических указаний подробно рассматриваются две физические задачи — задача исследования собственных колебаний некоторой модельной молекулы и задача о нахождении уровней энергии квантовой частицы в одномерной потенциальной яме. Авторы осознают, что указанный материал выходит за рамки того объёма знаний, которыми владеют студенты второго курса, и тем не менее, сочли желательным его включение в пособие по следующим причинам. В настоящее время на физическом факультете всё чаще и чаще встречаются случаи, когда отдельные студенты, приходя на 1

Он был создан в 1846 г. Активное практическое его применение началось лишь с 1959 г.

4

второй курс, уже достаточно хорошо владеют основными методами программирования. С такими студентами необходимо работать сугубо индивидуально, не привязываясь к стандартным занятиям в рамках курса КМСЕ, которые предусматривают решение простых вычислительных задач, представляющих известные трудности для менее подготовленных студентов. Сильным студентам целесообразно предлагать задачи с ясно выраженным физическим содержанием, которые могут иметь дальнейшее продолжение, подготавливая их тем самым к решению задач исследовательского характера. Эти задачи являются не просто задачами «повышенной сложности». Они требуют соответствующего расширения физического кругозора студента и, кроме всего прочего, играют пропедевтическую роль. В частности, авторы надеются, что после работы «своими руками» с одномерным стационарным уравнением Шрёдингера у студента возникнут вполне определённые ориентиры для последующего изучения курса квантовой механики, а может быть, и интерес к этой дисциплине. Список литературы, приведённый в конце настоящих методических указаний, включает целый ряд учебников и учебных пособий, которые посвящены не только проблеме нахождения СЗВМ, но и численным методам решения самых разнообразных задач современного естествознания.

2

Математическая постановка задачи

Пусть A есть квадратная n×n матрица, элементы которой aij (i = 1..n, j = 1..n) являются действительными числами. Тогда задача нахождения собственных значений и собственных векторов матриц сводится к решению уравнения A~x = λ~x

(1)

относительно компонент неизвестного вектора ~x = (x1 , . . . , xn ) и неизвестной скалярной величины λ. Если найдено некоторое решение системы (1), то вектор ~x называется собственным вектором матрицы A, а λ — соответствующим ему её собственным значением2 . В трёхмерном случае (n = 3) мы можем расписать матрично-векторное уравнение (1) в виде системы трёх алгебраических уравнений следующим об2

Несмотря на действительность матрицы A, её собственные значения λ могут быть и комплексными числами. В случае действительности λ уравнение (1) можно интерпретировать следующим образом. Если матрица A действует не на произвольный, а на «свой собственный» вектор ~x, то при λ > 0 она изменяет лишь его длину, но не направление (при λ < 0 направление вектора изменяется на противоположное).

5

разом: a11 x1 + a12 x2 + a13 x3 = λx1 , a21 x1 + a22 x2 + a23 x3 = λx2 , a31 x1 + a32 x2 + a33 x3 = λx3 .

(2)

Заметим, что на самом деле задача на нахождение СЗВМ является нелинейной, поскольку неизвестными в системе (2) являются не только компоненты вектора ~x, но и скалярная величина λ. Действительно, в правых частях этой системы стоят нелинейные члены — произведения неизвестных вида λxj . Тем не менее, рассматриваемая задача решается в курсе линейной алгебры следующим образом. Перепишем систему (2) в виде (a11 − λ)x1 + a12 x2 + a13 x3 = 0, a21 x1 + (a22 − λ)x2 + a23 x3 = 0, a31 x1 + a32 x2 + (a33 − λ)x3 = 0.

(3)

Матрица коэффициентов этой системы отличается от матрицы A только тем, что из всех диагональных элементов последней вычитается одно и то же (неизвестное!) значение λ. В силу этого систему (3) можно переписать в форме (A − λE)~x = 0,

(4)

 1 0 0 где E =  0 1 0  есть единичная матрица 3 × 3. Очевидно, что и в n0 0 1 мерном случае задача нахождения СЗВМ сводится к решению системы вида (4) при условии, что E является единичной матрицей n × n. Предположим теперь, что значение величины λ в системе (4) нам известно. Тогда эта система является однородной системой линейных алгебраических уравнений относительно компонент вектора ~x, которая, очевидно, всегда имеет нулевое решение x1 = 0, x2 = 0, . . . , xn = 0. Для физических приложений такое тривиальное решение обычно интереса не представляет (см. часть 2 данных методических указаний), и мы должны искать ненулевое решение системы (4). С другой стороны, в силу однородности системы (4) (для частного случая n = 3 она имеет вид (3)) ненулевое решение (~x 6= 0) может существовать только при условии, что её определитель равен нулю 

det(A − λE) = 0. 6

(5)

Расписывая этот определитель в явном виде, мы получим некоторое алгебраическое уравнение n-ой степени относительно неизвестного собственного значения λ. Как хорошо известно, такое уравнение имеет ровно n корней (среди которых могут быть и одинаковые). Заметим, что несмотря на действительность элементов матрицы A, некоторые из этих корней (они суть собственные значения рассматриваемой матрицы) могут оказаться комплексными числами. Итак, решая алгебраическое уравнение (5), мы найдем n собственных значений λj (j = 1..n) матрицы A. Подставляя их по очереди в систему (4), получим n разных систем линейных алгебраических уравнений, которые отличаются лишь значениями параметра λ. В силу однородности каждой такой системы, её решение определяется лишь с точностью до произвольного множителя. Иными словами, если ~x есть некоторый собственный вектор матрицы A, то умножая его на произвольный множитель µ, мы получим вектор µ~x, который также является решением задачи (4), т. е. собственным вектором той же матрицы. В силу этого, любой собственный вектор матрицы A всегда можно нормировать на единицу, т. е. считать, что он имеет единичную длину. Поскольку каждому собственному значению λ = λj отвечает свой вид системы (4), а стало быть, и своё решение ~x = ~x(j) , можно утверждать3 , что матрица A имеет n собственных значений λj и n соответствующих им собственных векторов ~x(j) . В силу вышесказанного, введённый нами верхний индекс при ~x(j) нумерует собственные векторы, а нижние индексы нумеруют компоненты этих (j) (j) (j) векторов: ~x(j) = (x1 , x2 , . . . , xn ). (Там, где не возникает неоднозначности толкования обозначений, мы будем верхние индексы опускать). Таким образом, задача нахождения СЗВМ может быть решена вышеописанным двухэтапным методом, который, однако, на практике в случае матриц большой размерности не применяется, поскольку существуют куда более эффективные численные методы решения рассматриваемой задачи. Действительно, он требует сначала получить в явном виде характеристическое уравнение (5), найти все его корни, и после этого решать для каждого такого корня λj соответствующую систему линейных алгебраических уравнений4 . Существу3

По поводу некоторых математических тонкостей этого утверждения см., например, [1, 2]. В случае эрмитовых матриц оно абсолютно справедливо, но для произвольной матрицы с вырожденным спектром число собственных векторов может быть и меньше n. 4 Численное решение такой задачи является нетривиальным, поскольку ошибки округления с неизбежностью приводят к тому, что определитель матрицы (A − λj E) оказывается малым, но всё-таки отличным от нуля числом. В этом случае единственным решением системы (A − λj E)~x = 0 будет нулевое решение: ~x = 0. Для того, чтобы обойти такого рода вычислительные трудности, применяется так называемый метод «обратных итераций» [1].

7

ет множество разных методов упрощения отдельных этапов такого подхода, и множество методов, основанных на совершенно иных подходах к решению задачи нахождения СЗВМ (см., например, [1, 2, 3, 4]). Особое значение при этом имеет класс методов, основанных на идее приведения матрицы A к диагональному виду с помощью некоторого преобразования подобия. Рассматриваемый ниже метод Якоби относится именно к этому классу методов.

3

Диагонализация матрицы

В курсе линейной алгебры доказывается теорема о том, что квадратную матрицу A можно привести к диагональному виду с помощью некоторого преобразования базиса векторного пространства, в котором она определена. Иными словами, можно найти такой базис, в котором все недиагональные элементы матрицы A оказываются равными нулю. На самом деле, здесь есть некоторые математические тонкости, и не всякую матрицу можно диагонализировать (см., например, [1, 2]), но для симметричных и эрмитовых матриц, которые играют особую роль в физических приложениях, диагонализация всегда возможна. Более того, в процессе доказательства сходимости метода Якоби мы убедимся в возможности диагонализации любых симметричных матриц. Из курса линейной алгебры также известно, что при действии на базис векторного пространства некоторой неособой5 матрицы S −1 , произвольный вектор ~x преобразуется в вектор, ~x0 = S~x, (6) а матрица A — в матрицу A0 = S −1 AS.

(7)

Здесь S −1 есть матрица обратная по отношению к матрице S, т. е. SS −1 = S −1 S = E,

(8)

где E — единичная матрица. Преобразование (7) называется преобразованием подобия. Покажем, что нахождение матрицы S, которая в результате преобразования подобия (7) приводит матрицу A к диагональному виду D, позволяет полностью решить задачу нахождения собственных значений и собственных векторов исходной матрицы A. 5

Т. е. матрицы, имеющей себе обратную.

8

Прежде всего, убедимся в том, что преобразование подобия не изменяет собственные значения (СЗ) матрицы, т. е. что у матрицы A и матрицы A0 , вычисленной по формуле (7), собственные значения одинаковы. Действительно, СЗ матрицы A0 можно найти с помощью характеристического уравнения det(A0 − λE) = 0.

(9)

Подставляя в это уравнение матрицу A0 из уравнения (7) и заменяя единичную матрицу E на выражение S −1 ES, получим det(A0 − λE) = det(S −1 AS − λS −1 ES) = det[S −1 (A − λE)S] = = det(S −1 ) det(A − λE) det(S) = det(A − λE) = 0.

(10)

В процессе этого преобразования мы воспользовались тем, что определитель произведения матриц равен произведению их определителей, и тем, что определитель обратной матрицы det(S −1 ) есть величина обратная по отношению к определителю det(S) исходной матрицы6 . Таким образом, характеристическое уравнение det(A − λE) = 0 для исходной матрицы A и характеристическое уравнение det(A0 −λE) = 0 для матрицы A0 , полученной из уравнения (7), оказываются тождественными друг другу: det(A0 − λE) = det(A − λE) = 0. Следовательно, совпадают и корни этих уравнений, т. е. матрицы A и A0 имеют одну и ту же совокупность собственных значений — λ1 , λ2 , . . . , λn . Что же касается собственных векторов (СВ) матриц A и A0 , то они, в отличие от их собственных значений, вообще говоря, различны! Действительно, рассмотрим определяющее их уравнение вида (1). Для новой матрицы A0 (т. е. матрицы A в новом базисе) имеем A0~y = λ~y .

(11)

Здесь и ниже мы обозначаем СВ матрицы A0 буквой ~y (в то время, как ~x есть СВ матрицы A). Собственные же значения и той, и другой матрицы обозначены одними и теми же символами (λ = λ1 , λ2 , . . . , λn ), поскольку выше была доказана их идентичность. Подставляя в уравнение (11) матрицу A0 из уравнения (7), получим S −1 AS~y = λ~y .

(12)

Последнее является следствием того же свойства определителей, поскольку det(E) = det(S −1 S) = det(S −1 ) det(S) = 1. 6

9

Умножая слева обе части этого уравнения на матрицу S и учитывая, что скалярный множитель λ можно «пронести сквозь» эту матрицу, получим A(S~y ) = λ(S~y ).

(13)

~x = S~y ,

(14)

Полагая теперь находим A~x = λ~x. Таким образом, мы вернулись к исходному уравнению (1), которое определяло СВ и СЗ матрицы A. Итак, мы пришли к выводу, что собственные векторы матриц A0 и A, в отличие от их собственных значений, не совпадают друг с другом, и между ними имеется связь вида (14). Предположим теперь, что мы нашли такую матрицу S, которая, в соответствии с формулой (7), даёт диагональную матрицу A0 , т. е. A0 = D. Здесь и ниже буквой D мы обозначаем диагональную матрицу с элементами d1 , d2 , . . . , dn на её диагонали. Итак, пусть S −1 AS = D

(15)

СЗ диагональной матрицы D, как и любой другой матрицы, можно найти из соответствующего ей характеристического уравнения. В нашем случае это уравнение имеет вид det(D − λE) = (d1 − λ)(d2 − λ) . . . (dn − λ) = 0, откуда очевидно, что его корнями являются значения λ равные d1 , d2 , . . . , dn . Таким образом, собственные значения диагональной матрицы — это её диагональные элементы. Найдем теперь собственные векторы диагональной матрицы D. Рассмотрим сначала частный случай n = 3 (обобщение на случай произвольного n оказы  d1 0 0 вается тривиальным), который соответствует матрице D =  0 d2 0 . Из 0 0 d3 векторного уравнения D~y = λ~y имеем три скалярных уравнения (d1 − λ)y1 = 0, (d2 − λ)y2 = 0, (d3 − λ)y3 = 0. 10

(16a) (16b) (16c)

Предположим, прежде всего, что все собственные значения матрицы D отличны друг от друга (это есть предположение об отсутствии вырождения в спектре собственных значений): d1 6= d2 6= d3 .

(17)

Тогда из системы уравнений (16) видно, что если λ не совпадает ни с одним из трёх чисел d1 , d2 , d3 , то все три компоненты вектора ~y = (y1 , y2 , y3 ) должны обращаться в нуль и мы имеем, таким образом, тривиальное решение ~y = 0 для уравнения D~y = λ~y . Для того же, чтобы это уравнение имело ненулевое решение, λ должно совпадать с одним из диагональных элементов di матрицы D. Пусть, например, λ = d1 . Тогда из уравнений (16) следует, что y1 может быть отличным от нуля, но при этом две другие компоненты вектора ~y , т. е. y2 и y3 , должны иметь нулевые значения, поскольку стоящие перед ними множители, по предположению об отсутствии вырождения, не равны нулю: (d2 − λ) 6= 0 и (d3 − λ) 6= 0. Таким образом, мы приходим к следующему решеa  нию: λ = d1 , ~y = 0 , где a 6= 0. Из требования нормировки собственного 0 вектора ~y на единицу получим a = 1, и следовательно, первая пара СЗ-СВ матрицы D есть   1 (1) (18a) λ1 = d1 , ~y =  0  . 0 Аналогично, из уравнений (16) получим и два других решения уравнения D~y = λ~y :   0 (2) (18b) λ2 = d2 , ~y =  1  , 0   0 (3) λ3 = d3 , ~y =  0  . (18c) 1 Рассмотрим теперь случай наличия вырождения. Это означает, что несколько собственных значений λi совпадают друг с другом. Пусть, например, в рассматриваемом нами случае n = 3 будет d1 = d2 6= d3 . Тогда из системы уравнений (16) следует, что при λ = d1 в нуль обращаются одновременно два множителя: (d1 − λ) и (d2 − λ). В свою очередь, отсюда следует, что в общем 11

случае две первые компоненты вектора ~y могут быть при λ = d1 отличными от нуля, т. е. y1 6= 0, y2 6= 0. Это означает, что собственному значению λ =  d1 = d2 a 7 отвечает двумерное подпространство собственных векторов вида ~y =  b , 0 где a и b суть произвольные числа. Далее, очевидно, что полученный вектор ~y можно представить в виде линейной комбинации     0 1    (19) ~y = a 0 + b 1  0 0     1 0    двух базисных векторов 0 и 1  этого двумерного подпространства. 0 0 Таким образом, можно считать, что в нашем случае имеется пара следующих линейно-независимых собственных векторов, ~y (1) и ~y (2) , которым отвечают одинаковые собственные значения (λ1 = λ2 = d1 = d2 ):   1 (1)  (20) λ1 = d1 , ~y = 0  , 0   0 (2) λ2 = d2 , ~y =  1  . 0 Согласно вышесказанному, любая линейная комбинация (19) этих двух собственных векторов также является собственным вектором матрицы D. Третий собственный вектор получается из системы уравнений (16), если положить λ = d3 . Поскольку в силу нашего предположения, d3 6= d1 и d3 6= d2 , (3) ясно, что две первые компоненты   вектора ~y должны быть равными нулю, 0 (3)  т. е. он сам имеет вид ~y = 0 . После нормировки на единицу мы получим, c таким образом, следующее третье решение векторного уравнения D~y = λ~y :   0 (3)  λ3 = d3 , ~y = 0  . 1 7

Имеется в виду подпространство пространства всех возможных векторов ~y .

12

Итак, мы снова вернулись к решению (18), однако, между двумя рассмотренными нами случаями есть принципиальное различие. Действительно, при отсутствии вырождения собственные векторы автоматически получаются сразу в «каноническом» виде (18), а в случае наличия вырождения они сами собой таковыми при решении уравнения D~y = λ~y «не рождаются», но их можно привести к этому каноническому виду нам самим. Обобщение этого вывода на случай произвольной размерности тривиально: всегда можно считать, что собственные векторы диагональной матрицы D имеют канонический вид       0 0 1 0 1 0          0  (2)  0  (n) (1) (21) ~y =   , ~y =   , . . . , ~y =  0  ,  ..   ..   ..   .   .   .  1 0 0 а соответствующие им собственные значения суть λ1 = d1 , λ2 = d2 , . . . , λn = dn .

(22)

Воспользуемся теперь соотношением ~x = S~y [см. уравнение (14)] между собственными векторами ~x и ~y матриц A и A0 , связанных друг с другом пре(1) образованием подобия (7). Обратимся снова  кслучаю n = 3 и найдём СВ ~x 1 (1) матрицы A, соответствующий СВ ~y =  0  матрицы A0 = D. Имеем 0      s11 s11 s12 s13 1 (23) ~x(1) = S~y (1) =  s21 s22 s23   0  =  s21  . s31 s31 s32 s33 0 Отсюда видно, что первый собственный вектор (~x(1) ) матрицы A является просто первым столбцом той матрицы S, которая приводит матрицу A к диагональному виду. Совершенно аналогично можно убедиться в том, что СВ ~x(2) и ~x(3) являются соответственно вторым и третьим столбцами матрицы S. Обобщение этого результата на случай произвольной размерности также тривиально: всегда можно считать, что ~x(j) является j-м столбцом матрицы преобразования S. Подведём итог. Если мы найдём такую матрицу S, которая приводит исходную матрицу A по формуле A0 = S −1 AS к диагональному виду (A0 = D), 13

то мы полностью решим задачу о нахождении всех собственных значений и собственных векторов матрицы A. Действительно, собственные значения исходной матрицы A суть диагональные элементы матрицы D, а собственные векторы матрицы A суть столбцы матрицы S. Таким образом, мы свели задачу о нахождении СЗ и СВ матрицы A к нахождению такого преобразования подобия, которое приводит её к диагональному виду.

4

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

В большинстве физических приложений мы сталкиваемся с проблемой диагонализации или симметричных или эрмитовых матриц (см., например, часть 2 настоящих методических указаний). Этот момент является принципиально важным, поскольку нахождение собственных значений и собственных векторов таких матриц существенным образом упрощается за счёт их особых свойств. Именно, можно доказать (и фактически это будет сделано при рассмотрении сходимости метода Якоби), что симметричную матрицу можно привести к диагональному виду преобразованием подобия с ортогональной матрицей S и, таким образом, существенно сузить класс матриц, в котором ищется диагонализующее преобразование S. Рассмотрим некоторые необходимые для дальнейшего изложения понятия и факты. Квадратная матрица называется симметричной, если A˜ = A, где с помощью тильды обозначена операция транспонирования матриц. Квадратная неособая матрица U называется ортогональной, если U˜ = U −1 .

(24)

Из этого определения следует, что U˜ U = U U˜ = E.

(25)

Согласно (24), нахождение обратной матрицы в том случае, когда исходная матрица является ортогональной, сводится просто к транспонированию последней (заметим, что нахождение обратной матрицы S −1 в случае матрицы S произвольного вида является достаточно сложной задачей). Из уравнения (25) можно получить следующее весьма полезное свойство ортогональной матрицы U : её столбцы (строки) образуют ортонормированную 14

систему векторов. Действительно, представим матрицу U как совокупность n столбцов ~ui (i = 1..n), каждый из которых является n-мерным вектором: U = (~u1 , ~u2 , . . . , ~un ).

(26)

В результате транспонирования  матрицы U её столбцы становятся строками  ~u1  ~u   2  матрицы U˜ , т. е. U˜ =  ..  . Тогда по определению матричного умножения  .  ~un имеем   ~u1  ~u   2  (27) U˜ U =  ..  (~u1 , ~u2 , . . . , ~un ) = k(~ui , ~uj )k.  .  ~un Таким образом, элемент (U˜ U )ij матрицы U˜ U , стоящий на пересечении i-ой строки и j-го столбца этой матрицы есть скалярное произведение (~ui , ~uj ). С другой стороны, по определению ортогональной матрицы U˜ U = E, и следовательно, (~ui , ~uj ) = δij , (28) где δij есть символ Кронекера, который в нашем случае определяет элементы единичной матрицы E (на диагонали этой матрицы стоят единицы, а все её недиагональные элементы являются нулями). Уравнение (28) означает, что столбцы матрицы U действительно образуют ортонормированную систему векторов. Совершенно аналогичным свойством обладает и совокупность строк ортогональной матрицы. Примером ортогональных матриц могут служить матрицы вращений, отражений и различные их произведения. Рассмотрим так называемые матрицы плоских вращений. Любой двумер  1 ный вектор V~ может быть представлен в виде V~ = v1~e1 + v2~e2 , где ~e1 = 0   0 ~ = (~e1 , ~e2 ) двумерного вектори ~e2 = суть орты «естественного» базиса Φ 1 ~ 0 = (e~0 , e~0 ), ного пространства. Рассмотрим теперь переход к новому базису Φ 1 2 ~ который определяется действием на старый базис Φ = (~e1 , ~e2 ) ортогональной   u11 u21 матрицы U˜ = . Иными словами, мы рассматриваем следующее u12 u22 15

преобразование базисных векторов: ~e1 = u11 e~01 + u21 e~02 , ~e2 = u12 e~0 + u22 e~0 . 1

2

~ = U˜ Φ ~ 0. В краткой форме это преобразование можно записать в виде8 Φ Тогда имеем V~ = v1~e1 +v2~e2 = v1 (u11 e~01 +u21 e~02 )+v2 (u12 e~01 +u22 e~02 ) = e~01 (u11 v1 + u12 v2 )+ e~02 (u21 v1 +u22 v2 ). Таким образом, компоненты v10 и v20 вектора V~ в новом ~ 0 суть базисе Φ v10 = u11 v1 + u12 v2 , v20 = u21 v1 + u22 v2 , что можно записать в виде  0     v1 u11 u12 v1 = v20 u21 u22 v2 или V~ 0 = U V~ . ~ 0 к старому Итак, если матрица U даёт преобразование от нового базиса Φ ~ (Φ ~ = UΦ ~ 0 ), то эта же матрица даёт переход от координат вектора базису Φ в старом базисе к координатам того же самого вектора в новом базисе (V~ 0 = U V~ ). Из курса аналитической геометрии известна следующая формула преобразования координат двумерного вектора при повороте (вращении) базиса на угол ϕ:   cos ϕ − sin ϕ U= . (29) sin ϕ cos ϕ (Для мнемонического запоминания матрицы вращения U : в первой её строке «полный беспорядок», а во второй, наоборот, — «полный порядок»). Таким образом, V~ 0 = U V~ , что можно записать в явном виде следующим образом: v10 = v1 cos ϕ − v2 sin ϕ, v20 = v1 sin ϕ + v2 cos ϕ.

(30)

В многомерном пространстве можно говорить о плоских вращениях вектора в разных плоскостях, которые определяются теми двумя компонентами этого 8

˜ является транспонированной по отношению к матрице U = Матрица U

~ 0 = UΦ ~ иΦ ~ =U ˜Φ ~ 0. нальности обеих этих матриц мы имеем Φ

16



u11 u21

u12 u22

 , и в силу ортого-

вектора которые изменяются (все остальные его компоненты остаются неизменными). Например, в трёхмерном пространстве можно говорить о вращениях в плоскостях (x, y), (x, z) и (y, z), т. е. о вращении на угол ϕ вокруг осей Z, X и Y соответственно. Этим трём случаям отвечают следующие матрицы плоских вращений:     cos ϕ 0 − sin ϕ cos ϕ − sin ϕ 0 , 1 0 Uxy =  sin ϕ cos ϕ 0  , Uxz =  0 sin ϕ 0 cos ϕ 0 0 1   1 0 0 Uyz =  0 cos ϕ − sin ϕ  . 0 sin ϕ cos ϕ В общем случае n-мерного векторного пространства определим матрицу вращения Ui0 j0 в плоскости (i0 , j0 ) следующим образом.   1 | |   ... | |       1 | |    − − − (cos ϕ) − − − (− sin ϕ) − − −  i0     | 1 |   .  . (31) Ui0 j0 =  . | |     | 1 |    − − − (sin ϕ) − − − (cos ϕ) − − −  j0     | | 1     . .   . | | | | 1 i0

j0

Матрица плоского вращения Ui0 j0 (31) отличается от n-мерной единичной матрицы лишь четырьмя своими элементами, именно теми, которые стоят на пересечении двух строк (с номерами i0 , j0 ) и двух столбцов (с теми же самыми номерами i0 , j0 ). Если подействовать матрицей Ui0 j0 на произвольный вектор V~ = (v1 , . . . , vn ), то все его компоненты кроме двух (с номерами i0 , j0 ) остаются неизменными, а компоненты vi0 и vj0 изменяются в соответствии с формулами (30): vi00 = vi0 cos ϕ − vj0 sin ϕ, vj0 0 = vi0 sin ϕ + vj0 cos ϕ, vk0 = vk для k 6= i0 , k 6= j0 . 17

(32)

Легко проверить, что матрица плоского вращения Ui0 j0 является ортогональной. Например, для двумерной матрицы U из формулы (29) находим следующие скалярные произведения её векторов — столбцов ~u1 и ~u2 : (~u1 , ~u1 ) = cos2 ϕ + sin2 ϕ = 1, (~u1 , ~u2 ) = − cos ϕ ∗ sin ϕ + sin ϕ ∗ cos ϕ = 0, (~u2 , ~u2 ) = cos2 ϕ + sin2 ϕ = 1. Таким образом, столбцы матрицы U из формулы (29) образуют ортонормированную систему векторов, откуда следует ортогональность матрицы U . Аналогичное утверждение имеет место и для матрицы плоского вращения (31) в n-мерном пространстве. Матрицы плоских вращений (31) играют в методе Якоби принципиально важную роль, в силу чего его часто называют методом плоских вращений.

5

Суть метода Якоби

Метод Якоби приводит симметричную действительную матрицу к диагональной форме с помощью некоторой (в принципе, бесконечной) последовательности плоских вращений в разных плоскостях исходного n-мерного векторного пространства. Суть этого метода заключается в следующем. Как уже отмечалось, всегда существует такое ортогональное преобразование9 U˜ AU = D, которое приводит исходную действительную симметричную матрицу (A) к диагональному виду (D), т. е. которое зануляет все её недиагональные элементы. Найти такое преобразование «одним махом» в общем случае не представляется возможным, в силу чего метод Якоби состоит из некоторой последовательности шагов, на каждом из которых зануляется один10 из недиагональных элементов (обычно наибольший по модулю), в результате чего старая матрица Aст преобразуется в некоторую новую матрицу Aнов . Делается это с помощью преобразования подобия, использующего матрицу плоского вращения Ui0 j0 , которая изменяет лишь две координаты n-мерных векторов, а именно, координаты с номерами i0 и j0 . Ниже мы покажем, что при таком шаге матрица Aнов отличается от матрицы Aст лишь элементами двух строк с номерами i0 , j0 и двух столбцов с 9 ˜ AU ), которое выполняОртогональным преобразованием называется такое преобразование подобия (U ется с помощью некоторой ортогональной матрицы U . 10 На самом деле, в силу симметричности матрицы A на одном шаге метода Якоби занулёнными оказываются по крайней мере два элемента матрицы, ai0 j0 и aj0 i0 , симметрично расположенные относительно её диагонали.

18

теми же номерами (i0 и j0 ). Все же другие элементы матрицы A остаются неизменными. Матрица плоского вращения Ui0 j0 = Ui0 j0 (ϕ) зависит от одного параметра — угла поворота ϕ, в силу чего в результате преобразования Aнов = U˜i0 j0 · Aст · Ui0 j0

(33)

подлежащий занулению элемент aст i0 j0 матрицы Aст с индексами i0 , j0 преобнов разуется в элемент ai0 j0 (ϕ) матрицы Aнов , т. е. его значение зависит от угла ϕ. Требуя зануления этого элемента, aнов i0 j0 (ϕ) = 0,

(34)

мы получим простое тригонометрическое уравнение, из которого можно найти угол поворота ϕ, приводящий к занулению выделенного нами элемента матрицы Aст . При этом Aст преобразуется в некоторую новую матрицу Aнов , которая, как и матрица Aст , является симметричной. Таким образом, ортогональное преобразование сохраняет свойство симметричности преобразуемой матрицы. Задание. Докажите это свойство ортогонального преобразования, воспользовавшись известным свойством транспонирования произведения двух матриц: ] =B ˜ A. ˜ (AB) Нашей целью, очевидно, является зануление всех недиагональных элементов исходной матрицы A — только в этом случае эта матрица становится диагональной. Может показаться, что зануляя на каждом шаге метода Якоби два ст недиагональных элемента (aст i0 j0 и aj0 i0 ), мы за конечное число шагов занулим все недиагональные элементы матрицы A и приведём её, таким образом, к желаемой диагональной форме. Однако, это не так, поскольку «покойники могут воскресать», именно, если на некотором шаге метода Якоби данный недиагональный элемент был уже занулён, на последующих шагах метода (т. е. в процессе зануления других элементов матрицы) он может снова стать ненулевым (обычно так и происходит!). В силу этого может показаться, что в методе Якоби происходит «переливание из пустого в порожнее» — один элемент зануляем, а другие, уже бывшие нулями, оказываются в результате данного шага отличными от нуля. Тем не менее (и мы докажем это ниже), в результате одного шага метода Якоби сумма квадратов всех недиагональных элементов матрицы уменьшается на конечную величину, именно, на 2a2i0 j0 . И поскольку эта сумма в силу действительности матрицы A не может быть отрицательной, 19

то в конце концов она обратится в нуль. В результате её зануления матрица приобретает, очевидно, диагональный вид, поскольку из равенства нулю суммы квадратов действительных чисел следует равенство нулю каждого из них. Число шагов, за которое матрица A приводится таким способом к диагональной форме, в общем случае является бесконечным. В результате метод Якоби представляет собой некоторый бесконечный итерационный процесс, на каждом шаге которого преобразующаяся матрица становится всё более и более близкой к диагональной форме (в смысле уменьшения суммы квадратов всех своих недиагональных элементов). При проведении практических вычислений мы обычно заканчиваем этот процесс, когда максимальный по модулю среди недиагональных элементов (т. е. тот, который определяет матрицу плоского вращения для следующего шага метода) окажется по модулю меньше заданной вычислительной погрешности ε. Очевидно, что в этом случае и все другие недиагональные элементы будут по модулю меньше ε. Таким образом, применяя на практике метод Якоби, мы приводим исходную матрицу к диагональной форме с точностью до некоторой вычислительной погрешности ε в результате конечного числа шагов. Повышение этой точности требует увеличения (и может быть, очень существенного!) числа шагов метода Якоби. Заметим сразу, что существуют вычислительные схемы, в которых единожды занулённые элементы уже не могут «воскреснуть», т. е. стать ненулевыми, на последующих шагах. При этом, однако, исходную матрицу уже не удаётся привести к диагональной форме, но за конечное число шагов её можно сделать трёхдиагональной. Этим достигается существенный прогресс, поскольку приведение трёхдиагональной матрицы к полностью диагональной форме далее можно осуществить уже другими, весьма эффективными и тоже конечными (в смысле числа шагов) методами (некоторые детали приведены ниже, а для более подробной информации см. книги по численным методам, например, [1, 5]).

6

Алгоритм метода Якоби

Итак, метод Якоби сводится к последовательности отдельных шагов, определяемых формулой (33). В результате каждого такого шага мы находим матрицу Aнов = U˜i0 j0 Aст Ui0 j0 , которую рассматриваем как Aст при выполнении следующего шага. Для того, чтобы не усложнять обозначений, будем матрицы Aст и Aнов , фигурирующие в формуле (33) для одного шага метода, обозначать просто буквами A и C, соответственно. В этих обозначениях один шаг 20

преобразования метода Якоби имеет вид C = U˜i0 j0 · A · Ui0 j0

(35)

Разобьём теперь этот шаг на две части следующим образом I часть : B = A · Ui0 j0 ,

(36)

II часть : C = U˜i0 j0 · B

(37)

и рассмотрим их порознь. Используя формулу матричного умножения, получим: I часть: B = A · Ui0 j0 =   a11 a12 . . . a1n    a21 a22 . . . a2n    = . . . . . . . . . . . . . . . . .    an1 an2 . . . ann   



1 ... − sin ϕ

cos ϕ ... sin ϕ

cos ϕ ...

     =     1

i0 j0    = стар  стар  стар . (38)   нов нов 

На этой схеме показано, что матрица B отличается от матрицы A лишь двумя своими столбцами с номерами i0 и j0 . При этом элементы, стоящие в этих двух «новых» столбцах, определяются формулами bki0 = aki0 cos ϕ + akj0 sin ϕ, bkj0 = −aki0 sin ϕ + akj0 cos ϕ, k = 1..n.

21

(39a) (39b)

Совершенно аналогично для второй части шага метода Якоби имеем: II часть: C = U˜i0 j0 · B =  1  ...   cos ϕ sin ϕ   . .. =   − sin ϕ cos ϕ  ... 

   b b ... b   11 12 1n    b21 b22 . . . b2n  =   . . . . . . . . . . . . . . . .   bn1 bn2 . . . bnn  1

 стар  нов       i0   стар =   нов      j0 стар 

(40)

Таким образом, матрица C отличается от матрицы B лишь элементами двух строк, которые имеют номера i0 и j0 , соответственно. Элементы этих двух «новых» строк определяются при этом формулами: ci0 k = bi0 k cos ϕ + bj0 k sin ϕ, cj0 k = −bi0 k sin ϕ + bj0 k cos ϕ, k = 1..n.

(41a) (41b)

В результате выполнения полного шага метода Якоби C = U˜i0 j0 · A · Ui0 j0 получим следующую диаграмму, из которой видно, что матрица C отличается от матрицы A лишь элементами, стоящими в двух горизонтальных и двух вертикальных полосах с номерами i0 и j0 (на диаграмме они отмечены чёрными квадратиками):            i0        (42) C=         j0  i0

 j0

Из диаграммы (42) видно, что недиагональные элементы с индексами (i0 j0 ) изменялись дважды — один раз при выполнении первой части шага метода Якоби, а другой раз при выполнении второй его части. 22

Полагая в формуле (41a) k = j0 , мы выразим ci0 j0 через bi0 j0 и bj0 j0 , которые в свою очередь, можно выразить через ai0 i0 , ai0 j0 = aj0 i0 и aj0 j0 с помощью формулы (39b). В результате, используя известные тригонометрические формулы, получим: ci0 j0 = [−ai0 i0 sin ϕ + ai0 j0 cos ϕ] cos ϕ+ + [−aj0 i0 sin ϕ + aj0 j0 cos ϕ] sin ϕ = = sin ϕ cos ϕ[aj0 j0 − ai0 i0 ] + [cos2 ϕ − sin2 ϕ]ai0 j0 = 1 = ai0 j0 cos(2ϕ) + [aj0 j0 − ai0 i0 ] sin(2ϕ). (43) 2 Согласно уже обсуждавшейся идее метода Якоби, мы требуем зануления элемента ci0 j0 (при этом предполагается, что элемент ai0 j0 был максимальным по модулю среди всех недиагональных элементов матрицы A): ci0 j0 (ϕ) = 0.

(44)

С учётом (43), уравнение (44) представляет собой простое тригонометрическое уравнение для определения угла ϕ: 1 ai0 j0 cos(2ϕ) + [aj0 j0 − ai0 i0 ] sin(2ϕ) = 0. 2 Отсюда ясно, что 2ai0 j0 tg(2ϕ) = . (45) ai0 i0 − aj0 j0 Из этого условия можно найти угол плоского вращения ϕ, который приводит к занулению элемента ci0 j0 . Однако фактически нам требуется не столько значение самого угла ϕ, сколько его синус и косинус, ибо именно эти величины и определяют матрицу плоского вращения Ui0 j0 согласно формуле (31). Используя простые тригонометрические соотношения, можно выразить sin ϕ и cos ϕ через тангенс двойного угла tg(2ϕ). Действительно, пусть η = ±1 определяет знак11 правой части уравнения (45), а 1 K ≡ cos(2ϕ) = p . (46) 1 + tg2 (2ϕ) Тогда имеем r 1−K sin ϕ = η · , (47) 2 r 1+K cos ϕ = . 2 11

Т. е. η = sign( ai

2ai0 j0 −aj0 j0

0 i0

).

23

Таким образом, мы полностью определили формулы преобразования, соответствующие одному шагу метода Якоби: номера i0 и j0 находятся по положению в матрице A максимального по модулю недиагонального элемента (ai0 j0 ), а входящие в матрицу плоского вращения Ui0 j0 неизвестные элементы sin ϕ и cos ϕ определяются формулами (46), (47). Заметим, что для осуществления шага метода Якоби нецелесообразно полностью выполнять матричные умножения, соответствующие формуле C = U˜i0 j0 · A · Ui0 j0 , а достаточно использовать готовые формулы (39) и (41), определяющие только те элементы матрицы C, которые изменяются в результате рассматриваемого ортогонального преобразования (см. диаграмму (42)). Теперь следует вспомнить, что нам необходимо не только найти явный вид диагональной матрицы D (её диагональные элементы являются собственными значениями матрицы A), которая получается из исходной матрицы A с помощью ортогонального преобразования U˜ AU = D, но и получить в явном виде матрицу полного преобразования U , столбцы которой, как было доказано ранее, суть собственные векторы матрицы A. Легко сообразить, что матрица U является произведением всех матриц плоских вращений Ui0 j0 , которые фигурировали на отдельных шагах метода Якоби. Действительно, обозначим через Ak (k = 1, 2, 3, . . . ) матрицы, получаемые из исходной матрицы A в процессе её диагонализации, а через Uk — матрицу плоского вращения на k-м шаге метода Якоби. Таким образом, в результате выполнения k-го шага метода мы получим матрицу Ak+1 из матрицы Ak в результате преобразования Ak+1 = U˜k Ak Uk . Тогда имеем Ak+2 = U˜k+1 Ak+1 Uk+1 = U˜k+1 (U˜k Ak Uk )Uk+1 = (U˜k+1 U˜k )Ak (Uk Uk+1 ). ˜ ˜ С другой стороны, (U^ k Uk+1 ) = Uk+1 Uk (при транспонировании произведения матриц транспонированные сомножители переставляются). Таким образом, Ak+2 = (U^ k Uk+1 )Ak (Uk Uk+1 ).

(48)

Из этой формулы ясно, что преобразование матриц Ak в результате двух последовательных шагов метода Якоби можно рассматривать как ортогональное преобразование с помощью матрицы, равной произведению матриц плоских вращений (Uk и Uk+1 ), используемых на каждом из этих шагов. 24

Из приведённого рассуждения следует, что окончательную матрицу U , которая приводит матрицу A к диагональной форме, можно получить как произведение всех матриц плоских вращений, использованных на отдельных шагах метода Якоби: N Y Uk , (49) U= k=1

где N — число сделанных шагов. Заметим, что при практическом вычислении этого произведения нерационально использовать общую формулу умножения квадратных матриц. Действительно, для этой цели достаточно применить формулы типа (39,41) для умножения произвольной матрицы B слева на очередную матрицу плоского вращения (31). Вернёмся теперь к общему описанию алгоритма метода Якоби. Применяя этот метод, будем находить на k-ом шаге максимальный по модулю недиагональный элемент матрицы Ak . Его положение в матрице Ak (т. е. номер строки и номер столбца, на пересечении которых он стоит) определяют два индекса i0 и j0 , которые используются для построения матрицы плоского вращения (31). Далее по формулам (47) находим sin ϕ и cos ϕ, входящие в эту матрицу (Uk = Ui0 j0 ), и по формулам (39,41) выполняем преобразование матрицы Ak , в результате чего она переходит в матрицу Ak+1 = U˜k Ak Uk . Этот процесс повторяется до тех пор пока максимальный по модулю недиагональный элемент на очередном шаге не окажется меньше некоторой вычислительной точности ε, с которой мы хотим получить диагональный вид исходной матрицы A. Как уже говорилось, в связи с этим алгоритмом возникает вопрос о сходимости метода Якоби. Ниже мы докажем, что на каждом шаге метода (т. е. при переходе от Ak к Ak+1 ) сумма квадратов всех недиагональных элементов матрицы Ak уменьшается на конечную величину. Поскольку эта сумма квадратов для действительной матрицы не может быть меньше нуля, отсюда следует, что всегда можно добиться того, чтобы она стала меньше любой наперёд заданной вычислительной точности ε. Описанный выше метод Якоби пригоден для диагонализации только симметричных матриц. В процессе преобразований на отдельных шагах этого метода свойство симметричности преобразуемой матрицы сохраняется. Действительно, пусть матрица Ak была симметричной, т. е. A˜k = Ak , и в результате 25

одного шага мы перешли к матрице Ak+1 = U˜k Ak Uk . Тогда имеем ˜ ˜ ˜ A˜k+1 = (U˜^ k Ak Uk ) = Uk Ak Uk = Uk Ak Uk = Ak+1 . В процессе этих преобразований использовано известное свойство транспони˜ A, ˜ которое получается ] = C˜ B рования тройного произведения матриц ABC тривиальным образом из соответствующего свойства транспонирования двойg = B ˜ A. ˜ Таким образом, новая матрица Ak+1 также ного произведения: AB оказывается симметричной (A˜k+1 = Ak+1 ).

7

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

При выполнении обеих частей шага метода Якоби имеют место определённые «законы сохранения». Рассмотрим этот вопрос более подробно. Пусть некоторая квадратная матрица A умножается на ортогональную матрицу V слева: Aнов = V ·A. Матрицу A можно представить в виде совокупности её столбцов: A = (~a1 , ~a2 , . . . , ~an ). Пользуясь правилом матричного умножения, легко понять, что столбцы матрицы Aнов получаются в результате умножения столбцов матрицы A на V : Aнов = (~aнов aнов aнов a1 , V ~a2 , . . . , V ~an ). 1 ,~ 2 , . . . ,~ n ) = (V ~ Таким образом, ~aнов = V ~aj j

(j = 1..n).

(50)

Рассмотрим теперь скалярное произведение двух произвольных столбцов матрицы Aнов : (~aнов aнов aj , V ~ak ) = (~aj , V˜ V ~ak ). (51) j ,~ k ) = (V ~ При выводе этого соотношения мы воспользовались очень важным свойством «переноса» действия произвольной матрицы V с первого множителя скалярного произведения на второй его множитель12 . Задание. Проверить справедливость формулы (V ~a, ~b) = (~a, V˜ ~b), выписывая в явном виде левую и правую её части (рекомендуется сначала сделать это для случаев n = 2 и n = 3). 12

Это соотношение часто используется в квантово-механических расчётах с учётом того, что в комплексном векторном пространстве переопределяется скалярное произведение: < ~a|~b >= (~a∗ , ~b). Тогда мы имеем соотношение < V ~a|~b >=< ~a|V +~b >. В приведённых выше формулах звёздочкой обозначена операция комплексного сопряжения, а крестом — операция эрмитова сопряжения, которая заключается в двух последовательных операциях над матрицей, а именно, в транспонировании и комплексном сопряжении (очевидно, в любом порядке).

26

Подчеркнём, что свойство (V ~a, ~b) = (~a, V˜ ~b) и следующая из него формула (51) имеют место для произвольной матрицы V , но у нас, по предположению, матрица V является ортогональной (V −1 = V˜ ) и, следовательно, V˜ V = E. В силу этого соотношения, формулу (51) можно переписать в виде (~aнов aнов aj , ~ak ), j ,~ k ) = (~

j = 1..n, k = 1..n.

(52)

Таким образом, при умножении матрицы A на ортогональную матрицу V слева сохраняются скалярные произведения всех пар её столбцов. В частности, из этого следует, что сохраняются и все квадраты длин векторов-столбцов матрицы A: (~aнов aнов aj , ~aj ), j ,~ j ) = (~ т. е. сохраняются суммы квадратов элементов каждого столбца матрицы A. Совершенно аналогично можно доказать, что при умножении матрицы A на ортогональную матрицу V справа (Aнов = AV ) сохраняются суммы квадратов всех элементов каждой строки матрицы A. Рассмотрим теперь изменение суммы квадратов S(A) всех недиагональных элементов матрицы A в результате одного шага метода Якоби: C = U˜i0 j0 · A · Ui0 j0 .

(53)

Структура матрицы C показана на диаграмме (42), которую мы воспроизведём теперь с некоторыми новыми деталями:    ↔      F   i0    l  ←→  l  l  C=  (54)   F     j0  ↔  i0 j 0 Согласно этой схеме, все элементы матрицы C, которые стоят вне выделенных полос (двух горизонтальных и двух вертикальных с номерами i0 и j0 ) не изменяются в процессе выполнения одного шага метода Якоби. Составим теперь разность ∆(A → C) = S(A) − S(C), которая показывает, насколько уменьшается сумма квадратов всех недиагональных элементов преобразуемой матрицы при переходе A → C, т. е. на одном шаге метода Якоби. Ясно, что элементы, стоящие вне выделенных полос матрицы C из схемы (54), не могут дать вклад в ∆(A → C), поскольку они в результате преобразования (53) вообще не изменяются. С другой стороны, любые два элемента, 27

соединённые на схеме (54) горизонтальной стрелкой, изменяются только на первой половине шага Якоби (см. схему (38)), но при этом должна сохраняться сумма квадратов элементов строки, в которой они стоят, поскольку матрица A умножается на ортогональную матрицу Ui0 j0 справа: B = A · Ui0 j0 . Отсюда ясно, что сумма квадратов элементов, соединённых горизонтальной стрелкой, в результате одного шага метода Якоби не изменяется, несмотря на то, что каждый из этих элементов изменяется. Таким образом, эта пара элементов не может дать вклад в величину ∆(A → C). Совершенно аналогично можно убедиться в том, что элементы, соединённые вертикальными стрелками на диаграмме (54), также не дают вклада в величину ∆(A → C). Действительно, эти элементы изменяются только на второй половине шага метода Якоби, но при этом имеет место закон сохранения суммы квадратов элементов каждого столбца (поскольку при преобразовании C = U˜i0 j0 · B происходит умножение матрицы B на ортогональную матрицу U˜i0 j0 слева). Какие же элементы преобразуемой матрицы могут дать вклад в ∆(A → C)? Очевидно, только те два элемента ai0 j0 и aj0 i0 (равные между собой в силу симметричности матрицы A), которые преобразуются в результате обеих частей шага метода Якоби. На схеме (54) они показаны звёздочками. (Заметим, что диагональные элементы ai0 i0 и aj0 j0 не входят в ∆(A → C) по определению). Таким образом, ∆(A → C) = 2a2i0 j0 − 2c2i0 j0 . (55) С другой стороны, по определению шага метода Якоби мы зануляем элемент ci0 j0 (который соответствовал максимальному по модулю элементу ai0 j0 матрицы A). Учитывая равенство ci0 j0 = 0, получим из (55): ∆(A → C) = 2a2i0 j0 > 0

(56)

(квадрат любого элемента матрицы A не меньше нуля в силу её действительности). Если бы ai0 j0 был равен нулю (а это ведь максимальный по модулю недиагональный элемент преобразуемой матрицы!), то мы бы уже не делали очередного шага метода Якоби, поскольку тогда и все остальные недиагональные элементы были бы равны нулю. Таким образом, если шаг A → C ещё делается, то имеет место строгое неравенство ai0 j0 > 0 и, следовательно, в результате перехода A → C по формуле (53) происходит уменьшение суммы квадратов недиагональных элементов преобразуемой матрицы на конечную величину 2a2i0 j0 . А поскольку сама по себе эта величина меньше нуля стать не может, 28

ясно, что рано или поздно (обычно лишь в пределе, когда число шагов метода стремится к бесконечности) эта сумма квадратов должна обратиться в нуль, т. е. преобразуемая матрица должна стать полностью диагональной. Из вышеобсужденных «законов сохранения» следует, что сумма квадратов всех (диагональных и недиагональных) элементов сохраняется и на первой, и на второй половине шага метода Якоби. Тогда ясно, что этот метод работает как некоторый «насос», который постепенно перекачивает недиагональные величины на диагональ в том смысле, что сумма квадратов недиагональных элементов на каждом шаге метода Якоби уменьшается, а сумма квадратов диагональных элементов, наоборот, увеличивается. Подводя итоги, скажем, что, таким образом, метод Якоби является некоторым итерационным процессом (в общем случае число его шагов бесконечно), в результате которого преобразуемая матрица на каждом шаге становится всё более и более близкой к диагональному виду (сумма квадратов недиагональных элементов всё время уменьшается). Приводя матрицу A к диагональному виду D (D = U˜ AU ) и найдя полную матрицу ортогонального преобразования U как произведение всех матриц плоских вращений, мы найдём собственные значения матрицы A (они являются диагональными элементами матрицы D) и её собственные векторы (они являются столбцами матрицы U ).

8

Дополнения к методу Якоби 1. О применении метода Якоби На каждом шаге метода Якоби мы зануляли максимальный по модулю элемент среди всех недиагональных матричных элементов. Таким образом, после каждого шага метода необходимо просматривать все недиагональные элементы в поиске их максимального по модулю значения. Эта процедура требует дополнительное машинное время (особенно в случае матриц большой размерности). Поэтому, применяя метод Якоби, часто зануляют «первый попавшийся» недиагональный элемент, модуль которого превышает ε. Метод Якоби будет, очевидно, сходиться и в этом случае. Более того, нахождение для зануления самого большого по модулю недиагонального элемента матрицы может, по целому ряду причин, как ускорить, так и замедлить сходимость алгоритма (см.[5]).

29

2. О нахождении СЗ и СВ эрмитовых матриц Мы подробно рассмотрели метод Якоби для случая задачи нахождения СЗ и СВ симметричной матрицы. Заметим, что в большинстве физических приложений приходится иметь дело именно с этим случаем (эрмитову матрицу нередко удаётся привести к действительному виду, в результате чего она становится симметричной). Разумеется, это можно сделать не всегда, но сам метод Якоби тривиальным образом обобщается на случай работы с эрмитовыми матрицами (которые играют особую роль в квантовой механике [см. часть II данных методических указаний]). Сведение эрмитовой матрицы к действительному виду экономит вдвое память и заметно ускоряет счёт, поскольку нет необходимости прибегать к комплексной арифметике. 3. О нахождении СЗ и СВ неэрмитовых матриц Метод Якоби можно обобщить и на случай произвольных неэрмитовых матриц. При этом удаётся обратить в нуль (с точностью до ε) все поддиагональные (наддиагональные) элементы, в результате чего исходная матрица становится верхней (нижней) треугольной матрицей. В свою очередь, такое сведение позволяет резко упростить («почти завершить», как говорится в [5]) задачу поиска СЗ и СВ исследуемой матрицы. 4. О вычислительных погрешностях Как уже многократно отмечалось, ортогональное преобразование сохраняет свойство симметричности преобразуемой матрицы. Однако, так происходит лишь в идеале, а при практических вычислениях накопление ошибок округления может привести к нарушению этого свойства. Погрешность будет гораздо меньше, если эрмитовость соблюдать принудительно, т. е. не вычислять aji , а сразу полагать его равным уже вычисленному элементу aij (см., например, [5]). 5. О точности нахождения СЗ и СВ Можно доказать, что если мы с помощью метода Якоби добились диагонализации матрицы с точностью до ε (т. е. все её недиагональные элементы стали по модулю меньше ε), то точность вычисления собственных значений будет более высокой по сравнению с точностью вычисления собственных векторов. Именно, СЗ при этом получаются с точностью до ε2 , а СВ лишь с точностью до ε1 . Поэтому, если нужны только собственные 30

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

9

Понятие о некоторых других методах нахождения СЗ и СВ матриц

Как уже отмечалось, можно построить такие вычислительные схемы, при которых единожды занулённый в результате ортогонального преобразования матричный элемент при дальнейших преобразованиях, в отличие от метода Якоби, уже «не воскресает» (т. е. не может вновь стать отличным от нуля). При этом, однако, не удаётся привести исходную матрицу к полностью диагональной форме, и максимальное её упрощение сводится лишь к тому, что она приобретает вид трёхдиагональной матрицы. После этого необходимо решить вторую часть задачи — найти СЗ и СВ полученной трёхдиагональной матрицы, что делается с помощью особых вычислительных процедур (эта задача является существенно более простой по сравнению с исходной задачей о нахождении СЗ и СВ произвольной матрицы). Первым из методов этого класса был предложенный в 1954 году метод Гивенса, который часто называют прямым методом вращений (в отличие от итерационного метода вращений — метода Якоби). В 1958 г. Хаусхолдер разработал существенно более эффективный метод, использующий не матрицы вращений, как это делается в методе Гивенса, а матрицы отражений. В результате, в настоящее время в распоряжении вычислителя имеются методы, которые работают в десятки раз быстрее метода Якоби. Описание такого рода методов можно найти в книгах [1, 2, 3, 4, 5]. Тем не менее, в вычислительной практике находит применение и рассмотренный нами метод Якоби, поскольку у него есть определённые достоинства по сравнению с вышеуказанными более быстрыми методами. Процитируем в связи с этим замечание Н. Н. Калиткина из книги [1]: «Итерационный метод вращений применяется там, где важны точность, надёжность и простота расчёта и менее существен объём вычислений». На практике нередко встречаются случаи, когда необходимо найти только собственные значения, а собственные векторы при этом можно не вычислять. Существует много разных методов решения этой, более простой задачи (см. [2, 3]). Более того, в физических приложениях нередко возникают задачи, в которых необходимо найти не все, а только некоторые собственные значения. 31

Например, надо найти несколько нижних уровней энергии данной квантовой системы (основное состояние и несколько ближайших к нему возбуждённых состояний). Разумеется, это существенно более простая задача по сравнению с нахождением всех СЗ и СВ. Для её решения разработаны специальные алгоритмы, построенные, например, на основе вариационных методов. Мы вернёмся к такой постановке задачи во второй части настоящих методических указаний. Описание различных методов нахождения СЗ и СВ матриц можно найти в большинстве пособий по численным методам, приведённых в списке литературы на стр. 36.

10

Глоссарий

1. Вырожденный спектр матрицы означает, что некоторым её собственным значениям соответствует несколько линейно независимых собственных векторов. 2. Диагонализация матрицы — приведение матрицы к диагональному виду (с помощью преобразования подобия). 3. Матрица плоского вращения — ортогональная матрица U , которая при действии на многомерный вектор изменяет лишь две его компоненты, например, с номерами i и j по формулам вращения вектора на угол ϕ в плоскости. Она отличается от единичной матрицы только четырьмя своими элементами: uii = ujj = cos ϕ, −uij = +uji = sin ϕ. 4. Ортогональная матрица — матрица U , которая при транспонировании превращается в себе обратную: U˜ = U −1 . Столбцы (строки) этой матрицы образуют ортонормированную систему векторов. 5. Ортогональное преобразование — преобразование над матрицей A вида U˜ AU , где U — ортогональная матрица. 6. Собственные векторы ~x(j) и собственные значения λj квадратной матрицы A удовлетворяют уравнению A~x(j) = λj ~x(j) . 7. Спектр матрицы — полный набор её собственных значений. 8. Преобразование подобия матрицы A определяется формулой S −1 AS, где S — некоторая неособая квадратная матрица. Это преобразование опи32

сывает изменение элементов матрицы A, индуцированное изменением базиса векторного пространства, в котором действует матрица A. 9. Симметричная матрица — квадратная матрица, которая не изменяется в результате транспонирования: A˜ = A. 10. Унитарная матрица — матрица (вообще говоря, комплексная), которая в результате операции эрмитова сопряжения превращается в себе обратную: U + = U −1 . 11. Унитарное преобразование матрицы A — преобразование подобия с помощью унитарной матрицы U : U + AU . 12. Характеристическое уравнение для квадратной n×n матрицы A имеет вид det(A − λE) = 0, где E — единичная матрица. Оно является алгебраическим уравнением n-го порядка относительно скаляра λ. Корни этого уравнения являются собственными значениями матрицы A. 13. Эрмитова (самосопряжённая) матрица — матрица, которая не изменяется в результате операции эрмитова сопряжения: A+ = A. 14. Эрмитово сопряжение матрицы обозначается крестом над матрицей и означает последовательное выполнение (в любом порядке) двух следующих операций — транспонирования и комплексного сопряжения (над всеми элементами матрицы).

11

Контрольные вопросы и задания для самостоятельной работы студентов

1. Что называется собственными векторами и собственными значениями матрицы? Является ли задача их нахождения линейной? 2. Могут ли собственные значения действительной матрицы быть комплексными числами? 3. Почему собственные векторы матриц можно нормировать? 4. Могут ли собственные значения симметричной матрицы быть отрицательными числами? 5. Что такое преобразование подобия? 33

6. Как изменяются собственные векторы и собственные значения матрицы в результате преобразования подобия? 7. Почему собственные значения диагональной матрицы, полученной с помощью преобразования подобия, являются собственными значениями исходной матрицы? 8. В чем состоят отличия при нахождении собственных векторов матрицы в случае вырожденности и невырожденности ее спектра собственных значений? 9. Чем отличается процесс диагонализации матрицы общего вида и матрицы симметричной? 10. Что такое ортогональная матрица? Какими свойствами обладают ее строки и столбцы? 11. Что такое матрица плоского вращения? 12. Для нахождения собственных значений каких матриц пригоден метод Якоби? 13. Почему заранее нельзя сказать, сколько шагов метода Якоби необходимо сделать для достижения диагонального вида исходной матрицы? 14. Какие элементы преобразуемой матрицы не изменяются в процессе одного шага метода Якоби? 15. Как найти матрицу плоского вращения на очередном шаге метода Якоби? Из какого условия находится угол плоского вращения? 16. Докажите, что в результате каждого шага метода Якоби свойство симметрии преобразуемой матрицы сохраняется. 17. Докажите, что на одном шаге метода Якоби сумма квадратов недиагональных элементов уменьшается на удвоенный квадрат того элемента, который подлежит занулению на данном шаге. 18. До каких пор продолжается итерационный процесс метода Якоби при практическом нахождении собственных значений и собственных векторов исходной матрицы?

34

19. Выведите формулы преобразования диагонализируемой матрицы на одном шаге метода Якоби. 20. Как в методе Якоби строится полная матрица ортогонального преобразования, которая приводит исходную матрицу к диагональному виду? 21. Выведите формулу для транспонирования тройного матричного произведения. 22. Докажите, что при умножении произвольной квадратной матрицы A на ортогональную матрицу V слева (Aнов = V A) сохраняется сумма квадратов каждого столбца матрицы A, а при умножении ее на ортогональную матрицу V справа (Aнов = AV ) сохраняется сумма квадратов элементов каждой строки матрицы A. 23. Докажите справедливость соотношения (V ~a, ~b) = (~a, V˜ ~b) для произвольных векторов ~a, ~b и произвольной квадратной матрицы V . 24. Как изменяется от шага к шагу метода Якоби сумма квадратов всех недиагональных и всех диагональных элементов преобразуемой матрицы? 25. Какой из недиагональных элементов преобразуемой матрицы подлежит занулению на очередном шаге метода Якоби и почему? 26. Следует ли на каждом шаге метода Якоби вычислять все элементы преобразуемой матрицы, которые находятся над и под ее диагональю? 27. С одинаковой ли точностью в методе Якоби находятся собственные значения и компоненты собственных векторов? 28. Докажите сходимость метода Якоби. 29. Какие другие методы нахождения собственных значений и собственных векторов Вы знаете? 30. Что Вам известно о нахождении собственных значений и собственных векторов эрмитовых и неэрмитовых матриц?

35

Список литературы [1] Калиткин Н. Н. Численные методы. — М.:Наука, 1978. [2] Фадеев Д. К., Фадеева В. Н. Вычислительные методы линейной алгебры. — М.:Физматгиз, 1963. [3] Воеводин В. В. Вычислительные методы линейной алгебры. — М.:Наука, 1977. [4] Уилкинсон Дж. Х. Алгебраическая проблема собственных значений. — М.:Наука, 1970. [5] Ильина В. А., Силаев П. К. Численные методы для физиков-теоретиков, Часть 1 и Часть 2. — Москва-Ижевск, 2003. [6] Хемминг Р. В. Численные методы для научных работников и инженеров. — М.:Наука, 1968. [7] Бахвалов Н. С., Жидков Н. П., Кобельков Г. М. Численные методы. — М.:Наука, 1987. [8] Самарский А. А. Введение в численные методы. — М.:Наука, 1997. [9] Турчак Л. И. Основы численных методов. — М.:Наука, 1987. [10] Волков Е. А. Численные методы. — М.:Наука, 1982. [11] Самарский А. А., Гулин А. В. Численные методы математической физики. — М.:Наука, 1989, М.:Научный мир, 2000. [12] Березин И. С., Жидков Н. П. Методы вычислений, Том 1. — М.:Наука, 1962 и Том 2 —М.:Физматлит, 1966. [13] Форсайт Дж., Малькольм М., Моулер К. Машинные методы математических вычислений. — М.:Мир, 1980. [14] Шуп Т. Решение инженерных задач на ЭВМ. — М.:Мир, 1982. [15] Турчак Л. И., Плотников М.:Физматлит, 2003.

П. В.

Основы

численных

методов.

—

[16] Говорухин В. Н., Цибулин В. Г. Введение в Maple. — М.:Мир, 1997. [17] Говорухин В. Н., Цибулин В. Г. Компьютер в математическом исследовании. Maple, Matlab, LATEX. — С.Петербург:Питер, 2001. 36