Дж. Деммель - Вычислительная линейная алгебра, страница 89
Описание файла
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]), что доказывает теорему Пейджа.