Metoda ćakrawala


Metoda ćakrawala w encyklopedii

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

Spis treści

Historia | edytuj kod

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

x 2 = N y 2 + 1 , {\displaystyle x^{2}=Ny^{2}+1,}

dla całkowitych wartości x {\displaystyle x} i y . {\displaystyle y.} Brahmagupta potrafił rozwiązać je dla wielu, choć nie wszystkich wartości N . {\displaystyle 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 : {\displaystyle N=61{:}}

x = 1 766 319 049 {\displaystyle x=1\,766\,319\,049} i y = 226 153 980. {\displaystyle 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[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 kod

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 . {\displaystyle (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 ) {\displaystyle (x_{1},y_{1},k_{1})} i ( x 2 , y 2 , k 2 ) {\displaystyle (x_{2},y_{2},k_{2})} będące rozwiązaniami równania

x 2 N y 2 = k , {\displaystyle x^{2}-Ny^{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 ) . {\displaystyle (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 ) {\displaystyle (a,b,k)} będącą znanym rozwiązaniem a 2 N b 2 = k {\displaystyle a^{2}-Nb^{2}=k} z trójką trywialną ( m , 1 , m 2 N ) {\displaystyle (m,1,m^{2}-N)} uzyskując nową trójkę ( a m + N b , a + b m , k ( m 2 N ) ) {\displaystyle (am+Nb,a+bm,k(m^{2}-N))} z parametrem m . {\displaystyle m.} Równanie z nowo uzyskaną trójką dzieli się przez k 2 {\displaystyle k^{2}} (przekształcenie to nosi nazwę lematu Bhaskary):

a 2 N b 2 = k ( a m + N b k ) 2 N ( a + b m k ) 2 = m 2 N k , {\displaystyle 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,

( a m + N b | k | ) 2 N ( a + b m | k | ) 2 = m 2 N k . {\displaystyle \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 {\displaystyle a} i b {\displaystyle b} (tj. takich, że N W D ( a , b ) = 1 {\displaystyle NWD(a,b)=1} ) i wybierzemy całkowite m {\displaystyle m} tak, aby a + b m k {\displaystyle {\frac {a+bm}{k}}} było całkowite, to wtedy pozostałe dwa wyrażenia a m + N b k {\displaystyle {\frac {am+Nb}{k}}} i m 2 N k {\displaystyle {\frac {m^{2}-N}{k}}} także będą całkowite.

Ze wszystkich odpowiadających m {\displaystyle m} wybiera się takie, aby wartość bezwzględna m 2 N {\displaystyle m^{2}-N} była najmniejsza. Wtedy trójkę ( a , b , k ) {\displaystyle (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. {\displaystyle 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 {\displaystyle k} wynosi ±1, ±2, or ±4, na których można zakończyć algorytm.

Przykłady | edytuj kod

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

x 2 7 y 2 = 1. {\displaystyle x^{2}-7y^{2}=1.}

W pierwszym kroku znajdujemy znaną trójkę ( a , b , k ) {\displaystyle (a,b,k)} spełniającą równanie a 2 7 b 2 = k . {\displaystyle a^{2}-7b^{2}=k.} Zauważmy, że

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

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

( 2 m 1 + 7 3 ) 2 7 ( 2 + m 1 3 ) 2 = m 1 2 7 3 . {\displaystyle \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 {\displaystyle m_{1}=1} uzyskujemy trójkę ( 3 , 1 , 2 ) . {\displaystyle (3,1,2).} Powtarzając algorytm otrzymujemy kolejne równanie:

( 3 m 2 + 7 2 ) 2 7 ( 3 + m 2 2 ) 2 = m 2 2 7 2 . {\displaystyle \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 {\displaystyle m_{2}=3} ostatecznie otrzymujemy trójkę ( 8 , 3 , 1 ) , {\displaystyle (8,3,1),} co oznacza, że

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

Przypadek n = 61 {\displaystyle n=61} | edytuj kod

Znalezienie rozwiązań całkowitych równania

a 2 61 b 2 = 1 , {\displaystyle 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 61 b 2 = k . {\displaystyle a^{2}-61b^{2}=k.}

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

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

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

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

Przypadek n = 67 {\displaystyle n=67} | edytuj kod

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

x 2 67 y 2 = 1 {\displaystyle x^{2}-67y^{2}=1}

dla x {\displaystyle x} i y {\displaystyle y} [9].

Rozpoczynamy od pewnego rozwiązania równania

a 2 67 b 2 = k . {\displaystyle a^{2}-67b^{2}=k.}

Możemy przyjąć b = 1 , {\displaystyle b=1,} otrzymując

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

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

a m + N b | k | , a + b m | k | , m 2 N k . {\displaystyle {\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 ) . {\displaystyle (a_{1},b_{1},k_{1})=(8,1,-3).} Chcemy znaleźć dodatnie m {\displaystyle m} takie, że k 1 {\displaystyle k_{1}} dzieli a 1 + m b 1 , {\displaystyle a_{1}+mb_{1},} tj. 3 dzieli 8 + m , {\displaystyle 8+m,} i | m 2 67 | {\displaystyle |m^{2}-67|} jest minimalne. Pierwszy warunek mówi, że m {\displaystyle m} jest postaci 3 t + 1 {\displaystyle 3t+1} (np. 1, 4, 7, 10,... itd.), a najmniejsza wartość wyrażenia zachodzi dla m = 7. {\displaystyle m=7.} Z trójki ( a 1 , b 1 , k 1 ) {\displaystyle (a_{1},b_{1},k_{1})} otrzymujemy nową:

a 2 = ( 8 7 + 67 1 ) 3 = 41 , b 2 = ( 8 + 1 7 ) 3 = 5 , k 2 = ( 7 2 67 ) ( 3 ) = 6. {\displaystyle 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 ( 5 ) 2 = 6. {\displaystyle 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. {\displaystyle a_{2}=41,b_{2}=5,k_{2}=6.} Chcemy znaleźć takie m > 0 , {\displaystyle m>0,} że k 2 {\displaystyle k_{2}} dzieli a 2 + m b 2 , {\displaystyle a_{2}+mb_{2},} tzn. 6 dzieli 41 + 5 m , {\displaystyle 41+5m,} i | m 2 67 | {\displaystyle |m^{2}-67|} jest minimalne. Pierwszy warunek mówi nam, że m {\displaystyle m} jest postaci 6 t + 5 {\displaystyle 6t+5} (np. 5, 11, 17,...), a wartość | m 2 67 | {\displaystyle |m^{2}-67|} jest najmniejsza dla m = 5. {\displaystyle m=5.} W podobny sposób jak poprzednio otrzymujemy nowe rozwiązanie ( a 3 , b 3 , k 3 ) = ( 90 , 11 , 7 ) {\displaystyle (a_{3},b_{3},k_{3})=(90,11,-7)} równania:

90 2 67 11 2 = 7. {\displaystyle 90^{2}-67\cdot 11^{2}=-7.}
Trzecia iteracja

Aby 7 dzieliło 90 + 11 m , {\displaystyle 90+11m,} musi zachodzić m = 2 + 7 t ( m = 2 , 9 , 16 , ) , {\displaystyle m=2+7t(m=2,9,16,\dots ),} a z takich m , {\displaystyle m,} wybieramy m = 9 , {\displaystyle m=9,} otrzymując kolejną trójkę ( a 4 , b 4 , k 4 ) = ( 221 , 27 , 2 ) {\displaystyle (a_{4},b_{4},k_{4})=(221,27,-2)} spełniającą równanie

221 2 67 27 2 = 2. {\displaystyle 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 ) {\displaystyle (221,27,-2)} z sobą samą, otrzymujemy

( 221 2 + 67 27 2 2 ) 2 67 ( 221 27 ) 2 = 1 , {\displaystyle \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 5967 2 = 1. {\displaystyle 48\,842^{2}-67\cdot 5967^{2}=1.}

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

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

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

Przypisy | 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 Q n {\displaystyle Q_{n}} na k , {\displaystyle k,} P n {\displaystyle P_{n}} na m {\displaystyle m} 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 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 kod

Na podstawie artykułu: "Metoda ćakrawala" pochodzącego z Wikipedii
OryginałEdytujHistoria i autorzy