बहुपद समीकरणों की प्रणाली

बहुपद समीकरणों की एक प्रणाली (कभी-कभी केवल कुछ बहुपद प्रणाली) के साथ समीकरणों का एक सेट $f 1 = 0, ..., f h = 0$ है जहां $f i$ कई चरों में बहुपद हैं, कहते हैं $x 1, ..., x n$ , कुछ क्षेत्रों $k$ में हैं।

बहुपद प्रणाली का एक समाधान मूल्यों का एक समूह $x i$ s है जो कुछ बीजगणितीय रूप से बंद फील्ड एक्सटेंशन $K$ का $k$ से संबंधित हैं, और सभी समीकरणों को सत्य बनाया जाता हैं। जहाँ $k$ परिमेय संख्याओं का क्षेत्र है, $K$ साधारणतयः जटिल संख्याओं का क्षेत्र माना जाता है, क्योंकि प्रत्येक समाधान के क्षेत्र विस्तार $k$ से संबंधित होता है, जो जटिल संख्याओं के उपक्षेत्रों के लिए समरूप होता है।

यह लेख हल करने की विधियों के बारे में है, अर्थात सभी समाधानों को खोजना या उनका वर्णन करना। चूंकि इन विधियों को एक कंप्यूटर में लागू करने के लिए डिज़ाइन किया गया है, इसलिए इन क्षेत्रों का $k$ पर जोर दिया जाता है जिसमें गणना (समानता परीक्षण सहित) आसान और कुशल है, यह परिमेय संख्याओं और परिमित क्षेत्रों का क्षेत्र हैं।

यहाँ विशिष्ट समूहों से संबंधित समाधानों की खोज करना एक ऐसी समस्या है जो साधारणतयः अधिक कठिन होती है, और इस आलेख के क्षेत्र से बाहर है, किसी दिए गए परिमित क्षेत्र में समाधान की स्थिति को छोड़कर, समाधान की ऐसी स्थिति के लिए जिसमें सभी घटक पूर्णांक या परिमेय संख्याएँ हैं, इसके लिए डायोफैंटाइन समीकरण देखें।

परिभाषा

बर्थ सेक्स्टिक के कई एकवचन बिंदु एक बहुपद प्रणाली के समाधान हैं

बहुपद समीकरणों की एक प्रणाली का एक सरल उदाहरण है

{\begin{aligned}x^{2}+y^{2}-5&=0\\xy-2&=0.\end{aligned}}

इसके हल चार जोड़े हैं $(x, y) = (1, 2), (2, 1), (-1, -2), (-2, -1)$ . इन समाधानों को सरल रूप से प्रतिस्थापन द्वारा जांचा जा सकता है, लेकिन यह अनुभूत करने के लिए और अधिक फंक्शन की आवश्यकता होती है जिसका इसके अतिरिक्त कोई अन्य समाधान नहीं है।

इस लेख का विषय ऐसे उदाहरणों के सामान्यीकरण का अध्ययन करना और समाधानों की गणना करना है जिसके लिए उपयोग की जाने वाली विधियों का वर्णन सुवर्णित किया जा सके।

बहुपद समीकरणों की एक प्रणाली, या बहुपद प्रणाली समीकरणों का एक संग्रह है

{\begin{aligned}f_{1}\left(x_{1},\ldots ,x_{m}\right)&=0\\&\;\;\vdots \\f_{n}\left(x_{1},\ldots ,x_{m}\right)&=0,\end{aligned}}

जहाँ प्रत्येक $f h$ अनिश्चित (चर) में एक बहुपद है $x 1, ..., x m$ , पूर्णांक गुणांक के साथ, या कुछ निश्चित क्षेत्र (गणित) में गुणांक, अधिकांशतः परिमेय संख्याओं का क्षेत्र या एक परिमित क्षेत्र।^[1] गुणांक के अन्य क्षेत्रों, जैसे कि वास्तविक संख्या, का प्रायः कम उपयोग किया जाता है, क्योंकि उनके तत्वों को एक कंप्यूटर में प्रदर्शित नहीं किया जा सकता है (गणना में केवल वास्तविक संख्याओं के सन्निकटन का उपयोग किया जा सकता है, और ये सन्निकटन हमेशा परिमेय संख्या होते हैं)।

एक बहुपद प्रणाली का एक समाधान के मूल्यों का टपल है $(x 1, ..., x m)$ जो बहुपद प्रणाली के सभी समीकरणों को संतुष्ट करता है। समाधान सम्मिश्र संख्याओं में खोजे जाते हैं, या अधिक सामान्य रूप से गुणांक वाले बीजगणितीय रूप से बंद क्षेत्र में। विशेष रूप से, विशेषतयः शून्य स्थिति में, सभी सम्मिश्र संख्या समाधानों का अन्वेषण किया जाता है। वास्तविक संख्या या परिमेय संख्या समाधानों की खोज अधिक कठिन समस्याएँ हैं जिन पर इस लेख में विचार नहीं किया गया है।

समाधानों का समुच्चय हमेशा परिमित नहीं होता है; उदाहरण के लिए, सिस्टम के समाधान

{\begin{aligned}x(x-1)&=0\\x(y-1)&=0\end{aligned}}

एक बिन्दु हैं $(x, y) = (1,1)$ और एक पंक्ति $x = 0$ .^[2] यहां तक कि जब समाधान समूह परिमित है, सामान्य रूप से, समाधान की कोई बंद-रूप अभिव्यक्ति नहीं है (एक समीकरण की स्थिति में, यह एबेल-रफिनी प्रमेय है)।

बार्थ सतह के चित्र में दिखाया गया है कि एक बहुपद प्रणाली के समाधान का ज्यामितीय प्रतिनिधित्व कैसे होता है जो कि 3 चरों में डिग्री 6 के एकल समीकरण में घटता है। बीजगणितीय विविधता के कई विलक्षण बिंदुओं में कुछ प्रतिबिम्ब यहाँ पर दिखाई दे रहे हैं। इन 3 चरों में डिग्री 5 के 4 समीकरणों की प्रणाली के लिए एक समाधान हैं। ऐसी अतिनिर्धारित प्रणाली का सामान्य रूप से कोई समाधान नहीं है (अर्थात यदि गुणांक विशिष्ट नहीं हैं)। यदि इसके हलों की संख्या परिमित है, तो यह संख्या अधिक से अधिक होती है जैसे $53 = 125$ (बेज़ाउट के प्रमेय द्वारा)। चूंकि, यह दिखाया गया है कि, डिग्री 6 की सतह के किसी एक बिंदु की स्थिति में प्राप्त समाधान की अधिकतम संख्या 65 होती है, और यह इसके बर्थ सतह तक पहुंच जाती है।

मूल गुण और परिभाषाएँ

एक प्रणाली अतिनिर्धारित प्रणाली है यदि समीकरणों की संख्या चर की संख्या से अधिक है। एक प्रणाली असंगत समीकरण है यदि इसका कोई जटिल संख्या समाधान नहीं है (या, यदि गुणांक जटिल संख्या नहीं हैं, बीजगणितीय रूप से बंद क्षेत्र में गुणांक वाले कोई समाधान नहीं है)। हिल्बर्ट के नलस्टेलनसैट्ज़ द्वारा इसका अर्थ है कि 1 समीकरण के पहले सदस्यों के गुणांक के रूप में बहुपदों के साथ एक रैखिक संयोजन होता है। अधिकांशतः लेकिन सभी अनिर्धारित प्रणालियाँ नहीं होती हैं, यादृच्छिक गुणांक के साथ निर्मित होने पर यह असंगत होते हैं। उदाहरण के लिए, सिस्टम $x 3 - 1 = 0, x 2 - 1 = 0$ अतिनिर्धारित है (दो समीकरण हैं लेकिन केवल एक अज्ञात है), लेकिन यह असंगत नहीं है क्योंकि इसका हल $x = 1$ है।

यदि समीकरणों की संख्या वैरिएबल्स की संख्या से कम हो तो यह प्रणाली अनिर्धारित प्रणाली होगी। एक कम निर्धारित प्रणाली या तो असंगत होगी या इसके बहुत अधिक रूप हो सकते हैं इस प्रकार इसके कई जटिल समाधान होंगे (यह वे बीजगणितीय रूप से बंद क्षेत्र में समाधान हैं जिसमें समीकरणों के गुणांक सम्मलित होते हैं)। यह क्रमविनिमेय बीजगणित का एक गैर तुच्छ परिणाम है जिसमें विशेष रूप से हिल्बर्ट का नलस्टेलेंसैट्ज और क्रुल का प्रमुख आदर्श प्रमेय सम्मलित हैं।

एक प्रणाली शून्य-आयामी स्थान है | शून्य-आयामी है यदि इसमें जटिल समाधानों की एक सीमित संख्या है (या बीजगणितीय रूप से बंद क्षेत्र में समाधान)। यह शब्दावली इस तथ्य से आती है कि समाधानों की बीजगणितीय विविधता में बीजगणितीय विविधता शून्य का आयाम है। असीम रूप से कई समाधानों वाली प्रणाली को सकारात्मक-आयामी कहा जाता है।

वैरिएबल के रूप में कई समीकरणों वाली एक शून्य-आयामी प्रणाली कभी-कभी अच्छी तरह से व्यवहार करती हैं।^[3] बेज़ाउट की प्रमेय के अनुसार एक अच्छी तरह से व्यवहार करने वाली प्रणाली जिनके समीकरणों की डिग्री $d 1, ..., d n$ में अधिक से अधिक $d 1 \cdot\cdot\cdot d n$ समाधान हैं। यह सीमा तीक्ष्ण है। यदि सभी डिग्रियां $d$ के बराबर हैं, यह सीमा $d n$ बन जाती है और वैरिएबल्स की संख्या में चरघातांकी होती है। (बीजगणित का मौलिक प्रमेय विशेष स्थिति में $n = 1$ होता है।)

यह घातीय व्यवहार बहुपद प्रणालियों को हल करने के लिए कठिन बनाता है और यह बताता है कि क्यों कुछ सॉल्वर बेज़ाउट की सीमा से अधिक स्वचालित रूप से इस प्रणाली को हल करने में सक्षम होते हैं, यहाँ जानने वाली बात यह हैं कि 25 (डिग्री 3 के तीन समीकरण या डिग्री 2 के पांच समीकरण इस सीमा से व्याप्त हैं)।^{[citation needed]}

क्या सुलझा रहा है?

बहुपद प्रणाली को हल करने के लिए पहली बात यह तय करना है कि यह असंगत, शून्य-आयामी या सकारात्मक आयामी है या नहीं। यह समीकरणों के बाएं हाथ के पक्ष के ग्रोबनेर आधार की गणना के द्वारा किया जा सकता है। सिस्टम असंगत है अगर यह ग्रोबनर आधार 1 तक कम हो जाता है। सिस्टम शून्य-आयामी है, यदि प्रत्येक चर के लिए ग्रोबनर आधार के कुछ तत्व का ग्रोबनर आधार है जो इस चर की शुद्ध शक्ति है। इस परीक्षण के लिए, सबसे अच्छा मोनोमियल ऑर्डर (जो आमतौर पर सबसे तेज़ गणना की ओर जाता है) आमतौर पर मोनोमियल ऑर्डर # ग्रेडेड रिवर्स लेक्सिकोग्राफ़िक ऑर्डर वन (ग्रेव्लेक्स) होता है।

यदि तंत्र धनात्मक विमीय है, तो इसके अपरिमित रूप से अनेक हल हैं। ऐसे में उनकी गिनती करना संभव नहीं है। यह इस प्रकार है कि, इस मामले में, हल करने का अर्थ केवल उन समाधानों का विवरण खोजना हो सकता है जिनसे समाधान के प्रासंगिक गुणों को निकालना आसान हो। ऐसा कोई सामान्य रूप से स्वीकृत विवरण नहीं है। वास्तव में कई अलग-अलग प्रासंगिक गुण हैं, जिनमें बीजगणितीय ज्यामिति के लगभग हर उपक्षेत्र शामिल हैं।

सकारात्मक-आयामी प्रणालियों से संबंधित ऐसे प्रश्न का एक स्वाभाविक उदाहरण निम्नलिखित है: यह तय करें कि क्या परिमेय संख्याओं पर एक बहुपद प्रणाली के पास वास्तविक समाधानों की एक सीमित संख्या है और उनकी गणना करें। इस प्रश्न का एक सामान्यीकरण एक बहुपद प्रणाली के वास्तविक समाधान के सेट के प्रत्येक जुड़े घटक (टोपोलॉजी) में कम से कम एक समाधान ढूंढता है। इन प्रश्नों को हल करने के लिए शास्त्रीय एल्गोरिथ्म बेलनाकार बीजगणितीय अपघटन है, जिसमें एक दोहरा घातीय कार्य कम्प्यूटेशनल जटिलता है और इसलिए बहुत छोटे उदाहरणों को छोड़कर व्यवहार में इसका उपयोग नहीं किया जा सकता है।

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

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

एक्सटेंशन

त्रिकोणमितीय समीकरण

त्रिकोणमितीय समीकरण एक समीकरण है $g = 0$ कहाँ पे $g$ एक त्रिकोणमितीय बहुपद है। इस तरह के एक समीकरण को इसमें ज्या और कोज्या का विस्तार करके (त्रिकोणमितीय कार्यों # योग और अंतर सूत्रों का उपयोग करके), एक बहुपद प्रणाली में परिवर्तित किया जा सकता है $sin(x)$ तथा $cos(x)$ दो नए चर द्वारा $s$ तथा $c$ और नया समीकरण जोड़ना $s 2 + c 2 - 1 = 0$ .

उदाहरण के लिए, पहचान के कारण

\cos(3x)=4\cos ^{3}(x)-3\cos(x),

समीकरण को हल करना

\sin ^{3}(x)+\cos(3x)=0

बहुपद प्रणाली को हल करने के बराबर है

{\begin{cases}s^{3}+4c^{3}-3c&=0\\s^{2}+c^{2}-1&=0.\end{cases}}

प्रत्येक समाधान के लिए $(c 0, s 0)$ इस प्रणाली का एक अनूठा समाधान है $x$ समीकरण का ऐसा है $0 \leq x < 2 π$ .

इस सरल उदाहरण के मामले में, यह स्पष्ट नहीं हो सकता है कि समीकरण की तुलना में प्रणाली को हल करना आसान है या नहीं। अधिक जटिल उदाहरणों पर, सीधे समीकरण को हल करने के लिए व्यवस्थित तरीकों का अभाव है, जबकि संबंधित सिस्टम को स्वचालित रूप से हल करने के लिए सॉफ़्टवेयर उपलब्ध हैं।

परिमित क्षेत्र में समाधान

एक परिमित क्षेत्र पर एक प्रणाली को हल करते समय $k$ साथ $q$ तत्व, मुख्य रूप से समाधान में रुचि रखते हैं $k$ . के तत्वों के रूप में $k$ समीकरण के सटीक हल हैं $x q - x = 0$ , यह समाधान को प्रतिबंधित करने के लिए पर्याप्त है $k$ , समीकरण जोड़ने के लिए $x i q - x i = 0$ प्रत्येक चर के लिए $x i$ .

=== संख्या क्षेत्र में गुणांक या गैर-प्रमुख क्रम === के साथ परिमित क्षेत्र में

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

उदाहरण के लिए, यदि किसी सिस्टम में शामिल है ${\sqrt {2}}$ परिमेय संख्याओं पर एक प्रणाली समीकरण को जोड़कर प्राप्त की जाती है $r 22 - 2 = 0$ और बदल रहा है ${\sqrt {2}}$ द्वारा $r 2$ अन्य समीकरणों में

परिमित क्षेत्र के मामले में, वही परिवर्तन हमेशा उस क्षेत्र को मानने की अनुमति देता है $k$ एक प्रमुख आदेश है।

समाधान का बीजगणितीय प्रतिनिधित्व

नियमित चेन

समाधानों का प्रतिनिधित्व करने का सामान्य तरीका शून्य-आयामी नियमित श्रृंखलाओं के माध्यम से होता है। ऐसी श्रृंखला में बहुपदों का एक क्रम होता है $f 1 (x 1)$ , $f 2 (x 1, x 2)$ , ..., $f n (x 1, ..., x n)$ ऐसा है कि, हर के लिए $i$ ऐसा है कि $1 \leq i \leq n$

$f i$ में बहुपद है $x 1, ..., x i$ केवल, जिसके पास डिग्री है $d i > 0$ में $x i$ ;
का गुणांक $x i d i$ में $f i$ में बहुपद है $x 1, ..., x i -1$ जिसका कोई उभयनिष्ठ शून्य नहीं है $f 1$ , ..., $f i - 1$ .

समीकरणों की एक त्रिकोणीय प्रणाली ऐसी नियमित श्रृंखला से जुड़ी होती है

{\begin{cases}f_{1}(x_{1})=0\\f_{2}(x_{1},x_{2})=0\\\quad \vdots \\f_{n}(x_{1},x_{2},\ldots ,x_{n})=0.\end{cases}}

इस प्रणाली के समाधान पहले एकविभाजित समीकरण को हल करके, अन्य समीकरणों में समाधानों को प्रतिस्थापित करके, फिर दूसरे समीकरण को हल करके प्राप्त किया जाता है जो अब अविभाजित है, और इसी तरह। नियमित जंजीरों की परिभाषा का अर्थ है कि एकतरफा समीकरण से प्राप्त किया गया $f i$ डिग्री है $d i$ और इस प्रकार सिस्टम के पास है $d 1 ... d n$ समाधान, बशर्ते कि इस संकल्प प्रक्रिया (बीजगणित के मौलिक प्रमेय) में कोई भी मूल न हो।

बहुपद समीकरणों की प्रत्येक शून्य-आयामी प्रणाली नियमित श्रृंखलाओं की सीमित संख्या के समतुल्य है (अर्थात समान समाधान हैं)। कई नियमित श्रृंखलाओं की आवश्यकता हो सकती है, क्योंकि यह निम्न प्रणाली का मामला है जिसमें तीन समाधान हैं।

{\begin{cases}x^{2}-1=0\\(x-1)(y-1)=0\\y^{2}-1=0.\end{cases}}

एक मनमाना बहुपद प्रणाली के त्रिकोणीय अपघटन की गणना के लिए कई एल्गोरिदम हैं (जरूरी नहीं कि शून्य-आयामी)^[4] नियमित शृंखलाओं में (या नियमित अर्ध-बीजगणितीय प्रणालियाँ)।

एक एल्गोरिथ्म भी है जो शून्य-आयामी मामले के लिए विशिष्ट है और प्रतिस्पर्धी है, इस मामले में, प्रत्यक्ष एल्गोरिदम के साथ। इसमें मोनोमियल ऑर्डर के लिए पहले ग्रोबनेर आधार की गणना करना शामिल है। ग्रेडेड रिवर्स लेक्सिकोग्राफ़िक ऑर्डर (ग्रेव्लेक्स), फिर एफजीएलएम एल्गोरिथम द्वारा लेक्सिकोग्राफ़िकल ग्रोबनर आधार को कम करना^[5] और अंत में लेक्स्ट्रियांगुलर एल्गोरिथ्म को लागू करना।^[6] परिमित क्षेत्र में गुणांकों के लिए समाधान का यह प्रतिनिधित्व पूरी तरह से सुविधाजनक है। हालाँकि, तर्कसंगत गुणांक के लिए, दो पहलुओं का ध्यान रखना होगा:

आउटपुट में विशाल पूर्णांक शामिल हो सकते हैं जो गणना और परिणाम के उपयोग को समस्याग्रस्त बना सकते हैं।
आउटपुट से समाधान के संख्यात्मक मूल्यों को निकालने के लिए, किसी को एकतरफा बहुपदों को अनुमानित गुणांक के साथ हल करना होगा, जो एक अत्यधिक अस्थिर समस्या है।

दहन और शोस्ट द्वारा पहला मुद्दा हल किया गया है:^[7]^[8] समाधान के दिए गए सेट का प्रतिनिधित्व करने वाले नियमित श्रृंखलाओं के सेट में, एक ऐसा सेट होता है जिसके लिए गुणांक लगभग इष्टतम सीमा के साथ इनपुट सिस्टम के आकार के संदर्भ में स्पष्ट रूप से बंधे होते हैं। यह सेट, जिसे इक्विप्रोजेक्टेबल अपघटन कहा जाता है, केवल निर्देशांक की पसंद पर निर्भर करता है। यह मॉड्यूलर अंकगणित के उपयोग की अनुमति देता है ताकि कुशल रूप से गणना योग्य अपघटन की गणना की जा सके।^[9] दूसरा मुद्दा आम तौर पर एक विशेष रूप की नियमित श्रृंखलाओं को आउटपुट करके हल किया जाता है, जिसे कभी-कभी आकार लेम्मा कहा जाता है, जिसके लिए सभी $d i$ लेकिन पहले वाले के बराबर हैं $1$ . ऐसी नियमित शृंखला प्राप्त करने के लिए, एक और चर जोड़ना पड़ सकता है, जिसे अलग करने वाला चर कहा जाता है, जिसे सूचकांक दिया जाता है $0$ . नीचे वर्णित तर्कसंगत अविभाज्य प्रतिनिधित्व, ऐसी विशेष नियमित श्रृंखला की गणना करने की अनुमति देता है, जो एक नियमित श्रृंखला या ग्रोबनेर आधार से शुरू करके दहन-शोस्ट बाध्य को संतुष्ट करता है।

तर्कसंगत अविभाज्य प्रतिनिधित्व

परिमेय अविभाज्य प्रतिनिधित्व या RUR परिमेय संख्याओं पर एक शून्य-आयामी बहुपद प्रणाली के समाधान का प्रतिनिधित्व है जिसे F. Roillier द्वारा पेश किया गया है।^[10] एक शून्य-आयामी प्रणाली का एक आरयूआर एक रैखिक संयोजन में होता है $x 0$ चरों का, पृथक करने वाला चर कहा जाता है, और समीकरणों की एक प्रणाली^[11]

{\begin{cases}h(x_{0})=0\\x_{1}=g_{1}(x_{0})/g_{0}(x_{0})\\\quad \vdots \\x_{n}=g_{n}(x_{0})/g_{0}(x_{0}),\end{cases}}

कहाँ पे $h$ में एक अविभाज्य बहुपद है $x 0$ डिग्री का $D$ तथा $g 0, ..., g n$ में अविभाज्य बहुपद हैं $x 0$ डिग्री से कम $D$ .

परिमेय संख्याओं पर शून्य-आयामी बहुपद प्रणाली को देखते हुए, RUR में निम्नलिखित गुण हैं।

चरों के परिमित संख्या रैखिक संयोजनों को छोड़कर सभी चरों को अलग कर रहे हैं।
जब अलग करने वाला चर चुना जाता है, तो RUR मौजूद होता है और अद्वितीय होता है। विशेष रूप से $h$ और यह $g i$ उनकी गणना करने के लिए किसी भी एल्गोरिदम से स्वतंत्र रूप से परिभाषित किया गया है।
प्रणाली के समाधान की जड़ों के साथ एक-से-एक पत्राचार में हैं $h$ और प्रत्येक जड़ की बहुलता (गणित)। $h$ संबंधित समाधान की बहुलता के बराबर है।
प्रणाली के समाधान की जड़ों को प्रतिस्थापित करके प्राप्त किया जाता है $h$ अन्य समीकरणों में
यदि $h$ तब कोई बहुमूल नहीं है $g 0$ का औपचारिक व्युत्पन्न है $h$ .

उदाहरण के लिए, पिछले अनुभाग में प्रणाली के लिए, के गुणकों को छोड़कर, चर का प्रत्येक रैखिक संयोजन $x$ , $y$ तथा $x + y$ , एक अलग करने वाला चर है। अगर कोई चुनता है $t = .mw-parser-output .sfrac{white-space:nowrap}.mw-parser-output .sfrac.tion,.mw-parser-output .sfrac .tion{display:inline-block;vertical-align:-0.5em;font-size:85%;text-align:center}.mw-parser-output .sfrac .num,.mw-parser-output .sfrac .den{display:block;line-height:1em;margin:0 0.1em}.mw-parser-output .sfrac .den{border-top:1px solid}.mw-parser-output .sr-only{border:0;clip:rect(0,0,0,0);height:1px;margin:-1px;overflow:hidden;padding:0;position:absolute;width:1px}x – y/2$ एक विभाजक चर के रूप में, तो RUR है

{\begin{cases}t^{3}-t=0\\x={\frac {t^{2}+2t-1}{3t^{2}-1}}\\y={\frac {t^{2}-2t-1}{3t^{2}-1}}.\\\end{cases}}

आरयूआर विशिष्ट रूप से किसी भी एल्गोरिदम से स्वतंत्र रूप से दिए गए अलग-अलग चर के लिए परिभाषित किया गया है, और यह जड़ों की बहुलताओं को संरक्षित करता है। यह त्रिकोणीय अपघटन (यहां तक कि समरूप अपघटन) के साथ एक उल्लेखनीय अंतर है, जो सामान्य रूप से बहुलताओं को संरक्षित नहीं करता है। आरयूआर अपेक्षाकृत छोटे आकार के गुणांक के साथ एक आउटपुट का उत्पादन करने की संपत्ति को समान रूप से अपघटन के साथ साझा करता है।

शून्य-आयामी प्रणालियों के लिए, आरयूआर एकल अविभाजित बहुपद को हल करके और उन्हें तर्कसंगत कार्यों में प्रतिस्थापित करके समाधान के संख्यात्मक मूल्यों की पुनर्प्राप्ति की अनुमति देता है। यह किसी भी सटीकता के समाधान के प्रमाणित सन्निकटन के उत्पादन की अनुमति देता है।

इसके अलावा, अविभाज्य बहुपद $h (x 0)$ RUR का गुणनखंड किया जा सकता है, और यह प्रत्येक अप्रासंगिक कारक के लिए एक RUR देता है। यह दिए गए आदर्श का प्रमुख अपघटन प्रदान करता है (जो कि आदर्श के एक आदर्श के कट्टरपंथी का प्राथमिक अपघटन है)। व्यवहार में, यह बहुत छोटे गुणांकों के साथ एक आउटपुट प्रदान करता है, विशेष रूप से उच्च बहुलता वाले सिस्टम के मामले में।

त्रिकोणीय अपघटन और समान प्रक्षेपण योग्य अपघटन के विपरीत, आरयूआर को सकारात्मक आयाम में परिभाषित नहीं किया गया है।

संख्यात्मक रूप से हल करना

सामान्य समाधान एल्गोरिदम

सामान्य संख्यात्मक एल्गोरिदम जो गैर-रैखिक समीकरणों की किसी भी प्रणाली के लिए डिज़ाइन किए गए हैं, बहुपद प्रणालियों के लिए भी काम करते हैं। हालाँकि, विशिष्ट तरीकों को आम तौर पर प्राथमिकता दी जाएगी, क्योंकि सामान्य तरीके आम तौर पर किसी को सभी समाधान खोजने की अनुमति नहीं देते हैं। विशेष रूप से, जब एक सामान्य विधि कोई समाधान नहीं ढूंढ पाती है, तो यह आमतौर पर कोई संकेत नहीं होता है कि कोई समाधान नहीं है।

फिर भी, यहाँ दो विधियों का उल्लेख किया जाना आवश्यक है।

न्यूटन की विधि का उपयोग तब किया जा सकता है जब समीकरणों की संख्या चरों की संख्या के बराबर हो। यह किसी को सभी समाधान खोजने की अनुमति नहीं देता है और न ही यह साबित करने की अनुमति देता है कि कोई समाधान नहीं है। लेकिन यह बहुत तेज है जब एक बिंदु से शुरू होता है जो एक समाधान के करीब है। इसलिए, यह नीचे वर्णित होमोटॉपी निरंतरता विधि के लिए एक बुनियादी उपकरण है।
अनुकूलन (गणित) का उपयोग शायद ही कभी बहुपद प्रणालियों को हल करने के लिए किया जाता है, लेकिन यह 1970 के लगभग सफल रहा, यह दिखाने में कि 56 चरों में 81 द्विघात समीकरणों की प्रणाली असंगत नहीं है।^[12] अन्य ज्ञात तरीकों के साथ, यह आधुनिक तकनीक की संभावनाओं से परे है, as of 2022^[update]. इस पद्धति में केवल समीकरणों के वर्गों के योग को कम करना शामिल है। यदि शून्य स्थानीय न्यूनतम के रूप में पाया जाता है, तो इसे एक समाधान पर प्राप्त किया जाता है। यह विधि अतिनिर्धारित प्रणालियों के लिए काम करती है, लेकिन यदि सभी स्थानीय न्यूनतम पाए जाते हैं जो सकारात्मक हैं तो एक खाली जानकारी का उत्पादन होता है।

होमोटॉपी निरंतरता विधि

यह एक अर्ध-संख्यात्मक विधि है जो मानती है कि समीकरणों की संख्या चरों की संख्या के बराबर है। यह तरीका अपेक्षाकृत पुराना है लेकिन पिछले दशकों में इसमें नाटकीय रूप से सुधार हुआ है।^[13] यह विधि तीन चरणों में विभाजित होती है। सबसे पहले समाधानों की संख्या पर ऊपरी सीमा की गणना की जाती है। यह बाउंड जितना संभव हो उतना तेज होना चाहिए। इसलिए, इसकी गणना, कम से कम, चार अलग-अलग तरीकों और सर्वोत्तम मान, कहते हैं, द्वारा की जाती है $N$ , रखा गया है।

दूसरे चरण में, एक system $g_{1}=0,\,\ldots ,\,g_{n}=0$ बहुपद समीकरणों की संख्या उत्पन्न होती है जो वास्तव में होती है $N$ गणना करने में आसान समाधान। इस नई प्रणाली में एक ही नंबर है $n$ चर और समान संख्या का $n$ समीकरणों और समान सामान्य संरचना को हल करने के लिए प्रणाली के रूप में, $f_{1}=0,\,\ldots ,\,f_{n}=0$ .

फिर दो प्रणालियों के बीच एक समरूपता पर विचार किया जाता है। इसमें, उदाहरण के लिए, दो प्रणालियों के बीच सीधी रेखा शामिल है, लेकिन अन्य रास्तों पर विचार किया जा सकता है, विशेष रूप से सिस्टम में कुछ विलक्षणताओं से बचने के लिए

(1-t)g_{1}+tf_{1}=0,\,\ldots ,\,(1-t)g_{n}+tf_{n}=0

.

होमोटॉपी निरंतरता में पैरामीटर को विकृत करना शामिल है $t$ 0 से 1 तक और उसके बाद $N$ इस विरूपण के दौरान समाधान। यह के लिए वांछित समाधान देता है $t=1$ . अनुसरण का अर्थ है कि, यदि $t_{1}<t_{2}$ , के लिए समाधान $t=t_{2}$ के हल से निकाले गए हैं $t=t_{1}$ न्यूटन की विधि द्वारा। यहां कठिनाई का मूल्य अच्छी तरह से चुनना है $t_{2}-t_{1}:$ बहुत बड़ा, न्यूटन का अभिसरण धीमा हो सकता है और यहां तक कि एक समाधान पथ से दूसरे पर कूद सकता है। बहुत छोटा, और चरणों की संख्या विधि को धीमा कर देती है।

तर्कसंगत अविभाज्य प्रतिनिधित्व से संख्यात्मक रूप से हल करना

आरयूआर से समाधान के संख्यात्मक मूल्यों को निकालना आसान लगता है: यह एकतरफा बहुपद की जड़ों की गणना करने और उन्हें अन्य समीकरणों में प्रतिस्थापित करने के लिए पर्याप्त है। यह इतना आसान नहीं है क्योंकि एक बहुपद का मूल्यांकन दूसरे बहुपद के मूल में अत्यधिक अस्थिर होता है।

इस प्रकार अविभाज्य बहुपद के मूलों की गणना एक उच्च परिशुद्धि से की जानी चाहिए जिसे हमेशा के लिए परिभाषित नहीं किया जा सकता है। दो एल्गोरिदम हैं जो इस आवश्यकता को पूरा करते हैं।

MPSolve में लागू एबर्थ विधि, सभी जटिल जड़ों की किसी भी सटीकता से गणना करती है।
कोलिन्स और अक्रितास का उसपेन्स्की का एल्गोरिथम,^[14] राउलियर और ज़िम्मरमैन द्वारा सुधार किया गया ^[15] और डेसकार्टेस के संकेतों के नियम पर आधारित है। यह एल्गोरिदम मनमाना छोटी चौड़ाई के अंतराल में पृथक वास्तविक जड़ों की गणना करता है। इसे मेपल (सॉफ्टवेयर) (फ़ंक्शंस fsolve और रूटफाइंडिंग [आइसोलेट]) में लागू किया गया है।

सॉफ्टवेयर पैकेज

कम से कम चार सॉफ़्टवेयर पैकेज हैं जो स्वचालित रूप से शून्य-आयामी सिस्टम को हल कर सकते हैं (स्वचालित रूप से, एक का अर्थ है कि इनपुट और आउटपुट के बीच कोई मानव हस्तक्षेप की आवश्यकता नहीं है, और इस प्रकार उपयोगकर्ता द्वारा विधि का कोई ज्ञान आवश्यक नहीं है)। कई अन्य सॉफ़्टवेयर पैकेज भी हैं जो शून्य-आयामी सिस्टम को हल करने के लिए उपयोगी हो सकते हैं। उनमें से कुछ स्वचालित सॉल्वर के बाद सूचीबद्ध हैं।

मेपल (सॉफ्टवेयर) फ़ंक्शन रूटफाइंडिंग [आइसोलेट] परिमेय संख्याओं पर किसी भी बहुपद प्रणाली को इनपुट के रूप में लेता है (यदि कुछ गुणांक तैरनेवाला स्थल नंबर हैं, तो वे परिमेय संख्याओं में परिवर्तित हो जाते हैं) और तर्कसंगत के अंतराल के रूप में या तो (वैकल्पिक रूप से) प्रतिनिधित्व किए गए वास्तविक समाधानों को आउटपुट करता है संख्या या मनमाना परिशुद्धता के चल बिंदु सन्निकटन के रूप में। यदि सिस्टम शून्य आयामी नहीं है, तो इसे एक त्रुटि के रूप में संकेतित किया जाता है।

आंतरिक रूप से, F. Rouillier द्वारा डिज़ाइन किया गया यह सॉल्वर पहले एक ग्रोबनर आधार और फिर एक तर्कसंगत अविभाज्य प्रतिनिधित्व की गणना करता है जिससे समाधान के आवश्यक सन्निकटन का अनुमान लगाया जाता है। यह कुछ सौ जटिल समाधानों वाले सिस्टम के लिए नियमित रूप से काम करता है।

तर्कसंगत अविभाज्य प्रतिनिधित्व की गणना मेपल (सॉफ्टवेयर) फ़ंक्शन ग्रोबनेर [रेशनल यूनीवेरिएट रिप्रेजेंटेशन] के साथ की जा सकती है।

तर्कसंगत अविभाज्य प्रतिनिधित्व से सभी जटिल समाधानों को निकालने के लिए, कोई MPSolve का उपयोग कर सकता है, जो किसी भी सटीकता के लिए अविभाजित बहुपदों की जटिल जड़ों की गणना करता है। MPSolve को कई बार चलाने की सिफारिश की जाती है, हर बार सटीकता को दोगुना करते हुए, जब तक कि समाधान स्थिर न रहें, क्योंकि इनपुट चर के समीकरणों में जड़ों का प्रतिस्थापन अत्यधिक अस्थिर हो सकता है।

दूसरा सॉल्वर PHCpack है,^[13]^[16] जे वर्शेल्डे के निर्देशन में लिखा गया। PHCpack होमोटॉपी निरंतरता विधि को लागू करता है। यह सॉल्वर चर के रूप में कई समीकरणों वाले बहुपद प्रणालियों के पृथक जटिल समाधानों की गणना करता है।

तीसरा सॉल्वर बर्टिनी है,^[17]^[18] डी. जे. बेट्स, जे. डी. हाउंस्टीन, ए. जे. सोम्मीस, और सी. डब्ल्यू. वामप्लर द्वारा लिखित। बर्टिनी अनुकूली परिशुद्धता के साथ संख्यात्मक समरूपता निरंतरता का उपयोग करता है। शून्य-आयामी समाधान सेटों की गणना के अलावा, PHCpack और बर्टिनी दोनों सकारात्मक आयामी समाधान सेटों के साथ काम करने में सक्षम हैं।

चौथा सॉल्वर मेपल (सॉफ्टवेयर) लाइब्रेरी रेग्युलर चेन्स है, जिसे मार्क मोरेनो-माजा और सहयोगियों द्वारा लिखा गया है। इसमें नियमित शृंखलाओं के माध्यम से बहुपद प्रणालियों को हल करने के लिए विभिन्न कार्य शामिल हैं।

यह भी देखें

उन्मूलन सिद्धांत
बहुपद असमानताओं की प्रणाली
त्रिकोणीय अपघटन
वू की विशेषता सेट की विधि

संदर्भ

↑ Bates et al. 2013, p. 4
↑ Bates et al. 2013, p. 8
↑ Songxin Liang, J. Gerhard, D.J. Jeffrey, G. Moroz, A Package for Solving Parametric Polynomial Systems. Communications in Computer Algebra (2009)
↑ Aubry, P.; Maza, M. Moreno (1999). "बहुपद प्रणालियों को हल करने के लिए त्रिकोणीय सेट: चार विधियों का तुलनात्मक कार्यान्वयन". J. Symb. Comput. 28 (1–2): 125–154. doi:10.1006/jsco.1999.0270.
↑ Faugère, J.C.; Gianni, P.; Lazard, D.; Mora, T. (1993). "आदेश में परिवर्तन द्वारा शून्य-आयामी ग्रोबनेर आधार की कुशल संगणना". Journal of Symbolic Computation. 16 (4): 329–344. doi:10.1006/jsco.1993.1051.
↑ Lazard, D. (1992). "शून्य आयामी बीजगणितीय प्रणालियों को हल करना". Journal of Symbolic Computation. 13 (2): 117–131. doi:10.1016/S0747-7171(08)80086-7.
↑ Xavier Dahan and Eric Schost. Sharp Estimates for Triangular Sets. Moreover, recent algorithms for decomposing polynomial systems into triangular decompositions produce regular chains with coefficients matching the results of Dahan and Schost. In proc. ISSAC'04, pages 103--110, ACM Press, 2004
↑ Dahan, Xavier; Moreno Maza, Marc; Schost, Eric; Wu, Wenyuan; Xie, Yuzhen (2005). "Lifting techniques for triangular decompositions" (PDF). Proceedings of ISAAC 2005. ACM Press. pp. 108–105.
↑ Changbo Chen and Marc Moreno-Maza. Algorithms for Computing Triangular Decomposition of Polynomial Systems.In proc. ISSAC'2011, pages 83-90, ACM Press, 2011 and Journal of Symbolic Computation (to appear)
↑ Rouillier, Fabrice (1999). "Solving Zero-Dimensional Systems Through the Rational Univariate Representation". Appl. Algebra Eng. Commun. Comput. 9 (9): 433–461. doi:10.1007/s002000050114. S2CID 25579305.
↑ Saugata Basu; Richard Pollack; Marie-Françoise Roy (2006). वास्तविक बीजगणितीय ज्यामिति में एल्गोरिदम, अध्याय 12.4. Springer-Verlag.
↑ Lazard, Daniel (2009). "बहुपद प्रणाली के समाधान के तीस साल, और अब?". J. Symb. Comput. 44 (3): 2009. doi:10.1016/j.jsc.2008.03.004.
↑ ^13.0 ^13.1 Verschelde, Jan (1999). "एल्गोरिथम 795: PHCpack: होमोटॉपी निरंतरता द्वारा बहुपद प्रणालियों के लिए एक सामान्य-उद्देश्य सॉल्वर" (PDF). ACM Transactions on Mathematical Software. 25 (2): 251–276. doi:10.1145/317275.317286. S2CID 15485257.
↑ George E. Collins and Alkiviadis G. Akritas, Polynomial Real Root Isolation Using Descartes' Rule of Signs. Proceedings of the 1976 ACM Symposium on Symbolic and Algebraic Computation
↑ Rouillier, F.; Zimmerman, P. (2004). "बहुपद की वास्तविक जड़ों का कुशल अलगाव". Journal of Computational and Applied Mathematics. 162 (1): 33–50. Bibcode:2004JCoAM.162...33R. doi:10.1016/j.cam.2003.08.015.
↑ Release 2.3.86 of PHCpack
↑ Bates et al. 2013
↑ Bertini: Software for Numerical Algebraic Geometry

Bates, Daniel J.; Sommese, Andrew J.; Hauenstein, Jonathan D.; Wampler, Charles W. (2013). Numerically solving polynomial systems with Bertini. Philadelphia: Society for Industrial and Applied Mathematics. ISBN 978-1-61197-269-6.
Cox, David; Little, John; O'Shea, Donal (1997). Ideals, varieties, and algorithms : an introduction to computational algebraic geometry and commutative algebra (2nd ed.). New York: Springer. ISBN 978-0387946801.
Morgan, Alexander (1987). Solving polynomial systems using continuation for engineering and scientific problems (SIAM ed.). Society for Industrial and Applied Mathematics (SIAM, 3600 Market Street, Floor 6, Philadelphia, PA 19104). ISBN 9780898719031.
Sturmfels, Bernd (2002). Solving systems of polynomial equations. Providence, RI: American Mathematical Soc. ISBN 0821832514.

[Bates_p4-1] Bates et al. 2013, p. 4

[2] Bates et al. 2013, p. 8

[3] Songxin Liang, J. Gerhard, D.J. Jeffrey, G. Moroz, A Package for Solving Parametric Polynomial Systems. Communications in Computer Algebra (2009)

[4] Aubry, P.; Maza, M. Moreno (1999). "बहुपद प्रणालियों को हल करने के लिए त्रिकोणीय सेट: चार विधियों का तुलनात्मक कार्यान्वयन". J. Symb. Comput. 28 (1–2): 125–154. doi:10.1006/jsco.1999.0270.

[5] Faugère, J.C.; Gianni, P.; Lazard, D.; Mora, T. (1993). "आदेश में परिवर्तन द्वारा शून्य-आयामी ग्रोबनेर आधार की कुशल संगणना". Journal of Symbolic Computation. 16 (4): 329–344. doi:10.1006/jsco.1993.1051.

[6] Lazard, D. (1992). "शून्य आयामी बीजगणितीय प्रणालियों को हल करना". Journal of Symbolic Computation. 13 (2): 117–131. doi:10.1016/S0747-7171(08)80086-7.

[7] Xavier Dahan and Eric Schost. Sharp Estimates for Triangular Sets. Moreover, recent algorithms for decomposing polynomial systems into triangular decompositions produce regular chains with coefficients matching the results of Dahan and Schost. In proc. ISSAC'04, pages 103--110, ACM Press, 2004

[8] Dahan, Xavier; Moreno Maza, Marc; Schost, Eric; Wu, Wenyuan; Xie, Yuzhen (2005). "Lifting techniques for triangular decompositions" (PDF). Proceedings of ISAAC 2005. ACM Press. pp. 108–105.

[9] Changbo Chen and Marc Moreno-Maza. Algorithms for Computing Triangular Decomposition of Polynomial Systems.In proc. ISSAC'2011, pages 83-90, ACM Press, 2011 and Journal of Symbolic Computation (to appear)

[10] Rouillier, Fabrice (1999). "Solving Zero-Dimensional Systems Through the Rational Univariate Representation". Appl. Algebra Eng. Commun. Comput. 9 (9): 433–461. doi:10.1007/s002000050114. S2CID 25579305.

[11] Saugata Basu; Richard Pollack; Marie-Françoise Roy (2006). वास्तविक बीजगणितीय ज्यामिति में एल्गोरिदम, अध्याय 12.4. Springer-Verlag.

[12] Lazard, Daniel (2009). "बहुपद प्रणाली के समाधान के तीस साल, और अब?". J. Symb. Comput. 44 (3): 2009. doi:10.1016/j.jsc.2008.03.004.

[Vers99-13] 13.0 ^13.1 Verschelde, Jan (1999). "एल्गोरिथम 795: PHCpack: होमोटॉपी निरंतरता द्वारा बहुपद प्रणालियों के लिए एक सामान्य-उद्देश्य सॉल्वर" (PDF). ACM Transactions on Mathematical Software. 25 (2): 251–276. doi:10.1145/317275.317286. S2CID 15485257.

[14] George E. Collins and Alkiviadis G. Akritas, Polynomial Real Root Isolation Using Descartes' Rule of Signs. Proceedings of the 1976 ACM Symposium on Symbolic and Algebraic Computation

[15] Rouillier, F.; Zimmerman, P. (2004). "बहुपद की वास्तविक जड़ों का कुशल अलगाव". Journal of Computational and Applied Mathematics. 162 (1): 33–50. Bibcode:2004JCoAM.162...33R. doi:10.1016/j.cam.2003.08.015.

[16] Release 2.3.86 of PHCpack

[17] Bates et al. 2013

[18] Bertini: Software for Numerical Algebraic Geometry

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

Anonymous

Search

बहुपद समीकरणों की प्रणाली

Namespaces

More

Page actions

Contents

परिभाषा

मूल गुण और परिभाषाएँ

क्या सुलझा रहा है?