बेरिस एल्गोरिथ्म

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

इतिहास

सामान्य बेरिस एल्गोरिदम टोएप्लिट्ज़ मैट्रिक्स के लिए बेरिस एल्गोरिदम से अलग है।

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

अवलोकन

निर्धारक परिभाषा में केवल गुणा, जोड़ और घटाव संक्रियाएँ होती हैं। यदि सभी मैट्रिक्स प्रविष्टियाँ पूर्णांक हैं तो स्पष्ट रूप से निर्धारक पूर्णांक है। हालाँकि परिभाषा या लीबनिज़_फॉर्मूला_फॉर_डिटर्मिनेंट्स का उपयोग करके निर्धारक की वास्तविक गणना अव्यावहारिक है, क्योंकि इसके लिए O(n!) संचालन की आवश्यकता होती है।

गाऊसी_उन्मूलन#कंप्यूटिंग_निर्धारकों में O(n) है³) जटिलता, लेकिन विभाजन का परिचय देती है, जिसके परिणामस्वरूप फ़्लोटिंग पॉइंट नंबरों का उपयोग करके कार्यान्वित किए जाने पर राउंड-ऑफ़ त्रुटियां होती हैं।

राउंड-ऑफ_एरर|राउंड-ऑफ त्रुटियों से बचा जा सकता है यदि सभी संख्याओं को फ्लोटिंग पॉइंट के बजाय पूर्णांक अंश के रूप में रखा जाए। लेकिन फिर प्रत्येक तत्व का आकार पंक्तियों की संख्या के साथ तेजी से बढ़ता है। बेरिस मध्यवर्ती गुणांकों के परिमाण को यथोचित रूप से छोटा रखते हुए एक पूर्णांक-संरक्षण विलोपन करने का प्रश्न उठाता है। दो एल्गोरिदम सुझाए गए हैं:

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

पूर्णता के लिए बेरिस भिन्न-उत्पादक गुणन-मुक्त उन्मूलन विधियों का भी सुझाव देते हैं।

एल्गोरिदम

इस एल्गोरिदम की प्रोग्राम संरचना एक सरल ट्रिपल-लूप है, जैसा कि मानक गाऊसी उन्मूलन में होता है। हालाँकि इस मामले में मैट्रिक्स को संशोधित किया गया है ताकि प्रत्येक M_k,k प्रविष्टि में प्रमुख प्रमुख माइनर_(रैखिक_बीजगणित) शामिल है [M]_k,k. एल्गोरिथम की शुद्धता आसानी से इंडक्शन द्वारा दिखाई जाती है k.

• इनपुट: M - एक n-वर्ग मैट्रिक्स
  इसके प्रमुख प्रमुख नाबालिगों को मानते हुए [M]_k,k सभी गैर-शून्य हैं.
• मुझे_0,0 = 1 (नोट: एम_0,0 एक विशेष चर है)
• के लिए k 1 से n−1:
  • के लिए i से k+1 से n:
    • के लिए j से k+1 से n:
      • तय करना $M_{i,j}={\frac {M_{i,j}M_{k,k}-M_{i,k}M_{k,j}}{M_{k-1,k-1}}}$
• आउटपुट: मैट्रिक्स को In-place_algorithm|in-place,
  प्रत्येक में संशोधित किया गया है M_k,k प्रविष्टि में प्रमुख लघु शामिल है [M]_k,k,
  प्रविष्टि M_n,n में मूल का निर्धारक शामिल है M.

यदि प्रमुख अवयस्कों के बारे में धारणा गलत साबित होती है, उदाहरण के लिए अगर M_k−1,k−1 = 0 और कुछ M_i,k−1 ≠ 0 (i = k,...,n) तो हम विनिमय कर सकते हैं k−1-वीं पंक्ति के साथ i-वीं पंक्ति और अंतिम उत्तर का चिह्न बदलें।

विश्लेषण

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

यह इस प्रकार है कि, अधिकतम (पूर्ण) मान 2 के n × n मैट्रिक्स के लिए^एल प्रत्येक प्रविष्टि के लिए, बेरिस एल्गोरिथ्म बिग ओ नोटेशन|ओ(एन) में चलता है³) O(n) के साथ प्रारंभिक संचालन^n/2 2^nL) आवश्यक मध्यवर्ती मूल्यों के पूर्ण मूल्य पर बाध्य है। इस प्रकार इसकी कम्प्यूटेशनल जटिलता O(n) है⁵एल² (लॉग(एन)²+एल²)) प्राथमिक अंकगणित या O(n) का उपयोग करते समय⁴L (log(n) + L) log(log(n) + L)) तेज गुणन का उपयोग करके।