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

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

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

सामान्य रूप से, मान लीजिए कि A वास्तविक आव्युह है जिसके आइजेनवैल्यू ​की गणना हम करना चाहते हैं, और मान लीजिए A₀:=A. K-वें चरण पर (k = 0 से प्रारंभ करके), हम क्युआर अपघटन A_k=Q_kR_k की गणना करते हैं जहाँ Q_k ऑर्थोगोनल आव्युह है (अर्थात, Q^T = Q⁻¹) और R_k ऊपरी त्रिकोणीय आव्युह है. फिर हम A_k+1 = R_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},$$

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

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

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

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

अभिसरण की दर आइजेनवैल्यू ​​​​के बीच सेपरेशन पर निर्भर करती है, इसलिए व्यावहारिक एल्गोरिदम सेपरेशन को बढ़ाने और अभिसरण में तेजी लाने के लिए स्पष्ट या अंतर्निहित शिफ्टो का उपयोग करेगा। विशिष्ट सममित क्यूआर एल्गोरिदम केवल या दो पुनरावृत्तियों के साथ प्रत्येक आइजेनवैल्यू को भिन्न करता है (फिर आव्युह के आकार को कम करता है), जिससे यह कुशल और प्रबल हो जाता है।

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

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

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

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

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

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

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

इतिहास

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

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