Metoda ćakrawala

Metoda ćakrawala (चक्रवाल विधि) – algorytm pozwalający rozwiązywać nieoznaczone równania kwadratowe, w tym równanie Pella. Przypisywana jest zazwyczaj Bhaskarze II (ok. 1114–1185), choć niektórzy przypisują ją Dźajadewie (ok. 950–1000). 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. 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.

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

Historia

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 ćakrawala do 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–1658 w odpowiedzi na wyzwanie rzucone przez Fermata. W całości metoda została po raz pierwszy opisana przez Lagrange’a w 1766. 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”.

Hermann Hankel nazywa metodę ćakrawala

„najdoskonalszym wynikiem w teorii liczb przez Lagrangem”.

Opis metody

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_{1}x_{2}+Ny_{1}y_{2})^{2}-N(x_{1}y_{2}+x_{2}y_{1})^{2}.$

Pozwala to „łączyć” (samāsa) dwie trójki $(x_{1},y_{1},k_{1})$ i $(x_{2},y_{2},k_{2})$ będące rozwiązaniami równania

$x^{2}-Ny^{2}=k,$

aby wygenerować nową trójkę:

$(x_{1}x_{2}+Ny_{1}y_{2},x_{1}y_{2}+x_{2}y_{1},k_{1}k_{2}).$

W metodzie ogólnej łączy się dowolną trójkę $(a,b,k)$ będącą znanym rozwiązaniem $a^{2}-Nb^{2}=k$ z trójką trywialną $(m,1,m^{2}-N)$ uzyskując nową trójkę $(am+Nb,a+bm,k(m^{2}-N))$ z parametrem $m.$ Równanie z nowo uzyskaną trójką dzieli się przez $k^{2}$ (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 ${\frac {a+bm}{k}}$ było całkowite, to wtedy pozostałe dwa wyrażenia ${\frac {am+Nb}{k}}$ i ${\frac {m^{2}-N}{k}}$ także będą całkowite.

Ze wszystkich odpowiadających $m$ wybiera się takie, aby wartość bezwzględna $m^{2}-N$ była najmniejsza. Wtedy trójkę $(a,b,k)$ 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. 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

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

$x^{2}-7y^{2}=1.$

W pierwszym kroku znajdujemy znaną trójkę $(a,b,k)$ spełniającą równanie $a^{2}-7b^{2}=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 $m_{1}=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 $m_{2}=3$ ostatecznie otrzymujemy trójkę $(8,3,1),$ co oznacza, że

$8^{2}-7\cdot 3^{2}=1.$

Przypadek $n=61$

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.

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,m^{2}-61),$ otrzymujemy $(8m+61,8+m,3(m^{2}-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 $m^{2}-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 $\left({\tfrac {39}{2}},\ {\tfrac {5}{2}},\ -1\right),$ która po połączeniu dwa razy z sobą samą daje $\left({\tfrac {1523}{2}},\ {\tfrac {195}{2}},\ 1\right),$ a następnie $(29\,718,\ 3805,\ -1).$

W końcu łączy się dwie kopie trójki $(29\,718,\ 3805,\ -1),$ otrzymując $(1\,766\,319\,049,\ 226\,153\,980,\ 1).$ Jest to najmniejsze rozwiązanie całkowite.

Przypadek $n=67$

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

$x^{2}-67y^{2}=1$

dla $x$ i $y$.

Rozpoczynamy od pewnego rozwiązania równania

$a^{2}-67b^{2}=k.$

Możemy przyjąć $b=1,$ otrzymując

$8^{2}-67\cdot 1^{2}=-3.$

W każdym kroku algorytmu znajdziemy $m>0$ takie, że $k$ dzieli $a+bm$ i $|m^{2}-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 $(a_{1},b_{1},k_{1})=(8,1,-3).$ Chcemy znaleźć dodatnie $m$ takie, że $k_{1}$ dzieli $a_{1}+mb_{1},$ tj. 3 dzieli $8+m,$ i $|m^{2}-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 $(a_{1},b_{1},k_{1})$ otrzymujemy nową:

$a_{2}={\frac {(8\cdot 7+67\cdot 1)}{3}}=41,b_{2}={\frac {(8+1\cdot 7)}{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 $a_{2}=41,b_{2}=5,k_{2}=6.$ Chcemy znaleźć takie $m>0,$ że $k_{2}$ dzieli $a_{2}+mb_{2},$ tzn. 6 dzieli $41+5m,$ i $|m^{2}-67|$ jest minimalne. Pierwszy warunek mówi nam, że $m$ jest postaci $6t+5$ (np. 5, 11, 17,...), a wartość $|m^{2}-67|$ jest najmniejsza dla $m=5.$ W podobny sposób jak poprzednio otrzymujemy nowe rozwiązanie $(a_{3},b_{3},k_{3})=(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,\dots ),$ a z takich $m,$ wybieramy $m=9,$ otrzymując kolejną trójkę $(a_{4},b_{4},k_{4})=(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\cdot 27^{2}}{2}}\right)^{2}-67\cdot (221\cdot 27)^{2}=1,$

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

$48\,842^{2}-67\cdot 5967^{2}=1.$

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

${\sqrt {67}}\approx {\frac {48\,842}{5967}},$

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

Bibliografia

• Florian Cajori (1918), Origin of the Name „Mathematical Induction”, „The American Mathematical Monthly” 25 (5), s. 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), s. 326–356.
• C.O. Selenius, Rationale of the chakravala process of Jayadeva and Bhaskara II, „Historia Mathematica” 2 (1975), s. 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.brak strony w książce

Linki zewnętrzne

• Wstęp do metody ćakrawala. www-groups.dcs.st-and.ac.uk. [zarchiwizowane z tego adresu (2011-07-07)]. (ang.)