Metoda ćakrawala

Z Wikipedii, wolnej encyklopedii
Przejdź do nawigacji Przejdź do wyszukiwania

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

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

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

i

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[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:

Pozwala to „łączyć” (samāsa) dwie trójki i będące rozwiązaniami równania

aby wygenerować nową trójkę:

W metodzie ogólnej łączy się dowolną trójkę będącą znanym rozwiązaniem z trójką trywialną uzyskując nową trójkę z parametrem Równanie z nowo uzyskaną trójką dzieli się przez (przekształcenie to nosi nazwę lematu Bhaskary):

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

Otrzymana nowa trójka liczb niekoniecznie jest całkowita. Jeśli jednak wystartowaliśmy od względnie pierwszych i (tj. takich, że ) i wybierzemy całkowite tak, aby było całkowite, to wtedy pozostałe dwa wyrażenia i także będą całkowite.

Ze wszystkich odpowiadających wybiera się takie, aby wartość bezwzględna była najmniejsza. Wtedy trójkę 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 Lagrange w 1768 roku udowodnił, że taki algorytm zawsze się zakończy[8]. Brahmagupta znalazł również rozwiązania w przypadkach, gdy 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

W pierwszym kroku znajdujemy znaną trójkę spełniającą równanie Zauważmy, że

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

Wybierając uzyskujemy trójkę Powtarzając algorytm otrzymujemy kolejne równanie:

Wybierając ostatecznie otrzymujemy trójkę co oznacza, że

Przypadek [edytuj | edytuj kod]

Znalezienie rozwiązań całkowitych równania

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

Rozpoczynamy od znalezienia rozwiązania równania

Przyjmując równe 1, uzyskujemy trójkę Łącząc ją z trójką trywialną otrzymujemy która z lematu Bhaskary przekształcana jest do postaci:

Aby 3 dzieliło i było najmniejsze, wybieramy uzyskując trójkę Ponieważ możemy użyć pomysłu Brahmagupty, dzieląc uzyskaną trójkę przez sprowadzając ją do postaci która po połączeniu dwa razy z sobą samą daje a następnie

W końcu łączy się dwie kopie trójki otrzymując Jest to najmniejsze rozwiązanie całkowite.

Przypadek [edytuj | edytuj kod]

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

dla i [9].

Rozpoczynamy od pewnego rozwiązania równania

Możemy przyjąć otrzymując

W każdym kroku algorytmu znajdziemy takie, że dzieli i jest najmniejsze, a następnie zastąpimy trójkę przez trójkę

W pierwszej iteracji otrzymujemy Chcemy znaleźć dodatnie takie, że dzieli tj. 3 dzieli i jest minimalne. Pierwszy warunek mówi, że jest postaci (np. 1, 4, 7, 10,... itd.), a najmniejsza wartość wyrażenia zachodzi dla Z trójki otrzymujemy nową:

Otrzymujemy więc nowe rozwiązanie:

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

Druga iteracja

Teraz powtarzamy proces: mamy Chcemy znaleźć takie że dzieli tzn. 6 dzieli i jest minimalne. Pierwszy warunek mówi nam, że jest postaci (np. 5, 11, 17,...), a wartość jest najmniejsza dla W podobny sposób jak poprzednio otrzymujemy nowe rozwiązanie równania:

Trzecia iteracja

Aby 7 dzieliło musi zachodzić a z takich wybieramy otrzymując kolejną trójkę spełniającą równanie

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ę z sobą samą, otrzymujemy

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

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

z dokładnością rzędu ok.

Przypisy[edytuj | edytuj kod]

  1. a b c Hoiberg & Ramchandani – Students’ Britannica India: Bhaskaracharya II, s. 200.
  2. Kumar, s. 23.
  3. Plofker, s. 474.
  4. a b c Goonatilake, s. 127, 128.
  5. Cajori (1918), s. 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), s. 337.
  8. a b John Stillwell: 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 na na itd.) można znaleźć w: Michael J. Jacobson, Hugh C. Williams: 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 Monthly25 (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.

Linki zewnętrzne[edytuj | edytuj kod]