Богачев - Практикум на ЭВМ. Методы решения линейных систем и нахождения собственных значений (947493), страница 17
Текст из файла (страница 17)
Компоненты 1+1,...,и /с-го столбца матрицы А1й), равные компонентам вектора (/а1 )/е,, уже вычислены в (10). Столбец й вычисляется не по '1й — Ц 1ч — й) общим формулам (7) для сокращения количества арифметических операций и уменыпения вычислительной погрептности. 3. Поскольку в формуле (19) (а1 ); й+1 „й+1 „— — П(хй)(а," ); й+, „й+, „П(хй), (20) (й) . (й-Ц К.Ю.Богачев Точные методы решения линейных систем "315. ПРИВЕДЕНИЕ МАТРИЦЫ К ПОЧТИ ТРЕУГОЛЬНОМУ ВИДУ 77 ~15.
ПРИВЕДЕНИЕ МАТРИЦЫ К ПОЧТИ ТРЕУГОЛЬНОМУ ВИДУ 78 то в силу леммы 1 на вычисление подматрицы (20) матрицы Айй требуется 2(п — й)г + 0(и — 1с) мультипликативных и столько же адцитивных операций. Итак, на й-ом шаге алгоритма требуется выполнить п — й+ 1+ 2(п — й)г+ 0(и — й) = 2(п — й)г+0(п — й) мультипликативных операций, п — И+1+2(п — 1с)а+ 0(п — й) = 21п — й) + 0(п — й) аддитивных операций и 2 операции извлечения корня.
Следовательно, всего для проведения алгоритма требуется выполнить ~~;(2(п — й)~+0(н — й)) = 2ип — 1)(п — 2)(2п — 3)/6)+0(п ) = ~~й+0(пг) (и — + оо) й=1 мультипликативных операций, столько же аддитивных операций и 2(п — 2) операций извлечения корня (которые по трудоемкости по порядку можно сравнить с операциями деления). Таким образом, на приведение матрицы к почти треугольному виду унитарным подобием методом отражений требуется гпг + 0(нг) (п — > оо) мультипликативных операций и столько же аддитивных операций.
Заметим, что зто количество операций в два с половиной раза меньше, чем требуется для приведения произвольной матрицы к почти треугольному виду унитарным подобием методом отражений и совпадает количеством операций, необходимым для решения линейной системы методом отражений. Теорема 2. Всякал невырожденнол самосопряженнал матрица А может быть представлена в виде А = Я Я Я~, где матрица Я вЂ” рнитарнол, а матрица  — трехдиагональная. Доказательство Совпадает с доказательством теоремы 1. Хранение матриц Ч и В в памяти осуществляется одним из способов, изложенных при обсуждении алгоритма построения ЯЛ-разложения для матрицы А методом отражений.
Трудоемкость алгоритма построения описанного вьппе разложения складывается из количества арифметических операций, необходимых для проведения самого алгоритма, и количества арифметических операций, необходимых для построения матрицы Я. Подробные выкладки были проведены при обсуждении алгоритма построения ЯВ-разложения методом отражений. К.Ю.Богачев Точные методы решения линейных систем Глава 11. МЕТОДЫ НАХОЖДЕНИЯ СОБСТВЕННЫХ ЗНАЧЕНИЙ ~ 1. ТОт1НЫ1' И ИТЕРАЦИОННЫЕ М1' ТОДЫ Определение. Метод решения линейной системы называется точным, если при отсутствии округлений точное решение системы находится этим методом за конечное число арифметических операций (например, для метода Гаусса это 2пз + Р(пг) ) На реальной вычислительной магпине точный метод дает некоторое приближение к точному решению системы. Мера близости оценена в з 1.3.
Все описанные выше методы являются точными. Определение. Метод решения линейной системы называется итерационным, если он состоит в вычислении последовательности (хь), сходящейся к точному решению: хь — ~ х при й -+ сс. Итерационный метод за конечное число арифметических операций дает только некоторое приближение хь, к точному решению. Теория итерационных методов будет изложена в курсе "Численные методы". Определение. Метод нахождения собственных значений называется итерационным, если он состоит в вычислении последовательности (Ль), сходящейся к точному собственному значению: Ль — > Л при й -+ со.
Итерационный метод за конечное число арифметических операций дает только некоторое приближение Ль, к точному собственному значению. Теорема 1. (Без доказательства.) Не может существовать точного метода нахожденил всех собственных значений произвольной матрицы А Е М„при и ) 5. Другими словами, за конечное число арифметических операций нельзя найти все собственные значения произвольной матрицы А Е М„при и ) 5. К.Ю.Богачев Методы нахождения собственных значений ~2. ЛОКАЛИЗАЦИЯ СОБСТВЕННЫХ ЗНАЧЕНИЙ 80 ~ 2. ЛОКАЛИЗАЦИЯ СОБСТВЕННЫХ ЗНАЧЕНИЙ Для матрицы А Е М„обозначим В;'(А) = ~ ~а; ~, т'=1 хн ст(А) = 1Ль..., Л„) — множество собственных значений. Теорема 1 (Гершгорин).
Для всякой матрицы А Е М„справедливо соотношениет о(А) с Ц 1г е С": )г — аа( < В';(А)) . (1) Кроме тпого, если обьединение й, 1 < й < и из зтих кругов есть связная область, не пересекающаяся с остальными п — 1с кругами, то в ней находится ровно й собственнтях значений матрицтя А.
Доказательство. Пусть Л вЂ” собственное значение матрицы А и х (хм...,х„) ф Π— соответствующий собственный вектор: Ах = Лх. Обозначим ~хр~ = тпах; т „~х;~ ф О. Так как Ах = Лх, то Лхр — — (Лх)р — — (Ах)р — — ~ , 'а хт хр(Л вЂ” арр) = ~ ар х. 1=1 1Фр Следовательно, ~хрОЛ вЂ” арр~ < т ~арДхД < ~хр~;т ~арт~ у=т Ыр 1Фр Таким образом, собственное значение Л е о(А) принадлежит объединению кругов в (1).
Докажем второе утверждение теоремы. Положим А = П + В, где П = йаи(ан,...,а„„) Е М„, В = А — П; А, = П+ еВ, е > О. Тогда Н;'(А,) = Я';(еВ) = еЛ,'(А). Без ограничения общности мы можем считать что первые Ж К.Ю.Богачев Методы нахождения собственных значений ~2. ЛОКАЛИЗАЦИЯ СОБСТВЕННЫХ ЗНАЧЕНИЙ 81 кругов в (1) образуют связную область, не пересекаюшуюся с остальными и — й кругами.
Обозначим Сь(А) = [ ) «э е С": !я — ан! < Н,'(А)), и=1 С„ь(А) = Д 1Я Е С": !г — аи! < Л,'(А)), причем по условию Сь(А) П С д(А) = И. Рассмотрим введенные множества для матрицы А,: (2) Сь(А,) = Д (г Е С": !э — ап! < е~к(А)), в=1 С„ь(А,) = О (г Е С": !я — ан! < еВ!(А)).
Тогда для всех е Е [0,1] С,(А,) с С„(А,) = С,(А), С„,(А.) с С„ „(А,) = С„,(А). (8) Л;(А,) ~ Сь(Ая) [)Сч ь(А.). (4) По доказанному выгпе Сь(А,) П С„ь(А,) = 9 (б) для всех е е [О, 1[, причем Л;(А~) = Л;(А) = Л,, Л;(Ае) = аи. Следовательно, Л;(Ае) = аи е Сд(Ае) для 1 < з < й Л;(Ае) = ан Е С„ь(Ае) для й+ 1 < з < п.
(б) Методы нахождения собственных значений К.Ю.Богачев причем множество С~(А,) = Сь(А) связно по условию. В силу (2), (3) Сь(А,) П С ь(А,) = 9 для всех е е [0,1!. Обозначим через Л;(А,) з-е собственное значение матрицы А„ н(А,) = 1Л1(А,),..., Л„(А,)) - спектр матрицы А,.
По построению Л;(А1) = Л;(А) = Л;, Л;(Ае) = ан. Собственное значение Л;(А,) матрицы А, является корнем характеристического многочлена этой матрицы. Корни многочлена являются непрерывными функциями его коэффициентов. Следовательно, собственные значения Л;(А,) матрицы А, являются непрерывными функциями элементов этой матрицы, которые, в свою очередь, являются непрерывными фунциями параметра е. Таким образом, как композиции непрерывных функций, собственные значения Л;(А,) матрицы А, являются непрерывными фунциями параметра е. По доказанному первому утверждению теоремы н(А,) С Сь(А,) () С„ь(А,) для всех е Е [О, 1[, т.е.
~3. ОШИБКИ ПРИ НАХОЖДЕНИИ СОБСТВЕННЫХ ЗНАЧЕНИЙ 82 Поскольку Лс(А,) — непрерывная функция и принимает все промежуточные зна- чения, то из (4), (5), (6) вытекает, что Л;(А,) Е Сь(А,) для 1 < с < й Л;(А,) = аа Е С„с»(А,) для й+ 1 < з < н для всех е Е (О, Ц. При е = 1 мы получаем второе утвеждение теоремы. 8 3.
ОШИБКИ ПРИ НАХО:~КДЕНИИ СОБСТВЕННЫХ ЗНАЧЕНИЙ Пусть находятся собственные значения матрицы А Е М„Пусть 6 алгоритм нахождения собственных значений, д(А) = 6(А) — полученный этим алгоритмом спектр матрицы А. Этот спектр не совпадает с истинным значением о(А) спектра матрицы А, поскольку в силу теоремы 1.1 найти все собственные значения матрицы А за конечное число арифметических операций невозможно. Обозначим через А + Е матрицу, спектром которой является набор д(А), т.е. д(А) = о.(А+ Е).
Оценим погрешность при нахождении собственных значений (т.е. д(А) — сг(А) ) через величину матрицы .Е. Лемма 1. Пусть Р = йаи(Л»,..., Л„) — диагональная матрица, Е = (ес ) е М„. Тогда длл всякого Л Е о (Р+ Е) собственного значения магирицы .Р+ Е, существует Л = Л; Е о (Р) — собственное значение лсатрицьс .Р, такое, что )Л вЂ” Л! < )/Е!) (где )) (! — максимальнол строчнал норма матрицьс, см. стр.
9). Доказательство. Применяя теорему Гершгорина к матрице Р+Е, находим, что существует такое с, 1 < с < н, что Л ~ г ~ С": (г — Л; — еа~ < Б,'(Е) = с ')ес,( с=» сФ» Так как (г — Л; — ен( > )г — Лс( — (есс), то Л е г е С": )г — Лс( < ~ (ес) 1=» Но ~~, )ес,! < шах ~~, (ес ( = !)Е(! Поэтому Л Е «г Е С": )г — Лс! < )/Е!)„) что доказывает утверждение леммы. К.Ю.Богачев Методы нахождения собственных значений ~4.
СТЕПЕННОЙ МЕТОД Теорема 1. Пусть А Е М„диагонализируемая матрица, тп.е. су»цестпвуют невь»розтсденная матрица С и диагональная матрица Л = »1»афЛ»,..., Л„) такие, что А = СЛС '. Пустпь Е = (е; ) Е М„. Тогда для всякого Л Е о(А+ Е) — собственного значения матриць» А+ Е, су»цестпвует Л = Л; е о(А) собственное значение матрицы А, п»акое, что (Л вЂ” Л( < к (С)()Е)! где к (С) — число обусловленности матрицы С относитпельно максимальной строчной нормы матрицы (см. стпр. 13).
Доказательство. Матрицы А+Е и С '(А+Е)С = Л+С 'ЕС подобны и потому имеют одинаковые собственные значения. В силу леммы 1 для всякого Л е в(А + Е) = »т(Л + С 'ЕС) существует Л = Л; е о(Л) = о(А) такое, что )Л вЂ” Л) < ()С 'ЕС!) < !)С ')( )(Е!) ))Сй = к (С))(Е!) Теорема доказана.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
