Дж. Деммель - Вычислительная линейная алгебра (1156793), страница 90
Текст из файла (страница 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), в котором «Зета» = Нь— верхняя хессенбергова матрица (а не симметричная трехдиагональная). Аналог процедуры Рэлея — Ритца для этого случая состоит в том, чтобы аппроксимировать собственные значения матрицы А собственными значениями матрицы Ны Поскольку матрица А несимметрична, ее собственные значения могут быть комплексными и/или плохо обусловленными.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
