क्यूआर एल्गोरिदम

संख्यात्मक रैखिक बीजगणित में, क्युआर एल्गोरिथ्म या क्युआर पुनरावृत्ति आइजेनवैल्यू एल्गोरिथ्म है: अर्थात, आव्युह (गणित) के आइजेनवैल्यू ​​और आइजेनवेक्टर की गणना करने की प्रक्रिया। क्यूआर एल्गोरिदम को 1950 के दशक के अंत में जॉन जी.एफ. फ्रांसिस और वेरा एन. कुब्लानोव्स्काया द्वारा स्वतंत्र रूप से काम करते हुए विकसित किया गया था। मूल विचार क्यूआर अपघटन करना है, आव्युह को ऑर्थोगोनल आव्युह और ऊपरी त्रिकोणीय आव्युह के उत्पाद के रूप में लिखना, कारकों को रिवर्स ऑर्डर में गुणा करना और पुनरावृत्त करना है।

व्यावहारिक क्युआर एल्गोरिथ्म

औपचारिक रूप से, मान लीजिए कि A वास्तविक आव्युह है जिसके आइजेनवैल्यू ​​​​की गणना हम करना चाहते हैं, और A को मान लीजिए₀:=ए. K-वें चरण पर (k = 0 से प्रारंभ करके), हम क्युआर अपघटन A की गणना करते हैं_k=प्र_kR_k कहां प्र_k ऑर्थोगोनल आव्युह है (यानी, Q^टी = क्यू⁻¹) और आर_k ऊपरी त्रिकोणीय आव्युह है. फिर हम A बनाते हैं_k+1 = आर_kQ_k. ध्यान दें कि

$$A_{k+1}=R_{k}Q_{k}=Q_{k}^{-1}Q_{k}R_{k}Q_{k}=Q_{k}^{-1}A_{k}Q_{k}=Q_{k}^{\mathsf {T}}A_{k}Q_{k},$$

तो सभी ए_k समान आव्युह हैं और इसलिए उनके आइजेनवैल्यू ​​​​समान हैं। एल्गोरिथ्म संख्यात्मक स्थिरता है क्योंकि यह ऑर्थोगोनल समानता परिवर्तनों द्वारा आगे बढ़ता है।

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

इस कच्चे रूप में पुनरावृत्तियाँ अपेक्षाकृत महंगी हैं। इसे पहले आव्युह ए को ऊपरी हेसेनबर्ग रूप में लाकर कम किया जा सकता है (जिसकी लागत है ${\begin{matrix}{\frac {10}{3}}\end{matrix}}n^{3}+{\mathcal {O}}(n^{2})$ घरेलू परिवर्तन पर आधारित तकनीक का उपयोग करके अंकगणितीय संचालन), ऑर्थोगोनल समानता परिवर्तनों के सीमित अनुक्रम के साथ, कुछ हद तक दो-तरफा क्यूआर अपघटन की तरह। (क्यूआर अपघटन के लिए, हाउसहोल्डर रिफ्लेक्टर को केवल बाईं ओर गुणा किया जाता है, लेकिन हेसेनबर्ग मामले के लिए उन्हें बाएं और दाएं दोनों पर गुणा किया जाता है।) ऊपरी हेसेनबर्ग आव्युह लागत के क्यूआर अपघटन का निर्धारण $6n^{2}+{\mathcal {O}}(n)$ अंकगणितीय आपरेशनस। इसके अलावा, क्योंकि हेसेनबर्ग रूप पहले से ही लगभग ऊपरी-त्रिकोणीय है (इसमें प्रत्येक विकर्ण के नीचे केवल गैर-शून्य प्रविष्टि है), इसे शुरुआती बिंदु के रूप में उपयोग करने से क्यूआर एल्गोरिदम के अभिसरण के लिए आवश्यक चरणों की संख्या कम हो जाती है।

यदि मूल आव्युह सममित आव्युह है, तो ऊपरी हेसेनबर्ग आव्युह भी सममित है और इस प्रकार त्रिविकर्ण आव्युह है, और सभी ए भी हैं_k. इस प्रक्रिया में लागत आती है ${\begin{matrix}{\frac {4}{3}}\end{matrix}}n^{3}+{\mathcal {O}}(n^{2})$ हाउसहोल्डर रिडक्शन पर आधारित तकनीक का उपयोग करके अंकगणितीय परिचालन।एक सममित त्रिविकर्ण आव्युह लागत के क्यूआर अपघटन का निर्धारण ${\mathcal {O}}(n)$ परिचालन. अभिसरण की दर आइजेनवैल्यू ​​​​के बीच अलगाव पर निर्भर करती है, इसलिए व्यावहारिक एल्गोरिदम अलगाव को बढ़ाने और अभिसरण में तेजी लाने के लिए स्पष्ट या अंतर्निहित बदलावों का उपयोग करेगा। विशिष्ट सममित क्यूआर एल्गोरिदम केवल या दो पुनरावृत्तियों के साथ प्रत्येक आइजेनवैल्यू को अलग करता है (फिर आव्युह के आकार को कम करता है), जिससे यह कुशल और मजबूत हो जाता है।

विज़ुअलाइज़ेशन

चित्र 1: क्यूआर या एलआर एल्गोरिथ्म के एकल पुनरावृत्ति का आउटपुट उसके इनपुट के साथ कैसे भिन्न होता है

मूल क्यूआर एल्गोरिदम की कल्पना उस स्थिति में की जा सकती है जहां ए सकारात्मक-निश्चित सममित आव्युह है। उस स्थिति में, A को 2 आयामों में दीर्घवृत्त या उच्च आयामों में दीर्घवृत्त के रूप में दर्शाया जा सकता है। एल्गोरिथम के इनपुट और एकल पुनरावृत्ति के बीच संबंध को चित्र 1 (एनीमेशन देखने के लिए क्लिक करें) के रूप में दर्शाया जा सकता है। ध्यान दें कि एलआर एल्गोरिदम को क्यूआर एल्गोरिदम के साथ दर्शाया गया है।

एक एकल पुनरावृत्ति के कारण दीर्घवृत्त x-अक्ष की ओर झुक जाता है या गिर जाता है। ऐसी स्थिति में जहां दीर्घवृत्त का बड़ा अर्ध-प्रमुख और अर्ध-लघु अक्ष | अर्ध-अक्ष x-अक्ष के समानांतर है, क्युआर का पुनरावृत्ति कुछ नहीं करता है। और स्थिति जहां एल्गोरिदम कुछ नहीं करता है वह यह है कि जब बड़ा अर्ध-अक्ष x-अक्ष के बजाय y-अक्ष के समानांतर होता है। उस घटना में, दीर्घवृत्त को किसी भी दिशा में गिरने में सक्षम हुए बिना अनिश्चित रूप से संतुलन बनाने के रूप में सोचा जा सकता है। दोनों स्थितियों में, आव्युह विकर्ण है। ऐसी स्थिति जहां एल्गोरिथम की पुनरावृत्ति कुछ नहीं करती, उसे निश्चित बिंदु (गणित) कहा जाता है। एल्गोरिथम द्वारा नियोजित रणनीति निश्चित-बिंदु पुनरावृत्ति|एक निश्चित-बिंदु की ओर पुनरावृत्ति है। ध्यान दें कि निश्चित बिंदु स्थिर है जबकि दूसरा अस्थिर है। यदि दीर्घवृत्त को अस्थिर निश्चित बिंदु से बहुत कम मात्रा में झुकाया जाता है, तो क्यूआर के पुनरावृत्ति के कारण दीर्घवृत्त निश्चित बिंदु की ओर झुकने के बजाय दूर झुक जाएगा। चूँकि अंततः, एल्गोरिदम अलग निश्चित बिंदु पर परिवर्तित हो जाएगा, लेकिन इसमें लंबा समय लगेगा।

आइजनवैल्यू ढूंढना बनाम आइजेनवेक्टर ढूंढना

चित्र 2: जब दो आइजेनवैल्यू ​​​​एक दूसरे के पास आते हैं तो क्युआर या LR के एकल पुनरावृत्ति का आउटपुट कैसे प्रभावित होता है

यह इंगित करने योग्य है कि सममित आव्युह का भी आइजनवेक्टर ढूंढना गणना योग्य नहीं है (गणना योग्य विश्लेषण में परिभाषाओं के अनुसार सटीक वास्तविक अंकगणित में)। यह कठिनाई तब मौजूद होती है जब किसी आव्युह के आइजेनवैल्यू ​​​​की बहुलताएं जानने योग्य नहीं होती हैं। दूसरी ओर, आइजेनवैल्यू ​​​​खोजने के लिए वही समस्या मौजूद नहीं है। आव्युह के आइजेनवैल्यू ​​​​हमेशा गणना योग्य होते हैं।

अब हम चर्चा करेंगे कि बुनियादी क्यूआर एल्गोरिदम में ये कठिनाइयाँ कैसे प्रकट होती हैं। इसे चित्र 2 में दर्शाया गया है। (थंबनेल पर क्लिक करना याद रखें)। याद रखें कि दीर्घवृत्त सकारात्मक-निश्चित सममित आव्युह का प्रतिनिधित्व करते हैं। जैसे ही इनपुट आव्युह के दो आइगेनवैल्यू एक-दूसरे के करीब आते हैं, इनपुट दीर्घवृत्त सर्कल में बदल जाता है। वृत्त पहचान आव्युह के गुणज से मेल खाता है। निकट-वृत्त पहचान आव्युह के निकट-गुणक से मेल खाता है जिसका आइजेनवैल्यू ​​​​आव्युह की विकर्ण प्रविष्टियों के लगभग बराबर है। इसलिए उस मामले में लगभग आइजेनवैल्यू ​​​​खोजने की समस्या आसान दिखाई देती है। लेकिन ध्यान दें कि दीर्घवृत्त के अर्ध-अक्षों का क्या होता है। क्यूआर (या एलआर) की पुनरावृत्ति अर्ध-अक्षों को कम से कम झुकाती है क्योंकि इनपुट दीर्घवृत्त वृत्त होने के करीब पहुंचता है। आइजनवेक्टर केवल तभी ज्ञात हो सकते हैं जब अर्ध-अक्ष x-अक्ष और y-अक्ष के समानांतर हों। निकट-समानांतरता प्राप्त करने के लिए आवश्यक पुनरावृत्तियों की संख्या बिना किसी सीमा के बढ़ जाती है क्योंकि इनपुट दीर्घवृत्त अधिक गोलाकार हो जाता है।

हालांकि मनमाना सममित आव्युह के आव्युह के ईजेंडेकंपोजिशन की गणना करना असंभव हो सकता है, आव्युह को इच्छानुसार छोटी राशि से परेशान करना और परिणामी आव्युह के ईजेंडेकंपोजीशन की गणना करना हमेशा संभव होता है। ऐसे मामले में जब आव्युह को निकट-वृत्त के रूप में दर्शाया गया है, आव्युह को उस आव्युह से बदला जा सकता है जिसका चित्रण पूर्ण वृत्त है। उस स्थिति में, आव्युह पहचान आव्युह का गुणक है, और इसका आइजेनडीकम्पोजिसन तत्काल है। चूँकि सावधान रहें कि परिणामी अपना आधार मूल आइजेनबासिस से काफी दूर हो सकता है।

अंतर्निहित क्यूआर एल्गोरिदम

आधुनिक कम्प्यूटेशनल अभ्यास में, क्यूआर एल्गोरिदम को अंतर्निहित संस्करण में निष्पादित किया जाता है जो कई बदलावों के उपयोग को प्रारंभ करना आसान बनाता है। आव्युह को पहले ऊपरी हेसेनबर्ग रूप में लाया जाता है $A_{0}=QAQ^{\mathsf {T}}$ जैसा कि स्पष्ट संस्करण में है; फिर, प्रत्येक चरण पर, का पहला कॉलम $A_{k}$ के पहले कॉलम में छोटे आकार के घरेलू समानता परिवर्तन के माध्यम से रूपांतरित किया गया है $p(A_{k})$ (या $p(A_{k})e_{1}$), कहाँ $p(A_{k})$, डिग्री का $r$, वह बहुपद है जो स्थानांतरण रणनीति को परिभाषित करता है (अक्सर $p(x)=(x-\lambda )(x-{\bar {\lambda }})$, कहाँ $\lambda$ और ${\bar {\lambda }}$ अनुगामी के दो आइजेनवैल्यू ​​हैं $2\times 2$ का प्रमुख सबआव्युह $A_{k}$, तथाकथित अंतर्निहित डबल-शिफ्ट)। फिर आकार का क्रमिक गृहस्वामी परिवर्तन $r+1$ कार्यशील आव्युह को वापस करने के लिए किया जाता है $A_{k}$ ऊपरी हेसेनबर्ग रूप में। एल्गोरिदम के चरणों के साथ आव्युह की गैर-शून्य प्रविष्टियों के अजीब आकार के कारण, इस ऑपरेशन को उभार पीछा के रूप में जाना जाता है। पहले संस्करण की तरह, उप-विकर्ण प्रविष्टियों में से के रूप में ही अपस्फीति का प्रदर्शन किया जाता है $A_{k}$ पर्याप्त रूप से छोटा है.

नाम बदलने का प्रस्ताव

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

व्याख्या और अभिसरण

क्यूआर एल्गोरिदम को बुनियादी पावर पुनरावृत्ति के अधिक परिष्कृत बदलाव के रूप में देखा जा सकता है पावर आइजेनवैल्यू एल्गोरिदम। याद रखें कि पावर एल्गोरिदम बार-बार वेक्टर को ए से गुणा करता है, प्रत्येक पुनरावृत्ति के बाद सामान्य हो जाता है। वेक्टर सबसे बड़े आइजेनवैल्यू के आइजेनवेक्टर में परिवर्तित हो जाता है। इसके बजाय, क्यूआर एल्गोरिदम वैक्टर के पूर्ण आधार के साथ काम करता है, क्यूआर अपघटन का उपयोग करके पुनर्सामान्यीकरण (और ऑर्थोगोनलाइज़) करता है। सममित आव्युह A के लिए, अभिसरण पर, AQ = QΛ, जहां Λ आइजेनवैल्यू ​​​​का विकर्ण आव्युह है जिसमें A अभिसरण करता है, और जहां Q वहां पहुंचने के लिए आवश्यक सभी ऑर्थोगोनल समानता परिवर्तनों का संयोजन है। इस प्रकार Q के कॉलम आइजेनवेक्टर हैं।

इतिहास

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

एलआर एल्गोरिथ्म को 1950 के दशक की शुरुआत में हेंज रूटीशौसर द्वारा विकसित किया गया था, जो उस समय ईटीएच ज्यूरिख में एडवर्ड बूट्स के अनुसंधान सहायक के रूप में काम करते थे। स्टिफ़ेल ने सुझाव दिया कि रूटीशौसर क्षणों y के अनुक्रम का उपयोग करें₀^टीए^कx₀, k = 0, 1, … (जहाँ x₀ और य₀ इच्छानुसार वेक्टर हैं) ए के आइजेनवैल्यू ​​​​को खोजने के लिए। रुतिशौसर ने इस कार्य के लिए अलेक्जेंडर ऐटकेन का एल्गोरिदम लिया और इसे भागफल-अंतर एल्गोरिदम या क्यूडी एल्गोरिदम में विकसित किया। गणना को उपयुक्त आकार में व्यवस्थित करने के बाद, उन्होंने पाया कि क्यूडी एल्गोरिदम वास्तव में पुनरावृत्ति ए है_k = एल_kU_k (एलयू अपघटन), ए_k+1 = यू_kL_k, त्रिविकर्ण आव्युह पर लागू किया जाता है, जिसमें से एलआर एल्गोरिदम अनुसरण करता है।

अन्य प्रकार

क्यूआर एल्गोरिथ्म का प्रकार, गोलूब-कहान-रीन्स्च एल्गोरिथ्म सामान्य आव्युह को द्विभुजीय आव्युह में कम करने के साथ प्रारंभ होता है। एकवचन मानों की गणना के लिए क्युआर एल्गोरिदम के इस संस्करण का वर्णन सबसे पहले किसके द्वारा किया गया था? गोलुब & कहन (1965). लापैक सबरूटीन डीबीडीएसयूआर उस मामले को कवर करने के लिए कुछ संशोधनों के साथ इस पुनरावृत्त विधि को कार्यान्वित करता है जहां एकवचन मान बहुत छोटे होते हैं (डेमेल & कहन 1990). हाउसहोल्डर रिफ्लेक्शन और, यदि उपयुक्त हो, क्यूआर अपघटन का उपयोग करते हुए पहले चरण के साथ, यह एकवचन मूल्य अपघटन की गणना के लिए डीजीईएसवीडी रूटीन बनाता है। क्यूआर एल्गोरिदम को संबंधित अभिसरण परिणामों के साथ अनंत आयामों में भी लागू किया जा सकता है।

स्रोत

• Demmel, James; Kahan, William (1990). "द्विदिशकोणीय आव्यूहों का सटीक एकवचन मान". SIAM Journal on Scientific and Statistical Computing. 11 (5): 873–912. CiteSeerX 10.1.1.48.3740. doi:10.1137/0911052.
• Golub, Gene H.; Kahan, William (1965). "किसी मैट्रिक्स के एकवचन मानों और छद्म-व्युत्क्रम की गणना करना". Journal of the Society for Industrial and Applied Mathematics, Series B: Numerical Analysis. 2 (2): 205–224. Bibcode:1965SJNA....2..205G. doi:10.1137/0702016. JSTOR 2949777.

बाहरी संबंध

• Eigenvalue problem at PlanetMath.
• Notes on orthogonal bases and the workings of the क्युआर algorithm by Peter J. Olver
• Module for the क्युआर Method
• C++ Library