Gauss–Legendre quadrature
संख्यात्मक विश्लेषण में, गॉस-लेजेंड्रे चतुर्भुज एक फलन के निश्चित समाकलन को अनुमानित करने के लिए गॉसियन चतुर्भुज का एक रूप है। अंतराल पर समाकलन के लिए, नियम यह रूप लेता हैः जहाँ n उपयोग किए गए नमूना बिंदुओं की संख्या है, wi चतुर्भुज भार हैं, और xi nवें लीजेंड्रे बहुपद के मूल हैं। चतुर्भुज भार वाई और चतुर्भुज नोड्स xi का यह विकल्प अद्वितीय विकल्प है जो चतुर्भुज नियम को डिग्री बहुपदों को ठीक से एकीकृत करने की अनुमति देता है। गॉस-लेजेंड्रे चतुर्भुज नियमों की गणना के लिए कई एल्गोरिदम विकसित किए गए हैं। 1969 में प्रस्तुत गोलूब-वेल्श एल्गोरिथ्म नोड्स और भार की गणना को एक आइगेनवैल्यू समस्या तक कम कर देता है जिसे क्यू. आर. एल्गोरिथ्म द्वारा हल किया जाता है। यह एल्गोरिदम लोकप्रिय था, लेकिन काफी अधिक कुशल एल्गोरिदम मौजूद हैं। न्यूटन-रैफसन विधि पर आधारित एल्गोरिदम काफी बड़े समस्या आकारों के लिए चतुर्भुज नियमों की गणना करने में सक्षम हैं। 2014 में, इग्नेस बोगर्ट ने गॉस-लेजेंड्रे क्वाड्रेचर वजन और नोड्स के लिए स्पष्ट एसिम्प्टोटिक सूत्र प्रस्तुत किए, जो n ≤ 21 के किसी भी विकल्प के लिए डबल-प्रिसिशन मशीन एप्सिलॉन के भीतर सटीक हैं। यह एक अरब से अधिक के मूल्यों के लिए नोड्स और भार की गणना की अनुमति देता है। इतिहास कार्ल फ्रेडरिक गॉस गौस-लेजेंड्रे चतुर्भुज नियम प्राप्त करने वाले पहले व्यक्ति थे, जिन्होंने 1814 में निरंतर अंशों के साथ एक गणना द्वारा ऐसा किया। उन्होंने हाथ से n = 7 क्रम में 16 अंकों तक नोड्स और भार की गणना की। कार्ल गुस्ताव जैकब जैकोबी ने चतुर्भुज नियम और लीजेंड्रे बहुपदों के ऑर्थोगोनल परिवार के बीच संबंध की खोज की। चूँकि चतुर्भुज भार और नोड्स के लिए कोई बंद-रूप सूत्र नहीं है, कई दशकों तक लोग केवल छोटे एन के लिए उनकी हाथ से गणना करने में सक्षम थे, और चतुर्भुज की गणना वजन और नोड मूल्यों वाली तालिकाओं को संदर्भित करके की जानी थी। 1942 तक ये मान केवल n = 16 तक के लिए ज्ञात थे। परिभाषा गॉस-लेजेंड्रे चतुर्भुज के साथ f ओवर को एकीकृत करने के लिए, संबंधित ऑर्थोगोनल बहुपद लेजेंड्रे बहुपद हैं, जिन्हें द्वारा दर्शाया जाता है। - th बहुपद को सामान्यीकृत करने के साथ,-th गॉस नोड, का-th मूल है और भार सूत्र द्वारा दिए गए हैं कुछ निम्न-क्रम चतुर्भुज नियमों को समाकलन के लिए नीचे सारणीबद्ध किया गया है। एक सामान्य वास्तविक अंतराल पर समाकलन के लिए, समस्या को समाकलन ओवर में बदलने के लिए अंतराल में परिवर्तन लागू किया जा सकता है। एल्गोरिदम न्यूटन-रैफसन विधियाँ कई शोधकर्ताओं ने कार्यों के मूल खोजने के लिए न्यूटन-रैफसन विधि के आधार पर गॉस-लेजेंड्रे चतुर्भुज नोड्स और भार की गणना के लिए एल्गोरिदम विकसित किए हैं। इस विशिष्ट समस्या के लिए विभिन्न अनुकूलन का उपयोग किया जाता है। उदाहरण के लिए, कुछ विधियाँ अंतराल के अंत के पास जड़ों के समूह से जुड़े मुद्दों से बचने के लिए गणना करती हैं। कुछ विधियाँ वजन का अनुमान लगाने के लिए सूत्रों का उपयोग करती हैं और फिर मशीन की सटीकता से नीचे के सन्निकटन की त्रुटि को कम करने के लिए न्यूटन-रैफसन के कुछ पुनरावृत्तियों का उपयोग करती हैं। 1969 में, गोलूब और वेल्श ने तीन शब्द पुनरावृत्ति संबंध को देखते हुए गॉसियन चतुर्भुज नियमों की गणना के लिए अपनी विधि प्रकाशित की, जिसे अंतर्निहित ऑर्थोगोनल बहुपद संतुष्ट करते हैं। वे एक गौसी चतुर्भुज नियम के नोड्स की गणना करने की समस्या को एक विशेष सममित त्रिकोणीय मैट्रिक्स के आइगेनवैल्यूज को खोजने की समस्या तक कम कर देते हैं। क्यू. आर. एल्गोरिदम का उपयोग इस मैट्रिक्स के आइगेनवैल्यू को खोजने के लिए किया जाता है। सममित त्रिकोणीय संरचना का लाभ उठाकर, एक सामान्य आइगेनवैल्यू समस्या के लिए अपेक्षित समय के विपरीत, आइगेनवैल्यू की गणना समय पर की जा सकती है। लक्षणहीन सूत्र विभिन्न विधियाँ विकसित की गई हैं जो नोड्स की गणना करने के लिए अनुमानित बंद-रूप अभिव्यक्तियों का उपयोग करती हैं। जैसा कि ऊपर उल्लेख किया गया है, कुछ विधियों में सूत्रों का उपयोग नोड्स के सन्निकटन के रूप में किया जाता है, जिसके बाद कुछ न्यूटन-रैफसन पुनरावृत्तियों को सन्निकटन को परिष्कृत करने के लिए किया जाता है। 2014 के एक पेपर में, इग्नेस बोगर्ट ने उन नोड्स के लिए एसिम्प्टोटिक सूत्र प्राप्त किए हैं जो मशीन की सटीकता के लिए और उन वजनों के लिए सटीक हैं जो मशीन की सटीकता के लिए सटीक हैं। इस विधि के लिए किसी भी न्यूटन-रैफसन पुनरावृत्ति या बेसल कार्यों के मूल्यांकन की आवश्यकता नहीं है जैसा कि अन्य विधियों में होता है। जैसा कि पेपर में दिखाया गया है, विधि 11 सेकंड में एक अरब के समस्या आकार पर नोड्स की गणना करने में सक्षम थी। चूँकि नोड्स के अंतिम बिंदुओं के पास के नोड्स इस समस्या के आकार पर एक दूसरे के बहुत करीब हो जाते हैं, इसलिए नोड्स की गणना करने की यह विधि अनिवार्य रूप से दोहरे परिशुद्धता वाले फ्लोटिंग पॉइंट में किसी भी व्यावहारिक अनुप्रयोग के लिए पर्याप्त है। उच्च परिशुद्धता वाले जोहानसन और मेज़ारोब्बा मनमाने-सटीक अंकगणित में गॉस-लेजेंड्रे चतुर्भुज नियमों की गणना करने की रणनीति का वर्णन करते हैं, जिससे छोटे और बड़े दोनों की अनुमति मिलती है। सटीकता के 1000 अंकों के साथ क्रम के नियम की गणना लगभग एक सेकंड में की जा सकती है। उनकी विधि लीजेंड्रे बहुपदों के मूल्यांकन के लिए कई अलग-अलग तकनीकों के साथ न्यूटन-रैफसन पुनरावृत्ति का उपयोग करती है। एल्गोरिथ्म एक प्रमाणित त्रुटि बाध्य भी प्रदान करता है। गिल, सेगुरा और टेमे गॉस-जैकोबी चतुर्भुज (और, विशेष रूप से, गॉस-लेजेंड्रे) की गणना के लिए चौथे क्रम के अभिसरण के साथ पुनरावृत्ति विधियों का वर्णन करते हैं। विधियों को अपने चौथे क्रम के अभिसरण की गारंटी के लिए नोड्स के प्राथमिक अनुमानों की आवश्यकता नहीं होती है। एक विशिष्ट लैपटॉप में लाखों नोड्स और हजारों अंकों के साथ चतुर्भुज नियमों की गणना संभव हो जाती है। अन्य चतुर्भुज नियमों के साथ तुलना गॉस-लेजेंड्रे चतुर्भुज एक फलन f के समाकलन की गणना के लिए बहुत संकीर्ण अर्थों में इष्टतम है, क्योंकि कोई अन्य चतुर्भुज नियम n नमूना बिंदुओं का उपयोग करते समय सभी डिग्री बहुपदों को ठीक से एकीकृत नहीं करता है। हालांकि, सटीकता का यह माप आम तौर पर बहुत उपयोगी नहीं है-- बहुपदों को एकीकृत करना बहुत आसान है और यह तर्क अपने आप में अन्य कार्यों को एकीकृत करने पर बेहतर सटीकता की गारंटी नहीं देता है। क्लेनशॉ-कर्टिस चतुर्भुज चेबीशेव नोड्स पर एक बहुपद अंतर्वेशक द्वारा अनुमानित f पर आधारित है और n नमूनों को दिए जाने पर ठीक n तक की डिग्री के बहुपदों को एकीकृत करता है। भले ही यह बहुपदों या अन्य कार्यों को एकीकृत नहीं करता है जो गॉस-लेजेंड्रे चतुर्भुज के साथ-साथ गॉस-लेजेंड्रे चतुर्भुज के एक बड़े पड़ोस में विश्लेषणात्मक हैं, क्लेनशॉ-कर्टिस अधिकांश (गैर-विश्लेषणात्मक) समाकलन के लिए गॉस-लेजेंड्रे चतुर्भुज के समान दर से अभिसरण करता है। इसके अलावा, क्लेनशॉ-कर्टिस उन गुणों को साझा करते हैं जो गॉस-लेजेंड्रे चतुर्भुज सभी निरंतर समाकलन f के लिए अभिसरण और संख्यात्मक गोलाकार त्रुटियों के लिए मजबूती का आनंद लेते हैं। क्लेनशॉ-कर्टिस को एफ. एफ. टी.-आधारित तरीकों से समय पर लागू करना आसान है। न्यूटन-कोट्स चतुर्भुज एक बहुपद अंतर्वेशक द्वारा समान दूरी वाले बिंदुओं पर f को अनुमानित करने पर आधारित है, और क्लेनशॉ-कर्टिस की तरह भी n नमूनों को दिए जाने पर ठीक n तक की डिग्री के बहुपदों को एकीकृत करता है। हालाँकि, यह रुंग की घटना से पीड़ित है क्योंकि n बढ़ता है; न्यूटन-कोट्स कुछ निरंतर समाकलन f के लिए अभिसरण नहीं करता है, और जब यह अभिसरण करता है तो यह संख्यात्मक गोल त्रुटियों से पीड़ित हो सकता है। इस प्रकार, क्लेनशॉ-कर्टिस और गॉस-लेजेंड्रे दोनों को मध्यम से बड़े n के लिए न्यूटन-कोट्स की तुलना में पर्याप्त लाभ मिलता है।