क्यूआर एल्गोरिदम: Difference between revisions

Revision as of 13:30, 29 July 2023

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

व्यावहारिक 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 समान हैं। एल्गोरिथ्म संख्यात्मक स्थिरता है क्योंकि यह ऑर्थोगोनल समानता परिवर्तनों द्वारा आगे बढ़ता है।

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

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

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

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

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

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

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

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

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

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

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

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

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

आधुनिक कम्प्यूटेशनल अभ्यास में, क्यूआर एल्गोरिदम को अंतर्निहित संस्करण में निष्पादित किया जाता है जो कई बदलावों के उपयोग को शुरू करना आसान बनाता है।^[4]मैट्रिक्स को पहले ऊपरी हेसेनबर्ग फॉर्म में लाया जाता है $A_{0}=QAQ^{\mathsf {T}}$ जैसा कि स्पष्ट संस्करण में है; फिर, प्रत्येक चरण पर, का पहला कॉलम $A_{k}$ के पहले कॉलम में छोटे आकार के घरेलू समानता परिवर्तन के माध्यम से रूपांतरित किया गया है $p(A_{k})$ ^{[clarification needed]} (या $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}$ पर्याप्त रूप से छोटा है.

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

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

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

क्यूआर एल्गोरिदम को बुनियादी पावर पुनरावृत्ति के अधिक परिष्कृत बदलाव के रूप में देखा जा सकता है पावर आइजेनवैल्यू एल्गोरिदम। याद रखें कि पावर एल्गोरिदम बार-बार वेक्टर को ए से गुणा करता है, प्रत्येक पुनरावृत्ति के बाद सामान्य हो जाता है। वेक्टर सबसे बड़े 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, त्रिविकर्ण मैट्रिक्स पर लागू किया जाता है, जिसमें से एलआर एल्गोरिदम अनुसरण करता है।^[10]

अन्य प्रकार

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

संदर्भ

↑ J.G.F. Francis, "The QR Transformation, I", The Computer Journal, 4(3), pages 265–271 (1961, received October 1959). doi:10.1093/comjnl/4.3.265
↑ Francis, J. G. F. (1962). "क्यूआर परिवर्तन, II". The Computer Journal. 4 (4): 332–345. doi:10.1093/comjnl/4.4.332.
↑ Vera N. Kublanovskaya, "On some algorithms for the solution of the complete eigenvalue problem," USSR Computational Mathematics and Mathematical Physics, vol. 1, no. 3, pages 637–657 (1963, received Feb 1961). Also published in: Zhurnal Vychislitel'noi Matematiki i Matematicheskoi Fiziki, vol.1, no. 4, pages 555–570 (1961). doi:10.1016/0041-5553(63)90168-X
↑ ^4.0 ^4.1 Golub, G. H.; Van Loan, C. F. (1996). मैट्रिक्स संगणना (3rd ed.). Baltimore: Johns Hopkins University Press. ISBN 0-8018-5414-8.
↑ ^5.0 ^5.1 Demmel, James W. (1997). अनुप्रयुक्त संख्यात्मक रैखिक बीजगणित. SIAM.
↑ ^6.0 ^6.1 Trefethen, Lloyd N.; Bau, David (1997). संख्यात्मक रैखिक बीजगणित. SIAM.
↑ Ortega, James M.; Kaiser, Henry F. (1963). "The LL^T and QR methods for symmetric tridiagonal matrices". The Computer Journal. 6 (1): 99–101. doi:10.1093/comjnl/6.1.99.
↑ "linear algebra - Why is uncomputability of the spectral decomposition not a problem?". MathOverflow. Retrieved 2021-08-09.
↑ Watkins, David S. (2007). The Matrix Eigenvalue Problem: GR and Krylov Subspace Methods. Philadelphia, PA: SIAM. ISBN 978-0-89871-641-2.
↑ Parlett, Beresford N.; Gutknecht, Martin H. (2011), "From qd to LR, or, how were the qd and LR algorithms discovered?" (PDF), IMA Journal of Numerical Analysis, 31 (3): 741–754, doi:10.1093/imanum/drq003, hdl:20.500.11850/159536, ISSN 0272-4979
↑ Bochkanov Sergey Anatolyevich. ALGLIB User Guide - General Matrix operations - Singular value decomposition . ALGLIB Project. 2010-12-11. URL:[1] Accessed: 2010-12-11. (Archived by WebCite at https://www.webcitation.org/5utO4iSnR?url=http://www.alglib.net/matrixops/general/svd.php
↑ Deift, Percy; Li, Luenchau C.; Tomei, Carlos (1985). "टोडा अनंत अनेक चरों के साथ बहती है". Journal of Functional Analysis. 64 (3): 358–402. doi:10.1016/0022-1236(85)90065-5.
↑ Colbrook, Matthew J.; Hansen, Anders C. (2019). "अनंत-आयामी क्यूआर एल्गोरिदम पर". Numerische Mathematik. 143 (1): 17–83. arXiv:2011.08172. doi:10.1007/s00211-019-01047-5.

स्रोत

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.

बाहरी संबंध

[1] J.G.F. Francis, "The QR Transformation, I", The Computer Journal, 4(3), pages 265–271 (1961, received October 1959). doi:10.1093/comjnl/4.3.265

[2] Francis, J. G. F. (1962). "क्यूआर परिवर्तन, II". The Computer Journal. 4 (4): 332–345. doi:10.1093/comjnl/4.4.332.

[3] Vera N. Kublanovskaya, "On some algorithms for the solution of the complete eigenvalue problem," USSR Computational Mathematics and Mathematical Physics, vol. 1, no. 3, pages 637–657 (1963, received Feb 1961). Also published in: Zhurnal Vychislitel'noi Matematiki i Matematicheskoi Fiziki, vol.1, no. 4, pages 555–570 (1961). doi:10.1016/0041-5553(63)90168-X

[golubvanloan-4] 4.0 ^4.1 Golub, G. H.; Van Loan, C. F. (1996). मैट्रिक्स संगणना (3rd ed.). Baltimore: Johns Hopkins University Press. ISBN 0-8018-5414-8.

[Demmel-5] 5.0 ^5.1 Demmel, James W. (1997). अनुप्रयुक्त संख्यात्मक रैखिक बीजगणित. SIAM.

[Trefethen-6] 6.0 ^6.1 Trefethen, Lloyd N.; Bau, David (1997). संख्यात्मक रैखिक बीजगणित. SIAM.

[7] Ortega, James M.; Kaiser, Henry F. (1963). "The LL^T and QR methods for symmetric tridiagonal matrices". The Computer Journal. 6 (1): 99–101. doi:10.1093/comjnl/6.1.99.

[8] "linear algebra - Why is uncomputability of the spectral decomposition not a problem?". MathOverflow. Retrieved 2021-08-09.

[9] Watkins, David S. (2007). The Matrix Eigenvalue Problem: GR and Krylov Subspace Methods. Philadelphia, PA: SIAM. ISBN 978-0-89871-641-2.

[10] Parlett, Beresford N.; Gutknecht, Martin H. (2011), "From qd to LR, or, how were the qd and LR algorithms discovered?" (PDF), IMA Journal of Numerical Analysis, 31 (3): 741–754, doi:10.1093/imanum/drq003, hdl:20.500.11850/159536, ISSN 0272-4979

[11] Bochkanov Sergey Anatolyevich. ALGLIB User Guide - General Matrix operations - Singular value decomposition . ALGLIB Project. 2010-12-11. URL:[1] Accessed: 2010-12-11. (Archived by WebCite at https://www.webcitation.org/5utO4iSnR?url=http://www.alglib.net/matrixops/general/svd.php

[12] Deift, Percy; Li, Luenchau C.; Tomei, Carlos (1985). "टोडा अनंत अनेक चरों के साथ बहती है". Journal of Functional Analysis. 64 (3): 358–402. doi:10.1016/0022-1236(85)90065-5.

[13] Colbrook, Matthew J.; Hansen, Anders C. (2019). "अनंत-आयामी क्यूआर एल्गोरिदम पर". Numerische Mathematik. 143 (1): 17–83. arXiv:2011.08172. doi:10.1007/s00211-019-01047-5.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

@@ Line 1: / Line 1: @@
-{{Short description|Algorithm to calculate eigenvalues}} }
+{{Short description|Algorithm to calculate eigenvalues}}
-[[संख्यात्मक रैखिक बीजगणित]] में, QR एल्गोरिथ्म या QR पुनरावृत्ति एक [[eigenvalue एल्गोरिथ्म]] है: अर्थात, एक [[मैट्रिक्स (गणित)]] के eigenvalues और eigenvectors की गणना करने की एक प्रक्रिया। क्यूआर एल्गोरिदम को 1950 के दशक के अंत में जॉन जी.एफ. फ्रांसिस और वेरा एन. कुब्लानोव्स्काया द्वारा स्वतंत्र रूप से काम करते हुए विकसित किया गया था।<ref>J.G.F. Francis, "The QR Transformation, I", ''[[The Computer Journal]]'', '''4'''(3), pages 265&ndash;271 (1961, received October 1959). [[doi:10.1093/comjnl/4.3.265]]</ref><ref>{{cite journal |first=J. G. F. |last=Francis |title=क्यूआर परिवर्तन, II|journal=The Computer Journal |volume=4 |issue=4 |pages=332–345 |year=1962 |doi=10.1093/comjnl/4.4.332 |doi-access=free }}</ref><ref>
+[[संख्यात्मक रैखिक बीजगणित]] में, QR एल्गोरिथ्म या QR पुनरावृत्ति [[eigenvalue एल्गोरिथ्म]] है: अर्थात, [[मैट्रिक्स (गणित)]] के eigenvalues और eigenvectors की गणना करने की प्रक्रिया। क्यूआर एल्गोरिदम को 1950 के दशक के अंत में जॉन जी.एफ. फ्रांसिस और वेरा एन. कुब्लानोव्स्काया द्वारा स्वतंत्र रूप से काम करते हुए विकसित किया गया था।<ref>J.G.F. Francis, "The QR Transformation, I", ''[[The Computer Journal]]'', '''4'''(3), pages 265&ndash;271 (1961, received October 1959). [[doi:10.1093/comjnl/4.3.265]]</ref><ref>{{cite journal |first=J. G. F. |last=Francis |title=क्यूआर परिवर्तन, II|journal=The Computer Journal |volume=4 |issue=4 |pages=332–345 |year=1962 |doi=10.1093/comjnl/4.4.332 |doi-access=free }}</ref><ref>
 Vera N. Kublanovskaya, "On some algorithms for the solution of the complete eigenvalue problem," ''USSR Computational Mathematics and Mathematical Physics'', vol. 1, no. 3, pages 637–657 (1963, received Feb 1961). Also published in: ''Zhurnal Vychislitel'noi Matematiki i Matematicheskoi Fiziki'', vol.1, no. 4, pages 555–570 (1961). [[doi:10.1016/0041-5553(63)90168-X]]</ref> मूल विचार [[क्यूआर अपघटन]] करना है, मैट्रिक्स को [[ऑर्थोगोनल मैट्रिक्स]] और ऊपरी [[त्रिकोणीय मैट्रिक्स]] के उत्पाद के रूप में लिखना, कारकों को रिवर्स ऑर्डर में गुणा करना और पुनरावृत्त करना है।
 ==व्यावहारिक QR एल्गोरिथ्म==
-औपचारिक रूप से, मान लीजिए कि A एक वास्तविक मैट्रिक्स है जिसके eigenvalues की गणना हम करना चाहते हैं, और A को मान लीजिए<sub>0</sub>:=ए. K-वें चरण पर (k = 0 से शुरू करके), हम QR अपघटन A की गणना करते हैं<sub>''k''</sub>=प्र<sub>''k''</sub>R<sub>''k''</sub> कहां प्र<sub>''k''</sub> एक ऑर्थोगोनल मैट्रिक्स है (यानी, Q<sup>टी</sup> = क्यू<sup>−1</sup>) और आर<sub>''k''</sub> एक ऊपरी त्रिकोणीय मैट्रिक्स है. फिर हम A बनाते हैं<sub>''k''+1</sub> = आर<sub>''k''</sub>Q<sub>''k''</sub>. ध्यान दें कि
+औपचारिक रूप से, मान लीजिए कि A वास्तविक मैट्रिक्स है जिसके eigenvalues की गणना हम करना चाहते हैं, और A को मान लीजिए<sub>0</sub>:=ए. K-वें चरण पर (k = 0 से शुरू करके), हम QR अपघटन A की गणना करते हैं<sub>''k''</sub>=प्र<sub>''k''</sub>R<sub>''k''</sub> कहां प्र<sub>''k''</sub> ऑर्थोगोनल मैट्रिक्स है (यानी, Q<sup>टी</sup> = क्यू<sup>−1</sup>) और आर<sub>''k''</sub> ऊपरी त्रिकोणीय मैट्रिक्स है. फिर हम A बनाते हैं<sub>''k''+1</sub> = आर<sub>''k''</sub>Q<sub>''k''</sub>. ध्यान दें कि
 <math display="block"> 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, </math>
 तो सभी ए<sub>''k''</sub> [[समान मैट्रिक्स]] हैं और इसलिए उनके eigenvalues समान हैं। एल्गोरिथ्म [[संख्यात्मक स्थिरता]] है क्योंकि यह ऑर्थोगोनल समानता परिवर्तनों द्वारा आगे बढ़ता है।
-खास शर्तों के अन्तर्गत,<ref name="golubvanloan">{{cite book |last1=Golub |first1=G. H. |last2=Van Loan |first2=C. F. |title=मैट्रिक्स संगणना|edition=3rd |publisher=Johns Hopkins University Press |location=Baltimore |year=1996 |isbn=0-8018-5414-8 }}</ref> मैट्रिक्स ए<sub>''k''</sub> एक त्रिकोणीय मैट्रिक्स में अभिसरण करें, ए का [[शूर रूप]]। त्रिकोणीय मैट्रिक्स के eigenvalues विकर्ण पर सूचीबद्ध हैं, और eigenvalue समस्या हल हो गई है। अभिसरण के परीक्षण में सटीक शून्य की आवश्यकता अव्यावहारिक है,{{citation needed|date=July 2020}} लेकिन [[गेर्शगोरिन सर्कल प्रमेय]] त्रुटि पर एक सीमा प्रदान करता है।
+खास शर्तों के अन्तर्गत,<ref name="golubvanloan">{{cite book |last1=Golub |first1=G. H. |last2=Van Loan |first2=C. F. |title=मैट्रिक्स संगणना|edition=3rd |publisher=Johns Hopkins University Press |location=Baltimore |year=1996 |isbn=0-8018-5414-8 }}</ref> मैट्रिक्स ए<sub>''k''</sub> त्रिकोणीय मैट्रिक्स में अभिसरण करें, ए का [[शूर रूप]]। त्रिकोणीय मैट्रिक्स के eigenvalues विकर्ण पर सूचीबद्ध हैं, और eigenvalue समस्या हल हो गई है। अभिसरण के परीक्षण में सटीक शून्य की आवश्यकता अव्यावहारिक है,{{citation needed|date=July 2020}} लेकिन [[गेर्शगोरिन सर्कल प्रमेय]] त्रुटि पर सीमा प्रदान करता है।
-इस कच्चे रूप में पुनरावृत्तियाँ अपेक्षाकृत महंगी हैं। इसे पहले मैट्रिक्स ए को ऊपरी [[हेसेनबर्ग फॉर्म]] में लाकर कम किया जा सकता है (जिसकी लागत है <math>\begin{matrix}\frac{10}{3}\end{matrix} n^3 + \mathcal{O}(n^2)</math> घरेलू परिवर्तन पर आधारित तकनीक का उपयोग करके अंकगणितीय संचालन), ऑर्थोगोनल समानता परिवर्तनों के एक सीमित अनुक्रम के साथ, कुछ हद तक दो-तरफा क्यूआर अपघटन की तरह।<ref name=Demmel>{{cite book |first=James W. |last=Demmel |author-link=James W. Demmel |title=अनुप्रयुक्त संख्यात्मक रैखिक बीजगणित|publisher=SIAM |year=1997 }}</ref><ref name=Trefethen>{{cite book |first1=Lloyd N. |last1=Trefethen |author-link=Lloyd N. Trefethen |first2=David |last2=Bau |title=संख्यात्मक रैखिक बीजगणित|publisher=SIAM |year=1997 }}</ref> (क्यूआर अपघटन के लिए, हाउसहोल्डर रिफ्लेक्टर को केवल बाईं ओर गुणा किया जाता है, लेकिन हेसेनबर्ग मामले के लिए उन्हें बाएं और दाएं दोनों पर गुणा किया जाता है।) ऊपरी हेसेनबर्ग मैट्रिक्स लागत के क्यूआर अपघटन का निर्धारण <math>6 n^2 + \mathcal{O}(n)</math> अंकगणितीय आपरेशनस। इसके अलावा, क्योंकि हेसेनबर्ग फॉर्म पहले से ही लगभग ऊपरी-त्रिकोणीय है (इसमें प्रत्येक विकर्ण के नीचे केवल एक गैर-शून्य प्रविष्टि है), इसे शुरुआती बिंदु के रूप में उपयोग करने से क्यूआर एल्गोरिदम के अभिसरण के लिए आवश्यक चरणों की संख्या कम हो जाती है।
+इस कच्चे रूप में पुनरावृत्तियाँ अपेक्षाकृत महंगी हैं। इसे पहले मैट्रिक्स ए को ऊपरी [[हेसेनबर्ग फॉर्म]] में लाकर कम किया जा सकता है (जिसकी लागत है <math>\begin{matrix}\frac{10}{3}\end{matrix} n^3 + \mathcal{O}(n^2)</math> घरेलू परिवर्तन पर आधारित तकनीक का उपयोग करके अंकगणितीय संचालन), ऑर्थोगोनल समानता परिवर्तनों के सीमित अनुक्रम के साथ, कुछ हद तक दो-तरफा क्यूआर अपघटन की तरह।<ref name=Demmel>{{cite book |first=James W. |last=Demmel |author-link=James W. Demmel |title=अनुप्रयुक्त संख्यात्मक रैखिक बीजगणित|publisher=SIAM |year=1997 }}</ref><ref name=Trefethen>{{cite book |first1=Lloyd N. |last1=Trefethen |author-link=Lloyd N. Trefethen |first2=David |last2=Bau |title=संख्यात्मक रैखिक बीजगणित|publisher=SIAM |year=1997 }}</ref> (क्यूआर अपघटन के लिए, हाउसहोल्डर रिफ्लेक्टर को केवल बाईं ओर गुणा किया जाता है, लेकिन हेसेनबर्ग मामले के लिए उन्हें बाएं और दाएं दोनों पर गुणा किया जाता है।) ऊपरी हेसेनबर्ग मैट्रिक्स लागत के क्यूआर अपघटन का निर्धारण <math>6 n^2 + \mathcal{O}(n)</math> अंकगणितीय आपरेशनस। इसके अलावा, क्योंकि हेसेनबर्ग फॉर्म पहले से ही लगभग ऊपरी-त्रिकोणीय है (इसमें प्रत्येक विकर्ण के नीचे केवल गैर-शून्य प्रविष्टि है), इसे शुरुआती बिंदु के रूप में उपयोग करने से क्यूआर एल्गोरिदम के अभिसरण के लिए आवश्यक चरणों की संख्या कम हो जाती है।
 यदि मूल मैट्रिक्स [[सममित मैट्रिक्स]] है, तो ऊपरी हेसेनबर्ग मैट्रिक्स भी सममित है और इस प्रकार त्रिविकर्ण मैट्रिक्स है, और सभी ए भी हैं<sub>''k''</sub>. इस प्रक्रिया में लागत आती है <math>\begin{matrix}\frac{4}{3}\end{matrix} n^3 + \mathcal{O}(n^2)</math> हाउसहोल्डर रिडक्शन पर आधारित तकनीक का उपयोग करके अंकगणितीय परिचालन।<ref name=Demmel/><ref name=Trefethen/>एक सममित त्रिविकर्ण मैट्रिक्स लागत के क्यूआर अपघटन का निर्धारण <math>\mathcal{O}(n)</math> परिचालन.<ref>{{cite journal |first1=James M. |last1=Ortega |first2=Henry F. |last2=Kaiser |title=The ''LL<sup>T</sup>'' and ''QR'' methods for symmetric tridiagonal matrices |journal=The Computer Journal |volume=6 |issue=1 |pages=99–101 |year=1963 |doi=10.1093/comjnl/6.1.99 |doi-access=free }}</ref>
-अभिसरण की दर eigenvalues के बीच अलगाव पर निर्भर करती है, इसलिए एक व्यावहारिक एल्गोरिदम अलगाव को बढ़ाने और अभिसरण में तेजी लाने के लिए स्पष्ट या अंतर्निहित बदलावों का उपयोग करेगा। एक विशिष्ट सममित क्यूआर एल्गोरिदम केवल एक या दो पुनरावृत्तियों के साथ प्रत्येक eigenvalue को अलग करता है (फिर मैट्रिक्स के आकार को कम करता है), जिससे यह कुशल और मजबूत हो जाता है।{{clarify|date=June 2012}}
+अभिसरण की दर eigenvalues के बीच अलगाव पर निर्भर करती है, इसलिए व्यावहारिक एल्गोरिदम अलगाव को बढ़ाने और अभिसरण में तेजी लाने के लिए स्पष्ट या अंतर्निहित बदलावों का उपयोग करेगा। विशिष्ट सममित क्यूआर एल्गोरिदम केवल या दो पुनरावृत्तियों के साथ प्रत्येक eigenvalue को अलग करता है (फिर मैट्रिक्स के आकार को कम करता है), जिससे यह कुशल और मजबूत हो जाता है।{{clarify|date=June 2012}}
 == विज़ुअलाइज़ेशन ==
-[[File:QR and LR visualization illustrating fixed points (corrected).gif|thumb|चित्र 1: क्यूआर या एलआर एल्गोरिथ्म के एकल पुनरावृत्ति का आउटपुट उसके इनपुट के साथ कैसे भिन्न होता है]]मूल क्यूआर एल्गोरिदम की कल्पना उस स्थिति में की जा सकती है जहां ए एक सकारात्मक-निश्चित सममित मैट्रिक्स है। उस स्थिति में, A को 2 आयामों में एक दीर्घवृत्त या उच्च आयामों में एक दीर्घवृत्त के रूप में दर्शाया जा सकता है। एल्गोरिथम के इनपुट और एकल पुनरावृत्ति के बीच संबंध को चित्र 1 (एनीमेशन देखने के लिए क्लिक करें) के रूप में दर्शाया जा सकता है। ध्यान दें कि एलआर एल्गोरिदम को क्यूआर एल्गोरिदम के साथ दर्शाया गया है।
+[[File:QR and LR visualization illustrating fixed points (corrected).gif|thumb|चित्र 1: क्यूआर या एलआर एल्गोरिथ्म के एकल पुनरावृत्ति का आउटपुट उसके इनपुट के साथ कैसे भिन्न होता है]]मूल क्यूआर एल्गोरिदम की कल्पना उस स्थिति में की जा सकती है जहां ए सकारात्मक-निश्चित सममित मैट्रिक्स है। उस स्थिति में, A को 2 आयामों में दीर्घवृत्त या उच्च आयामों में दीर्घवृत्त के रूप में दर्शाया जा सकता है। एल्गोरिथम के इनपुट और एकल पुनरावृत्ति के बीच संबंध को चित्र 1 (एनीमेशन देखने के लिए क्लिक करें) के रूप में दर्शाया जा सकता है। ध्यान दें कि एलआर एल्गोरिदम को क्यूआर एल्गोरिदम के साथ दर्शाया गया है।
-एक एकल पुनरावृत्ति के कारण दीर्घवृत्त x-अक्ष की ओर झुक जाता है या गिर जाता है। ऐसी स्थिति में जहां दीर्घवृत्त का बड़ा [[अर्ध-प्रमुख और अर्ध-लघु अक्ष]] | अर्ध-अक्ष x-अक्ष के समानांतर है, QR का एक पुनरावृत्ति कुछ नहीं करता है। एक और स्थिति जहां एल्गोरिदम कुछ नहीं करता है वह यह है कि जब बड़ा अर्ध-अक्ष x-अक्ष के बजाय y-अक्ष के समानांतर होता है। उस घटना में, दीर्घवृत्त को किसी भी दिशा में गिरने में सक्षम हुए बिना अनिश्चित रूप से संतुलन बनाने के रूप में सोचा जा सकता है। दोनों स्थितियों में, मैट्रिक्स विकर्ण है। ऐसी स्थिति जहां एल्गोरिथम की पुनरावृत्ति कुछ नहीं करती, उसे [[निश्चित बिंदु (गणित)]] कहा जाता है। एल्गोरिथम द्वारा नियोजित रणनीति [[निश्चित-बिंदु पुनरावृत्ति]]|एक निश्चित-बिंदु की ओर पुनरावृत्ति है। ध्यान दें कि एक निश्चित बिंदु स्थिर है जबकि दूसरा अस्थिर है। यदि दीर्घवृत्त को अस्थिर निश्चित बिंदु से बहुत कम मात्रा में झुकाया जाता है, तो क्यूआर के एक पुनरावृत्ति के कारण दीर्घवृत्त निश्चित बिंदु की ओर झुकने के बजाय दूर झुक जाएगा। हालाँकि अंततः, एल्गोरिदम एक अलग निश्चित बिंदु पर परिवर्तित हो जाएगा, लेकिन इसमें लंबा समय लगेगा।
+एक एकल पुनरावृत्ति के कारण दीर्घवृत्त x-अक्ष की ओर झुक जाता है या गिर जाता है। ऐसी स्थिति में जहां दीर्घवृत्त का बड़ा [[अर्ध-प्रमुख और अर्ध-लघु अक्ष]] | अर्ध-अक्ष x-अक्ष के समानांतर है, QR का पुनरावृत्ति कुछ नहीं करता है। और स्थिति जहां एल्गोरिदम कुछ नहीं करता है वह यह है कि जब बड़ा अर्ध-अक्ष x-अक्ष के बजाय y-अक्ष के समानांतर होता है। उस घटना में, दीर्घवृत्त को किसी भी दिशा में गिरने में सक्षम हुए बिना अनिश्चित रूप से संतुलन बनाने के रूप में सोचा जा सकता है। दोनों स्थितियों में, मैट्रिक्स विकर्ण है। ऐसी स्थिति जहां एल्गोरिथम की पुनरावृत्ति कुछ नहीं करती, उसे [[निश्चित बिंदु (गणित)]] कहा जाता है। एल्गोरिथम द्वारा नियोजित रणनीति [[निश्चित-बिंदु पुनरावृत्ति]]|एक निश्चित-बिंदु की ओर पुनरावृत्ति है। ध्यान दें कि निश्चित बिंदु स्थिर है जबकि दूसरा अस्थिर है। यदि दीर्घवृत्त को अस्थिर निश्चित बिंदु से बहुत कम मात्रा में झुकाया जाता है, तो क्यूआर के पुनरावृत्ति के कारण दीर्घवृत्त निश्चित बिंदु की ओर झुकने के बजाय दूर झुक जाएगा। हालाँकि अंततः, एल्गोरिदम अलग निश्चित बिंदु पर परिवर्तित हो जाएगा, लेकिन इसमें लंबा समय लगेगा।
 === आइजनवैल्यू ढूंढना बनाम आइजेनवेक्टर ढूंढना ===
-[[File:Qr lr eigenvalue clash.gif|thumb|चित्र 2: जब दो eigenvalues एक दूसरे के पास आते हैं तो QR या LR के एकल पुनरावृत्ति का आउटपुट कैसे प्रभावित होता है]]यह इंगित करने योग्य है कि एक सममित मैट्रिक्स का एक भी आइजनवेक्टर ढूंढना गणना योग्य नहीं है ([[गणना योग्य विश्लेषण]] में परिभाषाओं के अनुसार सटीक वास्तविक अंकगणित में)।<ref>{{Cite web|title=linear algebra - Why is uncomputability of the spectral decomposition not a problem?|url=https://mathoverflow.net/questions/369930/why-is-uncomputability-of-the-spectral-decomposition-not-a-problem|access-date=2021-08-09|website=MathOverflow}}</ref> यह कठिनाई तब मौजूद होती है जब किसी मैट्रिक्स के eigenvalues की बहुलताएं जानने योग्य नहीं होती हैं। दूसरी ओर, eigenvalues खोजने के लिए वही समस्या मौजूद नहीं है। मैट्रिक्स के eigenvalues हमेशा गणना योग्य होते हैं।
+[[File:Qr lr eigenvalue clash.gif|thumb|चित्र 2: जब दो eigenvalues एक दूसरे के पास आते हैं तो QR या LR के एकल पुनरावृत्ति का आउटपुट कैसे प्रभावित होता है]]यह इंगित करने योग्य है कि सममित मैट्रिक्स का भी आइजनवेक्टर ढूंढना गणना योग्य नहीं है ([[गणना योग्य विश्लेषण]] में परिभाषाओं के अनुसार सटीक वास्तविक अंकगणित में)।<ref>{{Cite web|title=linear algebra - Why is uncomputability of the spectral decomposition not a problem?|url=https://mathoverflow.net/questions/369930/why-is-uncomputability-of-the-spectral-decomposition-not-a-problem|access-date=2021-08-09|website=MathOverflow}}</ref> यह कठिनाई तब मौजूद होती है जब किसी मैट्रिक्स के eigenvalues की बहुलताएं जानने योग्य नहीं होती हैं। दूसरी ओर, eigenvalues खोजने के लिए वही समस्या मौजूद नहीं है। मैट्रिक्स के eigenvalues हमेशा गणना योग्य होते हैं।
-अब हम चर्चा करेंगे कि बुनियादी क्यूआर एल्गोरिदम में ये कठिनाइयाँ कैसे प्रकट होती हैं। इसे चित्र 2 में दर्शाया गया है। (थंबनेल पर क्लिक करना याद रखें)। याद रखें कि दीर्घवृत्त सकारात्मक-निश्चित सममित मैट्रिक्स का प्रतिनिधित्व करते हैं। जैसे ही इनपुट मैट्रिक्स के दो आइगेनवैल्यू एक-दूसरे के करीब आते हैं, इनपुट दीर्घवृत्त एक सर्कल में बदल जाता है। एक वृत्त पहचान मैट्रिक्स के गुणज से मेल खाता है। एक निकट-वृत्त पहचान मैट्रिक्स के निकट-गुणक से मेल खाता है जिसका eigenvalues मैट्रिक्स की विकर्ण प्रविष्टियों के लगभग बराबर है। इसलिए उस मामले में लगभग eigenvalues खोजने की समस्या आसान दिखाई देती है। लेकिन ध्यान दें कि दीर्घवृत्त के अर्ध-अक्षों का क्या होता है। क्यूआर (या एलआर) की पुनरावृत्ति अर्ध-अक्षों को कम से कम झुकाती है क्योंकि इनपुट दीर्घवृत्त एक वृत्त होने के करीब पहुंचता है। आइजनवेक्टर केवल तभी ज्ञात हो सकते हैं जब अर्ध-अक्ष x-अक्ष और y-अक्ष के समानांतर हों। निकट-समानांतरता प्राप्त करने के लिए आवश्यक पुनरावृत्तियों की संख्या बिना किसी सीमा के बढ़ जाती है क्योंकि इनपुट दीर्घवृत्त अधिक गोलाकार हो जाता है।
+अब हम चर्चा करेंगे कि बुनियादी क्यूआर एल्गोरिदम में ये कठिनाइयाँ कैसे प्रकट होती हैं। इसे चित्र 2 में दर्शाया गया है। (थंबनेल पर क्लिक करना याद रखें)। याद रखें कि दीर्घवृत्त सकारात्मक-निश्चित सममित मैट्रिक्स का प्रतिनिधित्व करते हैं। जैसे ही इनपुट मैट्रिक्स के दो आइगेनवैल्यू एक-दूसरे के करीब आते हैं, इनपुट दीर्घवृत्त सर्कल में बदल जाता है। वृत्त पहचान मैट्रिक्स के गुणज से मेल खाता है। निकट-वृत्त पहचान मैट्रिक्स के निकट-गुणक से मेल खाता है जिसका eigenvalues मैट्रिक्स की विकर्ण प्रविष्टियों के लगभग बराबर है। इसलिए उस मामले में लगभग eigenvalues खोजने की समस्या आसान दिखाई देती है। लेकिन ध्यान दें कि दीर्घवृत्त के अर्ध-अक्षों का क्या होता है। क्यूआर (या एलआर) की पुनरावृत्ति अर्ध-अक्षों को कम से कम झुकाती है क्योंकि इनपुट दीर्घवृत्त वृत्त होने के करीब पहुंचता है। आइजनवेक्टर केवल तभी ज्ञात हो सकते हैं जब अर्ध-अक्ष x-अक्ष और y-अक्ष के समानांतर हों। निकट-समानांतरता प्राप्त करने के लिए आवश्यक पुनरावृत्तियों की संख्या बिना किसी सीमा के बढ़ जाती है क्योंकि इनपुट दीर्घवृत्त अधिक गोलाकार हो जाता है।
-हालांकि एक मनमाना सममित मैट्रिक्स के मैट्रिक्स के ईजेंडेकंपोजिशन की गणना करना असंभव हो सकता है, मैट्रिक्स को मनमाने ढंग से छोटी राशि से परेशान करना और परिणामी मैट्रिक्स के ईजेंडेकंपोजीशन की गणना करना हमेशा संभव होता है। ऐसे मामले में जब मैट्रिक्स को एक निकट-वृत्त के रूप में दर्शाया गया है, मैट्रिक्स को उस मैट्रिक्स से बदला जा सकता है जिसका चित्रण एक पूर्ण वृत्त है। उस स्थिति में, मैट्रिक्स पहचान मैट्रिक्स का एक गुणक है, और इसका eigendecomposition तत्काल है। हालाँकि सावधान रहें कि परिणामी [[अपना आधार]] मूल आइजेनबासिस से काफी दूर हो सकता है।
+हालांकि मनमाना सममित मैट्रिक्स के मैट्रिक्स के ईजेंडेकंपोजिशन की गणना करना असंभव हो सकता है, मैट्रिक्स को मनमाने ढंग से छोटी राशि से परेशान करना और परिणामी मैट्रिक्स के ईजेंडेकंपोजीशन की गणना करना हमेशा संभव होता है। ऐसे मामले में जब मैट्रिक्स को निकट-वृत्त के रूप में दर्शाया गया है, मैट्रिक्स को उस मैट्रिक्स से बदला जा सकता है जिसका चित्रण पूर्ण वृत्त है। उस स्थिति में, मैट्रिक्स पहचान मैट्रिक्स का गुणक है, और इसका eigendecomposition तत्काल है। हालाँकि सावधान रहें कि परिणामी [[अपना आधार]] मूल आइजेनबासिस से काफी दूर हो सकता है।
 == अंतर्निहित क्यूआर एल्गोरिदम ==
-आधुनिक कम्प्यूटेशनल अभ्यास में, क्यूआर एल्गोरिदम को एक अंतर्निहित संस्करण में निष्पादित किया जाता है जो कई बदलावों के उपयोग को शुरू करना आसान बनाता है।<ref name="golubvanloan" />मैट्रिक्स को पहले ऊपरी हेसेनबर्ग फॉर्म में लाया जाता है <math>A_0=QAQ^{\mathsf{T}}</math> जैसा कि स्पष्ट संस्करण में है; फिर, प्रत्येक चरण पर, का पहला कॉलम <math>A_k</math> के पहले कॉलम में एक छोटे आकार के घरेलू समानता परिवर्तन के माध्यम से रूपांतरित किया गया है <math>p(A_k)</math> {{Clarify|date=October 2022}} (या <math>p(A_k)e_1</math>), कहाँ <math>p(A_k)</math>, डिग्री का <math>r</math>, वह बहुपद है जो स्थानांतरण रणनीति को परिभाषित करता है (अक्सर <math>p(x)=(x-\lambda)(x-\bar\lambda)</math>, कहाँ <math>\lambda</math> और <math>\bar\lambda</math> अनुगामी के दो eigenvalues हैं <math>2 \times 2</math> का प्रमुख सबमैट्रिक्स <math>A_k</math>, तथाकथित अंतर्निहित डबल-शिफ्ट)। फिर आकार का क्रमिक गृहस्वामी परिवर्तन <math>r+1</math> कार्यशील मैट्रिक्स को वापस करने के लिए किया जाता है <math>A_k</math> ऊपरी हेसेनबर्ग रूप में। एल्गोरिदम के चरणों के साथ मैट्रिक्स की गैर-शून्य प्रविष्टियों के अजीब आकार के कारण, इस ऑपरेशन को उभार पीछा के रूप में जाना जाता है। पहले संस्करण की तरह, उप-विकर्ण प्रविष्टियों में से एक के रूप में ही अपस्फीति का प्रदर्शन किया जाता है <math>A_k</math> पर्याप्त रूप से छोटा है.
+आधुनिक कम्प्यूटेशनल अभ्यास में, क्यूआर एल्गोरिदम को अंतर्निहित संस्करण में निष्पादित किया जाता है जो कई बदलावों के उपयोग को शुरू करना आसान बनाता है।<ref name="golubvanloan" />मैट्रिक्स को पहले ऊपरी हेसेनबर्ग फॉर्म में लाया जाता है <math>A_0=QAQ^{\mathsf{T}}</math> जैसा कि स्पष्ट संस्करण में है; फिर, प्रत्येक चरण पर, का पहला कॉलम <math>A_k</math> के पहले कॉलम में छोटे आकार के घरेलू समानता परिवर्तन के माध्यम से रूपांतरित किया गया है <math>p(A_k)</math> {{Clarify|date=October 2022}} (या <math>p(A_k)e_1</math>), कहाँ <math>p(A_k)</math>, डिग्री का <math>r</math>, वह बहुपद है जो स्थानांतरण रणनीति को परिभाषित करता है (अक्सर <math>p(x)=(x-\lambda)(x-\bar\lambda)</math>, कहाँ <math>\lambda</math> और <math>\bar\lambda</math> अनुगामी के दो eigenvalues हैं <math>2 \times 2</math> का प्रमुख सबमैट्रिक्स <math>A_k</math>, तथाकथित अंतर्निहित डबल-शिफ्ट)। फिर आकार का क्रमिक गृहस्वामी परिवर्तन <math>r+1</math> कार्यशील मैट्रिक्स को वापस करने के लिए किया जाता है <math>A_k</math> ऊपरी हेसेनबर्ग रूप में। एल्गोरिदम के चरणों के साथ मैट्रिक्स की गैर-शून्य प्रविष्टियों के अजीब आकार के कारण, इस ऑपरेशन को उभार पीछा के रूप में जाना जाता है। पहले संस्करण की तरह, उप-विकर्ण प्रविष्टियों में से के रूप में ही अपस्फीति का प्रदर्शन किया जाता है <math>A_k</math> पर्याप्त रूप से छोटा है.
 ===नाम बदलने का प्रस्ताव===
@@ Line 34: / Line 35: @@
 == व्याख्या और अभिसरण ==
-क्यूआर एल्गोरिदम को बुनियादी पावर पुनरावृत्ति के अधिक परिष्कृत बदलाव के रूप में देखा जा सकता है पावर आइजेनवैल्यू एल्गोरिदम। याद रखें कि पावर एल्गोरिदम बार-बार एक वेक्टर को ए से गुणा करता है, प्रत्येक पुनरावृत्ति के बाद सामान्य हो जाता है। वेक्टर सबसे बड़े eigenvalue के eigenvector में परिवर्तित हो जाता है। इसके बजाय, क्यूआर एल्गोरिदम वैक्टर के पूर्ण आधार के साथ काम करता है, क्यूआर अपघटन का उपयोग करके पुनर्सामान्यीकरण (और ऑर्थोगोनलाइज़) करता है। एक सममित मैट्रिक्स A के लिए, अभिसरण पर, AQ = QΛ, जहां Λ eigenvalues का विकर्ण मैट्रिक्स है जिसमें A अभिसरण करता है, और जहां Q वहां पहुंचने के लिए आवश्यक सभी ऑर्थोगोनल समानता परिवर्तनों का एक संयोजन है। इस प्रकार Q के कॉलम eigenvectors हैं।
+क्यूआर एल्गोरिदम को बुनियादी पावर पुनरावृत्ति के अधिक परिष्कृत बदलाव के रूप में देखा जा सकता है पावर आइजेनवैल्यू एल्गोरिदम। याद रखें कि पावर एल्गोरिदम बार-बार वेक्टर को ए से गुणा करता है, प्रत्येक पुनरावृत्ति के बाद सामान्य हो जाता है। वेक्टर सबसे बड़े eigenvalue के eigenvector में परिवर्तित हो जाता है। इसके बजाय, क्यूआर एल्गोरिदम वैक्टर के पूर्ण आधार के साथ काम करता है, क्यूआर अपघटन का उपयोग करके पुनर्सामान्यीकरण (और ऑर्थोगोनलाइज़) करता है। सममित मैट्रिक्स A के लिए, अभिसरण पर, AQ = QΛ, जहां Λ eigenvalues का विकर्ण मैट्रिक्स है जिसमें A अभिसरण करता है, और जहां Q वहां पहुंचने के लिए आवश्यक सभी ऑर्थोगोनल समानता परिवर्तनों का संयोजन है। इस प्रकार Q के कॉलम eigenvectors हैं।
-== इतिहास ==
+== इतिहास             ==
-क्यूआर एल्गोरिदम एलआर एल्गोरिदम से पहले था, जो क्यूआर अपघटन के बजाय [[एलयू अपघटन]] का उपयोग करता है। क्यूआर एल्गोरिदम अधिक स्थिर है, इसलिए आजकल एलआर एल्गोरिदम का उपयोग शायद ही कभी किया जाता है। हालाँकि, यह QR एल्गोरिदम के विकास में एक महत्वपूर्ण कदम का प्रतिनिधित्व करता है।
+क्यूआर एल्गोरिदम एलआर एल्गोरिदम से पहले था, जो क्यूआर अपघटन के बजाय [[एलयू अपघटन]] का उपयोग करता है। क्यूआर एल्गोरिदम अधिक स्थिर है, इसलिए आजकल एलआर एल्गोरिदम का उपयोग शायद ही कभी किया जाता है। हालाँकि, यह QR एल्गोरिदम के विकास में महत्वपूर्ण कदम का प्रतिनिधित्व करता है।
-एलआर एल्गोरिथ्म को 1950 के दशक की शुरुआत में [[हेंज रूटीशौसर]] द्वारा विकसित किया गया था, जो उस समय [[ईटीएच ज्यूरिख]] में [[एडवर्ड बूट्स]] के अनुसंधान सहायक के रूप में काम करते थे। स्टिफ़ेल ने सुझाव दिया कि रूटीशौसर क्षणों y के अनुक्रम का उपयोग करें<sub>0</sub><sup>टी</sup>ए<sup>क</sup>x<sub>0</sub>, k = 0, 1, … (जहाँ x<sub>0</sub> और य<sub>0</sub> मनमाने ढंग से वेक्टर हैं) ए के eigenvalues को खोजने के लिए। रुतिशौसर ने इस कार्य के लिए [[अलेक्जेंडर ऐटकेन]] का एक एल्गोरिदम लिया और इसे भागफल-अंतर एल्गोरिदम या क्यूडी एल्गोरिदम में विकसित किया। गणना को उपयुक्त आकार में व्यवस्थित करने के बाद, उन्होंने पाया कि क्यूडी एल्गोरिदम वास्तव में पुनरावृत्ति ए है<sub>''k''</sub> = एल<sub>''k''</sub>U<sub>''k''</sub> (एलयू अपघटन), ए<sub>''k''+1</sub> = यू<sub>''k''</sub>L<sub>''k''</sub>, एक त्रिविकर्ण मैट्रिक्स पर लागू किया जाता है, जिसमें से एलआर एल्गोरिदम अनुसरण करता है।<ref>{{Citation | last1=Parlett | first1=Beresford N. | last2=Gutknecht | first2=Martin H. | title=From qd to LR, or, how were the qd and LR algorithms discovered? | doi=10.1093/imanum/drq003 | year=2011 | journal=IMA Journal of Numerical Analysis | issn=0272-4979 | volume=31 | issue=3 | pages=741–754| hdl=20.500.11850/159536 | url=http://doc.rero.ch/record/299139/files/drq003.pdf }}</ref>
+एलआर एल्गोरिथ्म को 1950 के दशक की शुरुआत में [[हेंज रूटीशौसर]] द्वारा विकसित किया गया था, जो उस समय [[ईटीएच ज्यूरिख]] में [[एडवर्ड बूट्स]] के अनुसंधान सहायक के रूप में काम करते थे। स्टिफ़ेल ने सुझाव दिया कि रूटीशौसर क्षणों y के अनुक्रम का उपयोग करें<sub>0</sub><sup>टी</sup>ए<sup>क</sup>x<sub>0</sub>, k = 0, 1, … (जहाँ x<sub>0</sub> और य<sub>0</sub> मनमाने ढंग से वेक्टर हैं) ए के eigenvalues को खोजने के लिए। रुतिशौसर ने इस कार्य के लिए [[अलेक्जेंडर ऐटकेन]] का एल्गोरिदम लिया और इसे भागफल-अंतर एल्गोरिदम या क्यूडी एल्गोरिदम में विकसित किया। गणना को उपयुक्त आकार में व्यवस्थित करने के बाद, उन्होंने पाया कि क्यूडी एल्गोरिदम वास्तव में पुनरावृत्ति ए है<sub>''k''</sub> = एल<sub>''k''</sub>U<sub>''k''</sub> (एलयू अपघटन), ए<sub>''k''+1</sub> = यू<sub>''k''</sub>L<sub>''k''</sub>, त्रिविकर्ण मैट्रिक्स पर लागू किया जाता है, जिसमें से एलआर एल्गोरिदम अनुसरण करता है।<ref>{{Citation | last1=Parlett | first1=Beresford N. | last2=Gutknecht | first2=Martin H. | title=From qd to LR, or, how were the qd and LR algorithms discovered? | doi=10.1093/imanum/drq003 | year=2011 | journal=IMA Journal of Numerical Analysis | issn=0272-4979 | volume=31 | issue=3 | pages=741–754| hdl=20.500.11850/159536 | url=http://doc.rero.ch/record/299139/files/drq003.pdf }}</ref>
-== अन्य प्रकार ==
+== अन्य प्रकार                                                                   ==
-क्यूआर एल्गोरिथ्म का एक प्रकार, गोलूब-कहान-रीन्स्च एल्गोरिथ्म एक सामान्य मैट्रिक्स को एक द्विभुजीय मैट्रिक्स में कम करने के साथ शुरू होता है।<ref>Bochkanov Sergey Anatolyevich. ALGLIB User Guide - General Matrix operations - Singular value decomposition . ALGLIB Project. 2010-12-11. URL:[http://www.alglib.net/matrixops/general/svd.php] Accessed: 2010-12-11. (Archived by WebCite at https://www.webcitation.org/5utO4iSnR?url=http://www.alglib.net/matrixops/general/svd.php</ref> [[एकवचन मान]]ों की गणना के लिए QR एल्गोरिदम के इस संस्करण का वर्णन सबसे पहले किसके द्वारा किया गया था? {{harvtxt|Golub|Kahan|1965}}. [[LAPACK]] सबरूटीन [http://www.netlib.org/lapack/double/dbdsqr.f DBDSQR] उस मामले को कवर करने के लिए कुछ संशोधनों के साथ इस पुनरावृत्त विधि को कार्यान्वित करता है जहां एकवचन मान बहुत छोटे होते हैं {{harv|Demmel|Kahan|1990}}. हाउसहोल्डर रिफ्लेक्शन और, यदि उपयुक्त हो, क्यूआर अपघटन का उपयोग करते हुए पहले चरण के साथ, यह एकवचन मूल्य अपघटन की गणना के लिए [http://www.netlib.org/lapack/double/dgesvd.f DGESVD] रूटीन बनाता है। क्यूआर एल्गोरिदम को संबंधित अभिसरण परिणामों के साथ अनंत आयामों में भी लागू किया जा सकता है।<ref>{{cite journal |first1=Percy |last1=Deift |first2=Luenchau C. |last2=Li |first3=Carlos |last3=Tomei|title=टोडा अनंत अनेक चरों के साथ बहती है|journal=Journal of Functional Analysis |volume=64 | number=3| pages=358–402 |year=1985 |doi=10.1016/0022-1236(85)90065-5|doi-access=free }}</ref><ref>{{cite journal |first1=Matthew J. |last1=Colbrook |first2=Anders C.|last2=Hansen|title=अनंत-आयामी क्यूआर एल्गोरिदम पर|journal=Numerische Mathematik |volume=143 | number=1| pages=17–83 |year=2019 |doi=10.1007/s00211-019-01047-5|arxiv=2011.08172|doi-access=free }}</ref>
+क्यूआर एल्गोरिथ्म का प्रकार, गोलूब-कहान-रीन्स्च एल्गोरिथ्म सामान्य मैट्रिक्स को द्विभुजीय मैट्रिक्स में कम करने के साथ शुरू होता है।<ref>Bochkanov Sergey Anatolyevich. ALGLIB User Guide - General Matrix operations - Singular value decomposition . ALGLIB Project. 2010-12-11. URL:[http://www.alglib.net/matrixops/general/svd.php] Accessed: 2010-12-11. (Archived by WebCite at https://www.webcitation.org/5utO4iSnR?url=http://www.alglib.net/matrixops/general/svd.php</ref> [[एकवचन मान]]ों की गणना के लिए QR एल्गोरिदम के इस संस्करण का वर्णन सबसे पहले किसके द्वारा किया गया था? {{harvtxt|Golub|Kahan|1965}}. [[LAPACK]] सबरूटीन [http://www.netlib.org/lapack/double/dbdsqr.f DBDSQR] उस मामले को कवर करने के लिए कुछ संशोधनों के साथ इस पुनरावृत्त विधि को कार्यान्वित करता है जहां एकवचन मान बहुत छोटे होते हैं {{harv|Demmel|Kahan|1990}}. हाउसहोल्डर रिफ्लेक्शन और, यदि उपयुक्त हो, क्यूआर अपघटन का उपयोग करते हुए पहले चरण के साथ, यह एकवचन मूल्य अपघटन की गणना के लिए [http://www.netlib.org/lapack/double/dgesvd.f DGESVD] रूटीन बनाता है। क्यूआर एल्गोरिदम को संबंधित अभिसरण परिणामों के साथ अनंत आयामों में भी लागू किया जा सकता है।<ref>{{cite journal |first1=Percy |last1=Deift |first2=Luenchau C. |last2=Li |first3=Carlos |last3=Tomei|title=टोडा अनंत अनेक चरों के साथ बहती है|journal=Journal of Functional Analysis |volume=64 | number=3| pages=358–402 |year=1985 |doi=10.1016/0022-1236(85)90065-5|doi-access=free }}</ref><ref>{{cite journal |first1=Matthew J. |last1=Colbrook |first2=Anders C.|last2=Hansen|title=अनंत-आयामी क्यूआर एल्गोरिदम पर|journal=Numerische Mathematik |volume=143 | number=1| pages=17–83 |year=2019 |doi=10.1007/s00211-019-01047-5|arxiv=2011.08172|doi-access=free }}</ref>

v t e Numerical linear algebra
Key concepts	Floating point Numerical stability
Problems	System of linear equations Matrix decompositions Matrix multiplication (algorithms) Matrix splitting Sparse problems
Hardware	CPU cache TLB Cache-oblivious algorithm SIMD Multiprocessing
Software	MATLAB Basic Linear Algebra Subprograms (BLAS) LAPACK Specialized libraries General purpose software

Anonymous

Search

क्यूआर एल्गोरिदम: Difference between revisions

Namespaces

More

Page actions

Revision as of 13:30, 29 July 2023

Contents

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

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

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

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

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

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

इतिहास

अन्य प्रकार

संदर्भ

स्रोत

बाहरी संबंध

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

क्यूआर एल्गोरिदम: Difference between revisions

Revision as of 13:30, 29 July 2023

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

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

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

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

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

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

इतिहास

अन्य प्रकार

संदर्भ

स्रोत

बाहरी संबंध

Navigation

Wiki tools

Page tools

Other projects

Categories