1626435584-7c6402f545ecf856225d6cf8d21519c9 (844233), страница 39
Текст из файла (страница 39)
Любое вращение можно свести к последовательности элементарных (плоских) вращений — поворотов в двумерной плоскости, проходящей через л-ю и 1-ю оси координат; остальные оси координат при этом неподвижны. Для комплексных векторов матрица элементарного вращения имеет следующий вид: а соз ~р, а=е ьй мп ф, (42) 1-я аз+( р ~а=1.
Остальные недиагональные элементы этой матрицы — нули. Для вещественных векторов надо полагать ф=о. Непосредственным перемножением легко проверить, что У Уз~= Е, т. е, матрица вращения унитарна (напомним, что преп м образования с упнтарпымн матрицами обычно устойчивы). Очень важно помнить, что если из-за погрешностей расчета окажется, что ыз+! р э~1, или р и ()' в (42) не тоюю сопряжены друг другу, то унитарность матрицы нарушается. Тогда прн преобразовании подобия нарушится эрмитовость матрицы А и сильно ухудшится устойчивость всех методов вращения, которые будут описаны далее.
Поэтому в численных расчетах следует определять сс и р по таким формулам, чтобы укаэанные соотношения выпол. нялись с очень высокой точностью. Построим формулы для преобразования матрицы А при элементарном вращении. Матрица В=АУЫ отличается от мазрицы А элементами й.го и 1.го столбцов; остальные элементы у иих совпадают; Ь|ь = азьи+ап(4, Ьн = — а~ь()" +она, 1 щ 1 ( л, (43) Ц =ап при 1'~Ф, 1 и 1 (1~о. 176 АЛГЕБРАИЧЕСКАЯ ПРОБЛЕМА СОБСТБЕННЫХ ЗНАЧЕНИИ (ГЛ. У! Аналогично, матрица С= ()ьн!В отличается от матрицы В только элементами Ь-й и !.й строк: сзг=ьна+ьггя<»*, сл= — ьаг!1+ьигх, ! ()к л, (44) гу<4 Ь)г при )~Ь, ! и 1 -"!<йи.
Следовательно, матрица С=УНАУ отличается от матрицы А лишь двумя строками и двумя столбцами. Формулы для вычисления элементов этих с~рок и столбцов написать нетрудно, но в этом нет необходимости; удобнее программировать на ЭВМ непосредственно формулы (43) †(44). Заметим, что если матрица А эрмитова, то матрицз С также будет эрмитова; тогда в изменившихся столбцах .и строках достаточно вычислить только половину элементов и тем "1 ! самым вдвое уменьшить обьем расчетов. Найдем такую последовательность элементарных У О7(у<!) вращений, которая приводит произвольную (незрмитову) о 4 Ог (г!) ((У) матрицу А к верхней почти треугольной форме. 5 У Гх 14 ГЬ Можно так подобрать а) л) угол поворота в матрице ()ьь чтобы уничтожить элеРис. 33.
мент сь э,, расположенный непосредственно перед левым нижним углом подматрицы плоского поворота (рис. ЗЗ, а). Из формул (43) и (44) видно, что для этого надо положить ,'амь,', <хаг ь» р , 'а», а г,"+! аь А,,» ' пь, э-< (45а) Сами углы вычислять нет необходимости, ибо в формулы для преобразования матричных элементов они не входят. Отметим, что для вещественных матриц величина () тоже будет вещественнои; тогда формулы (45) удобнее записать следующим образом: ц= ь'» ', ()= о» ', (455) )/аз» А, +аг А, )l аа» э,+а! ь Теперь будем аннулировать те элементы матрицы н в том порядке, как это указано цифрами на рис. ЗЗ, б.
Первый элемент уничтожается прн помощи матрицы (/ы, обозначенной иа рисунке сплошным квадратом. Второй уничтожается вращением !!»<, обозначенным пунктирным квадратом. При втором вра. шенин в матрице А меняются элементы вторых и четвертых строк и столбцов. Значит, аннулированный элемент <1», лежащий в треп,ей строке, так и останется равным нулю.
Продолжая эти рассуждения, можно убедиться, что однажды уничтоженный элемент при такой последовательности исключения будет оставаться рав. ным нулю, Поэтому после окончания всех исключений матрица станет верхней почти треугольной матрицей (аг)=0 пря < )/+1). Это справедливо для произвольной -(неэрмитовои) матрицы. Если исходная матрица А эрмитова, то благодаря сохранению эрмитовости при унитарном преобразовании подобия она приводится к трехдиагональнон форме. В этом случае для экономии времени прк каждом вращении достаточно )77 ЭРМИТОВЫ МАТРИЦЫ вычислять только измеиивншеся элементы нижней половины матрицы (уже обратившиеся п нуль элементы в дальнейшие расчеты не включают).
Для полученной трехдиагональной (или почти треугольной) матрицы можно вычислять собственные значения и собственные векторы способами, изложенными в 4 !. Найденные собственные значения будут одновременно собственными значениями исходной матрицы. А собственные векторы х; исходной мат. рицы связаны с собственнымп векторами трехдиагональной матрицы соотношением х;=и„и„... и„ь „уь Проще всего вычкслять их, последовательно умножая требуемый вентор у слева на матрицы вращения.
Структура матриц такова, что при умнозкении на из, меняются только ь-я и 1-я компоненты вектора хе = ауз — ()*уь хг = руз+ аул х =уг прн 1 ФА, 1. Предварительное перемножение самих матрац вращения потребовало бы боль. н1его числа действий (это особенно невыгодно, если нул<на только часть собственных векторов). На пряведение эрмвтовой матрицы к трсхдиагональной форме н нахождение всех собственных значений в методе вращений требуется около 2пз+бопз арифметических действий и гя ячеек оперзтнвноа памяти.
Для нахождения каждого собственного вектора надо затратить еще Злз действий. Собственные аначення и собственные векторы в этом методе определяются устойчиво (если унитарность изг не нарушена ошибками округления). 3. Итерационный метод вращений. Несмотря на свою быстроту, описанные выше прямые методы не вполне удовлетворительны. Так, их алгоритм состоит из разнородных частей: преобразования исходной матрицы, вычисления корней многочлена, нахождения собственных векторов обратными итерациями, Кроме того, их формулы не упрощаются для некоторых употребительных специальных форм матриц (например, ленточных); тем самым они невыгодны дчя таких матриц.
Поэтому разработан и используется ряд итерационных методов, в общем случае более медленных, но обладающих какими-то частными преимуществами. Для эрмитовых матриц наиболее известен итерационный метод вращений, предложенный Якоби в 1846 г.; но в численных расчетах он начал использоваться только после появления работы 1521. Метод основан на подборе такой бесконечной последовательности элементарных вращений, которая в пределе преобразует эрмитову матрицу А в диагональную. При этом используются преобразования вращения с матрицами (42) такого же типа, как и для прямого метода вращений, но последовательность поворотов н их углы подбираются совершенно иным способом.
Рассмотрим, как действует элементарное вращение на сферическую норму матрицы (точнее, квадрат этой нормы): 5 = ~~А ~й = '~зт ~ ац !з. (48) с1=! 1УЗ АЛГЕБРАИЧЕСКАЯ ПРОБЛЕМА СОБСТВЕННЫХ ЗНАЧЕНИИ [ГЛ, Ут Для определенности рассмотрим сначала умножение справа, В = =АУА1. Из формулы (43) видно, что при этом элементы Ьго и Ьго столбцов меняются так, что попарные суммы квадратов модулей сохраняются: ,'Ь1а/в+/Ь!1/а=)а1а/в+!ал~в, 1 =1' =л; элементы остальных столбцов остаются неизменными.
Отсюда следует, что ЕАУЕБ=~~А!1е, т. е, сферическая норма л1атрицы А не меняется при умножении справа на матрицу вращения. Аналогичное утверждение легко доказать для умножения на матрицу У или У" слева *). Описываемый метод основан на сохранении сферической нормы при вращениях. Разобьем сумму, входящую в сферическую норму (48), на диагональную и недиагональную части: 5,= ~ Рви(в, 5,= ~ )а11(в. (49) При элементарном преобразовании вращения УА1АУаг недиагональные элементы ам, а11 и ам, ал пРи 1~)т, ! менЯютсЯ так, что попарные суммы квадратов их модулей сохраняются; это легко видеть из формул (43) — (44).
Кроме этих элементов вне диагонали есть еще один меняющийся элемент — это а„1, Поэтому величина 5, меняется при элементарном вращении настолько, насколько изменится ( ам )а, Будем подбирать вращения так, чтобы 5, уменьшалась. Чтобы максимально уменьшить 5, за одно вращение, подберем угол поворота так, чтобы аннулировать элемент аав Для простоты ограничимся вещественными эрмитовыми (т. е.
симметричными) матрнцами. Тогда ам = ам — вещественные числа, и матрицы вращений (таг тоже вещественны. Из формул (44) и (43) с учетом вещественности всех величин следует са1 = Ьма + Ьлр = а„1 (а' — ра) + (ал — а,а) сф. (30) *) Это является частным случаем общего утверждения, которое мы не доказываем: сферическая норма любой матрицы не меняется при умножении с любой стороны на унитарную матрицу. Полагая сы=б и вспоминая условие нормировки (42), получим систему уравнений для определения параметров поворота ав+ра= 1 ам (ав — ра) = (ааа — ап) ар.
Возводя второе уравнение (30) в квадрат и исключая из него ра прн помощи первого уравнения, получим биквадратное уравнение 179 эомитовы млтгицы для определения са и' — а'+ а344а11 + (аль — аа) ~-' = О, св= — ~1+ . -), где р= 2 1 1'1+92/' аль — аи -. Г1,! 1 р=(з!япр) ь' — 11 — = — ) . )Г1+ 92 ) (51) Сами углы поворота находить не требуется, Итак, прн каждом вращении 5, уменьшается, а 5, соответствеипо увеличивается, поскольку 5 = 5,+ 5, сохраняется. Если подобрать такую последовательность вращений, чтобы 5,-+ О, то все недиагональные элементы после достаточного числа поворотов станут пренебрежимо малыми и матрица А преобразуется в диагональную.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
