Метод «чакравала»

Метод «чакравала» (санскр. चक्रवाल विधि) — это итерационный алгоритм решения неопределённых квадратных уравнений, включая Уравнение Пелля. Обычно метод приписывают Бхаскаре II, (1114 – 1185), хотя некоторые указывают автором Джаядеву (950 ~ 1000 н.э.). Джаядева указал на то, что подход Брахмагупты для решения уравнений такого типа можно обобщить и описал этот метод обобщения. Метод позднее доработал Бхаскара II в своём трактате Bijaganita (Алгебра). Он назвал этот метод «чакравала» — чакра на санскрите означает «колесо», что указывает на циклическую натуру алгоритма. Селениус придерживается мнения, что никто из европейцев не достигал во времена Бхаскара и в более поздние времена столь изумительной высоты математической сложности.

Метод известен также как циклический метод и содержит следы математической индукции.

История

Чакра на санскрите означает цикл. В буддийской космографии вселенная состоит из бесчисленных сфер (чакравал), каждая из которых имеет свою землю, своё солнце, свою луну, небеса и ады и делится на три области, или авачара

Брахмагупта в 628 н.э. изучал неопределённые квадратные уравнения, включая уравнение Пелля

$\,x^{2}=Ny^{2}+1,$

для минимальных целых x и y. Брахмагупта смог решить уравнение для некоторых N, но не для всех.

Джаядева (9-й век) и Бхаскара (12-й век) предложили полное решение уравнения, используя метод чакравала, чтобы найти для $\,x^{2}=61y^{2}+1$ решение

$\,x=1766319049,y=226153980.$

Случай был печально известен своей сложностью и в Европе впервые был решён Браункером в 1657–58 в ответ на вызов Ферма. Браункер использовал для решения непрерывные дроби. Метод для полного решения задачи был впервые описан строго Лагранжем в 1766. Метод Лагранжа, однако, требует вычисление 21 неполных частных непрерывной дроби квадратного корня из 61, в то время как метод метод чакравала много проще. Селениус в своём обозрении метода чакравала утверждает:

«Метод, представляет лучший аппроксимационный алгоритм минимальной длины, который благодаря некоторым свойствам минимизации с наименьшими усилиями и без больших чисел автоматически даёт лучшее решение уравнения. Метод чакравала возник за более чем тысячу лет до европейских методов. Но успехи европейцев во всей алгебре во времена, более поздние времён Бхаскара, не были столь выдающимися, по сравнению с изумительной сложностью и неординарностью метода чакравала»

Герман Ганкель назвал метод чакравала

«самым лучшим, что было достигнуто в теории чисел до Лагранжа».

Метод

Из тождества Брахмагупты мы видим, что для заданного N,

$(x_{1}^{2}-Ny_{1}^{2})(x_{2}^{2}-Ny_{2}^{2})=(x_{1}x_{2}+Ny_{1}y_{2})^{2}-N(x_{1}y_{2}+x_{2}y_{1})^{2}$

Для уравнения $x^{2}-Ny^{2}=k$ это позволяет «скомбинировать» две тройки решения $(x_{1},y_{1},k_{1})$ и $(x_{2},y_{2},k_{2})$ в новую тройку

$(x_{1}x_{2}+Ny_{1}y_{2}\,,\,x_{1}y_{2}+x_{2}y_{1}\,,\,k_{1}k_{2}).$

Главная идея метода состоит в том, что любая тройка $(a,b,k)$ (удовлетворяющая уравнению $a^{2}-Nb^{2}=k$) может быть скомбинирована с тривиальной тройкой $(m,1,m^{2}-N)$ (для любого m), что даст новую тройку $(am+Nb,a+bm,k(m^{2}-N))$. Если принять, что мы начинаем с тройки, для которой НОД(a, b)=1, последнюю тройку можно понизить на k (это лемма Бхаскара):

$a^{2}-Nb^{2}=k\Rightarrow \left({\frac {am+Nb}{k}}\right)^{2}-N\left({\frac {a+bm}{k}}\right)^{2}={\frac {m^{2}-N}{k}}$

Поскольку знаки внутри скобок значения не имеют, возможны следующие подстановки:

$a\leftarrow {\frac {am+Nb}{|k|}},b\leftarrow {\frac {a+bm}{|k|}},k\leftarrow {\frac {m^{2}-N}{k}}$

Когда положительное число m выбрано так, что (a + bm)/k является целым, то целыми будут и другие два числа в тройке. Среди возможных значений m метод выбирает то, которое минимизирует абсолютное значение m² − N, а потому значение (m² − N)/k. Затем осуществляем подстановку с выбранным значением m, что приводит к тройке (a, b, k). Процесс повторяется, пока тройка с $k=1$ не будет найдена. Этот метод всегда заканчивается решением (доказано Лагранжем в 1768). Мы можем завершить процесс, когда k равно ±1, ±2 или ±4, где даёт решение подход Брахмагупты.

Примеры

n = 61

Случай n = 61 (поиск решения уравнения $a^{2}-61b^{2}=1$), которое было вызовом Ферма много веков позже, Бхаскара дал как пример.

Мы начинаем с решения $a^{2}-61b^{2}=k$ для любого k, найденного произвольным способом. Мы можем взять b равным 1 и, поскольку $8^{2}-61\cdot 1^{2}=3$, мы получим тройку $(a,b,k)=(8,1,3)$. Скомбинируем её с тройкой $(m,1,m^{2}-61)$, что даст $(8m+61,8+m,3(m^{2}-61))$, а после понижения (по лемме Бхаскара)

$\left({\frac {8m+61}{3}},{\frac {8+m}{3}},{\frac {m^{2}-61}{3}}\right).$

Чтобы 3 делило $8+m$, а $|m^{2}-61|$ было минимальным, выбираем $m=7$, так что получим тройку $(39,5,-4)$. Теперь имеем k = −4 и мы можем воспользоваться идеей Брахмагупты — тройка может быть сведена к рациональному решению $(39/2,5/2,-1)\,$, которое затем комбинируется с собой три раза с $m={7,11,9}$ соответственно, пока k не станет квадратом и мы не сможем произвести понижение. Это даёт $(1523/2,195/2,1)$. Такая процедура может быть повторена, пока не получим решение (требуется 9 дополнительных комбинаций и 4 дополнительных квадратичных понижений) $(1766319049,\,226153980,\,1)$. Это минимальное целое решение.

n = 67

Пусть нужно решить уравнение $x^{2}-67y^{2}=1$

Начинаем с решения уравнения $a^{2}-67b^{2}=k$ для k, найденного любым способом. Мы можем взять b равным 1, что даёт $8^{2}-67\cdot 1^{2}=-3$. На каждой итерации мы находим m > 0, такое, что k делит a + bm и |m² − 67| минимально. Затем мы обновляем a, b и k на ${\frac {am+Nb}{|k|}},{\frac {a+bm}{|k|}},{\frac {m^{2}-N}{k}}$.

Первая итерация

Мы имеем $(a,b,k)=(8,1,-3)$. Нам нужно положительное целое m, такое что k делит a + bm, то есть 3 делит 8 + m. Нам нужно также, чтобы при этом значение |m² − 67| было минимальным. Из первого условия следует, что m имеет вид 3t + 1 (то есть m = 1, 4, 7, 10,… и т.д.), а среди таких значений m, минимальное значение получается при m = 7. Заменяя (a, b, k) на $\left({\frac {am+Nb}{|k|}},{\frac {a+bm}{|k|}},{\frac {m^{2}-N}{k}}\right)$, получим новые значения $a=(8\cdot 7+67\cdot 1)/3=41,b=(8+1\cdot 7)/3=5,k=(7^{2}-67)/(-3)=6$. То есть, мы имеем новое решение

$41^{2}-67\cdot (5)^{2}=6.$

Вторая итерация

Повторяем процесс. Мы имеем $(a,b,k)=(41,5,6)$. Нам нужно m > 0, такое, что k делит a + bm, то есть 6 делит 41 + 5m. Нам при этом нужно, чтобы |m² − 67| было минимальным. Из первого условия следует, что m имеет вид 6t + 5 (то есть m = 5, 11, 17,… и т.д.), а среди таких чисел m минимум |m² − 67| достигается на m = 5. Это приводит нас к новому решению a = (41⋅5 + 67⋅5)/6, и т.д.:

$90^{2}-67\cdot 11^{2}=-7.$

Третья итерация

Для того, чтобы 7 делило 90 + 11m, m должно иметь вид m = 2 + 7t (то есть, 2, 9, 16,… и т.д.). Среди таких m выбираем m = 9.

$221^{2}-67\cdot 27^{2}=-2.$

Конечное решение

Мы можем продолжать итерации (и закончим после семи итераций), но поскольку правая часть находится среди чисел ±1, ±2, ±4, мы можем использовать напрямую наблюдение Брахмагупты. Скомбинируем тройку (221, 27, −2) с собой, мы получим

$\left({\frac {221^{2}+67\cdot 27^{2}}{2}}\right)^{2}-67\cdot (221\cdot 27)^{2}=1,$

То есть мы имеем целое решение:

$48842^{2}-67\cdot 5967^{2}=1.$

Это решение является приближением ${\sqrt {67}}$ в виде ${\frac {48842}{5967}}$, в котором ошибка находится в пределах $10^{-9}$.

Ссылки

• Introduction to chakravala Архивная копия от 7 июля 2011 на Wayback Machine