Дж. Деммель - Вычислительная линейная алгебра, страница 9
Описание файла
PDF-файл из архива "Дж. Деммель - Вычислительная линейная алгебра", который расположен в категории "". Всё это находится в предмете "квантовые вычисления" из 7 семестр, которые можно найти в файловом архиве МГУ им. Ломоносова. Не смотря на прямую связь этого архива с МГУ им. Ломоносова, его также можно найти и в других разделах. .
Просмотр PDF-файла онлайн
Текст 9 страницы из PDF
Данное задание иллюстрирует трудности, сопряженные с разработкой высоконадежных программ численного анализа. Ваша задача — написать программу, вычисляющую 2-норму з = ЬхЙг = (2,, г х;) по зацанным хы...,х„. Наиболее очевидный (и неудовлег 1Л творительный) алгоритм выглядит так: в=0 Гог 1 = 1 $о п 1.9. Вопросы к главе 1 37 8=8+я, епЖог 8 = в«1г»(в) Мы считаем этот алгоритм неудовлетворительным, потому что он не обладает совокупностью следующих желательных свойств: 1. Результат должен вычисляться с высокой точностью (т. е, почти все разряды вычисленного результата должны быть верными), если Оз9з не находится (почти) за пределами области нормализованных чисел с плавающей точкой.
2. Алгоритм должен быть в болыпинстве случаев почти столь же быстр, как и приведенная выше программа. 3. Он должен работать на любой «разумной» машине, включая, возможно, и те, арифметика которых отлична от 1ЕЕЕ-арифметики. Это означает, что работа алгоритма не может приводить к остаиову, если 9х9» не (почти) превосходит наибольшего числа с плавающей точкой. Чтобы проиллюстрировать имеющиеся здесь трудности, отметим, что указанный выше алгоритм терпит неудачу, если п = 1, а хг больше квадратного корня из наибольшего числа с плавающей точкой (в этом случае х~ вызывает переполнение, что приводит к выдаче символа +со в 1ЕЕЕ-арифметике и астапову в большинстве других арифметик), а также если и = 1 и я» меньше квадратного корня из наименьшего нормализованного числа с плавающей точкой (в этом случае хз» является машинным нулем и алгоритм может выдать нуль в качестве результата).
Масштабирование чисел х, путем деления их на шах ~х;~ приводит к потере свойства 2, поскольку деление обычно гораздо дороже умножения или сложения. Если же умножать х«на с = 1/шах; ~я,~, то возможно переполнение при вычислении с, даже если шах, ~х,~ > О. Программа вычисления 2-иормы настолько важна, что была включена в число основных подпрограмм линейной алгебр»Ь или ВЕАЯ (от Ваз1с 1апеаг А13еЬга ЯпЬгоп11пез). Эти подпрограммы должны иметься на любом компьютере [169). Подробное обсуждение пакета В1 АЯ дается в разд.
2.6.1; документацию к нему и реализации-шаблоны можно найти в ХЕТ1ДВ/Ыаз. В частности, шаблон, находящийся в ХЕТТ!В/с31-Ып/пес11Ьйес.р1/Ыав/вппп2 1, обладает свойствами 1 и 3, но не свойством 2. Эти шаблоны задуманы как отправная точка при разработке реализаций для конкретных архитектур (что является более простой задачей, чем порученное вам создание полностью переносимой программы). Итак, при составлении своей программы вы должны думать о вычислении 9х9» как об одном из фрагментов библиотеки численного анализа, имеющейся на любом компьютере. Тщательно продуманная реализация вычисления 2-нормы описана в 135). Для проверки правильности своей реализации вы можете воспользоваться тестовой программой из ХЕТЫВ/Ыез/вЫа$1, Ваш отчет по настоящему заданию должен содержать полностью тестированную реализацию, а также сопоставление времени ее работы с временем приведенного выше «очевидного» алгоритма на тех примерах, где обе программы работают успешно.
Интересно, насколько вы сможете приблизиться к выполнению всех выдвинутых условий. Частое использование слова «почти» в их формулировках указывает область 38 Глава 1. Введение для компромисса: можно частично ослабить одно из условий, чтобы более полно удовлетворить 1ругие. Например, вы можете исследовать, насколько упростится задача, если ограничиться машинами с 1ЕЕЕ-арифметикой. Указание; счн гать, что алгоритму известны значения порогов переполнения и машинного нулю Существуют переносимые программы для вычисления этих значений (см.
ХЕТ1В/с81-Ь1п/пеь11Ьйес.р!/1арас1с/пг11/э1ашсЬ.1). Вопрос 1.20 (легкий; средней трудности). Мы пронллюстрируем чувствительность корней многочлена к малым возмущениям его коэффициентов с помощью МаС1аЬ-программы Ро1ур1ос, находящейся в НОМЕРАСЕ/Ма11аЬ/ ро1ур1ог.ш.! Многочлен на входе программы задается набором своих корней.
К его коэффициентам программа прибавляет случайные возмущения, вычисляет корни возмущенного многочлена и наносит их на диаграмму. Входными параметрами являются: г=вектор, составленый из корней многочлена; е=максимвльное относительное возмущение в произвольном коэффициенте многочлена; ш=число возмущенных многочленов, чьи корни выводятся на диаграмму. 2 (легкий). Первый пункт вашего задания — применить программу к приведенным ниже входным данным. Во всех случаях выбирайте гп достаточно большим, чтобы получилась по-настоящему плотная диаграмма, но не настолько большим, чтобы пришлось ждать результата чересчур долго.
Значение ш, равное нескольким сотням или, может быть, 1000, вполне подходит. Вы можете изменить масштаб на осях, если разрешение графика слишком мало или слишком велико. ° г=(1:10); е=1е-З, 1е-4, 1е-5, 1е-б, 1е-?, 1е-8, ° г=(1:20); е=1е-9, 1е-11, 1е-13, 1е-15, ° с=[2,4,8,16,...,1024); е=1е-1, 1е-2, 1е-З, 1е-4. Постройте и свои примеры с комплексно-сопряженными корнями. Какие корни наиболее чувствительны к возмущениям? 3 (средней трудности).
Второй пункт вашего задания — модифицировать программу так, чтобы она вычисляла число обусловленности с(1) для каждого корня. Иначе говоря, относительное возмущение е в любом коэффициенте не должно изменять корень г(!) более чем на е*с(!). Измените программу таким образом, чтобы она строила круги с центрами г(!) и радиусами е*с(1), и убедитесь, что эти круги содержат корни возмущенных многочленов (по крайней мере, при е настолько малом, что линеаризация, используемая при определении числа обусловленности, правильно отражает положение вещей).
Вы должны представить несколько диаграмм с кругами и возмущенными собственными значениями, а также свои объяснения на- блюдаемых явлений. 4 (средней трудности). Для последней части задания обратите внимание на то, что формула для с(!) теряет смысл, когда ее знаменатель р'(г(!)) равен нулю. Это означает, что г(!) есть кратный корень многочлена р(к). Тем не менее мы можем и для кратного корня надеяться получить какие-то верные ! Нвпомннм, что в книге НОМЕГАОЕ используется кнк сокращение для ННЬ-префнкса Ьир //пи п.иагп.агя/Ьоокв/<1епппе1/г1ещще!.с!ваз.
1.9. Вопросьг к главе 1 39 знаки в вычисленном его приближении. В этой части задания выясняется, насколько чувствительным к возмущениям может быть кратный корень многочлена. Положим р(х) = д(х) (х — г(1)), где д(г(1)) 1е О, а т — кратность корня г(1). Нужно вычислить га корней, ближайших к г(1), для слабо возмущенного многочлена р(х) — д(х)е и убедиться, что они отстоят от г(1) на расстоянии ~е~'~ .
Если, например, т = 2, то корень г(1) возмущается на е'1~, что много больше, чем е, если (е! << 1. Большие значения т приводят к еще бблыпим возмущениям. Пусть е — величина порядка машинного эпсилон, представляющая ошибки округлений в процессе вычисления корня. Из сказанного выше следует, что в случае т-кратного корня лишь — я часть разрядов вычисленного приближения будут верными. Вопрос 1.21 (средней трудности). Применить метод бисекции (см. алгоритм 1.1) к вычислению корней уравнения р(х) = (х — 2)в = О.
Значения многочлена р(х) вычисляются по правилу Горнера. Использовать Мас1аЬ-программу, находящуюся в НОМЕРАСЕ/Ма11аЬ/Ьйаесс.ш, или составить собственную программу. Убедиться в том, что очень малые изменения входного интервала могут совершенно изменить вычисленное значение корня. Изменить алгоритм таким образом, чтобы процесс деления пополам прекращался, когда ошибка в вычисленном значении р(х) столь велика, что правильный знак многочлена определить не удается. Использовать для этого оценку ошибки, обсуждавшуюся в основном тексте главы. Глава 2 Решение линейных уравнений 2.1.
Введение В этой главе обсуждаются теория возмущений, алгоритмы и анализ ошибок при решении системы линейных уравнений Ах = Ь. Все алгоритмы являются вариантами гауссова исключения. Они называются прлмвьми методами по той причине, что в отсутствие ошибок округления дают точное решение системы за конечное число шагов. В противоположность этому, в итерационных методах, обсуждаемых в гл. 6, строится последовательность хо, хы хз,... все лучших приближенных решений системы Ах = Ь; итерации прекращаются (с вычислением следующего вектора х, еы когда получено достаточно точное приближение хь Какой метод, прямой или итерационный, окажется более быстрым или более точным, зависит от матрицы А и скорости, с какой последовательность (х,) сходится к х = А г Ь.
Сравнительные достоинства прямых и итерационных методов подробно обсуждаются в гл. 6. Пока что мы ограничимся указанием, что пользователю следует выбрать прямые методы, если отсутствует информация о происхождении матрицы А' или решение системы нужно получить с гарантированной точностью и в заранее известное время. Остальная часть данной главы организована следующим образом. В рвзд. 2.2 обсуждается теория возмущений для системы Ах = Ь; на этой теории основываются практические оценки ошибок из равд. 2.4.
Алгоритм гауссова исключения для случая плотных матриц, описан в равд. 2.3. В равд. 2.4 анализируются ошибки в гауссовом исключении н выводятся практические оценки для них. В разделе 2.5 показано, как улучшить точность решения, вычисленного гауссовым исключением, посредством простого и экономичного итерационного метода. Чтобы обеспечить высокую скорость работы гауссова исключения и других алгоритмов линейной алгебры, вычисления должны учитывать организацию памяти современных компьютеров. Эта тема обсуждается в равд.