Дж. Деммель - Вычислительная линейная алгебра, страница 63

Сформулировать и доказать теорему для сингуляр- ных векторов, аналогичную теореме 5.4. Вопрос 5.9 (трудный). Доказать оценку (5.б) в теореме 5.5. Вопрос 5.10 (еще более трудный). Доказать оценку (5.7) в теореме 5.5. Вопрос 5.11 (легкий). Пусть 0 = 0« + 0г, причем все три угла заключены между О и я/2. Доказать, что -' гш 20 ( г ею 20« + -' эш20г. Этот результат используется в доказательстве теоремы 5.7. Вопрос 5.12 (трудный).

Доказать следствие 5.2. Указание: использовать ут- верждение 4 теоремы З.З. Вопрос 5.13 (средней трудности). Пусть А — симметричная матрица. Предположим, что к А применяется СгВ;итерация со сдвигами (алгоритм 4.5). На каждом шаге в качестве сдвига берется отношение Рэлея (т; = а„„), что порождает последовательность сдвигов аы аг, .... Пусть, кроме того, к А применяется ВХг-итерация (алгоритм 5.1) с начальным вектором хе = [О,..., 0,1[т, порождающая последовательность частных Рэлея рг, рг,..., Показать, что эти две последовательности одинаковы, т.е.

а, = р; для всех г. Этим обосновано утверждение, сделанное в разд. 5.3.2, что ЯВ-итерация со сдвигами обладает свойством локальной кубической сходимости. Вопрос 5.14 (легкий). Доказать лемму 5.1. Вопрос 5.15 (легкий). Доказать, что если г(п) = 2»(п/2) + спг + 0(пг), то г(п) с«пг. На этом факте основывается анализ сложности алгоритма «разделяй-и-властвуй» (алгоритма 5.2). Вопрос 5.16 (легкий). Пусть А = Р + риит, где П = йак(4,...,4,) и и = [иг,...,и„]~.

Показать, что если с(; = д,+~ или и; = О, то д«есть собственное значение матрицы А. Для случая и; = 0 показать, что собственному значению д, в качестве собственного вектора отвечает «ьй столбец е; единичной матрицы. Вывести аналогичное простое выражение для собственного вектора в случае 4 = д«.~ы Это показывает, как обрабатывается ситуация дефляции в алгоритме «разделяй-и-властвуй» (алгоритм 5.2). Вопрос 5.17 (легкий). Пусть «р и «Р' — заданные числа.

Показать, как вычисляются коэффициенты с и с, определяющие функцию й(Л) = с+ «х, такую, что при Л = с имеем 6(с) = «р и Ь'(с) = «р~. Этот результат нужен для алгоритма решения векового уравнения (см. разд. 5.3.3). Вопрос 5.18 (легкий; Е Ва~). Используя ЯИ), показать, что для вещественной т х п-матрицы А, где т > и, найдутся т х и-матрица Я с ортонормированными столбцами (т.е.

ЯтЦ = 1) и положительно полуопределенная и х и-матрица Р, такие, что А = б/Р. Такое представление матрицы А называется ее поллрн»ьм разлоэкениел«, потому что оно аналогично полярной форме 276 Глава 5. Симметричная проблема собственных значений комплексного числа: г = е""ебб ~г!. Доказать, что полярное разложение квадратной невырожденной матрицы А единственно. Вопрос 5.19 (легкий). Доказать лемму 5.5. Вопрос 5.20 (легкий). Доказать лемму 5.7. Вопрос 5.21 (трудный). Доказать теорему 5.13.

Кроме того, уменьшить показатель 4п — 2 в оценке из этой теоремы до 2п — 1. Указание: в лемме 5.7 умножить Р, и разделить Рг на подходящим образом выбранную константу. Вопрос 5.22 (средней трудности). Доказать, что алгоритм 5.13 вычисляет БЧР матрицы С, предполагая, что СтС сходится к диагональной матрице. Вопрос 5.23 (более трудный). Пусть А — симметричная положительно определенная п х и-матрица с разложением Холесского А = ЕЕ~ и пусть Х вЂ” ее множитель Холесского, вычисленный в арифметике с плавающей точкой.

В этой задаче мы оценим относительную погрешность (возведенных в квадрат) сингулярных чисел матрицы Х как приближений к собственным значениям матрицы А. Показать, что А может быть представлена в виде А = РАР, где Р = бйаб(ам,...,а„„) и ан = 1 для всех 1. Положим 1 = РХ. Показать, что кг(Х) = к(А). Используя оценку (2.16) для обратной ошибки БА метода Холесского (т.

е, А + 4А = ХХт), показать возможность представления ьть = 1'т171Х, где Й1'т1' — 1!)г < 0(е)к(А). Опираясь на теорему 5.6, вывести отсюда, что относительные разности собственных значений матриц ХтУ и ЕтЬ не превосходят 0(е)к(А). Затем показать, что такое же утверждение верно в отношении собственных значений матриц ХХт и ЬЕт. Это доказывает, что относительные разности квадратов сингулярных чисел матрицы Х и собственных значений матрицы А ограничены величиной 0(е)к(А) = 0(е)кг(Х). Вопрос 5.24 (более трудный). В этой задаче обосновывается критерий астапова метода односторонних вращений для вычисления БЧР (см. алгоритм 5.13).

Пусть С и А — матрицы порядка п и А = СтС. Предположим, что ~а е) < е /агуаье для всех у ~ к. Пусть о„< .. < ог — сингулярные числа матрицы С, а аг « . а㻠— упорядоченные диагональные элементы матрицы А. Доказать неравенства )а, — ~а;Й < не~а,~. Таким образом, (а,! суть приближения высокой относительной точности к соответствующим сингулярным числам. Указание:использовать следствие 5.2. Вопрос 5.25 (более трудный).

В вопросе 4.15 вы «заметили», что если к симметричной матрице применить т шагов (4В;итерации, «зеркально отразить» строки и столбцы полученной матрицы, провести еще т шагов ЯВ-итерации и снова выполнить зеркальное отражение, то результатом будет исходная матрица. (Зеркальное отражение матрицы Х заменяет ее матрицей УХА, где 1 получается из единичной матрицы обращением порядка строк.) В этом упражнении мы обосновываем данный феномен для симметричных положительно определенных матриц Т, используя подход, отличающийся от следствия 5.4. Рассмотрим ЬВ;итерацию (алгоритм 5.9) с нулевым сдвигом в применении к симметричной положительно определенной матрице Т (не обязательно трех- диагональной): сначала вычисляется разложение Холесского Т = Те = ВедВе, 277 5.7.

Вопросы к главе о затем матрица Тс = ВоВт = В~В~ и, более общо, матрица Т; = В; ~В7, = В, В,. Пусть Т; — матрица, полученная из То посредством 1 шагов Я1ьитерации без сдвигов (т.е. если Т; = Я;В, есть ЯВ;разложение матрицы Тн то Т+~ — — В;Щ). В лемме 5.6 было показано, что Т; = Тао т. е. один шаг Ягьитерации эквивалентен двум шагам ЬВ-итерации. 1.

Показать, что Т; = (В; дВ; г ..Во) тТо(В; сВ; г . Во)г. 2, Показать, что Т; = (В; сВ; г Во)ТоМ-~В; — г Во) 3. Показать, что разложение Холесского матрицы Т,,' имеет вид То (В;В; ~ Во) (В;В; с Во). 4. Показать, что ЯВ;разложение матрицы То имеетвид То' = (Яо . ° Я; г1г; ~). (В~ — ~Вг-г Во) 5. Показать, что разложение Холесского матрицы Тоьт имеет вид Т<~' (Вм-1Вга-2 ' ' ' Ю (Вм-1г'"м-2 ' ' ' Во). 6. Показать, что матрица, полученная в результате т шагов ЯВ;итерации, зеркального отражения, еще т шагов ЯВ;итерации и еще одного отражения совпадает с исходной матрицей. Указание; использовать единственность разложения Холесского.

Вопрос 5.26 (трудный; Е Ва1). Пусть х — вектор размерности и. Определим матрицу С с элементами с, = ~х,)+ ~х ! — )х; — х !. Показать, что эта матрица положительно полуопределена. Вопрос 5.27 (легкий; Е Ва1). Пусть А= Вн 1 причем уВут ( 1. Показать, что ~~АЫА-"~Ь = "~~'~'. =1 !!В!!,' Вопрос 5.28 (средней трудности; Е Ва1). Квадратная матрица А называется косоэрмитовой, если А* = — А. Доказать, что 1. собственные значения косоэрмитовой матрицы суть чисто мнимые числа; 2.

матрица 1 — А невырожденна; 3. матрица С = (1 — А) г(1+ А) унитарная. Эта матрица называется преобразованием Коли матрицы А. Глава 6 Итерационные методы для линейных систем 6.1. Введение Итерационные алеорипьмм используются для решения системы Ах = б тогда, когда методы типа гауссова исключения требуют слишком много времени или памяти. Методы, вычисляющие точное решение (в отсутствие ошибок округлений!) за конечное число шагов, называются пряммми.

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

Последняя часто является конечно-разностной или конечно-элементной моделью некоторой физической системы, обычно описываемой дифференциальным уравнением. Существует множество физических систем, дифференциальных уравнений, конечно-рэзностных и конечно-элементных моделей, а потому и множество итерационных методов. Невозможно охватить все ситуации или хотя бы самые интересные из них, поэтому мы ограничимся исследованием модельной задачи, представляющей собой стандартную конечно-разностную аппроксимацию уравнения Пуассона в квадрате. Уравнение Пуассона и тесно с ним связанное уравнение Лапласа возникают во многих приложениях; укажем, например, задачи электромагнитной теории, гидродинамики, теплопередачн, диффузии и квантовой механики.