\documentclass[11pt]{article}
\usepackage[utf-8]{inputenc}
\usepackage[T2A,T1]{fontenc}
\usepackage[russian]{babel}
%\usepackage{amsmath,amssymb,amsfonts}
\usepackage{amsmath,amssymb,amsfonts,textcomp}
\begin{document}
\fontencoding{T2A}\selectfont
\begin{titlepage}
\huge{\textbf{Цепные пропорции}}\newline\newline
\LARGE{Автор: Бродников Александр Петрович}\newline\newline
\LARGE{Email: chillugy@omsknet.ru}\newline\newline
\LARGE{Homepage: http://chillugy.narod.ru}
\end{titlepage}
\newpage
%\maketitle{}
%\title{Title Титул}
\section{Введение}
\textbf{\textit{Цепные пропорции}} - размерное обобщение цепных дробей. Некоторые авторы
 пользуются термином \textbf{\textit{цепные дроби размерности $n$}}. Аналогично могут
  построены обобщения для поля комплексных чисел, а также непрерывные пропорции, 
  обобщающие непрерывные дроби.  Используются цепные пропорции для совместных приближений 
  вещественных чисел рациональными, например, в теории алгебраических чмсел. Оказывается, 
  цепные пропорции позволяют построить быстрые алгоритмы для решений некоторых так называемых
   \textbf{${NP}$-полных} задач.
\section{История}
Автор придумал метод цепных пропорций ещё в $1964$ году, будучи школьником. Позже, обучаясь 
в НГУ, он же обнаружил, что этот алгоритм известен под другими названиями - и одновременно 
неизвестен, потому что не нашёл области своего применения. Попытки доказать для
цепных пропорций аналог теоремы Лагранжа-Эйлера для цепных дробей так и не удались.\newline

В теории квадратичных иррациональностей существуют две теоремы: первая гласит,
что каждая периодическая цепная дробь соответствует разложению некоторой квадратичной 
иррациональности в эту цепную пропорцию. Вторая утверждает, что каждая квадратичная 
иррациональность разлагается в периодическую цепную дробь (\textit{теорема Лагранжа-Эйлера}).
Аналог первой торемы для цепных пропорций доказывается легко. Доказательство аналога второй
теоремы для цепных пропорций ещё ждёт своего автора. Квадратичным иррациональстям в теории 
цепных дробей оответствуют векторы, составленные из алгебраических чисел заданной размерности,
или \textit{модули}.
\section{Метод цепных дробей}
Постановка задачи: найти приближения вещественного числа $\alpha$ рациональнымы, желательно 
с \textit{наилучшей} в некотором смысле точностью. Например, чтобы абсолютная ошибка ${\left|{}a/b - \alpha\right|}$ не превышала ${1/b}$, где ${a,b \in Z}$. Если $\alpha \in Z$, приближение единственно: $\alpha/1$. Иначе запускается следующий шаговый алгоритм:
\newline
%\begin{enumerate}
\par
%\item 
1. Задать аргументы: $\alpha$ - приближаемое число, $n$ - максимальное число итераций. Создать массивы $\alpha_i$ - массив частных, и $a_i$ - массив неполных частных. Переход на шаг 2; 
%\item 
\par
2. $\alpha_0 := \alpha; i := 0;$ ($i$ - \textit{число выполненных итераций}); Переход на шаг 3;
%\item $a_i := \left\llcorner\alpha_i\lrcorner\right;$ Если 
%\item $a_i := \left\lfloor\alpha_i\rfloor\right;$ Если 
%\item 
\par
3. $a_i := \left\lfloor\alpha_i\right\rfloor\;$ Переход на шаг 4;
%\item 
\par
4. Если ${\alpha_i-a_i = 0}$, то выход, иначе переход на шаг 5;
%\item 
\par
5. Если $i + 1 > n$, то выход, иначе переход на шаг 6; 
%\item 
\par
6. ${\alpha_{i+1} := \displaystyle\frac{1}{\alpha_i-a_i}; i := i + 1;}$ Переход на шаг 3.
%\end{enumerate}
\newline
\newline
В результате получаем для $\alpha$ выражение в виде
$$
%\alpha = a_0 + \frac{1}{a_1 + \cfrac{1}{a_2 + \cfrac{1}{a_3 + \ldots}}}
\alpha = a_0 + \frac{1}{\displaystyle a_1 + \frac{1}{\displaystyle a_2 + \frac{1}{\displaystyle a_3 + \ldots}}}
$$
, которое принято записывать в линию примерно так:
$$
\alpha = a_0 +
\frac{\scriptstyle{1\lefteqn{/}}}{\phantom{}}\:a_1 + 
\frac{\scriptstyle{1\lefteqn{/}}}{\phantom{}}\:a_2 + 
\frac{\scriptstyle{1\lefteqn{/}}}{\phantom{}}\:a_3 + 
\ldots
$$
Если $\alpha\in{Q}$, то ряд состоит из конечного числа слагаемых. Для иррациональных $\alpha$
ряд бесконечен и всегда сходится к $\alpha$. У цепных дробей числители равны $1$, у непрерывных дробей числители - произвольны.\newline

Конечная сумма вида
${
S_n = a_0 + \sum_{i=1}^n\frac{\scriptstyle{1\lefteqn{/}}}{\phantom{}}\:a_i
}$
называется $n$-й подходящей дробью и является рациональным числом. Существуют рекуррентные формулы для вычисления таких сумм, которые естественно обобщаются на случай цепных пропорций.
\section{Пропорции}
Пропорция - это вектор из $n>1$ вещественных чисел, определённых с точностью до ненулевого множителя. Это значит, что пропорция, все компоненты которой равны $0$, является недопустимой. $\bar 0$ - пропорция, все компоненты которой равны $0$, кроме последнего,
равного $1$. Конкретная запись пропорции в виде вектора называется её представлением.
\section{Операции над пропорциями}
На множестве пропорций определены бинарные операции пропорционального сложения $\oplus$ и пропорционального вычитания $\ominus$. Пусть $C=A\oplus B$, где $A,B,C$ - пропорции размера $n$. Тогда
\begin{equation}
C_i=A_iB_n+A_nB_i,\quad(1\leqslant i\leqslant n-1),\quad C_n=A_nB_n
\notag
\end{equation}
Если $C=A\ominus B$, то
\begin{equation}
C_i=A_iB_n-A_nB_i,\quad(1\leqslant i\leqslant n-1),\quad C_n=A_nB_n
\notag
\end{equation}
В отличие от дробей, последний компонент пропорции, к примеру, $A_n$, может принимать значение $0$. Верны формулы $A=A\oplus\bar 0$ и $A=A\ominus\bar 0$.
\newline
\newline
Бинарные операции сравнения $\cong,\ncong$ на множестве пропорций возвращают логический результат $true$ или $false$. Операция $\cong$ определяется на паре пропорций $A,B$ следующим образом:
\begin{equation}
A\cong B\Rightarrow\exists\lambda\ne 0:A_i=\lambda B_i,\quad(1\leqslant i\leqslant n)
\notag
\end{equation}
Операция $\ncong$ возвращает противоположный признак результата, нежели $\cong$.
\newline
\newline
%\par
На множестве пропорций определена унарная операция инверсия $\diagup$. В случае $n=2$ ей соответствует операция обращения дроби, когда числитель и знаменатель меняются местами. В отличие от обычной дроби знаменатель пропорции может принимать значение $0$. В случае $n>2$ 
инверсия пропорции - это просто некоторая перестановка, отличная от тождественной, её компонентов. Более строгие правила правила могут требовать отсутствия циклов либо налагать какие-либо иные ограничения на эту перестановку. В данном случае вполне достаточно объявить инверсией перестановку циклического сдвига влево:
\begin{equation}
A=\diagup B\quad
\Rightarrow 
A_i=B_{i+1},\quad A_n=B_1,\quad(1\leqslant i\leqslant n-1)
\notag
\end{equation}
Операция, обратная инверсии, обозначается символом $\diagdown$. Это есть перестановка циклического сдвига вправо: 
\begin{equation}
A=\diagdown B\quad
\Rightarrow 
A_i=B_{i-1},\quad A_1=B_n,\quad(2\leqslant i\leqslant n)
\notag
\end{equation}
%\newline
%\newline
На множестве пропорций определена унарная операция $floor$. Записывается она для пропорций $A$ и $B$ так:
\begin{equation}
A=floor(B),\quad\mbox{ либо }A=\left\lfloor B\right\rfloor 
\notag
\end{equation}
, что означает
\begin{gather*}
A=\left\lfloor B\right\rfloor\quad\Rightarrow
A_i=\left\lfloor\frac{B_i}{B_n}\right\rfloor,\quad
(1\leqslant i\leqslant n-1),\quad A_n=1,\quad\mbox{ при $B_n\ne 0$}\\
%\notag
%\end{equation}
%Если $B_n=0$, то
%\begin{equation}
A=\left\lfloor B\right\rfloor\quad\Rightarrow
A=\bar 0
%A_i=0,\quad(1\leqslant i\leqslant n-1),\quad A_n=1
,\quad\mbox{ при $B_n=0$}
%\notag
\end{gather*}
\section{Разложение пропорции в цепную пропорцию}
Обозначим через $\alpha_{k,i}$ $i$-ю компоненту пропорции $\alpha$ на $k$-том шаге итерации. Соответственно $a_{k,i}$ - это $i$-я компонента пропорции $a$ на $k$-том шаге итерации.
\newline
\newline
Для произвольной пропорции $\alpha$ алгоритм разложения её в цепную пропорцию выглядит следующим образом:
%\begin{enumerate}
\newline
\par
%\item 
1. Задать аргументы $\alpha$ - приближаеиая пропорция, $N$ - максимальное
число итераций. Создать массив $\alpha_k$ - массив частных пропорций и $a_k$ - массив неполных частных пропорций. Переход на шаг 2.
%\item 
\par
2. $\alpha_0 := \alpha; i := 0;$ ($i$ - \textit{число выполненных итераций}); Переход на шаг 3;
%\item 
\par
3. $a_i := \left\lfloor\alpha_i\right\rfloor;$ Переход на шаг 4.
%\item 
\par
4. Вычислить пропорцию $\beta := \alpha_i\ominus a_i$. Если $\beta\cong\bar 0$, то выход. Иначе переход на шаг 5;
%\item 
\par
5. Если $i + 1 > N$, то выход, иначе переход на шаг 6; 
%\item 
\par
6. ${\alpha_{i+1} := \diagdown\beta; i := i + 1;}$ Переход на шаг 3.
%\end{enumerate}
\newline
\newline
В результате получаем для $\alpha$ выражение вида
\begin{equation}
\alpha=a_0\oplus(\diagup(a_1\oplus(\diagup(a_2\oplus(\diagup(a_3\oplus\ldots)))))
\notag
\end{equation}
, которое можно записать в линию примерно так:
\begin{equation}
\alpha = a_0\oplus
\frac{\scriptstyle{1\lefteqn{/}}}{\phantom{}}\:a_1\oplus 
\frac{\scriptstyle{1\lefteqn{/}}}{\phantom{}}\:a_2\oplus 
\frac{\scriptstyle{1\lefteqn{/}}}{\phantom{}}\:a_3\oplus 
\ldots
\notag
\end{equation}
Конечная сумма вида
\begin{equation}
S_k = a_0\oplus\sum_{i=1}^k\frac{\scriptstyle{1\lefteqn{/}}}{\phantom{}}\:a_i
\notag
\end{equation}
называется $k$-й подходящей пропорцией, она эквивалентна некоторой рациональной пропорции, так как имеет представление, все компоненты которого целочисленны. Знак $\sum$ здесь означает последовательное применение операции пропорционального сложения $\oplus$. Для рациональной пропорции процесс разлодения в цепную будет конечным, так как целые числа частных пропорций $\alpha_{k,i}$ убывают.
\newline
\newline
Приведём пример разложения пропорции в цепную пропорцию. Пусть $\alpha=(\sqrt[3]{4}:\sqrt[3]{2}:1)'$, где $'$ - знак траспозиции. Тогда 
\begin{gather*}
\alpha_0=\alpha=(1:1:1)'\oplus(\sqrt[3]{4}-1:\sqrt[3]{2}-1:1)'\\
\alpha_1=\diagdown(\sqrt[3]{4}-1:\sqrt[3]{2}-1:1)'=(1:\sqrt[3]{4}-1:\sqrt[3]{2}-1)'\cong\\
(\sqrt[3]{4}+\sqrt[3]{2}+1:\sqrt[3]{2}+1:1)'=(3:2:1)'\oplus(\sqrt[3]{4}+\sqrt[3]{2}-2:\sqrt[3]{2}-1:1)'\\
\alpha_2=\diagdown(\sqrt[3]{4}+\sqrt[3]{2}-2:\sqrt[3]{2}-1:1)'=(1:\sqrt[3]{4}+\sqrt[3]{2}-2:\sqrt[3]{2}-1)'\cong\\
(\sqrt[3]{4}+\sqrt[3]{2}+1:\sqrt[3]{2}+2:1)'=(3:3:1)'\oplus(\sqrt[3]{4}+\sqrt[3]{2}-2:\sqrt[3]{2}-1:1)'\\
\alpha_3=\diagdown(\sqrt[3]{4}+\sqrt[3]{2}-2:\sqrt[3]{2}-1:1)'=(1:\sqrt[3]{4}+\sqrt[3]{2}-2:\sqrt[3]{2}-1)'\cong\alpha_2
\notag
\end{gather*}
Поскольку $\alpha_3=\alpha_2$, при дальнейшем разложении пропорции $\alpha$ неполные частные $(3:3:1)'$ будут повторяться, т.е. разложение пропорции, составленной из алгебраических чисел, или модуля - $(\sqrt[3]{4}:\sqrt[3]{2}:1)'$ является периодическим, и, следовательно, бесконечным.
\newline
\newline
Займёмся рекуррентными формулами для вычисления компонент подходящих пропорций. Определим квадратную матрицу $\hat T_k$ размера $n$, составленную из столбцов $\left(T_{k-n+1},\ldots T_k\right)$. Стартовой матрицей будет матрица $\hat T_{-1}$, заполненная числами $0$ повсюду, за исключением побочной диагонали, содержащей числа $1$.
%$$
%\begin{pmatrix}
%0 & 1\\
%1 & 0
%\end{pmatrix}
%$,\quad\mbox{ при }n=2
%$$
$$
\left(
\begin{array}{cc}
0 & 1\\
1 & 0
\end{array}
\right)
\mbox{ при $n=2$}
,\quad
\left(
\begin{array}{ccc}
0 & 0 & 1\\
0 & 1 & 0\\
1 & 0 & 0
\end{array}
\right)
\mbox{ при $n=3$, и т.д.}
$$
Вектор-столбец $T_{-n}$ имеет значение $(0 \ldots 0\: 1)'$, а вектор-столбец $T_{-1}$, соответственно, ~$(1\: 0 \ldots 0)'$. Обозначим $\hat a_k=\left(1\: a_{k,n-1}\: \ldots a_{k,2}\: a_{k,1}\right)'$ и выпишем таблицу, где верхняя строка содержит номер итерации при вычислении цепной пропорции. 
\begin{equation}
%$$
\label{main_array}
\begin{array}{cccccccc}
-n     & 1-n     & \ldots & -1     & 0        & 1        & \ldots & k\\
       &         & \ldots &        & \hat a_0 & \hat a_1 & \ldots & \hat a_k\\
T_{-n} & T_{1-n} & \ldots & T_{-1} & T_0      & T_1      & \ldots & T_k
\end{array}
%$$
\end{equation}
Теперь получить формулу 
\begin{equation}
\label{k_propor}
\hat T_{k-1}\hat a_k=T_k,\quad\forall k=0,1,\ldots
\end{equation}
по индукции несложно. Именно эта формула (\ref{k_propor}) используется для вычисления вектор-столбца $T_k$, который является представлением $k$-той подходящей пропорции. Если ввести в рассмотрение матрицу, где все незаполненные элементы равны $0$,
$$
\hat A_k=\left(
\begin{array}{ccccc}
0      & \ldots & \ldots & \ldots & 1\\
1      & 0      & \ldots & \ldots & a_{k,n-1}\\
\ldots & \ldots & \ldots & \ldots & \ldots\\
\ldots & \ldots & 1      & 0 & a_{k,2}\\
\ldots & \ldots & \ldots & 1 & a_{k,1}
\end{array}
\right) 
$$
, то формулу (\ref{k_propor}) можно записать в матричном виде
\begin{equation}
\label{k_matrix_propor}
\hat T_{k-1}\hat A_k=\hat T_k,\quad\forall k=0,1,\ldots
\end{equation}
Полезность такой записи состоит в том, что ${\left|det(\hat A_k)\right|=1}$, ${\left|det(\hat T_{-1})\right|=1}$, и, следовательно, 
\begin{equation}
\label{det1}
\left|det(\hat T_{k})\right|=1,\quad\forall k=0,1,\ldots 
%\notag
\end{equation}
Поскольку в (\ref{main_array}) все матрицы $\hat T_k$ целочисленны, (\ref{det1}) означает, что любая из них целочисленно обратима, т.е. $\hat T_k^{-1}$ - тоже целочисленная матрица. Имея $\hat T_k^{-1}\hat T_k=E$, мы немедленно получаем 
$\hat T_k^{-1}T_k=\bar 0$. Получить такой результат без метода цепных пропорций было бы весьма непросто. 
\newline
\newline
Последнему результату можно придать и другую, имеющую большое практическое применение, формулировку. Пусть $\{\lambda_i\},i=1,\ldots n$ - последовательность целых чисел, такая, что Н.О.Д$(\lambda_1,\lambda_2,\ldots \lambda_n)=1$. Тогда существует целочисленное линейное преобразование с детерминантом, по модулю равном $1$, переводящее линейную комбинацию 
$\sum_{i=1}^n{}\lambda_i b_i$ в $\tilde b_j$. Здесь переменные $b_i$ - переменные до преобразования, $\tilde b_j$ - после. Индекс $j$ - произволен. Для построения такого преобразования достаточно вектор из чисел $\lambda_i$, переставленных в зависимости от $j$ порядке, записать в виде пропорции и разложить эту пропорцию в цепную пропорцию. Разложение будет конечным и оборвётся на некотором шаге $k$, так как числа $\lambda_i$ - целые. Матрица $\hat T_k^{-1}$ будет искомой матрицей преобразования. Далее показан простой способ её вычисления. 
\newline
\newline
Из (\ref{k_matrix_propor}) следует
\begin{equation}
%\label{k_matrix_propor}
\hat T_k^{-1}=\hat A_k^{-1}\hat T_{k-1}^{-1},\quad\forall k=0,1,\ldots
\notag
\end{equation}
, что позволяет, зная $\hat T_{-1}^{-1}=\hat T_{-1}$ и $\hat A_k^{-1}$, рекуррентно вычислить $\hat T_k^{-1}$, проводя все вычисления в целых числах.
Матрица $\hat A_k^{-1}$ имеет вид
$$
\hat A_k^{-1}=\left(
\begin{array}{ccccc}
-a_{k,n-1} & 1      & \ldots & \ldots & \ldots\\
-a_{k,n-2} & 0      & 1      & \ldots & \ldots\\
\ldots     & \ldots & \ldots & \ldots & \ldots\\
-a_{k,1}   & \ldots & \ldots & 0      & 1\\
1          & \ldots & \ldots & \ldots & \ldots
\end{array}
\right) 
$$
, где все незаполненные элементы равны $0$. Умножение этой матрицы на любую другую не представляет никакой сложности из-за регулярности её структуры и разрежённости.
\newline
\newline
Несложно показать, что если разложение некоторой пропорции $\alpha$ в цепную пропорцию имеет период, то $\alpha$ - алгебраический модуль, т.е. вектор, составленный из алгебраических чисел степени не выше $n$. Если некоторая частные пропорции экввалентны друг другу, т.е. $\alpha_k\cong\alpha_m$, то существует целочисленная матрица $S$ с детерминантом, равным $1$ или $-1$, такая, что $S\alpha_k=\lambda\alpha_m$. Тогда $S-\lambda E=0$, откуда легко следует нужный результат. Сама матрица $S$ вычисляется по матрицам $\hat T$. 

\end{document}
