Программирование, 2023, № 1, стр. 38-47
ВЫЧИСЛЕНИЕ УНИМОДУЛЯРНЫХ МАТРИЦ СТЕПЕННЫХ ПРЕОБРАЗОВАНИЙ
А. Д. Брюно a, *, А. А. Азимов b, **
a Институт прикладной математики им. М.В. Келдыша РАН
125047 Москва, Миусская пл., д. 4, Россия
b Самаркандский государственный университет
140104 Самарканд, Университетский бульвар, д. 15, Узбекистан
* E-mail: abruno@keldysh.ru
** E-mail: Azimov_Alijon_Akhmadovich@mail.ru
Поступила в редакцию 01.08.2022
После доработки 13.08.2022
Принята к публикации 07.09.2022
- EDN: GRRDJF
- DOI: 10.31857/S013234742301003X
Аннотация
Здесь указан алгоритм решения следующей задачи. Пусть в n-мерном вещественном пространстве задано $m < n$ целочисленных векторов. Их линейная оболочка образует линейное подпространство L в ${{\mathbb{R}}^{n}}$. Требуется вычислить такую унимодулярную матрицу, что линейное преобразование с ней переводит подпространство L в координатное. Также приведены программы, реализующие эти алгоритмы, и степенные преобразования, для которых они предназначены.
1. ВВЕДЕНИЕ
Напомним, что матрица называется унимодулярной, если она квадратная, все ее элементы – целые числа и ее определитель равен ±1. Ее обратная матрица также унимодулярна.
Будем векторы обозначать как векторы-строки: $X = ({{x}_{1}}, \ldots ,{{x}_{n}})$. $\left[ x \right]$ – это целая часть вещественного числа x.
Задача 1. Пусть в n-мерном вещественном пространстве ${{\mathbb{R}}^{n}}$ задано m, $(m < n)$ целочисленных векторов ${{A}_{1}}, \ldots ,{{A}_{m}}$. Их линейная оболочка
(1.1)
$L = \left\{ {X = \sum\limits_{j = 1}^m {{\lambda }_{j}}{{A}_{j}},{{\lambda }_{j}} \in \mathbb{R},j = 1, \ldots ,m} \right\}$Здесь указан алгоритм решения этой задачи, и составлена программа его реализующая. Это некоторое обобщение алгоритма цепной дроби [1], который напоминается в разделе 2. В разделе 3 описан алгоритм Эйлера [2], который обобщает алгоритм Евклида (т.е. цепной дроби) на n-мерный целочисленный вектор. В разделе 4 дается решение задачи 1, а в разделах 5, 6 – программы, соответствующие разделам 2, 3, 4. В разделе 7 рассмотрены степенные преобразования. Для вычисления их унимодулярных матриц развиты все эти алгоритмы и программы.
2. АЛГОРИТМ ЕВКЛИДА И ЦЕПНАЯ ДРОБЬ
Задача 2. Пусть заданы 2 целых положительных числа a1 и a2. Надо найти их наибольший общий делитель (НОД).
Для этого используется алгоритм Евклида. Пусть ${{a}_{1}} \geqslant {{a}_{2}}$; делим a1 на a2 с остатком:
где ${{b}_{1}} = [{{a}_{1}}{\text{/}}{{a}_{2}}]$ и ${{a}_{3}}$ – целые числа, $0 \leqslant {{a}_{3}} < {{a}_{2}}$. Если ${{a}_{3}} = 0$, то НОД равен ${{a}_{2}}$. Если ${{a}_{3}} \ne 0\;$, то делим с остатком ${{a}_{2}}$ на ${{a}_{3}}$: где ${{b}_{2}} = [{{a}_{2}}{\text{/}}{{a}_{3}}]$ и где $0 \leqslant {{a}_{4}} < {{a}_{3}}$. Если ${{a}_{4}} = 0$, то НОД равен a3. Если ${{a}_{4}} \ne 0$, то продолжаем процедуру, пока не получим нулевой остаток ${{a}_{{k + 1}}} = 0$.Тогда НОД – это ak. Эту процедуру можно записать в виде цепной дроби
(2.3)
$\frac{{{{a}_{1}}}}{{{{a}_{2}}}} = {{b}_{1}} + \frac{1}{{{{b}_{2}} + \frac{1}{{{{b}_{3}} + \frac{1}{{ \ldots + \frac{1}{{{{b}_{{k - 1}}}}}}}}}}}.$Она применима к любому вещественному числу β и дает, вообще говоря, бесконечное разложение. Только для рациональных чисел $\beta = {{a}_{1}}{\text{/}}{{a}_{2}}$ оно конечно. Для квадратичных иррациональностей β оно периодично [1]. Если в цепной дроби (2.3) отбросить окончание, начинающееся с ${{b}_{{l + 1}}}$, и свернуть полученную цепную дробь в рациональное число, то оно называется подходящей дробью.
Задача 3. Пусть заданы 2 целых положительных числа a1 и a2. Надо вычислить такую унимодулярную матрицу α, что $\left( {{{a}_{1}},{{a}_{2}}} \right)\alpha = ({{a}_{k}},0)$ или (0, ak), где целое число ${{a}_{k}} > 0$.
Деление с остатком (2.1) можно записать в виде умножения на матрицу $\left( {{{a}_{1}},{{a}_{2}}} \right)\left( {\begin{array}{*{20}{c}} 1&0 \\ { - {{b}_{1}}}&1 \end{array}} \right) = ({{a}_{3}},{{a}_{2}})$ или $\left( {{{a}_{1}},{{a}_{2}}} \right){{\beta }_{1}} = \left( {{{a}_{3}},{{a}_{2}}} \right)$, где ${{\beta }_{1}} = \left( {\begin{array}{*{20}{c}} 1&0 \\ { - {{b}_{1}}}&1 \end{array}} \right)$, а деление с остатком (2.2) есть $\left( {{{a}_{3}},{{a}_{2}}} \right)\left( {\begin{array}{*{20}{c}} 1&{ - {{b}_{2}}} \\ 0&1 \end{array}} \right) = ({{a}_{3}},{{a}_{4}})$ или $\left( {{{a}_{3}},{{a}_{2}}} \right){{\beta }_{2}} = \left( {{{a}_{3}},{{a}_{4}}} \right)$, где ${{\beta }_{2}} = \left( {\begin{array}{*{20}{c}} 1&{ - {{b}_{2}}} \\ 0&1 \end{array}} \right)$. Последний шаг алгоритма Евклида есть либо
Поэтому искомая матрица
где(2.4)
${{\beta }_{j}} = \left( {\begin{array}{*{20}{c}} 1&0 \\ { - {{b}_{j}}}&1 \end{array}} \right),$(2.5)
${{\beta }_{j}} = \left( {\begin{array}{*{20}{c}} 1&{ - {{b}_{j}}} \\ 0&1 \end{array}} \right),$Поскольку все матрицы ${{\beta }_{j}}$ унимодулярны, то их произведение α также унимодулярная матрица. Она дает решение задачи 3.
Отметим, что
Пример 1. Пусть ${{a}_{1}}$ = 17, ${{a}_{2}}$ = 5. Тогда ${{b}_{1}} = [17{\text{/}}5]$ = 3, ${{a}_{3}} = 2$, ${{\alpha }_{1}} = \left( {\begin{array}{*{20}{c}} 1&0 \\ { - 3}&1 \end{array}} \right)$,
Матрица $\alpha = {{\alpha }_{1}}{{\alpha }_{2}}{{\alpha }_{3}}$ = $\left( {\begin{array}{*{20}{c}} 1&0 \\ { - 3}&1 \end{array}} \right)\left( {\begin{array}{*{20}{c}} 1&{ - 2} \\ 0&1 \end{array}} \right)\left( {\begin{array}{*{20}{c}} 1&0 \\ { - 2}&1 \end{array}} \right)$ = = $\left( {\begin{array}{*{20}{c}} 5&{ - 2} \\ { - 17}&7 \end{array}} \right)$.
Раскладывая в цепную дробь
получим, что последняя подходящая дробь – это $3 + 1{\text{/}}2 = 7{\text{/}}2$. Поэтому в матрице α второй столбец состоит из –2, 7.Здесь было предложено решение задачи 3 для ${{a}_{1}}$, ${{a}_{2}} > 0$. Если ${{a}_{1}}$, ${{a}_{2}} < 0$, то надо взять матрицу α для вектора $\left( { - {{a}_{1}}, - {{a}_{2}}} \right).$ Если ${{a}_{1}} \cdot {{a}_{2}} < 0$, то надо взять матрицу $\alpha = \left( {\begin{array}{*{20}{c}} {{{\alpha }_{{11}}}}&{{{\alpha }_{{12}}}} \\ {{{\alpha }_{{21}}}}&{{{\alpha }_{{22}}}} \end{array}} \right)$ для вектора $\left( {\left| {{{a}_{1}}} \right|,\left| {{{a}_{2}}} \right|} \right)$. Тогда матрица
Здесь предполагалось, что $\left| {{{a}_{1}}} \right| \geqslant \left| {{{a}_{2}}} \right|$. Если это не так, то надо предварительно сделать перестановку координат
Похожее изложение см. в п. 1.9, § 1, гл. І [3].
3. АЛГОРИТМ ЭЙЛЕРА И ОБОБЩЕНИЕ ЦЕПНОЙ ДРОБИ
Задача 4. Пусть задан n-мерный целочисленный вектор $A = ({{a}_{1}},{{a}_{2}}, \ldots ,{{a}_{n}})$. Надо найти такую n‑мерную унимодулярную матрицу $\alpha $, что вектор Aα = C = $({{c}_{1}}, \ldots ,{{c}_{n}})$ содержит только одну координату ${{c}_{n}}$, отличную от нуля.
Для ее решения Эйлер [2] предложил следующий алгоритм. Пусть для начала все координаты вектора A неотрицательны. С помощью перестановки $A{{\alpha }_{0}} = \left( {{{{\tilde {a}}}_{1}},{{{\tilde {a}}}_{2}}, \ldots ,{{{\tilde {a}}}_{n}}} \right)$ упорядочим координаты
Здесь ${{\alpha }_{0}}$ – унимодулярная матрица перестановки. Пусть ${{\tilde {a}}_{k}}$ – наименьшее из чисел ${{\tilde {a}}_{j}}$, отличное от нуля.
Пусть
При этом ${{b}_{1}} = \cdots = {{b}_{{k - 1}}} = 0$, ${{b}_{k}} = 1$. Делаем преобразование
(3.1)
${{d}_{j}} = {{\tilde {a}}_{j}} - {{b}_{j}}{{\tilde {a}}_{k}},\quad 1 \leqslant j \leqslant n,\quad j \ne k,\quad {{d}_{k}} = {{\tilde {a}}_{k}}.$Ему соответствует унимодулярная матрица ${{\alpha }_{1}}$, у которой на диагонали стоят единицы, в k-й строке стоят
т.е.Теперь упорядочиваем компоненты вектора D с помощью унимодулярной матрицы-перестановки ${{\beta }_{0}}$ так, что $D{{\beta }_{0}} = \tilde {D}$ = $(0, \ldots ,0,{{\widetilde d}_{k}}, \ldots ,{{\widetilde d}_{n}})$, где ${{\widetilde d}_{j}} \leqslant {{\widetilde d}_{{j + 1}}}$.
Пусть ${{\widetilde d}_{l}}$ – наименьшее из ${{\widetilde d}_{j}}$, отличное от нуля, и ${{e}_{j}} = [{{\widetilde d}_{j}}{\text{/}}{{\widetilde d}_{l}}]$, $\;j = 1, \ldots ,l$. Делаем преобразование
Матрица
(3.2)
$\alpha = {{\alpha }_{0}}{{\alpha }_{1}}{{\beta }_{0}}{{\beta }_{1}}{{\gamma }_{0}}{{\gamma }_{1}} \cdots {{\omega }_{0}}{{\omega }_{1}}$Если не все координаты aj исходного вектора A одного знака, то сначала упорядочиваем их по модулю
и полагаемЗамечание 1. Умножая справа матрицу α на унимодулярную матрицу-перестановку, можно из вектора C получить вектор, у которого все координаты кроме одной равны нулю, а единственная ненулевая координата расположена на любом месте.
Пример 2. Пусть n = 4 и $A = \left( {5,2,4,3} \right)$. Упорядочиваем координаты вектора A: A · $\left( {\begin{array}{*{20}{c}} 0&0&0&1 \\ 1&0&0&0 \\ 0&0&1&0 \\ 0&1&0&0 \end{array}} \right) = \tilde {A}$ = = (2, 3, 4, 5), где $\left( {\begin{array}{*{20}{c}} 0&0&0&1 \\ 1&0&0&0 \\ 0&0&1&0 \\ 0&1&0&0 \end{array}} \right) = {{\alpha }_{0}}$, имеем k = 1. Получаем
Поэтому
Упорядочиваем координаты вектора D:
$D\left( {\begin{array}{*{20}{c}} 0&0&0&1 \\ 0&1&0&0 \\ 1&0&0&0 \\ 0&0&1&0 \end{array}} \right)\, = \,\left( {0,1,1,2} \right)\, = \,\tilde {D}$, где $\left( {\begin{array}{*{20}{c}} 0&0&0&1 \\ 0&1&0&0 \\ 1&0&0&0 \\ 0&0&1&0 \end{array}} \right)$ = β0. Здесь l = 2. Получаем ${{e}_{1}} = 0$, ${{e}_{2}} = 1$, ${{e}_{3}} = 1$, ${{e}_{4}} = 2$ и ${{\beta }_{1}} = \left( {\begin{array}{*{20}{c}} 1&0&0&0 \\ 0&1&{ - 1}&{ - 2} \\ 0&0&1&0 \\ 0&0&0&1 \end{array}} \right)$.
$\tilde {D}{{\beta }_{1}} = \left( {0,1,0,0} \right)$. Наконец, ${{\gamma }_{0}} = \left( {\begin{array}{*{20}{c}} 1&0&0&0 \\ 0&0&0&1 \\ 0&1&0&0 \\ 0&0&1&0 \end{array}} \right)$ и $\tilde {D}{{\beta }_{1}}{{\gamma }_{0}} = \left( {0,0,0,1} \right)$ = C.
Здесь
(3.3)
$\alpha = {{\alpha }_{0}}{{\alpha }_{1}}{{\beta }_{0}}{{\beta }_{1}}{{\gamma }_{0}} = \left( {\begin{array}{*{20}{c}} 0&1&0&0 \\ { - 2}&{ - 1}&3&{ - 1} \\ 1&0&0&0 \\ 0&{ - 1}&{ - 2}&1 \end{array}} \right).$Пусть заданный вектор A является нормалью к некоторому линейному многообразию. Тогда после преобразования с помощью матрицы α получим, что этот вектор содержит первые n – 1 нулевые координаты. Следовательно, все векторы исходного многообразия после преобразования будут иметь последней координатой ноль.
Алгоритм Эйлера обобщает алгоритм цепной дроби только для целочисленных векторов. Для произвольных вещественных векторов это обобщение искали все крупные математики XIX века. Но безуспешно. В [4] предложено такое обобщение цепной дроби для n-мерного вектора, которое дает последовательность наилучших приближений и периодично, если все координаты исходного вектора являются корнями многочлена степени n с целыми коэффициентами.
4. РЕШЕНИЕ ЗАДАЧИ 1
Пусть заданы целочисленные векторы
(4.1)
$\begin{array}{*{20}{l}} {{{A}_{1}}}&{ = \left( {{{a}_{{11}}},{{a}_{{12}}}, \ldots ,{{a}_{{1n}}}} \right),} \\ {{{A}_{2}}}&{ = \left( {{{a}_{{21}}},{{a}_{{22}}}, \ldots ,{{a}_{{2n}}}} \right),} \\ {}&{...} \\ {{{A}_{m}}}&{ = \left( {{{a}_{{m1}}},{{a}_{{m2}}}, \ldots ,{{a}_{{mn}}}} \right)} \end{array}$Первым делом проверяем, что среди них нет одинаковых. Если есть, то оставляем из них только один, а остальные отбрасываем. Поэтому будем считать, что все векторы (4.1) разные. Теперь применяем алгоритм Эйлера к вектору ${{A}_{1}}$, т.е. вычисляем матрицу ${{\alpha }_{0}}$, такую, что ${{A}_{1}}{{\alpha }_{0}} = {{C}_{1}} = {{c}_{n}}{{E}_{n}}$, где cn – целое число и ${{E}_{k}}$ – это k-й единичный вектор.
Пусть ${{A}_{j}}{{\alpha }_{0}} = {{C}_{j}} = ({{c}_{{j1}}}, \ldots ,{{c}_{{jn}}})$, $j = 2, \ldots ,m$. Полагаем $A_{j}^{1} = ({{c}_{{j1}}}, \ldots ,{{c}_{{jn - 1}}})$, $j = 2, \ldots ,m$. Применяем алгоритм Эйлера к (n – 1)-мерному вектору $A_{2}^{1}$. Получаем $A_{2}^{1}{{\alpha }_{1}} = C_{2}^{1} = (0,0, \ldots ,c_{{n - 1}}^{1})$, где ${{\alpha }_{1}}$ – это (n – 1)-мерная квадратная матрица. Пусть $A_{j}^{1}{{\alpha }_{1}}$ = = $C_{j}^{1} = (c_{{j1}}^{1}, \ldots ,c_{{jn - 1}}^{1})$, $j = 3, \ldots ,m$. Применяем алгоритм Эйлера к (n – 2)-мерному вектору $C_{3}^{1}$ и т. д. В итоге получаем последовательность матриц ${{\alpha }_{0}},{{\alpha }_{1}}, \ldots ,{{\alpha }_{{m - 1}}}$ убывающих размерностей n, n – 1, ..., $n - m + 1$. Образуем блочные квадратные матрицы ${{\beta }_{j}} = \left( {\begin{array}{*{20}{c}} {{{\alpha }_{j}}}&0 \\ 0&{{{I}_{{j + 1}}}} \end{array}} \right)$, $j = 0, \ldots ,n - m$, размерности n, где ${{I}_{{j + 1}}}$ – это единичные матрицы размерности j + 1. Положим
Тогда ${{A}_{j}}\gamma = (0,0, \ldots ,0,{{w}_{{j,n - j + 1}}}, \ldots ,{{w}_{{j,n}}}) = {{W}_{j}}$, j = = $1, \ldots ,m$. Матрица γ дает решение задачи 1.
Замечание 2. Умножая справа матрицу γ на матрицу-перестановку $\left( {\begin{array}{*{20}{c}} 0&{}&1 \\ {}& {\mathinner{\mkern2mu\raise1pt\hbox{.}\mkern2mu \raise4pt\hbox{.}\mkern2mu\raise7pt\hbox{.}\mkern1mu}} &{} \\ 1&{}&0 \end{array}} \right)$, можно из набора векторов ${{W}_{1}}, \ldots ,{{W}_{m}}$ получить треугольную матрицу $U\, = \,({{u}_{{jk}}})$, $j = 1, \ldots ,m$, $k = 1, \ldots ,n$, у которой ${{u}_{{jk}}}$ = 0, если $k > j$.
Пример 3 (продолжение примера 2). Пусть $n = 4$, $m = 2$, заданы векторы ${{A}_{1}} = \left( {5,2,4,3} \right)$, A2 = = $(7,8,9,3)$. Согласно примеру 2 матрица $\alpha $ из (3.3) приводит вектор ${{A}_{1}}$ к виду (0, 0, 0, 1). Имеем
Имеем
Получаем
Упорядочиваем координаты по модулю
Имеем
Получаем
Упорядочиваем
Имеем
получаемУпорядочиваем
Теперь
(4.2)
$\begin{gathered} {{\alpha }_{1}} = \left( {\begin{array}{*{20}{c}} 0&1&0 \\ 1&0&0 \\ 0&0&1 \end{array}} \right) \cdot \left( {\begin{array}{*{20}{c}} 1&{ - 1}&4 \\ 0&1&0 \\ 0&0&1 \end{array}} \right) \cdot \left( {\begin{array}{*{20}{c}} 0&0&1 \\ 0&1&0 \\ 1&0&0 \end{array}} \right)\left( {\begin{array}{*{20}{c}} 1&1&2 \\ 0&1&0 \\ 0&0&1 \end{array}} \right) \times \\ \, \times \left( {\begin{array}{*{20}{c}} 0&0&1 \\ 0&1&0 \\ 1&0&0 \end{array}} \right) \cdot \left( {\begin{array}{*{20}{c}} 1&0&0 \\ 0&1&2 \\ 0&0&1 \end{array}} \right) \cdot \left( {\begin{array}{*{20}{c}} 1&0&0 \\ 0&0&1 \\ 0&1&0 \end{array}} \right) = \left( {\begin{array}{*{20}{c}} 0&2&1 \\ 9&{10}&3 \\ 2&3&1 \end{array}} \right). \\ \end{gathered} $Полагаем
Теперь
Проверяем ${{A}_{1}}\gamma = (0,0,0,1)$, ${{A}_{2}}\gamma = (0,0, - 1, - 5)$. Итак,
5. ПРОГРАММЫ ВЫЧИСЛЕНИЯ ЦЕПНОЙ ДРОБИ
Алгоритмы вычисления цепных дробей реализованы в различных системах. Здесь опишем основные процедуры в двух системах компьютерной алгебры (СКА): в проприетарной Maple и в открытой sympy. Пакет NumberTheory в СКА Maple [5] позволяет получать разложение в цепную дробь рациональных, алгебраических и трансцендентных чисел, а также полиномов или элементарных функций от одной переменной. В пакете sympy [7] такой функционал реализован только для рациональных чисел или квадратичных иррациональностей. Если требуется работа с цепными дробями для других иррациональностей или трансцендентных чисел, то следует использовать открытую СКА Sage [6].
Для работы с рациональным числом в виде цепной дроби достаточно трех основных процедур: [1)]
1) преобразование в цепную дробь;
2) получение элементов цепной дроби;
3) получение рациональных приближений.
В СКА Maple соответствующие действия обеспечивают процедуры ContinuedFraction, Term и Convergent, а в sympy функционал пунктов 1 и 2 обеспечивает процедура continued_fraction, а пункта 3 – процедура continued_fraction_convergents.
Ниже приведем примеры реализации вычисления унимодулярных 2 × 2 матриц в соответствии с алгоритмами п. 1.9 книги [3]. Эти алгоритмы используют цепные дроби.
Первый алгоритм (см. [3], стр. 28–30) использует слагаемые разложения рационального числа p/q, а итоговая унимодулярная матрица получается путем последовательного умножения верхне- или нижнетреугольных матриц, которые составляются на основе элементов разложения цепной дроби. Его реализация для Maple и для sympy приведена на листингах 1 и 2 соответственно.
Листинг 1
UniMod1:=proc (p:: integer, q:: integer) |
description “Compute unimodular 2 × 2- |
matrix with the help of continued |
fraction"; |
uses NumberTheory, LinearAlgebra, |
ListTools; |
local pabs:=abs (p), qabs:=abs (q), gcdpq |
:=igcd (pabs, qabs), cf_terms, |
k,M, alpha:=DiagonalMatrix ([1, 1 ]); |
if gcdpq!=1 then pabs:=pabs/gcdpq; |
qabs:=qabs/gcdpq; end if; |
cf_terms:= Term(ContinuedFraction ( |
pabs/qabs), all); |
for k in [seq] ([i, cf_terms [i]], i =1.. |
numelems (cf_terms)) do |
M:=DiagonalMatrix ([1, 1 ]); |
if type (k [1], even) then M [2, 1 ]:= -k |
[-1] else M [1, 2]:= -k[-1] end if; |
alpha:=M. alpha; |
end do; |
return Matrix ([sign (p) *Column(alpha |
, 1), sign (q) *Column(alpha, 2)]); |
[-1] else M [1, 2]:= =k[=1] end if; |
alpha:=M. alpha; |
end proc; |
Листинг 2
import sympy as sym |
from sympy import Rational, eye, Matrix |
from sympy.ntheory.continued_fraction\ |
import continued_fraction_convergents,\ |
continued_fraction_iterator,\ |
continued_fraction |
def UniMod1(p, q): |
""" |
Construct 2 × 2 unimodular matrix |
for fraction p/q. |
First variant |
""" |
r - Rational (p, q) |
cfr - continued_fraction (r) |
Mlst - [eye (2.1) for k in range (len (cfr))] |
for k, m in enumerate(cfr): |
if k%2=-1: Mlst [k] [1,0]=-m |
else: Mlst [k] [0,1]= -m |
alpha = eye (2.1) |
for M in Mlst [:: -1]: alpha*-M |
return alpha |
Пример работы процедуры UniMod1 для пары чисел 5, 17 примера 1 приведен на листинге 3.
Листинг 3
>r := [5, 17]: UniMod2(op(r1)); %.Vector (r1); |
$\left[ {\begin{array}{*{20}{c}} 7&{ - 2} \\ { - 17}&5 \end{array}} \right]$ |
$\left[ \begin{gathered} 1 \\ 0 \\ \end{gathered} \right]$ |
Второй алгоритм (см. [3], стр. 30–31) использует только само рациональное число p/q и его последнюю подходящую дробь ${{p}_{{n - 1}}}{\text{/}}{{q}_{{n - 1}}}$. Его реализация приведена на листингах 4 и 5 соответственно.
Листинг 4
UniMod2:=proc (p:: integer, q:: integer) |
description “Compute unimodular 2 × 2= |
matrix with the help of continued |
fraction. Second variant"; uses |
NumberTheory; |
local pabs:=abs (p), qabs:=abs (q), gcdpq |
:=igcd (pabs, qabs), cf, cf_conv, |
gamma, rho, Sigma, alpha; |
if gcdpq!=1 then pabs:=pabs/gcdpq; |
qabs:=qabs /gcdpq; end if; |
cf:= ContinuedFraction (pabs/qabs); |
cf_conv:=Convergent (cf, all); |
gamma:=cf_conv [=1]; |
rho:=cf_conv [=2]; |
Sigma:=numer (gamma=rho); |
alpha:=Matrix ([[s i gn (p) *Sigma*denom( |
rho),=sign (q) *Sigma*numer (rho)], |
[-sign (p) *denom(gamma), sign (q) *numer ( |
gamma)]]); |
return alpha; |
end proc; |
Листинг 5
import sympy as sym |
from sympy import Rational, eye, Matrix |
from sympy.ntheory.continued_fraction\ |
import continued_fraction_convergents,\ |
continued_fraction_iterator,\ |
continued_fraction |
def UniMod2(p, q): |
""" |
Construct 2 × 2 unimodular matrix |
for fraction p/q. |
Second variant |
""" |
r = Rational (p, q) |
cfr = continued_fraction (r) |
cfr_conv = \ |
list (continued_fraction_convergents (cfr)) |
gamma = cfr1_conv [=1] |
rho = cfr1_conv [=2] |
sigma=(gamma=rho). numerator |
alpha = Matrix ([[sigma* rho. denominator, \ |
=sigma * rho.numerator], \ |
[=gamma.denominator, gamma. numerator]]) |
return alpha |
6. РЕАЛИЗАЦИЯ АЛГОРИТМА ЭЙЛЕРА И РЕШЕНИЯ ЗАДАЧИ 1
Для имплементации алгоритма Эйлера, описанного в разделе 3, был реализован набор процедур в СКА Maple, листинги которых представлены ниже вместе с кратким их описанием. Отметим, что целочисленный вектор в СКА Maple может быть представлен в двух различных формах: в виде списка (перечня чисел в квадратных скобках) или в виде вектора-строки (вектора-столбца) пакета LinearAlgebra (Vector[row] или Vector[column] соответственно). Если имя процедуры содержит цифру 2, то это означает, что входной целочисленный вектор может быть задан в одном из двух указанных видов.
Процедура MakePermute2 представлена на листинге 6. Она строит перестановочную матрицу по заданному вектору $A$. Результат работы процедуры – упорядоченный вектор и перестановочная матрица ${{\alpha }_{0}}$. Порядок сортировки элементов вектора задается параметром sorting, но по умолчанию элементы упорядочиваются по возрастанию. В начале работы процедура проверяет, что вектор $A$ не является нульмерным (строка 4 листинга 6).
Листинг 6
1 | MakePermute2:= proc (A:: {Vector, list |
}, sorting:=‘<‘) | |
uses LinearAlgebra; | |
local Asort, Aind, Aper, i, nA:= | |
numelems (A); | |
if nA=0 then error (“Zero dimensional | |
vector!"); end if; | |
Aind:= sort (abs~(A), sorting, output | |
= [permutat ion]); | |
6 | Asort:= A[Aind]; |
Aper:= Matrix (nA, nA, fill = 0); | |
for i to numelems (Aind) do | |
Aper [i, Aind [i]]:= 1; | |
end do; | |
11 | if type (A, Vector [row]) then |
return Asort, Transpose (Aper); | |
else | |
return Asort, Aper; | |
end if; | |
16 | end proc; |
Вторая процедура MakeUnimod2 (листинг 7) для упорядоченного по возрастанию вектора A строит унимодулярную матрицу α1, реализующую один шаг (3.1) алгоритма Эйлера.
Листинг 7
1 | MakeUnimod2:= proc (As:: {Vector, list |
}) | |
uses ListTools, LinearAlgebra; | |
local M, i, Amin, nminpos, ncol, absAs | |
:=abs~(As),nA; | |
4 | nA:=numelems (As); |
if nA=0 then error (“Zero dimensional | |
vector!"); end if; | |
M:= DiagonalMatrix ([seq] (1, k = 1.. | |
nA)); | |
Amin, nminpos:= FindMinimalElement ( | |
convert (absAs, list), position); | |
Amin:= As [nminpos]; | |
9 | if Amin = 0 then |
ncol:= [Sear chAl l] (0, convert (absAs, | |
list)) [=1] + 1; | |
else | |
ncol:= nminpos; | |
end if; | |
14 | for i from ncol+1 to nA do |
M[i, ncol]:= =t runc (As [i] /As [ncol]); | |
end do; | |
if type (As, Vector [row]) then | |
return LinearAlgebra:=Transpose (M); | |
19 | else |
return M; | |
end if; | |
end proc; |
Рекурсивная процедура Unimodr2 (листинг 8) вычисляет по исходному вектору A унимодулярную матрицу α, которая преобразует A в вектор C с единственной последней ненулевой координатой. При первом ее вызове второй параметр Uni не указывается. В этом случае он полагается равным единичной матрице (строка 7 листинга). При последующих вызовах в процедуру передается унимодулярная матрица, вычисленная на предыдущих вызовах. Для своей работы процедура Unimod2 использует описанные выше процедуры MakePermute2 и MakeUnimod2. Условие окончания рекурсии – это получение вектора, у которого все элементы, кроме одного, равны нулю (строка 16 листинга).
Листинг 8
1 | Unimodr2:= proc (A:: {Vector, list}, |
Uni:: Matrix) | |
uses LinearAlgebra, ListTools; | |
3 | local Alen, Avec, Alst, As, Aper, M, |
Mperm, Auni, res, _; | |
Alen:= numelems (A) | |
if Alen=0 then error (“Zero | |
dimensional vector!"); end if; | |
if nargs = 1 then | |
res:= DiagonalMatrix ([seq] (1, k = 1 | |
.. Alen)); | |
8 | else |
res:= Uni; | |
end if; | |
if type (A, list) then | |
Alst:=A; Avec:=convert (A, Vector [ | |
column]); | |
13 | elif type (A, Vector) then |
Alst:=convert (A, list); Avec:=convert (A | |
, Vector [column]); | |
end if; | |
if Occurrences (0, Alst) = Alen = 1 | |
then | |
_, Mperm:= MakePermute2 (A); | |
18 | if type (A, list) then |
return convert (Mperm. Vector (A), list), | |
Mperm. res; | |
elif type (A, Vector [row]) then | |
return A.Mperm, res.Mperm; | |
else | |
23 | return Mperm. Avec, Mperm. res; |
end if; | |
end if; | |
As, Aper:= MakePermute2 (A); | |
M:= MakeUnimod2 (As); | |
28 | if type (A, list) then |
Auni:= M. Aper; | |
return Unimodr2 (convert (Auni. (Vector ( | |
A)), list), Auni. res); | |
elif type (A, Vector [row]) then | |
Auni:= Aper.M; | |
33 | return Unimodr2 (A. Auni, res. Auni); |
el se | |
Auni:= M. Aper; | |
return Unimodr2 (Auni.A, Auni. res); | |
end if; | |
38 | end proc; |
Ниже приведен листинг 9 решения примера 2 для вектора $A = (5,2,4,3)$.
Листинг 9
Решение задачи 1 в соответствии с алгоритмом раздела 4 реализовано в рекурсивной процедуре UniSys, приведенной на листинге 10. Процедура получает исходный набор целочисленных векторов Aj, $j = 1, \ldots ,m$ в виде списка Vlst. Если исходный список пуст (строка 5), либо число векторов превышает их размерность (строка 8), либо векторы являются линейно зависимыми (строки 9–15), либо векторы из набора имеют разный тип (строки 16–24) или разную размерность (строки 25–28), то процедура UniSys завершает свою работу. Если список состоит из одного вектора, то вызывается процедура Unimodr2, вычисляется матрица α – и на этом работа процедуры окончена. В противном случае осуществляется повторный вызов процедуры UniSys для набора векторов $A_{j}^{1}$, $j = 2, \ldots ,m$, из которого исключен первый вектор, к оставшимся векторам применена унимодулярная матрица α. При этом размерность векторов $A_{j}^{1}$ уменьшена на единицу, а матрица α передается в виде параметра Uni для повторного вызова процедуры. При успешном окончании работы процедура UniSys возвращает итоговую матрицу $\gamma $, решающую задачу 1.
Листинг 10
1 | UniSys:=proc (Vlst:: list, Uni:: Matrix) |
uses LinearAlgebra; | |
local res, dlst,UM,_,Vdim, nVlst, Vtcol | |
:=t rue,Mtmp; | |
nVl st:=numelems (Vl s t); | |
5 | if nVl st=0 then error (“Initial list |
is empty!"); end if; | |
Vdim:=Dimension (Vlst [1]); | |
if type (Vlst [1], Vector [row]) then | |
Vtcol:= false; end if; | |
if nVlst>Vdim then error (“Too many | |
vector sofdimens ion “,Vdim); end | |
if; | |
if Vtcol then | |
10 | Mtmp:=Matrix (Vlst); |
if Rank(Mtmp)<nVl st then error (" | |
Vectors are not independent ! “); | |
end if; | |
else | |
Mtmp:=<op (Vlst)>; | |
if Rank(Mtmp)<nVl st then error (" | |
Vectors are not independent!"); | |
end if; | |
15 | end if; |
if Vtcol then | |
if not evalb (‘and‘ (op ([seq] (type (V, | |
Vector [column]),V in Vl s t)))) then | |
error (“All elements should be Vectors | |
“); | |
end if; | |
20 | else |
if not evalb (‘and‘ (op ([seq] (type (V, | |
Vector [row]),V in Vl s t)))) then | |
error (“All elements should be Vectors | |
“); | |
end if; | |
end if; | |
25 | dlst:=[seq] (Dimension (V),V in Vl st); |
if ListTools [Occur rences] (dlst [1], | |
dlst) <> nVlst then | |
error (“All vectors should be o f the | |
same size"); | |
end if; | |
if nargs = 1 then | |
30 | res:= DiagonalMatrix ([seq] (1, k = 1.. |
Vdim)); | |
else | |
res:= Uni; | |
end if; | |
_,UM:=Unimodr2 (Vlst [1]); | |
35 | if nVl st=1 then |
if Vtcol then return UM. res; else | |
return res.UM; end if; | |
end if; | |
if Vtcol then | |
return DiagonalMatrix ([UniSys2 ([seq] ( | |
SubVector (UM.V, [1.. Vdim=1]), V in | |
Vl s t [2.. =1])), 1]).UM; | |
40 | else |
return UM. DiagonalMatrix ([UniSys2 ([ | |
seq] (SubVector (V.UM, [1.. Vdim=1]), | |
V in Vlst [2.. =1])), 1]); | |
end if; | |
end proc; |
Ниже приведен листинг 11 решения примера 3 для векторов $A = (5,2,4,3)$ и $B = (7,8,9,3)$.
Листинг 11
>A:= [5, 2, 4, 3 ]: Arow:=Vector [row] (A): |
>B:= [7–9, 3 ]: Brow:=Vector [row] (B): |
>UniSys ([Arow,Brow]); |
$\left[ {\begin{array}{*{20}{c}} 0&0&0&1 \end{array}} \right],\left[ {\begin{array}{*{20}{c}} 9&{10}&3&0 \\ { - 3}&{ - 5}&{ - 2}&{ - 1} \\ 0&2&1&0 \\ { - 13}&{ - 16}&{ - 5}&1 \end{array}} \right]$ |
7. СТЕПЕННЫЕ ПРЕОБРАЗОВАНИЯ
Пусть задан многочлен
где $X = ({{x}_{1}}, \ldots ,{{x}_{n}}) \in {{\mathbb{R}}^{n}}$ или ${{\mathbb{C}}^{n}}$, $Q = ({{q}_{1}}, \ldots ,{{q}_{n}}) \in {{\mathbb{Z}}^{n}},$ $Q \geqslant 0,$ fQ – постоянные коэффициенты из $\mathbb{R}$ или $\mathbb{C}$, ${\mathbf{S}} = {\mathbf{S}}(f)$ – носитель многочлена f. Пусть $\mathcal{F}$ – алгебраическое многообразие $f(X) = 0$ и точка $X = {{X}^{0}} \in \mathcal{F}$.Если X0 – простая точка, т.е. хотя бы одна из производных $\partial f{\text{/}}\partial {{x}_{j}}$ в этой точке X0 отлична от нуля, то, по теореме о неявной функции, вблизи точки X0 многообразие $\mathcal{F}$ описывается уравнением
(7.2)
$\Delta {{x}_{j}} = \varphi (\Delta {{x}_{1}}, \ldots ,\Delta {{x}_{{j - 1}}},\Delta {{x}_{{j + 1}}}, \ldots ,\Delta {{x}_{n}}),$Если точка X0 – не простая, то согласно [8, 9] можно искать ветви многообразия $\mathcal{F}$, проходящие через точку X0, в виде параметрических разложений
(7.3)
$\Delta {{x}_{j}} = {{\varphi }_{j}}({{\xi }_{1}}, \ldots ,{{\xi }_{{n - 1}}}),\quad i = 1, \ldots ,n,$Кроме того, каждой грани $\Gamma _{j}^{{(d)}}$ соответствуют граничное множество
и укороченная суммаТеорема ([8, следствие § 3, гл. II] и теорема 3.1 [9]). Для грани $\Gamma _{j}^{{(d)}}$ существует степенное преобразование
где $\ln Y = (\ln {{y}_{1}}, \ldots ,\ln {{y}_{n}})$, $\ln X = (\ln {{x}_{1}}, \ldots ,\ln {{x}_{n}})$ с унимодулярной матрицей α, которое переводит укороченную сумму (7.4) в многочлен g от d координат, т.е.где $T = ({{t}_{1}}, \ldots ,{{t}_{n}}) \in {{\mathbb{Z}}^{n}}$.Но в [8, 9] не было указано, как вычислять унимодулярную матрицу $\alpha $. Это сделано в настоящей работе. А именно: если n = 2, то с помощью цепной дроби раздела 2, если $d = n - 1$, то с помощью алгоритма Эйлера, если n > 2 и $d < n - 1$, то с помощью алгоритма раздела 4, решающего задачу 1.
Список литературы
Хинчин А.Я. Цепные дроби. М.: Физматгиз, 1961.
Euler L. De relatione inter ternas pluresve quantitates instituenda // 1785, All Works 591.
Брюно А.Д. Локальный метод нелинейного анализа дифференциальных уравнений. М.: Наука, 1979. 252 с.
Брюно А.Д. Вычисление основных единиц числовых колец с помощью обобщенной цепной дроби // Программирование. 2019. № 2. С. 17–31. https://doi.org/10.1134/S0132347419020055
Thompson I. Understanding Maple. Cambridge University Press, 2016. 228 p.
The Sage Developers. SageMath, the Sage Mathematics Software System (Version 9.1.1). 2020. https://doi.org/10.5281/zenodo. 4066866. https://www.sagemath.org.
Meurer A., Smith C.P., [et al.]. SymPy: symbolic computing in Python // PeerJ Computer Science. 2017. V. 3. e103. ISSN 2376–5992. DOI: . URL: https://doi.org/10.7717/ peerj-cs.103.
Брюно А.Д. Степенная геометрия в алгебраических и дифференциальных уравнениях. М.: Физматлит, 1998. 288 с.
Брюно А.Д., Батхин А.Б. Разрешение алгебраической сингулярности алгоритмами степенной геометрии // Программирование. 2012. № 2. С. 11–28.
Дополнительные материалы отсутствуют.
Инструменты
Программирование