Русская Википедия:Метод «чакравала»
Метод «чакравала» (Шаблон:Lang-sa) — это итерационный алгоритм решения Шаблон:Не переведено 5 квадратных уравнений, включая Уравнение Пелля. Обычно метод приписывают Бхаскаре II, (1114 – 1185)Шаблон:SfnШаблон:Sfn, хотя некоторые указывают автором Шаблон:Не переведено 5 (950 ~ 1000 н.э.)Шаблон:Sfn. Джаядева указал на то, что подход Брахмагупты для решения уравнений такого типа можно обобщить и описал этот метод обобщения. Метод позднее доработал Бхаскара II в своём трактате Шаблон:Не переведено 5 (Алгебра). Он назвал этот метод «чакравала» — чакра на санскрите означает «колесо», что указывает на циклическую натуру алгоритмаШаблон:Sfn. СелениусШаблон:Sfn придерживается мнения, что никто из европейцев не достигал во времена Бхаскара и в более поздние времена столь изумительной высоты математической сложностиШаблон:SfnШаблон:Sfn.
Метод известен также как циклический метод и содержит следы математической индукции[1].
История
Чакра на санскрите означает цикл. В буддийской космографии вселенная состоит из бесчисленных сфер (чакравал), каждая из которых имеет свою землю, своё солнце, свою луну, небеса и ады и делится на три области, или авачара[2]
Брахмагупта в 628 н.э. изучал неопределённые квадратные уравнения, включая уравнение Пелля
- <math>\,x^2 = Ny^2 + 1,</math>
для минимальных целых x и y. Брахмагупта смог решить уравнение для некоторых N, но не для всех.
Джаядева (9-й век) и Бхаскара (12-й век) предложили полное решение уравнения, используя метод чакравала, чтобы найти для <math>\,x^2 = 61y^2 + 1</math> решение
- <math>\,x = 1 766 319 049, y = 226 153 980.</math>
Случай был печально известен своей сложностью и в Европе впервые был решён Браункером в 1657–58 в ответ на вызов Ферма. Браункер использовал для решения непрерывные дроби. Метод для полного решения задачи был впервые описан строго Лагранжем в 1766[3]. Метод Лагранжа, однако, требует вычисление 21 неполных частных непрерывной дроби квадратного корня из 61, в то время как метод метод чакравала много проще. Селениус в своём обозрении метода чакравала утверждает
- «Метод, представляет лучший аппроксимационный алгоритм минимальной длины, который благодаря некоторым свойствам минимизации с наименьшими усилиями и без больших чисел автоматически даёт лучшее решение уравнения. Метод чакравала возник за более чем тысячу лет до европейских методов. Но успехи европейцев во всей алгебре во времена, более поздние времён Бхаскара, не были столь выдающимися, по сравнению с изумительной сложностью и неординарностью метода чакравалаШаблон:SfnШаблон:Sfn»
Герман Ганкель назвал метод чакравала
- «самым лучшим, что было достигнуто в теории чисел до Лагранжа»Шаблон:Sfn.
Метод
Из тождества Брахмагупты мы видим, что для заданного N,
- <math>(x_1^2 - Ny_1^2)(x_2^2 - Ny_2^2) = (x_1x_2 + Ny_1y_2)^2 - N(x_1y_2 + x_2y_1)^2</math>
Для уравнения <math>x^2 - Ny^2 = k</math> это позволяет «скомбинировать» две тройки решения <math>(x_1, y_1, k_1)</math> и <math>(x_2, y_2, k_2)</math> в новую тройку
- <math>(x_1x_2 + Ny_1y_2 \,,\, x_1y_2 + x_2y_1 \,,\, k_1k_2).</math>
Главная идея метода состоит в том, что любая тройка <math>(a,b,k)</math> (удовлетворяющая уравнению <math>a^2 - Nb^2 = k</math>) может быть скомбинирована с тривиальной тройкой <math>(m, 1, m^2 - N)</math> (для любого m), что даст новую тройку <math>(am + Nb, a+bm, k(m^2-N))</math>. Если принять, что мы начинаем с тройки, для которой НОД(a, b)=1, последнюю тройку можно понизить на k (это Шаблон:Не переведено 5):
- <math>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}</math>
Поскольку знаки внутри скобок значения не имеют, возможны следующие подстановки:
- <math>a\leftarrow\frac{am+Nb}{|k|}, b\leftarrow\frac{a+bm}{|k|}, k\leftarrow\frac{m^2-N}{k}</math>
Когда положительное число m выбрано так, что (a + bm)/k является целым, то целыми будут и другие два числа в тройке. Среди возможных значений m метод выбирает то, которое минимизирует абсолютное значение m2 − N, а потому значение (m2 − N)/k. Затем осуществляем подстановку с выбранным значением m, что приводит к тройке (a, b, k). Процесс повторяется, пока тройка с <math>k=1</math> не будет найдена. Этот метод всегда заканчивается решением (доказано Лагранжем в 1768)Шаблон:Sfn. Мы можем завершить процесс, когда k равно ±1, ±2 или ±4, где даёт решение подход Брахмагупты.
Примеры
n = 61
Случай n = 61 (поиск решения уравнения <math>a^2 - 61b^2 = 1</math>), которое было вызовом Ферма много веков позже, Бхаскара дал как примерШаблон:Sfn.
Мы начинаем с решения <math>a^2 - 61b^2 = k</math> для любого k, найденного произвольным способом. Мы можем взять b равным 1 и, поскольку <math>8^2 - 61\cdot1^2 = 3</math>, мы получим тройку <math>(a,b,k) = (8, 1, 3)</math>. Скомбинируем её с тройкой <math>(m, 1, m^2-61)</math>, что даст <math>(8m+61, 8+m, 3(m^2-61))</math>, а после понижения (по Шаблон:Не переведено 5)
- <math>\left( \frac{8m+61}{3}, \frac{8+m}{3}, \frac{m^2-61}{3} \right).</math>
Чтобы 3 делило <math>8+m</math>, а <math>|m^2-61|</math> было минимальным, выбираем <math>m=7</math>, так что получим тройку <math>(39, 5, -4)</math>. Теперь имеем k = −4 и мы можем воспользоваться идеей Брахмагупты — тройка может быть сведена к рациональному решению <math>(39/2, 5/2, -1)\,</math>, которое затем комбинируется с собой три раза с <math>m={7,11,9}</math> соответственно, пока k не станет квадратом и мы не сможем произвести понижение. Это даёт <math>(1523/2, 195/2, 1)</math>. Такая процедура может быть повторена, пока не получим решение (требуется 9 дополнительных комбинаций и 4 дополнительных квадратичных понижений) <math>(1766319049,\, 226153980,\, 1)</math>. Это минимальное целое решение.
n = 67
Пусть нужно решить уравнение <math>x^2 - 67y^2 = 1</math> [4]
Начинаем с решения уравнения <math>a^2 - 67b^2 = k</math> для k, найденного любым способом. Мы можем взять b равным 1, что даёт <math>8^2 - 67\cdot1^2 = -3</math>. На каждой итерации мы находим m > 0, такое, что k делит a + bm и |m2 − 67| минимально. Затем мы обновляем a, b и k на <math>\frac{am+Nb}{|k|}, \frac{a+bm}{|k|}, \frac{m^2-N}{k}</math>.
- Первая итерация
Мы имеем <math>(a,b,k) = (8,1,-3)</math>. Нам нужно положительное целое m, такое что k делит a + bm, то есть 3 делит 8 + m. Нам нужно также, чтобы при этом значение |m2 − 67| было минимальным. Из первого условия следует, что m имеет вид 3t + 1 (то есть m = 1, 4, 7, 10,… и т.д.), а среди таких значений m, минимальное значение получается при m = 7. Заменяя (a, b, k) на <math>\left(\frac{am+Nb}{|k|}, \frac{a+bm}{|k|}, \frac{m^2-N}{k}\right)</math>, получим новые значения <math>a = (8\cdot7+67\cdot1)/3 = 41, b = (8 + 1\cdot7)/3 = 5, k = (7^2-67)/(-3) = 6</math>. То есть, мы имеем новое решение
- <math>41^2 - 67\cdot(5)^2 = 6.</math>
- Вторая итерация
Повторяем процесс. Мы имеем <math>(a,b,k) = (41,5,6)</math>. Нам нужно m > 0, такое, что k делит a + bm, то есть 6 делит 41 + 5m. Нам при этом нужно, чтобы |m2 − 67| было минимальным. Из первого условия следует, что m имеет вид 6t + 5 (то есть m = 5, 11, 17,… и т.д.), а среди таких чисел m минимум |m2 − 67| достигается на m = 5. Это приводит нас к новому решению a = (41⋅5 + 67⋅5)/6, и т.д.:
- <math>90^2 - 67 \cdot 11^2 = -7.</math>
- Третья итерация
Для того, чтобы 7 делило 90 + 11m, m должно иметь вид m = 2 + 7t (то есть, 2, 9, 16,… и т.д.). Среди таких m выбираем m = 9.
- <math>221^2 - 67\cdot 27^2 = -2.</math>
- Конечное решение
Мы можем продолжать итерации (и закончим после семи итераций), но поскольку правая часть находится среди чисел ±1, ±2, ±4, мы можем использовать напрямую наблюдение Брахмагупты. Скомбинируем тройку (221, 27, −2) с собой, мы получим
- <math> \left(\frac{221^2 + 67\cdot27^2}{2}\right)^2 - 67\cdot(221\cdot27)^2 = 1,</math>
То есть мы имеем целое решение:
- <math> 48842^2 - 67 \cdot 5967^2 = 1.</math>
Это решение является приближением <math>\sqrt{67}</math> в виде <math> \frac{48842}{5967}</math>, в котором ошибка находится в пределах <math>10^{-9}</math>.
Примечания
Литература
- Шаблон:Книга
- Шаблон:Статья
- Шаблон:Книга
- Шаблон:Статья
- Шаблон:Статья
- Шаблон:Статья
- Шаблон:Книга
- Шаблон:Книга
- Шаблон:Книга
- Шаблон:Книга
- Шаблон:Книга
- Шаблон:Книга
Ссылки
Шаблон:Теоретико-числовые алгоритмы Шаблон:Rq
- ↑ Шаблон:Harvnb
«Рассуждения, называемые «математической индукцией», имели несколько независимых источников. Они прослеживаются в глубину к швейцарцу Якобу Бернулли, французам Б. Паскалю и П. Ферма, итальянцу Ф. Мавролику. [...] Если читать немножко между строк, можно найти следы математической индукции много раньше, в работах индусов и греков, как, например, в «циклическом методе» Бхаскара и доказательстве Евклида, что число простых чисел бесконечно.»
- ↑ Энциклопедический словарь Ф.А. Брокгауза и И.А. Ефрона. — С.-Пб.: Брокгауз-Ефрон 1890—1907
- ↑ John J. O'Connor, Edmund F. Robertson; «Pell's equation» MacTutor History of Mathematics archive, University of St Andrews
- ↑ Пример взят из книги (с обозначением <math>Q_n</math> для k, <math>P_n</math> для m, etc.) Якобсона и Уильямса Шаблон:Harv
