त्रिकोणीय अपघटन: Difference between revisions

From Vigyanwiki
No edit summary
No edit summary
 
(8 intermediate revisions by 4 users not shown)
Line 1: Line 1:
chye{{Short description|Algorithm on systems of polynomials}}
{{Short description|Algorithm on systems of polynomials}}
[[कंप्यूटर बीजगणित]] में, एक [[बहुपद प्रणाली|बहुपद {{mvar| S}}]] का त्रिकोणीय अपघटन सरल बहुपद प्रणालियों का {{math|''S''<sub>1</sub>, ..., ''S<sub>e</sub>''}} एक समुच्चय है जैसे कि एक बिंदु का समाधान है {{mvar|S}} यदि और केवल यदि यह किसी एक प्रणाली का समाधान है {{math|''S''<sub>1</sub>, ..., ''S<sub>e</sub>''}}.
[[कंप्यूटर बीजगणित]] में, एक [[बहुपद प्रणाली]] {{mvar|S}} का त्रिकोणीय अपघटन सरल बहुपद प्रणालियों का एक समुच्चय है इस प्रकार एक बिंदु S का एक समाधान तभी संभव है यदि यह प्रणाली  S1, ..., Se में से किसी एक का समाधान है।


जब उद्देश्य के समाधान सेट का वर्णन करना है {{mvar|S}} इसके गुणांक [[क्षेत्र (गणित)]] के बीजीय समापन में, वे सरल प्रणालियाँ [[नियमित श्रृंखला]]एँ हैं। यदि बहुपद प्रणालियों के गुणांक {{math|''S''<sub>1</sub>, ..., ''S<sub>e</sub>''}} वास्तविक संख्याएं हैं, फिर वास्तविक समाधान हैं  {{mvar|S}} त्रिकोणीय अपघटन द्वारा नियमित अर्ध-बीजीय प्रणालियों में प्राप्त किया जा सकता है। दोनों ही मामलों में, इन सरल प्रणालियों में से प्रत्येक में त्रिकोणीय आकार और उल्लेखनीय गुण हैं, जो शब्दावली को सही ठहराते हैं।
जब इसका उद्देश्य इसके गुणांक क्षेत्र के बीजगणितीय समापन में S के समाधान समुच्चय का वर्णन करना है, तो वे सरल प्रणालियां, नियमित श्रृंखलाएं हैं। यदि बहुपद प्रणालियों के गुणांक {{math|''S''<sub>1</sub>, ..., ''S<sub>e</sub>''}} वास्तविक संख्याएं हैं, तों वास्तविक समाधान {{mvar|S}} त्रिकोणीय अपघटन द्वारा नियमित अर्ध-बीजीय प्रणालियों में प्राप्त किया जा सकता है। दोनों ही स्थितियों में, इन सरल प्रणालियों में से प्रत्येक में त्रिकोणीय आकार और उल्लेखनीय गुण हैं, जो शब्दावली को सही स्थापित करते हैं।


== इतिहास ==
== इतिहास ==
विशेषता सेट विधि पहला गुणनखंड-मुक्त एल्गोरिथ्म है, जिसे एक बीजगणितीय विविधता को समान घटकों में विघटित करने के लिए प्रस्तावित किया गया था। इसके अलावा, लेखक, [[मिस्टर वू यू वेन]] | वेन-सुन वू, ने इस पद्धति के कार्यान्वयन को महसूस किया और अपने 1987 के अग्रणी लेख में बहुपद समीकरणों को हल करने के लिए एक शून्य संरचना प्रमेय शीर्षक से प्रयोगात्मक डेटा की सूचना दी।<ref>Wu, W. T. (1987). A zero structure theorem for polynomial equations solving. MM Research Preprints, 1, 2–12</ref> इस कार्य को संदर्भ में रखने के लिए, आइए याद करें कि इस लेख के लिखे जाने के समय बीजगणितीय समुच्चय अपघटन का सामान्य विचार क्या था।
विशेषता समुच्चय विधि पहला गुणनखंड-मुक्त कलन विधि  है, जिसे एक बीजगणितीय विविधता को समान घटकों में विघटित करने के लिए प्रस्तावित किया गया था। इसके अतिरिक्त, लेखक, [[मिस्टर वू यू वेन]] ने इस पद्धति के कार्यान्वयन को महसूस किया और अपने 1987 के अग्रणी लेख में बहुपद समीकरणों को हल करने के लिए एक शून्य संरचना प्रमेय शीर्षक से प्रयोगात्मक डेटा की सूचना दी।<ref>Wu, W. T. (1987). A zero structure theorem for polynomial equations solving. MM Research Preprints, 1, 2–12</ref> इस कार्य को संदर्भ में रखने के लिए, आइए याद करें कि इस लेख के लिखे जाने के समय बीजगणितीय समुच्चय अपघटन का सामान्य विचार क्या था।


होने देना {{math|'''K'''}} बीजगणितीय रूप से बंद क्षेत्र हो और {{math|'''k'''}} का उपक्षेत्र हो {{math|'''K'''}}. उपसमुच्चय {{math|''V'' ⊂ '''K'''<sup>''n''</sup>}} एक (affine) बीजगणितीय विविधता है {{math|'''k'''}} यदि कोई बहुपद समुच्चय मौजूद है {{math|''F'' ⊂ '''k'''[''x''<sub>1</sub>, ..., ''x<sub>n</sub>'']}} जैसे कि शून्य सेट {{math|''V''(''F'') ⊂ '''K'''<sup>''n''</sup>}} का {{mvar|F}} बराबर है {{mvar|V}}.
K को एक बीजगणितीय रूप से बंद क्षेत्र होने दें और K का एक उपक्षेत्र हो। एक उपसमुच्चय V ⊂ Kn k पर एक बीजगणितीय विविधता है यदि एक बहुपद समुच्चय F ⊂ k[x1, ..., xn] उपस्थित है जैसे कि शून्य समुच्चय  V(F) ⊂ F का Kn V के बराबर है।


याद करें कि {{mvar|V}} अगर सभी बीजगणितीय किस्मों के लिए अप्रासंगिक कहा जाता है {{math|''V''<sub>1</sub>, ''V''<sub>2</sub> ⊂ '''K'''<sup>''n''</sup>}} रिश्ता {{math|''V'' {{=}} ''V''<sub>1</sub> ∪ ''V''<sub>2</sub>}} का तात्पर्य है {{math|''V'' {{=}} ''V''<sub>1</sub>}} या {{math|''V'' {{=}} ''V''<sub>2</sub>}}. पहला बीजगणितीय विविधता अपघटन परिणाम प्रसिद्ध लस्कर-नोथेर प्रमेय है जिसका अर्थ निम्नलिखित है।
याद रखें कि V को अलघुकरणीय कहा जाता है यदि सभी बीजगणितीय किस्मों के लिए V1, V2 ⊂ Kn संबंध V = V1 ∪ V2 या तो V = V1 या V = V2 को दर्शाता है पहला बीजगणितीय विविधता अपघटन परिणाम प्रसिद्ध लस्कर-नोथेर प्रमेय है जिसका अर्थ निम्नलिखित है।


: प्रमेय (लास्कर - नोथेर)। प्रत्येक बीजगणितीय किस्म के लिए {{math|''V'' ⊂ '''K'''<sup>''n''</sup>}} सूक्ष्म रूप से कई अलघुकरणीय बीजगणितीय किस्में मौजूद हैं {{math|''V''<sub>1</sub>, ..., ''V<sub>e</sub>'' ⊂ '''K'''<sup>''n''</sup>}} ऐसा कि हमारे पास है
: प्रमेय लास्कर - नोथेर प्रत्येक बीजगणितीय किस्म V ⊂ Kn के लिए सूक्ष्म रूप से कई अलघुकरणीय बीजगणितीय किस्में V1, ..., Ve ⊂ Kn उपस्थित हैं जैसे कि हमारे पास है
::<math>  V = V_1 \cup \cdots \cup V_e. </math>
::<math>  V = V_1 \cup \cdots \cup V_e. </math>
: इसके अलावा, अगर  {{math|''V<sub>i</sub>'' ⊈ ''V<sub>j</sub>''}} के लिए रखता है {{math|1 ≤ ''i'' < ''j'' ≤ ''e''}} फिर सेट {{math|{''V''<sub>1</sub>, ..., ''V<sub>e</sub>''} }} अद्वितीय है और इसका अलघुकरणीय अपघटन बनाता है {{mvar|V}}.
: उपरोक्त प्रमेय में किस्मों V1, ..., Ve को V के अलघुकरणीय घटक कहा जाता है और इसे अपघटन कलन विधि के लिए एक प्राकृतिक आउटपुट के रूप में माना जा सकता है, या, दूसरे शब्दों में, k में समीकरणों की एक प्रणाली को हल करने वाले कलन विधि के लिए  ''x''<sub>1</sub>, ..., ''x<sub>n</sub>''एक कंप्यूटर प्रोग्राम का नेतृत्व करने के लिए, इस कलन विधि विनिर्देश को निर्धारित करना चाहिए कि लघुकरणीय घटकों का प्रतिनिधित्व कैसे किया जाता है। इस तरह के एक एन्कोडिंग जोसेफ रिट [2] द्वारा निम्नलिखित परिणाम के माध्यम से प्रस्तुत किया गया है।


किस्में {{math|''V''<sub>1</sub>, ..., ''V<sub>e</sub>''}उपरोक्त प्रमेय में } के अलघुकरणीय घटक कहलाते हैं {{mvar|V}} और एक अपघटन एल्गोरिथ्म के लिए एक प्राकृतिक आउटपुट के रूप में माना जा सकता है, या, दूसरे शब्दों में, एक एल्गोरिथ्म के लिए समीकरणों की एक प्रणाली को हल करने के लिए {{math|'''k'''[''x''<sub>1</sub>, ..., ''x<sub>n</sub>'']}}.
: प्रमेय यदि  {{math|''V'' ⊂ '''K'''<sup>''n''</sup>}} एक गैर-खाली और अलघुकरणीय किस्म है तो कोई कम त्रिकोणीय समुच्चय  की गणना कर सकता है {{mvar|C}} आदर्श में निहित है <math>\langle F \rangle</math> द्वारा उत्पन्न {{mvar|F}} में {{math|'''k'''[''x''<sub>1</sub>, ..., ''x<sub>n</sub>'']}} और ऐसा है कि सभी बहुपद {{mvar|g}} में <math>\langle F \rangle</math> छद्म-विभाजन w.r.t {{mvar|C}} द्वारा शून्य हो जाता है।


एक कंप्यूटर प्रोग्राम का नेतृत्व करने के लिए, इस एल्गोरिथम विनिर्देश को निर्धारित करना चाहिए कि इरेड्यूसिबल घटकों का प्रतिनिधित्व कैसे किया जाता है। इस तरह के एक एन्कोडिंग [[जोसेफ रिट]] द्वारा पेश किया गया है<ref>Ritt, J. (1966). Differential Algebra. New York, Dover Publications</ref> निम्नलिखित परिणाम के माध्यम से।
जोसेफ रिट ने फील्ड एक्सटेंशन पर बहुपद गुणनखंडन पर आधारित बहुपद प्रणालियों को हल करने के लिए एक विधि का वर्णन किया और प्रमुख आदर्शों के विशिष्ट समुच्चय की गणना की।


: प्रमेय (रिट)। अगर {{math|''V'' ⊂ '''K'''<sup>''n''</sup>}} एक गैर-खाली और अलघुकरणीय किस्म है तो कोई कम त्रिकोणीय सेट की गणना कर सकता है {{mvar|C}} आदर्श में निहित है <math>\langle F \rangle</math> द्वारा उत्पन्न {{mvar|F}} में {{math|'''k'''[''x''<sub>1</sub>, ..., ''x<sub>n</sub>'']}} और ऐसा है कि सभी बहुपद {{mvar|g}} में <math>\langle F \rangle</math> छद्म-विभाजन w.r.t द्वारा शून्य को कम करता है {{mvar|C}}.
यद्यपि, इस पद्धति का व्यावहारिक कार्यान्वयन प्राप्त करना एक कठिन समस्या थी और बनी हुई है।1980 के दशक में, जब विशेषता समुच्चय पद्धति प्रस्तुत की गई थी, बहुपद गुणनखंडन एक सक्रिय अनुसंधान क्षेत्र था और इस विषय पर कुछ मूलभूत प्रश्न हाल ही में हल किए गए थे<ref>A. M. Steel Conquering inseparability: Primary decomposition and multivariate factorization over algebraic function fields of positive characteristic</ref>आजकल, अधिकांश अनुप्रयोग समस्याओं को संसाधित करने के लिए एक बीजगणितीय विविधता को अप्रासंगिक घटकों में विघटित करना आवश्यक नहीं है, क्योंकि अपघटन की कमजोर धारणाएं, गणना करने के लिए कम खर्चीला,पर्याप्त हैं।


हम सेट कहते हैं {{mvar|C}} Ritt के प्रमेय में आदर्श का एक Ritt विशेषता सेट <math>\langle F \rangle</math>. त्रिकोणीय सेट की धारणा के लिए कृपया नियमित श्रृंखला देखें।
अभिलक्षण समुच्चय विधि रिट की प्रमेय के निम्न संस्करण पर निर्भर करती है।


जोसेफ रिट ने फील्ड एक्सटेंशन पर बहुपद गुणनखंडन पर आधारित बहुपद प्रणालियों को हल करने के लिए एक विधि का वर्णन किया और प्रमुख आदर्शों के विशिष्ट सेटों की गणना की।
: प्रमेय वेन-त्सुन वू किसी परिमित बहुपद समुच्चय के लिए {{math|''F'' ⊂ '''k'''[''x''<sub>1</sub>, ..., ''x<sub>n</sub>'']}}, कम त्रिकोणीय समुच्चय  की गणना कर सकता है <math>C \subset \langle F \rangle</math> ऐसा है कि सभी बहुपद {{mvar|g}} में {{mvar|F}} छद्म-विभाजन w.r.t  {{mvar|C}} द्वारा शून्य को कम कर देता है .


हालाँकि, इस पद्धति का व्यावहारिक कार्यान्वयन प्राप्त करना एक कठिन समस्या थी और बनी हुई है। 1980 के दशक में, जब वू की विशेषता सेट विधि की विधि पेश की गई थी, तो बहुपद गुणनखंडन एक सक्रिय शोध क्षेत्र था और इस विषय पर कुछ मूलभूत प्रश्न हाल ही में हल किए गए थे।<ref>A. M. Steel Conquering inseparability: Primary decomposition and multivariate factorization over algebraic function fields of positive characteristic</ref>
विभिन्न अवधारणाओं औरकलन विधि  ने वेन-त्सुन वू के काम को आगे बढ़ाया। 1990 के दशक की प्रारंभ में, एक नियमित श्रृंखला की धारणा, स्वतंत्र रूप से 1991 में माइकल काल्कब्रेनर द्वारा अपनी पीएचडी थीसिस और लू यांग और जिंगझोंग झांग द्वारा प्रस्तुत  की गई थी।<ref>Yang, L., Zhang, J. (1994). [http://www.iaea.org/inis/collection/NCLCollectionStore/_Public/22/086/22086436.pdf Searching dependency between algebraic equations: an algorithm applied to automated reasoning]. Artificial Intelligence in Mathematics, pp.&nbsp;14715,  Oxford University Press.</ref> महत्वपूर्ण कलन विधि खोजों का नेतृत्व किया।
आजकल, अधिकांश अनुप्रयोग समस्याओं को संसाधित करने के लिए एक बीजगणितीय विविधता को अप्रासंगिक घटकों में विघटित करना आवश्यक नहीं है, क्योंकि अपघटन की कमजोर धारणाएं, गणना करने के लिए कम खर्चीला, पर्याप्त हैं।


अभिलक्षण समुच्चय विधि Ritt's Theorem के निम्न संस्करण पर निर्भर करती है।
काल्कब्रेनर की दृष्टि में,<ref>M. Kalkbrener: A Generalized Euclidean Algorithm for Computing Triangular Representations of Algebraic Varieties. J. Symb. Comput. 15(2): 143&ndash;167 (1993)</ref> एक बीजगणितीय विविधता के अलघुकरणीय घटकों के सामान्य शून्य का प्रतिनिधित्व करने के लिए नियमित श्रृंखलाओं का उपयोग किया जाता है। यांग और झांग के मूल कार्य में, उनका उपयोग यह तय करने के लिए किया जाता है कि क्या एक हाइपरसफेस एक अर्ध-विविधता एक नियमित श्रृंखला को काटता है। नियमित शृंखलाओं में, वास्तव में, कई दिलचस्प गुण होते हैं और बीजगणितीय या अवकल समीकरणों की प्रणाली को विघटित करने के लिए कई कलन विधि में महत्वपूर्ण धारणा है।


: प्रमेय (वेन-त्सुन वू)। किसी परिमित बहुपद समुच्चय के लिए {{math|''F'' ⊂ '''k'''[''x''<sub>1</sub>, ..., ''x<sub>n</sub>'']}}, कोई कम त्रिकोणीय सेट की गणना कर सकता है <math>C \subset \langle F \rangle</math> ऐसा है कि सभी बहुपद {{mvar|g}} में {{mvar|F}} छद्म-विभाजन w.r.t द्वारा शून्य को कम कर देता है {{mvar|C}}.
कई पत्रों में नियमित जंजीरों की जांच की गई है।<ref>S.C. Chou and X.S. Gao. On the dimension of an arbitrary ascending chain.  Chinese Bull. of Sci., 38:799--804, 1991.</ref><ref>Michael Kalkbrener. Algorithmic properties of polynomial rings. J. Symb. Comput.}, 26(5):525--581, 1998.</ref><ref>P. Aubry, D. Lazard, M. Moreno Maza. [http://www.sciencedirect.com/science/article/pii/S0747717199902699 On the theories of triangular sets]. Journal of Symbolic Computation, 28(1&ndash;2):105&ndash;124, 1999.</ref>इस विषय पर प्रचुर मात्रा में साहित्य को नियमित श्रृंखला की कई समकक्ष परिभाषाओं द्वारा समझाया जा सकता है। वास्तव मे काल्कब्रेनर का मूल सूत्रीकरण यांग और झांग से बिल्कुल अलग है। इन दो धारणाओं के बीच एक पुल, काल्कब्रेनर और यांग और झांग का दृष्टिकोण, डोंगमिंग वांग के पेपर में दिखाई देता है।<ref>D. Wang. Computing Triangular Systems and Regular Systems. Journal of Symbolic Computation 30(2) (2000) 221&ndash;236</ref>त्रिकोणीय अपघटन प्राप्त करने के लिए विभिन्न कलन विधि उपलब्ध हैं {{math|''V''(''F'')}} कालब्रेनर के अर्थ में और [[डेनियल लाजार्ड]] और वू वेनजुन वेन-त्सुन वू के अर्थ में डैनियल लाजार्ड द्वारा


विभिन्न अवधारणाओं और एल्गोरिदम ने वू वेनजुन | वेन-त्सुन वू के काम को आगे बढ़ाया। 1990 के दशक की शुरुआत में, एक नियमित श्रृंखला की धारणा, स्वतंत्र रूप से 1991 में माइकल काल्कब्रेनर द्वारा अपनी पीएचडी थीसिस और लू यांग और जिंगझोंग झांग द्वारा पेश की गई थी।<ref>Yang, L., Zhang, J. (1994). [http://www.iaea.org/inis/collection/NCLCollectionStore/_Public/22/086/22086436.pdf Searching dependency between algebraic equations: an algorithm applied to automated reasoning]. Artificial Intelligence in Mathematics, pp.&nbsp;14715,  Oxford University Press.</ref> महत्वपूर्ण एल्गोरिथम खोजों का नेतृत्व किया।
लेक्सत्रिकोणीय कलन विधि<ref>D. Lazard, ''Solving zero-dimensional algebraic systems''. Journal of Symbolic Computation '''13''', 1992</ref> और ट्रायड कलन विधि मार्क मोरेनो माज़ा द्वारा<ref>M. Moreno Maza: On triangular decomposition of algebraic varieties. MEGA 2000 (2000).</ref> विशेषता समुच्चय विधि के साथ मिलकर विभिन्न कंप्यूटर बीजगणित प्रणालियों में उपलब्ध हैं, जिनमें स्वयंसिद्धऔर [[मेपल (सॉफ्टवेयर)|मेपल सॉफ्टवेयर]] सम्मिलित हैं।
 
काल्कब्रेनर की दृष्टि में,<ref>M. Kalkbrener: A Generalized Euclidean Algorithm for Computing Triangular Representations of Algebraic Varieties. J. Symb. Comput. 15(2): 143&ndash;167 (1993)</ref> एक बीजगणितीय विविधता के अलघुकरणीय घटकों के सामान्य शून्य का प्रतिनिधित्व करने के लिए नियमित श्रृंखलाओं का उपयोग किया जाता है। यांग और झांग के मूल कार्य में, उनका उपयोग यह तय करने के लिए किया जाता है कि क्या एक हाइपरसफेस एक अर्ध-विविधता (एक नियमित श्रृंखला द्वारा दी गई) को काटता है। नियमित शृंखलाओं में, वास्तव में, कई दिलचस्प गुण होते हैं और बीजगणितीय या अवकल समीकरणों की प्रणाली को विघटित करने के लिए कई एल्गोरिदम में महत्वपूर्ण धारणा है।
 
कई पत्रों में नियमित जंजीरों की जांच की गई है।<ref>S.C. Chou and X.S. Gao. On the dimension of an arbitrary ascending chain.  Chinese Bull. of Sci., 38:799--804, 1991.</ref><ref>Michael Kalkbrener. Algorithmic properties of polynomial rings. J. Symb. Comput.}, 26(5):525--581, 1998.</ref><ref>P. Aubry, D. Lazard, M. Moreno Maza. [http://www.sciencedirect.com/science/article/pii/S0747717199902699 On the theories of triangular sets]. Journal of Symbolic Computation, 28(1&ndash;2):105&ndash;124, 1999.</ref>
इस विषय पर प्रचुर मात्रा में साहित्य को नियमित श्रृंखला की कई समकक्ष परिभाषाओं द्वारा समझाया जा सकता है। दरअसल, काल्कब्रेनर का मूल सूत्रीकरण यांग और झांग से काफी अलग है। इन दो धारणाओं के बीच एक पुल, काल्कब्रेनर और यांग और झांग का दृष्टिकोण, डोंगमिंग वांग के पेपर में दिखाई देता है।<ref>D. Wang. Computing Triangular Systems and Regular Systems. Journal of Symbolic Computation 30(2) (2000) 221&ndash;236</ref>
त्रिकोणीय अपघटन प्राप्त करने के लिए विभिन्न एल्गोरिदम उपलब्ध हैं {{math|''V''(''F'')}} कालब्रेनर के अर्थ में और [[डेनियल लाजार्ड]] और वू वेनजुन|वेन-त्सुन वू के अर्थ में। डैनियल लाजार्ड द्वारा लेक्स्ट्रियांगुलर एल्गोरिथम<ref>D. Lazard, ''Solving zero-dimensional algebraic systems''. Journal of Symbolic Computation '''13''', 1992</ref> और ट्रायड एल्गोरिदम [http://www.csd.uwo.ca/~moreno/ Marc Moreno Maza] द्वारा<ref>M. Moreno Maza: On triangular decomposition of algebraic varieties. MEGA 2000 (2000).</ref> विशेषता सेट विधि के साथ मिलकर विभिन्न कंप्यूटर बीजगणित प्रणालियों में उपलब्ध हैं, जिनमें Axiom (कंप्यूटर बीजगणित प्रणाली) और [[मेपल (सॉफ्टवेयर)]] शामिल हैं।


== औपचारिक परिभाषाएँ ==
== औपचारिक परिभाषाएँ ==
होने देना {{math|'''k'''}} एक क्षेत्र हो और {{math|''x''<sub>1</sub> < ... < ''x<sub>n</sub>''}} आदेशित चर हो। हम द्वारा निरूपित करते हैं {{math|''R'' {{=}} '''k'''[''x''<sub>1</sub>, ..., ''x<sub>n</sub>'']}} संगत बहुपद वलय। के लिए {{math|''F'' ⊂ ''R''}}, बहुपद समीकरणों की एक प्रणाली के रूप में माना जाता है, बीजगणितीय बंद होने पर त्रिकोणीय अपघटन के दो विचार हैं {{math|'''k'''}}. सबसे पहले बीजगणितीय सेट के केवल [[सामान्य बिंदु]]ओं का प्रतिनिधित्व करके आलसी रूप से विघटित करना है {{math|''V''(''F'')}} कालब्रेनर के तथाकथित अर्थ में।
मान लीजिए कि k एक क्षेत्र है और x1 <... < xn क्रमबद्ध चर हैं। हम संगत बहुपद वलय को R = k[x1, ..., xn] से निरूपित करते हैं। एफ ⊂ आर के लिए, बहुपद समीकरणों की एक प्रणाली के रूप में माना जाता है,k बीजगणितीय समापन पर त्रिकोणीय अपघटन के दो विचार हैं। कल्ब्रेनर के तथाकथित अर्थ में बीजगणितीय समुच्चय वी (एफ) के केवल सामान्य बिंदुओं का प्रतिनिधित्व करके, निरुद्योग रूप से विघटित करना पड़ता है।


 
: <math>\sqrt{(F)}=\bigcap_{i=1}^{e}\sqrt{\mathrm{sat}(T_i)}.</math>
: <math>\sqrt{(F)}=\bigcap_{i=1}^{e}\sqrt{\mathrm{sat}(T_i)}.</math>
दूसरा स्पष्ट रूप से सभी बिंदुओं का वर्णन करना है {{math|''V''(''F'')}} डैनियल लाजार्ड और वू वेनजुन | वेन-सुन वू के तथाकथित अर्थ में।
दूसरा स्पष्ट रूप से सभी बिंदुओं का वर्णन करना है {{math|''V''(''F'')}} डैनियल लाजार्ड और वू वेनजुन वेन-सुन वू के तथाकथित अर्थ में।


: <math>V(F)=\bigcup_{i=1}^{e}W(T_i).</math>
: <math>V(F)=\bigcup_{i=1}^{e}W(T_i).</math>
दोनों ही मामलों में {{math|''T''<sub>1</sub>, ..., ''T<sub>e</sub>''}} निश्चित रूप से कई नियमित श्रृंखलाएं हैं {{mvar|R}} और <math>\sqrt{\mathrm{sat}(T_i)}</math> के संतृप्त आदर्श के मूलांक को दर्शाता है {{math|''T<sub>i</sub>''}} जबकि {{math|''W''(''T<sub>i</sub>'')}} के अर्ध-घटक को दर्शाता है {{math|''T<sub>i</sub>''}}. कृपया इन धारणाओं की परिभाषा के लिए नियमित श्रृंखला देखें।
दोनों ही स्थितियों में {{math|''T''<sub>1</sub>, ..., ''T<sub>e</sub>''}} निश्चित रूप से कई नियमित श्रृंखलाएं हैं {{mvar|R}} और <math>\sqrt{\mathrm{sat}(T_i)}</math> के संतृप्त आदर्श के मूलांक को दर्शाता है जबकि {{math|''W''(''T<sub>i</sub>'')}} के अर्ध-घटक को दर्शाता है कृपया इन धारणाओं की परिभाषा के लिए नियमित श्रृंखला देखें।


अभी से मान लीजिए {{math|'''k'''}} एक [[वास्तविक बंद क्षेत्र]] है। विचार करना {{mvar|S}} बहुपदों के साथ एक अर्ध-बीजगणितीय प्रणाली {{mvar|R}}. वहां है<ref>Changbo Chen, James H. Davenport, John P. May, Marc Moreno-Maza, Bican Xia, Rong Xiao. [http://www.sciencedirect.com/science/article/pii/S0747717111002070/pdf?md5=9344a2f6467b91cc32bcef52f9275ab2&pid=1-s2.0-S0747717111002070-main.pdf&_valck=1 Triangular decomposition of semi-algebraic systems].  Proceedings of 2010 International Symposium on Symbolic and Algebraic Computation (ISSAC 2010), ACM Press, pp. 187--194, 2010.</ref> निश्चित रूप से कई नियमित अर्ध-बीजगणितीय प्रणालियाँ {{math|''S''<sub>1</sub>, ..., ''S<sub>e</sub>''}} ऐसा कि हमारे पास है
अभी से मान लीजिए {{math|'''k'''}} एक [[वास्तविक बंद क्षेत्र]] है। विचार करना {{mvar|S}} बहुपदों के साथ एक अर्ध-बीजगणितीय प्रणाली {{mvar|R}}. वहां है<ref>Changbo Chen, James H. Davenport, John P. May, Marc Moreno-Maza, Bican Xia, Rong Xiao. [http://www.sciencedirect.com/science/article/pii/S0747717111002070/pdf?md5=9344a2f6467b91cc32bcef52f9275ab2&pid=1-s2.0-S0747717111002070-main.pdf&_valck=1 Triangular decomposition of semi-algebraic systems].  Proceedings of 2010 International Symposium on Symbolic and Algebraic Computation (ISSAC 2010), ACM Press, pp. 187--194, 2010.</ref> निश्चित रूप से कई नियमित अर्ध-बीजगणितीय प्रणालियाँ {{math|''S''<sub>1</sub>, ..., ''S<sub>e</sub>''}} ऐसा कि हमारे पास है


:<math>Z_{\mathbf{k}}(S) = Z_{\mathbf{k}}(S_1) \cup \cdots \cup Z_{\mathbf{k}}(S_e) </math>
:<math>Z_{\mathbf{k}}(S) = Z_{\mathbf{k}}(S_1) \cup \cdots \cup Z_{\mathbf{k}}(S_e) </math>
कहाँ {{math|''Z''<sub>'''k'''</sub>(''S'')}} के बिंदुओं को दर्शाता है {{math|'''k'''<sup>''n''</sup>}} जो हल करता है {{mvar|S}}. नियमित अर्ध-बीजीय प्रणाली {{math|''S''<sub>1</sub>, ..., ''S<sub>e</sub>''}} अर्ध-बीजगणितीय प्रणाली का त्रिकोणीय अपघटन बनाते हैं {{mvar|S}}.
जहाँ Zk(S) kn के उन बिंदुओं को दर्शाता है जो S को हल करते हैं। नियमित अर्ध-बीजगणितीय सिस्टम S1, ..., Se अर्ध-बीजीय प्रणाली S का त्रिकोणीय अपघटन बनाते हैं.


== उदाहरण ==
== उदाहरण ==
Line 59: Line 53:
:<math>S =  
:<math>S =  
\begin{cases} x^2 + y + z = 1 \\ x + y^2 + z = 1 \\ x + y + z^2 = 1 \end{cases}</math>
\begin{cases} x^2 + y + z = 1 \\ x + y^2 + z = 1 \\ x + y + z^2 = 1 \end{cases}</math>
मेपल कोड के अनुसार:


मेपल (सॉफ्टवेयर) कोड के अनुसार:
के समाधान समुच्चय  का एक संभावित त्रिकोणीय अपघटन {{mvar|S}} [http://www.regularchains.org/ नियमित चेन]लाइब्रेरी का उपयोग करने के साथ है:
 
के समाधान सेट का एक संभावित त्रिकोणीय अपघटन {{mvar|S}} [http://www.regularchains.org/ RegularChains] लाइब्रेरी का उपयोग करने के साथ है:


:<math>\begin{cases} z = 0 \\ y = 1 \\ x = 0 \end{cases}
:<math>\begin{cases} z = 0 \\ y = 1 \\ x = 0 \end{cases}
Line 71: Line 64:
\cup
\cup
\begin{cases} z^2 + 2z -1 = 0 \\ y = z \\ x = z \end{cases}
\begin{cases} z^2 + 2z -1 = 0 \\ y = z \\ x = z \end{cases}
</math><br />
</math>
== यह भी देखें ==
== ह भी देखें ==
* वू की विशेषता सेट की विधि
* वू की विशेषता समुच्चय  की विधि
* नियमित श्रृंखला
* नियमित श्रृंखला
* नियमित अर्ध-बीजगणितीय प्रणाली
* नियमित अर्ध-बीजगणितीय प्रणाली
Line 80: Line 73:


{{Reflist}}
{{Reflist}}
[[Category: समीकरण]] [[Category: बीजगणित]] [[Category: बहुपदों]] [[Category: बीजगणितीय ज्यामिति]] [[Category: कंप्यूटर बीजगणित]] [[Category: कंप्यूटर बीजगणित प्रणाली]]


[[Category: Machine Translated Page]]
[[Category:Created On 03/03/2023]]
[[Category:Created On 03/03/2023]]
[[Category:Lua-based templates]]
[[Category:Machine Translated Page]]
[[Category:Pages with script errors]]
[[Category:Short description with empty Wikidata description]]
[[Category:Template documentation pages|Short description/doc]]
[[Category:Templates Vigyan Ready]]
[[Category:Templates that add a tracking category]]
[[Category:Templates that generate short descriptions]]
[[Category:Templates using TemplateData]]
[[Category:कंप्यूटर बीजगणित]]

Latest revision as of 07:30, 19 March 2023

कंप्यूटर बीजगणित में, एक बहुपद प्रणाली S का त्रिकोणीय अपघटन सरल बहुपद प्रणालियों का एक समुच्चय है इस प्रकार एक बिंदु S का एक समाधान तभी संभव है यदि यह प्रणाली  S1, ..., Se में से किसी एक का समाधान है।

जब इसका उद्देश्य इसके गुणांक क्षेत्र के बीजगणितीय समापन में S के समाधान समुच्चय का वर्णन करना है, तो वे सरल प्रणालियां, नियमित श्रृंखलाएं हैं। यदि बहुपद प्रणालियों के गुणांक S1, ..., Se वास्तविक संख्याएं हैं, तों वास्तविक समाधान S त्रिकोणीय अपघटन द्वारा नियमित अर्ध-बीजीय प्रणालियों में प्राप्त किया जा सकता है। दोनों ही स्थितियों में, इन सरल प्रणालियों में से प्रत्येक में त्रिकोणीय आकार और उल्लेखनीय गुण हैं, जो शब्दावली को सही स्थापित करते हैं।

इतिहास

विशेषता समुच्चय विधि पहला गुणनखंड-मुक्त कलन विधि है, जिसे एक बीजगणितीय विविधता को समान घटकों में विघटित करने के लिए प्रस्तावित किया गया था। इसके अतिरिक्त, लेखक, मिस्टर वू यू वेन ने इस पद्धति के कार्यान्वयन को महसूस किया और अपने 1987 के अग्रणी लेख में बहुपद समीकरणों को हल करने के लिए एक शून्य संरचना प्रमेय शीर्षक से प्रयोगात्मक डेटा की सूचना दी।[1] इस कार्य को संदर्भ में रखने के लिए, आइए याद करें कि इस लेख के लिखे जाने के समय बीजगणितीय समुच्चय अपघटन का सामान्य विचार क्या था।

K को एक बीजगणितीय रूप से बंद क्षेत्र होने दें और K का एक उपक्षेत्र हो। एक उपसमुच्चय V ⊂ Kn k पर एक बीजगणितीय विविधता है यदि एक बहुपद समुच्चय F ⊂ k[x1, ..., xn] उपस्थित है जैसे कि शून्य समुच्चय V(F) ⊂ F का Kn V के बराबर है।

याद रखें कि V को अलघुकरणीय कहा जाता है यदि सभी बीजगणितीय किस्मों के लिए V1, V2 ⊂ Kn संबंध V = V1 ∪ V2 या तो V = V1 या V = V2 को दर्शाता है पहला बीजगणितीय विविधता अपघटन परिणाम प्रसिद्ध लस्कर-नोथेर प्रमेय है जिसका अर्थ निम्नलिखित है।

प्रमेय लास्कर - नोथेर प्रत्येक बीजगणितीय किस्म V ⊂ Kn के लिए सूक्ष्म रूप से कई अलघुकरणीय बीजगणितीय किस्में V1, ..., Ve ⊂ Kn उपस्थित हैं जैसे कि हमारे पास है
उपरोक्त प्रमेय में किस्मों V1, ..., Ve को V के अलघुकरणीय घटक कहा जाता है और इसे अपघटन कलन विधि के लिए एक प्राकृतिक आउटपुट के रूप में माना जा सकता है, या, दूसरे शब्दों में, k में समीकरणों की एक प्रणाली को हल करने वाले कलन विधि के लिए x1, ..., xnएक कंप्यूटर प्रोग्राम का नेतृत्व करने के लिए, इस कलन विधि विनिर्देश को निर्धारित करना चाहिए कि लघुकरणीय घटकों का प्रतिनिधित्व कैसे किया जाता है। इस तरह के एक एन्कोडिंग जोसेफ रिट [2] द्वारा निम्नलिखित परिणाम के माध्यम से प्रस्तुत किया गया है।
प्रमेय यदि V ⊂ Kn एक गैर-खाली और अलघुकरणीय किस्म है तो कोई कम त्रिकोणीय समुच्चय की गणना कर सकता है C आदर्श में निहित है द्वारा उत्पन्न F में k[x1, ..., xn] और ऐसा है कि सभी बहुपद g में छद्म-विभाजन w.r.t C द्वारा शून्य हो जाता है।

जोसेफ रिट ने फील्ड एक्सटेंशन पर बहुपद गुणनखंडन पर आधारित बहुपद प्रणालियों को हल करने के लिए एक विधि का वर्णन किया और प्रमुख आदर्शों के विशिष्ट समुच्चय की गणना की।

यद्यपि, इस पद्धति का व्यावहारिक कार्यान्वयन प्राप्त करना एक कठिन समस्या थी और बनी हुई है।1980 के दशक में, जब विशेषता समुच्चय पद्धति प्रस्तुत की गई थी, बहुपद गुणनखंडन एक सक्रिय अनुसंधान क्षेत्र था और इस विषय पर कुछ मूलभूत प्रश्न हाल ही में हल किए गए थे[2]आजकल, अधिकांश अनुप्रयोग समस्याओं को संसाधित करने के लिए एक बीजगणितीय विविधता को अप्रासंगिक घटकों में विघटित करना आवश्यक नहीं है, क्योंकि अपघटन की कमजोर धारणाएं, गणना करने के लिए कम खर्चीला,पर्याप्त हैं।

अभिलक्षण समुच्चय विधि रिट की प्रमेय के निम्न संस्करण पर निर्भर करती है।

प्रमेय वेन-त्सुन वू किसी परिमित बहुपद समुच्चय के लिए F ⊂ k[x1, ..., xn], कम त्रिकोणीय समुच्चय की गणना कर सकता है ऐसा है कि सभी बहुपद g में F छद्म-विभाजन w.r.t C द्वारा शून्य को कम कर देता है .

विभिन्न अवधारणाओं औरकलन विधि ने वेन-त्सुन वू के काम को आगे बढ़ाया। 1990 के दशक की प्रारंभ में, एक नियमित श्रृंखला की धारणा, स्वतंत्र रूप से 1991 में माइकल काल्कब्रेनर द्वारा अपनी पीएचडी थीसिस और लू यांग और जिंगझोंग झांग द्वारा प्रस्तुत की गई थी।[3] महत्वपूर्ण कलन विधि खोजों का नेतृत्व किया।

काल्कब्रेनर की दृष्टि में,[4] एक बीजगणितीय विविधता के अलघुकरणीय घटकों के सामान्य शून्य का प्रतिनिधित्व करने के लिए नियमित श्रृंखलाओं का उपयोग किया जाता है। यांग और झांग के मूल कार्य में, उनका उपयोग यह तय करने के लिए किया जाता है कि क्या एक हाइपरसफेस एक अर्ध-विविधता एक नियमित श्रृंखला को काटता है। नियमित शृंखलाओं में, वास्तव में, कई दिलचस्प गुण होते हैं और बीजगणितीय या अवकल समीकरणों की प्रणाली को विघटित करने के लिए कई कलन विधि में महत्वपूर्ण धारणा है।

कई पत्रों में नियमित जंजीरों की जांच की गई है।[5][6][7]इस विषय पर प्रचुर मात्रा में साहित्य को नियमित श्रृंखला की कई समकक्ष परिभाषाओं द्वारा समझाया जा सकता है। वास्तव मे काल्कब्रेनर का मूल सूत्रीकरण यांग और झांग से बिल्कुल अलग है। इन दो धारणाओं के बीच एक पुल, काल्कब्रेनर और यांग और झांग का दृष्टिकोण, डोंगमिंग वांग के पेपर में दिखाई देता है।[8]त्रिकोणीय अपघटन प्राप्त करने के लिए विभिन्न कलन विधि उपलब्ध हैं V(F) कालब्रेनर के अर्थ में और डेनियल लाजार्ड और वू वेनजुन वेन-त्सुन वू के अर्थ में डैनियल लाजार्ड द्वारा

लेक्सत्रिकोणीय कलन विधि[9] और ट्रायड कलन विधि मार्क मोरेनो माज़ा द्वारा[10] विशेषता समुच्चय विधि के साथ मिलकर विभिन्न कंप्यूटर बीजगणित प्रणालियों में उपलब्ध हैं, जिनमें स्वयंसिद्धऔर मेपल सॉफ्टवेयर सम्मिलित हैं।

औपचारिक परिभाषाएँ

मान लीजिए कि k एक क्षेत्र है और x1 <... < xn क्रमबद्ध चर हैं। हम संगत बहुपद वलय को R = k[x1, ..., xn] से निरूपित करते हैं। एफ ⊂ आर के लिए, बहुपद समीकरणों की एक प्रणाली के रूप में माना जाता है,k बीजगणितीय समापन पर त्रिकोणीय अपघटन के दो विचार हैं। कल्ब्रेनर के तथाकथित अर्थ में बीजगणितीय समुच्चय वी (एफ) के केवल सामान्य बिंदुओं का प्रतिनिधित्व करके, निरुद्योग रूप से विघटित करना पड़ता है।


दूसरा स्पष्ट रूप से सभी बिंदुओं का वर्णन करना है V(F) डैनियल लाजार्ड और वू वेनजुन वेन-सुन वू के तथाकथित अर्थ में।

दोनों ही स्थितियों में T1, ..., Te निश्चित रूप से कई नियमित श्रृंखलाएं हैं R और के संतृप्त आदर्श के मूलांक को दर्शाता है जबकि W(Ti) के अर्ध-घटक को दर्शाता है कृपया इन धारणाओं की परिभाषा के लिए नियमित श्रृंखला देखें।

अभी से मान लीजिए k एक वास्तविक बंद क्षेत्र है। विचार करना S बहुपदों के साथ एक अर्ध-बीजगणितीय प्रणाली R. वहां है[11] निश्चित रूप से कई नियमित अर्ध-बीजगणितीय प्रणालियाँ S1, ..., Se ऐसा कि हमारे पास है

जहाँ Zk(S) kn के उन बिंदुओं को दर्शाता है जो S को हल करते हैं। नियमित अर्ध-बीजगणितीय सिस्टम S1, ..., Se अर्ध-बीजीय प्रणाली S का त्रिकोणीय अपघटन बनाते हैं.

उदाहरण

निरूपित Q परिमेय संख्या क्षेत्र। में परिवर्तनीय क्रम के साथ , निम्नलिखित बहुपद प्रणाली पर विचार करें:

मेपल कोड के अनुसार:

के समाधान समुच्चय का एक संभावित त्रिकोणीय अपघटन S नियमित चेनलाइब्रेरी का उपयोग करने के साथ है:

ह भी देखें

  • वू की विशेषता समुच्चय की विधि
  • नियमित श्रृंखला
  • नियमित अर्ध-बीजगणितीय प्रणाली

संदर्भ

  1. ↑ Wu, W. T. (1987). A zero structure theorem for polynomial equations solving. MM Research Preprints, 1, 2–12
  2. ↑ A. M. Steel Conquering inseparability: Primary decomposition and multivariate factorization over algebraic function fields of positive characteristic
  3. ↑ Yang, L., Zhang, J. (1994). Searching dependency between algebraic equations: an algorithm applied to automated reasoning. Artificial Intelligence in Mathematics, pp. 14715, Oxford University Press.
  4. ↑ M. Kalkbrener: A Generalized Euclidean Algorithm for Computing Triangular Representations of Algebraic Varieties. J. Symb. Comput. 15(2): 143–167 (1993)
  5. ↑ S.C. Chou and X.S. Gao. On the dimension of an arbitrary ascending chain. Chinese Bull. of Sci., 38:799--804, 1991.
  6. ↑ Michael Kalkbrener. Algorithmic properties of polynomial rings. J. Symb. Comput.}, 26(5):525--581, 1998.
  7. ↑ P. Aubry, D. Lazard, M. Moreno Maza. On the theories of triangular sets. Journal of Symbolic Computation, 28(1–2):105–124, 1999.
  8. ↑ D. Wang. Computing Triangular Systems and Regular Systems. Journal of Symbolic Computation 30(2) (2000) 221–236
  9. ↑ D. Lazard, Solving zero-dimensional algebraic systems. Journal of Symbolic Computation 13, 1992
  10. ↑ M. Moreno Maza: On triangular decomposition of algebraic varieties. MEGA 2000 (2000).
  11. ↑ Changbo Chen, James H. Davenport, John P. May, Marc Moreno-Maza, Bican Xia, Rong Xiao. Triangular decomposition of semi-algebraic systems. Proceedings of 2010 International Symposium on Symbolic and Algebraic Computation (ISSAC 2010), ACM Press, pp. 187--194, 2010.
Retrieved from ‘https://www.vigyanwiki.in/index.php?title=त्रिकोणीय_अपघटन&oldid=113326’