1626435584-7c6402f545ecf856225d6cf8d21519c9 (844233), страница 38
Текст из файла (страница 38)
Рассмотрим его. Произведем в п-мерном векторном Рис. 31. пространстве отражение относительно некоторой гиперплоскости, проходящей через начало координат. Преобразование полностью определяется заданием нормали аг к гиперплоскости. Эта нормаль есть нормированный вектор-столбец а а,наз 'Ч~~ шею. 1 (23) г=1 где аг" есть вектор-строка, эрмитово сопряженный к столбцу. Возьмем произвольный вектор у и разложим его на две составляющие: параллельно нормали у,=тег(а~, у) и перпендикулярно ей. При отражении вектора его перпендикулярная составляющая остается неизменной, а параллельная — меняет знак (рис.
31), поэтому отраженный вектор е отличается от исходного на удвоенную величину параллельной компоненты г =у — 2аг (а~, у). (24) Зго преобразование вектора можно записать в канонической форме умножения на матрит(у отражения Й: г = )су, )с = Š— 2агтвн, (25) *) Практически все описанные в 44 2 — 3 методы хорошо применимы к матрипам, порядок которых не превышает сотни. Для матриц произвольного типа с л) 100 удовлетворительных методов решения общей проблемы собственных значений пока нет, 171 ЭРМИТОВЫ МАТРИЦЫ $2! где умножение столбца то справа на строку той же длины тон дает, по правилам умножения прямоугольных матриц, квадратную матрицу.
Заметим, что равенства (24) — (25) в координатной форме записываются следующим образом: а 22 = Рг — 2%2 ~~„гц";Ум 1=1 )сгу = бу — 2в,гц';. Исследуем свойства матрицы отражения. Эта матрица эрмитова, что непосредственно вытекает нз следующей цепочки преобразований: Ни (Е 2плцн)и Е 2 (тцн)нтцн Е 2 гци (( (от) Возведем матрицу отражения в квадрат: )72 = (Š— 2цмци) (Š— 2ПЗПЕ~Г) = Š— 4олцн+ 4цжци тцтци Преобразуем последний член правой части, используя ассоциативность умно. женил матриц и условие нормировки (23); н н,„(,„н ) н и Тогда последний член сократитсл с предпоследним, и мы получим (7((= Е, или зЧ=((-з, (28) т.
е. матрица отражения равна своей обратной. А сравнивая (27) и (28), убедимся, что Я =)7, так что матрица отражений унитарна. н Последнее свойство для нас наиболее важно, поскольку для эрмитовых матриц наиболее выгодны унитарные преобразования подобия. В $ 1 было показано, что они сохраняют эрмитовость матрицы.
Поэтому если мы унитарным преобразованием подобия приведем матрицу к верхней почти треугольной форме, то в силу зрмитовосги она будет трехдиагональной, Заметиьг, что произведение любого числа унитарных матриц есть также унитарная матрица. В самом деле, если матрицы У, г', ..., Ит унитарны, то ((7у йу)-з=йт-' и'(7-'=три 1нии=(ир йг)и. Поэтому если лгы применяем к эрмитовой матрице последовательность унитарных прсобразованвй подобнл, то она эквивалентна одному результирующему унитарному преобразованию подобия, и эрмитовость матрицы сохраняется, Покажем, что для произвольной матрицы А можно подобрать такую конечную последовательность отражений, которая приводит матрицу к верхней почти треугольной форме.
Для этого очередное отражение должно уничтожать самый длинный ненулевой столбец в нижней части матрицы А. Действие первых двух отражений показано на рис. 32, где жирными точками обозначеяы ненулевые элементы матрицы, а кружками — нулевые; третье отражение обращает в нуль обведенные элементы третьего столбца. Будем считать, что уже уничтожен е) — ! столбец, и разобьем матрицу Л на клетки, как показано на рис.
32. Квадратная клетка Л, есть верхняя почти треугольная матрица, а в прямоугольной клетке Аа только последний столбец отличен от нуля. 172 АЛГЕБРАИЧЕСКАЯ ПРОБЛЕМА СОБСТВЕННЫХ ЗНАЧЕНИИ !ГЛ Ш Сделаем отражение при помощи вектора твз =(шз~, у которого первые д компонент нулевые: взз = О при 1 =- д (дальше верхний индекс вектора будем обычно опускать).
Тогда видно, что если матрицу отражения разбить на клетки того же размера, что у матрицы А, то недиагональные клетки будут нулевыми.' ° о ° ( ° ° ° ° ° ° ° ' ° ° ° ° 1 о о ° ! ° ° ° ° з о о ° 1 ° ° ° ° К=В '=~ (29) !и-у йтц=б;,— 2сазгв*;, о ой!1 ° о ° ° о оз ° ° о ° 1 оо ~ ° ° ° ° а + 1 =-" 1; 1 ( и. Из курса линейной алгебРис. 32. ры известно, что если матрицы одинаковым образом разбиты на клетки, то они перемножаются по таким же формулам, как если бы этн клетки были обыкновенными элементами. Тогда искомое преобразование подобия принимает следующий вид: ( О Нз1 !Аз А41 ~ О: Б71 ~азАз ' азАзаз ! Левая верхняя клетка результирующей матрицы В имеет нужную нам форму — верхнюю почти треугольную. Поскольку у клетки А, только последний столбец отличен от нуля, то у клетки В,='йзАз элементы последнего столбца равны бзз=а„— сзшн а+1=-.1(и, (31) где а=2 ~х, 'се,*а;з; 1=-о+1 (32) остальные же элементы этой клетки равны нулю.
Нам надо так подобрать вектор тв, чтобы обратились в нуль все элементы столбца (31), кроме верхнего. Очевидно, для этого надо положить азз = а;з/и при з)+ 2 -.= ( =. и (33) и найти, чему равна постоянная а. Заметим, что умножение вектора а~ на множитель ео не меняет матрицы отражения; тогда из (32) следует, что и также определена только с точностью до этого множителя. Рго всегда можно выбрать так, чтобы сз была вещественной положительной, что будем предполагать выполненным, 173 $2] ЗРМИТОВЫ МАТРИЦЫ Из (31) следует, что де + =(а + д — Ьд д д)/сд, (34) Подставляя (33) — (34) в условие нормировки (23), получим сдд = ~~ (а,д )д+-) Ьд+ д (д — (Ьд.ь1 даддд д+ Ьддь дадч ь д). (35) д=д+! Подстановка тех же выражений в формулу (32) дает (38) яд=2 ~" ~а,дР— 2Ь,"< 1 дадд, д.
(36) д=д+ ~ Последнее слагаемое в правой части этого равенства должно быть вещественным, поскольку остальные члены вещественны. Поэтому должно выполняться соотношение агнЬ;ч ~ д=пй — агнад,,ъд. где й — любое целое число. Для улучшения счетной устойчивости алгоритма выгодно полагать й = .+'1: тогда последний член в правой части (36) будет положительным, и величина а никогда не станет близкой к нулю.
Таким образом, агнЬд, д — — и+агапдд, (37) Учитывая этот выбор аргумента и приравнивая друг другу правые части равенств (35) и (36), получим ) Ьддъд ~= ч, ')ад), д=д+1 Заменяя в (36) сумму при помощи равенства (38) и учитывая (37), упростим выражение для ол а=12)Ьд+, д)((Ьдд ~+)ад, д()1цд. (39) Формулы (37) — (39) и (33) — (34) полностью определяют матрицу очередного отражения. Эти формулы составлены так, что для вещественной матрицы А при вычислениях не возникает комплексных величин, а формула (37) для вычисления аргумента принимает при этом вид з(нп Ь,.„, д — — — з1нп пд Последовательно полагая д=1, 2, ..., а — 2, определяя соответствующие векторы дддд и производя отражения, мы приведем произвольную матрицу А к верхней почти треугольной форме. Если исходная матрица А была эрмитова, то результирующая матрица будет трехдиагональной. Рассмотрим, как экономно организовать вычисления.
Формулы для определения матрицы отражения не требуют большого объема 174 АлгеБРАическАя НРОБлемА сОБстненных знАченил [Гл. Б1 расчетов. Основное число действий уходит на перемножение матричных клеток в формуле (30). Заметим, что клетка А, не меняется, а в клетке В„=(Р'А, имеется только один ненулевой элемент Ь .„, „уже вычисленный при нахождении матрицы отражения; следовательно, эти клетки не нужно специально вычислять.
При нахождении остальных двух клеток умножение на матрицу отражения (Р' надо выполнять специальным образом; например, умножим А, на УР' справа, тогда А,(Р = А, (Š— 2чптвп) = А, — 2 (А,яп) япн. (40) Вместо того, чтобы перемножать две матрицы, мы пользуемся ассоциативностью умножения и сводим вычисление к двукратному умножению матрицы на вектор, что примерно в л раз быстрее. Умножение на (Р' слева выполняется аналогично. Заметим, что если матрица А эрмитова, то возможна дополнительная экономия; тогда В, =- Вз и В,. = Вз, так что клетку В., можно вообще не вычнсн н лять, а в клетке В, достаточно найти только нижнюю половину элементов.
Устойчивость численного алгоритма теоретически исследована недостаточно. Однако практика вычислений показала, что преобразования унитарными матрицами достаточно устойчивы. Поэтому основное, на что надо обращать внимание, — это чтобы ошибки округления не сказались бы на унитарности матриц отражения. Для контроля следует проверять выполнение условия нормировки (23); если оно соблюдается с очень высокой точностью (верны почти все двоичные разряды), то устойчивость обычно хорошая. Когда матрица А приведена к трехдиагональной (нлн верхней почти треугольной) форме, то для этой формы собственные значения )ч и собственные векторы у~ находятся легко. Найденные собственные значения одновременно являются собственными значениями исходной матрицы А.
Для нахождения собственных векторов х, исходной матрицы надо применить преобразование отражения х1 (й1й2 ' ' ') — 2)У!' Вычисления по этой формуле также надо делать экономично, выполняя каждое умножение на очередную матрицу )1 как два умножения на вектор по формуле (24). Подсчет числа операций показывает, что для эрмитовых матриц метод отражения позволяет найти все собственные значения примерно за ((4(3) и'+50п') арифметических действий, а все собственные векторы — еще за (2п'+1Оп') действий. Это самый быстрый из известных методов.
Его скорость настолько велика, что позволяет на ЭВМ класса БЭСМ-6 вести расчет для матриц порядка и 100; фактическую границу его применимости определяет устойчивость, которая при расчете с обычной точностью 17Б ЭРМИТОВЫ МАТРИЦЫ 4 г1 теряется при меньших значениях п (расчет с двойным числом знаков более устойчив, но и более трудоемок).
К сожалению, метод отражений не дает дополнительной экономии в случае ленточных и других аналогичных специальных структур матриц, потому что такие структуры не сохраняются в процессе расчета. Для неэрмитовых матриц метод отражения менее выгоден, ибо результирующая матрица является верхней почти треугольной, а для нее описанный в 2 1 метод нахождения собственных значений. довольно трудоемок.
В итоге такой подход требует около 13п' арифметических действий для вычисления всех собст- ВЕННЫХ ЗНаЧЕНИй И ЕЩЕ (972) из ДЕйетннй ДЛЯ НаХОжДЕНИЯ ВСЕХ собственных векторов. Зато численная устойчивость алгоритма хорошая. 2. Прямой метод вращений. Этот метод немного уступает по скорости ме. тод> отражений, однако формулы расчша в нем несколько проще. Он также устойчив и позволяет привести преобразованием подобия неэрмитову матрицу к почти треугольной форме, а эрмитову — к трехдиагональной, Метод основан на специально подобранном вращении координатной системы. Поэтому исследуем свойства вращений.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
