Главная » Все файлы » Просмотр файлов из архивов » PDF-файлы » Дж. Деммель - Вычислительная линейная алгебра

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

PDF-файл Дж. Деммель - Вычислительная линейная алгебра, страница 9 Квантовые вычисления (53191): Книга - 7 семестрДж. Деммель - Вычислительная линейная алгебра: Квантовые вычисления - PDF, страница 9 (53191) - СтудИзба2019-09-18СтудИзба

Описание файла

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 показано, как улучшить точность решения, вычисленного гауссовым исключением, посредством простого и экономичного итерационного метода. Чтобы обеспечить высокую скорость работы гауссова исключения и других алгоритмов линейной алгебры, вычисления должны учитывать организацию памяти современных компьютеров. Эта тема обсуждается в равд.

Свежие статьи
Популярно сейчас
Почему делать на заказ в разы дороже, чем купить готовую учебную работу на СтудИзбе? Наши учебные работы продаются каждый год, тогда как большинство заказов выполняются с нуля. Найдите подходящий учебный материал на СтудИзбе!
Ответы на популярные вопросы
Да! Наши авторы собирают и выкладывают те работы, которые сдаются в Вашем учебном заведении ежегодно и уже проверены преподавателями.
Да! У нас любой человек может выложить любую учебную работу и зарабатывать на её продажах! Но каждый учебный материал публикуется только после тщательной проверки администрацией.
Вернём деньги! А если быть более точными, то автору даётся немного времени на исправление, а если не исправит или выйдет время, то вернём деньги в полном объёме!
Да! На равне с готовыми студенческими работами у нас продаются услуги. Цены на услуги видны сразу, то есть Вам нужно только указать параметры и сразу можно оплачивать.
Отзывы студентов
Ставлю 10/10
Все нравится, очень удобный сайт, помогает в учебе. Кроме этого, можно заработать самому, выставляя готовые учебные материалы на продажу здесь. Рейтинги и отзывы на преподавателей очень помогают сориентироваться в начале нового семестра. Спасибо за такую функцию. Ставлю максимальную оценку.
Лучшая платформа для успешной сдачи сессии
Познакомился со СтудИзбой благодаря своему другу, очень нравится интерфейс, количество доступных файлов, цена, в общем, все прекрасно. Даже сам продаю какие-то свои работы.
Студизба ван лав ❤
Очень офигенный сайт для студентов. Много полезных учебных материалов. Пользуюсь студизбой с октября 2021 года. Серьёзных нареканий нет. Хотелось бы, что бы ввели подписочную модель и сделали материалы дешевле 300 рублей в рамках подписки бесплатными.
Отличный сайт
Лично меня всё устраивает - и покупка, и продажа; и цены, и возможность предпросмотра куска файла, и обилие бесплатных файлов (в подборках по авторам, читай, ВУЗам и факультетам). Есть определённые баги, но всё решаемо, да и администраторы реагируют в течение суток.
Маленький отзыв о большом помощнике!
Студизба спасает в те моменты, когда сроки горят, а работ накопилось достаточно. Довольно удобный сайт с простой навигацией и огромным количеством материалов.
Студ. Изба как крупнейший сборник работ для студентов
Тут дофига бывает всего полезного. Печально, что бывают предметы по которым даже одного бесплатного решения нет, но это скорее вопрос к студентам. В остальном всё здорово.
Спасательный островок
Если уже не успеваешь разобраться или застрял на каком-то задание поможет тебе быстро и недорого решить твою проблему.
Всё и так отлично
Всё очень удобно. Особенно круто, что есть система бонусов и можно выводить остатки денег. Очень много качественных бесплатных файлов.
Отзыв о системе "Студизба"
Отличная платформа для распространения работ, востребованных студентами. Хорошо налаженная и качественная работа сайта, огромная база заданий и аудитория.
Отличный помощник
Отличный сайт с кучей полезных файлов, позволяющий найти много методичек / учебников / отзывов о вузах и преподователях.
Отлично помогает студентам в любой момент для решения трудных и незамедлительных задач
Хотелось бы больше конкретной информации о преподавателях. А так в принципе хороший сайт, всегда им пользуюсь и ни разу не было желания прекратить. Хороший сайт для помощи студентам, удобный и приятный интерфейс. Из недостатков можно выделить только отсутствия небольшого количества файлов.
Спасибо за шикарный сайт
Великолепный сайт на котором студент за не большие деньги может найти помощь с дз, проектами курсовыми, лабораторными, а также узнать отзывы на преподавателей и бесплатно скачать пособия.
Популярные преподаватели
Нашёл ошибку?
Или хочешь предложить что-то улучшить на этой странице? Напиши об этом и получи бонус!
Бонус рассчитывается индивидуально в каждом случае и может быть в виде баллов или бесплатной услуги от студизбы.
Предложить исправление
Добавляйте материалы
и зарабатывайте!
Продажи идут автоматически
5076
Авторов
на СтудИзбе
455
Средний доход
с одного платного файла
Обучение Подробнее