Богачев - Практикум на ЭВМ. Методы решения линейных систем и нахождения собственных значений (947493), страница 16
Текст из файла (страница 16)
ПРИВЕДЕНИЕ МАТРИЦЫ К ПОЧТИ ТРЕУГОЛЬНОМУ ВИДУ 74 б) одно умножение, одно сложение и одна операция извлечения корня для вычисления ~~аь' )~~ в (10),: в) одно вычитание для построения вектора хьй) в (11): г) одно умножение, одно сложение и одна операция извлечения корня для вычисления !/х~й)// в (12); д) и — й делений для построения вектора хьй) в (13).
Всего для построения матрицы П(хй) требуется (и — й — 1)+1+1+ (и — й) = 2(п — й) + 1 мультипликативных, (и — й — 2) + 1 + 1 + 1 = п — й + 1 аддитивных операций и 1 + 1 = 2 операции извлечения корня. 2. Компоненты 1+1,..., и й-го столбца матрицы Аьй), равные компонентам ьй — ь) ьч — й) вектора ~)а~ ~(е~, уже вычислены в (10). Столбец й вычисляется не по общим формулам (7) для сокращения количества арифметических операций и уменыпения вычислительной погрешности. 3. Поскольку в формуле (7) матрица П(хй) Е М„й умножается на подматрицу (и)"; "))ь й.ь.ь „, й.ьь „матрицы Аьй ') размера (п — й) х (п — й) (й-й столбец матрицы Аьй) уже вычислен в пункте 2), то согласно лемме 13.11 на это требуется 2(п — й) + 0(п — й) (и -+ сс) умножений и столько же сложений.
4. Поскольку в формуле (8) матрица П(хй) е М„й умножается на подматрицу (а; ); — ь „,„,ь — й.ьь „матрицы А размера и х (п — й), то согласно ьй-ь) ьй — ь) лемме 13.11 на зто требуется 2(п — й)п+0(п — Й) (и -+ оо) умножений и столько же сложений. Итак, на й-ом шаге алгоритма требуется выполнить 2(п — й) + 1+ 2(ив й)~+ 2п(п — й) + 0(п — й) = 2п(п — й) + 2(п — й) + 0(п — й) мультипликативных операций, п — К+1+2(п — К)г+2п(п — И)+0(п — К) = 2п(п — )ь)+2(п — й) +0(п — й) адцитивных операций и 2 операции извлечения корня. Следовательно, всего для проведения алгоритма требуется выполнить и — 2 ~, (2п(п — й) + 2(п — й) + 0(п — й)) й=ь = 2п((п — 1)(п — 2)/2) + 2((п — 1)(п — 2)(2п — 3)/6) + 0(п ) = пг + 0(п ) + 2~из + 0(п ) = 5 из + 0(п ) (и — + оо) мультипликативных операций, столько же адцитивных операций и 2(п — 2) операций извлечения корня (которые по трудоемкости по порядку можно сравнить с операциями деления).
Таким образом,на приведение матрицы к почти треугольному виду унитарным подобием методом отРажений тРебУетсЯ ~зпг + 0(п~) (п -+ сс) мУльтипликативных операций и столько же аддитивных операций. Заметим, что это количество операций в два с половиной раза больше, чем нужно для решения линейной системы методом отражений. Теорема 1. Веякол невььрооьсденная матрица А моэьсет быть представлена в виде А = ЯВЯ~, где матрица Я вЂ” унитарная, а матрица  — верхнял почти треугольная. К.Ю.Богачев Точные методы решения линейных систем Доказательство. Проведем для матрицы А изложенный вьппе алгоритм, осуществимый для всякой невырожденной матрицы.
Обозначим в (14) » П П». Как произведение унитарных матриц, матрица Я унитарна. Тогда (14) »= — г имеет вид Н = ЯАф, откуда А = (ф»В(ф) ' = ЯВЯ', где Я = ®)' = ®) ' — унитарная матрица. Матрица В, имеющая вид (14.12), удовлетворяет условиям теоремы. Замечание 1. Как отмечалось вы»пе, построенное в теореме 1 разложение используется в ряде алгоритмов нахождения собственных значений матрицы.
Хранение матриц Я и В в памяти осуществляется одним из способов, изложенных при обсуждении алгоритма построения ЯР»-разложения для матрицы А методом отражений. Трудоемкость алгоритма построения описанного вьппе разложения складывается из количества арифметических операций, необходимых для проведения самого алгоритма, и количества арифметических операций, необходимых для построения матрицы Я. Подробные выкладки были проведены при обсуждении алгоритма построения ЯЛ-разложения методом отражений.
з 15.2. Случай самосопряженной матрицы Рассмотрим ситуацию, когда описанный выше метод приведения к почти треугольному виду применяется к самосопряженной матрице А е М„. Согласно (14.1), (14.2) А»»» = П»АП»', где Ь»» — унитарная матрица, т.е. А»»» и А — унитарно подобны. Следовательно, А»»~ — самосопряженная матрица. Согласно (7), (8) на й-ом (й = 1,..., и — 2) шаге алгоритма А® = 11~А»" »»Пъ», где Пь — унитарная матрица.
Следовательно, А~ъ~ и А унитарно подобны, и А~"~ — самосопряженная матрица для всякого й = 1,..., и — 2. Таким образом, В = А»" 㻠— почти треугольная н самосопряженная, т.е. трехдиагональная матрица. Запишем описанный выше процесс приведения самосопряженной матрицы к трехдиагональному виду так, чтобы максимально уменьшить объем вычислительной работы за счет использования симметрии. Лемма 1.
Для всякой матрицы оп»ражения П = с»(х) Е М„и всякой самосопряженной матрицы А Е Мъ матрица В = ПАП* = ПАП может быть вычислена за 2пг+ 0(п) умножений и столько же сложений. Доказательство. Поскольку Ь»(х) = 1 — 2хх", то В = (1 — 2хх*)А(1 — 2хх*) = (1 — 2хх*)(А — 2Ахх*) = А — 2Ахх* — 2хх*А+4хх*Ахх*. Обозначим (15) у = Ах Е С" К.Ю.Богачев Точные методы решения линейных систем ~1 О. ПРИВЕДЕНИЕ МАТРИЦЫ К ПОЧТИ ТРЕУГОЛЬНОМУ ВИДУ 75 В силу самосопряженности матрицы А имеем у = Ах = А*х = (х*А)*, 4хх'Ахх" = 2хх*Ахх* + 2хх'Ахх" = 2хх" ух* + 2ху'хх* В = А — 2ух' — 2ху'+ 2хх*ух* + 2ху*хх' = А — 2(1 — хх*)ух* — 2ху*(1 — хх") Обозначим я = 2(1 — хх*)у = 2у — х(х" у) = 2у — 2(х, у)х.
(16) Тогда В = А — ах* — хг* (17) После этих преобразований мы можем сформулировать алгоритм вычисления матрицы В: 1) Вычисляется вектор у по формуле (15). На это требуется па+ О(п) мультипликативных операций и столько же аддитивных операций. 2) Вычисляется вектор я по формуле (16). На вычисление а = 2(х, у) — удвоенного евклидова скалярного произведения, требуется и + О(1) мультипликативных операций и столько же андитивных операций; на вычисление я = 2у — ах требуется 2п мультипликативных операций и п аддитивных операций. Общее число операция, необходимое для вычисления вектора я Зп+ 0(1) мультипликативных и 2п + 0(1) а,пдитивных операций. 3) Вычисляется матрица В по формуле (17).
Матрица В как унитарно подобная А самосопряжена, поэтому по формуле (17) вычисляются только п(и+ 1)/2 элементов верхнего треугольника матрицы В. На вычисление каждого элемента матрицы В по формуле (17) надо выполнить 2 умножения и 2 вычитания, поэтому трудоемкость вычисления В по формуле (17) равна п(п+ 1) = и + 0(п) мультипликативным и п~ + 0(п) аддитивным операциям. Таким образом, этот алгоритм требует и +0(п)+Зп+0(1)+и +0(п) = 2п + 0(п) мультипликативных и столько же аддитивных операций.
Лемма доказана. Замечание 2. Для несамосопряженной матрицы А вычисление матрицы В = 17АП требует 4п + О(и) умножений столько же сложений (см. лемму 13.11). Обозначим а1 — — (а~1,..., а,п) . Согласно лемме 13.9 существует вектор х (0 С", равный 60 а1 — !)аг (/е1 !)а1 — ))а1 (/е1 )/ такой, что П(х0~)а1 = Д~а1Де1, где е1 — — (1,0,...,О) Е С" ', П(х~0) б М„1 — матрица отражения. Введем матрицу П1 как в (2) и вычислим матрицу К.Ю.Богачев Точные методы ретения линейных систем 315.
ПРИВЕДЕНИЕ МАТРИЦЫ К ПОЧТИ ТРЕУГОЛЬНОМУ ВИДУ 76 АО) = П1АП1. В силу самосопряженности матрицы АО) вместо (14.2) для нее справедливо более точное равенство а11 )(а1!) 0 ... О ~!п1~! пгг пгз пг (Ц (Ц 00 (Ц (Ц (Ц пзг пзз пз АО) = П1АП1 —— (18) 0 а„г а„з ... а„„ 10 11) (Ц Таким образом, у матрицы АО) необходимо с помощью леммы 1 вычислить только подматрицу (а;1 );, — г „Е М„1 (так как остальные элементы уже вы- (Ц числены) . Пусть сделаны Й вЂ” 1, Й = 1,...,п — 1 шагов этого процесса, т.е.
матрица преобразована к виду (14.3), где матрица А1й ') имеет вид (14.14). Введем обозначение (14.5). Согласно лемме 13.9 существует матрица отражения (4) такая, что выполнено (5). Определим Пй равенством (6). Вычислим матрицу А1~) = 17йА1" ')с1й. (19) Матрица А1й) унитарно подобна самосопряженной матрице А1й 1). Поэтому она самосопряжена и вместо (14.10) для нее справедливо более точное равенство (14.16). Таким образом, у матрицы А1й) необходимо с помощью леммы 1 вычислить только подматрицу (а; );, й„1 „Е М„й 1 (так как остальные эле(й) менты уже вычислены).
После и — 2 пгагов этого процесса (т.е. перехода от матриц (14.3), (14.14) к (19), (14.16)) матрица примет требуемый трехциагональный вид (14.17). Оценка количества арифметических операций в алгоритме приведения самосопряженной матрицы к трехдиагональному виду унитарным подобием методом отражений Оценим трудоемкость к-го шага алгоритма, а затем просуммируем полученные оценки по всем й = 1,..., п — 2. 1. На вычисление матрицы П(хй) по формулам (4) требуется 2(п — Й) + 1 мультипликативных, п — 1+ 1 аддитивных операций и 2 операции извлечения корня (см. вычисления при оценке количества арифметических операций в алгоритме приведения матрицы к почти треугольному виду унитарным подобием методом отражений). 2.