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

Примерно до 75-го шага она переоценивает величину действительной ошибки. Все же и оценка относительной ошибки правильно указывает на наличие нескольких верных десятичных разрядов в вычисленном старшем собственном значении. Собственные значения с номерами 2, 3 и 4 (им соответствуют верхние красные, зеленые и синие плюсы на левой верхней диаграмме рис. 7.3) сходятся аналогичным образом, хотя для всякого «собственное значение» сходится немного быстрее, чем собственное значение» + 1. Таково типичное поведение алгоритма Ланцоша. На левой нижней диаграмме рнс.

7.3 сходимость измеряется с помощью величин да е.. Чтобы понять смысл этой диаграммы, посмотрим, что происходит с вектором Ланцоша ды когда сходится первое собственное значение. Сходнмость означает, что соответствующий собственный вектор е1 почти принадлежит крыловскому подпространству, натянутому на векторы Ланцоша.

В частности, поскольку первое собственное значение сошлось после и = 50 шагов Ланцоша, вектор е1 очень мало отличается от некоторой линейной комбинации векторов ды ..., дае. Поскольку векторы 9; попарно ортогональны, вектор дь для й > 50 должен быть почти ортогонален вектору ем Это подтверждается черной кривой на левой нижней диаграмме, которая к шагу 50 опускается до уровня, меньшего чем 10 7. Красная кривая соответствует второй компоненте 388 Глава 7, Итерационные методы для задач на собственные значения вектора йы которая к шагу бО достигает уровня 10 д. Несколькими шагами позже сравнимую малость приобретают зеленая и синяя кривые (т. е.

третья и четвертая компоненты векторов 9ь). Обсудим теперь поведение четырех младших собственных значений, которым соответствуют три правых диаграммы рис. 7.3. Матрица А и начальный вектор 91 были выбраны так, чтобы проиллюстрировать некоторые осложнения в сходимости метода Ланцоша и подчеркнуть, что сходимость не всегда происходит столь очевидным образом, как в только что рассмотренном случае четырех старших собственных значений.

В частности, мы взяли значение, примерно равное 10 т, для 91(999), т. е. для компоненты вектора 9з в направлении собственного вектора для второго слева собственного значения ( — 2.81). Это значение в 10д раз меньше, чем все другие компоненты вектора 9ы которые равны между собой. Кроме того, в качестве третьего и четвертого слева собственных значений (т. е, собственных значений с номерами 998 и 997) мы взяли очень близкие числа — 2.700001 и — 2.7. Сходимость наименьшего собственного значения матрицы Тд к Л1доо(А) и — 3.03 происходит столь же «гладко», как и для старших собственных значений. К 40-му шагу оно имеет 1б верных десятичных разрядов.

Второе слева собственное значение матрицы Ты указываемое красным цветом, демонстрирует вначале ложную сходимоснчь к третьему слева собственному значению матрицы А, находящемуся вблизи — 2.7. В самом деле, точечная красная линия на правой средней диаграмме рис. 7.3. показывает, что для шагов Ланцоша с номерами 40 < к < 50 собственное значение Лддд(Тд) согласуется с Лддд(А) в шести десятичных разрядах. Для тех же значений й соответствующая оценка ошибки (красная пунктирная линия) свидетельствует, что Лддд (Тд) в трех или четырех десятичных разрядах совпадает с некоторым собственным значением матрицы А. Причина ложной сходимости в том, что построение крыловского подпространства начинается с вектора, имеющего очень малую компоненту (а именно, 10 т) в направлении еддд.

Это подтверждается красной кривой на правой нижней диаграмме, начинающейся с уровня 10 т. Лишь на 45-м шаге появляется большая компонента по направлению еддд. Только с этого момента, когда в крыловском подпространстве собственный вектор еддд уже достаточно хорошо представлен, собственное значение Лодд(Тд) снова может начать сходиться, теперь к своему окончательному значению Лддд(А) -2.81. Это видно из верхней и средней диаграмм правого ряда.

По мере прогресса этого второго этапа сходимости компонента в направлении еддд снова убывает и становится очень малой, когда Лддд(Тд) достаточно точно аппроксимирует Лддд(А). (Количественное описание связи между скоростью сходимости и величиной 9~~еддд дает теоРема КаниэлЯ вЂ” Саада, обсУждаеман ниже.) Если бы о1 был шочно оРтогонален вектоРУ еддд (т. е. вместо гедде — 10 мы имели бы 91теддд — — 0), то все последующие векторы Лаяцоша тоже были бы ортогональны к еддд.

Это означало бы, что Лддд(Тд) не может сойтись к Лддд(А). (Доказательство этого утверждения вынесено в вопрос 7.3). На рис. 7.4 показана эта ситуация; вектор 9~ для него был немного изменен так, чтобы выполнялось условие 9~ еддд — — О. Мы видим, что здесь вообще не появляется т приближения к собственному значению Лддд(А) — 2.81. 389 7.3. Алгоритм Ланцоша в точной арифметике 99 шагов алгоритма Ланцоша (с полной переортогоналнзацней) для матрицы А. 3 И .«л 3 1- т 8 ° О ' е ю ае зе «е ее ее ю ае ю гю -ел Номер шага Рис. 7.4.

Алгоритм Ланцоша в применении к матрице А. Начальный вектор дг ортогонален собственному вектору, соответствующему второму (с левого конца спектра) собственному значению — Ул81. Приближение к этому собственному значению вычислить не удается. 99 шагов алгоритма Ланпоша (с полной переортогоналнзацней) для матрицы А. .«л х -а« х « -зл 3 о ае х 8 ел о О,» ' е 1« ю ае «е ю ю ю ю ю гю -эл Номер шага Рис. 7.5. Алгоритм Ланцоша в применении к матрице А. Третье н четвертое (с левого конца спектра) собственные значения равны.

Вычисляется только одно приближение к этому двойному собственному значению. К счастью, если г)г выбирается случайным образом, то вероятность для него оказаться ортогональным какому-либо собственному вектору чрезвычайно мала. Чтобы получить «статистическое» подтверждение, что никакие собственные значения не были упущены, мы всегда можем повторно применить алгоритм Ланцоша с другим случайным вектором г)г. 390 Глава 7. Итерационные методы для задач на собственные значения Другим источником «ложной сходимости» являются (почти) кратные собственные значения; в нашем случае это третье и четвертое (с левого конца спектра) собственные значения Лддд(А) = — 2.700001 и Лддт(А) = — 2.7.

Исследуя поведение Лддд(Т«), которому соответствует самая нижняя зеленая кривая на верхней и средней правых диаграммах рис. 7.3, мы видим, что на шагах Ланцоша с номерамч 50 < 1«< 75 происходит лодкина сход«»мостпь этого собственного значения к числу — 2.7000005, находящемуся посередине между двумя ближайшими собственными значениями матрицы А.

Это не заметно при уровне разрешения, даваемом верхней диаграммой, но очевидно из горизонтального сегмента, который сплошная зеленая кривая на средней диаграмме имеет для шагов Ланцоша с номерами 50 < й < 75. Начиная с шага 76 устанавливается быстрая сходимость к окончательному значению Л999(А) = — 2.700001. Между тем, четвертое (с левого конца спектра) собственное значение Л»97(Т»), показанное синим цветом, демонстрирует ложную сходимость к числу, находящемуся вблизи Лдда(А) — 2.64.

Синяя точечная линия на средней правой диаграмме показывает, что вблизи й = 61 собственные зна- ченнЯ Лддт(Т«) и Ладе(А) совпадают в девЯти десЯтичных РазРЯдах. НачинаЯ с шага й = 65, устанавливается быстрая сходимость к окончательному значению Лддт(А) = — 2.7. Это же можно видеть из нижней правой диаграммы, где компоненты в направлениях е997 и еддд увеличиваются на шагах с номерами 50 < й < 65; они снова убывают, когда собственные значения вступают в зону быстрой сходимости. Если бы Лддт(А) было е точиости двойным собственным значением, то (в точной арифметике) Ть имела бы лишь одно собственное значение, близкое к Л997(А), а не два.

(Доказательство этого утвер»клелия вынесено в вопрос 7.3.) На рис. 7.5 показана эта ситуация; матрица А для него была совсем немного изменена так, чтобы число — 2.7 стало двойным собственным значением. Заметим, что на любом шаге имеется лишь одно приближение к Лддд(А) = Л997(А) = — 2.7. К счастью, существует ряд приложений, в которьгх достаточно определить одну копию каждого (кратного) собственного значения, а знание кратностей несущественно. Кроме того, кратные собственные значения вместе с правильными кратностями можно находить посредством «блочных методов Ланцоша» (см. алгоритмы, упоминаемые в разд.

7.6). Исследуя другие собственные значения на верхней правой диаграмме рис. 7.3, мы видим, что ложная сходимость является весьма обычным событием. Об этом свидетельствуют многочисленные короткие горизонтальные сегменты, образованные плюсами одного цвета; они затем сменяются фазами убывания к меньшему собственному значению. Например, седьмое (с левого конца спектра) собственное значение на разных шагах Ланцоша хорошо аппроксимируется пятым (черный цвет), шестым (красный) и седьмым (зеленый) собственными значениями матрицы Тд.