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

Как и в многосеточном методе, таким оператором оказывается В~. Алгоритм 6.20. Двухуровневый аддитивный метод Шварца длл пересчета приближенного решения х; системы Ах = Ь в более точное приближение х;<.1.. хьы = хг 1ог у' = 1 1о число областей Пь 371 6.12. Вопросы к главе б гп» = (Ь вЂ” Ах )и, »-1 х««.~ и, = х;.»» и, +Ай, и . гп» епй /ог хоы — — х»ы + Н Ан Нг т Как и алгоритм 6.18, этот алгоритм обычно используется в качестве предобуславливателя для методов крыловского подпространства. Согласно теории сходимости этого алгоритма, применимой к более общим задачам, чем уравнение Пуассона, число итераций, необходимых для сходимости, не зависит от Н, Ь и 5, когда все три величины стремятся к нулю так, что отношение 5/Н остается неизменным.

Это означает, что сложность алгоритма будет столь же низкой, как и у многосеточного метода, если работа при решении подзадач с матрицами Ай~ и и Ад' пропорциональна числу неизвестных. Читателю, вероятно, ясно, что реализация подобных алгоритмов для реальных задач является непростым делом. Имеется комплекс программ, доступный в Интернете, реализующий многие из описанных здесь «строительных блоков»; программы способны работать и на параллельных компьютерах. Комплекс называется РЕТ8с (сокращение от РогсаЫе Ех1епг1Ые Тоо1ЫФ 1ог 8с1еп»16с сошрп11п8).

Он может быть найден по адресу ЬФФр://кк«г.шсэ.ап1.8оч/ресгс/ ремис.51ш1, а краткое его описание дано в [232]. 6.11. Литература и смежные вопросы к главе 6 Обзоры современных итерационных методов, доведенные до новейших достижений, даны в [15, 107, 136, 214), а обзор их параллельных реализаций — в [76]. Классические методы типа методов Якоби, Гаусса — Зейделя и 8ОК подробно описаны в [249, 137). По поводу многосеточных методов см. [43, 185, 186, 260, 268), а также литературу, упоминаемую в этих публикациях; на Интернетсайте [91] можно найти ссылки на обширную библиографию, программы и. т.

и. Методы декомпозиции области обсуждаются в [49, 116, 205, 232). Описание чебышевских и родственных многочленов дано в [240). Изложение алгоритма РРТ содержится в любом хорошем учебнике по теории вычислений; см., например, [3] и [248]. Стабилизированный вариант блочной циклической редукции можно найти в [47, 46]. 6.12. Вопросы к главе 6 Вопрос 6.1 (легкий). Доказать лемму 6.1. Вопрос 6.2 (легкий). Доказать приводимые ниже формулы для треугольных разложений матрицы Твп 1.

Разложение Холесского Т»« — — Впту имеет множитель Холесского Вк верхнего двухдиагонального вида с элементами 1»+1 » В»«(»,») = ~( —, и Вч[»',»+1) = )/ —, 1 1+1 372 Глава б. Итерационные методы для линейных систем 2. Гауссово исключение с частичным выбором ведущего элемента дает для Тк разложение Тк = Х нХ1к, где оба треугольных множителя — двухдиагональные: г Хк(г,г) = 1 и Хк(1+1,1) = — —, 1+1 г+ 1 11н(г,г) = —, и Х1н(г,г+1) = — 1. г 3. Тн = РнР~к, где Рк — верхняя двухдиагональная матрица размера Ю х (Х+ 1) с 1 на главной диагонали и — 1 на первой надциагонали. Вопрос 6.3 (легкий). Проверить равенство (6.13). Вопрос 6.4 (легкий).

1. Доказать лемму 6.2. 2. Доказать лемму 6.3. 3. Доказать, что уравнение Сильвестра АХ вЂ” ХВ = С эквивалентно системе линейных уравнений (1„З А — Вт З 1,„) нес(Х) = чес(С). 4. Доказать, что чес(АХВ) = (Вг З А) нес(Х). Вопрос 6.5 (средней трудности). Пусть А""" — диагонализуемая матрица, т. е. А имеет и линейно независимых собственных векторов: Ах; = епх;, или АХ = ХЛл, где Х = [хг,..., х„] и Лл = 61ая(еп). Точно так же, пусть В диагонализуемая матрица, так что В имеет т линейно независимых собственных векторов: Ву; = Ду,, или ВУ = УЛн, где1 = [уг,...,у ] и Лн = ббай(61). Доказать следующие утверждения: 1.

Собственными значениями матрицы (1 З А+ В З 1„) являются тп чисел А„. = о, + 11., т. е. все возможные парные суммы собственных значений матриц А и В. Соответствующие собственные векторы имеют вид гй = х; З у,, где (от+1)-я компонента равна х;(К)уд(1). Это же можно записать матричным соотношением (1,н З А + В З 1„) (1' З Х) = (У З Х) (1п, З Лл + Л в З 1н). (6.63) 2. Уравнение Сильвестра АХ + ХВт = С невырожденно (т. е.

разрешимо относительно Х при любой матрице С) тогда и только тогда, когда си+ 61 ф 0 для всех собственных значений ог матрицы А и 6 матрицы В. То же самое справедливо для несколько иного уравнения Сильвестра АХ + ХВ = С (см, также вопрос 4.6). 3. Собственными значениями матрицы А З В являются тп чисел А„= ое61, т. е. все возможные парные произведения собственных значений матриц А и В. Соответствующие собственные векторы имеют вид гкч = х; З уз где (Йт+1)-я компонента равна х;(Й)у (1).

Это же можно записать матричным соотношением (В З А)(У З Х) = (1' З Х) (Лв З Лл). (6.64) Вопрос 6.6 (легкий; программирование). Написать однострочную МаВаЪ- программу, ревлизующую алгоритм 6.2, т. е. шаг алгоритма Якоби для уравнения Пуассона. Проверьте ее, убедившись, что скорость сходимости алгоритма соответствует предсказанию в разд. 6.5.4. 373 6.12. Вопросы к главе 6 Вопрос 6.7 (трудный). Доказать лемму 6.7. Вопрос 6.8 (средней трудности; программирование). Написать Мас1аЬ- программу, решающую дискретную модельную задачу на квадрате посредством алгоритма РРТ.

Входными параметрами программы должны быть порядок Х и Ю х Х-матрица значений /0. Выходными параметрами должны быть Х х Х-матрица решения ий и невязка йТп по — Й /аг/ЦТпкл4г аиаг). Нужно также получить трехмерные графики функций / и о. Используйте процедуру РРТ, встроенную в Мас1аЬ. Если использовать все возможности, предоставляемые Мас1аЬ'ом, то длина вашей программы не должна превышать нескольких строк. Решите с ее помощью несколько задач как с известным, так и неизвестным вам решением: 1.

/1ь = япОя/(Ю + 1)) яп(Ьг/(Ю+ 1)). 2. /дь = яп(ух/1Л+1)) в1п(кя/(%+ 1)) + еш(3ук/(Я+1)) яп(бйк/(Я+ 1)). 3. / имеет несколько острых пиков (как в положительную, так и отрицательную сторону), а в остальном равна нулю. Такую функцию можно рассматривать как аппроксимацию электростатического потенциала системы заряженных частиц, помещенных у оснований пиков, заряды которых пропорциональны (положительным или отрицательным) высотам пиков. Если все пики направлены в положительную сторону, то функцию можно интерпретировать и квк аппроксимацию гравитационного потенциала. Вопрос 6.9 (средней трудности). Проверить, что последовательное выполнение справа налево матрично-векторных произведений в формуле (6А7) математически эквивалентно алгоритму 6.13.

Вопрос 6.10 (труднми средней трудности). 1 (трудный). Пусть вещественные симметричные матрицы А и Н перестановочнм, т. е. АН = НА. Доказать, что найдется ортогональная матрица Я, такая, что обе матрицы с„АЯс и б/НЯт — диагональные: ЯАЯт = с11а8(оы...,о„), ЯНсгт = йа81оы...,В„). Иными словами, А и Н имеют одни и те же собственные векторы. Указание: предположите вначале, что все собственные значения матрицы А различны, а затем устраните это предположение. 2 (средней трудности). Рассмотрим симметричную трехдиагональную теплицеву матрицу д В сг т.

е. симметричную трехдиагонвльную матрипу с константой о на главной диагонали и константой д на двух соседних диагоналях. Выписать простые формулы для собственных значений и собственных векторов матрицы Т. Указание: воспользоваться леммой 6.1. 374 Глава б. Итерацяояные методы длл линейных систем 3 (трудный). Рассмотрим пг х пг-матрицу А Н Т= Н Н А блочно-трехдиагонального вида с п копиями матрицы А вдоль главной диагонали. Пусть «ЗА«Зг = д)ак(с«ы...,с«„) и ЯНь)т = с))а8(ды...,6в) — указанные выше спектральные разложения матриц А и Н. Выписать простые формулы для пг собственных значений и собственных векторов матрицы Т как функций от чисел сп и 6) и матрицы сд.

4 (средней трудности). Указать способ решения системы Тх = Ь за время 0(пг). Насколько больше было бы время при решении системы посредством плотного или ленточного 1Л)-разложения? 5 (средней трудности). Пусть А и Н вЂ” (возможно, различные) симметричные трехдиагональные тгплицевы матрицы (см. определение выше). Используя алгоритм РРТ, найти способ решения системы Тх = Ь за время 0(пг )ойп). Вопрос 6.11 (легкий). Пусть Н вЂ” невырожденная верхняя треугольная матрица.

Проверить, что для верхней хессенберговой матрицы С матрица НСН» также верхняя хессенбергова. Вопрос 6.12 (средней трудности). Проверить, что крыловское подпространство Кь(А,у») тогда и только тогда имеет размерность й, когда при вычислении вектора дь не происходит досрочного выхода из алгоритма Арнольди (алгоритм 6.9) или алгоритма Лалцоша (алгоритм 6.10).

Вопрос 6.13 (средней трудности). Пусть А""" — симметричная положительно определенная матрица и пусть матрица Я""" имеет полный столбцевой ранг. Проверить, что матрица Т = ЯтАЯ также симметричная и положительно определенная. (Здесь матрица Ц не обязана иметь ортонормированные столбцы.) Вопрос 6.14 (средней трудности). Доказать теорему 6.9. Вопрос 6.15 ((средней трудности; трудный)' ). 1 (средней трудности). Проверить равенство (6.58). 2 (средней трудности). Проверить равенство (6.60). 3 (трудный).

Доказать теорему 6.П. Вопрос 6.16 (средней трудности; программирование). На Интернет-странице НОМЕРАСЕ/Маг)аЬ/МС.НЕАВМЕ.Ь)ш) имеется Ма1)аЬ-программа, реализующая решение дискретной модельной задачи на квадрате многосеточным методом. Начните работу с ней запуском демонстрационной программы (для чего введите команду «ша)сешйс)ешо», а затем «1ег16пйл»). После этого проверьте, как работает Фег16пйл для различных правых частей (входной массив 'Ь), различного числа взвешенных итераций Якоби до и после каждого рекурсивного обращения к многосеточному решателю (входные параметры)ас1 и )ас2) и различного числа итераций (входной параметр ))ег).