Chakravala metoda - Chakravala method - Wikipedia

The chakravala metoda (Sanskrt: चक्रवाल विधि) je cyklický algoritmus vyřešit neurčitý kvadratické rovnice, počítaje v to Pellova rovnice. Běžně se mu připisuje Bhāskara II, (c. 1114 - 1185 nl)^[1][2] ačkoli někteří to připisují Jayadeva (c. 950 ~ 1 000 CE).^[3] Jayadeva na to poukázal Brahmagupta Přístup k řešení rovnic tohoto typu lze zobecnit a poté popsal tuto obecnou metodu, kterou později ve svém díle zdokonalil Bhāskara II. Bijaganita pojednání. Nazval ji metodou Chakravala: čakra což znamená "kolo" v Sanskrt, odkaz na cyklickou povahu algoritmu.^[4] C.-O. Selenius si myslel, že žádná evropská představení v době Bhāskary ani mnohem později nepřekročila jeho úžasnou výšku matematické složitosti.^[1][4]

Tato metoda je také známá jako cyklická metoda a obsahuje stopy matematická indukce.^[5]

Dějiny

Čakra v sanskrtu znamená cyklus. Podle populární legendy označuje Chakravala mýtický rozsah hor, které obíhají kolem Země jako zeď a nejsou omezeny světlem a temnotou.^[6]

Brahmagupta v 628 CE studoval neurčité kvadratické rovnice, včetně Pellova rovnice

${ displaystyle , x ^ {2} = Ny ^ {2} +1,}$

pro minimální celá čísla X a y. Brahmagupta to mohl vyřešit za několik N, ale ne všichni.

Jayadeva (9. století) a Bhaskara (12. století) nabídli první úplné řešení rovnice pomocí chakravala metoda najít pro ${ displaystyle , x ^ {2} = 61y ^ {2} +1,}$ řešení

${ displaystyle , x = 1766319049, y = 226153980.}$

Tento případ byl proslulý svou obtížností a byl poprvé vyřešen v roce Evropa podle Brouncker v letech 1657–58 v reakci na výzvu od Fermat za použití pokračujících frakcí. Metoda pro obecný problém byla nejprve úplně důkladně popsána Lagrange v roce 1766.^[7] Lagrangeova metoda však vyžaduje výpočet 21 po sobě jdoucích konvergentů pokračující zlomek pro odmocnina 61, zatímco chakravala metoda je mnohem jednodušší. Selenius ve svém hodnocení chakravala metoda, uvádí

„Metoda představuje nejlepší aproximační algoritmus minimální délky, který díky několika vlastnostem minimalizace s minimálním úsilím a vyhýbáním se velkému počtu automaticky vytváří nejlepší řešení rovnice. chakravala metoda předvídala evropské metody o více než tisíc let. Ale žádná evropská vystoupení v celé oblasti algebra v době mnohem pozdější než Bhaskarova, ne téměř stejná jako naše doba, se rovnala úžasné složitosti a vynalézavosti chakravala."^[1][4]

Hermann Hankel volá chakravala metoda

„to nejlepší, co bylo v teorii čísel dosaženo před Lagrangeem.“^[8]

Metoda

Z Brahmaguptaova identita, pozorujeme to za dané N,

${ displaystyle (x_ {1} x_ {2} + Ny_ {1} y_ {2}) ^ {2} -N (x_ {1} y_ {2} + x_ {2} y_ {1}) ^ {2 } = (x_ {1} ^ {2} -Ny_ {1} ^ {2}) (x_ {2} ^ {2} -Ny_ {2} ^ {2})}$

Pro rovnici ${ displaystyle x ^ {2} -Ny ^ {2} = k}$, toto umožňuje „složení“ (samāsa) dvou trojic řešení ${ displaystyle (x_ {1}, y_ {1}, k_ {1})}$ a ${ displaystyle (x_ {2}, y_ {2}, k_ {2})}$ do nové trojky

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

Obecně platí, že hlavní myšlenkou je, že každá trojná ${ displaystyle (a, b, k)}$ (tj. ten, který uspokojuje ${ displaystyle a ^ {2} -Nb ^ {2} = k}$) lze skládat s triviální trojkou ${ displaystyle (m, 1, m ^ {2} -N)}$ získat novou trojku ${ displaystyle (am + Nb, a + bm, k (m ^ {2} -N))}$ pro všechny m. Za předpokladu, že jsme začali s trojkou ${ displaystyle gcd (a, b) = 1}$, toto lze zmenšit pomocí k (tohle je Bhaskarovo lemma ):

${ displaystyle a ^ {2} -Nb ^ {2} = k Rightarrow left ({ frac {am + Nb} {k}} right) ^ {2} -N left ({ frac {a + bm} {k}} vpravo) ^ {2} = { frac {m ^ {2} -N} {k}}}$

Protože na znacích uvnitř čtverců nezáleží, jsou možné následující náhrady:

${ displaystyle a leftarrow { frac {am + Nb} {| k |}}, b leftarrow { frac {a + bm} {| k |}}, k leftarrow { frac {m ^ {2 } -N} {k}}}$

Když kladné celé číslo m je zvolen tak, aby (A + bm)/k je celé číslo, stejně tak další dvě čísla v trojnásobku. Mezi takovými m, metoda zvolí ten, který minimalizuje absolutní hodnotu m² − N a tedy to (m² − N)/k. Poté se žádá o substituční vztahy m rovná se zvolené hodnotě. Výsledkem je nový triple (A, b, k). Proces se opakuje, dokud se trojnásobek ne ${ displaystyle k = 1}$ je nalezeno. Tato metoda vždy končí řešením (prokázáno Lagrangeem v roce 1768).^[9]Volitelně můžeme zastavit kdy k je ± 1, ± 2 nebo ± 4, protože Brahmaguptův přístup poskytuje řešení pro tyto případy.

Příklady

n = 61

The n = 61 případů (určení vyhovujícího celočíselného řešení ${ displaystyle a ^ {2} -61b ^ {2} = 1}$), kterou Fermat vydal jako výzvu o mnoho století později, dal Bhaskara jako příklad.^[9]

Začínáme s řešením ${ displaystyle a ^ {2} -61b ^ {2} = k}$ pro všechny k nalezen jakýmkoli způsobem. V tomto případě to můžeme nechat b být tedy 1, protože ${ displaystyle 8 ^ {2} -61 cdot 1 ^ {2} = 3}$, máme trojku ${ displaystyle (a, b, k) = (8,1,3)}$. Skládání s ${ displaystyle (m, 1, m ^ {2} -61)}$ dává trojnásobek ${ displaystyle (8m + 61,8 + m, 3 (m ^ {2} -61))}$, který je zmenšen (nebo Bhaskarovo lemma se přímo používá) k získání:

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

Pro 3 rozdělit ${ displaystyle 8 + m}$ a ${ displaystyle | m ^ {2} -61 |}$ abychom byli minimální, volíme ${ displaystyle m = 7}$, abychom měli trojku ${ displaystyle (39,5, -4)}$. Teď tohle k je −4, můžeme použít Brahmaguptovu myšlenku: lze ji zmenšit na racionální řešení ${ displaystyle (39 / 2,5 / 2, -1) ,}$, který skládal sám se sebou třikrát, s ${ displaystyle m = {7,11,9}}$ respektive, když se k stane čtvercem a lze použít změnu měřítka, dává to ${ displaystyle (1523 / 2,195 / 2,1) ,}$. Nakonec lze takový postup opakovat, dokud není nalezeno řešení (vyžadující 9 dalších vlastních kompozic a 4 další čtverce): ${ displaystyle (1766319049, , 226153980, , 1)}$. Toto je minimální celočíselné řešení.

n = 67

Předpokládejme, že to musíme vyřešit ${ displaystyle x ^ {2} -67y ^ {2} = 1}$ pro X a y.^[10]

Začínáme s řešením ${ displaystyle a ^ {2} -67b ^ {2} = k}$ pro všechny k nalezen jakýmkoli způsobem; v tomto případě to můžeme nechat b být 1, tedy produkovat ${ displaystyle 8 ^ {2} -67 cdot 1 ^ {2} = - 3}$. Na každém kroku najdeme m > 0 takových k rozděluje A + bma |m² - 67 | je minimální. Poté aktualizujeme A, b, a k na ${ displaystyle { frac {am + Nb} {| k |}}, { frac {a + bm} {| k |}}}$ a ${ displaystyle { frac {m ^ {2} -N} {k}}}$ resp.

První iterace

My máme ${ displaystyle (a, b, k) = (8,1, -3)}$. Chceme kladné celé číslo m takhle k rozděluje A + bm, tj. 3 přepážky 8 + m, a |m² - 67 | je minimální. První podmínka to naznačuje m je ve formě 3t + 1 (tj. 1, 4, 7, 10,… atd.) A mezi nimi m, je dosaženo minimální hodnoty pro m = 7. Výměna (A, b, k) s ${ displaystyle left ({ frac {am + Nb} {| k |}}, { frac {a + bm} {| k |}}, { frac {m ^ {2} -N} {k }}že jo)}$, dostaneme nové hodnoty ${ displaystyle a = (8 cdot 7 + 67 cdot 1) / 3 = 41, b = (8 + 1 cdot 7) / 3 = 5, k = (7 ^ {2} -67) / (- 3) = 6}$. To znamená, že máme nové řešení:

${ displaystyle 41 ^ {2} -67 cdot (5) ^ {2} = 6.}$

V tomto okamžiku je dokončeno jedno kolo cyklického algoritmu.

Druhá iterace

Nyní postup opakujeme. My máme ${ displaystyle (a, b, k) = (41,5,6)}$. Chceme m > 0 takových k rozděluje A + bm, tj. 6 dělí 41 + 5ma |m² - 67 | je minimální. První podmínka to naznačuje m je ve formě 6t + 5 (tj. 5, 11, 17,… atd.) A mezi nimi m, |m² - 67 | je minimální pro m = 5. To vede k novému řešení A = (41⋅5 + 67⋅5) / 6 atd .:

${ displaystyle 90 ^ {2} -67 cdot 11 ^ {2} = - 7.}$

Třetí iterace

Pro 7 rozdělit 90 + 11m, musíme mít m = 2 + 7t (tj. 2, 9, 16, ... atd.) a mezi nimi m, vybíráme m = 9.

${ displaystyle 221 ^ {2} -67 cdot 27 ^ {2} = - 2.}$

Konečné řešení

V tomto okamžiku bychom mohli pokračovat v cyklické metodě (a ta by skončila po sedmi iteracích), ale protože pravá strana je mezi ± 1, ± 2, ± 4, můžeme také použít Brahmaguptovo pozorování přímo. Skládáme-li trojici (221, 27, −2) sami se sebou, dostaneme

${ displaystyle left ({ frac {221 ^ {2} +67 cdot 27 ^ {2}} {2}} right) ^ {2} -67 cdot (221 cdot 27) ^ {2} = 1,}$

to znamená, že máme celočíselné řešení:

${ displaystyle 48842 ^ {2} -67 cdot 5967 ^ {2} = 1.}$

Tato rovnice se přibližuje ${ displaystyle { sqrt {67}}}$ tak jako ${ displaystyle { frac {48842} {5967}}}$ na rozpětí asi ${ displaystyle 2 krát 10 ^ {- 9}}$.

Poznámky

Reference

• Florian Cajori (1918), Původ názvu „Matematická indukce“, Americký matematický měsíčník 25 (5), s. 197-201.
• George Gheverghese Joseph, The Crest of the Peacock: Non-European Roots of Mathematics (1975).
• G. R. Kaye, „indická matematika“, Isis 2: 2 (1919), s. 326–356.
• Clas-Olaf Selenius, „Odůvodnění chakravala procesu Jayadeva a Bhaskara II.“, Historia Mathematica 2 (1975), str. 167-184.
• Clas-Olaf Selenius, "Kettenbruchtheoretische Erklärung der zyklischen Methode zur Lösung der Bhaskara-Pell-Gleichung", Acta Acad. Abo. Matematika. Phys. 23 (10) (1963), s. 1-44.
• Hoiberg, Dale & Ramchandani, Indu (2000). Britannica studentů Indie. Bombaj: Populární Prakashan. ISBN  0-85229-760-2
• Goonatilake, Susantha (1998). Směrem ke globální vědě: těžba civilizačních znalostí. Indiana: Indiana University Press. ISBN  0-253-33388-1.
• Kumar, Narendra (2004). Věda ve starověké Indii. Dillí: Anmol Publications Pvt Ltd. ISBN  81-261-2056-8
• Ploker, Kim (2007) „Mathematics in India“. Matematika Egypta, Mezopotámie, Číny, Indie a islámu: Zdrojová kniha New Jersey: Princeton University Press. ISBN  0-691-11485-4
• Edwards, Harold (1977). Fermatova poslední věta. New York: Springer. ISBN  0-387-90230-9.

externí odkazy

• Úvod do chakravaly