Богачев - Практикум на ЭВМ. Методы решения линейных систем и нахождения собственных значений (947493), страница 25
Текст из файла (страница 25)
3 9.1.3. Алгоритм построения ЯВ-разложения для трехдиагональной матрицы Рассмотрим случай, когда матрица А е М„в приведенном выше алгоритме трехдиагональная. Алгоритм построения ЯВ-разложения для трехдиагональной матрицы методом вращений !)ац) ги гы 0) 0) ае2 а2з Р) ()) а ее ааз А0) = Т~2А = (22) 0) а„,„ 0) 0) а„„, а„„ Далее процесс применяется к подматрице (а; ); (Ц) Методы нахождения собственных значений К.Ю.Богачев Обозначим а~ — — (ап, азь О,...,О)' Е Н," — первый столбец матрицы А. Согласно лемме1.12.3 существует матрица Т~2 — — Тн(рп), такая, что Тина~ = ~~а~ ~) е~ (причем значение угла <р~з определяется леммами 1.12.2, 1.12.3).
Умножим матрицу Аб на Т~г слева, получим матрицу ~9. ЯЛ АЛГОРИТМ 121 Пусть сделаны й — 1, й = 1,..., и — 1 шагов этого процесса, т.е. матрица преобразована к виду (2), где )(ад!) тдг тдг /!а(д )// тй-г,й-д тй-г,й ~(ад ~! тй д,й тй д,й.дд (й — 2) (й-1) (й-'Ц айй ай,и.! (й — Ц ай А(й ') = (23) (й — Ц а в — д,в — 1 (й-'Ц авв, (й — Ц ав, „ а(й ') Введем обозначение (4) для первого столбца подматрицы (ад ); й „. Со(й — Ц гласно лемме 1.12.3 сУЩествУет матРиЦа Тй й„д — — Тй й 11(йгй й.дд), такаЯ, что вылолено соотношение (5) (значения угла ддгй й.11 опредечяются леммами 1.12.2, 1.12.3).
Умножим матрипу (23) на Тй й.11 слева, получим (6), где А(") = )(ад!) тдг тдз !)а( д) )/ тй — 2,й — 1 тй — 2,й (й — 2) ~~ад ~~ тй й тй, й„., (й-1) ~! ~! (й) (й) ай11 „, ай 11 „„, (й) ойдг йдд 'в Од () т12 т13 ()а( ))) (25) тв 2в 1 тв 2в ~(4" '~! а(в Методы нахождения собственных значений К.Ю.Богачев а а() ав,в, ав,в (й)' (й)' Ов,в 1 Овв (24) Отметим, что в (6) матрица элементарного вращения Тй йч.д умножается только на подматрицу (а(~ ))„й „матрицы А(й ') размера п — й + 1 (остальная часть А(й ') в преобразовании (6) не участвует).
Следовательно, матрица А(") получается из А(" ') изменением двух строк (х-ой и (1+ 1)-ой) длины и — 1+ 1, имеющими не более трех ненулевых элементов. После и — 1 пдагов этого процесса (т.е. перехода от матриц (23) к (24)), матрица примет вид (8), где ~9. ЯЛ АЛГОРИТМ 122 (напомним, определения векторов а1 , Й = 1,...,п — 1 даются в (4), где счи(ь — 1) таем, что а1 —— а1). (а) Так как матрицы вращения ортогональные, то Т;,', = Т,„, и из (8) получаем искомое ЯВ-разложение (10). Хранение матриц Я и В в памяти. Матрица А хранится в виде трех векторов, задающих ненулевые диагонали матрицы. Матрица В хранится на месте матрицы А и получается из нее последовательным применением элементарных вращений (как описано выпте). Для хранения матрицы Я выделяются два вектора длины и — 1.
В первом векторе хранятся значения сов 1р;1+1, г = 1,2,..., и — 1, во втором векторе — значения з1п 1р„;.11, г' = 1, 2,..., и — 1. Оценка количества арифметических операций Оценим трудоемкость й-го шага алгоритма, а затем просуммируем полученные оценки по всем Й = 1,..., п — 1. 1. На вычисление матрицы Т11.11, участвующей в (6), согласно лемме 1.12.2 требуется 4 мультипликативные, одна аддитивная и одна операция извлечения корня. 2.
На вычисление компонент й,...,и й-го столбца матрицы А' ', равных (ь) (ь — 1) (и — й-~-1) компонентам вектора ~~а1 ~~ е, требуется (для вычисления длины вектора (4)) две операции умножения, одна операция сложения и одна операция извлечения корня. Столбец й вычисляется именно этим способом (а не по общим формулам (6)) для сокра1цения количества арифметических операций и уменыпения вычислительной погрешности. 3. Поскольку в формуле (6) матрица элементарного вращения умножается на подматрипу (а,, ); ь „,,=ьч.1,,„матрицы А(" ") размера (и — /с+ 1) х (п — й) (й-й столбец матрицы А(") уже вычислен в пункте 2), имеющими не более двух ненулевых элементов, то согласно лемме 1.12.5 на это требуется не более 4 2 = 8 умножений и 2 2 = 4 сложений.
Итак, на Й-ом шаге алгоритма требуется выполнить не более 4+ 2 + 8 = 14 мультипликативных операций, 1+1+4 = 6 аддитивных операций и две операции извлечения корня. Следовательно, всего для проведения алгоритма требуется выполнить не более 2 ~ 1'14 = 14(п — 1) мультипликативных операций, 6(п — 1) аддитивных операций и 2(п — 1) операций извлечения корня (которые по трудоемкости по порядку можно сравнить с операциями деления). Алгоритм построения ЯВ-разложения для трехдиагональной матрицы методом отражений Обозначим а1 — — (а11,ае1,0,...,0)' б Н," первый столбец матрицы А.
Согласно лемме 1.13.9 существует вектор х(') е С", вида (11), такой, что 1)(хи)а1 = ~~а1~)е1, где е1 — — (1,0,...,О) Е С", У1 = Цх01) — матрица отражения. Отметим, что у вектора х(') только первые две компоненты отличны от нуля. Следовательно, матрица У(х(') ) отличается от единичной матрицы только К.Ю.Богачев Методы нахождения собственных значений ~9.
ЯЛ АЛГОРИТМ 123 блоком 2 х 2, стоящим на главной диагонали. Умножим матрипу А на 1т(хтт)) слева, получим матрипу А0) = 17(хтт))А вида (22). Далее процесс применяется к подматрице (а; );,, 2,„,,„. (т) Пусть сделаны й — 1, й = 1,..., и шагов этого процесса, т.е. матрица преобразована к виду (12) где матрица А0т ') имеет вид (23), матрица Ц построена в (13).
Введем обозначение (4) для первого столбца подматрицы (ат, ); т. „. Сот/с — т) гласно лемме 1.13.9 существует матрица отражения (1.13.5) такая, что выполнено соотношение (1.13.6). Введем матрицу Ь~ вида (1.13.7). Соотношения (1.13.8) и (1.13.9) показывают, что матрица Пь унитарна и самосопряжена. Отметим, что у вектора хт~) в (1.13.5) только первые две компоненты отличны от нуля. Следовательно, матрица Ц, отличается от единичной матрицы только блоком 2 х 2, стоящим на главной диагонали. Умножим матрицу (3) на ать слева, получим (14), где А~") имеет вид (24). Отметим, что в (14) матРица Бть УмножаетсЯ только на подматРипУ (ат, )т, т, (ь — т) матрицы А~" ') размера п — 1+1 (остальная часть А~ь ') в преобразовании (14) не участвует).
Поскольку матрица 17ь отличается от единичной матрицы только блоком 2х 2, стоящим на главной диагонали в строках й и )с+1, то матрица Ат~) получается из Ат~ ') изменением двух строк (й-ой и (1+ 1)-ой) длины и — К+ 1, имеющими не более трех ненулевых элементов. После и шагов этого процесса (т.е. перехода от матриц (23) к (24)), матрица примет вид (20), где матрица Л имеет вид (25). Так как матрицы Бь унитарные и самосопряженные, то Е; т = Ь = Ц и из (20) получаем искомое ЯЛ-разложение (21). Хранение матриц Я и Л в памяти. Матрица А хранится в виде трех векторов, задающих ненулевые диагонали матрицы. Матрица Л хранится на месте матрицы А и получается из нее последовательным применением матриц отражения (как описано выпте).
Для хранения матрицы Я выделяются два вектора длины и. В первом векторе хранятся первые ненулевые компоненты векторов хй), г = 1,2,..., и, во втором векторе вторые ненулевые компоненты векторов хй), г = 1,2,...,и. Оценка количества арифметических операций Оценим трудоемкость й-го шага алгоритма, а затем просуммируем полученные оценки по всем Й = 1,..., и. 1. На вычисление матрицы 17(хт,) по формулам (1.13.5) требуется 1+1+1+2 = 5 мультипликативных, 1+ 1+1 = 3 аддитивные операции и 1+1 = 2 операции извлечения корня.
2. Компоненты й,...,п й-го столбца матрицы А~"), равные компонентам вектора ~~ат ~~~ е," ~ ), уже вычислены в (16). Столбец й вычисляется не по общим формулам (20) для сокращения количества арифметических операций и уменьшения вычислительной погретпности. К.Ю.Богачев Методы нахождения собственных значений ~9. ЯЛ АЛГОРИТМ 124 3. Поскольку в формуле (20) матрица 14 вида (1.13.5) умножается на матрипу А~ь 0 вида (23), то при вычислениях по (20) надо умножить матрипу отражения П'(х~"~) е М„ь~1 наподматрицу (а~~~ 0); ь „, ь~, „матрицы А~" 0 размера (п — й + 1) х (и — й) (й-й столбец матрицы А® уже вычислен в пункте 2). Поскольку матрица 7У(х~"~) отличается от единичной матрицы только блоком 2 х 2, стоящим на главной диагонали в строках 1 и 2, то то при вычислениях по (20) надо умножить матрицу отражения с"(х~"~) Е М„ь 1 на подматрицу (а; ); ьь~1 ь~1 „матрицы А размера 2 х (и — й), где в каждой строке (ь — 0 (й — 0 не более двух ненулевых элементов, Согласно лемме 1.13.11 на это требуется 2(2 2+ 1) = 10 умножений и 2(2.
2 — 1) = 6 сложений. Итак, на й-ом шаге алгоритма требуется выполнить 5+ 10 = 15 мультипликативных операций, 3+ 6 = 9 аддитивных операций и 2 операции извлечения корня. Следовательно, всего для проведения алгоритма требуется выполнить не более 2 ~, 15 = 15п мультипликативных операций, 9п аддитивных операций и 2п операций извлечения корня (которые по трудоемкости по порядку можно сравнить с операциями деления). 3 9.2.
ЯВ алгоритм нахождения собственных значений Будем строить для матрицы А Е М„последовательность (Аь) матриц Аь Е М„по следующим правилам: 1) А~ — — А; 2) для всех й = 1,2,... матрица Аь+1 получается из матрицы Аь следующим образом: а) строим ЯВ-разложение матрицы Аь. Аь = ЯьВь, б) вычисляем матрицу Аь~, как произведение матриц Пь и Яь. Аьч., —— ПьЮь. Лемма 1. Для всех й = 1,2,... матрица Аь унитарно подобна А. Доказательство. Имеем: Аьч.1 = ВьЯь = ЯЯь)ВЯь = ЩЯьйьЯь = Я~АЯь. Следовательно, матрица Аь~1 унитарно подобна Аь. Поскольку А1 —— А, то по индукции получаем, что Аь унитарно подобна А для всех /с = 1,2,..., причем Аь~1 —— ф...
ЩАЯь...Щ = (Яь... Я1)*АЩ... Я1). Следствие 1. Матрицы Аь, й = 1,2,... имеют те же собственные значения, что и матрица А. Теорема 1. (Без доказательства.) Пусть собственные значения (А;) матприцы А Е М„таковы, что ~л ~>~л ~>...>~л„~. К.1О.Богачев Методы нахождения собственных значений ~9. ЯЛ АЛГОРИТМ 125 Тогда в некотором смысле (детали выходятп за рамки настоятцего курса) Яь -+ 1 при Й вЂ” т со, Вь — т Аь при Й -+ оо. Тем самым диагональные элементы матрицы Аь — — (а~" ~) сходятпся к собстпвенным значениям матрицы А: (й) аи — т Л; при Й -+ со, т' = 1, 2,..., и при некотпором те (т.е.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
