Polynomial root-finding algorithms
बहुपद जड़ों का पता लगाना एक लंबे समय से चली आ रही समस्या है जो पूरे इतिहास में बहुत शोध का विषय रही है। इसका एक प्रमाण यह है कि 19वीं शताब्दी तक, बीजगणित का अर्थ अनिवार्य रूप से बहुपद समीकरणों का सिद्धांत था। सिद्धांत एक रैखिक बहुपद (डिग्री एक) का मूल खोजना आसान है और इसके लिए केवल एक विभाजन की आवश्यकता होती हैः सामान्य समीकरण का समाधान होता है द्विघात बहुपदों (डिग्री दो) के लिए, द्विघात सूत्र एक समाधान उत्पन्न करता है, लेकिन इसके संख्यात्मक मूल्यांकन के लिए संख्यात्मक स्थिरता सुनिश्चित करने के लिए कुछ देखभाल की आवश्यकता हो सकती है। डिग्री तीन और चार के लिए, रेडिकल के संदर्भ में बंद-रूप समाधान होते हैं, जो आम तौर पर संख्यात्मक मूल्यांकन के लिए सुविधाजनक नहीं होते हैं, क्योंकि ये बहुत जटिल होते हैं और इसमें कई मूल की गणना शामिल होती है जिनकी गणना बहुपद के मूल की प्रत्यक्ष गणना से आसान नहीं होती है (उदाहरण के लिए एक घन बहुपद के वास्तविक मूल की अभिव्यक्ति में गैर-वास्तविक घन मूल शामिल हो सकते हैं)। पाँच डिग्री या उससे अधिक के बहुपदों के लिए एबेल-रफ़िनी प्रमेय दावा करता है कि सामान्य रूप से, जड़ों की कोई मौलिक अभिव्यक्ति नहीं है। इसलिए, बहुत कम डिग्री को छोड़कर, बहुपदों की मूल खोज में मूल के सन्निकटन का पता लगाना शामिल है। बीजगणित के मौलिक प्रमेय के अनुसार, डिग्री के बहुपद में वास्तव में वास्तविक या जटिल मूल होते हैं जो गुणकों को गिनते हैं। यह इस प्रकार है कि बहुपदों के लिए जड़ खोजने की समस्या को तीन अलग-अलग उप-समस्याओं में विभाजित किया जा सकता है; एक जड़ ढूंढना सभी जड़ों को ढूंढना जटिल तल के एक विशिष्ट क्षेत्र में जड़ ढूंढना, आमतौर पर वास्तविक जड़ें या दिए गए अंतराल में वास्तविक जड़ें (उदाहरण के लिए, जब जड़ें एक भौतिक मात्रा का प्रतिनिधित्व करती हैं, तो केवल वास्तविक सकारात्मक ही दिलचस्प होती हैं)। एक मूल खोजने के लिए, न्यूटन की विधि और अन्य सामान्य पुनरावृत्ति विधियाँ आम तौर पर अच्छी तरह से काम करती हैं। सभी जड़ों को खोजने के लिए, यकीनन सबसे विश्वसनीय विधि फ्रांसिस क्यू. आर. एल्गोरिथ्म है जो बहुपद के अनुरूप कम्पैनियन मैट्रिक्स के आइगेनवैल्यूज की गणना करता है, जिसे मैटलैब में मानक विधि के रूप में लागू किया जाता है। सभी जड़ों को खोजने का सबसे पुराना तरीका एक ही जड़ को ढूंढना है। जब एक मूल पाया जाता है, तो इसे द्विपद को विभाजित करके बहुपद से हटाया जा सकता है। परिणामी बहुपद में शेष मूल होते हैं, जिन्हें इस प्रक्रिया पर पुनरावृत्ति करके पाया जा सकता है। हालांकि, कम डिग्री को छोड़कर, यह संख्यात्मक अस्थिरता के कारण अच्छी तरह से काम नहीं करता हैः विल्किंसन के बहुपद से पता चलता है कि एक गुणांक का बहुत छोटा संशोधन न केवल जड़ों के मूल्य को नाटकीय रूप से बदल सकता है, बल्कि उनकी प्रकृति (वास्तविक या जटिल) को भी बदल सकता है। इसके अलावा, एक अच्छे सन्निकटन के साथ भी, जब कोई एक अनुमानित मूल पर एक बहुपद का मूल्यांकन करता है, तो उसे एक ऐसा परिणाम मिल सकता है जो शून्य के करीब होना बहुत दूर है। उदाहरण के लिए, यदि डिग्री 20 (विल्किंसन के बहुपद की डिग्री) की बहुपद का मूल 10 के करीब है, तो मूल पर बहुपद का व्युत्पन्न इसके क्रम का हो सकता है जिसका अर्थ है कि मूल के मूल्य पर एक त्रुटि अनुमानित मूल पर बहुपद का मान उत्पन्न कर सकती है जो कि के क्रम की है। इन समस्याओं से बचने के लिए, विधियों को विस्तृत किया गया है, जो किसी भी वांछित सटीकता के लिए सभी मूल की गणना एक साथ करते हैं। वर्तमान में सबसे कुशल विधि एबरथ विधि है। एम. पी. सॉल्व के नाम से एक मुफ्त कार्यान्वयन उपलब्ध है। यह एक संदर्भ कार्यान्वयन है, जो नियमित रूप से 1,000 से अधिक महत्वपूर्ण दशमलव अंकों के साथ 1,000 से अधिक डिग्री के बहुपदों के मूल पा सकता है। सभी मूल की गणना करने के तरीकों का उपयोग वास्तविक मूल की गणना के लिए किया जा सकता है। हालाँकि, यह तय करना मुश्किल हो सकता है कि एक छोटे से काल्पनिक भाग वाली जड़ वास्तविक है या नहीं। इसके अलावा, जैसा कि वास्तविक जड़ों की संख्या, औसतन, डिग्री का लघुगणक है, जब कोई वास्तविक जड़ों में रुचि रखता है तो गैर-वास्तविक जड़ों की गणना करना कंप्यूटर संसाधनों की बर्बादी है। वास्तविक जड़ों की संख्या की गणना करने की सबसे पुरानी विधि, और एक अंतराल में जड़ों की संख्या स्टर्म के प्रमेय से प्राप्त होती है, लेकिन डेसकार्टेस के संकेतों के नियम और इसके विस्तार पर आधारित विधियाँ-बुडन और विंसेंट के प्रमेय-आम तौर पर अधिक कुशल हैं। जड़ खोजने के लिए, सभी उन अंतरालों के आकार को कम करके आगे बढ़ते हैं जिनमें जड़ों की खोज की जाती है जब तक कि शून्य या एक मूल वाले अंतराल नहीं मिल जाते। फिर पृथक जड़ों के लिए न्यूटन की विधि का द्विघात अभिसरण प्राप्त करने के लिए एक मूल वाले अंतराल को और कम किया जा सकता है। मुख्य कंप्यूटर बीजगणित प्रणालियों (मेपल, मैथेमेटिका, सेजमैथ, पी. ए. आर. आई./जी. पी.) में एक बहुपद के वास्तविक मूल के लिए डिफ़ॉल्ट एल्गोरिथ्म के रूप में इस विधि का एक प्रकार है। विधियों का वर्ग बहुपद के मूल खोजने की समस्या को बहुपद के साथी मैट्रिक्स के आइगेनवैल्यू खोजने की समस्या में परिवर्तित करने पर आधारित है, सिद्धांत रूप में, बहुपद के मूल खोजने के लिए किसी भी आइगेनवैल्यू एल्गोरिथ्म का उपयोग कर सकते हैं। हालांकि, दक्षता कारणों से कोई भी ऐसे तरीकों को पसंद करता है जो मैट्रिक्स की संरचना को नियोजित करते हैं, यानी, मैट्रिक्स-मुक्त रूप में लागू किया जा सकता है। इन विधियों में शक्ति विधि है, जिसका अनुप्रयोग साथी मैट्रिक्स के स्थानांतर के लिए सबसे बड़े मापांक के मूल को खोजने के लिए शास्त्रीय बर्नौली की विधि है। शिफ्ट के साथ व्युत्क्रम शक्ति विधि, जो पहले कुछ सबसे छोटे मूल का पता लगाती है, वह है जो जेनकिंस-ट्राब एल्गोरिथ्म के जटिल (सी. पी. ओ. एल.) संस्करण को चलाती है और इसे अपनी संख्यात्मक स्थिरता देती है। इसके अतिरिक्त, गुच्छेदार जड़ों की उपस्थिति में भी इसका क्रम के साथ तेजी से अभिसरण होता है (जहाँ सुनहरा अनुपात होता है)। यह तेज अभिसरण प्रति चरण तीन बहुपद मूल्यांकनों की लागत के साथ आता है, जिसके परिणामस्वरूप एक अवशिष्ट होता है, जो कि न्यूटन की विधि के तीन चरणों की तुलना में धीमा अभिसरण है। एक मूल का पता लगाना एक मूल की गणना के लिए सबसे व्यापक रूप से उपयोग की जाने वाली विधि न्यूटन की विधि है, जिसमें एक अच्छी तरह से चुने गए मान से शुरू करके की गणना की पुनरावृत्ति होती है यदि एक बहुपद है, तो प्रत्येक पुनरावृत्ति में बहुपद और उसके व्युत्पन्न की गणना के लिए पूर्व-प्रसंस्करण के साथ हॉर्नर की विधि या मूल्यांकन का उपयोग करते समय गणना तेज होती है। हालाँकि अभिसरण आम तौर पर द्विघात होता है, लेकिन यह बहुत धीरे-धीरे अभिसरण कर सकता है या यहाँ तक कि बिल्कुल भी अभिसरण नहीं कर सकता है। विशेष रूप से, यदि बहुपद का कोई वास्तविक मूल नहीं है, और वास्तविक है, तो न्यूटन की विधि अभिसरण नहीं कर सकती है। हालाँकि, यदि बहुपद का एक वास्तविक मूल है, जो इसके व्युत्पन्न के बड़े वास्तविक मूल से बड़ा है, तो न्यूटन की विधि इस सबसे बड़े मूल में चतुर्भुज रूप से परिवर्तित हो जाती है यदि यह इस बड़े मूल से बड़ा है (मूल की ऊपरी सीमा की गणना करने के लिए आसान तरीके हैं, बहुपद मूल के गुण देखें)। यह मूल की गणना के लिए हॉर्नर विधि का प्रारंभिक बिंदु है। जब एक मूल पाया जाता है, तो बहुपद से कारक को हटाने के लिए यूक्लिडियन विभाजन का उपयोग किया जा सकता है। परिणामी भागफल के मूल की गणना करना, और प्रक्रिया को दोहराना, सिद्धांत रूप में, सभी मूल की गणना करने का एक तरीका प्रदान करता है। हालाँकि, यह पुनरावृत्ति योजना संख्यात्मक रूप से अस्थिर है; अनुमानित त्रुटियाँ क्रमिक गुणनखंडन के दौरान जमा होती हैं, ताकि अंतिम मूल एक बहुपद के साथ निर्धारित किए जाते हैं जो मूल बहुपद के एक कारक से व्यापक रूप से विचलित होता है। इस त्रुटि को कम करने के लिए, पाया जाने वाले प्रत्येक मूल के लिए, मूल बहुपद के साथ न्यूटन की विधि को फिर से शुरू कर सकते हैं, और इस अनुमानित मूल को प्रारंभिक मूल्य के रूप में। हालाँकि, इस बात की कोई गारंटी नहीं है कि यह सभी जड़ों को खोजने की अनुमति देगा। वास्तव में, एक बहुपद के मूल को उसके गुणांक से खोजने की समस्या अत्यधिक खराब स्थिति में हो सकती है। यह विल्किंसन के बहुपद द्वारा सचित्र हैः डिग्री 20 के इस बहुपद के मूल 20 पहले सकारात्मक पूर्णांक हैं; इसके गुणांक (-210 के बराबर) में से एक के 32-बिट प्रतिनिधित्व के अंतिम बिट को बदलने से केवल 10 वास्तविक मूल और 10 जटिल मूल के साथ एक बहुपद उत्पन्न होता है जिसमें काल्पनिक भाग 0.6 से बड़े होते हैं। हैली की विधि और लैगुएरे की विधि न्यूटन की विधि से निकटता से संबंधित हैं। दोनों एक पुनरावृत्ति प्रक्रिया के लिए बहुपद और इसकी दो पहली व्युत्पत्तियों का उपयोग करते हैं जिसमें एक घन अभिसरण होता है। इन विधियों के लगातार दो चरणों को एक ही परीक्षण में जोड़कर, 6 बहुपद मूल्यांकन (हॉर्नर नियम के साथ) की कीमत पर 9 के अभिसरण की दर प्राप्त होती है। दूसरी ओर, न्यूटन विधि के तीन चरणों के संयोजन से समान संख्या में बहुपद मूल्यांकन की कीमत पर 8 के अभिसरण की दर मिलती है। यह इन विधियों को थोड़ा लाभ देता है (लैगुएरे की विधि के लिए कम स्पष्ट है, क्योंकि प्रत्येक चरण में एक वर्गमूल की गणना की जानी है)। इन विधियों को वास्तविक गुणांक और वास्तविक प्रारंभिक बिंदुओं के साथ बहुपदों पर लागू करते समय, न्यूटन और हेली की विधि वास्तविक संख्या रेखा के भीतर रहती है। जटिल जड़ों को खोजने के लिए जटिल प्रारंभिक बिंदुओं का चयन करना पड़ता है। इसके विपरीत, अपने मूल्यांकन में वर्गमूल के साथ लैगुएरे विधि अपने अनुसार वास्तविक अक्ष को छोड़ देगी। जोड़ों में जड़ों का पता लगाना यदि दिए गए बहुपद में केवल वास्तविक गुणांक हैं, तो कोई जटिल संख्याओं वाली गणनाओं से बचना चाह सकता है। उस प्रभाव के लिए, संयुग्म जटिल जड़ों के जोड़े के लिए द्विघात कारकों को खोजना होगा। बेयरस्टो की विधि में इस कार्य के लिए बहुआयामी न्यूटन की विधि के अनुप्रयोग का परिणाम है। जेनकिंस-ट्राब एल्गोरिदम का वास्तविक संस्करण इस विधि का एक सुधार है। सरल डूरंड-कर्नर और थोड़ी अधिक जटिल एबरथ विधि एक साथ केवल सरल जटिल संख्या अंकगणित का उपयोग करके सभी जड़ों का पता लगाती है। बहु-बिंदु मूल्यांकन और त्वरित फूरियर परिवर्तन के समान अंतर्वेशन के लिए त्वरित एल्गोरिदम बहुपद की बड़ी डिग्री के लिए उन्हें गति देने में मदद कर सकते हैं। प्रारंभिक बिंदुओं का एक असममित, लेकिन समान रूप से वितरित सेट चुनने की सलाह दी जाती है। मुक्त सॉफ्टवेयर एम. पी. सॉल्व में इस विधि का कार्यान्वयन इसकी दक्षता और सटीकता के लिए एक संदर्भ है। इस शैली के साथ एक अन्य विधि डैंडेलिन-ग्रैफ विधि है (कभी-कभी लोबाचेव्स्की को भी कहा जाता है), जो जड़ों को बार-बार और निहित रूप से वर्ग करने के लिए बहुपद परिवर्तनों का उपयोग करती है। यह जड़ों में भिन्नताओं को बहुत बढ़ाता है। वाइटे के सूत्रों को लागू करते हुए, जड़ों के मापांक के लिए आसान अनुमान प्राप्त किया जाता है, और कुछ और प्रयास के साथ, जड़ों के लिए। बहिष्करण और घेरने की विधियाँ कई तेज़ परीक्षण मौजूद हैं जो बताते हैं कि क्या वास्तविक रेखा के एक खंड या जटिल तल के एक क्षेत्र में कोई जड़ नहीं है। जड़ों के मापांक को बांधकर और इन सीमाओं द्वारा इंगित प्रारंभिक क्षेत्र को पुनरावर्ती रूप से उपविभाजित करके, कोई भी उन छोटे क्षेत्रों को अलग कर सकता है जिनमें जड़ें हो सकती हैं और फिर उनका सटीक पता लगाने के लिए अन्य तरीकों को लागू कर सकता है। इन सभी विधियों में बहुपद के स्थानांतरित और स्केल किए गए संस्करणों के गुणांक का पता लगाना शामिल है। बड़ी डिग्री के लिए, एफ. एफ. टी.-आधारित त्वरित तरीके व्यवहार्य हो जाते हैं। वास्तविक जड़ों के लिए, अगले खंड देखें। लेहमर-शूर एल्गोरिथ्म वृत्तों के लिए शूर-कोहन परीक्षण का उपयोग करता है; एक प्रकार, विल्फ का वैश्विक द्विभाजन एल्गोरिथ्म जटिल तल में आयताकार क्षेत्रों के लिए एक घुमावदार संख्या गणना का उपयोग करता है। विभाजन वृत्त विधि जड़ों के समूहों के अनुरूप बड़े स्तर के कारकों को खोजने के लिए एफ. एफ. टी.-आधारित बहुपद परिवर्तनों का उपयोग करती है। फैक्टराइजेशन की सटीकता को न्यूटन-प्रकार पुनरावृत्ति का उपयोग करके अधिकतम किया जाता है। यह विधि उच्च डिग्री से मनमाने ढंग से सटीकता के बहुपदों की जड़ों को खोजने के लिए उपयोगी है; इस सेटिंग में इसकी लगभग इष्टतम जटिलता है। वास्तविक मूल अलगाव वास्तविक गुणांक के साथ एक बहुपद की वास्तविक जड़ों का पता लगाना एक ऐसी समस्या है जिस पर 19वीं शताब्दी की शुरुआत से ही बहुत ध्यान दिया गया है, और यह अभी भी अनुसंधान का एक सक्रिय क्षेत्र है। अधिकांश रूट-फाइंडिंग एल्गोरिदम कुछ वास्तविक रूट पा सकते हैं, लेकिन सभी रूट पाए जाने को प्रमाणित नहीं कर सकते हैं। सभी जटिल जड़ों को खोजने के तरीके, जैसे कि एबरथ विधि वास्तविक जड़ें प्रदान कर सकती है। हालांकि, बहुपदों की संख्यात्मक अस्थिरता के कारण (विल्किंसन की बहुपद देखें), उन्हें यह तय करने के लिए मनमाना-सटीक अंकगणित की आवश्यकता हो सकती है कि कौन से मूल वास्तविक हैं। इसके अलावा, वे सभी जटिल जड़ों की गणना करते हैं जब केवल कुछ ही वास्तविक होते हैं। यह इस प्रकार है कि वास्तविक जड़ों की गणना करने का मानक तरीका पहले असंबद्ध अंतरालों की गणना करना है, जिन्हें पृथक अंतराल कहा जाता है, जैसे कि प्रत्येक में बिल्कुल एक वास्तविक मूल होता है, और एक साथ उनमें सभी मूल होते हैं। इस गणना को वास्तविक मूल अलगाव कहा जाता है। पृथक अंतराल होने पर, कोई भी त्वरित संख्यात्मक विधियों का उपयोग कर सकता है, जैसे कि परिणाम की सटीकता में सुधार के लिए न्यूटन की विधि। वास्तविक जड़ अलगाव के लिए सबसे पुराना पूर्ण एल्गोरिथ्म स्टर्म के प्रमेय से प्राप्त होता है। हालाँकि, यह डेसकार्टेस के संकेतों के नियम और विंसेंट के प्रमेय पर आधारित विधियों की तुलना में बहुत कम कुशल प्रतीत होता है। ये विधियाँ दो मुख्य वर्गों में विभाजित होती हैं, एक निरंतर अंशों का उपयोग करके और दूसरा द्विभाजन का उपयोग करके। 21वीं सदी की शुरुआत से दोनों विधियों में नाटकीय रूप से सुधार हुआ है। इन सुधारों के साथ वे एक कम्प्यूटेशनल जटिलता तक पहुँचते हैं जो सभी मूल की गणना के लिए सबसे अच्छे एल्गोरिदम के समान है (भले ही सभी मूल वास्तविक हों)। ये एल्गोरिदम लागू किए गए हैं और गणितीय (निरंतर अंश विधि) और मेपल (द्विभाजन विधि) में उपलब्ध हैं। दोनों कार्यान्वयन नियमित रूप से 1,000 से अधिक डिग्री के बहुपदों के वास्तविक मूल का पता लगा सकते हैं। बहुपदों की कई जड़ों का पता लगाना कई जड़ों की संख्यात्मक गणना कई जड़ें अत्यधिक संवेदनशील होती हैं, जिन्हें सामान्य रूप से असंबंधित और संख्यात्मक गणना में गलत माना जाता है। झोंगगैंग ज़ेंग (2004) द्वारा एक विधि, जिसे एक MATLAB पैकेज के रूप में लागू किया गया है, एक बहुपद के कई मूल और संबंधित गुणकों की गणना सटीक रूप से करता है, भले ही गुणांक सटीक न हों। विधि को दो चरणों में संक्षेपित किया जा सकता है। दी गई बहुपद को मान लीजिए। पहला चरण एक संख्यात्मक सबसे बड़े सामान्य भाजक एल्गोरिथ्म के साथ वर्ग-मुक्त गुणनखंडन को लागू करके बहुलता संरचना को निर्धारित करता है। यह लिखने की अनुमति देता है जहाँ अलग-अलग जड़ों की बहुलताएँ हैं। यह समीकरण (अग्रणी गुणांक एक चर नहीं है) के साथ गुणांक से मेल खाने वाले समीकरणों पर चर होने के लिए एक अतिनिर्धारित प्रणाली है। अधिकांश मामलों में सबसे कम वर्ग समाधान अब खराब स्थिति में नहीं है। दूसरा चरण विशिष्ट जड़ों के लिए अतिनिर्धारित प्रणाली को हल करने के लिए गॉस-न्यूटन एल्गोरिदम को लागू करता है। विलियम काहन (1972) द्वारा खोजे गए कई जड़ों के ज्यामितीय गुण के कारण कई जड़ों की संवेदनशीलता को नियमित किया जा सकता है और अतिनिर्धारित प्रणाली मॉडल गुणों को बनाए रखता है। वर्ग-मुक्त गुणनखंडन उन बहुपदों के लिए जिनके गुणांक पूर्णांक या परिमेय संख्याओं के रूप में दिए गए हैं, उन्हें उन कारकों में गुणनखंडित करने की एक कुशल विधि है जिनके मूल केवल सरल हैं और जिनके गुणांक भी बिल्कुल दिए गए हैं। यह विधि, जिसे वर्ग-मुक्त गुणनखंडन कहा जाता है, एक बहुपद के कई मूल पर आधारित है जो बहुपद और उसके व्युत्पन्न के सबसे बड़े सामान्य भाजक के मूल हैं। एक बहुपद p का वर्ग-मुक्त गुणनखंडन एक गुणनखंडन है जहाँ प्रत्येक या तो 1 है या कई मूलों के बिना एक बहुपद है, और दो अलग-अलग का कोई सामान्य मूल नहीं है। इस गुणनखंडन की गणना करने का एक कुशल तरीका यून का एल्गोरिथ्म है। संदर्भ बहुपद मूल-खोज एल्गोरिदम