Быстрые алгоритмы решения линейных систем с тёплицевыми матрицами

FAST ALGORITHMS FOR SOLVING SYSTEMS OF LINEAR EQUATIONS WITH TOEPLITZ MATRICES

Gerel Dorzheeva

graduate student, Kalmyk state university named after B.B. Gorodovikova, Russia, Elista

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

Abstract. The formulas handling nondegenerate Toeplitz matrices with complex elements, or specifying a known or new giving the possibility of creating efficient algorithms for the multiplication inverse of a Toeplitz matrix by a vector in the mass calculations.

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

Keywords: matrix, Toeplitz matrices; matrix inversion; unstable systems of linear equations; regularization; skew-circulants are obtained; cocirculate; spectral decomposition; Toeplitz rank.

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

Введем тёплицевы (су)- и (^-разложения произвольной квадратной комплексной матрицы на основе их связи с решениями двух неявных уравнений Сильвестра. Далее приведены различные соотношения, связывающие тёплицевы (су)- и (^-разложения заданной матрицы с тёплицевыми (су)- и («^-разложениями матриц, полученных в ряде преобразований этой матрицы. Установлены связи тёплицевых (с«)-, («с)-, (/и)- и (и/)-разложений одной и той же матрицы. Там же введены более общие тёплицевы разложения как решения им соответствующих однозначно разрешимых уравнений Сильвестра и выведены связи различных типов таких разложений для одной и той же матрицы.

Установим связи тёплицевых (с«)- и (^-разложений и затем и общих тёплицевых разложений с разложениями матрицы, обратной невырожденной исходной.

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

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

Для произвольного комплексного а определим квадратную порядка п комплексную матрицу соотношением 0а = ((а/1)  Рп-1)Рп, в котором матрицы 1ки Рк — единичная и перъединичная матрицы порядка к. Всевозможные многочлены от 0а образуют коммутативное кольцо с единицей а-циркулянтов, для которых будем использовать обозначения Са(х), указывая в качестве их аргументов п-мерные векторы их нулевых столбцов. В частных случаях а = 1 и а = —1 а-циркулянты — это, соответственно, циркулянты и косоциркулянты, для которых наряду с введенными обозначениями будем использовать стандартные обозначения С(х) и 5(у). Для а Ф 0 матрицы 0а невырожденны, 0-циркулянты являются нижнетреугольными тёплицевыми матрицами, для которых будем использовать стандартные обозначения Х(х), всевозможные многочлены от матрицы являются верхнетреугольными тёплицевыми матрицами, для которых будем использовать обозначение Хт(х) наряду со стандартным обозначением, у которого векторный аргумент — транспонированная нулевая строка. При а Ф 0 каждое семейство а-циркулянтов диагонализуемо единым преобразованием, отличным лишь диагональной матрицей-сомножителем от матрицы дискретного преобразования Фурье.

Для квадратной комплексной матрицы В порядка п рассмотрим уравнение

(О,В - ВО !)Рп = О. (1)

Данное уравнение именуется неявным уравнением Сильвестра и только правым множителем Рп отличается от непрерывного уравнения Сильвестра, а левым — от дискретного уравнения Сильвестра. Все три данные эквивалентные уравнения можем просто назвать формами уравнения Сильвестра. Так как спектры матриц и не имеют пересечений (в чем можно убедиться, приметив, что 0"[ = 1п, а 0п_1 = — 1п), то из непрерывной формы уравнения Сильвестра следует его (следовательно, и остальных двух форм) однозначная разрешимость. Далее без особых оговорок следует использовать более удобную в каждом конкретном случае форму уравнения Сильвестра, помня об их эквивалентности и в особенности о равенстве рангов матриц их левых частей.

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

(О В - ВО,) Рп = 2хут — В = С(хЖу). (2а)

Именно из-за такой простой и наглядной связи этих двух уравнений была выбрана в качестве исходной неявная форма уравнения Сильвестра.

Введем по аналогии с инволютивным преобразованием транспонирования В ■*—- Вт инволютивное преобразование пертранспонирования В -«—► РпВТРп и обозначение для этой операции В —— Вр, отталкиваясь от определения симметричной матрицы, удовлетворяющей условию В = Вт, при этом условие В = Вр влечет именование такой матрицы персимметричной, что оправдывает введенное определение.