Математическая энциклопедия - итерационные методы

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

Первый И. м. был предложен К. Якоби [1] для вычисления собственных значений и векторов действительных симметричных матриц (см. Вращений метод). Метод переносится на комплексные эрмитовы матрицы, а также на более широкий класс нормальных матриц.

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

При этом роль подобного преобразования с (элементарной) матрицей Sk состоит в уменьшении евклидовой нормы текущей матрицы А k, т. е. в приближении ее к нек-рой нормальной матрице. В качестве Т k обычно берется матрица вращений или ее унитарный аналог. Смысл подобного преобразования с этой матрицей, как и в классич. методе Якоби, заключается в аннулировании внедиагонального элемента в нек-рой эрмитовой матрице, связанной с матрицей А k+1, напр, в матрице С ростом kматрицы А k сходятся к матрице диагонального или квазидиагонального вида, а накопленное произведение матриц Sk и Т k дает матрицу, столбцами к-рой являются приближенные собственные векторы либо векторы, образующие базисы инвариантных подпространств матрицы (см. [2], [3]).

продолжение Итерационные методы...

Наряду с вышеописанными методами развиваются алгоритмы другого класса, так. наз. степенные методы. Самым эффективным методом этого направления, наиболее широко применяющимся для решения задач среднего размера, является QR -алгоритм (см. [4], [5]). Итерации QR-алгоритма проводятся по следующей схеме:

здесь Qkортогональная или унитарная, a Rkправая треугольная матрица. Для перехода от А k к Ak+1 сначала находится ортогонально-треугольное разложение матрицы А и, после чего матрицы Qk и Rk перемножаются в обратном порядке. Если положить Rk=Rk ...R1, то из (1) следует схема

Таким образом, QR-алгоритм генерирует последовательность матриц А k, ортогонально подобных исходной' матрице А 1;при этом трансформирующая матрица является ортогональной компонентой в разложении (2) матрицы

При итерации по схеме (1) матрицы А k сходятся к правой треугольной или квазитреугольной матрице, причем скорость сходимости поддиагональных элементов к нулю управляется отношениями модулей различных собственных значений и является, вообще говоря, довольно медленной. Для ускорения сходимости QR- алгоритма используются так наз. сдвиги, что приводит к следующему видоизменению схемы (1):

Обычно применение сдвигов (напр., xk=а nn^(k) )позволяет, получить быструю сходимость внедиагональных элементов последней строки к нулю (асимптотически квадратичную в общем случае и кубическую для эрмитовых матриц) и соответственно быструю стабилизацию диагонального элемента ( п, п). После того, как значение этого элемента установилось, дальнейшие итерации проводят с главной подматрицей порядка n-1, и т. д. Собственные векторы результирующей треугольной матрицы после умножения на накопленное произведение ортогональных матриц Qk дают собственные векторы исходной матрицы А 1.

Итерации по схеме (1) либо (3) применяют к матрице, предварительно приведенной к так наз. форме Хессенберга. Говорят, что матрица Аимеет правую форму Хессенберга, если а ij=0 при i>j+l. QR-алго ритм обладает свойством сохранять форму Хессенберга исходной матрицы, что намного удешевляет стоимость каждой итерации. Есть и другие важные возможности уменьшения объема вычислений, напр., неявное использование сдвигов, что позволяет находить комплексно сопряженные собственные значения действительных матриц, не прибегая к комплексной арифметике.

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

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

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

Эта последовательность сходится к собственному вектору, отвечающему l1, при выполнении следующих условий: 1) все элементарные делители матрицы А, относящиеся к l1,линейные; 2) нет других собственных значений с тем же модулем; 3) в разложении исходного вектора х 0 по корневому базису матрицы Аимеется нетривиальная компонента по собственному подпространству для l1. Однако сходимость степенного метода, как правило, медленная и определяется отношением величин двух старших по модулю собственных значений.

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

Метод обратных итераций есть по существу степенной метод для матрицы имеющей сильно доминирующее собственное значение Реализация формулы (5) требует, однако, решения линейной системы с матрицей и даже при использовании специальных методов для разреженных систем предъявляет повышенные требования к оперативной памяти по сравнению со степенным методом.

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

Выбирается начальная п r-матрица Q0 с ортонормированными столбцами. Исходя из Q0, строится последовательность матриц Qk по схеме: