Дж. Деммель - Вычислительная линейная алгебра (1156793), страница 24
Текст из файла (страница 24)
Описание пакета ВЬА8 имеется в [87, 89, 169]. Названные программы, как и ряд других, могут быть импортированы из ХЕТЫВ'а. Анализ блочных стратегий матричного умножения проведен в [151]. Алгоритм Штрассена для умножения матриц изложен в [3], его поведение в реальных вычислениях описано в [22], а численная устойчивость обсуждается в [77, 149]. Обзор параллельных, в том числе блочных алгоритмов дан в [76], а обзор алгоритмов для структурированных плотных систем, зависящих лишь от 0(п) параметров, — в недавней публикации [160]. Дополнительная информация о прямых методах для разреженных систем содержится в [93, 94, 114, 177]. 2.9.
Вопросы к главе 2 Вопрос 2.1 (легкий). С помощью своего излюбленного броузера откройте страницу ХЕТЫВ (Ьсср://шшш.пес!1Ь.ог8) и ответьте на следующие вопросы. 1. Предположим, что вам нужна фортран-подпрограмма для вычисления собственных значений и собственных векторов вещественных симметричных матриц в арифметике двойной точности. Найдите такую подпрограмму, пользуясь возможностями для поиска, предоставляемыми ХЕТЬ1В'ом.
Укажите имя и ПВ1 адрес подпрограммы; опишите, как вы нашли ее. 2. Используя Регуоппапсе ПагаЬаве Яегчег, установите, каков в данное время мировой рекорд скорости при решении плотной системы порядка 100 посредством гауссова исключения. Какова скорость в мегафлопах и на какой машине она достигнута? Проделайте то же самое для плотных линейных систем порядка 1000 и плотных систем екак угодно большого порядкам Пользуясь этой базой данных, выясните, насколько быстро может решить плотную линейную систему порядка 100 ваша рабочая станция.
Указание: загляните в отчет ЫХРАСК ВепсЬшаг1с. Вопрос 2.2 (легкий). Пусть нужно решить относительно Х уравнение АХ = В, где А — матрица размера и х п, а Х и В имеют размер и х т. Имеются два очевидных алгоритма для этой задачи. В первом алгоритме вычисляется разложение А = РЫ? с помощью гауссова исключения, а затем каждый столбец в Х определяется посредством прямой подстановки и обратного хода. Во втором алгоритме гауссово исключение используется для вычисления обратной матрицы А ~, а затем производится умножение Х = А гВ. Подсчитайте число флопов, выполняемых каждым алгоритмом, и покажите, что для первого алгоритма оно меньше, чем для второго.
105 2.9. Вопросы к главе 2 Вопрос 2.3 (средней трудности). Пусть 9 '9 есть 2-норма, и пусть заданы невырожденная матрица А и вектор Ь. Показать, что для достаточно малых 96А~~ найдутся ненулевые ЬА и 66, такие, что неравенство (2.2) превращается в равенство. Это оправдывает название «число обусловленности матрицы А», принятое для величины к(А) = 9А 1'9'9А9. Указание: используйте идеи из доказательства теоремы 2.1. Вопрос 2.4 (трудный). Показать, что оценки (2.7) и (2.8) достижимы.
Вопрос 2.5 (средней трудности). Доказать теорему 2.3. Пусть г = Ах — Ь. Используя теорему 2.3, показать, что граница (2.9) не превосходит границы (2.7). Это объясняет, почему в ЬАРАСК'е вычисляется оценка, основанная на (2.9) (см. разд. 2.4.4). Вопрос 2.6 (лггкий). Доказать лемму 2.2. Вопрос 2.7 (легкий; Х Ва1). Пусть А — невырожденная симметричная матрица, разложенная в произведение А = ЬРМт, где Ь и М вЂ” нижние унитреугольные матрицы, а Р— диагональная матрица. Доказать, что Ь = М. Вопрос 2.8 (трудный).
Рассмотрим два способа для решения системы из двух линейных уравнений с двумя неизвестными Ь Алгоритм 1. Гауссово исключение с частичным выбором главных элементов (метод СЕРР). Алгоритм 2. Формулы Крамера: бес = аы «агг — агг * агы х1 — — (агг * 6| — а1г» Ьг)/пе1, хг = ( — аг1» 61 + аы * Ьг) ~деС. Показать с помощью численного примера, что формулы Крамера не являются обратно устойчивым алгоритмом. Указание: выбрать почти вырожденнУю матРипУ А и пРавУю часть (ЬмЬг]т (а1гагг)г.
Какое влиЯние имеет свойство обратной устойчивости на величину невязки? Свой численный пример вы можете построить вручную на бумаге (используя, например, четырех- разрядную десятичную арифметику с плавающей точкой) либо с помощью карманного калькулятора или компьютера. Вопрос 2.9 (средней трудности). Пусть  — верхняя двухдиагональная матрица порядка и, т.е. ненулевые элементы присутствуют лишь на ее главной диагонали и первой наддиагонали. Построить алгоритм, точно вычисляющий величину к (В) = 9В9 '9В '9 (ошибки округлений игнорируются).
Другими словами, нельзя пользоваться итерационным алгоритмом типа оценщика Хэйджера. Ваш алгоритм должен быть возможно более экономичным; оказывается, что можно ограничиться 2п — 2 сложениями, и умножениями, п делениями, 4п — 2 операциями взятия модуля и 2п — 2 сравнениями. (Если ваш алгоритм не укладывается в эти границы, но близок к ним, то он вполне приемлем.) Глава 2. Решение линейных уравнений Вопрос 2,10 (легкий; Т Ва1). Пусть А — матрица размера и х п. Показать, что !1АТ А)!~ !)АЙЯ кг(АтА) кг(А) Пусть М вЂ” положительно определенная и х п-матрица, а Т, — ее множитель Холесского, так что М = Х Т~. Показать, что ~(М)(г = ~Д(~ ~и кг(М) = югЮ .
Вопрос 2.11 (легкий; о. Ва1). Пусть А — симметричная положительно опре- деленная матрица. Показать, что ~а;,.~ < (а„а,,)'~~. Вопрос 2.12 (легкий; 3. Ва1). Показать, что если 0 1 где 1 — единичная и х п-матрица, то ко(У) = )(У)(г ))1' "11Р = 2п+ )Щгл.
Вопрос 2.13 (средней шрудности). В этом вопросе мы обсудим, как решать систему Ву = с, если известен быстрый способ решения систем вида Ах = Ь и матрица А — В в том или ином смысле «мвла». 1. Доказать формулу Шермана — Моррисона: пусть А — невырожденная матрица, и и и — векторы-столбцы и матрица А+пот также невырожденна. Тогда (А+ иит)-~ А — » (А-~иитА-»)/(1+ итА — 'и) Более общо, доказать формулу Шермана — Моррисона-Вудбери: пусть (? и г' — прямоугольные матрицы размера и х Ь, где Ь < и, и пусть А— квадратная и х и-матрица. Матрица Т = 1 + Ъ'тА 'Ь' тогда и только тогда невырожденна, когда невырожденна матрица А + 1?1'т; при этом (А+ [11'т)-ь = А — ' — А-'|1Т вЂ” 'Ъ'тА — ' 2. Предположим, что имеется быстрый алгоритм для решения систем вида Ах = Ь. Показать, как построить быстрый алгоритм для решения системы Ву = с, где В = А + иит. 3. Предположим, что имеется быстрый алгоритм для решения систем вида Ах = Ь, и пусть величина ИА — В(~ мала.
Описать итерационную схему для решения системы Ву = с. Насколько быстрой сходимости вы ожидаете от своего алгоритма? Указание: использовать итерационное уточнение. Вопрос 2.14 (средней трудносгли. программирование). Импортируйте из Ые111Ь подпрограмму, решающую систему Ах = Ь гауссовым исключением с частичным выбором главных элементов. Вы должны найти ее в БАРАСК'е (на фортране, ЫЕТЫВ/1арас)г) или СЬАРАСК'е (на языке С, Ь1ЕТЫВ/с1араск); в обоих случаях вйеягх есть главная программа. (Возможно, вы захотите поработать и с более простой программой вйеаг.) Измените вйеагх (и, возможно, некоторые из подпрограмм, к которым она обращается) так, чтобы вместо частичного выполнялся полный выбор; полученную программу назовите йеср.
Вероятно, простейшим вариантом является модификация программы вйесг2 и использование ее вместо вйесгг. Маг1аЬ-реализацию программы йеср см. в НОМЕРАСЕ/Мас1аЬ/йеср.ш. Сравните вйевгх и йеср на многих случайно порожденных матрицах различных порядков (доходящих, скажем, до 30). Задавая х и вычисляя Ь = Ах, вы можете получить системы, для которых правильный ответ известен. Точность вычисленного решения х проверяйте следующим образом. Сначала исследуйте границы ошибок »Ейй («Рогшаг«1 ЕВВог») 2.9. Вопросы к главе 2 1О? и ВЕКК («Вас(«вагб ЕВНог»), вычисляемые программами; своими словами объясните смысл этих границ. Пользуясь знанием точного ответа, убедитесь, что граница РЕЕК верна. Далее найдите точное число обусловленности путем явного обращения матрицы и сравните это число с оценкой ЕСОР, определяемой программой.
(На самом деле, ВСОМО есть оценка величины, обратной к числу обусловленности.) Затем проверьте, что отношение )))Гф ограничено умеренным кратным числа тасйерз/Ксопо. Наконец, нужно проверить, что (масштабированная) обратная ошибка Л:— 'ОАŠ— Ь|(/((ОАО '9хй + '9Ьй) тпасЬерз) в каждом случае является величиной порядка единицы. Более точно, ваш ответ на данный вопрос должен включать в себя хорошо документированную распечатку программы яеср, объяснение, как генерировались случайные матрицы (см.
об этом ниже), и таблицу, содержащую следующие столбцы (или, что предпочтительно, графики каждого из столбцов данных, отнесенного к первому столбцу): ° номер тестовой матрицы (соответствующий ее номеру в объяснении способа генерирования); ° ее порядок; ° информация, получаемая от вяевчх: — коэффициент роста, определяемый программой (в идеальном случае, он не должен быть много больше единицы), оценка числа обусловленности (1/КСОМО), — отношение числа 1/КСО1«О к явно вычисленному вами числу обусловленности (в идеальном случае, это отношение должно быть близко к единице), — граница ошибки ЕЕВВ, — отношение числа РЕЕК к подлинной ошибке (в идеальном случае, это отношение не меньше единицы и не намного больше ее; исключением является «удачный» случай, когда подлинная ошибка равна нулю), — отношение подлинной ошибки к числу с/КСОВО (в идеальном случае, это отношение должно быть не больше единицы или, чуть меньше ее; исключением является «удачный» случай, когда подлинная ошибка равна нулю), — масштабированная обратная ошибка В/е (в идеальном случае, должна быть величиной порядка 0(1) нли, возможно, 0(п)), — обратная ошибка ВЕВВ/е (в идеальном случае, должна быть величиной порядка 0(1) нли, возможно, 0(п)), — время работы программы в секундах; ° такая же информация, получаемая от яеср.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
