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=N{y}^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=1766319049$ i $y=226153980.$

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-N{y}_1^2)(x_2^2-N{y}_2^2)=(x_1{x}_2+N{y}_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-N{y}^2=k,$

aby wygenerować nową trójkę:

$(x_1{x}_2+N{y}_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-N{b}^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-N{b}^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:

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

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 $(\frac{39}{2},\frac{5}{2},-1),$ która po połączeniu dwa razy z sobą samą daje $(\frac{1523}{2},\frac{195}{2},1),$ 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$

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+m{b}_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+m{b}_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:

$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}.$

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. Szablon:ISBN.
• Goonatilake, Susantha (1998). Toward a Global Science: Mining Civilizational Knowledge. Indiana: Indiana University Press. Szablon:ISBN.
• Kumar, Narendra (2004). Science in Ancient India. Delhi: Anmol Publications Pvt Ltd. Szablon:ISBN.
• Ploker, Kim (2007) „Mathematics in India”. The Mathematics of Egypt, Mesopotamia, China, India, and Islam: A Sourcebook New Jersey: Princeton University Press. Szablon:ISBN.
• Szablon:Cytuj książkę

Linki zewnętrzne

• Szablon:Cytuj stronę Szablon:Lang