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

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

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

औपचारिक रूप से, मान लीजिए कि A वास्तविक मैट्रिक्स है जिसके eigenvalues ​​​​की गणना हम करना चाहते हैं, और A को मान लीजिए₀:=ए. K-वें चरण पर (k = 0 से शुरू करके), हम QR अपघटन 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 समान मैट्रिक्स हैं और इसलिए उनके eigenvalues ​​​​समान हैं। एल्गोरिथ्म संख्यात्मक स्थिरता है क्योंकि यह ऑर्थोगोनल समानता परिवर्तनों द्वारा आगे बढ़ता है।

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

इस कच्चे रूप में पुनरावृत्तियाँ अपेक्षाकृत महंगी हैं। इसे पहले मैट्रिक्स ए को ऊपरी हेसेनबर्ग फॉर्म में लाकर कम किया जा सकता है (जिसकी लागत है ${\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)$ परिचालन. अभिसरण की दर eigenvalues ​​​​के बीच अलगाव पर निर्भर करती है, इसलिए व्यावहारिक एल्गोरिदम अलगाव को बढ़ाने और अभिसरण में तेजी लाने के लिए स्पष्ट या अंतर्निहित बदलावों का उपयोग करेगा। विशिष्ट सममित क्यूआर एल्गोरिदम केवल या दो पुनरावृत्तियों के साथ प्रत्येक eigenvalue को अलग करता है (फिर मैट्रिक्स के आकार को कम करता है), जिससे यह कुशल और मजबूत हो जाता है।

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

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

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

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

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

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

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

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

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

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

आधुनिक कम्प्यूटेशनल अभ्यास में, क्यूआर एल्गोरिदम को अंतर्निहित संस्करण में निष्पादित किया जाता है जो कई बदलावों के उपयोग को शुरू करना आसान बनाता है।मैट्रिक्स को पहले ऊपरी हेसेनबर्ग फॉर्म में लाया जाता है $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 }}$ अनुगामी के दो eigenvalues ​​हैं $2\times 2$ का प्रमुख सबमैट्रिक्स $A_{k}$, तथाकथित अंतर्निहित डबल-शिफ्ट)। फिर आकार का क्रमिक गृहस्वामी परिवर्तन $r+1$ कार्यशील मैट्रिक्स को वापस करने के लिए किया जाता है $A_{k}$ ऊपरी हेसेनबर्ग रूप में। एल्गोरिदम के चरणों के साथ मैट्रिक्स की गैर-शून्य प्रविष्टियों के अजीब आकार के कारण, इस ऑपरेशन को उभार पीछा के रूप में जाना जाता है। पहले संस्करण की तरह, उप-विकर्ण प्रविष्टियों में से के रूप में ही अपस्फीति का प्रदर्शन किया जाता है $A_{k}$ पर्याप्त रूप से छोटा है.

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

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

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

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

इतिहास

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

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

अन्य प्रकार

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

स्रोत

• 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 QR algorithm by Peter J. Olver
• Module for the QR Method
• C++ Library