Архив публикаций

Тезисы

XV-ая конференция

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

Борзых А.Н.

Россия, 199034, г. Санкт-Петербург, Университетская наб, д.7-9, Тел.: (812) 328-20-00, E-mail: alex@borz.ru

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

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

Отмечается ряд интересных особенностей предлагаемого алгоритма.

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

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

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

• открыть в PDF формате