Metoda ćakrawala

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj

Metoda ćakrawala (चक्रवाल विधि) – algorytm pozwalający rozwiązywać nieoznaczone równania kwadratowe, w tym równanie Pella. Przypisywana jest zazwyczaj Bhaskarze II (ok. 1114–1185)[1][2], choć niektórzy przypisują ją Dźajadewie (ok. 950~1000)[3]. Jayadeva odkrył, że metoda Brahmagupty rozwiązywania tego typu równań może być uogólniona, a następnie opisał ogólny proces, który został dopracowany przez Bhaskarę II w pracy Bidźaganita. Algorytm został nazwany metodą ćakrawala od słowa ćakra, oznaczającego koło w sanskrycie, co odnosi się do jego cyklicznej natury[4]. E. O. Selenius stwierdził, że żadne z ówczesnych, ani późniejszych dokonań matematyki europejskiej nie dorównuje potędze matematycznej złożoności metody Bhaskary[1][4].

Metoda znana jest także jako metoda cykliczna i zawiera ślady indukcji matematycznej[5].

Historia[edytuj]

Brahmagupta w 628 r. n.e. badał nieoznaczone równania kwadratowe, w tym równanie Pella

\,x^2 = Ny^2 + 1,

dla całkowitych wartości x i y. Brahmagupta potrafił rozwiązać je dla wielu, choć nie wszystkich wartości N.

Dźajadewa (IX wiek) i Bhaskara (XII wiek) zaproponowali pierwsze pełne rozwiązanie powyższego równania, używając metody chakravalado rozwiązania przypadku N = 61:

\,x = 1 766 319 049 i \,y = 226 153 980.

Równanie to zostało po raz pierwszy rozwiązane w Europie przez Williama Brounckera w latach 1657–58 w odpowiedzi na wyzwanie rzucone przez Fermata. W całości metoda została po raz pierwszy opisana przez Lagrange'a w 1766[6]. Metoda Lagrange'a wymagała obliczania dwudziestu jeden kolejnych rozwinięć ułamka łańcuchowego pierwiastka z 61, podczas gdy metoda ćakrawala jest znacznie prostsza. Selenius, ocenia metodę ćakrawala mówiąc:

"Metoda ta jest najkrótszym i najlepiej przybliżającym algorytmem, który, dzięki swoim właściwościom, przy minimalnym wysiłku i bez potrzeby obliczania dużych liczb, podaje najlepsze rozwiązanie równania. Metoda ćakrawala wyprzedziła metody europejskie o ponad tysiąc lat. Żadne europejskie osiągnięcie na polu algebry w czasach późniejszych niż czasy Bhaskary nie może się równać cudownej złożoności i pomysłowości tej metody"[1][4].

Hermann Hankel nazywa metodę ćakrawala

"najdoskonalszym wynikiem w teorii liczb przez Lagrangem"[7].

Opis metody[edytuj]

Metoda ćakrawala pozwala rozwiązywać równanie Pella dzięki użyciu tożsamości Brahmagupty:

(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.

Pozwala to "łączyć" (samāsa) dwie trójki (x1, y1, k1) i (x2, y2, k2) będące rozwiązaniami równania

x^2 - Ny^2 = k\,

aby wygenerować nową trójkę:

(x_1x_2 + Ny_1y_2 \,,\, x_1y_2 + x_2y_1 \,,\, k_1k_2).

W metodzie ogólnej łączy się dowolną trójkę (abk) będącą znanym rozwiązaniem a2 - Nb2 = k z trójką trywialną (m, 1, m2- N) uzyskując nową trójkę (am + Nba + bm, k(m2- N)) z parametrem m. Równanie z nowo uzyskaną trójką dzieli się przez k2 (przekształcenie to nosi nazwę lematu Bhaskary):

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},

lub, ponieważ znaki wyrażeń wewnątrz nawiasów nie grają roli,

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

Otrzymana nowa trójka liczb niekoniecznie jest całkowita. Jeśli jednak wystartowaliśmy od względnie pierwszych a i b (tj, takich, że NWD(a,b) = 1) i wybierzemy całkowite m tak, aby \scriptstyle \frac{a+bm}{k} było całkowite, to wtedy pozostałe dwa wyrażenia \scriptstyle \frac{am+Nb}{k} i \scriptstyle \frac{m^2-N}{k} także będą całkowite.

Ze wszystkich odpowiadających m wybiera się takie, aby wartość bezwzględna m2 - N była najmniejsza. Wtedy trójkę (abk) zastępuje się nową trójką uzyskaną z tego równania i cały proces zaczyna się od nowa, aż do momentu uzyskania trójki, dla której k = 1. Lagrange w 1768 roku udowodnił, że taki algorytm zawsze się zakończy[8]. Brahmagupta znalazł również rozwiązania w przypadkach, gdy k wynosi ±1, ±2, or ±4, na których można zakończyć algorytm.

Przykłady[edytuj]

Znajdźmy w liczbach całkowitych rozwiązanie równania

x^2-7y^2=1

W pierwszym kroku znajdujemy znaną trójkę (abk) spełniającą równanie a2 - 7b2 = k. Zauważmy, że

 2^2 - 7\cdot 1^2 = -3

Trójkę (2, 1, -3) łączymy z trójką trywialną uzyskując:

\left(\frac{2m_1+7}{3}\right)^2 - 7\cdot \left(\frac{2+m_1}{3}\right)^2 = -\frac{m_1^2-7}{3}

Wybierając m1 = 1 uzyskujemy trójkę (3, 1, 2). Powtarzając algorytm otrzymujemy kolejne równanie:

\left(\frac{3m_2+7}{2}\right)^2 - 7\cdot \left(\frac{3+m_2}{2}\right)^2 = \frac{m_2^2-7}{2}

Wybierając m2 = 3 ostatecznie otrzymujemy trójkę (8, 3, 1), co oznacza, że

8^2-7\cdot3^2=1

Przypadek n = 61[edytuj]

Znalezienie rozwiązań całkowitych równania

a^2 - 61b^2 = 1,

ustanowione przez Fermata jako wyzwanie, zostało podane przez Bhaksarę jako przykład[8].

Rozpoczynamy od znalezienia rozwiązania równania

a^2 - 61b^2 = k

Przyjmując b równe 1, uzyskujemy trójkę (8, 1, 3). Łącząc ją z trójką trywialną (m, 1, m2 - 61) otrzymujemy (8m + 61, 8 + m, 3(m2 - 61)), która z lematu Bhaskary przekształcana jest do postaci:

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

Aby 3 dzieliło 8 + m i m2 - 61 było najmniejsze, wybieramy m = 7, uzyskując trójkę (39, 5, -4). Ponieważ k = -4, możemy użyć pomysłu Brahmagupty, dzieląc uzyskaną trójkę przez -4 sprowadzając ją do postaci \scriptstyle \left(\frac{39}{2},~\frac{5}{2},~-1\right), która po połączeniu dwa razy z sobą samą daje \scriptstyle  \left(\frac{1523}{2},~\frac{195}{2},~1\right), a następnie (29718, 3805, -1).

W końcu łączy się dwie kopie trójki (29718, 3805, -1) otrzymując (1766319049, 226153980, 1). Jest to najmniejsze rozwiązanie całkowite.

Przypadek n = 67[edytuj]

Przypuśćmy, że chcielibyśmy rozwiązać równanie

x^2 - 67y^2 = 1

dla x i y[9].

Rozpoczynamy od pewnego rozwiązania równania

a^2 - 67b^2 = k

Możemy przyjąć b równe 1, otrzymując

8^2 - 67\cdot1^2 = -3.

W każdym kroku algorytmu znajdziemy m > 0 takie, że k dzieli a + bm i |m2-N| jest najmniejsze, a następnie zastąpimy trójkę (a, b, k) przez trójkę

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

W pierwszej iteracji otrzymujemy (a1,b1,k1) =(8,1,-3). Chcemy znaleźć dodatnie m takie, że k1 dzieli a1+mb1, tj. 3 dzieli 8 + m, i |m2-67| jest minimalne. Pierwszy warunek mówi, że m jest postaci 3t+1 (np. 1, 4, 7, 10,... itd.), a najmniejsza wartość wyrażenia zachodzi dla m=7. Z trójki (a1b1k1) otrzymujemy nową:

a_2 = \frac{(8\cdot7+67\cdot1)}{3} = 41, b_2 = \frac{(8 + 1\cdot7)}{3} = 5, k_2 = \frac{(7^2-67)}{(-3)} = 6.

Otrzymujemy więc nowe rozwiązanie:

41^2 - 67\cdot(5)^2 = 6

Pierwsza część cyklicznego algorytmu jest zakończona.

Druga iteracja

Teraz powtarzamy proces: mamy a2 = 41, b2 = 5, k2 = 6. Chcemy znaleźć takie m > 0, że k2 dzieli a2 + mb2, tzn. 6 dzieli 41 + 5m, i |m2 − 67| jest minimalne. Pierwszy warunek mówi nam, że m jest postaci 6t + 5 (np. 5, 11, 17,…), a wartość |m2 − 67| jest najmniejsza dla m = 5. W podobny sposób jak poprzednio otrzymujemy nowe rozwiązanie (a3b3k3)=(90,11,-7) równania:

90^2 - 67 \cdot 11^2 = -7 \,
Trzecia iteracja

Aby 7 dzieliło 90+11m, musi zachodzić m = 2 + 7t (m =2, 9, 16,…), a z takich m, wybieramy m=9, otrzymując kolejną trójkę (a4b4k4)=(221,27,-2) spełniającą równanie

221^2 - 67\cdot 27^2 = -2 \,
Rozwiązanie końcowe

Moglibyśmy powtarzać metodę cykliczną (która zakończyłaby się po siedmiu iteracjach), ale ponieważ prawa strona równania jest równa jednej z liczb ±1, ±2, ±4, możemy użyć obserwacji Brahmagupty: łącząc trójkę (221, 27, −2) z sobą samą, otrzymujemy

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

czyli rozwiązanie w liczbach całkowitych równania:

 48842^2 - 67 \cdot 5967^2 = 1

Dzięki niemu otrzymujemy również przybliżenie

\sqrt{67}\approx \frac{48842}{5967}

z dokładnością rzędu ok. 2 \times 10^{-9}.

Przypisy

  1. a b c Hoiberg & Ramchandani – Students' Britannica India: Bhaskaracharya II, str. 200
  2. Kumar, str. 23
  3. Plofker, str. 474
  4. a b c Goonatilake, str. 127, 128
  5. Cajori (1918), str. 197

    "Metoda dowodzenia zwana "indukcją matematyczną" narodziła się w wielu miejscach jednocześnie. Została znaleziona u Szwajcara Jakuba Bernoulliego, Francuza B. Pascala i P. Fermata i Włocha F. Maurolycusa [...] Jeśli wgłębić się w lekturę można odnaleźć ją wcześniej, w dziełach indyjskich i greckich, między innymi w "cyklicznej metodzie" Bhaskary i w dowodzie Euklidesa o tym, że zbiór liczb pierwszych jest nieskończony."

  6. John J. O'Connor; Edmund F. Robertson: Pell's equation w MacTutor History of Mathematics archive (ang.)
  7. Kaye (1919), str. 337.
  8. a b Mathematics and its history. Wyd. 2. Springer, 2002, s. 72–76. ISBN 978-0-387-95336-6.
  9. Przykład podany w tej sekcji (przy oznaczeniach \scriptstyle Q_n na k, \scriptstyle P_n na m, itd.) można znaleźć w: Solving the Pell equation. Springer, 2009, s. 31. ISBN 978-0-387-84922-5.

Bibliografia[edytuj]

  • Florian Cajori (1918), Origin of the Name "Mathematical Induction", The American Mathematical Monthly 25 (5), str. 197-201.
  • George Gheverghese Joseph, The Crest of the Peacock: Non-European Roots of Mathematics (1975).
  • G. R. Kaye, "Indian Mathematics", Isis 2:2 (1919), str. 326–356.
  • C. O. Selenius, "Rationale of the chakravala process of Jayadeva and Bhaskara II", Historia Mathematica 2 (1975), str. 167-184.
  • C. O. Selenius, "Kettenbruch theoretische Erklarung der zyklischen Methode zur Losung der Bhaskara-Pell-Gleichung", Acta Acad. Abo. Math. Phys. 23 (10) (1963).
  • Hoiberg, Dale & Ramchandani, Indu (2000). Students' Britannica India. Mumbai: Popular Prakashan. ISBN 0-85229-760-2
  • Goonatilake, Susantha (1998). Toward a Global Science: Mining Civilizational Knowledge. Indiana: Indiana University Press. ISBN 0-253-33388-1.
  • Kumar, Narendra (2004). Science in Ancient India. Delhi: Anmol Publications Pvt Ltd. ISBN 81-261-2056-8
  • Ploker, Kim (2007) "Mathematics in India". The Mathematics of Egypt, Mesopotamia, China, India, and Islam: A Sourcebook New Jersey: Princeton University Press. ISBN 0-691-11485-4
  • Harold Edwards: Fermat's Last Theorem. Nowy Jork: Springer, 1977. ISBN 0-387-90230-9.

Linki zewnętrzne[edytuj]