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

Далее зти обозначения циклически повторяются по направлению к середине спектра. Для лучшего понимания сходимости рассмотрим поведение старших собственных значений матриц Та, .они указаны крестиками вверху каждого столбца. Видио, что с ростом и старшие собственные значения возрастают.

Это следствие теоремы Коши о перемежаемости: ведь Та есть подматрица матрицы Та+1 (см. вопрос 5.4). В действительности, теорема Коши утверждает большее, а именно, что все собственные значениЯ матРиЦы ТаЧ.1 пеРемежаютсл собственными значениями подматрицы Та, т. е. Л;(Та+1) > Л;(Та) > Лт+1(Тач.т) > Лгьт(Та). Иначе говоря, Л11Та) монотонно возрастает с ростом 16 для любого фиксированного значения 1, а не только для 1 = 1 (что соответствует старшему собственному значению).

Это утверждение иллюстрируется последовательностями символов одного типа, направленными вправо и вверх. Совершенно аналогично поведение младших собственных значений: нижний крестик в каждом столбце на рис. 7.2 указывает наименьшее собственное 384 Глава 7. Итерационные методы для задач па собственные значения 9 шагов алгоритма Лвнцошя (с полной переортогонвлизвцией) лля матрицы А в Я о Й о 1 в в о о ь в о о !о Номер швгв 29 шагов алгоритмов Лвнцошв (с полной ) А со 1 у о оя о Й 3 О о и и и и и Номер швов Рис. 7.2. Алгоритм Ланцоша в применении к матрице А.

На верхней диаграмме представлены первые 9 шагов алгоритма, а на нижней — первые 29 шагов. В столбце я указаны собственные значения матрицы То, а в самом правом столбце ()О-м столбце верхней диаграммы и ЗО-м столбце нижней диаграммы) — собственные значения матрицы А. значение соответствующей матрицы Тл, и эти собственные значения монотонно убывают с ростом )с. Точно так же монотонно убывает в-е собственное значение, считая от левого конца спектра.

Это тоже простое следствие теоремы Коши о перемежаемости. Мы можем задаться вопросом, к какому собственному значению матрицы А сходится собственное значение Л;(Тл) с ростом и. Ясно, что наибольшее собственное значение Лт(Тл) должно сходиться к наибольшему собственному значению Лт(А). Действительно, когда алгоритм Ланцоша дойдет до шага )с = и (в предположении, что он не остановится раньше из-за того, что какое-то Д, равно нулю), то будет получена матрица Т„, подобная матрице А, поэтому Лв(Т„) = Лт(А).

Аналогично, в-е по старшинству собственное значение Лв(Тл), 385 7.3. Алгоритм Ланцоша в точной арифметике монотонно возрастая, должно сойтись к 1-му по старшинству собственному значению Л;(А) матрицы А (если не произойдет преждевременной остановки алгоритма Ланцоша), а собственное значение Лг~, г(Тг), монотонно убывая, должно сойтись к собственному значению Л„.ьг,(А). Все эти сходящиеся последовательности представлены последовательностями символов одного типа на рис.

7.2 и других рисунках данного раздела. Рассмотрим нижнюю диаграмму рис. 7.2. Для й, начиная примерно с 16, верхние и нижние плюсы образуют горизонтальные линии, находящиеся на уровне крайних собственных значений матрицы А, показанных в самом правом столбце; такое их поведение свидетельствует о сходимости. Аналогично, верхняя последовательность квадратиков образует горизонтальную линию на уровне второго по старшинству собственного значения матрицы А (указанного в самом правом столбце). Эта последовательность сходится несколько позже, чем последовательности крайних собственных значений.

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

Теперь мы более подробно изучим характер сходимости, вычислим действительные ошибки чисел Ритца и сравним эти ошибки с оценками из утверждения 2 теоремы 7.2. Для той же матрицы, которая использовалась для рис. 7.2, были проведены 99 шагов алгоритма Ланцоша; результаты показаны на рис. 7.3. Верхняя левая диаграмма относится к наибольшим собственным значениям, а верхняя правая — к наименьшим.

Две средние диаграммы рис. 7.3 показывают ошибки в вычисленных собственных значениях: левая — для четырех старших собственных значений, а правая — для четырех младших. Цвета на средних диаграммах соответствуют цветам на верхних. Ошибки измеряются (и наносятся на диаграммы) тремя способами: ° Глобальные ошибки (сплошные линии) вычисляются по формулам ~ Лг(Тг)— Лг(А))/)Л,(А)!. Деление на )Л;(А)) производится для нормализации ошибок так, чтобы их значения были заключены между 1 (что соответствует отсутствию какой-либо точности), с одной стороны, и величиной, примерно равной 10 1в (машинное эпсилон, или полная возможная точность), с другой стороны.

С ростом й глобальная ошибка монотонно уменьшается; мы ожидаем, что в конечном счете она достигнет уровня машинного эпсилон, если только алгоритм Ланцоша не остановится преждевременно. ° Локальные ошибки (линии, состоящие из точек) вычисляются по формулам ш1пДЛ,(Тг) — Л (А))ДЛ;(А)!. Локальная ошибка измеряет расстояние между Л;(Ть) и ближайшим собственным значением Л, (А) матрицы А, которое не обязательно совпадает с предельным собственным значением Л;(А).

Мы 386 Глава 7. Итерационные методы для задач на собственные значения % шзгов алгоритма Ланцоша )о полной переортогонализацией) для матрицы А 99 шагов ыгоритма Ланцоша )о полной переортогонализацией) для ышрицы А й 44 й з и ю м «ю м м ш ю гю Номер шага и» ю «ш «и ю ю мз Номер шага Действителен ив ошибки в о об отавы мы х значенияк (997-1000) и оценки дпя них Дейотвитшънзм ошибки в ооботвенных значаннияю х)!-4) и оценки для них '$1 9$5 М 44 44 44 Ю Ю 14 44 Вз Номер шага )полная нереортогонализация) Компоненты вюгторов Ланцоша в направлениях ооботвенных векторов )997-1 000) Номер шага (полная пврвортогонвлизация) Компоненпл векторов Ланцоша в направлениях ооботввнных векторов )! -4) 3 ~$ $~ в и м» «ю ю» ю ю ю Номер шаге )полная пвреортопшелизация) 4 Гз ВВ Вз «44 44 М Ю 44 !44 Номер шага )полная перво рта голан иззция) Рис.

7.3. 99 шагов алгоритма Ланцоша для матрицы А. Левые диаграммы относятся к наиболыпим собственным значениям, а правые — к наименьшим. На двух верхних диаграммах показаны сами собственные значения, на двух средних — ошибки в них (глобальным ошибкам соответствуют сплошные линии, локальным ошибкам— линии, состоящие вз точек, и оценкам ошибок — пунктирные линии). На двух нижних диаграммах показаны компоненты векторов Ланцоша по собственным направлениям. Цвета всех трех диаграмм одного вертикального ряда согласованы. (Цветной вариант рис. 7.3 см на.

обложке' книги. — Перев.) 387 7.3. Алгоритм Лаипоша и точкой арифметике вводим эту характеристику потому, что локальная ошибка подчас оказывается значительно меньше глобальной. е Оценки ошибок (пунктирные линии) — это величины ))1«ю; (1«) ИЛ, (А) (, вычисляемые алгоритмом (с точностью до нормирующих коэффициентов ~Л;(А) ~, которых алгоритм, разумеется, не знает!). Две нижние диаграммы рис. 7.3 показывают компоненты векторов Ланцоша да в направлениях собственных векторов: левая диаграмма соответствует собственным векторам для четырех старших собственных значений, а правая диаграмма — собственным векторам для четырех младших собственных значений. Иными словами, на диаграммах изображены величины 9~~е = щ:,(у), где е.

есть у-й собственный вектор диагональной матрицы А. Значения й изменяются от1до 99, азначенияу от1до4(налевойднаграмме) и от997до 1000 (направой диаграмме). Для изображения компонент взята логарифмическая шкала; символы «+» и «о» указывают соответственно положительные н отрицательные значения компонент. Ниже этн диаграммы используются для объяснения сходимости собственных значений. Теперь с помощью рис. 7.3 мы исследуем сходимость более подробно.

Наибольшие собственные значения матриц Та (нм соответствуют верхние черные плюсы на верхней левой диаграмме рис. 7.3) начинают сходиться к своему предельному значению ( 2.81) немедленно. После 25 шагов Ланцоша они имеют шесть верных десятичных разрядов, а к 50-му шагу верны с полной машинной точностью. Глобальная ошибка показана сплошной черной линией на левой средней диаграмме. Локальная ошибка (черная линия, состоящая из точек) после небольшого количества шагов совпадает с глобальной, хотя «случайно» может оказаться значительно меньше, если собственное значение Л;(Т») на своем пути к Л;(А) окажется очень близким к некоторому другому собственному значению Л,(А). Пунктирная черная линия на той же диаграмме — это оценка относительной ошибки, вычисляемая алгоритмом.