Богачев - Практикум на ЭВМ. Методы решения линейных систем и нахождения собственных значений (947493), страница 15
Текст из файла (страница 15)
Согласно (1), (2) А(') = А('). В силу симметрии матрицы А(') вместо (2) для нее справедливо более точное равенство )/аг!) О ... О ап !)а1)( агг агз .. аг„ (1) (1) (О (1) ОО (г) пзг озз .. аз А = Тг ( .. (Тгз(ТгзАТгз)Т~4) ..)Тг„= (13) О аг аз О) ОО (О Таким образом, у матрицы А(") необходимо с помощью леммы 1 вычислить только подматрицу (а; ); . г „Е М„~ (так как остальные элементы уже вы()) числены). Пусть сделаны Й вЂ” 1, Й = 1,..., и — 1 шагов этого процесса, т.е.
матрица преобразована к виду (3), где А(" ') = (14) (й-1) (й -1) айй ... ай„ (й-й) (й-1) ай,,й ... ай „„ (й-1) (й 1) а„й ... а„„ Введем обозначение (5). Согласно лемме 12.3 существуют и — й — 1 матриц Тй~1, — — Тй~,, г(рйч., -), )' = й + 2,..., и таких, что справедливо равенство (6). (й) (й-г) с (й) , (й) Обозначим Ай+г = Тй-;1,й-~гА Тй+1,й-л Ай+з = Тй-н,й-~зАй~-гТй+1,и-з А(й) = Тйч.1„А( ),Т„'„,„. Все матрицы А(, у = й + 1,й + 2,...,и унитарно (й) с ' (й) подобны А(" ") и потому симметричны. Согласно (7), (9) А(й) = А(й). В силу симметрии матрицы А = Тй~ьи( (Тй+Ой+з(Тй-,1,к-~гА Т,, 1,й+г)Тй+1,й;-з) ..)Тй+Од (15) (й) , (й — г) с К.Ю.Богачев аы !)а~ (! !!ай агг' 1~аГЦ~! ~! Г!! Й !)а(1 ))( ~~ (й-з)~~ (й-г) ой, й, )!а~ )!) Точные методы решения линейных систем ~14. ПРИВЕДЕНИЕ МАТРИЦЫ К ПОЧТИ ТРЕУГОЛЬНОМУ ВИДУ 69 вместо (10) для нее справедливо более точное равенство А(") = (з) а„~„1 а(" ') (16) Таким образом, у матрицы А(ь) необходимо с помощью леммы 1 вычислить только подматрицу (сч );, з.11 „е м„ь 1 (так как остальные элементы уже (ь) вычислены).
После и — 2 шагов этого процесса (т.е. перехода от матриц (3), (14) к (15), (16)) матрица примет требуемый трехдиагональный вид (11), где )/а(1 ) )! (о — г) и и — 1,н — 1 (ч-2) ан„1 (и-2) аи„1 Н(и — 2) (напомним, определения векторов а1, й = 1,..., и — 2 даются в (о), где счи- (Ь-1) таем, что а1 = а1). (о) Оценка количества арифметических операций в алгоритме приведения симметричной матрицы к трехдиагональному виду унитарным подобием методом вращений Оценим трудоемкость и-го шага алгоритма, а затем просуммируем полученные оценки по всем й = 1,..., п — 2.
1. На вычисление и — й — 1 матриц То ь 11,..., Т~„, участвующих в (6), согласно лемме 12.2 требуется 4(п — Й вЂ” 1) мультипликативных, 2(и — Й вЂ” 1) аддитивных и и — Й операций извлечения корня. 2. На вычисление компонент й+ 1,... и й-го столбца и й-ой строки матрицы А(з), равных компонентам вектора ~~а~ ) ~~ е( ) требуется (для вычисления (з-1) ( -ь) К.Ю.Богачев Точные методы решения линейных систем а11 )(а1(! ~!аЛ агг' !1а1Ц ~! ~!п1 ~! пзз !)а(1 ) (/ ап !)а1!) !)а1!) агг !)а1 )( ~~а1'~!! азз !/а(1 )// /!а, )!/ (ь-1) аьь )(а(1 !) /!а(1 ) // а (и — 3) и — г,ч — г /!а(1 ) // !/а(1 // (й) (ь) аЬ,, 1Ь„, ... а~„,1„ (з) ' (з) ' нь+г,ь~-1 ож-12, '314. ПРИВЕДЕНИЕ МАТРИЦЫ К ПОЧТИ ТРЕУГОЛЬНОМУ ВИДУ 70 длины вектора (5)) п — Й операций умножения, п — Й вЂ” 1 операций сложения и одна операция извлечения корня.
й-й столбец и й-ая строка вычисляются именно этим способом для сокращения количества арифметических операций и уменьшения вычислительной погрешности. 3. Вычисления по формуле (15) можно представить как последовательное вычисление матриц А, ), 1 = й + 1, й + 2,..., и, у которых нужно вычислить (й) только подматрипу ((а, ); ),, й ~1 „е М„й 1.
Согласно лемме 1 на вычисле'(й)' ние каждой подматрицы требуется 4(п — й — 1) + 8 = 4(п — й) + 4 умножений и 2(п — )с — 1)+4 = 2(п — й)+2 сложений. На вычисление всех и — )с — 1 подматриц требуется, таким образом, (и — й — 1)(4(п — й) + 4) = 4(п — й)~ — 4 умножений и (п — Й вЂ” 1)(2(п — Й) + 2) = 2(п — Й)г — 2 сложений. Итак, на й-ом шаге алгоритма требуется выполнить 4(п — Й вЂ” 1) + (п — Й) + 4(п — й)г — 4 = 4(п — й)г+ 5(п — й) — 8 мультипликативных операций, 2(п — й— 1) + (и — Й вЂ” 1) + 2(п — Й) — 2 = 2(п — Й) — 3(п — Й) — 5 аддитивных операций и и — к операций извлечения корня.
Следовательно, всего для проведения алгоритма требуется выполнить Я(4(п — 1с)г+5(п — И) — 8) = 4(п(п — 1)(2п — 1)/6 — 1)+5(п(п — 1)/2 — 1) — 8(п — 2) й=1 3 = — и + 0(п ) + 0(п~) + 0(п) = — пг + 0(п ) (и — + оо) 3 мультипликативных операций, 2.й. ~(2(п — й)г — 3(п — й) — 5) = ~~из+О(пг) (и — + оо) адцитивных операций и 2 й,(п — Й) = О(п~) (п — + оо) операций извлечения корня (которые по трудоемкости по порядку можно сравнить с операциями деления). Таким образом, на приведение симметричной матрицы к трехдиагональному виду унитарным подобием методом вращений требуется Дпг + 0(и~) (п — + оо) мультипликативных операций и гйпг + 0(пг) (и -+ оо) алдитивных операций.
Заметим, что это количество операций в два с половиной раза меньше, чем требуется для приведения произвольной матрицы к почти треугольному виду унитарным подобием методом вращений и совпадает количеством операций, необходимым для решения линейной системы методом вращений.
Теорема 2. Всякол невырожденная вещесглвеннал симметричнвл матрица А можеги быть представлена в виде А = ЯВЯ', где матрица Я - ортогональная, а магприца В - трехдиагональная. Доказательство Совпадает с доказательством теоремы 1. Хранение матриц Я и В в памяти осуществляется одним из способов, изложенных при обсуждении алгоритма построения ЯВ-разложения для матрицы А методом вращений. Для симметричных матриц А удобно применять второй способ. Действительно, так как на шаге й, й = 1,...,и — 2 мы использовали п — й — 1 элементарных вращений Тй~~ й+.г,..., Тй~1 „для получения нулевых К.Ю.Богачев Точные методы решения линейных систем "315.
ПРИВЕДЕНИЕ МАТРИЦЫ К ПОЧТИ ТРЕУГОЛЬНОМУ ВИДУ 71 3 15. ПРИВКДЕНИК МАТРИЦЫ К ПО'ЧТИ ТРЕУГОЛЬНОМУ ВИДУ УНИТАРНЫМ ПОДОБИЕМ МЕТОДОМ ОТРАЖЕНИЙ Пусть требуется привести матрицу А (не обязательно вещественную) к почти треугольному виду. Всюду ниже мы будем часто пользоваться следующими фактами. 1. Если по произвольной матрице Ь/// е М/, (размера й х й) построить матрипу ед е М„(размера и х п) по формуле где Т„ь е Мн и — единичная матрица размера (и — Й) х (и — Й), то при умножении матрицы А на матрицу Ь/ слева изменяются только последние й строк матрицы А, а при умножении на Ь/ справа изменяются только последние й столбцов матрицы А.
Это следует из определения умножения матриц. 2. Если матрица ~4 Е Мь в (1) самосопряженная, то матрица П Е М„, полученная в (1), также самосопряженная. Это доказано при рассмотрении алгоритма метода отражений, см. (13.8). 3. Если матрица ~4 е Мь в (1) унитарна, то матрица П е М„, полученная в (1), также унитарна. Это доказано при рассмотрении алгоритма метода отражений, см. (13.9). 3 15.1. Случай произвольной матрицы Обозначим ад — — (а2д,..., а„д)'. Согласно лемме 13.9 существует вектор х(') е С", равный ад — //ад //ед ))ад — ))ад ()ед )( такой, что П(х('))ад = )/ад)/ед, где ед —— (1,О,...,О) Е С" ', П(х(')) Е М„д матрица отражения. Положим ('1 О д О 17(х(')) (2) К.Ю.Богачев Точные методы решения линейных систем элементов а ~ — — О, аь — — О, )' = й + 2,..., и, то можем хранить, например, (д) (й) сов /р~+д - на месте а ~ = О, а здп //дьдд — на месте а„= О.
Трудоемкость алгоритма построения описанного выше разложения складывается из количества арифметических операций, необходимых для проведения самого алгоритма, и количества арифметических операций, необходимых для построения матрицы Я. Подробные выкладки были проведены при обсуждении алгоритма построения ЧГт-разложения методом вращений. 315. ПРИВЕДЕНИЕ МАТРИЦЫ К ПОЧТИ ТРЕУГОЛЬНОМУ ВИДУ 72 Как отмечалось выше, матрица Пд является унитарной.
Умножим матрицу А на 11д слева, получим матрицу АО) вида (14.1) (поскольку первая строка матрицы А не изменяется). Умножим матрицу АО) на Ьдд* = Пд справа, получим матрицу (14.2) (с учетом того, что при умножении справа на 11д первый столбец матрицы АО) не изменяется). Пусть сделаны й — 1, й = 1,...,и — 1 шагов этого процесса, т.е. матрица преобразована к виду А~"-д) = ПП,АПП, (3) д=2 где А~ь ') имеет вид (14.4), д 1д 0 д 0 11(хдд) ) а, — )(а, ()ед Π— д) )( 0 — д) () дп — д) () где е~д ) — — (1,0,...,0) Е С™, Π— д), (д — д) Π— д),д ад — — (а; д;,...,а„; ) Е С Обозначим через а, часть первого столбца подматрицы (а;, );й д,ч, (д — д) (ь — д) см. (14.5). Согласно лемме 13.9 существует матрица отражения (ь-д) з дд-д) з д -ь) Цхд~)) =1 — 2хд~)(хд~))*, хд~) = ~ ' з ' з ' е С" ~, (4) (Ь вЂ” д) (! (д — Ц(! (ч — Ь))! такая,что дь)) ~ь — Ц ~) Од — Ц ~) дч — ь) (5) Положим 0 П(хь) (б) Как отмечалось выше, матрица Пь является самосопряженной и унитарной.
Умножим матрицу (3) на 1)ь слева, получим (7) где матрица А~~) имеет вид (14.8) Отметим, что в (7) первые й строк у матриц А~") и А~" ') совпадают. Другими словами, преобразование (7) заключается в К.Ю.Богачев Точные методы решения линейных систем здесь 1; Е М; — единичная матрица размера г х г, дд(хй)) Е М„д — матрица отражения размера (и — д) х (и — г), построенная по вектору Умножении матРиЦы с)(хй) Е М„й на поДматРиЦУ (а1 ); йч.1 „й „ма~й — Ц трицы А1й ') размера (п — й) х (и — 1+1) (остальная часть А1й ') в преобразовании (7) не участвует). Умножим матрипу А1й) на Пй = Пй справа, получим из (14.8) (с учетом того, что при умножении справа на Пй столбцы 1,..., й матрицы А1й) не изменяются) А1й) = А1й)Ц, = ПйА1й ') Пй, (8) где матрица А1й) имеет вид (14.10).
Отметим, что в (8) первые й столбцов у матриц А1й) и А00 совпадают. Другими словами, преобразование (8) заключается (й — Ц в умножении матрицы П(хй) Е М„й на подматрицу (а," );, „, й11 „матрицы А1й ') размера п х (и — й) (остальная часть А1й ') в преобразовании (8) не участвует). Вычисления по формулам (4) осуществляются следующим образом: вначале вычисляются числа нй = ~~~„~а й 1=й-~-2 (9) (10) затем — вектор 1й) 1й — Ц 1й-Ц 1й-Ц 1й-Ц х = (ай11й — /!а1 //,ай 2й,...,а„й ) е С и его норма (12) Теперь можно вычислить искомый вектор х1й) х1 ):= х1 )///х1 )!/, т.е.
х~~ ):= х~~ )/Цх1 )//, )' = 1,...,п — Й. (13) После и — 2 шагов этого процесса (т.е. перехода от матриц (3), (14.4) к (8), (14.10)) матрица примет требуемый почти треугольный вид (14.12), где 1 в — 2 В=А("-') = П П1АПП,. (14) Оценка количества арифметических операций в алгоритме приведения матрицы к почти треугольному виду унитарным подобием методом отражений Оценим трудоемкость и-го шага алгоритма, а затем просуммируем полученные оценки по всем й = 1,..., и — 2. 1. На вычисление матрицы П(хй) по формулам (4) требуется а) и — й — 1 умножений и и — й — 2 сложений для вычисления зй в (9); К.Ю.Богачев Точные методы решения линейных систем 315. ПРИВЕДЕНИЕ МАТРИЦЫ К ПОЧТИ ТРЕУГОЛЬНОМУ ВИДУ 73 315.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
