IV Канатников А.Н., Крищенко А.П. Линейная алгебра (Зарубин В.С., Крищенко А.П. - Комплекс учебников из 21 выпуска), страница 48

В зтом случае характеристическое уравнение матрицы Т может иметь как действительные корни (собственные значения), так и комплексные. Для сходимости итерационной последовательности нужно, чтобы все корни, и действительные, и комплексные, по модулю были меньше единицы. 11.5. Скорость сходимости стационарных итерационных методов Пусть х, — точное решение системы линейных алгебраических уравнений (СЛАУ) Ах = 5 с квадратной невырожденной матрицей А порядка н; (хо) — итерационном последовательность стаиионарного итерационного метода (11.22).

Разность о~ = х~ — х, называют ошибкой М-й итерации. Подставляя в уравнение (11.22) выражения х~ = о~ + х„ х~+1 = о~+1+х, и учитывая равенство Ах, = 5, находим Ь1+1 У В +Аои =О. т откуда о+ =То (11.25) где Т = Š— тВ 'А. Соотношение (11.25) позволяет выразить ошибку Ф-й итерации через ошибку начального приближения: о~ = Ткео. (11.26) Сходимость итерационной последовательности стационарного метода означает, что к нулю сходится последовательность (оо), определенная ренуррентным соотношением (11.25). Согласно равенству (11.26), указанная сходимость определяется 322 П.

ИТЕРАЦИОННЫЕ МЕТОДЫ сжимающими свойствами матрицы Т [1-Д8.2!. Если отображение у = Тх в пространстве К" с заданной нормой является схсимаешим, т.е. для некоторой постоянной о < 1 и любых х1, х Е К" выполняется неравенство !!Тх — Тх $~ = !!Т(х — х )!! < д!)х — х )! то последовательность (и~) сходится. Постоянная о определяется свойствами матрицы Т, и от величины этой постоянной зависит, насколько быстро сходится последовательность (ин). Необходимое и достаточное условие сходимости к нулю последовательности ошибок дает теорема 11.4, но проверка условия теоремы достаточно сложна.

Поэтому часто прибегают к другим условиям, более простым, но имеющим лишь достаточный характер. Эти условия обычно связаны с нормой матрицы Т. Как и вьппе, будем рассматривать столбцы высоты и в качестве векшоров линейного арифметического иросшраиства К", в котором задана некоторая норма !! !!.

Для матриц будем использовать норму, иидуиироваииую заданной нормой в К", и для индуцированной нормы используем то же обозначение, что и для нормы в К". Из (11.26) следует, что Отсюда видим, что последовательность (и~1 сходится к нулю, если !!Т~!! -+ 0 при Ф -+ со. Взяв г ) О, найдем такой номер Ф(г), что при Ф ) )Ф(г) будет !!Т~!! < г. Тогда для Ф = Ф(г) получаем !!и'" !! < г!!ие!!, т.е.

за Л итераций начальное приближение уменьшилось в 1/г раз. Число Ф(г) следует выбирать наименее возможным, и тогда оно будет определять минимальное число итераций для заданной точности г, а обратную величину 1/М(г) естественно рассматривать как скорость сходимостпи итперациоииого метода. Отметим, что минимальное число интераций и скорость сходимости метода зависят от того, какая выбрана норма в линейном арифметическом пространстве. 11.о.

Скорость сходиыости стационарных методов 323 Вычислить нормы 3Т~'3 очень сложно. Чтобы установить сходимость последовательности таких норм и выяснить скорость сходимости,надо использовать для таких норм различные оценки. Например, если )(ТЙ = 4 < 1, то, согласно неравенству ~)АВ3 < ))А)! 3В)), верному для любой колаиевот1 нормы, имеем неравенство ))Т~)! < цТ((~ = д~, откуда сразу следует сходимость к нулю последовательности Ц~Твт~Ц.

Более того, записав неравенства )(Т~)! < 4~ < е, получаем при помощи логарифмирования оценку минимального числа итераций: 1пе 1п(1/е) * 1п4 1п(1/ ~)Т(!) ' Скорость сходимости итерационной последовательности в стационарном методе зависит, вообще говоря, от выбранного значения итпераиионноео параметпра т. То значение то параметра,при котором скорость сходимости метода наивысшая,называют отатпимальным итперат1ионным таараметпром.

Это значение, конечно, зависит от используемой нормы. Остановимся на случае, когда в Жп рассматривается евклидова норма, порожденная стпандартпным скалярным произведением. Если А — симметрическая положительно определенная матрица, то для метода простой итерации (11.16) 2 Л,пах(А) + Лппп(А) ' где Лпнп(л) и Л,„а„(л) — соответственно минимальное и максимальное собственные значения матрицы А. При этом верна следующая оценка ошибки Ф-й итерации: ~)о1т~~ < рт* ~~ив~~, где Лп1ах(-4) Лпт!п(А) Р Лотах(А) + Лппп(,4) Параметр р определяется отношением ( = Л (А)/Л;„(А), представляющим собой число обусловленностпи симметрической положительно определенной матрицы А. Чем меньше 324 11. ИТЕРАЦИОННЫЕ МЕТОДЫ число обусловленности, тем меньше р и тем вьппе скорость сходимости метода.

При плохо обусловленной матрице А параметр р близок к единице и скорость сходимости метода простой итерации мала. В такой ситуации целесообразно ориентироваться на неявные итерационные методы (11.22). Для неявного итерационного метода (11.22), т.е. при В ф В, в случае симметрических матриц А и В 2 Л (В 1А) + Л;„(В 1А) ' где Лы„(В 1А) и Л„, (В 1А) — соответственно минимальное и максимальное собственные значения матрицы В 1А. Для ошибки итерации верна оценка ~~еН~~ < р ~~ез~~, где Л (В 1А)-Л„я„(В 'А) Л,„(В 1А)+Л„„„(В 1А) Величина р определяется числом обусловленности Л , (В 'А) Л;„(В 'А) матрицы В 1А.

Невырожденную симметрическую матрицу В следует выбирать так, чтобы ~ было малб и во всяком случае было меньше числа обусловленности матрицы А (в противном случае использование неявного метода не имеет смысла). Вопросы и задачи 11.1. Может ли число обусловленности квадратной невырожденной матрицы быть: а) отрицательным; б) положительным; в) целым; г) иррациональным; д) ббльшим единицы; е) мйньшим единицы; ж) равным единице? 11.2. Найдите число обусловленности матрицы ~ 4 /, рас- /1 2Л сматривая и качестве нормы матриц: а) спектральную норму; б) октаздрическую норму; в) кубическую норму. Сравните полученные ответы.

325 Воиросы и эаяаии 11.3. Докажите, что с(аА) = с(А) для любого действительного числа а Ф О. 11.4. Приведите пример нормы матриц и матрицы, которая относительно этой нормы имеет число обусловленности, меньшее единицы. 11.5. Найдите все матрицы А, для которых с(А). = 1 относительно спектральной нормы матриц. 11.6. Докажите, что для октаздрической, спектральной, кубической, евклидовой норм матриц число обусловленности не изменяетсл при Перестановке строк и столбцов матрицы.

11.7. Как найти сингулярное разложение симметрической положительно определенной матрицы? 11.8. Найдите ЯВ-разложение, полярное и сингулярное разложения для матриц: а) 3 — 5 5, б) 3 14 2 11.9. Составьте программу на одном из алгоритмических языков, реалиэующую метод Зейдеяя. При помощи составленной программы решите систему Сравните найденное решение с решением той же системы методом Гаусса.

0>1х1 — 8,0хэ + 9,3хз — 8,2х4 = -3,3х1 + 2,4хз — 2,8хз+ 2,4х4 = -2,6х1 + 1,9хз — 2,2хз+ 1,9х4 = -1,3х1 +9,3хз — 1,1хз+9,5х4 = 1,5, 2, -1, О. СПИСОК РЕКОМЕНДУЕМОЙ ЛИТЕРАТУРЫ Учебники и учебные пособил Беклаиишев Д.В. Доцолнительные главы линейной алгебры. Мс Наука, 1983.

336 с. Беклемшиев Д.В. Курс гиалитической геометрии и линейной алгебры; Учеб. пособие для физ.-мат. и инж.-физ. специальностей вузов. 6-е изд., стереотип. Мс Наука, 1984. 319 с. Беллман Р. Введение в теорию матриц / Пер. с англ. под ред. В.Б. Лидсного. Мс Наука, 1969. 368 с. Воеводин В.В, Вычислительные основы линейной алгебры. Мс Наука, 1977. Воеводин В,В.

Линейная алгебра. Мл Наука, 1980. Гантмахер Ф.Р. Теория матрац. 3-е изд. Мс Наука, 1967. 576 с. ГельФа«д Б.М. Лекции по линейной алгебре. 4-е изд., доп. Мс Наука, 1971. 272 с. Головина Л,Б. Линейная алгебра и некоторые ее прилоиения. Мс Наука, 1979. 392 с. ильин В.А., Познан Э.Г. Линейная алгебра. 2-е изд. Мс Наука, 1978.

304 с. КУРош А.Г. Курс высшей алгебры. 8-е изд. Мл Наука, 1965. 432 с. Ланнасхаер Б. Теория матриц / Пер, с англ. С.П. Девушкина Мс Наука, 1978. 280 с. Мальцев А.Б. Основы линейной алгебры. Мс Наука, 1970. Спьренг Г- Линейная алгебра и ее применения / Пер. с англ, под ред. Г.Б. Марчука.

Мс Мир, 1980. 456 с. Фаддеев д.К., Фаддеева В.Н. Вычислитеш ные методы линейной алгебры. Мс Физматгиз, 1963. Хорн Р., Джонсон У. Матричный анализ / Пер. с англ. под ред. Х.Д. Якрамова. Мс Мир, 1989. 656 с. 327 Справочные издания Александрова Н.В. Математические термины; Справочник. Мэ Высш. шк., 1978. 190 с. Броншшеан И.Н., Семепдлев К.А. Справочник по математике для инженеров и учащихся втузов. 13-е изд., испр. Мэ Наука, 198б.

544 с. Водвев В. Т., Наумович А.Ф., Наумович Н.Ф. Математический словарь нысшей шкивы / Под ред. Ю.С. Богданова Минеи: Вышзнш. шк., 1984. 528 с. Воеводин В.В., Кузнецов Ю.А. Матрицы и вычисления. Мг Наука, 1984. 320 с. Вмгодскиб М.Я. Справочник по высшей математике.

13-е изд., стереотип. Мг Физматлит, 1995. 872 с. Кори Г., Кори Т. Справочник по математике (для научных работнвков и инженеров) / Пер. с англ. под ред, И.Г. Арамановича Мэ Наука, 1973. 832 с. Математический энциклопедический словарь / Гл. ред. Ю.В. Прохоров. Мэ Сов. энцикл., 1988. 848 с. Сигорскиб В.П.

Математический гппарат инженера. 2-е изд., стереотип. Киев: Техн1ка, 1977. 7б8 с. Фор Р., Кофмап А., Дени-Лапен М. Современная математика / Пер. с франц. под ред. А.Н. Колмогорова. Мг Мир, 19бб. 272 с. Задачники Беклемишева Л.А., Пешроеич А.Ю., Чубаров Н.А. Сборник задач по аналитической геометрви и линейной алгебре: Учеб. пособие / Под ред.

Д.В. Беклемишева. Мэ Наука, 1987. 49б с. Икрамов Х.Д. Задачник по линейной алгебре. Мэ Наука, 1975. 320 с. Лефор Г. Алгебра н анализ. Задачи / Пер, с франц. Е.И. Сшечкипоа. Мэ Наука, 1973. 4б4 с. Окунев Л.Я. Сборник задач по высшей алгебре. Мг Просвещение, 19б4. 184 с. Проскуряков И.В.