बेरिस एल्गोरिथ्म: Difference between revisions
(Created page with "गणित में, बेरेज़ कलन विधि, जिसका नाम इरविन बेरेज़ के नाम पर रखा गया...") |
No edit summary |
||
| Line 1: | Line 1: | ||
गणित में, | गणित में, बेरिस एल्गोरिथ्म '''(बेरिस [[कलन विधि]])''', जिसका नाम इरविन बेरेज़ के नाम पर रखा गया है, केवल [[पूर्णांक]] अंकगणित का उपयोग करके पूर्णांक प्रविष्टियों के साथ [[मैट्रिक्स (गणित)|आव्यूह (गणित)]] के निर्धारक या [[सोपानक रूप]] की गणना करने के लिए एक एल्गोरिदम है; किया गया कोई भी विभाजन (गणित) सटीक होने की गारंटी है (कोई [[शेष]] नहीं है)। विधि का उपयोग (अनुमानित) [[वास्तविक संख्या]] प्रविष्टियों के साथ आव्यूह के निर्धारक की गणना करने के लिए भी किया जा सकता है, जिससे इनपुट में पहले से उपस्थित त्रुटियों से परे किसी भी राउंड-ऑफ त्रुटियों की प्रांरम्भ से बचा जा सके। | ||
==इतिहास== | ==इतिहास== | ||
सामान्य बेरिस एल्गोरिदम [[टोएप्लिट्ज़ मैट्रिक्स]] के लिए बेरिस एल्गोरिदम से अलग है। | सामान्य बेरिस एल्गोरिदम [[टोएप्लिट्ज़ मैट्रिक्स|टोएप्लिट्ज़ आव्यूह]] के लिए बेरिस एल्गोरिदम से अलग है। | ||
कुछ स्पैनिश भाषी देशों में, इस एल्गोरिदम को बेरिस-मोंटांटे के नाम से भी जाना जाता है, क्योंकि [[मेक्सिको]] के यूनिवर्सिडैड ऑटोनोमा डी नुएवो लियोन के प्रोफेसर रेने मारियो मोंटेंटे पार्डो ने इस पद्धति को अपने छात्रों के बीच लोकप्रिय बनाया। | कुछ स्पैनिश भाषी देशों में, इस एल्गोरिदम को '''बेरिस-मोंटांटे''' के नाम से भी जाना जाता है, क्योंकि [[मेक्सिको]] के यूनिवर्सिडैड ऑटोनोमा डी नुएवो लियोन के प्रोफेसर रेने मारियो मोंटेंटे पार्डो ने इस पद्धति को अपने छात्रों के बीच लोकप्रिय बनाया। | ||
==अवलोकन== | ==अवलोकन== | ||
निर्धारक परिभाषा में केवल गुणा, जोड़ और घटाव संक्रियाएँ होती हैं। यदि सभी | निर्धारक परिभाषा में केवल गुणा, जोड़ और घटाव संक्रियाएँ होती हैं। यदि सभी आव्यूह प्रविष्टियाँ पूर्णांक हैं तो स्पष्ट रूप से निर्धारक पूर्णांक है। हालाँकि परिभाषा या लीबनिज़_फॉर्मूला_फॉर_डिटर्मिनेंट्स का उपयोग करके निर्धारक की वास्तविक गणना अव्यावहारिक है, क्योंकि इसके लिए O(''n!'') संचालन की आवश्यकता होती है। | ||
गाऊसी_उन्मूलन | गाऊसी_उन्मूलन कंप्यूटिंग_निर्धारकों में O(''n<sup>3</sup>'') है) सम्मिश्रता, लेकिन विभाजन का परिचय देती है, जिसके परिणामस्वरूप फ़्लोटिंग पॉइंट नंबरों का उपयोग करके कार्यान्वित किए जाने पर राउंड-ऑफ़ त्रुटियां होती हैं। | ||
राउंड-ऑफ एरर (राउंड-ऑफ त्रुटियों) से बचा जा सकता है यदि सभी संख्याओं को फ्लोटिंग पॉइंट के बजाय पूर्णांक अंश के रूप में रखा जाए। लेकिन फिर प्रत्येक तत्व का आकार पंक्तियों की संख्या के साथ तेजी से बढ़ता है।<ref>{{citation|last1=Middeke|first1=J.|last2=Jeffrey|first2=D.J.|last3=Koutschan|first3=C.|title=Common Factors in Fraction-Free Matrix Decompositions|journal= Mathematics in Computer Science|year=2020|volume=15|issue=4|pages=589–608|doi=10.1007/s11786-020-00495-9|arxiv=2005.12380|doi-access=free}}</ref> | |||
बेरिस मध्यवर्ती गुणांकों के परिमाण को यथोचित रूप से छोटा रखते हुए एक पूर्णांक-संरक्षण विलोपन करने का प्रश्न उठाता है। दो एल्गोरिदम सुझाए गए हैं:<ref name="bareiss">{{citation|first=Erwin H.|last=Bareiss|title= Sylvester's Identity and multistep integer-preserving Gaussian elimination|pages=565–578|url=https://www.ams.org/journals/mcom/1968-22-103/S0025-5718-1968-0226829-0/S0025-5718-1968-0226829-0.pdf|journal=[[Mathematics of Computation]]|year=1968|volume=22|issue=103|doi=10.2307/2004533|jstor=2004533}}</ref><ref>{{citation|first=Erwin H.|last=Bareiss|title=MULTISTEP INTEGER-PRESERVING GAUSSIAN ELIMINATION|url=https://digital.library.unt.edu/ark:/67531/metadc1035277/m2/1/high_res_d/4474185.pdf|year=1966}}. ''(Contains a clearer picture of the operations sequence)''</ref> | बेरिस मध्यवर्ती गुणांकों के परिमाण को यथोचित रूप से छोटा रखते हुए एक पूर्णांक-संरक्षण विलोपन करने का प्रश्न उठाता है। दो एल्गोरिदम सुझाए गए हैं:<ref name="bareiss">{{citation|first=Erwin H.|last=Bareiss|title= Sylvester's Identity and multistep integer-preserving Gaussian elimination|pages=565–578|url=https://www.ams.org/journals/mcom/1968-22-103/S0025-5718-1968-0226829-0/S0025-5718-1968-0226829-0.pdf|journal=[[Mathematics of Computation]]|year=1968|volume=22|issue=103|doi=10.2307/2004533|jstor=2004533}}</ref><ref>{{citation|first=Erwin H.|last=Bareiss|title=MULTISTEP INTEGER-PRESERVING GAUSSIAN ELIMINATION|url=https://digital.library.unt.edu/ark:/67531/metadc1035277/m2/1/high_res_d/4474185.pdf|year=1966}}. ''(Contains a clearer picture of the operations sequence)''</ref> | ||
# डिवीजन-मुक्त एल्गोरिदम - बिना किसी डिवीजन ऑपरेशन के त्रिकोणीय रूप में | # डिवीजन-मुक्त एल्गोरिदम - बिना किसी डिवीजन ऑपरेशन के त्रिकोणीय रूप में आव्यूह कटौती करता है। | ||
# भिन्न-मुक्त एल्गोरिथ्म - मध्यवर्ती प्रविष्टियों को छोटा रखने के लिए विभाजन का उपयोग करता है, लेकिन सिल्वेस्टर की पहचान के कारण परिवर्तन अभी भी पूर्णांक-संरक्षित है (विभाजन में शून्य शेष है)। | # भिन्न-मुक्त एल्गोरिथ्म - मध्यवर्ती प्रविष्टियों को छोटा रखने के लिए विभाजन का उपयोग करता है, लेकिन सिल्वेस्टर की पहचान के कारण परिवर्तन अभी भी पूर्णांक-संरक्षित है (विभाजन में शून्य शेष है)। | ||
पूर्णता के लिए बेरिस भिन्न-उत्पादक गुणन-मुक्त उन्मूलन विधियों का भी सुझाव देते हैं।<ref name="bareiss"/> | पूर्णता के लिए बेरिस भिन्न-उत्पादक गुणन-मुक्त उन्मूलन विधियों का भी सुझाव देते हैं।<ref name="bareiss"/> | ||
==एल्गोरिदम== | ==एल्गोरिदम== | ||
इस एल्गोरिदम की प्रोग्राम संरचना एक सरल ट्रिपल-लूप है, जैसा कि मानक गाऊसी उन्मूलन में होता है। हालाँकि इस | इस एल्गोरिदम की प्रोग्राम संरचना एक सरल ट्रिपल-लूप है, जैसा कि मानक गाऊसी उन्मूलन में होता है। हालाँकि इस स्थिति में आव्यूह को संशोधित किया गया है ताकि प्रत्येक {{mvar|M}}<sub>{{mvar|k,k}}</sub> प्रविष्टि में प्रमुख प्रमुख माइनर_(रैखिक_बीजगणित) शामिल है [{{mvar|M}}]<sub>{{mvar|k,k}}</sub>. एल्गोरिथम की शुद्धता आसानी से इंडक्शन द्वारा दिखाई जाती है {{mvar|k}}.<ref>{{citation|last=Yap|first=Chee Keng|title=Fundamental Problems of Algorithmic Algebra|publisher=Oxford University Press|year=2000}}</ref> | ||
{{framebox|blue}} | {{framebox|blue}} | ||
* इनपुट: {{mvar|M}} - एक {{mvar|n}}-वर्ग मैट्रिक्स<br/>इसके प्रमुख प्रमुख नाबालिगों को मानते हुए [{{mvar|M}}]<sub>{{mvar|k,k}}</sub> सभी गैर-शून्य हैं. | * इनपुट: {{mvar|M}} - एक {{mvar|n}}-वर्ग मैट्रिक्स<br/>इसके प्रमुख प्रमुख नाबालिगों को मानते हुए [{{mvar|M}}]<sub>{{mvar|k,k}}</sub> सभी गैर-शून्य हैं. | ||
* | * मान लीजिये M<sub>0,0</sub> {{=}} 1 (नोट: M<sub>0,0</sub> एक विशेष चर है) | ||
* के लिए {{mvar|k}} 1 से {{mvar|n}}−1: | * के लिए {{mvar|k}} 1 से {{mvar|n}}−1: | ||
** के लिए {{mvar|i}} से {{mvar|k}}+1 से {{mvar|n}}: | ** के लिए {{mvar|i}} से {{mvar|k}}+1 से {{mvar|n}}: | ||
*** के लिए {{mvar|j}} से {{mvar|k}}+1 से {{mvar|n}}: | *** के लिए {{mvar|j}} से {{mvar|k}}+1 से {{mvar|n}}: | ||
**** तय करना <math>M_{i,j} = \frac{M_{i,j} M_{k,k} - M_{i,k} M_{k,j}}{M_{k-1,k-1}}</math> | **** तय करना <math>M_{i,j} = \frac{M_{i,j} M_{k,k} - M_{i,k} M_{k,j}}{M_{k-1,k-1}}</math> | ||
* आउटपुट: | * आउटपुट: आव्यूह को In-place_algorithm|in-place,<br/>प्रत्येक में संशोधित किया गया है {{mvar|M}}<sub>{{mvar|k,k}}</sub> प्रविष्टि में प्रमुख लघु सम्मिलित है [{{mvar|M}}]<sub>{{mvar|k,k}}</sub>,<br/>प्रविष्टि {{mvar|M<sub>n,n</sub>}} में मूल का निर्धारक सम्मिलित है {{mvar|M}}. | ||
{{frame-footer}} | {{frame-footer}} | ||
| Line 35: | Line 34: | ||
==विश्लेषण== | ==विश्लेषण== | ||
बेरिस एल्गोरिथ्म के निष्पादन के दौरान, गणना किया जाने वाला प्रत्येक पूर्णांक इनपुट | बेरिस एल्गोरिथ्म के निष्पादन के दौरान, गणना किया जाने वाला प्रत्येक पूर्णांक इनपुट आव्यूह के उपाव्यूह का निर्धारक होता है। यह [[हैडामर्ड असमानता]] का उपयोग करके, इन पूर्णांकों के आकार को सीमित करने की अनुमति देता है। अन्यथा, बेरिस एल्गोरिदम को गॉसियन उन्मूलन के एक प्रकार के रूप में देखा जा सकता है और इसके लिए लगभग समान संख्या में अंकगणितीय परिचालन की आवश्यकता होती है। | ||
यह इस प्रकार है कि, अधिकतम (पूर्ण) मान 2 | यह इस प्रकार है कि, अधिकतम (पूर्ण) मान 2<sup>''L''</sup> के ''n × n'' आव्यूह के लिए प्रत्येक प्रविष्टि के लिए, बेरिस एल्गोरिथ्म बिग ओ नोटेशन O(''n<sup>3</sup>'') में चलता है) O(n<sup>n/2</sup> 2<sup>nL</sup>) के साथ प्रारंभिक संचालन आवश्यक मध्यवर्ती मूल्यों के पूर्ण मूल्य पर बाध्य है। इस प्रकार इसकी कम्प्यूटेशनल सम्मिश्रता O(''n<sup>5</sup> L<sup>2</sup>'') (l''og(n)<sup>2</sup>+L<sup>2</sup>'')) हैl प्राथमिक अंकगणित या O(''n''<sup>4</sup>L) (log(''n'') + L) log(log(''n'') + L))का उपयोग करते समय तेज गुणन का उपयोग करके। | ||
==संदर्भ== | ==संदर्भ == | ||
{{reflist}} | {{reflist}} | ||
Revision as of 16:39, 29 July 2023
गणित में, बेरिस एल्गोरिथ्म (बेरिस कलन विधि), जिसका नाम इरविन बेरेज़ के नाम पर रखा गया है, केवल पूर्णांक अंकगणित का उपयोग करके पूर्णांक प्रविष्टियों के साथ आव्यूह (गणित) के निर्धारक या सोपानक रूप की गणना करने के लिए एक एल्गोरिदम है; किया गया कोई भी विभाजन (गणित) सटीक होने की गारंटी है (कोई शेष नहीं है)। विधि का उपयोग (अनुमानित) वास्तविक संख्या प्रविष्टियों के साथ आव्यूह के निर्धारक की गणना करने के लिए भी किया जा सकता है, जिससे इनपुट में पहले से उपस्थित त्रुटियों से परे किसी भी राउंड-ऑफ त्रुटियों की प्रांरम्भ से बचा जा सके।
इतिहास
सामान्य बेरिस एल्गोरिदम टोएप्लिट्ज़ आव्यूह के लिए बेरिस एल्गोरिदम से अलग है।
कुछ स्पैनिश भाषी देशों में, इस एल्गोरिदम को बेरिस-मोंटांटे के नाम से भी जाना जाता है, क्योंकि मेक्सिको के यूनिवर्सिडैड ऑटोनोमा डी नुएवो लियोन के प्रोफेसर रेने मारियो मोंटेंटे पार्डो ने इस पद्धति को अपने छात्रों के बीच लोकप्रिय बनाया।
अवलोकन
निर्धारक परिभाषा में केवल गुणा, जोड़ और घटाव संक्रियाएँ होती हैं। यदि सभी आव्यूह प्रविष्टियाँ पूर्णांक हैं तो स्पष्ट रूप से निर्धारक पूर्णांक है। हालाँकि परिभाषा या लीबनिज़_फॉर्मूला_फॉर_डिटर्मिनेंट्स का उपयोग करके निर्धारक की वास्तविक गणना अव्यावहारिक है, क्योंकि इसके लिए O(n!) संचालन की आवश्यकता होती है।
गाऊसी_उन्मूलन कंप्यूटिंग_निर्धारकों में O(n3) है) सम्मिश्रता, लेकिन विभाजन का परिचय देती है, जिसके परिणामस्वरूप फ़्लोटिंग पॉइंट नंबरों का उपयोग करके कार्यान्वित किए जाने पर राउंड-ऑफ़ त्रुटियां होती हैं।
राउंड-ऑफ एरर (राउंड-ऑफ त्रुटियों) से बचा जा सकता है यदि सभी संख्याओं को फ्लोटिंग पॉइंट के बजाय पूर्णांक अंश के रूप में रखा जाए। लेकिन फिर प्रत्येक तत्व का आकार पंक्तियों की संख्या के साथ तेजी से बढ़ता है।[1]
बेरिस मध्यवर्ती गुणांकों के परिमाण को यथोचित रूप से छोटा रखते हुए एक पूर्णांक-संरक्षण विलोपन करने का प्रश्न उठाता है। दो एल्गोरिदम सुझाए गए हैं:[2][3]
- डिवीजन-मुक्त एल्गोरिदम - बिना किसी डिवीजन ऑपरेशन के त्रिकोणीय रूप में आव्यूह कटौती करता है।
- भिन्न-मुक्त एल्गोरिथ्म - मध्यवर्ती प्रविष्टियों को छोटा रखने के लिए विभाजन का उपयोग करता है, लेकिन सिल्वेस्टर की पहचान के कारण परिवर्तन अभी भी पूर्णांक-संरक्षित है (विभाजन में शून्य शेष है)।
पूर्णता के लिए बेरिस भिन्न-उत्पादक गुणन-मुक्त उन्मूलन विधियों का भी सुझाव देते हैं।[2]
एल्गोरिदम
इस एल्गोरिदम की प्रोग्राम संरचना एक सरल ट्रिपल-लूप है, जैसा कि मानक गाऊसी उन्मूलन में होता है। हालाँकि इस स्थिति में आव्यूह को संशोधित किया गया है ताकि प्रत्येक Mk,k प्रविष्टि में प्रमुख प्रमुख माइनर_(रैखिक_बीजगणित) शामिल है [M]k,k. एल्गोरिथम की शुद्धता आसानी से इंडक्शन द्वारा दिखाई जाती है k.[4]
- इनपुट: M - एक n-वर्ग मैट्रिक्स
इसके प्रमुख प्रमुख नाबालिगों को मानते हुए [M]k,k सभी गैर-शून्य हैं. - मान लीजिये M0,0 = 1 (नोट: M0,0 एक विशेष चर है)
- के लिए k 1 से n−1:
- के लिए i से k+1 से n:
- के लिए j से k+1 से n:
- तय करना
- के लिए j से k+1 से n:
- के लिए i से k+1 से n:
- आउटपुट: आव्यूह को In-place_algorithm|in-place,
प्रत्येक में संशोधित किया गया है Mk,k प्रविष्टि में प्रमुख लघु सम्मिलित है [M]k,k,
प्रविष्टि Mn,n में मूल का निर्धारक सम्मिलित है M.
यदि प्रमुख अवयस्कों के बारे में धारणा गलत साबित होती है, उदाहरण के लिए अगर Mk−1,k−1 = 0 और कुछ Mi,k−1 ≠ 0 (i = k,...,n) तो हम विनिमय कर सकते हैं k−1-वीं पंक्ति के साथ i-वीं पंक्ति और अंतिम उत्तर का चिह्न बदलें।
विश्लेषण
बेरिस एल्गोरिथ्म के निष्पादन के दौरान, गणना किया जाने वाला प्रत्येक पूर्णांक इनपुट आव्यूह के उपाव्यूह का निर्धारक होता है। यह हैडामर्ड असमानता का उपयोग करके, इन पूर्णांकों के आकार को सीमित करने की अनुमति देता है। अन्यथा, बेरिस एल्गोरिदम को गॉसियन उन्मूलन के एक प्रकार के रूप में देखा जा सकता है और इसके लिए लगभग समान संख्या में अंकगणितीय परिचालन की आवश्यकता होती है।
यह इस प्रकार है कि, अधिकतम (पूर्ण) मान 2L के n × n आव्यूह के लिए प्रत्येक प्रविष्टि के लिए, बेरिस एल्गोरिथ्म बिग ओ नोटेशन O(n3) में चलता है) O(nn/2 2nL) के साथ प्रारंभिक संचालन आवश्यक मध्यवर्ती मूल्यों के पूर्ण मूल्य पर बाध्य है। इस प्रकार इसकी कम्प्यूटेशनल सम्मिश्रता O(n5 L2) (log(n)2+L2)) हैl प्राथमिक अंकगणित या O(n4L) (log(n) + L) log(log(n) + L))का उपयोग करते समय तेज गुणन का उपयोग करके।
संदर्भ
- ↑ Middeke, J.; Jeffrey, D.J.; Koutschan, C. (2020), "Common Factors in Fraction-Free Matrix Decompositions", Mathematics in Computer Science, 15 (4): 589–608, arXiv:2005.12380, doi:10.1007/s11786-020-00495-9
- ↑ 2.0 2.1 Bareiss, Erwin H. (1968), "Sylvester's Identity and multistep integer-preserving Gaussian elimination" (PDF), Mathematics of Computation, 22 (103): 565–578, doi:10.2307/2004533, JSTOR 2004533
- ↑ Bareiss, Erwin H. (1966), MULTISTEP INTEGER-PRESERVING GAUSSIAN ELIMINATION (PDF). (Contains a clearer picture of the operations sequence)
- ↑ Yap, Chee Keng (2000), Fundamental Problems of Algorithmic Algebra, Oxford University Press
