ГЛАВА VI. РЕШЕНИЕ ПРОБЛЕМЫ СОБСТВЕННЫХ ЗНАЧЕНИЙ

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

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

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

§ 43. Метод вращений

Рассмотрим вещественную симметричную матрицу А порядка Определение ее собственных значений и собственных векторов равносильно отысканию такфй ортогональной матрицы для которой

есть диагональная матрица. В этом случае столбцы будут собственными векторами матрицы а диагональные элементы ее собственными значениями.

Среди всех ортогональных лреобразований подобия преобразование (43.1) минимизирует сумму квадратов внедиагональных элементов. Поэтому попытаемся находить

матрицу на основе какого-либо процесса минимизации данной суммы. Будем строить последовательность матриц

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

Для упрощения записи опустим индекс и исследуем результат преобразования

Обозначим через элементы матриц и пусть, в соответствии с (18.22), угол поворота матрицы вращения Ту есть а. Матрица А отличается от А двумя строками и двумя столбцами с номерами Если к тому же принять во внимание инвариантность евклидовой нормы к унитарным преобразованиям, то из (43.3) легко получить соотношение

связывающее суммы квадратов внедиагональных элементов матриц

Соотношение (43.4) означает, что для максимального уменьшения суммы квадратов внедиагональных элементов необходимо матрицу вращения Ту выбрать так, чтобы выполнялись два условия:

и

Второе из условий дает

Ясно, что посда выполнения преобразования (43.3) внедиагональные элементы матрицы А, находящиеся в позициях будут равны нулю.

Пусть есть сумма квадратов внедиагональных элементов матрицы из последовательности (43.2). В силу формулы (43.4) и выбора угла поворота

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

и далее будем иметь

Следовательно,

Согласно (43.3) любая матрица из последовательности (43.2) связана с исходной матрицей А ортогональным подобным преобразованием

Поэтому диагональные элементы и соответствующие столбцы матрицы

являются точными собственными значениями и точными собственными векторами некоторой симметричной матрицы где

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

Может показаться, что неравенства (43.6) свидетельствуют о весьма слабых свойствах построенного метода

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

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

Обозначим через и воспользуемся результатами теории возмущений из § 13. Матрица имеет собственные значения, совпадающие с диагональными элементами матрицы Поэтому в обозначениях § 13 из формулы (13.8) вытекает, что все элементы матриц являются величинами порядка . В терминах лостроенного метода это означает следующее. Во-первых, диагональные элементы матрицы приближают собственные значения матрицы А с точностью порядка независимо от их кратности. Кроме этого, если диагональные элементы близки к одному и тому же собственному значению, то внедиагональные элементы и на самом деле являются величинами порядка

Для максимального по модулю внедиагонального элемента матрицы соответствующие диагональные элементы не могут быть близкими. Следовательно, угол поворота, вычисляемый согласно (43.5), будет порядка Но тогда

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

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

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

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

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

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

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

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

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

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

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

Обратим внимание на некоторые детали, связанные с вычислением самих матриц вращения. Обозначим

Если то берем

В случае из (43.5) получаем, что

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

когда мал по сравнению с Но заметим, что

Следовательно,

Теперь первая из формул (43.9) совместно с (43.10) позволяет вычислить все элементы матрицы вращения с высокой относительной точностью. Если выражения

находить в соответствии с алгорифмом, описанным в § 18, то опорные элементы реально полученной матрицы вращения будут иметь вид (18.4). При этом

где

если умножение и деление на 2 осуществляются неточно, и

в противном случае. Проверку правильности этих соотношений мы предлагаем провести читателю в качестве упражнений.

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

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

соображений симметрии. Если матрица получена на цикле, то, используя оценку (43.11) и результаты исследований в §§ 19, 23, 32, заключаем, что

Опыт практического применения метода вращений показывает, что независимо от порядка матрицы обычно требуется выполнить не более 5—б полных циклов для максимального уменьшения суммы квадратов внедиагональных элементов. Однако ошибки округления оказывают основное влияние лишь на первых 2—3 циклах.

Для процессов с выбором максимального или оптимального элемента не удается получить оценку лучше, чем (43.12), или хотя бы сравнимую с ней. Как правило, вместо появляется множитель Но, по-видимому, это связано лишь с трудностью получения хорошей оценки, а не с тем, что такие процессы менее точны, чем циклические.

В заключение приведем одно полезное следствие из (43.12). Обозначим через точные собственные значения, через реально вычисленные. Если в формуле (43.12) взять 3, то из (13.9) вытекает, что

УПРАЖНЕНИЯ

(см. скан)

(см. скан)