Богачев - Практикум на ЭВМ. Методы решения линейных систем и нахождения собственных значений (947493), страница 26
Текст из файла (страница 26)
порядок собственных значении можетп нарушатпься) ь Скорость сходимости матрицы Аь к тпреугольноа имеетп порядок О л,. но нельзя утверждать, что а;, =Π— при к-тес, 1)1. (л, "') Замечание 1. (Без доказательства). Если для матрицы А осуществим ЬВ- алгоритм, то при применении ЯВ-алгоритма собственные значения А получаются в правильном порядке аа — т Л; при й — т оо, т= 1,2,...,тц и скорость сходимости матрицы Аь к треугольной дается соотношением а; =Π— при к — ~со, т>3.
(л, "~ Замечание 2. ЯЛ-алгоритм сходится при сутцественно менее ограничительных условия, чем зто указано в теореме 1. Применение алгоритма к матрице А е М„произвольного вида требует слишком большого числа арифметических операций (Спз + О(п ), константа С зависит от метода построения ЯВ-разложения). ~ Я.2.1. ЯЛ, алгоритм нахождения собственных значений для почти треугольной матрицы Лемма 2.
Если матрица А — — почти треугольнал, то все матрицы Аь, й = 1,2,... в бгК-алгоритме — — почти тпреугольные. ч — 1 ч Доказательство. Согласно (10) или (21) Я = П Т,';, или Я = П Ц (по ;=1 в=1 утверждаемой в теоремах 1.12.1) и 1.13.1) единственности ЯЛ-разложения зти матрицы совпадают). Если матрица А — почти треугольная и А = Я — ее ЯН-разложение, то матрица ВЯ будет почти треугольной, так как умножение треугольной матрицы Н на матрипу Т; „, или Ц справа заменяет ее т-й и т'+ 1 К.Ю.Богачев Методы нахождения собственных значений ~9. ЯЛ АЛГОРИТМ 126 столбцы на их линейную комбинацию, что в результате дает почти треугольную матрипу. Эта лемма позволяет значительно ускорить работу ЯВ-алгоритма.
Перед его применением исходная матрица А приводится к почти треугольному виду А' унитарным подобием одним из алгоритмов, описанных в 3 1.14 и 3 1.15. Затем к матрице А' применяется ЧВ-алгоритм. Оценка количества арифметических операций на один шаг ЯН-алгоритма для почти треугольной матрицы для метода вращений 1) Построение ЯВ-разложения матрицы Аь — — ЯьВк требует 2п'+0(п) (и — з сс) мультипликативных операций, п" + 0(п) (п -+ оо) аддитивных операций и Г) (и) (п -+ оа) операций извлечения корня (которые по трудоемкости по порядку можно сравнить с операциями деления). 2) Подсчитаем затраты на вычисление произведения (10). Так как умножение треугольной матрицы В на матрицу Т,',+, справа изменяет ее г-й и г + 1 столбцы, имеющие не более г+ 1 ненулевой элемент, то согласно лемме 1.12.5 на это требуется 4(г+ 1) умножений и 2(г+ 1) сложений. Следовательно, на вычисление произведения (10) требуется ~," 1' 4(1+ 1) = 4п(п+ 1)/2 = 2п + 0(п) (и -+ оо) мультипликативных операций и ив + 0(п) аддитивных операций.
Следовательно, один шаг алгоритма для почти треугольной матрицы требует 4и2 + 0(п) (и -+ оо) мультипликативных и 2п2+ 0(п) (и -+ со) аддитивных операций. Оценка количества арифметических операций на один шаг Ч)г-алгоритма для почти треугольной матрицы для метода отражений 1) ПостРоение ЧВ-РазложениЯ матРицы Аь = ЯьВн тРебУет (5/2)пт + 0(п) (и — + со) мультипликативных операций, (3/2)из+ 0(п) (и -+ оо) аддитивных операций и 0(п) (и + со) операций извлечения корня (которые по трудоемкости по порядку можно сравнить с операциями деления). 2) Подсчитаем затраты на вычисление произведения (21).
Так как умножение треугольной матрицы В на матрицу Ц справа изменяет ее г-й и 1+ 1 столбцы, имеющие не более г + 1 ненулевой элемент, то Согласно лемме 1.13.11 на это требуется 5(1+1) умножений и 3(1+1) сложений. Следовательно, на вычисление произведения (21) требуется ~,", 5(г + 1) = 5(и + 1) (п+ 2)/2 = (5/2)п~ + 0(и) (и — ~ сс) мультипликативных операций и (3/2)п2+ О(п) аддитивных операций. Следовательно, один шаг алгоритма для почти треугольной матрицы требует 5и2 + 0(п) (и — ) оо) мультипликативных и 3п2+ 0(п) (и — ) ос) аддитивных операций.
3 9.2.2. ЯЛ алгоритм нахождения собственных значений для самосопряженной трехдиагональной матрицы К.Ю.Богачев Методы нахождения собственных значений ~9. ЯВ АЛГОРИТМ Лемма 3. Если матрица А — самосопряженноя, то все магприцы Аь, 1с = 1, 2,... в ЯВ-алгоритме — самосопряженные. Доказательство. Действительно, пусть Аг = ЯьВь — самосопряженная, т.е. А„' = В~Я*„= Аь.
Тогда Аь+1 — — ВЯь и в силу унитарности Яг имеем А*„, = а~В~' а — 1В~ а — 1ВФМ вЂ” 1а ) а — 1(В~а~)а а — 1А~Ю а — 1А а матрипа Аь+1 унитарно подобна самосопряженной матрице Аь и потому само- сопряжена. Лемма 4. Если матрица А самосопряженная трехдиагональнац то все матрицы Аь, й = 1,2,... в ОВ-алгориьпме самосопрхнсенные трехдиагональные.
Доказательство. Всилулеммы 3 все матрицы Аь, й = 1,2,... самосопряженные. Поскольку трехдиагональная матрица А является почти треугольной, то в силу леммы 2 все матрицы Аь, й = 1,2,... почти треугольные. Итак, для всякого Й = 1,2,... матрица Аь является самосопряженной и почти треугольной, и, следовательно, трехдиагональной. Эти леммы позволяют значительно ускорить работу ЯВ-алгоритма для самосопряженной матрицы. Перед его применением исходная матрица А приводится к трехдиагональному виду А' унитарным подобием одним из алгоритмов, описанных в 3 1.14 и 3 1.15. Затем к матрице А' применяется ЧВ-алгоритм. Шаг ЯВ-алгоритма для самосопряжениой трехдиагоиальиой матрицы Для целей ЯВ-алгоритма описанное вьппе построение ЯВ-разложения для трехдиагональной матрицы (см. стр.
120) может быть значительно ускорено. 1) В матрице В (25) элементы гш, гы,..., г„г „не вычисляются и не хранятся, поскольку, если А = ЯВ самосопряженная трехдиагональная, то матрипу ВЯ можно вычислить, не используя эти элементы. Действительно, поскольку при переходе от матрицы А~" 0 (23) к матрице А® (24) изменяются только й-я и (й+ 1)-я строки матрицы А~" '~, то невычисление элемента ге ь+г не окажет влияния на остальные элементы матрицы и — 1 а А~"~.
Далее, согласно (10) или (21) Я = П Т~~,, или Я = П Гь, а умной=1 й=1 жение В на Т„'я „, или Б'ь справа изменяет только й-й и (й + 1)-й столбцы матрицы В вида (25). Поэтому нижний треугольник произведения ВЯ можно вычислить, не используя элементы г,;+г, 1 = 1,2,...,п — 2. По лемме 4 матрица ВЯ вЂ” самосопряженная, поэтому ее верхний треугольник получается из нижнего транспонированием и комплексным сопряжением. Это наблюдение всегда используют при реализации ЯВ-алгоритма для самосопряженной трехдиагональной матрицы, поскольку оно не только ускоряет вычисления и экономит память ЭВМ, но обеспечивает сохранение самосопряженности матрицы вне зависимости от вносимой вычислительной погрешности. К.Ю.Богачев Методы нахождения собственных значений ~9.
ЯВ АЛГОРИТМ 128 2) При проведении ЯВ-алгоритма для самосопряженной трехдиагональной матрицы нет необходимости хранить все матрицы, составляющие матрицу Я, достаточно хранить только последнюю (т.е. после Й-го птага построения ЯВ- разложения достаточно помнить только матрицу Т~а ьз, или Уь. Действительно, после перехода от матрицы А~" 0 (23) к матрице Айй (24) в алгоритме участвует только подматрица (а; ),„ьз.1 „и столбцы 1,2,..., й в (ь-0 дальнейших вычислениях не изменяются. Поэтому можно сразу умножить А~"> на матрицу Т~, ь или Уь 1 справа (это изменяет только (й — 1)-й и й-й столбцы матрицы Арй ). На последнем шаге (й = и — 1) надо умножить еще и на матрицу Т„', „или У„1 справа. В результате такого процесса матрица Аь в ЯЯ-алгоритме нахождения собственных значений сразу перейдет в матрицу Аь,~ (без построения ЯВ- разложения матрицы Аь в явном виде). Оценка количества арифметических операций на один шаг ЯВ-алгоритма для самосопряженной трехдиагональной матрицы для метода вращений 1) Построение ЯВ-разложения матрицы Аь = Яьйк требует 14п+0(1) (и -+ оо) мультипликативных операций, бп+ 0(1) (и — ~ оо) аддитивных операций и 2п+ О(1) (п -+ ос) операций извлечения корня (которые по трудоемкости по порядку можно сравнить с операциями деления).
2) Подсчитаем затраты на вычисление произведения (10). Так как умножение трехдиагональной матрицы Л на матрицу Т,',~, справа изменяет ее г-й и г + 1 столбцы, имеющие не более трех ненулевых элементов, из которых один мы не вычисляем, то согласно лемме 1.12.5 на это требуется 8 умножений и 4 сложения. Следовательно, на вычисление произведения (10) требуется 8 = 8 (и — 1) мультипликативных операций и 4(п — 1) аддитивных операций. Следовательно, один шаг алгоритма для трехдиагональной матрицы требует 22п+0(1) (п -+ со) мультипликативных, 10п+0(1) (и — ~ оо) аддитивных операций и 2п+ ОЯ (и — э оо) операций извлечения корня (которые по трудоемкости по порядку можно сравнить с операциями деления).
Оценка количества арифметических операций на один шаг ЯВ-алгоритма для самосопряженной трехдиагональной матрицы для метода отражений 1) Следовательно, всего для проведения алгоритма требуется выполнить не более 15п мультипликативных операций, 9п адцитивных операций и 2п операций извлечения корня (которые по трудоемкости по порядку можно сравнить с операциями деления). 2) Подсчитаем затраты на вычисление произведения (21). Так как умножение трехдиагональной матрицы Л на матрицу Ц справа изменяет ее г-й и г+ 1 столбцы, имеющие не более трех ненулевых элементов, из которых один мы не вычисляем, то согласно лемме 1.13.11 на это требуется 10 умножений и 6 К.Ю.Богачев Методы нахождения собственных значений ~9. ЯЛ АЛГОРИТМ сложений. Следовательно, на вычисление произведения (21) требуется 2,", 10 = 10п мультипликативных операций и бп аддитивных операций.
Следовательно, один шаг алгоритма для трехдиагональной матрицы требует 2Оп+ОЯ (и -э оо) мультипликативных, 15п+О(1) (п — э со) аддитивных операций и 2п+ О(1) (и — э сс) операций извлечения корня (которые по трудоемкости по порядку можно сравнить с операциями деления). З 9.3. Ускорение сходимости алгоритма Рассмотрим способы, применяемые для ускорения сходимости последовательности матриц (Аь) к диагональной матрице. Как отмечалось вьппе (см. стр. 104), эти способы во многом схожи со способами ускорения сходимости 1 В-алгоритма и алгоритма Холецкого. Также справедливы замечания 7.3 и 7.4. Поскольку ЯВ-алгоритм никогда не применяется для матриц произвольного вида, всюду ниже мы будем считать, что исходная матрица уже приведена унитарным подобием к почти треугольному или трехдиагональному виду.
Таким образом, начальная матрица А~ — почти треугольная (или трехдиагональная). По доказанному вьппе это означает, что все матрицы Аь почти треугольные (трехдиагональные) . ~ 9.3.1. Исчерпывание матрицы Идея исчерпывания матрицы для ЯВ-алгоритма та же, что и для ЬН,— алгоритма (см. стр. 105). З 9.3.2. Сдвиги Идея использования сдвигов для ЯЛ-алгоритма та же, что и для 1,В- алгоритма (см. стр. 106). Модифицированный ЯВ-алгоритм, основанный на этой идее, выглядит следующим образом. Будем строить для матрицы А е М„последовательность (Аь) матриц Аь е М„по следующим правилам: 1) А~ — — А; 2) для всех й = 1, 2,... матрица Аьз.~ получается из матрицы Аь следующим образом: а) определяем требуемый сдвиг зь (его оптимальный выбор — отдельная задача), б) строим ЯВ-разложение матрицы Аь — зь1: Аь — зь1 = ЯьЛь, в) вычисляем матрипу Аьз.~ как произведение матриц Вь и Щ плюс зь1: Аьз.~ — — Кь1ь + зь1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
