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 | edytuj kod]

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 | edytuj kod]

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 | edytuj kod]

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 | edytuj kod]

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 | edytuj kod]

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. 1,0 1,1 1,2 Hoiberg & Ramchandani – Students' Britannica India: Bhaskaracharya II, str. 200
  2. Kumar, str. 23
  3. Plofker, str. 474
  4. 4,0 4,1 4,2 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. 8,0 8,1 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 | edytuj kod]

  • 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 | edytuj kod]