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

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

Файл №1156793 Дж. Деммель - Вычислительная линейная алгебра (Дж. Деммель - Вычислительная линейная алгебра) 90 страницаДж. Деммель - Вычислительная линейная алгебра (1156793) страница 902019-09-18СтудИзба
Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 90)

398 Глава 7. Итерационные методы для задач на собственные значения 7.5. Алгоритм Ланцоша с выборочной ортогонализацией Обсудим модификацию алгоритма Ланцоша, которая обладает почти столь же высокой точностью, как алгоритм с полной переортогонализацией, и почти столь же низкой стоимостью, как алгоритм без переортогонализации.

Эта модификация называется алгоритмом Ланцоша с выборочной ортогонолизацией. Как уже отмечалось в предыдущем разделе, наша цель состоит в том, чтобы поддерживать в вычисленных векторах Ланцоша уг как можно ббльшую степень ортогональности (для обеспечения высокой точности), достигая этого путем ортогонализации дг к возможно меньшему числу векторов (чтобы снизить стоимость). Теорема Пэйджа (теорема 7.3 из предыдущего раздела) показывает, что векторы дь теряют ортогональность вследствие приобретения больших компонент в направлениях векторов Ритца усе = ь/гио отвечающих сошедшимся числам Ритца б;; на сходимость же указывают малые значения оценки погрешности Вг!ш(Ь)!. Иллюстрация этого явления была дана в примере 7.2. Итак, простейший вариант выборочной ортогонзлизации состоит в том, чтобы следить на каждом шаге за оценками погрешностей 17ь!и;(Й)! и, когда какая-то оценка становится слишком малой, проводить ортогонализацию вектора г во внутреннем цикле алгоритма Ланцоша по отношению к соответствующему вектору у; ь: г = г — 1у, „г)у; ь.

Величина Вь!щ(й) ! считается малой, если она меньше, чем ь/е!!А!!. Действительно, в этом случае, согласно теореме Пэйджа, компонента !у~ель+1! = !у,'.гг!/!!г!!г, скорей всего, превосходит уровень |/е. (На практике можно использовать !)Тя!! вместо !!А!), поскольку первое число известно, а второе, может быть, и нет.) В результате приходим к снедующему алгоритму: Алгоритм 7.3. Алгоритм Ланцоша с выборочной ортогонализацией длл вычисления собственных значений и собственных векторов матрицы А = Атг 91 — — Ь/)!Ь!!г~ Во = О, чо = 0 /агу = 1 Фо Ь г = Ад оз — 9 г г г одчд 171-1чд-1 /" Провести выборочную ортогонализацию по отношению к сошедшимся векторам Ригнца '"/ /ог г < к, таких, что (3г!и;Я! < Я!!Тг!! г = г — (уг г)у; ь т епд /ог А = !!г!!г если /дд = О, то прекратить выполнение алгоритма чд+1 = /111 Вычислить собственные значения и собственньге векторы матрицьг Т.

и оценки погрешностей в них епд /ог В следующем примере описывается, что происходит с нашей диагональной матрицей порядка 1000 при использовании этого алгоритма (НОМЕРАСЕ/ Ма11аЬ/ЬапсгозБе1есСОгСЬоб.ш). 7.5. Алгоритм Ланцоша с выборочной ортогоналнзацней 399 Числа Рнтца, чьн векторы выбраны длл ортогоналнзацнн 22 $ ае оа ЕО 5 22 2.1 О ОО 1ЕО Номер шага Числа Рнтца, чьн векторы выбраны длл ортогоналнзацнн -2.1 -а! ОО 1ОО Номер шага Рис. 7.9.

Алгоритм Ланцоша с выборочной ортогоналнзацией в применении к матрице А. Показаны числа Ритца, соответствующие векторам Рнтца, выбранным длн ортогоналнзации. Пример 7.3. Поведение алгоритма Ланцоша с выборочной ортогонализацией визуально неотличимо от поведения алгоритма с полной переортогонализацией, показанного на трех правых диаграммах рис. 7.7. Иными словами, выборочная ортогонализация обеспечивала такую же точность, как полная переортогонализация.

Для всех матриц Огь наименыпие сингулярные числа были больше уровня 1 — 10 а. Это означает, что выборочная ортогонализация действительно поддерживает ортогональность векторов Ланцоша в пределах примерно половины рабочей точности. 400 Глава 7. Итерационные методы для задач иа собственные значения На рис.

7.9 показаны числа Ритца, соответствующие векторам Ритца, выбранным для переортогонализации. Так как выбираемые векторы отвечают сошедшимся числам Ритца, а первыми сходятся наибольшие и наименьшие числа, то рисунок состоит из двух графиков: большие сошедшиеся числа Ритца изображены на верхнем графике, а малые — на нижнем. Верхний график соответствует числам Ритца, сошедшимся, по крайней мере, с половиной машинной точности, тем самым числам, что показаны на правой верхней диаграмме рис.

7.7. Всего для ортогонализации было выбрано 1485 векторов Ритца из общего числа их 149*150/2 = 11175. Таким образом, чтобы поддерживать (почти) тот же уровень ортогональности векторов Ланцоша,что и в полной переортогонализации, в методе выборочной ортогонализации пришлось затратить лишь 1485/11175 — 13% работы по сравнению с алгоритмом полной переортогонализации. На рис. 7.10 показано, как метод Ланцоша с выборочной ортогонализацией осуществляет поддержание ортогональности векторов Ланцоша к векторам Ритца, отвечающим двум старшим числам Ритца. Верхний график есть суперпозиция двух графиков рис. 7.8, изображающих оценки погрешностей и компоненты в направлениях векторов Ритца для метода Ланцоша без переортогонализации.

Нижний график показывает те же величины для метода выборочной ортогоналнзации. Обратим внимание на то, что на шаге я = 50 оценка погрешности для наибольшего собственного значения (пунктирная черная линия) достигает порогового значения /е. Соответствующий вектор Ритца выбирается для ортогонализации (это показано плюсами в верхней части верхнего графика рис. 7.9); в результате компонента в направлении этого вектора исчезает с нижнего графика рис. 7.10. Несколькими шагами позже, а именно при я = 58, оценка погрешности для второго по величине числа Ритца достигает уровня ~/е, и соответствующий вектор Ритца также выбирается для ортогонализации.

Оценки погрешностей на нижнем графике продолжают убывать, достигая в конечном счете уровня машинного эпсилон и оставаясь далее на этом уровне. В то же время на верхнем графике оценки погрешностей с какого-то момента вновь начинают расти. О 7.6. Другие возможности Выборочной ортогонализацией история не заканчивается, так как стоимость симметричного алгоритма Ланцоша можно снизить в еще большей степени.

Оказывается, что в течение многих шагов после того, как вектор Ланцоша был ортогонализован к конкретному вектору Ритца у, ортогонализации по отношению к этому вектору р не требуется. Поэтому можно устранить значительную часть работы по переортогонализации из алгоритма 7.3. Существуют простые и дешевые рекурсии, позволяющие определить момент, когда переортогонализация необходима (224,192). Другое усовершенствование состоит в использовании оценок погрешностей для эффективного различения сошедшихся и «ложно сошедшихся» собственных значений (1981.

Наиболее современная реализация алгоритма Ланцоша описана в (125]. Другой вариант реализации выбран в пакете АНРАСК (г1ЕТ11В/зса1арас1с/геабше.аграс1с [171, 2331). Если алгоритм Ланцоша применяется к матрице (А — а1) ', полученной из А сдвигом и обращением, то следует ожидать, что в первую очередь сойдут- 401 7.б. Другие возможности Оценки ошибок и компоненты векторов Лвнцоше дня первого и второго векторов Рит 1О' и" м" м" 10 10" 10 " о ОО ню Номер шага (без пвреортогонвпизвции~ Оценки ошибок и компоненты векторов л 10 и" Рнс. 7.10.

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

Отметим, что в методе выборочной ортогонализации эти компоненты исключаются в результате первых выборочных ортоговализаций на шагах 50 (1 = 1) и 58 (з = 2). ся собственные значения, ближайшие к и. Существуют и другие методы «предобусловливания» матрицы А, обеспечивающие более быструю сходимость к некоторым собственным значениям. Например, в задачах квантовой химии, где типичны матрицы А со строгим диагональным преобладанием, широко используется метод Дэвидсона [бО).

Этот метод может быть скомбинирован с методом Якоби (229). с с с. о 0 в со 8 с о к и ОО с з с й с и с а к с з и 11 йс я о с 8 .1. я3 ой с с х с а с у с 10" о 10 110 110 Номер шага (о выборочной ортогонвпизвцией ) 402 Глава 7. Итерационные методы для звлвч нв собственные значения Т.Т. Итерационные алгоритмы для несимметричной проблемы собственных значений Для несимметричной матрицы А описанный выше алгоритм Ланцоша не пригоден. Имеются две альтернативные возможности. Первая состоит в том, чтобы использовать алгоритм Арнольдо [алгоритм 6.9). Вспомним, что в алгоритме Арнольди вычисляется ортогональный базис ф, крыловского подпространства К»[А, 91), в котором «Зета» = Нь— верхняя хессенбергова матрица (а не симметричная трехдиагональная). Аналог процедуры Рэлея — Ритца для этого случая состоит в том, чтобы аппроксимировать собственные значения матрицы А собственными значениями матрицы Ны Поскольку матрица А несимметрична, ее собственные значения могут быть комплексными и/или плохо обусловленными.

Характеристики

Тип файла
PDF-файл
Размер
40,83 Mb
Тип материала
Высшее учебное заведение

Список файлов книги

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