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

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

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

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

PDF-файл из архива "Дж. Деммель - Вычислительная линейная алгебра", который расположен в категории "". Всё это находится в предмете "квантовые вычисления" из 7 семестр, которые можно найти в файловом архиве МГУ им. Ломоносова. Не смотря на прямую связь этого архива с МГУ им. Ломоносова, его также можно найти и в других разделах. .

Просмотр PDF-файла онлайн

Текст 89 страницы из PDF

Итерационные методы для задач на собственные значения 149 шагов аппгритма Ланцсша (с полной пересргоганвлиэацией) для маэрицм А 149 шагов алгоритма Лвицоша (без пвреортогонализации) дпя мат рицм А ° э Ю Номер шага Номер шага Дейсэвигельные локальныв ошибки в ссбственнык значениях 1-4 и оценки для них Действигел ыкые локальные ошибки в собственных значениях 1-4 и оценки дпя ни» йф й $ Я пе э4 й яо 3Й шо 4 и ин нк Номер шага (с полной переоргсгснализвциай) Компаненгы векгоров Лвнцоша в направлениях собственных векгоров 1-4 и и Номер шага (без переортагснализации) Компсншпы еекшров Лвнцоша в направленияк собственных вв«коров 1-4 ° ' ш но Номер шаге (беэ переоргогоналимции) е и гш Номер шага (с полной пераорэогоналиэацией) Рис.

7.7. 149 шагов алгоритма Ланцоша для матрицы А. Столбец 150 (правый край верхних диаграмм) показывает собственные значения матрицы А. Диаграммы левого ряда соответствуют алгоритму без переортогонализацин, а диаграммы правого ряда — алгоритму с полной переортогонализацней. (Цветной вариант рис. 7.7 см. на обложке книги. — Перев.) 7.4. Алгоритм Ланцоша в арифметике с плавающей точкой 395 синяя линия на левой средней диаграмме) возле )г = 95 и предсказывается возрастанием красной кривой на левой нижней диаграмме, свидетельствующей о росте компоненты по направлению ег в векторах Ланцоша.

Эта компонента достигает максимума вблизи и = 95, а затем начинает убывать. Наконец, в районе й = 145 появляется третья копия числа Л1(А). Снова это событие сопровождается и предсказывается изменениями на двух нижних левых диаграммах. Если бы мы продолжали процесс Ланцоша далее, то периодически получали бы новые копии многих ранее сошедшихся чисел Ритца. О Обсуждаемая ниже теорема объясняет явления, которые мы наблюдали в данном примере, и указывает практичный критерий для выборочной ортогонализации векторов Ланцоша. Чтобы не завязнуть в анализе, берущем в расчет все округления, мы выделим, опираясь на существующий практический опыт, те немногие ошибки округлений, которые действительно важны, а остальные будем просто игнорировать [197, рвзд. 13-4). Это позволит нам записать алгоритм Ланцоша без переортогонализации одним уравнением Пуз-г + Б = Ауд — одг5 — Вд- чд- .

(7.3) В этом уравнении переменные обозначают величины, действительно хранимые в машине, за исключением вектора 71, который представляет ошибки округлений, проистекающие из вычисления правой части, а затем числа ~3 и вектора 91+м Норма [[71[[э ограничена величиной 0(в~[А[~), где е — машинный эпсилон, и это все, что нам нужно знать о Л. Кроме того, мы будем пользоваться точным спектральным разложением Тг = 1гАУ~, поскольку известно, что ошибки округлений, совершенных при его вычислении, не важны для нашего анализа.

Таким образом, Ъ' — ортогональная матрица, в то время как столбцы матрицы Сгг не обязаны быть ортогональными. Теорема 7.3 (Пэйдж). Примем обозначения и предположения предыдущего абзаца. Кроме того, положим Яг = [ды...,г7г), Ъ' = [ом...,иг] и А = йа8(Вы...,Вг). Столбцы угд = Яки, матрицы ЯгЪ' будем по-прежнему называть векторами Ритца, а числа В; — числами Ритца. Тогда 0(в[[А[[) Уг,Яг;1 = 3 ~ (а)[ ° Иными словами, компонента уг,щ,.гг вычисленного вектора Ланцоша г7гч.1 т в направлении вектора Ритца уг; = Яьо, обратно пропорциональна величине Дг~ог(й)~, являющейся оценкой погрешности для соответствующего числа Ритца В, (см.

утверждение 2 теоремы 7.2). Поэтому, когда число Ритца сходится, а его оценка погрешности Вг[ог(й)[ приближается к нулю, вектор Ланцоша дьг1 приобретает большую компоненту в направлении вектора Ритца уг о В результате векторы Ритца становятся (почти) линейно зависимыми, что мы и вццели в примере 7.2. На рис. 7.8 приведены графики оценки погрешности [Дю;(1г)[/[Л,(А)[ [)7ге;(й)[ДА[[ и величины уат,.уча для наибольшего числа Ритца (1 = 1, верхний график) и второго по величине числа Ритца (1 = 2, нижний график) в нашем примере с диагональной матрицей порядка 1000.

Согласно теореме Пэйджа, произведение этих двух величин должно иметь порядок 0(е), что подтверждается нашими полулогарифмическимн графиками: на каждом из них обе кривые симметричны относительно средней линии ч/е. 39б Глава 7. Итерационные методы для задач на собственные значения Оценки ошибок и компоненты векторов Лен цоша для первого вектора Ритце ы й Я оо Я и" и "й' Н го ге 'п по, о о о 'о 'о' ио оо ою Номер шаги (без переортогонзлизации) Оценки ошибок и компоненты векторов Лен пошл для второго лектора Ритпе й ш о6 оо го и и и и'оо о8 зол ! но . оо йм из и ое о оо ио Номер шага (без переортогонолиззции) Рис. 7.8, Алгоритм Ланцоша без переортогонализации в применении к матрице А.

Показаны первые 149 шагов для наибольшего собственного значения (верхний график) и Лля второго по величине собственного значения (нижний график). Как и на предыдущих рисунках, пунктирные линии соответствуют оценкам ошибок. Линии, составленные из символов + и о, указывают значение величины умгу~.д, т. е, компот ненты вектора Ланцоша длтд в направлении вектора Ритца для наибольшего числа Ритца (з = 1, верхний график) или для второго по величине числа Ритца (о = 2, нижний график). Доказапдельство (теоремы Пэйджа).

Начнем с того, что запишем А уравне- ний (7.3), отвечающих значениям у от 1 до )е, одним соотношением А()л = д,т, +]О,...,О,)у,д,+д]+Р; =д,Те+О,г)„.де, +К„ где ее~ — — [0,...,0,1] — вектор размерности ге, а Рд = ]уд,...,ул] — матрица, составленная из ошибок округлений. Опуская для простоты индекс и, имеем А(„г = ЯТ + Щет + Е. Умножая обе части слева на Дт, получаем (о)~А(е = (е~бкТ+ Щ~о)е + Я~Е.

Поскольку Я~АД вЂ” симметричная матри- 7.4. Алгоритм Лаицоюа в арифметике с плавающей точкой 397 ца, матрица Я~ЯТ + ОД~де + Я~У совпадает со своей транспонированной, откуда выводим О = Д'ат — Та'О) + 6(д'де' — вата) + (Д'Р— Г'д). (7.4) Пусть д и о суть соответственно число и вектор Ритца, так что Ти = до. Заметим, что величина о 11(ей Я)и = ]1Ь(й)] (4 (Яо)] (7.5) есть произведение оценки погрешности 11о(й) и величины д~(Яо) = 4~у, т. е. компоненты вектора д в направлении вектора Ритца. Теорема Пэйджа утверждает, что это произведение должно иметь величину 0(е]~А~~). Чтобы доказать это, получим выражение для едгЯ, преобразуя равенство (7.4), а затем воспользуемся соотношением (7.5). С этой целью введем дополнительные упрощающие предположения относительно округлений. Всякий столбец матрицы Я получается делением вектора в на его норму, поэтому в пределах машинной точности все диагональные элементы матрицы ЯтЯ равны 1; мы будем считать их точно равными 1.

Далее, вектор з' = а — а.д = а — (~Та)щ вычисляется в алгоритме Ланцоша так, чтобы быть ортогональным вектору су „следовательно, дг. 1 и Б ортогональны с почти полной машинной точностью. Поэтому 4Д.гщ = Я~Я)гч-цз = 0(е)' для простоты будем считать, что ЯтЯ) та = О. Введем представление Я~Я = 1+ С + С~, где С вЂ” нижнетреугольная матрица. Наши предположения об округлениях означают, что в матрице С отличные от нуля могут быть только элементы, находящиеся на второй поддиагоналн и ниже ее. Имеем ЯгЯТ вЂ” ЩтЯ = (СТ вЂ” ТС) + (С Т вЂ” ТСг). Учитывая расположение нулей в С и Т, легко показать, что матрица СТ вЂ” ТС нижняя строго треугольная, а матрица С Т вЂ” ТС верхняя строго треугольная.

Поскольку в векторе е отлична от нуля только последняя компонента, в матрице ей~Я отлична от нуля только последняя строка. Более того, из наших предположений об округлениях следует, что последний элемент этой строки равен нулю. Это означает, в частности, что матрица ей~0 нижняя строго треугольная, а матрица Я~де верхняя строго треугольная. Используя нижний строго треугольный вид матриц едгЯ и СТ вЂ” ТС, можно вывести из (7.4) равенство О = (СТ вЂ” ТС) — ~Зед~Я+ Ь, где Š— нижняя строго треугольная часть матрицы Ягà — ГтЯ. Умножал (7.6) слева на от, а справа на и и учитывая соотношение (7.5) и равенство ил(СТ— ТС)о = итСио' — оотСо = О, получаем о 17(ей Я)о = (13о(й)] (д (Яо)] = и Ьо. Так как ]игби~ < Щ = ОЩгà — ГтСЯ = ОЦГ)]) = 0(е]]А]]), то Р (й)] [7т(Юо)] =ОИА1]), что доказывает теорему Пейджа.

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