Богачев - Практикум на ЭВМ. Методы решения линейных систем и нахождения собственных значений (947493), страница 20
Текст из файла (страница 20)
Эта функция может быть вычислена достаточно быстро только для трехдиагональных матриц. Поэтому исходную симметричную матрицу А перед началом алгоритма метода бисекции приводят к трехдиагональному виду унитарным подобием одним из описанных вьппе способов (см.Я 1.14.2 и ~ 1.15.2). К.Ю.Богачев Методы нахождения собственных значений ~6. МЕТОД БИСЕКЦИИ 96 Для вычисления функции п (Л) для трехдиагональных симметричных матриц сутцествуют несколько способов. 3 6.4.1. Вычисление числа перемен знака в последовательности главных миноров с помощью ПУ-разложения 3 6.4.2.
Вычисление числа перемен знака в последовательности главных миноров с помощью реккурентных формул Пусть требуется вычислить число перемен знака в последовательности 1, б„бг,..., Б„главных миноров трехдиагональной симметричной матрицы А (в алгоритме А:= А — Л1): а~ Ь| Ь| аг Ьг Ьг аг Ь„г а„~ Ь„д Ь„~ а„ Ь„г Имеем: б~ — — а~, Бг = айаг — Ьг. Пусть для некоторого й = 3,..., п — 1 бь = с1е$Аь, Бь г = бе1Аь ~ уже вычислены.
Вычислим бь,~ — — бе$Аь,ы Разложим Методы нахождения собственных значений К.Ю.Богачев Пусть требуется вычислить число перемен знака в последовательности 1,бг,бг,...,б„главных миноров трехдиагональной матрицы А (в алгоритме А:= А — Л1). Построим для матрицы А И1-разложение (см. 31.5.2, стр. 23). В силу определения перемножения матриц Аь = 1ьУ~, где Аь, 1ь, б'ь соответсвенно главные подматрицы матриц А, 1, У. Следовательно, Бь — — с1еС Аь — — де1 1ч, де1 11ь.
В силу я вида (1.5.2) треугольных матриц Е и Ц получаем де11ь = П 1,", де1 Уь = 1. По1=! этому бь — — 1„... 1ьь и число перемен знака в последовательности 1, б„бг,..., б„ равно числу перемен знака в последовательности 1,1п, 1гг,..., 1„„. Само ЫУ-разложение матрицы А не строится, находятся лишь знаки 1н. Память под матрицы 1 и У не выделяется, так как согласно формулам (1.5.3) для вычисления очередных элементов 1н, 1;+и;, и;;~~ нужно знать лишь элементы 1~ — кз — ~, 1;и — ~ > ич Согласно доказанному в 3 1.5.2 для построения ИУ-разложения требуется и — 1 аддитивных и 2(и — 1) мультипликативных операций.
Поскольку для вычисления числа перемен знака требуется еше не более и сложений (для суммирования знаков 1и), то на вычисление функции Я(А) требуется 2н+ О(1) аддитивных и столько же мультипликативных операций. ~6. МЕТОД БИСЕКЦИИ 97 де1 Аь+1 по последнему столбпу: а1 Ь1 Ь1 а~ Ьг Ьз аз = аь,1бь — Ььдь ь 2 бь~, — — аь~,бь — Ь| деФ Ь Ь| е аь 1 О Ь Ь„ Эта формула позволяет вычислить все бь, но может приводить к переполнению или потере точности. Поскольку требуются не сами числа бь, а только их знаки, то эти формулы домножают на специально подобранные множители так, чтобы все числа бь были бы не слишком велики или малы. У матриц А и аА собственные значения различаются на множитель а и потому при а ) О числа перемен знака в последовательности главных миноров совпадают. Возьмем 1) Полагаем х = а1, у = 1.
Если з1цп(хд) ( О, число перемен знака т = 1, иначе т = О. 2) Для всех Й = 2, 3,..., и вычисляем: а) а = аь, Ь = Ьь ~, б) у = (1/е „ь)/шах(/х!, !Ь(Ьд)/); в) и = "«(ах — Ь у), и = ух; г) если з1яп(их) ( О, то т = т+ 1; д) х=и, д=и. В этих формулах в начале и-го шага х равен Бь 1, умноженному на некото- рое положительное число «ь, у равен Ьь ~, умноженному на «ь. Множитель « подбирается для обеспечения максимальной вычислительной устойчивости.
Методы нахождения собственных значений К.Ю.Богачев и будем рассматривать матрипу А:= о 'А. У этой матрицы все элементы по модулю не превышают 1/4. Если оказалось, что при некотором г' элемент ~Ьг~ ( стань (где екиазь машинная точность для данной ЭВМ), то полагаем Ь; = О. При этом матрица распадается на две подматрицы, объединение наборов собственных значений которых дает набор собственных значений исходной матрицы.
Поэтому мы можем считать, что все ~Ь;~ > е „ь. Запишем для так преобразованной матрицы алгоритм вычисления числа перемен знака т в последовательности главных миноров. ~7. ЕЯ АЛГОРИТМ 98 8 7. ЬЛ АЛГОРИТМ ьг1 алгоритм позволяет находить все собственные значения матрицы А е М„. з 7.1. ЬВ-разложение, используемое в ЬЛ алгоритме Теорема 1.
(О ЛВ-разложении) Если все главные угловые миноры матрицы А Е М„отличны от нуля, то матрица А допускает представление А = ьгс, где Ь Е 1Т(п) с 1 на главной диагонали, Л б КТ(п). Доказательство. Для матрицы А' все главные угловые миноры отличны от нуля. По теореме 1А.1 для матрицы А' осуществимо ИУ-разложение А' = Ш, где Х Е 1Т(п), О Е ВТ(п) с 1 на главной диагонали. Следовательно, А = БоХ' = ХЛ, где Ь = О' ~ 1Т(п) с 1 на главной диагонали, В = Х' е ВТ(п).
Теорема доказана. З 7.1.1. Алгоритм построения ЬВ-разложения для произвольной матрицы Алгоритм построения ЬВ-разложения матрицы А е М„очень похож на алгоритм построения И7-разложения (см. стр. 19). Пусть требуется найти нижнюю треугольную матрицу Ь = (1„) с единицами на главной диагонали и верхнюю треугольную матрипу В = (т; ) такую, что А = ьГс, т.е. 1" то,, = аао Е 1=1 1, й = 1,..., и. Поскольку Ц = О при з < у, 1~" = 1, тзь — — О при 1' > й, то (1) есть система из п~ уравнений относительно п(п — 1)/2 неизвестных 1;, з > 1' и п(п+ 1)/2 неизвестных т ь, 1' < й, всего п(п+1)/2+п(п — 1)/2 = п~ неизвестных.
Получим формулы для решения системы (1), которые и составляют алгоритм нахождения ЬЛ-разложения. В силу 1; = О при 1 < 1', т,ь — — О при 1 > 1с сумма в (1) имеет вид п~~пр,й1 1,,т ь — — а;~, зг 1 1,1=1,...,п, или к>1, 1,1=1,...,п, Й<г, 1, Й = 1,..., и. К.Ю.Богачев 1,,т,,=апо 1=1 й 1; то~ = апо 1=1 Методы нахождения собственных значений ~7. ЬВ АЛГОРИТМ Выделим в первой из этих сумм отдельно случай 1 = 1, а во второй - случай Й = 1, и учтем, что 1н — — 1 для всех г = 1,..., и, к=1,...,п, Й>г>1, тп, = апо ю — ! ~,'1; та+те,=аь, 1=1 1п то —— ап, ь — 1 Ц т,ь+ 1;атьь — — аео 1=1 г, й = 2,..., п.
1=2,...,п, 1<1<1, г,1=2,...,п, Перегруппируем эти формулы А=1,...,и, 1=2,...,п, т1ь = апо 1п — — ан /тп, ю — 1 ть = аьз — 2 Ц-то,, ь-1 1;ь = (а;~, — ~" 1;. т ь)~тц„ 1=1 (2) Й>г>1, г,1=2,...,п, 1<1<1, з,1=2,...,п. Процесс вычислений по этим формулам строится следующим образом: вначале по первой из формул (2) вычисляются неизвестные элементы первой строки матрицы Гг: тп„й = 1,...,п, затем по второй из формул (2) вычисляются неизвестные элементы первого столбца матрицы Л: 1п, 1 = 2,..., п, (напомним, элемент 1п известен, он равен 1).
Далее в вычислениях участвуют только третья и четвертая из формул (2). По третьей формуле (2) вычисляются неизвестные элементы второй строки матрицы Н: таь, й = 2,..., ё (напомним, ттн —— О, так как Л -верхняя треугольная) тж = азь — 1ж тпо й = 2,..., п. 1;~ = (аьз — 1п тд)/т~2, ю' = 3,..., п. Затем по третьей формуле (2) вычисляются неизвестные элементы третьей стро- ки матрицы В: таю й = 3,..., п и так далее. а по четвертой формуле (2) вычи- сляются неизвестные элементы третьего столбца матрицы Ь: 1в, г = 4,...,п, и так далее. Замечание 1. Организация хранения матриц Б и Л в памяти. Формулы (2) таковы, что при вычислении элемента 1; или т; используются значения элемента а; и вычисленных Ранее элементов 1ь, т < 1 и ть~, Й < г.
Это позволяет хранить нижнюю треугольную матрицу Т (без единичной главной диагонали) на месте нижнего треугольника матрицы А: 1; = а;,, г > у, 1, 1' = 1,..., и, а вернюю треугольную матрицу В -- на месте верхнего треугольника матрицы А: т; =а,, 1<1, з,у=1,...,п. Методы нахождения собственных значений К.Ю.Богачев По четвертой формуле (2) вычисляются неизвестные элементы второго столбца матрицы А: 1а, г = 3,..., н (напомним, 11~ — — О, так как Е -нижняя треугольная, 122 — — 1, так как Б имеет единичную главную диагональ) ~7. БЛ, АЛГОРИТМ Оценка количества арифметических операций в алгоритме построения БВ-разложения 1.
При фиксированном г' = 1,...,и вычисление элементов тт для всех й = г,..., и по третьей формуле (2) требует ~,",,(ю' — 1) = (п — 1+1)(1 — 1) мультипликативных и столько же аддитивных операций. Следовательно, вычисление всех элементов матрицы В требует 2,", (и — 1+1) (ю' — 1) = и 2.,", (ю — 1) — 2,", (г — 1) п Ц':о',1' — ~",":,', у~ = п (и — 1)/2 — (п — 1)п(2п — 1)/6 = и /2 — пз/3+ 0(п2) = п~/6+ 0(и2) (и -+ сс) мультипликативных и столько же аддитивных операций. 2. При фиксированном й = 1,...,п вычисление элементов 1;ь для всех г = й+ 1,...,п по четвертой формуле (2) требует 2," ь+, й = (и — й)й мультипликативных и 2," ь„,(й — 1) = (и — й)(й — 1) аддитивных опеРаций. Следовательно, вычисление всех элементов матрицы В требует ~ ~,(п — 1с)й = п2(и + 1)/2 — п(п + 1) (2п + 1)/6 = пз/6+ 0(п2) (и -э сс) мультипликативных и ~„,", (и — й) Я вЂ” 1) = п2(п — 1)/2 — п(п+1) (2п+1)/6+п(п+1)/2 = пз/6+0(п2) (и -+ сс) адцитивных операций.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
