Wusova metoda sady charakteristik - Wus method of characteristic set - Wikipedia

Tento článek obsahuje seznam obecných Reference, ale zůstává z velké části neověřený, protože postrádá dostatečné odpovídající vložené citace. Prosím pomozte zlepšit tento článek představuji přesnější citace. (Listopad 2012) (Zjistěte, jak a kdy odstranit tuto zprávu šablony)

Wenjun Wu metoda je algoritmus pro řešení vícerozměrné polynomické rovnice představen koncem 70. let čínským matematikem Wen-Tsun Wu. Tato metoda je založena na matematickém konceptu charakteristická sada představen koncem 40. let 20. století J.F.Ritt. Je zcela nezávislý na Gröbnerův základ metoda zavedená Bruno Buchberger (1965), i když k výpočtu charakteristických množin lze použít Gröbnerovy báze.^[1][2]

Wuova metoda je účinná pro prokázání mechanické věty v elementární geometrie a poskytuje kompletní rozhodovací proces pro určité třídy problémů. Používá se při výzkumu v jeho laboratoři (KLMM, Key Laboratory of Mathematics Mechanization in Chinese Academy of Science) a po celém světě. Hlavní trendy výzkumu Wuovy metody se týkají soustavy polynomiálních rovnic pozitivní dimenze a diferenciální algebra kde Ritt výsledky byly zefektivněny.^[3][4] Wuova metoda byla použita v různých vědeckých oborech, jako je biologie, počítačové vidění, kinematika robota a hlavně automatické kontroly v geometrii.^[5]

Neformální popis

Wuova metoda používá polynomiální divize k řešení problémů formuláře:

${ displaystyle forall x, y, z, dots I (x, y, z, dots) implikuje f (x, y, z, dots) ,}$

kde F je polynomiální rovnice a Já je spojení z polynomiální rovnice. Algoritmus je u těchto problémů kompletní komplexní doména.

Základní myšlenkou algoritmu je, že můžete rozdělit jeden polynom na druhý, abyste získali zbytek. Opakované dělení má za následek buď zmizení zbytku (v tom případě Já naznačuje F prohlášení je pravdivé), nebo zbyl neredukovatelný zbytek (v takovém případě je prohlášení nepravdivé).

Přesněji řečeno, pro ideál Já v prsten k[X₁, ..., X_n] nad polem k, (Rittova) charakteristická sada C z Já se skládá ze sady polynomů v Já, který má trojúhelníkový tvar: polynomy v C mají odlišné hlavní proměnné (viz formální definice níže). Vzhledem k charakteristické sadě C z Já, lze rozhodnout, zda polynom F je nula modulo Já. To znamená, že je možné ověřit test členství Já, za předpokladu charakteristické sady Já.

Sada charakteristik Ritt

Rittova charakteristická množina je konečná množina polynomů v trojúhelníkový tvar ideálu. Tato trojúhelníková sada splňuje určité minimální podmínky s ohledem na Rittovo uspořádání a zachovává mnoho zajímavých geometrických vlastností ideálu. Nemusí to však být jeho systém generátorů.

Zápis

Nechť R je vícerozměrný polynomiální kruh k[X₁, ..., X_n] nad polem kProměnné jsou řazeny lineárně podle jejich dolního indexu: X₁ < ... < X_nPro nekonstantní polynom p v R, největší proměnná účinně prezentující v p, volala hlavní proměnná nebo třídahraje zvláštní roli:p lze přirozeně považovat za jednorozměrný polynom ve své hlavní proměnné X_k s koeficienty v k[X₁, ..., X_k−1]. Stupeň p jako univariantního polynomu v jeho hlavní proměnné se také nazývá jeho hlavní stupeň.

Trojúhelníková sada

Sada T nekonstantních polynomů se nazývá a trojúhelníková sada pokud jsou všechny polynomy v T mají odlišné hlavní proměnné. Tím se zobecní trojúhelníkový tvar soustavy lineárních rovnic přirozeným způsobem.

Ritt objednávání

Pro dva nekonstantní polynomy p a q, říkáme p je menší než q s ohledem na Ritt objednávání a napsáno jako p <_r q, pokud platí jedno z následujících tvrzení:

(1) hlavní proměnná p je menší než hlavní proměnná q, tj. mvar (p) q),

(2) p a q mají stejnou hlavní proměnnou a hlavní stupeň p je menší než hlavní stupeň zq, tj. mvar (p) = mvar (q) a mdeg (p) q).

Takto, (k[X₁, ..., X_n],<_r) tvoří a částečný řád. Objednávání Ritt však není celková objednávka: existují polynomy p a q takové, že ani jeden p <_r q ani p >_r q. V tomto případě to říkáme p a q nejsou srovnatelné. Řazení Ritt porovnává hodnost z p a q. Hodnost, označená hodností (p), nekonstantního polynomu p je definován jako síla jeho hlavní proměnné: mvar (p)^{mdeg (p)} a pozice se porovnávají nejprve porovnáním proměnných a poté v případě rovnosti proměnných stupně.

Rittovo objednávání na trojúhelníkových sadách

Rozhodujícím zobecněním při Rittově objednávání je porovnání trojúhelníkových množin T = { t₁, ..., t_u} a S = { s₁, ..., s_proti} být dvě trojúhelníkové množiny, ve kterých jsou polynomy T a S jsou stále více tříděny podle jejich hlavních proměnných T je menší než S w.r.t. Objednávejte podle Ritta, pokud platí jedno z následujících tvrzení

(1) existuje k ≤ min (u, proti) takové, že pozice (t_i) = pořadí (s_i) pro 1 ≤i < k a t_k <_r s_k,

(2) u > proti a pořadí (t_i) = pořadí (s_i) pro 1 ≤i ≤ proti.

Existují také nesrovnatelné trojúhelníkové sady s uspořádáním Ritt.

Sada charakteristik Ritt

Nechť jsem nenulový ideál k [x₁, ..., X_n]. Podskupina T I je a Sada charakteristik Ritt z I, pokud platí jedna z následujících podmínek:

(1) T se skládá z jediné nenulové konstanty k,

(2) T je trojúhelníková množina a T je minimální w.r.t Rittovo uspořádání v množině všech trojúhelníkových množin obsažených v I.

Polynomiální ideál může mít (nekonečně) mnoho charakteristických množin, protože Rittovo uspořádání je částečné pořadí.

Sada charakteristik Wu

Proces Ritt – Wu, nejprve navržený Rittem, následně modifikovaný Wu, nepočítá Rittovu charakteristiku, ale rozšířenou, nazvanou Wu charakteristická sada nebo vzestupný řetězec.

Neprázdná podmnožina T ideálního ⟨F⟩ generovaného F je a Sada charakteristik Wu F, pokud platí některá z následujících podmínek

(1) T = {a} s nenulovou konstantou,

(2) T je trojúhelníková množina a existuje podmnožina G ⟨F⟩ taková, že ⟨F⟩ = ⟨G⟩ a každý polynom v G je pseudo-redukovaný na nulu vzhledem k T.

Sada charakteristik Wu je definována množinou F polynomů, spíše ideálním ⟨F⟩ generovaným F. Rovněž lze ukázat, že Rittova charakteristická sada T ofF⟩ je charakteristická sada Wu F. Sada charakteristik Wu být vypočítán Wuovým algoritmem CHRST-REM, který vyžaduje pouze výpočty pseudo-zbytku a nejsou potřeba žádné faktorizace.

Metoda charakteristické sady Wu má exponenciální složitost; vylepšení výpočetní efektivity slabými řetězci, pravidelné řetězy byly zavedeny nasycené řetězce^[6]

Rozkládající se algebraické odrůdy

Aplikace je algoritmus pro řešení systémů algebraických rovnic pomocí charakteristických množin. Přesněji řečeno, vzhledem k konečné podmnožině F polynomů existuje algoritmus pro výpočet charakteristických množin T₁, ..., T_E takové, že:

${ displaystyle V (F) = W (T_ {1}) pohár cdots pohár W (T_ {e}), ,}$

kde W (T_i) je rozdíl V (T_i) a V (h_i), zde h_i je produktem iniciál polynomů v T_i.

Viz také

• Pravidelný řetěz
• Matematicko-mechanická platforma

Reference

• P. Aubry, M. Moreno Maza (1999) Trojúhelníkové sady pro řešení polynomiálních systémů: komparativní implementace čtyř metod. J. Symb. Comput. 28 (1–2): 125–154
• David A. Cox, John B. Little, Donal O'Shea. Ideály, odrůdy a algoritmy. 2007.
• Hua-Shan, Liu (24. srpna 2005). „WuRittSolva: Implementation of Wu-Ritt Characteristic Set Method“. Archiv knihovny Wolfram. Wolfram. Citováno 17. listopadu 2012.
• Heck, André (2003). Úvod do javoru (3. vyd.). New York: Springer. str.105, 508. ISBN  9780387002309.
• Ritt, J. (1966). Diferenciální algebra. New York, Dover Publications.
• Dongming Wang (1998). Metody eliminace. Springer-Verlag, Wien, Springer-Verlag
• Dongming Wang (2004). Eliminační praxe, Imperial College Press, Londýn ISBN  1-86094-438-8
• Wu, W. T. (1984). Základní principy dokazování mechanické věty v elementárních geometriích. J. Syst. Sci. Matematika. Sci., 4, 207–35
• Wu, W. T. (1987). Věta o nulové struktuře pro řešení polynomiálních rovnic. MM Research Preprints, 1, 2–12
• Xiaoshan, Gao; Chunming, Yuan; Guilin, Zhang (2009). "Metoda Ritt-Wu pro charakteristickou množinu pro běžné diferenciální polynomické systémy s libovolným uspořádáním". Acta Mathematica Scientia. 29 (4): 1063–1080. CiteSeerX  10.1.1.556.9549. doi:10.1016 / S0252-9602 (09) 60086-2.

externí odkazy

• balíček wsolve Maple
• Sada charakteristických sad Ritt-Wu pro Mathematica
• Metoda sady charakteristik