Богачев - Практикум на ЭВМ. Методы решения линейных систем и нахождения собственных значений (947493), страница 23
Текст из файла (страница 23)
при подсчете количества арифметических операций для метода Холецкого решения линейных систем). 3 8.1.2. Алгоритм построения разложения Холецкого для трехдиагональной матрицы Рассмотрим случай, когда самосопряженная матрица А е М„в приведенном выше алгоритме трехдиагональная. Из определения произведения матриц вытекает, что матрица Ь в разложении Холецкого А = ЛЬ* будет двухдиагональной: а11 а1г а21 агг агз азг азз ~!1 121 ~гг 132 ~33 (6) А= а„1„ а„„1 а„„ Методы нахождения собственных значений К.Ю.Богачев потом по формулам (4) при 1 = 2 вычисляются неизвестные элементы второго столбца матрицы Ь: '38.
МЕТОД ХОЛЕЦКОГО Формулы 14), следовательно, примут вид Алгоритм построения разложения Холецкого по этим формулам требует для своего проведения выполнения и операций извлечения корня, 2п — 1 мультипликативных и п аддитивных операций. 3 8.2. Метод Холецкого нахождения собственных значений Будем строить для самосопряженной положительно определенной матрицы А е М„последовательность (Аг) матриц Аг е М„по следующим правилам: 1) А~ — — А; 2) для всех й = 1,2,...
матрица Ад~, получается из матрицы Аг следующим образом: а) строим разложение Холецкого матрицы Ая. Ая = йгй*„, б) вычисляем матрипу Агз.~ как произведение матриц й~ и йг. Аг„.~ —— й,~йь. Лемма 1. Для всех Й = 1,2,... матрица Аь подобна А. Доказательство. Имеем: Аг+~ — — й*„йг — — (й„~йг)й*„йг — — й„~(Бай*„)йг —— й~'Агйг. Следовательно, матрица Аг+~ подобна Аг. Поскольку А~ — — А, то по индукции получаем, что Аг подобна А для всех й = 1,2,..., причем Аг+~ —— й1 '... йя 'А1 йя... й1 —— (йг...
й1) 'А(йг... й1) . Следствие 1. Матрицы Ая, й = 1,2,... имеют те эке собственные значения, что и матрица А. Лемма 2. Для всех й = 1,2,... Ая — самосопряэкеннол полоэкительно определенная матрица. Доказательство. Действительно, А~ — — А — самосопряженная положительно определенная матрица. Пусть сделано й = 1,2,...
шагов описанного вьппе процесса. Матрица Аь = (й| ~...й,) 'А(й| ~...й~) подобна матрице А и имеет те же собственные значения. Поскольку Аь = й*,йг ~ и А~ = йг,(йг,)* = Аг, то Ая — самосопряженная матрица. По лемме 1.9.3 все собственные значения матрицы А вещественны и положительны. Следовательно, все собственные значения матрицы Аг вещественны и положительны. По лемме 1.9.3 это означает, что Аг — самосопряженная положительно определенная матрица. Лемма 3. Разлоэкение Холецкого осуществимо для всякого й = 1, 2, К.Ю.Богачев Методы нахождения собственных значений Р. МЕТОД ХОЛЕЦКОГ0 Доказательство.
Действительно, по лемме 2 Ас — симметричная положительно определенная матрица, и для нее разложение Холецкого существует по теореме 1. Теорема 2. (Вез доказательства.) Пусть А е М„--- симметричная полоэссительно определенная матрица, и собственные ее значения 1Лс) матрицы А таковы, что Лс>Лг»...Л Тогда Ас -+ йа8(Лс,..., Л„1 при й — ~ со (по норме в пространстве матриц). Другими словами, диагональные элементьс матрицьс Аь — — (а~ ) сходятся к (~) собственным значениям мапсрицъс А, причем в правильном порядкес аь -+Л; при й-+со, с=1,2,...,п.
Скорость сходимости матрицьс Ас к диагональной дается соотношением Применение алгоритма к произвольной самосопряженной матрице А е М„ требует слишком большого числа арифметических операций: пз~З+ 0(пг) (п -+ оо) на постРоение РазложениЯ Холецкого матРицы Аь и не более пз+0(п ) (п -+ оо) на вычисление матрицы Ас.с.с как произведения двух треугольных матриц. Поэтому метод Холецкого никогда не применяется к матрицам произвольного вида.
з 8.2.1. Метод Холецкого нахождения собственных значений для трехдиагональной матрицы Лемма 4. Если матрица А -- трехдиагональная, то все матрицьс Ас, й = 1,2,... в методе Холецкого --- трехдиагональньсе. Доказательство. Матрица Ас — — А трехдиагональная. Предположим, что матрица Ас трехдиагональная. Тогда в разложении Холецкого Аь —— АьЬ~ матрица Ьс имеет вид (5) (т.е. является двухдиагональной). Из определения произведения матриц вытекает, что матрица Ас.с.с — — ЦБс, является трехдиагональной матрицей.
Лемма доказана. Эта лемма позволяет значительно ускорить работу метода Холецкого. Перед его применением исходная матрица А приводится к трехдиагональному виду А' унитарным подобием одним из алгоритмов, описанных в С 1.14 и С 1.15. Затем к матрице А' применяется метод Холецкого.
К.Ю.Богачев Методы нахождения собственных значений ~8. МЕТОД ХОЛЕЦКОГО Алгоритм вычисления произведения матриц Ь* и А Произведение матриц А = Ь*Л, где Ь имеет вид (5), может быть вычислено значительно быстрее, чем произведение произвольных треугольных матриц. По определению произведения матриц г = 2,3,...,п г =1,2,...,п — 1 (7) Вычисление произведения А = Ь*Ь по этим формулам требует 4п + 0(1) (п — + сс) мультипликативных и п + 0(1) (и — + сс) аддитивных операций.
Оценка количества арифметических операций на один шаг метода Холецкого для трехдиагональной матрицы 1) Построение разложения Холецкого матрицы Аь = ЛьЦ по формулам (6) требует и операций извлечения корня, 2п+ 0(1) (и — ~ сс) мультипликативных и и+ 0(1) (и -+ сс) аддитивных операций. 2) Вычисление произведения Аь~1 = ЬьЬ| по формулам (7) требует 4п + 0(1) (и -+ сс) мультипликативных и и+ 0(1) (п — ~ сс) аддитивных операций.
Следовательно, один шаг алгоритма для трехдиагональной матрицы требует и операций извлечения корня, 6п+ 0(1) (и — ~ сс) мультипликативных и 2п+ 0(1) (и — + сс) алдитивных операций. З 8.3. Ускорение сходимости алгоритма Рассмотрим способы, применяемые для ускорения сходимости последовательности матриц (Аь) к диагональной матрице. Как отмечалось вьппе (см. стр. 104), эти способы во многом схожи со способами ускорения сходимости Х 1г- и ЯВ- алгоритмов.
Также справедливы замечания 7.3 и 7.4. Поскольку метод Холецкого никогда не применяется для матриц произвольного вида, всюду ниже мы будем считать, что исходная матрица уже приведена унитарным подобием к трехдиагональному виду. Таким образом, начальная матрица А1 --- трехдиагонаньная. По доказанному выше это означает, что все матрицы Аь -- трехдиагональные. 3 8.3.1. Исчерпывание матрицы Идея исчерпывания матрицы для метода Холецкого та же, что и для ЬВ- алгоритма (см. стр.
105). К.Ю.Богачев Методы нахождения собственных значений 1)8. МЕТОД ХОЛЕЦКОГО З 8.3.2. Сдвиги Идея использования сдвигов для метода Холецкого та же, что и для БЛ- алгоритма (см. стр. 106). Модифицированный метод Холецкого, основанный на этой идее, выглядит следующим образом. Будем строить для матрицы А Е М„последовательность (Аь) матриц Аь Е М„по следующим правилам: 1) А~ — — А; 2) для всех й = 1,2,... матрица Аь „~ получается из матрицы Аь следующим образом: а) определяем требуемый сдвиг зь (его оптимальный выбор отдельная задача), б) строим разложение Холецкого матрицы Аь — зь1: Аь — зь1 = А|1*,, в) вычисляем матрицу А~~~ как произведение матриц 1*,. и Ьь плюс зь1: Аь и = 141ь + зь1 Здесь мы предполагаем, что для каждого й = 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, 2,...
имеют те же собственные значения, что и матрица А. 3 8.3.3. Практическая организация вычислений в методе Холецкого Пусть требуется определить все собственные значения самосопряженной положительно определенной матрицы А Е М„с точностью и. Вначале приводим матрипу к трехдиагональному виду А~ унитарным подобием одним из алгоритмов, описанных в З 1.14 и 3 1.15.
Затем к матрице А~ применяем метод Холецкого со сдвигами. На гпаге й в качестве сдвига нь возьмем а„„, т.е. зь —— а„„. Поскольку а„-+ Л„, то нь (й) (ь) (ь) является приближением к Л„и скорость сходимости к нулю элемента а„„, (ь) будет очень высокой. Как только на некотором шаге й будет выполнено условие (а„„,) < н)(А(), в качестве Л„берем а„„и применяем алгоритм к подматрице (ь) (й) (а;,);,,— ~д, „~ Е М„~ на 1 меныпей размерности. Так поступаем до тех пор, пока размерность матрицы не станет равной 2. Для этой матрицы собственные значения определяются как решения соответствующего квадратного уравнения. К.Ю.Богачев Методы нахождения собственных значений ~9.
ЯЛ АЛГОРИТМ 3 9. ЧВ АЛГОРИТМ ЯВ алгоритм позволяет находить все собственные значения матрицы А е Мп. 3 Я.1. ЯВ-разложение, используемое в ЯЛ алгоритме В ЯВ-алгоритме используется то же Яге-разложение, что строилось в методе вращений (см. 3' 1.12, теорема 1.12.1) и в методе отражений решения линейных систем (см. 3' 1.13, теорема 1.13.1). 3 9.1.1. Алгоритм построения ЯВ-разложения для произвольной матрицы Алгоритм построения ЯВ-разложения для произвольной матрицы был описан ранее, см. 3 1.12.4, "Построение ЯН-разложения методом вращений", с. 50, или 3 1.13.4, "Построение ЯВ-разложения методом отражений", с.
59. Там же подсчитана вычислительная сложность этих алгоритмов. 3 9.1.2. Алгоритм построения ЯВ-разложения для почти треугольной матрицы Рассмотрим случай, когда матрица А Е Мп в алгоритме построения чН,- разложения почти треугольная: ац а1г . а1,; ... а1,„2 а1,п 1 агп а21 агг ° ° ° а24 ° ° ° а2,п — 2 аг,п — 1 а2п азг ай1 аю,п 2 агп 1 а,„1,; а„г,„г ап гп 1 ап г,п ап 1,п 2 ап 1п 1 ап 1,п ап,п 1 Алгоритм построения ЯВ-разложения для почти треугольной матрицы методом вращений Обозначим а1 —— (а11, а21,0,...,О)' Е Кп — первый столбец матрицы А.
Согласно лемме112 3 существует матрица Т1г = Т12(~р12), такая, что Тгга1 = ~~а1~) е1 К.Ю.Богачев Методы нахождения собственных значений ~9. ЯЛ АЛГОРИТМ (причем значение угла 11212 определяется леммами 1.12.2, 1.12.3). Умножим ма- трипу А на Т12 слева, получим матрицу А(Ц = Т,2А, А(Ц (Ц (Ц Пп,п — 1 ахим Далее процесс применяется к подматрице (а1 ); (1) Пусть сделаны Й вЂ” 1, Й = 1,...,и — 1 шагов этого процесса, т.е. матрица преобразована к виду 1 А(й-') = П Т11+,А, (2) где т1й .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
