2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу Пред.  1, 2
 
 Re: Диофантово уравнение с N неизвестными
Сообщение21.08.2017, 16:01 


21/11/12
852
Санкт-Петербург
Ладно. Принцип ясен, на досуге разберусь.
Спасибо.

 Профиль  
                  
 
 Re: Диофантово уравнение с N неизвестными
Сообщение21.08.2017, 21:40 


21/11/12
852
Санкт-Петербург
Врубился. $n=2$ решается не хуже, должна быть удобная форма записи - что-то вроде $n$-кратных дробей. Оно и есть алгоритм Евклида для многочленов, чудо неизъяснимое. Интересно, кто это изобрел?

 Профиль  
                  
 
 Re: Диофантово уравнение с N неизвестными
Сообщение01.09.2017, 18:37 


21/11/12
852
Санкт-Петербург
Тут хочется еще порассуждать. Решая уравнение $6x_1+10x_2+15x_3=c\ (1)$ указанным способом, получаем

$x_1=\ c+5y_1-5y_2$
$x_2=\ c+0y_1-3y_2$
$x_3=-c-2y_1+4y_2$, где $y_1,y_2$ - пара свободных переменных.

Первые слагаемые многочленов от верхнего к нижнему образуют некоторое решение: $6\cdot c+10\cdot c+15\cdot -c=c$. Вторые и третьи слагаемые образуют пару непропорциональных решений уравнения $6x_1+10x_2+15x_3=0$. Запишем коэффициенты при переменных в квадратную матрицу: $$\begin{pmatrix}
1 & 5 & -5\\ 
1 & 0 & -3\\ 
-1 & -2 & 4
\end{pmatrix}$$
Элементы первого столбца, подставленные в уравнение $(1)$ возвращают единицу, остальных столбцов - ноль. В некотором смысле они "почти пропорциональны".
Пусть теперь дана матрица $\begin{pmatrix}
k_{11} & k_{12} & k_{13}\\ 
k_{21} & k_{22} & k_{23}\\ 
k_{31} & k_{32} & k_{33}
\end{pmatrix}$ , и нужно определить какому из возможных уравнений она соответствует (выражает решение). Из $\left\{\begin{matrix}
k_{12}a+k_{22}b+k_{32}c=0\\ 
k_{13}a+k_{23}b+k_{33}c=0
\end{matrix}\right.$ , перенося различные слагаемые в правую часть, получаем $\dfrac{a}{b}=\dfrac{k_{22}k_{33}-k_{23}k_{32}}{k_{12}k_{33}-k_{13}k_{32}},\ \dfrac{a}{c}=\dfrac{k_{22}k_{33}-k_{23}k_{32}}{k_{12}k_{23}-k_{13}k_{22}}$. Обозначим $k_{22}k_{33}-k_{23}k_{32}=m_1, k_{12}k_{33}-k_{13}k_{32}=m_2,k_{12}k_{23}-k_{13}k_{22}=m_3$. Тогда $\dfrac{a}{b}=\dfrac{m_1}{m_2},\dfrac{b}{c}=\dfrac{m_2}{m_3},\dfrac{c}{a}=\dfrac{m_3}{m_1}$. Тройка $ a,b,c$ по предположению взаимно проста, отсюда $a=\pm m_1,b=\pm m_2,c=\pm m_3$, и должно выполняться $k_{11}m_1+k_{21}m_2+k_{31}m_3=\pm 1$. В противном случае (а так же в случае $\gcd  (m_1,m_2,m_3)>1$) матрица не выражает никакого решения. То есть не любые три столбца "почти пропорциональны" даже в некотором смысле. Всё сказанное можно продолжить на квадратную матрицу со стороной $>3$. Иными словами, решение целочисленного уравнения первой степени с $k$ неизвестными выражается $k$ многочленами, коэффициенты которых образуют определитель $k$-того порядка $=\pm 1$, а правые миноры равны по абсолютной величине заданным аргументам (правые - значит образованные вычеркиванием первого столбца и строк от первой до $k$-той). Операция прибавления/вычитания к элементам некоторого столбца нескольких элементов другого столбца за исключением первого оставляет неизменными значения как определителя, так и правых миноров. Как следствие - существование если не приведенных (как в случае $k=2$), то хотя бы нормализованных решений с "маленькими" коэффициентами. Решение $(1)$ из начала поста можно немножко подровнять, прибавляя к третьему столбцу второй или удвоенный второй:
$$\begin{pmatrix}
1 & 5 & -5\\ 
1 & 0 & -3\\ 
-1 & -2 & 4
\end{pmatrix}\rightarrow \begin{pmatrix}
1 & 5 & 0\\ 
1 & 0 & -3\\ 
-1 & -2 & 2
\end{pmatrix}\rightarrow \begin{pmatrix}
1 & 5 & 5\\ 
1 & 0 & -3\\ 
-1 & -2 & 0
\end{pmatrix}$$ Изменим несколько терминологию и будем говорить о решении уравнения $$a_1x_1-a_2x_2+a_3x_3-...\pm a_kx_k=\pm 1\ (2),$$ где попарно отличные натуральные аргументы $a_1,a_2,...,a_k$ не имеют общего делителя $>1$ и расположены от большего к меньшему в порядке убывания: $a_1>a_2>...>a_k$. Вопрос: нельзя ли получить матрицу решения $(2)$ посредством нескольких операций с определителями $k$-того порядка из некой сингулярной матрицы подобно последовательности подходящих дробей, которая и есть в сущности последовательность единичных определителей второго порядка? Заключение домашней лаборатории дает положительный ответ на этот вопрос при соблюдении некоторых правил.

1) Последовательность остатков $r_n$.
$r_{1-k}=a_1,r_{2-k}=a_2,...,r_{-1}=a_{k-1},r_0=a_k.$ $r_1$ есть остаток от деления $a_1\mod a_2,r_2=a_2\mod a_3,...,r_n=r_{n-k}\mod r_{n-k+1}.$ Вычисления заканчиваются при достижении подпоследовательности из $k-1$ нулей. При достижении подпоследовательности из меньшего количества нулей с последующим ненулевым членом нулевые остатки меняются на соответствующие делители (возврат на $k-1$ шаг), и вычисления продолжаются.

2) Последовательность неполных частных $u_n$ (аналог непрерывной дроби). $u_1=\dfrac{a_1-r_1}{a_2},u_2=\dfrac{a_2-r_2}{a_3},...,u_n=\dfrac{r_{n-k}-r_n}{r_{n-k+1}}.$

3) Последовательность столбцов единичных определителей $k$-того порядка (аналог последовательности подходящих дробей). $k$ начальных членов суть столбцы сингулярной матрицы
$$\begin{pmatrix}
-1 & 0 & \ 0 & \cdots & 0 \\
0 & 1 & \ 0 & \cdots & 0 \\   
0 & 0 &  \ \ & \cdots & 0 \\       
\vdots & \vdots  & \vdots & \ddots & \vdots \\
0 & 0 & \ 0 & \cdots & (-1)^k
\end{pmatrix}$$ Начиная с $n=1$, члены каждой строки вычисляются по формуле $q_n=-u_nq_{n-k+1}+q_{n-k}$. $k$ последних столбцов образуют матрицу решения уравнения $(2)$.




При вычислении последовательности $r_n$ можно брать вместо остатков абсолютно наименьшие вычеты, а при замене локальных нулевых остатков уменьшать на единицу неполные частные по абсолютной величине. При $k>2$ разница весьма ощутима. Для уравнения $140x_1-105_2+84x_3-60x_4=\pm 1$, к примеру, в первом случае получаем дробь из $25$-и знаков и большие числа в решении, во втором - всего из четырнадцати: $u_n=1,1,1,2,2,1,-2,1,2,-1,-1,3,-1,1$ и вполне симпатичную последовательность $$\begin{matrix}
-1 & 0 & 0 & 0 & -1 & 0 & 0 & 2 & -1\\
0 & 1 & 0 & 0 & -1 & 1 & 0 & 2 & -3\\
0 & 0 & -1 & 0 & 0 & 1 & -1 & 0 & -2\\
0 & 0 & 0 & 1 & 0 & 0 & -1 & 1 & 0
\end{matrix}\ \ \ \ \begin{matrix}
0 & 4 & 3 & -1 & 4 & 7 & 6 & 3 & -3\\
1 & 4 & 5 & -5 & 5 & 9 & 20 & 0 & -4\\
2 & -1 & 2 & -6 & 1 & 1 & 20 & -5 & 0\\
1 & 1 & 1 & -2 & 2 & 2 & 7 & 0 & 0
\end{matrix}$$ Подровняем: $$\begin{pmatrix}
7 & 6 & 3 & -3\\ 
9 & 20 & 0 & -4\\ 
1 & 20 & -5 & 0\\ 
2 & 7 & 0 & 0
\end{pmatrix}\rightarrow \begin{pmatrix}
7 & -9 & 3 & -3\\ 
9 & 0 & 0 & -4\\ 
1 & 20 & -5 & 0\\ 
2 & 7 & 0 & 0
\end{pmatrix}\rightarrow \begin{pmatrix}
7 & 3 & 3 & -3\\ 
9 & 0 & 0 & -4\\ 
1 & 0 & -5 & 0\\ 
2 & 7 & 0 & 0
\end{pmatrix} $$ Каждому единичному остатку в процессе вычисления $r_n$ соответствует вариант первого столбца матрицы решения. В данном примере это пятый и шестой столбцы от конца. Кажется всё.

ex-math, спасибо еще раз за поправку, тема в самом деле интересная. Наверное должен быть более экономный подход, где сама дробь записывается не в строку, а в таблицу из $k$ строк, но меня интересует главным образом возможность перехода к иррациональностям, а там нужны инструменты попроще. $x\sqrt{a}+y\sqrt{b}+z\sqrt{c}\approx 0$ например. Каким это может сопутствовать уравнениям?

Такие $ k$-этажные дроби :wink:

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 18 ]  На страницу Пред.  1, 2

Модераторы: Toucan, maxal, PAV, Karan, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group