Богачев - Практикум на ЭВМ. Методы решения линейных систем и нахождения собственных значений (Богачев - Практикум на ЭВМ), страница 27

К.1О.Богачев Методы нахождения собственных значений ~1 О. МЕТОД ОБРАТНОЙ ИТЕРАЦИИ 13О 2 9.3.3. Практическая органиэация вычислений в ЯВ алгоритме Пусть требуется определить все собственные значения матрицы А е М„с ТОЧНОСТЬЮ Е. Вначале приводим матрицу к почти треугольному виду А1 унитарным подобием одним из алгоритмов, описанных в ~ 1.14 и ~ 1.15. Затем к матрице А1 применяем ЯВ-алгоритм со сдвигами. На шаге й в качестве сдвига гй возьмем а„„, т.е. гй = а„„. Поскольку а„ь — й Л„, то гй (й) (й) (й) является приближением к Л„и скорость сходимости к нулю элемента а„„, будет очень высокой. Как только на некотором шаге й будет выполнено условие ~а~, ~~ 1~ < еОА~), „в качестве Л„берем а1й1 и применяем алгоритм к подматрице (а; );д 1г „1 Е М„1 на 1 меньшей размерности. Так поступаем до тех пор, пока размерность матрицы не станет равной 2.

Для этой матрицы собственные значения определяются как решения соответствующего квадратного уравнения. 3 10. МЕТОД ОБРАТНОЙ ИТЕРАЦИИ НАХОЖДЕНИЯ СОБСТВЕННЫХ ВЕКТОРОВ Метод обратной итерации позволяет найти собственный вектор, соответствующий однократному собственному значению Л диагонализируемой матрицы А Е М„, если известно достаточно хороп1ее приближение Л к собственному значению Л. Теорема 1 (Метод обратной итерации). Пусть матрица А Е М„имеенс полную систему ортонормированных собственных векторов е;, 1 = 1,..., п: Ае; = Л;е;, (е;, еу) = б1;, причем собсн1венное значение Л, т = 1, 2,..., п однократное.

Пусть Л ~ Л вЂ” достаточно хорошее приближение к Л Л вЂ” Л шах =у(1. '=1,2,.... Л; — Л 1ф~ Тогда для всякого вектора х1"1 Е С" такого, чгпо (х1"1, е ) ф О, итерационный процесс (А — Л |) Ый О= (й1 х1йч Π— решение уравнения (й-~1) е1"+О = ~Ф"'~! ' сходится к собственному вектору е (с шелл): (2) В=О,1, точностью до постоянного мноо1си- е~„1 -+ е'~е при к -+ оо Методы нахождения собственных значений К.Ю.Богачев Нетрудно проверить, что матрица Айч.1 (унитарно) подобна А1,. Ай.11 |1Ай+ гй| = Яй''Яй)ЯЯй+ гй|) = Чй'Яйлой)Чй+ вЯй| = К'Яйлой+ ей|а = Яй 'АЯй и, следовательно, все матрицы Ай, й = 1, 2,... имеют те же собственные значения, что и матрица А. 'з1 О.

МЕТОД ОБРАТНОЙ ИТЕРАЦИИ 1З1 (где е''г -- число, по модулю равное 1). При этом существует такое Ло > О, нто длл всех й > йо выполнено неравенство 11е(,) — е'~е„,11 < Сд~, (з) еде постоянная С не зависит от (с. Доказательство. Поскольку вектора еы...,е„образуют базис в С", то х(о) = ) с;е;, причем по условию с = (х(о),е,„) ~ О. Поскольку х("+') = (А — Л„,Т) 'х(~), то (ь~-1) ( 1 Л г) — ь (о) Так как собственные значения матрицы А — Л Т равны Л; — Л, г = 1, 2„..., и, то собственные значения матрицы (А — Л Т) ' есть (Л; — Л ) ', ( = 1,2,...,п, а матрицы (А — Л 1) г — — (Л; — Л ) ", г = 1, 2,..., и. Следовательно, х( ) = (А — Л 1) "", с;е; = ~ '"'= — - ",,"=,,(л, л.,) В силу ортонормированности базиса (е;) гь 11' "'11' = ( '"' х"') = — „1 1'+ Е 1' 1' ( (л — л) ',, ' ~л,— л,„~ В силу (1) и равенства 11х(о)11г = 2.

1с; 1г получаем и=1 или Вычислим 11 (")11 1 1 ~(л — л ) 11х(")11 1.,1,) "' ,, 11х("Ч(л — л ) с '~л,— л„,/ ' Методы нахождения собственных значений К.Ю.Богачев Ь)1 О. метОД ОБРАтнОЙ итеРАЦии В силу (1), (2) и равенств (/еь!) = 1, ь = 1,2,...,и, обозначив еа» = с,„/(с ), находим — 1/2 »,; (( ( ь»ь» — ~с„„~2 Так как » 112 ~~'; )сь! <;/пь ~ Ц' = 1/ть )/х~')!), ь=1 ь=1 то В силу (1) найдется й0 > О, такое, что для всех й ) й0 выполнено сь = )х(0) ~)2 " д~~ < 1. Тогда (1 — а) 112 > 1 — а/2 и 1 — (1 — а) 112 < сь/2 < сььь2/2. )2 Поэтому для всех и ) н0 справедливо неравенство еь") — еьь'е ) < (1/2+ 1/и) д".

, 10) /с / Это неравенство является требуемой оценкой (3). К.Ю.Богачев Методы нахождения собственных значений ПРОГРАММА КУРСА 1. Матричные нормы. Подчиненые матричные нормы. 2. Максимальная строчная и максимальная столбцовая нормы. Их подчиненность. 3. Спектральная норма и ее свойства. Спектральный радиус и его свойства.

4. Обратимость матрицы, близкой к обратимой (теорема Банаха). 5. Оценка относительной погрешности решения линейной системы через относительные погрешности в матрице системы и в правой части. Число обусловленности. 6. Оценка относительной погрешности решения линейной системы через не- вязку.

Свойства числа обусловленности. 7. Метод Гаусса. Оценка числа арифметических операций. 8. Представление метода Гаусса в виде последовательности элементарных преобразований. Ш-разложение. 9. Алгоритм построения ИУ-разложения. Оценка числа арифметических операций. 10. Критерий осуществимости метода Гаусса. 11. Метод Гаусса для ленточных матриц. Оценка числа арифметических операций. 12. Алгоритм построения ЫУ-разложения для трехдиагональных матриц.

Оценка числа арифметических операций. Организация хранения матриц в памяти ЭВМ. 13. Метод прогонки для трехдиагональных матриц. Оценка числа арифметических операций. Организация хранения матриц в памяти ЭВМ. 14. Задача обращения матрицы. Обрагцение матрицы с помощью ИГ-разложения. Оценка числа арифметических операций. К.Ю.Богачев Программа курса ПРОГРАММА КУРСА Метод Гаусса с выбором главного элемента.

Критерий осуществимости. Способы программной реализации. Метод Жордана (Гаусса-2Кордана) решения систем линейных уравнений. Оценка числа арифметических операций. Положительно определенные матрицы. Осуществимость П7-разложения для положительно определенных матриц. Теорема о разложении Холецкого для самосопряженной матрицы.

Метод Холецкого (квадратного корня) решения систем линейных уравне- ний. Организация процесса вычислений и хранения матриц в памяти ЭВМ. Оценка числа арифметических операций. Метод ортогонализации решения систем линейных уравнений. Оценка чи- сла арифметических операций. 20. Матрица элементарного вращения и ее свойства (геометрический смысл, затраты на вычисление произведений на вектор и матрицу). 21.

Метод вращений решения систем линейных уравнений. Осуществимость. Оценка числа арифметических операций. 22. Теорема о построении ЯВ-разложения методом вращений. Единственность разложения. Способы хранения матриц Ч и В в памяти ЭВМ. Оценка чи- сла арифметических операций, необходимых для построения Я — разло- жения. Матрица отражения и ее свойства (геометрический смысл, затраты на вы- числение произведений на вектор и матрипу). Метод отражений реп|ения систем линейных уравнений. Осуществимость. Оценка числа арифметических операций. 25. Приведение матрицы к почти треугольному виду унитарным подобием ме- тодом вращений.

Осуществимость. Оценка числа арифметических опера- ций. 28. Приведение симметричной матрицы к трехдиагональному виду унитарным подобием методом вращений. Осуществимость. Оценка числа арифметических операций. Программа курса К.Ю.Богачев Теорема о построении ЯВ-разложения методом отражений.

Единствен- ность разложения. Способы хранения матриц Ч' и Л в памяти ЭВМ. Оценка числа арифметических операций, необходимых для построения ЯВ-разложения. ПРОГРАММА КУРСА 135 Приведение матрицы к почти треугольному виду унитарным подобием ме- тодом отражений. Осуществимость. Оценка числа арифметических опера- ций. Приведение симметричной матрицы к трехдиагональному виду унитарным подобием методом отражений.

Осуществимость. Оценка числа арифмети- ческих операций. 30. Локализация собственных значений. Теорема о кругах Гершгорина. Оценка погрешности нахождения собственных значений через погрешность в матрице системы для диагонализируемых матриц. Степенной метод поиска максимального собственного значения. Достаточ- ные условия сходимости. Оценка числа арифметических операций на один шаг алгоритма. 33.

Общий вид методов нахождения собственных значений, минимизирующих сумму квадратов внедиагональных элементов матрицы. Теорема о сходи- мости таких методов (достаточное условие окончания итераций). 35. Стратегии выбора очередного обнуляемого элемента в методе Якоби. Оцен- ка скорости сходимости в случае обнуления максимального по модулю вне- диагонального элемента. Оценка числа арифметических операций на один шаг алгоритма для каждой из стратегий. Вычисление й-го по величине собственного значения методом бисекции.

Оценка количества итераций. Способы вычисления числа перемен знака в последовательности главных миноров. Организация процесса вычислений для предотвращения переполнения или потери точности. 37. Вычисление всех собственных значений матрицы на заданном интервале методом бисекции. Оценка количества итераций. Способы вычисления числа перемен знака в последовательности главных миноров. Организация процесса вычислений для предотвращения переполнения или потери точности. Теорема о БЛ-разложении. БЛ-алгоритм поиска собственных значений, его осуществимость. Достаточные условия сходимости (без доказатель- ства).

Алгоритм построения ЬВ-разложения. Сохранение почти треугольного ви- да матрицы в ЬЛ-алгоритме нахождения собственных значений. 40. Программа курса К.Ю.Богачев Преобразование элементарного вращения, используемое в методе вращений Якоби. Вид формул, обеспечивающий меньшее накопление вычислитель- ной погрешности. ПРОГРАММА КУРСА Ускорение сходимости ЬВ-алгоритма с помощью исчерпывания матрицы и сдвигов (без доказательства).

Пример выбора сдвига и исчерпывания ма- трицы. Теорема о разложении Холецкого, используемом в методе Холецкого поис- ка собственных значений симметричной матрицы. Метод Холецкого поиска собственных значений симметричной матрицы, его осуществимость. Доста- точные условия сходимости (без доказательства). Алгоритм построения разложения Холецкого, используемом в методе Хо- лецкого поиска собственных значений симметричной матрицы. Сохранение трехдиагонального вида матрицы в методе Холецкого поиска собственных значений симметричной матрицы.

Алгоритм построения разложения Холецкого, используемом в методе Холецкого поиска собственных значений симметричной матрицы, для трех- диагональной матрицы. Расчетные формулы метода Холецкого поиска собственных значений для трехдиагональной матрицы. Оценка числа арифметических операций на один шаг алгоритма. Ускорение сходимости метода Холецкого поиска собственных значений с помощью исчерпывания матрицы и сдвигов (без доказательства). Пример выбора сдвига и исчерпывания матрицы. ЯВ-алгоритм поиска собственных значений, его осуществимость. Доста- точные условия сходимости (без доказательства).

Сохранение почти треугольного вида матрицы в ЧЛ-алгоритме нахожде- ния собственных значений. Алгоритм построения ЯВ-разложения для почти треугольной матрицы. Расчетные формулы ЯЛ-алгоритма нахождения собственных значений для почти треугольной матрицы. Оценка числа арифметических операций на один шаг алгоритма. Ускорение сходимости ЧГг-алгоритма с помощью исчерпывания матрицы и сдвигов (без доказательства). Пример выбора сдвига и исчерпывания ма- трицы. 50. Программа курса К.Ю.Богачев Алгоритм построения ЬВ-разложения для почти треугольной матрицы. Расчетные формулы АВ-алгоритма нахождения собственных значений для почти треугольной матрицы. Оценка числа арифметических операций на один шаг алгоритма. 137 ЛИТЕРАТУРА 1.

Практикум по алгебре. Под ред. Н.С. Бахвалова, А.И. Кострикина. Изд.-во МГУ, 1983. 2. Ю.П. Размыслов, С.Я. Ищенко. Практикум по вычислительным методам алгебры. Изд.-во МГУ, 1988. 3. Н.С. Бахвалов, Н.П. Жидков, Г.М. Кобельков. Численные методы. М., "Наука", 1987. 4. Д.К. Фадцеев, В.К. Фадцеева. Вычислительные методы линейной алгебры, 1963. 5. Дж.Х. Уилкинсон. Алгебраическая проблема собственных значений. М., "Наука", 1970. б. Р. Хорн, Ч.

Джонсон. Матричный анализ. М., "Мир", 1989. 7. А.А. Самарский, А.В. Гулин. Численные методы. М., "Наука", 1989. 8. С. Писсанецки. Технология разреженных матриц. М., "Мир", 1988. К.Ю.Богачев Список литературы .