Метод Чакравалы

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

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

История

Чакра на санскрите означает цикл. Согласно популярной легенде, Чакравала обозначает мифический массив гор, вращающихся вокруг Земли, как стена, и не ограниченных светом и тьмой.

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

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

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

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

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

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

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

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

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

Метод

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

$(x_{1}x_{2}+Ny_{1}y_{2})^{2}-N(x_{1}y_{2}+x_{2}y_{1})^{2}=(x_{1}^{2}-Ny_{1}^{2})(x_{2}^{2}-Ny_{2}^{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)$ чтобы получить новую тройку $(am+Nb,a+bm,k(m^{2}-N))$ для любого м . Предположим, мы начали с тройки, для которой $\gcd(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, поскольку подход Брахмагупты дает решение для этих случаев.

Метод композиции Брахмагупты

В 628 году нашей эры Брахмагупта открыл общий способ найти $x$ и $y$ из $x^{2}=Ny^{2}+1,$ когда дано $a^{2}=Nb^{2}+k$, когда k равно ±1, ±2 или ±4.

к = ±1

Использование личности Брахмагупты для составления тройки $(a,b,k)$ с собой:

$(a^{2}+Nb^{2})^{2}-N(2ab)^{2}=k^{2}$ $\Rightarrow$ $(2a^{2}-k)^{2}-N(2ab)^{2}=k^{2}$

Новую тройку можно выразить как $(2a^{2}-k,2ab,k^{2})$.

Замена $k=-1$ дает решение:

$x=2a^{2}+1,y=2ab$

Для $k=1$, оригинал $(a,b)$ уже было решение. Замена $k=1$ дает секунду:

$x=2a^{2}-1,y=2ab$

к = ±2

Опять используя уравнение, $(2a^{2}-k)^{2}-N(2ab)^{2}=k^{2}$$\Rightarrow$$\left({\frac {2a^{2}-k}{k}}\right)^{2}-N\left({\frac {2ab}{k}}\right)^{2}=1$

Замена $k=2$,

$x=a^{2}-1,y=ab$

Замена $k=-2$,

$x=a^{2}+1,y=ab$

к = 4

Замена $k=4$ в уравнение $({\frac {2a^{2}-4}{4}})^{2}-N({\frac {2ab}{4}})^{2}=1$ создает тройку $({\frac {a^{2}-2}{2}},{\frac {ab}{2}},1)$.

Какое решение, если $a$ четный:

$x={\frac {a^{2}-2}{2}},y={\frac {ab}{2}}$

Если a нечетно, начните с уравнений $({\frac {a}{2}})^{2}-N({\frac {b}{2}})^{2}=1$ и $({\frac {2a^{2}-4}{4}})^{2}-N({\frac {2ab}{4}})^{2}=1$.

Ведущий к тройкам $({\frac {a}{2}},{\frac {b}{2}},1)$ и $({\frac {a^{2}-2}{2}},{\frac {ab}{2}},1)$. Составление троек дает $({\frac {a}{2}}(a^{2}-3))^{2}-N({\frac {b}{2}}(a^{2}-1))^{2}=1$

Когда $a$ странно,

$x={\frac {a}{2}}(a^{2}-3),y={\frac {b}{2}}(a^{2}-1)$

к = -4

Когда $k=-4$, затем $({\frac {a}{2}})^{2}-N({\frac {b}{2}})^{2}=-1$. Сочинение с самим собой дает $({\frac {a^{2}+Nb^{2}}{4}})^{2}-N({\frac {ab}{2}})^{2}=1$$\Rightarrow$$({\frac {a^{2}+2}{2}})^{2}-N({\frac {ab}{2}})^{2}=1$.

Снова составление себя дает $({\frac {(a^{2}+2)^{2}+Na^{2}b^{2})}{4}})^{2}-N({\frac {ab(a^{2}+2)}{2}})^{2}=1$$\Rightarrow$ $({\frac {a^{4}+4a^{2}+2}{2}})^{2}-N({\frac {ab(a^{2}+2)}{2}})^{2}=1$

Наконец, из предыдущих уравнений составьте тройки $({\frac {a^{2}+2}{2}},{\frac {ab}{2}},1)$ и $({\frac {a^{4}+4a^{2}+2}{2}},{\frac {ab(a^{2}+2)}{2}},1)$, получить

$({\frac {(a^{2}+2)(a^{4}+4a^{2}+2)+Na^{2}b^{2}(a^{2}+2)}{4}})^{2}-N({\frac {ab(a^{4}+4a^{2}+3)}{2}})^{2}=1$$\Rightarrow$$({\frac {(a^{2}+2)(a^{4}+4a^{2}+1)}{2}})^{2}-N({\frac {ab(a^{2}+3)(a^{2}+1)}{2}})^{2}=1$$\Rightarrow$$({\frac {(a^{2}+2)[(a^{2}+1)(a^{2}+3)-2)]}{2}})^{2}-N({\frac {ab(a^{2}+3)(a^{2}+1)}{2}})^{2}=1$.

Это дает нам решения

$x={\frac {(a^{2}+2)[(a^{2}+1)(a^{2}+3)-2)]}{2}}y={\frac {ab(a^{2}+3)(a^{2}+1)}{2}}$

(Примечание, $k=-4$ полезно найти решение уравнения Пелла , но это не всегда наименьшая пара целых чисел. например $36^{2}-52*5^{2}=-4$. Уравнение даст вам $x=1093436498,y=151632270$, что при включении в уравнение Пелла дает $1195601955878350801-1195601955878350800=1$, что работает, но то же самое $x=649,y=90$ для $N=52$.

Примеры

п = 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)$. Это минимальное целочисленное решение.

п = 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 и | м ² − 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, и | м ² − 67 | является минимальным. Первое условие подразумевает, что m имеет вид 3 t + 1 (т.е. 1, 4, 7, 10 и т. д.), и среди таких m минимальное значение достигается при m = 7. Заменив ( a , b , к ) с $\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 + 5 m , и | м ² − 67 | является минимальным. Первое условие подразумевает, что m имеет вид 6 t + 5 (т.е. 5, 11, 17 и т. д.), и среди таких m , | м ² − 67 | минимально при m = 5. Это приводит к новому решению a = (41⋅5 + 67⋅5)/6 и т. д.:

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

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

Чтобы 7 делило 90 + 11 m , у нас должно быть m = 2 + 7 t (т.е. 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}}$ с точностью до примерно $2\times 10^{-9}$.

Ссылки

• Флориан Каджори (1918), Происхождение названия «Математическая индукция», The American Mathematical Monthly 25 (5), стр. 197-201.
• Джордж Гевергезе Джозеф, Герб павлина: неевропейские корни математики (1975).
• Г. Р. Кэй, «Индийская математика», Исида 2 :2 (1919), с. 326–356.
• Клас-Олаф Селениус, «Обоснование процесса чакравалы Джаядевы и Бхаскары II». Архивировано 30 ноября 2021 г. в Wayback Machine , Historia Mathematica 2 (1975), стр. 167–184.
• Клас-Олаф Селениус, «Продолжение теории непрерывных дробей циклического метода решения уравнения Бхаскары-Пелла», Acta Acad. Подписка. Матем. 23 (10) (1963), стр. 1–44.
• Хойберг, Дейл и Рамчандани, Инду (2000). Студенческая Британика Индия . Мумбаи: Популярный Пракашан. ISBN   0-85229-760-2
• Гунатилаке, Сузанта (1998). На пути к глобальной науке: знания горнодобывающей цивилизации . Индиана: Издательство Университета Индианы. ISBN   0-253-33388-1 .
• Кумар, Нарендра (2004). Наука в Древней Индии . Дели: Anmol Publications Pvt Ltd. ISBN   81-261-2056-8
• Плокер, Ким (2007) «Математика в Индии». Математика Египта, Месопотамии, Китая, Индии и ислама: справочник Нью-Джерси: Издательство Принстонского университета. ISBN   0-691-11485-4
• Эдвардс, Гарольд (1977). Великая теорема Ферма . Нью-Йорк: Спрингер . ISBN  0-387-90230-9 .

Внешние ссылки

• Знакомство с чакравалой