Оптимизация сингулярных чисел матриц, зависящих от параметров, с использованием гибридных алгоритмов

Оптимизация сингулярных чисел матриц, зависящих от параметров…

ISSN 1812-3368. Вестник МГТУ им. Н.Э. Баумана. Сер. Естественные науки. 2016. № 5

аппроксимация спектров динамических систем, малоранговая аппроксимация

больших матриц, восстановление потенциальной части трехмерного векторного

поля, численное обращение операторов лучевых преобразований в двухмерной

компьютерной томографии, исследование динамических систем с кратными ган-

келевыми сингулярными числами, квантовая теория информации [5–10].

Некоторые практические задачи связаны с получением надежных оценок экс-

тремальных сингулярных чисел. Новые алгоритмы сингулярного разложения

больших матриц, основанные на малоранговой тензорной аппроксимации, называ-

емой TT-форматом (tensor train format), предложены в работе [11]. Указанные ал-

горитмы позволяют вычислять несколько экстремальных (т. е. наибольших или

наименьших) сингулярных чисел и соответствующих сингулярных векторов для

больших структурированных матриц, заданных в TT-формате. Возникающая в

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

последовательности задач оптимизации меньшей размерности (при этом каждый

тензор ядра блочной TT-декомпозиции может быть уточнен с использованием лю-

бого стандартного метода сингулярного разложения). Численные эксперименты

проведены для нескольких типов TT структурированных матриц, таких как гиль-

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

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

эффективность предложенных алгоритмов при определении нескольких экстре-

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

дартными алгоритмами сингулярного разложения. К этому направлению также

следует отнести задачи построения неотрицательных матриц с заданными экстре-

мальными сингулярными числами, которые рассмотрены в работе [12]. При этом

необходимо учитывать, что сингулярные числа, подобно собственным значениям,

не являются всюду дифференцируемыми функциями элементов матриц [13]. Сле-

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

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

специальных методов анализа чувствительности сингулярных чисел [14, 15].

В последнее время широкое распространение получили алгоритмы анализа

сингулярных спектров [16]. Это обусловлено простотой структуры и низкой вы-

числительной стоимостью их реализации. В работе [16] на основе сравнения ре-

зультатов, полученных с использованием указанного подхода и методов глобаль-

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

спектров, в частности, применительно к построению различных моделей иссле-

дований. Вместе с тем, наблюдаемое увеличение вычислительной стоимости ре-

шаемых задач, связанное с ростом размера матриц исследуемых систем, стимули-

рует создание более эффективных алгоритмов.

Цель настоящей работы — разработка новых гибридных алгоритмов гло-

бальной недифференцируемой оптимизации, ориентированных на решение за-

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

раметров.