Богачев - Практикум на ЭВМ. Методы решения линейных систем и нахождения собственных значений (947493), страница 13
Текст из файла (страница 13)
К.Ю.Богачев Точные методы решения линейных систем ~13. МЕТОД ОТРАЖЕНИЙ 00 (см. (10), (20)). Матрица 14 вида (5) умножается по алгоритму из леммы 11 на матрицу Я произвольного вида за 2п(п — 1+1)+О(п) = 2п(п — й)+О(п) (и -+ со) умножений и такого же количества сложений (поскольку для вычисления произведения ЯГ~ матрицы Я на матрицу Г~ вида (5) надо вычислить произведение подматрицы (щ~);, „~ ь „размера п х (п — Й+ 1) на матрицу отражения Г(х~~)) Е М„д+1 размера (п — й + 1) х (и — й + 1) ).
Следовательно, произведение п матриц отражения в (20) может быть вычислено за ~~,(2п(п — й) + 0(п)) = 2пп(п — 1)/2 + 0(п2) = пз + 0(п2) (и -+ со) умножений и столько же сложений. 2. Как и в первом способе, матрица В хранится на месте верхнего треугольника матрицы А. Для хранения же матрицы Я отдельная память не выделяется. Заметим, что на шаге й, й = 1,..., и мы использовали матрицу Уь, получающуюся в (7) из матрицы отражения У(х~~) ), которая в свою очередь целиком определяется вектором х~~) е С" "+' из (5).
При этом после преобразования (10), т.е. перехода от матрицы (3) к матрице (11), в й-ом столбце матрицы А~") образовались и — й нулевых элементов а~~~) = О, 1 = й+ 1,..., и. Поэтому возможно (й) вместо матрицы Ч вида (20) хранить на месте нижнего треугольника матрицы А набор векторов х~"), й = 1,..., п, задающий матрицы отражения У(х®). Формула (14) подсказывает удобный способ организации такого хранения: на (й) (й- Ц 00 (ь- Ц (й) (й — 1) шаге и х, = аьь,...,х„ь, = а„ь, а элемент аьь — — ~~а, ~! хранится в виде (й — 1)-ой компоненты дополнительного вектора П. В итоге после и шагов процесса на месте исходной п х и матрицы А и дополнительного вектора П длины п будет находиться следующая информация: верхний треугольник матрицы В: т; =а;,, в <у,г =1,...,п,у =2,...,п,диагональматрицы В: та = д;, г = 1,..., п, набор векторов х, й = 1,..., и, х, = аьь,..., х„„,, = ань.
При втором способе хранения матрицы Я не только экономится из ячеек памяти, но и экономится из+ 0(п2) (и -+ со) умножений и такое же количество сложений на построение матрицы Я. Второму способу хранения благоприятствует также то обстоятельство, что редко требуется знать матрипу Я "саму по себе". Обычно требуется уметь вычислять ее произведения на вектор и матрицу. Для того, чтобы вычислить произведение матрицы Я вида (20) на некоторую матрицу В требуется вычислить ЧВ = П (Б;В) .
На это нужно из+0(пх) (п — ~ со) в=1 умножений и столько же сложений (см. подсчет количества операций при рассмотрении первого способа хранения, в котором фактически вычислялось произведение матрицы вида (20) и единичной матрицы). Это количество совпадает с количеством арифметических операций, необходимых для вычисления произведения двух матриц Я и В произвольного вида. В силу этого почти всегда используется второй способ хранения матрицы Я. К.Ю.Богачев Точные методы решения линейных систем ~13. МЕТОД ОТРАЖЕНИЙ 61 З 13.5. Оценка количества арифметических операций в алгоритме построения ЯН-разложения методом отражений Трудоемкость алгоритма построения ЯЛ-разложения складывается из количества арифметических операций, необходимых для проведения алгоритма метода отражений, и количества арифметических операций, необходимых для построения матрицы Я.
Если для Я используется второй способ хранения, то дополнительных действий для ее построения не требуется. Следовательно, в этом случае для построения ЯВ-разложения надо выполнить ~~из+О(тР) (и -э сс) мультипликативных операций и такое же количество аддитивных операций. Если для Я используется первый способ хранения, то как показано выше для ее построения дополнительно к 1~пз + 0(пя) (п — + ос) мультипликативным и 1заз + 0(п') (и -+ ос) аддитивным опеРациЯм, необходимых длЯ пРоведениЯ алгоритма метода отражений, требуется па+ 0(пз) (и -+ сс) умножений и пз+ 0(п ) (п -+ ос) сложений, всего —,и + 0(п ) (и — + ос) мультипликативных и столько же аддитивных операций. Приведение матрицы к почти треугольному виду унитарным подобием Определение.
Матрица В называется подобной матрице А, если существует невырожденная матрица С такая, что А = С В С '. В курсе алгебры доказывается, что подобные матрицы имеют один и тот же набор собственных значений. Определение. Матрица В называется унитарно подобной матрице А, если матрица С в определении вьппе унитарная. И силу свойства 6 числа обусловленности (см. з3) у унитарно подобных матриц числа обусловленности совпадают.
Поэтому именно преобразование унитарного подобия будет вносить наименыпую вычислительную погрешность. Отметим еще одно свойство унитарного подобия: если матрица А самосопряженная, то унитарно подобная ей матрица В также самосопряженная. Действительно, В* = (САС ')' = (С ')*А*С* = САС ' = В. Рассмотренные выше алгоритмы решения линейных систем работали единообразным способом: они приводили исходную матрипу к более простому виду (треугольному) с помощью преобразований, сохраняющих решение системы; затем решение системы с более простой матрицей находилось в явном виде. Пусть стоит задача найти собственные значения матрицы. Попробуем действовать по той же схеме: приведем исходную матрицу к более простому виду с помощью преобразований подобия, сохраняющих собственные значения; затем для этой более простой матрицы тем или иным способом найдем ее собственные значения, которые совпадают с собственными значениями исходной матрицы.
Для того, чтобы вносить меныпую вычислительную погрешность, будем использовать преобразования унитарного подобия. К.Ю.Богачев Точные методы решения линейных систем 314. ПРИВЕДЕНИЕ МАТРИЦЫ К ПОЧТИ ТРЕУГОЛЬНОМУ ВИДУ 62 Простейпзее рассмотрение алгоритмов метода вращений и отражений показывает, что вид этой более простой матрицы не может быть треугольным. Действительно, пусть, например, в методе вращений при умножении на матрипу Тзг слева элемент (2, 1) исходной матрицы становится равным нулю. Тогда при умножении на матрицу Т1г = Т,'г справа этот элемент может измениться и перестать быть равным нулю. Определение.
Матрица А = (а; ) называется почти треугольной, если а; О при з)у+1, )'=1,...,п — 2, з'=З,...,п. Оказывается, всякую матрицу можно привести к почти треугольному виду с помощью унитарного подобия. 3 14. ПРИВЕДЕНИЕ МАТРИЦЫ К ПОЧТИ ТРЕУГОЛЬНОМУ ВИДУ УНИТАРНЫМ ПОДОБИЕМ МЕТОДОМ ВРАЩЕНИЙ Пусть требуется привести вещественную матрипу А к почти треугольному виду. Всюду ниже мы будем часто пользоваться тем фактом, что при умножении матрицы А на матрицу элементарного вращения Т; слева изменяются только строки з и )' матрицы А, а при умножении на Т;, справа изменяются только столбцы з' и )' матрицы А. 3 14.1.
Случай произвольной матрицы Обозначим а1 — — (аг1,..., а„1)'. Согласно лемме 12.3 сугцествуют п — 2 матриц Тг — — Тг;(~рг ), г = З,...,п, таких, что Тг„...Тг4Тгза1 —— ~~аз~(е, (причем значения углов риаз, у = 3,...,п определяются леммами 12.2, 12.3). Умножим матрицу А на Тг„...ТгзТгз слева, получим а1„ -(г) аг -(з) аз ап азг ()а1 )! а(,) -(з) О азг А( ) = Тг„... Тг4ТгзА = О а„ - (1) "(з) а„„ К.Ю.Богачев Точные методы регнення линейных систем Умножим матрицу Ар~ на (Тг„...ТгзТгз) = ТгзТгз...Т справа, получим (с учетом того, что при умножении справа на Тг,, з' = 3,...,и первый столбец 314.
ПРИВЕДЕНИЕ МАТРИЦЫ К ПОЧТИ ТРЕУГОЛЬНОМУ ВИДУ 63 матрицы А(') не изменяется) А = А ТгзТгз ° .. Тг„—— (2) О а„г ... а„„ (Ц (Ц Пусть сделаны Й вЂ” 1, Й = 1,..., и — 1 шагов этого процесса, т.е. матрица преобразована к виду г 44-1 -4" ' = П П Т*'4 П П Т( (3) оп сгг с1з А(й ') = (й-2) (й-Ц ~й-1,й-1 ~й- 1,й (й — 2) ~~ (й-1) (й — Ц ай4.1,й (4) (й — Ц а„й а(й ') Обозначим (й — Ц 1 (й — Ц (й — Ц11 11я — й а1 = (айй,...,а„й ) Е (5) -- часть первого столбца подматрицы (а11 ); й „. Согласно лемме 12.3 су(й — Ц Шествуют и — й — 1 матриц Тй4.1, — — Тй„1;2(4рй4.,;), ) = Й+ 2,...,п таких, что (й — Ц (й — Ц (и — й) Тй+1,~...
Гй11,й+зТй+1,й+го1 ~~01 ~) е1 (б) (значения углов <рй4.1,1, 1 = й+ 2,..., и определяются леммами 12.2, 12.3). Умно- жим матрипу (3) на Тй4.1 „... Тй„1 й4.зТй4.1,й4.2 слева, получим й4-2 А(') = П Тй„3А('-Ц, К.Ю.Богачев Точные методы решения линейных систем ~!о1~! огг сгз (Ц !1о1' ~! взз )(а(1 ) !) (Ц ап а12 !)а1)( агг а (Ц С1й 1 С2й 1 СЗ,й — 1 (й-Ц О1й (й — Ц ай (й — Ц азй (Ц а1„ (Ц аг„ (Ц аз (й — Ц а„, (й — Ц аг (й — Ц аз (й — Ц ай, „ (й-1) ай„ (й — Ц ай„й „ ~14. ПРИВЕДЕНИЕ МАТРИЦЫ К ПОЧТИ ТРЕУГОЛЬНОМУ ВИДУ 64 где ам сгг сгз С1,й 1 С2й 1 СЗ,й — 1 сгй сгй сзй 1й-2) ай , й , сй 1 й 199 1й — 2] )) 1й — Ц -1й) -1й — Ц и„й„, ...
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
