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

बहुपद समीकरणों की एक प्रणाली (कभी-कभी केवल कुछ बहुपद प्रणाली) के साथ समीकरणों का एक सेट $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$ दिया गया है। नीचे वर्णित तर्कसंगत अविभाज्य प्रतिनिधित्व, ऐसी विशेष नियमित श्रृंखला की गणना करने की अनुमति देता है, जो एक नियमित श्रृंखला या ग्रोबनेर आधार से शुरू करके दहन-शोस्ट बाध्य को संतुष्ट करता है।

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

परिमेय अविभाज्य प्रतिनिधित्व या आरयूआर परिमेय संख्याओं पर एक शून्य आयामी बहुपद प्रणाली के समाधान का प्रतिनिधित्व है जिसे एफ. रूइलियर द्वारा निवेदित किया गया है।^[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$ डिग्री $D$ के $x 0$ में एक अविभाजित बहुपद है और $g 0, ..., g n$ , $D$ से कम डिग्री वाले $x 0$ में अविभिन्न बहुपद हैं।

परिमेय संख्याओं पर शून्य-आयामी बहुपद प्रणाली को देखते हुए, 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$ ,द्वारा निरूपित करते हैं।

दूसरे वैरिएबल में, एक श्रंख्ला $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}:$ का मान अच्छी तरह से चुना जाए: बहुत बड़ा, न्यूटन का अभिसरण धीमा हो सकता है और यहां तक कि एक समाधान पथ से दूसरे पर कूद सकता है। बहुत छोटा और चरणों की संख्या विधि को धीमा कर देती है।

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

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

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

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

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

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

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

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

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

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

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

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

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

यह भी देखें

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

संदर्भ

↑ 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

परिभाषा

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

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