Аппроксимация матрицы с положительными элементами матрицей единичного ранга

Аннотация

Большинство современных математических методов решения задач естествознания, техники, экономики требуют решения линейных задач большой размерности. Для понижения вычислительной сложности используется специальная структура матриц, соответствующих этим задачам. Блочно-малоранговые матрицы представляют из себя приближение с хорошей точностью плотных матриц в малопараметрическом формате. Блоки малого ранга представляются в виде произведения матриц меньшего размера. Это позволяет значительно экономить машинную память. Методы приближенной факторизации блочно-малоранговых матриц могут быть применены для приближенного решения и предобуславливания систем с плотными матрицами в задачах аэро-, гидро- и электродинамики, а также в прикладной статистике и логистике. Для построения малопараметрических представлений матриц, основанных на малоранговых аппроксимациях отдельных блоков, широко используются алгебраические методы. В данной работе рассмотрен эффективный способ аппроксимации блоков матрицы с положительными элементами матрицей единичного ранга, т. е. в виде произведения столбца на строку. Решение задачи ищется среди допустимых представлений, минимизирующих среднее значение модулей логарифмов отношения приближенного представления элемента к точному значению. Аппроксимирующая задача сведена к задаче линейного программирования, для которой двойственная задача является задачей построения циркуляции минимальной стоимости в полном двудольном графе с пропускными способностями всех дуг равными единице. Для решения полученной задачи предложен алгоритм, имеющий вычислительную сложность не более O(|I|·|J|·log(|I|·|J|)), где I – множество строк в блоке, J – множество столбцов в блоке