Разложение пропорции в цепную пропорцию

Обозначим через $\alpha_{k,i}$ $i$-ю компоненту пропорции $\alpha$ на $k$-том шаге итерации. Соответственно $a_{k,i}$ - это $i$-я компонента пропорции $a$ на $k$-том шаге итерации.

Для произвольной пропорции $\alpha$ алгоритм разложения её в цепную пропорцию выглядит следующим образом:

1. Задать аргументы $\alpha$ - приближаеиая пропорция, $N$ - максимальное число итераций. Создать массив $\alpha_k$ - массив частных пропорций и $a_k$ - массив неполных частных пропорций. Переход на шаг 2.

2. $\alpha_0 := \alpha; i := 0;$ ($i$ - число выполненных итераций); Переход на шаг 3;

3. $a_i := \left\lfloor\alpha_i\right\rfloor\;$ Переход на шаг 4.

4. Вычислить пропорцию $\beta := \alpha_i\ominus a_i$. Если $\beta\cong\bar 0$, то выход. Иначе переход на шаг 5;

5. Если $i + 1 > N$, то выход, иначе переход на шаг 6;

6. ${\alpha_{i+1} := \diagdown\beta; i := i + 1;}$ Переход на шаг 3.

В результате получаем для $\alpha$ выражение вида

$$\alpha=a_0\oplus(\diagup(a_1\oplus(\diagup(a_2\oplus(\diagup(a_3\oplus\ldots)))))$$

, которое можно записать в линию примерно так:

$$\alpha = a_0\oplus \frac{\scriptstyle{1\lefteqn{/}}}{\phantom{}}\... ...m{}}\:a_2\oplus \frac{\scriptstyle{1\lefteqn{/}}}{\phantom{}}\:a_3\oplus \ldots$$

Конечная сумма вида

$$S_k = a_0\oplus\sum_{i=1}^k\frac{\scriptstyle{1\lefteqn{/}}}{\phantom{}}\:a_i$$

называется $k$-й подходящей пропорцией, она эквивалентна некоторой рациональной пропорции, так как имеет представление, все компоненты которого целочисленны. Знак $\sum$ здесь означает последовательное применение операции пропорционального сложения $\oplus$. Для рациональной пропорции процесс разлодения в цепную будет конечным, так как целые числа частных пропорций $\alpha_{k,i}$ убывают.

Приведём пример разложения пропорции в цепную пропорцию. Пусть $\alpha=(\sqrt[3]{4}:\sqrt[3]{2}:1)'$, где $'$ - знак траспозиции. Тогда

$$\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$$

Поскольку $\alpha_3=\alpha_2$, при дальнейшем разложении пропорции $\alpha$ неполные частные $(3:3:1)'$ будут повторяться, т.е. разложение пропорции, составленной из алгебраических чисел, или модуля - $(\sqrt[3]{4}:\sqrt[3]{2}:1)'$ является периодическим, и, следовательно, бесконечным.

Займёмся рекуррентными формулами для вычисления компонент подходящих пропорций. Определим квадратную матрицу $\hat T_k$ размера $n$, составленную из столбцов $\left(T_{k-n+1},\ldots T_k\right)$. Стартовой матрицей будет матрица $\hat T_{-1}$, заполненная числами 0 повсюду, за исключением побочной диагонали, содержащей числа $1$.

$$\left( \begin{array}{cc} 0 & 1\\ 1 & 0 \end{array}\right) \... ... 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{array}{cccccccc} -n & 1-n & \ldots & -1 & 0 & 1 & \ldo... ..._{1-n} & \ldots & T_{-1} & T_0 & T_1 & \ldots & T_k \end{array}$$ (1)

Теперь получить формулу

$$\hat T_{k-1}\hat a_k=T_k,\quad\forall k=0,1,\ldots$$ (2)

по индукции несложно. Именно эта формула (2) используется для вычисления вектор-столбца $T_k$, который является представлением $k$-той подходящей пропорции. Если ввести в рассмотрение матрицу, где все незаполненные элементы равны 0,

$$\hat A_k=\left( \begin{array}{ccccc} 0 & \ldots & \ldots & \... ...\\ \ldots & \ldots & \ldots & 1 & a_{k,1} \end{array}\right)$$

, то формулу (2) можно записать в матричном виде

$$\hat T_{k-1}\hat A_k=\hat T_k,\quad\forall k=0,1,\ldots$$ (3)

Полезность такой записи состоит в том, что ${\left\vert det(\hat A_k)\right\vert=1}$, ${\left\vert det(\hat T_{-1})\right\vert=1}$, и, следовательно,

$$\left\vert det(\hat T_{k})\right\vert=1,\quad\forall k=0,1,\ldots$$ (4)

Поскольку в (1) все матрицы $\hat T_k$ целочисленны, (4) означает, что любая из них целочисленно обратима, т.е. $\hat T_k^{-1}$ - тоже целочисленная матрица. Имея $\hat T_k^{-1}\hat T_k=E$, мы немедленно получаем $\hat T_k^{-1}T_k=\bar 0$. Получить такой результат без метода цепных пропорций было бы весьма непросто.

Последнему результату можно придать и другую, имеющую большое практическое применение, формулировку. Пусть $\{\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}$ будет искомой матрицей преобразования. Далее показан простой способ её вычисления.

Из (3) следует

$$\hat T_k^{-1}=\hat A_k^{-1}\hat T_{k-1}^{-1},\quad\forall k=0,1,\ldots$$

, что позволяет, зная $\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 & \... ...1\\ 1 & \ldots & \ldots & \ldots & \ldots \end{array}\right)$$

, где все незаполненные элементы равны 0. Умножение этой матрицы на любую другую не представляет никакой сложности из-за регулярности её структуры и разрежённости.

Несложно показать, что если разложение некоторой пропорции $\alpha$ в цепную пропорцию имеет период, то $\alpha$ - алгебраический модуль, т.е. вектор, составленный из алгебраических чисел степени не выше $n$. Если некоторые частные пропорции эквивалентны друг другу, т.е. $\alpha_k\cong\alpha_m$, то существует целочисленная матрица $S$ с детерминантом, равным $1$ или $-1$, такая, что $S\alpha_k=\lambda\alpha_m$. Тогда $S-\lambda E=0$, откуда легко следует нужный результат. Сама матрица $S$ вычисляется по матрицам $\hat T$, упражнение для студентов.

Используются технологии uCoz