Богачев - Практикум на ЭВМ. Методы решения линейных систем и нахождения собственных значений (947493), страница 21
Текст из файла (страница 21)
Таким образом, алгоритм построения ЬЛ-разложения требует для своего проведения выполнения п~/3+0(п~) (и + сс) мультипликативных и столько же адцитивных операций, а в сумме (2/3) из+ 0(п2) (и — ~ сс) арифметических операций. 3 7.1.2.
Алгоритм построения ЬЛ-разложения для почти треугольной матрицы Рассмотрим случай, когда матрица А Е М„в приведенном вьппе алгоритме почти треугольная. Из определения произведения матриц вытекает, что матрица Ь в ЬЛ-разложении будет двухдиагональной: 1 41 1 1зя (3) Формулы (2), следовательно, примут вид т|ь = апо Й = 1, ,п, lс>1>1, ю,1=2,...,п, 1=2,...,п. Алгоритм построения ЬВ-разложения по этим формулам требует для своего проведения выполнения пх/2+ 0(п) (п — ~ сс) мультипликативных и столько же аддитивных операций. К.Ю.Богачев Методы нахождения собственных значений 1О1 з 7.1.3. Алгоритм построения оВ-разложения для трехдиагональной матрицы Рассмотрим случай, когда матрица А Е М„в приведенном вьппе алгоритме трехдиагональная.
Из определения произведения матриц вытекает, что матрицы Б и В в оВ-разложении будут двухдиагональными: т11 т12 т22 т23 1 (о) т„1„ Формулы (4), следовательно, примут вид тн, = а1ь Й = 1,2, ! т;ь — — а;ь — 1;,; 1т; 1,1, 1ц1 — 1 ац1 — 1/т1 — 1,1 — 1 ~ (б) й =1,г+1, г= 2,...,п, Алгоритм построения АВ-разложения по этим формулам требует для своего проведения выполнения Зп+0(1) (и -+ со) мультипликативных и п+О(1) (и — 1 оо) аддитивных операций.
з 7.2. БВ алгоритм нахождения собственных значений Будем строить для матрицы А Е М„последовательность (Ае) матриц Аь Е М„по следующим правилам: 1) А1=А,: 2) для всех й = 1,2,... матрица Аь.11 получается из матрицы Аь следующим образом: а) строим 2 В-разложение матрицы Аь. Аь — — Бьйь, б) вычисляем матрицу Аь.11 как произведение матриц Вь и 1ь. А1~1 —— ЛьБь. Здесь мы предполагаем, что для каждого й = 1, 2,... ЬЛ-разложение матрицы Аь существует, т.е. для нее выполнены условия теоремы 1.
Если это не так, то алгоритм не применим. Лемма 1. Для всех й = 1,2,... матрица Аь подобна А. Доказательство. Имеем: А„г1 = йьйь — — (1,'Б~)йьйь — — й„'(БьЛи)Би —— Ь~'АьЬ|. Следовательно, матрица Аь~1 подобна Аь. Поскольку А1 —— А, то по индукции получаем, что Аь подобна А для всех й = 1,2,..., причем Аьч.1 —— Б ... Б;„'А1Б,...
Б1 = (Б,... Б1)-1А(~,„... Б1). К.10.Богачев 1 121 132 Методы нахождения собственных значений ~7. 1В АЛГОРИТМ 102 Следствие 1. Матрицы Ат,, й = 1,2,... имеют те эке собственные значения, что и матрица А. Теорема 2. (Без доказательства.) Пусть матрица А Е М„такова, что на каэкдом шаге й = 1,2,... ЬК-алгоритма осуществимо 1 К-разлоэкение для матрицы Аь, и собственные значения (Лт) матрицы А тпаковьс, что Тогда 1.ь -+ 1 при й -+ со, Кь -+ Аь ттри й -+ со (пв норме в простпранстве матприц).
Тем самым диагональные элементы матрицы Аь = (а~~~) сходятся (г) к собственным значениям матрицы А, причем в правильном порядке: аь -+Л; при Й-+со, 1=1,2,...,п. Скорость сходимости матрицы Аь к тпреугольной дается соотношением а; =Π— при Й-+со, 1>у. (Л, "~ Применение алгоритма к матрице А е М„произвольногс вида требует слишком большого числа арифметических операций: (2/3) пг + О(п ) (п -+ со) на постРоение 1В-Разложении матРицы Аь и не более пг+ О(пг) (и — ~ со) на вычисление матрицы А~~, как произведения двух треугольных матриц.
Поэтому ЬЛ-алгоритм никогда не применяется к матрицам произвольного вида. З 7.2.1. ЕВ алгоритм нахождения собственных значений для почти треугольной матрицы Лемма 2. Если матприца А — почтпи треугольная, то все матрицы Аь, Й = 1,2,... в 1Я-алгоритме почти треугольные. Доказательство. Матрица Ат — — А — почти треугольная. Предположим, что матрица Аь --- почти треугольная. Тогда в 1,Я-разложении Аг = 1ьЛг матрица 1,г имеет вид (3) (т.е. является двухдиагональной), Вь е ВТ(п).
Из определения произведения матриц вытекает, что матрица Аь,т — — Вь1,ь является почти треугольной матрицей. Лемма доказана. Эта лемма позволяет значительно ускорить работу АВ-алгоритма. Перед его применением исходная матрица А приводится к почти треугольному виду А' унитарным подобием одним из алгоритмов, описанных в з 1.14 и 3 1.15. Затем к матрице А' применяется ЬВ-алгоритм. К.Ю.Богачев Методы нахождения собственных значений ~7.
1В А,ЛГОРИТМ 1О3 Алгоритм вычисления произведения матриц В и Е Й = г,1+1,...,п — 1, 1=1,2,...,п 1= 2,3,...,п 1=1,2,...,п 17) а;„= г;„, а;,; ~ — — г;Д,; ь Вычисление произведения А = ЛЬ по зтим формулам требует пг/2 + 0(п) (п — ~ оо) мультипликативных и столько же аддитивных операций. Оценка количества арифметических операций на один шаг ЬЛ-алгоритма для почти треугольной матрицы 1) Построение ЬЛ-разложения матрицы Аг — — 1 гак по формулам (4) требует пг/2+ 0(п) (и -+ со) мультипликативных и столько же аддитивных операций.
2) Вычисление пРоизвсдениЯ Аг+~ — — ВгЬг по фоРмУлам (7) тРебУет пг/2+ 0(п) (и -+ оо) мультипликативных и столько же аддитивных операций. Следовательно, один шаг алгоритма для почти треугольной матрицы требует п~ + 0(п) (и -+ ос) мультипликативных и столько же аддитивных операций. 3 7.2.2. АГг алгоритм нахождения собственных значений для трехдиагональной матрицы Лемма 3. Если матрица А трехдиагональнол, то все матрицы Аг, й = 1, 2,... в 1 К-алгоритме — трехдиагональные. Доказательство. Матрица А~ — — А -- трехдиагональная. Предположим, что матрица Аь — трехдиагональная. Тогда в 1В-разложении Аг = Ь|Вг матрицы Ег и Вг имеют вид (5) (т.е. являются двухдиагональными).
Из определения произведения матриц вытекает, что матрица Аг+~ —— Щ1г является трехдиагональной матрицей. Лемма доказана. Эта лемма позволяет значительно ускорить работу ЕВ-алгоритма для само- сопряженной матрицы. Перед его применением исходная матрица А приводится к трехдиагональному виду А' унитарным подобием одним из алгоритмов, описанных в 3 1.14 и 3 1.15. Затем к матрице А' применяется ЛВ-алгоритм. Замечание 2. 11г-алгоритм сохраняет трехдиагональный вид матрицы, но не ее самосопряженность. Другими словами, если матрица Аг была самосопряженной, то после тпага алгоритма матрица Аг „~ может не быть самосопряженной.
Методы нахождения собственных значений К.Ю.Богачев Произведение матриц А = ВЬ, где Л Е ВТ(п), Е имеет вид (3), может быть вычислено значительно быстрее, чем произведение произвольных треугольных матриц. По определению произведения матриц ~7. ЬЛ А,ЛГОРИТМ Алгоритм вычисления произведения матриц 1т и Х Произведение матриц А = Ш, где Л и Ь имеют вид (5), может быть вычислено значительно быстрее, чем произведение произвольных треугольных матриц. По определению произведения матриц ая — — тв + т;, ч.11и.по г = 1, 2,...,п — 1 г = 1, 2,...,п — 1 (8) Вычисление произведения А = ЛЬ по этим формулам требует 2п+0(1) (и -+ ос) мультипликативных и п+ О(1) (и -э со) аддитивных операций. Оценка количества арифметических операций на один шаг ЬЛ-алгоритма для трехдиагональной матрицы 1) Построение АВ-разложения матрицы Аь = Тьйк по формулам (6) требует Зп+ 0(1) (и -э оо) мультипликативных и т~+ О(1) (п — ~ со) аддитивных операций.
2) Вычисление произведения Аь~1 — — ВьЬь по формулам (7) требует 2п + 0(1) (и -+ оо) мультипликативных и и+ 0(1) (и — ) со) аддитивных операций. Следовательно, один шаг алгоритма для трехдиагональной матрицы требует 5п + 0(1) (п -+ оо) мультипликативных и 2п + 0(1) (и — э оо) аддитивных операций. з 7.3. Ускорение сходимости алгоритма Рассмотрим способы, применяемые для ускорения сходимости последовательности матриц ~Аь) к треугольной матрице. Эти способы одинаковы как для ЬЛ-алгоритма, так и для рассматриваемых ниже алгоритма Холецкого и ЯВ- алгоритма нахождения собственных значений. Поскольку все эти алгоритмы никогда не применяются для матриц произвольного вида, всюду ниже мы будем считать, что исходная матрица уже приведена унитарным подобием к почти треугольному или трехдиагональному виду. Таким образом, начальная матрица А1 почти треугольная (или трехдиагональная).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
