РЕАЛИЗАЦИЯ АЛГОРИТМА НАХОЖДЕНИЯ РЕЗОЛЬВЕНТЫ МАТРИЦЫ С ИСПОЛЬЗОВАНИЕМ ПРИСОЕДИНЕННОЙ МАТРИЦЫ И ХАРАКТЕРИСТИЧЕСКОГО МНОГОЧЛЕНА

ШАМАНАЕВ П. А., КАТИН Д. А., ДЕСЯЕВ Е. В.

РЕАЛИЗАЦИЯ АЛГОРИТМА НАХОЖДЕНИЯ РЕЗОЛЬВЕНТЫ МАТРИЦЫ С ИСПОЛЬЗОВАНИЕМ ПРИСОЕДИНЕННОЙ МАТРИЦЫ И ХАРАКТЕРИСТИЧЕСКОГО МНОГОЧЛЕНА

Аннотация. В настоящей работе излагается реализация алгоритма вычисления резольвенты матрицы с использованием присоединенной матрицы и характеристического многочлена матрицы на языке Python. На графиках приведены зависимости скорости работы алгоритма при различных размерностях матрицы.

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

SHAMANAEV P. A., KATIN D. A., DESYAEV E. V.

IMPLEMENTATION OF AN ALGORITHM FOR FINDING THE RESOLVENT OF A MATRIX USING THE ADJECT MATRIX AND CHARACTERISTIC POLYNOMIAL

Abstract. The article describes the implementation of an algorithm for calculating the resolvent of a matrix using the adjoint matrix and the characteristic polynomial of the matrix in Python. The graphs show the speed of the algorithm for various matrix dimensions.

Keywords: matrix resolvent, adjoint matrix, characteristic polynomial, greatest common divisor, Python.

Введение. При решении многих задач требуется вычислять резольвенту матрицы [1], не зная ее собственных значений. В частности, такая задача возникает при решении систем линейных алгебраических уравнений с малым параметром методом Ляпунова-Шмидта [2; 3].

В работе [1] приведен подход вычисления резольвенты матрицы с использованием присоединенной матрицы и характеристического многочлена матрицы. Для вычисления последних Д. К. Фаддеевым предложен метод одновременного вычисления коэффициентов характеристического многочлена и присоединенной матрицы [1].

Изложим алгоритм вычисления резольвенты матрицы на основе подхода, изложенного в [1] и метода Д. К. Фаддеева одновременного вычисления коэффициентов характеристического многочлена и присоединенной матрицы.

Алгоритм вычисления резольвенты матрицы. Для вычисления резольвенты постоянной (т X т) —матрицы А

R (X) = [АЕ — А]-1

воспользуемся формулой [1, с. 112]

*

где С(Л) - приведенная присоединенная матрица для матрицы [ЛЕ — А] (см. [1, с. 99]); Хтт(^) - минимальный характеристический многочлен матрицы А.

Приведенную присоединенную матрицу С (Л) и минимальный характеристический многочлен матрицы А будем вычислять по формулам [1, с. 99-100]

ад = ^ вАю

_ ДШ

Хт1п

где ВА(Л) - присоединенная матрица для матрицы А [1, с. 92], й(Л) - наибольший общий делитель всех элементов матрицы ВА(Л),

А(Х) = Лп — р^-1 — р2Лп-2-----рп-1Л — рп,

- характеристический многочлен матрицы А.

Для нахождения присоединенной матрицы ВА(Л) воспользуемся формулой [1, с. 94]

ВА(Л) = В0Лп-1 + В1Лп-2 + В2Лп-3 + • + Вп-1,

где В0 - единичная (т х т) —матрица, а (т х т) —матрицы Вк ,к = 1, ...,п — 1, находятся методом Д. К. Фаддеева по формулам [1, с. 97]

Ак=А Вк-1, 1

Рк= £ 5р(Ак),

Вк=Ак — ркЕ, к = 1, ...,т. Здесь Е0 - единичная (т х т) —матрица.

Программная реализация алгоритм вычисления резольвенты матрицы.

Приведем фрагменты алгоритма вычисления резольвенты матрицы А на языке Python с использованием пакета SymPy.

Фрагмент кода инициализации матрицы А с целыми случайными элементами а^, i,j = = 1, ...,т из отрезка [—10,10]:

max_aij = 10

A = np.random.randint

Фрагмент кода реализации метода Д. К. Фаддеева одновременного вычисления характеристического многочлена Д(А) и присоединенной матрицы ВА(Х):

def fadeev_method(A): m = len(A) E = sympy.eye(m) B = [0 for i in range(m + 1)] B[0] = sympy.eye(m) tmpA = [0 for i in range(m + 1)] p = [0 for i in range(m + 1)] for k in range(1, m + 1): tmpA[k] = A * B[k - 1] p[k] = 1 / k * matrix_trace(tmpA[k]) B[k] = tmpA[k] - p[k] * E deltaLambda = lyamda ** m for i in range(1, m + 1):

deltaLambda -= p[i] * lyamda ** (m - i) B_A = sympy.zeros(m) for k in range(m):

B_A += B[k] * lyamda ** (m - 1 - k) return B_A, deltaLambda

Фрагмент кода вычисления наибольшего общего делителя всех элементов присоединенной матрицы BA (X):

d = B_A[0, 0] for i in range(m):

for j in range(m):

d = sympy.gcd

Фрагмент кода вычисления приведенной присоединенной матрицы С(Х), минимального характеристического многочлена Хтт (^) и резольвенты И (Л) матрицы А:

C = 1 / d * B_A

x_min = deltaLambda.as_expr() / d R = 1 / x min * C

Вычислительный эксперимент. Вычисления проводились на ноутбуке с процессором 11th Gen Intel(R) Core(TM) i7-11800H @ 2.30GHz и операционной системой Windows 11 Pro.

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

a)

b)

Рисунок. Графики зависимостей скорости работы алгоритма от размерности матрицы А при условиях: а) \щ]\ < 10, Ь) < 105, с) \ац\ < 106, Я) \ац\ < 107,1,] = 1, ...,т

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

Для сравнительного анализа использовалась функция пакета Бушру нахождения обратной матрицы, зависящей от параметра. Вычисления показали, что при т = 30 и \Щ]\ < 10 эта функция уже затрачивает порядка 10 мин., что значительно превышает скорость работы разработанного алгоритма вычисления резольвенты матрицы с использованием приведенной присоединенной матрицы и минимального характеристического многочлена.

СПИСОК ЛИТЕРАТУРЫ

1. Гантмахер Ф. Р. Теория матриц. - М.: Наука, 1966. - 576 с.

2. Вайнберг М. М., Треногин В. А. Теория ветвления решений нелинейных уравнений. - М.: Наука, 1964. - 524 с.

3. Шаманаев П. А., Прохоров С. А. Алгоритм решения систем линейных алгебраических уравнений с малым параметром методом Ляпунова-Шмидта в регулярном случае [Электронный ресурс] // Математическое моделирование, численные методы и комплексы программ имени Е. В. Воскресенского: IX Международная научная молодежная школа-семинар (Саранск, 8-11 октября 2020 г.). - С. 129-131. - Режим доступа: https://conf.svmo.ru/files/2020/papers/paper40.pdf (дата обращения: 23.11.2023).