Приведение симметричной матрицы к трехдиагональному виду

Лекция 15

Метод Ланцоша

18.1. Подпространства Крылова [1]

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

Вспомним также, что использование процедуры Рэлея ‑ Ритца для корректировки системы векторов значительно повысило скорость сходимости метода. Отметим, что эта процедура использует матрицу , которая содержит некоторую, хотя и урезанную, информацию о матрице .

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

Наилучшим известным на сегодня выбором такой системы являются вектора следующего вида:

, (18.1)

где первый вектор выбирается произвольно, а все остальные вектора уже несут в себе информацию об исследуемой матрице .

Система векторов (18.1) порождает векторное пространство размерности . Напомним, что линейным подпространством, порожденным системой векторов , называется множество всех векторов , которые можно представить в виде линейной комбинации:

. (18.2)

Кстати, короче такое подпространство часто называется линейной оболочкой векторов . Линейные оболочки системы векторов вида (18.1) и называются подпространствами Крылова по имени советского академика, впервые использовавшего их для решения практических задач.

Система векторов хороша тем, что сами вектора этой системы содержат информацию о матрице . Однако у нее есть серьезный недостаток – эти вектора неортогональны.

Поясним это геометрической иллюстрацией (рис. 18.1). В результате первого умножения будет получен вектор, который повернут относительно исходного вектора на некоторый угол. Вновь умножая полученный вектор на матрицу , получаем следующий вектор , который также повернут на некоторый угол по отношению к предыдущему вектору. Из рассмотренного ранее степенного метода нам известно, что вектор при стремится к собственному вектору, соответствующему максимальному собственному значению. Таким образом, с ростом направление очередного вектора все меньше будет отличаться от направления предыдущего. На рис.18.1 это направление обозначено пунктирной линией.

Нам уже известно средство для «исправления» таких систем векторов – алгоритм Грама ‑ Шмидта. Применив его к системе можно получить равноценную систему векторов , но уже с ортогональными единичными векторами. Как мы сейчас увидим, алгоритм Грама ‑ Шмидта, вообще говоря, весьма трудоемкий, значительно упрощается для системы векторов .

Найдем несколько первых векторов этой ортогональной системы.

Первый вектор

1) обозначим исходный вектор (зерно подпространства) ;

2) длину этого вектора обозначим ;

3) тогда для получения первого вектора надо только нормировать исходный вектор:

. (18.2)

Второй вектор

1) вычисляем очередной вектор Крылова:

; (18.3)

2) вычитаем из этого вектора составляющую в направлении :

. (18.4)

Здесь введено обозначение:

. (18.5)

Отметим, что для вычисления не надо полностью вычислять значение квадратичной формы , но можно просто вычислить скалярное произведение векторов и , определенных на предыдущих шагах;

3) определяем длину вектора :

; (18.6)

4) нормируя вектор , получаем второй вектор ортогональной системы:

. (18.7)

Третий вектор

1) вычисляем очередной вектор Крылова:

; (18.8)

2) вычитаем из этого вектора составляющие в направлении и :

. (18.9)

Вновь обозначим

. (18.10)

Что касается произведения , то следует отметить, что согласно (18.8)

. (18.11)

Кроме того, учитывая, что согласно (18.7)

,

и в соответствии с (18.3) и (18.4)

,

получим

, (18.12)

т.е. специально вычислять это произведение не надо. Оно уже вычислено на предыдущем шаге.

Итак, окончательно для получаем

; (18.13)

3) вычисляем длину вектора

, (18.14)

которая, как нам уже известно, понадобится и на следующем шаге;

4) . (18.15)

Четвертый вектор :

1) ;

2) .

Здесь необходимо заметить, что . Вспомним, что при построении мы представили как сумму двух составляющих: одна направлена вдоль , другая вдоль , т.е.

,

где и – некоторые коэффициенты. Следовательно,

вследствие взаимной ортогональности векторов . Следовательно,

.

Это очень важный момент, определяющий в конечном счете эффективность и популярность метода Ланцоша: для определения вектора используются вектора и , но не нужен вектор !

Такие же рассуждения можно привести и для произвольного -го вектора – для его определения используются и и не нужны остальные вектора ;

3) ;

4) .

Теперь мы готовы сформулировать алгоритм построения ортонормированного базиса подпространства Крылова:

Задаемся произвольным начальным вектором длиной . Если уже определены вектора , то очередной вектор определяется следующим образом:

1. ; 2. ; 3. ; 4. ; 5. .

Для практического усвоения этого алгоритма полезно рассмотреть следующий пример.

Пример. Рассмотрим построение ортогонального базиса подпространства Крылова для матрицы

.

В качестве начального вектора («зерна») берем

.

Определяем :

.

Определяем :

.

Определяем :

,

.

Определяем :

, ,

.

Приведение симметричной матрицы к трехдиагональному виду

Почти вся необходимая нам информация о методе Ланцоша содержится в разд.18.1. Осталось сделать только еще одно наблюдение.

Составим из полученных векторов прямоугольную матрицу

. (18.16)

Попробуем применить алгоритм Рэлея ‑ Ритца, подробно рассмотренный в лекции 13. Для этого следует вычислить матрицу

(18.17)

Выше уже было отмечено, что для векторов , построенных по алгоритму Ланцоша,

при . (18.18)

Также были введены обозначения:

(18.19)

Следовательно, полученная в результате (18.17) матрица является трехдиагональной матрицей следующего вида:

(18.20)

При рассмотрении QR-алгоритма, отмечалось, что для трехдиагональных матриц этот метод обладает очень высокой эффективностью.

Пример. Продолжая рассмотрение предыдущего примера, получаем последовательность трехдиагональных матриц:

Для этой последовательности матриц имеем собственные значения:

Последняя строчка, естественно, содержит точные значения. Рассматривая последовательность максимальных , видим, что эти значения довольно быстро стремятся к максимальному собственному значению матрицы .

Важный для любого итерационного метода вопрос: когда можно прекращать вычисления? Оказывается, для решения этого вопроса в методе Ланцоша не требуется никаких дополнительных вычислений. Необходимое число на каждом шаге вычисляется в ходе основного алгоритма. Напомним, что есть длина вектора . Сам же вектор (рис. 18.2) это та составляющая очередного вектора Крылова – , которая перпендикулярна векторам и всем остальным векторам .

Если величина (длина ) мала, то это значит, что вектор уже очень близок по направлению к максимальному собственному вектору.

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

Заключительные замечания по методу Ланцоша:

1. Метод Ланцоша может рассматриваться как разновидность метода Грама ‑ Шмидта. При этом специальный выбор исходной системы векторов позволяет построить трехдиагональную матрицу, подобную данной.

2. Вычислительная эффективность метода для больших задач обусловливается:

1) трехдиагональной формой приведенной матрицы ;

2) при переходе к следующему шагу алгоритма (от матрицы к матрице ) элементы матрицы остаются без изменений и только добавляются элементы ;

3) в памяти ЭВМ одновременно надо хранить лишь три последних вектора .

Современные реализации метода Ланцоша гораздо сложнее рассмотренной нами простой и ясной схемы. Так, в силу вычислительных погрешностей ЭВМ для больших задач вектора в ходе вычислений перестают быть ортогональными. Поэтому периодически эти вектора приходится подвергать выборочной переортогонализации. Кроме того, оказывается, что, опять-таки из-за ошибок округления, процесс можно продолжить и после того как будет найден «последний» вектор . Причем, как ни странно, получаемые результаты оказываются полезными при определении собственных значений. Впрочем, обсуждение этих нюансов выходит за рамки настоящего курса. За дополнительной информацией по этому вопросу можно обратиться к [15.1]. А закончить обсуждение этого наиболее эффективного для задач большой размерности метода имеет смысл следующей цитатой [15.2]: «Интерес к нему (методу Ланцоша) в настоящее время определяется тем, что методы такого типа являются единственными среди известных, которые дают хотя бы какую-нибудь возможность решать спектральные задачи для очень больших разреженных матриц… Изящная теоретическая картина метода Ланцоша основательно нарушается при его практической реализации. Реальный процесс не обладает некоторыми свойствами, указанными точной теорией, но приобретает другие, не предсказанные ею… В этом методе пока еще слишком много неясного, и его практическое использование скорее похоже на искусство, чем на обоснованные вычисления».

Литература

15.1. Парлетт Б. Симметричная проблема собственных значений. Численные методы. – М.: Мир, 1983. – 384с.

15.2. Воеводин В.В., Кузнецов Ю.А. Матрицы и вычисления. – М.: Наука, 1984. – 320с.

[1] Крылов Алексей Николаевич (1863-1945) – советский кораблестроитель, механик и математик, академик АН СССР (академик Петербургской АН с 1916 г.), Герой Социалистического Труда (1943 г.). Автор многочисленных основополагающих трудов по теории корабля. Участник проектирования и постройки первых русских линкоров, активный участник решения основных технических вопросов военного и гражданского судостроения в СССР. Труды по теории магнитных и гироскопических компасов, артиллерии, механике, математике, истории науки. Создал ряд корабельных и артиллерийских приборов. Лауреат Государственной премии СССР (1941 г.)