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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

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

История[править | править вики-текст]

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

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

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

Джаядева (9-й век) и Бхаскара (12-й век) предложили полное решение уравнения, используя метод чакравала, чтобы найти для решение

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

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

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

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

Метод[править | править вики-текст]

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

Для уравнения это позволяет «скомбинировать» две тройки решения и в новую тройку

Главная идея метода состоит в том, что любая тройка (удовлетворяющая уравнению ) может быть скомбинирована с тривиальной тройкой (для любого m), что даст новую тройку . Если принять, что мы начинаем с тройки, для которой НОД(a, b)=1, последнюю тройку можно понизить на k (это лемма Бхаскара[en]):

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

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

Примеры[править | править вики-текст]

n = 61[править | править вики-текст]

Случай n = 61 (поиск решения уравнения ), которое было вызовом Ферма много веков позже, Бхаскара дал как пример[10].

Мы начинаем с решения для любого k, найденного произвольным способом. Мы можем взять b равным 1 и, поскольку , мы получим тройку . Скомбинируем её с тройкой , что даст , а после понижения (по лемме Бхаскара[en])

Чтобы 3 делило , а было минимальным, выбираем , так что получим тройку . Теперь имеем k = −4 и мы можем воспользоваться идеей Брахмагупты — тройка может быть сведена к рациональному решению , которое затем комбинируется с собой три раза с соответственно, пока k не станет квадратом и мы не сможем произвести понижение. Это даёт . Такая процедура может быть повторена, пока не получим решение (требуется 9 дополнительных комбинаций и 4 дополнительных квадратичных понижений) . Это минимальное целое решение.

n = 67[править | править вики-текст]

Пусть нужно решить уравнение [11]

Начинаем с решения уравнения для k, найденного любым способом. Мы можем взять b равным 1, что даёт . На каждой итерации ми находим m > 0, такое, что k делит a + bm и |m2 − 67| минимально. Затем мы обновляем a, b и k на .

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

Мы имеем . Нам нужно положительное целое m, такое что k делит a + bm, то есть 3 делит 8 + m. Нам нужно также, чтобы при этом значение |m2 − 67| было минимальным. Из первого условия следует, что m имеет вид 3t + 1 (то есть m = 1, 4, 7, 10,… и т.д.), а среди таких значений m, минимальное значение получается при m = 7. Заменяя (abk) на , получим новые значения . То есть, мы имеем новое решение

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

Повторяем процесс. Мы имеем . Нам нужно 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, и т.д.:

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

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

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

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

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

Это решение является приближением в виде , в котором ошибка находится в пределах .

Примечания[править | править вики-текст]

  1. 1 2 3 Encyclopedia Britannica (India), 2000, с. 200.
  2. Kumar, 2004, с. 23.
  3. Plofker, 2007, с. 474.
  4. 1 2 3 Goonatilake, 1998, с. 127-128.
  5. Selenius, 1975, с. 167-184.
  6. Cajori 1918

    «Рассуждения, называемые «математической индукцией», имели несколько независимых источников. Они прослеживаются в глубину к швейцарцу Якобу Бернулли, французам Б. Паскалю и П. Ферма, итальянцу Ф. Мавролику. [...] Если читать немножко между строк, можно найти следы математической индукции много раньше, в работах индусов и греков, как, например, в «циклическом методе» Бхаскара и доказательстве Евклида, что число простых чисел бесконечно.»

  7. Энциклопедический словарь Ф.А. Брокгауза и И.А. Ефрона. — С.-Пб.: Брокгауз-Ефрон 1890—1907
  8. John J. O'Connor, Edmund F. Robertson; «Pell's equation» MacTutor History of Mathematics archive, University of St Andrews
  9. Kaye, 1919, с. 337.
  10. 1 2 Stillwell, 2002, с. 72–76.
  11. Пример взят из книги (с обозначением для k, для m, etc.) Якобсона и Уильямса (Jacobson, Williams 2009)

Литература[править | править вики-текст]

  • Dale Hoiberg, Indu Ramchandani. Bhaskaracharya II // Students' Britannica India. — New Delhi: Encyclopedia Britannica (India), 2000. — Т. 1 (A – C).
  • Florian Cajori Origin of the Name «Mathematical Induction» // The American Mathematical Monthly. — 1918. — Т. 25, вып. 5. — С. 197-201.
  • George Gheverghese Joseph. The Crest of the Peacock: Non-European Roots of Mathematics. — 3rd. — Princeton University Press, 1991. — ISBN 9780691135267.
  • G. R. Kaye Indian Mathematics // Isis. — 1919. — Т. 2, вып. 2. — С. 326–356.
  • C.-O. Selenius Rationale of the chakravala process of Jayadeva and Bhaskara II // Historia Mathematica. — 1975. — Вып. 2. — С. 167-184.
  • C.-O. Selenius Kettenbruch theoretische Erklarung der zyklischen Methode zur Losung der Bhaskara-Pell-Gleichung // Acta Acad. Abo. Math. Phys. — 1963. — Т. 23, вып. 10.
  • Susantha Goonatilake. Toward a Global Science: Mining Civilizational Knowledge. — Indiana: Indiana University Press, 1998. — ISBN 0-253-33388-1.
  • Narendra Kumar. Science in Ancient India. — Delhi: Anmol Publications Pvt Ltd, 2004. — ISBN 81-261-2056-8.
  • Kim Plofker. Mathematics in India // The Mathematics of Egypt, Mesopotamia, China, India, and Islam: A Sourcebook. — New Jersey: Princeton University Press, 2007. — ISBN 0-691-11485-4.
  • Harold Edwards. Fermat's Last Theorem. — New York: Springer, 1977. — ISBN 0-387-90230-9.
  • John Stillwell. Mathematics and its history. — 2. — Springer, 2002. — С. 72–76. — ISBN 978-0-387-95336-6.
  • Michael J. Jacobson, Hugh C. Williams. Solving the Pell equation. — Springer, 2009. — С. 31. — ISBN 978-0-387-84922-5.

Ссылки[править | править вики-текст]