डिवाइड-और-कॉन्कर आइजेनवैल्यू एल्गोरिदम

विभाजन-और-कॉन्कर अभिलक्षणिक मान एल्गोरिदम हर्मिटियन या वास्तविक सममित मैट्रिक्स के लिए अभिलक्षणिक मान एल्गोरिदम का एक वर्ग है जो हाल ही में (लगभग 1990 के दशक में) क्यूआर (QR) एल्गोरिदम जैसे अधिक पारंपरिक एल्गोरिदम के साथ स्थिरता और दक्षता की स्थिति में प्रतिस्पर्धी बन गया है। इन एल्गोरिदम के पीछे मूल अवधारणा कंप्यूटर विज्ञान से विभाजन और कॉन्कर दृष्टिकोण है। अभिलक्षणिक मान प्रश्न को लगभग आधे आकार के दो प्रश्नों में विभाजित किया जाता है, इनमें से प्रत्येक को पुनरावर्ती रूप से हल किया जाता है, और मूल प्रश्न के अभिलक्षणिक मानों ​​की गणना इन छोटे प्रश्नों के परिणामों से की जाती है।

यहां हम विभाजन और कॉन्कर एल्गोरिदम का सबसे सरल संस्करण प्रस्तुत करते हैं, जो मूल रूप से 1981 में क्यूपेन द्वारा प्रस्तावित एल्गोरिदम के समान है। इस लेख के क्षेत्र से बाहर उपस्थित कई विवरण छोड़ दिए जाएंगे हालाँकि, इन विवरणों पर विचार किए बिना, एल्गोरिथ्म पूरी तरह से स्थिर नहीं है।

पृष्ठभूमि

हर्मिटियन मैट्रिक्स के लिए अधिकांश अभिलक्षणिक मान एल्गोरिदम की तरह, विभाजन-और-कॉन्कर त्रिविकर्णी रूप में कमी के साथ प्रारम्भ होते है। $m\times m$ मैट्रिक्स के लिए, इसके लिए मानक विधि, हाउसहोल्डर परावर्तन के माध्यम से, ${\frac {4}{3}}m^{3}$ प्लवी बिंदु संचालन लेती है, या ${\frac {8}{3}}m^{3}$ यदि अभिलक्षणिक सदिशों की भी आवश्यकता होती है। अन्य एल्गोरिदम हैं, जैसे कि अर्नोल्डी पुनरावृत्ति, जो मैट्रिक्स के कुछ वर्गों के लिए बेहतर प्रदर्शन कर सकते हैं हम यहां इस पर आगे विचार नहीं करेंगे। कुछ स्थितियों में, अभिलक्षणिक मान प्रश्न को छोटे प्रश्नों में विभाजित करना संभव है। ब्लॉक विकर्ण मैट्रिक्स पर विचार करें

$T={\begin{bmatrix}T_{1}&0\\0&T_{2}\end{bmatrix}}.$

$T$ के अभिलक्षणिक मानों ​​और अभिलक्षणिक सदिशों केवल $T_{1}$ और $T_{2}$ के समान हैं, और इन दो छोटे प्रश्नों को हल करना मूल प्रश्न को एक साथ हल करने की तुलना में लगभग सदैव तीव्र होगा। इस तकनीक का उपयोग कई अभिलक्षणिक मान एल्गोरिदम की दक्षता में सुधार करने के लिए किया जा सकता है, लेकिन इसके विभाजन-और-कॉन्कर के लिए विशेष महत्व है।

इस लेख के शेष भाग के लिए, हम मान लेंगे कि विभाजन-और-कॉन्कर एल्गोरिथ्म का इनपुट $m\times m$ वास्तविक सममित त्रिविकर्णी मैट्रिक्स $T$ है। हालाँकि हर्मिटियन मैट्रिक्स के लिए एल्गोरिदम को संशोधित किया जा सकता है, हम यहां विवरण नहीं देते हैं।

विभाजन

विभाजन-और-कॉन्कर एल्गोरिथ्म का विभाजन भाग इस प्रतिफलन से आता है कि त्रिविकर्णी मैट्रिक्स "लगभग" ब्लॉक विकर्ण है।

सबमैट्रिक्स $T_{1}$ का आकार हम $n\times n$ कहेंगे, और फिर $T_{2}$ $(m-n)\times (m-n)$ है। ध्यान दें कि $T$ के लगभग ब्लॉक विकर्ण होने की टिप्पणी सत्य है, चाहे $n$ को कैसे भी चुना जाए (अर्थात, मैट्रिक्स को विघटित करने के कई तरीके हैं)। हालाँकि, दक्षता के दृष्टिकोण से, $n\approx m/2$ चुनना उचित है।

हम $T$ को एक ब्लॉक विकर्ण मैट्रिक्स के साथ-साथ रैंक-1 सुधार के रूप में लिखते हैं-

$T_{1}$ और ${\hat {T}}_{1}$ के बीच एकमात्र अंतर यह है कि ${\hat {T}}_{1}$ में निचली दाईं ओर की प्रविष्टि $t_{nn}$ को $t_{nn}-\beta$ से बदल दिया गया है और इसी तरह, ${\hat {T}}_{2}$ में ऊपरी बाईं ओर की प्रविष्टि $t_{n+1,n+1}$ को $t_{n+1,n+1}-\beta$ से बदल दिया गया है।

विभाजन चरण का शेष भाग ${\hat {T}}_{1}$और ${\hat {T}}_{2}$ के अभिलक्षणिक मानों ​​(और यदि वांछित हो तो अभिलक्षणिक सदिशों) को हल करना है, अर्थात विकर्णन ${\hat {T}}_{1}=Q_{1}D_{1}Q_{1}^{T}$ और ${\hat {T}}_{2}=Q_{2}D_{2}Q_{2}^{T}$ खोजना है। इसे विभाजन-और-कॉन्कर एल्गोरिदम में पुनरावर्ती निर्देश के साथ पूरा किया जा सकता है, हालांकि व्यावहारिक कार्यान्वयन प्रायः छोटे पर्याप्त सबमैट्रिसेस के लिए क्यूआर एल्गोरिदम पर स्विच करते हैं।

कॉन्कर

एल्गोरिथम का कॉन्कर भाग अबोधगम्य भाग है। ऊपर परिकलित उपमैट्रिक्स के विकर्णीकरण को देखते हुए, हम मूल मैट्रिक्स का विकर्णीकरण कैसे ज्ञात कर सकते हैं?

सबसे पहले, $z^{T}=(q_{1}^{T},q_{2}^{T})$ को परिभाषित करें, जहां $q_{1}^{T}$ $Q_{1}$ की अंतिम पंक्ति है और $q_{2}^{T}$ $Q_{2}$ की पहली पंक्ति है। यह दर्शाना अब प्राथमिक है

$T={\begin{bmatrix}Q_{1}&\\&Q_{2}\end{bmatrix}}\left({\begin{bmatrix}D_{1}&\\&D_{2}\end{bmatrix}}+\beta zz^{T}\right){\begin{bmatrix}Q_{1}^{T}&\\&Q_{2}^{T}\end{bmatrix}}$

शेष कार्य को विकर्ण मैट्रिक्स के अभिलक्षणिक मानों ​​के साथ-साथ रैंक-एक सुधार को खोजने के लिए कम कर दिया गया है। यह कैसे करना है यह दिखाने से पहले, आइए अंकन को सरल बनाएं। हम मैट्रिक्स $D+ww^{T}$ के अभिलक्षणिक मानों ​​की खोज कर रहे हैं, जहां $D$ अलग-अलग प्रविष्टियों के साथ विकर्ण है और $w$ गैर-शून्य प्रविष्टियों वाला कोई सदिश है।

शून्य प्रविष्टि की स्थिति सरल है, क्योंकि यदि w_i शून्य है, ($e_{i}$,d_i) $D+ww^{T}$ का अभिलक्षणिक युग्म ($e_{i}$ मानक आधार पर है) है क्योंकि

$(D+ww^{T})e_{i}=De_{i}=d_{i}e_{i}$।

यदि $\lambda$ एक अभिलक्षणिक मान है, तो हमारे पास है-

$(D+ww^{T})q=\lambda q$

जहां $q$ संगत अभिलक्षणिक सदिश है। अब

$(D-\lambda I)q+w(w^{T}q)=0$

$q+(D-\lambda I)^{-1}w(w^{T}q)=0$

$w^{T}q+w^{T}(D-\lambda I)^{-1}w(w^{T}q)=0$

ध्यान रखें कि $w^{T}q$ एक शून्येतर अदिश राशि है। न तो $w$ और न ही $q$ शून्य हैं। यदि $w^{T}q$ शून्य होता, तो $q$ $(D+ww^{T})q=\lambda q$ द्वारा $D$ का अभिलक्षणिक सदिश होता है। यदि ऐसा होता, तो $q$ में केवल एक गैर-शून्य स्थिति होती क्योंकि $D$ अलग विकर्ण है और इस प्रकार आंतरिक गुणनफल $w^{T}q$ अंततः शून्य नहीं हो सकता। इसलिए, हमारे पास है-

$1+w^{T}(D-\lambda I)^{-1}w=0$

या अदिश समीकरण के रूप में लिखा गया है,

$1+\sum _{j=1}^{m}{\frac {w_{j}^{2}}{d_{j}-\lambda }}=0.$

इस समीकरण को दीर्घकालिक समीकरण के नाम से जाना जाता है। इसलिए प्रश्न को इस समीकरण के बाईं ओर द्वारा परिभाषित तर्कसंगत फलन के रूट्स को खोजने तक सीमित कर दिया गया है।

सभी सामान्य अभिलक्षणिक मान एल्गोरिदम पुनरावृत्त होने चाहिए, और विभाजन-और-कॉन्कर एल्गोरिदम अलग नहीं है। अरेखीय दीर्घकालिक समीकरण को हल करने के लिए पुनरावृत्तीय तकनीक की आवश्यकता होती है, जैसे न्यूटन-रेफसन विधि। हालाँकि, प्रत्येक रूट को O(1) पुनरावृत्तियों में पाया जा सकता है, जिनमें से प्रत्येक को $\Theta (m)$ फ़्लॉप्स ($m$-डिग्री तर्कसंगत फलन के लिए) की आवश्यकता होती है, जिससे इस एल्गोरिदम के पुनरावृत्त भाग की लागत $\Theta (m^{2})$ हो जाती है।

विश्लेषण

जैसा कि विभाजन और कॉन्कर एल्गोरिदम के लिए सामान्य है, हम कार्यावधि का विश्लेषण करने के लिए विभाजन-और-कॉन्कर पुनरावृत्ति के लिए मास्टर प्रमेय का उपयोग करेंगे।

याद रखें कि ऊपर हमने कहा है कि हम $n\approx m/2$ चुनते हैं। हम पुनरावृत्ति संबंध लिख सकते हैं-

$T(m)=2\times T\left({\frac {m}{2}}\right)+\Theta (m^{2})$

मास्टर प्रमेय के अंकन में, $a=b=2$ और इस प्रकार $\log _{b}a=1$। स्पष्ट रूप से, $\Theta (m^{2})=\Omega (m^{1})$, तो हमारे पास है

$T(m)=\Theta (m^{2})$

याद रखें कि ऊपर हमने बताया था कि हर्मिटियन मैट्रिक्स को त्रिविकर्ण रूप में कम करने में ${\frac {4}{3}}m^{3}$ फ्लॉप्स लगते हैं। यह विभाजन-और-कॉन्कर भाग की कार्यावधि को कम कर देती है, और इस बिंदु पर यह स्पष्ट नहीं है कि विभाजन-और-कॉन्कर एल्गोरिथ्म क्यूआर एल्गोरिथ्म (जो त्रिविकर्ण मैट्रिक्स के लिए $\Theta (m^{2})$ फ्लॉप्स भी लेता है) पर क्या लाभ प्रदान करता है।

विभाजन-और-कॉन्कर का लाभ तब मिलता है जब अभिलक्षणिक सदिश की भी आवश्यकता होती है। यदि यह स्थिति है, तो त्रिविकर्ण रूप में कमी में ${\frac {8}{3}}m^{3}$ लगता है, लेकिन एल्गोरिथ्म का दूसरा भाग $\Theta (m^{3})$ भी लेता है। उचित लक्ष्य परिशुद्धता वाले क्यूआर एल्गोरिदम के लिए, यह $\approx 6m^{3}$ है, जबकि विभाजन-और-कॉन्कर के लिए यह $\approx {\frac {4}{3}}m^{3}$ है। इस सुधार का कारण यह है कि विभाजन-और-कॉन्कर में, एल्गोरिदम का $\Theta (m^{3})$ भाग ($Q$ मैट्रिसेस को गुणा करना) पुनरावृत्ति से अलग है, जबकि क्यूआर में, यह प्रत्येक पुनरावृत्त चरण में होना चाहिए। कमी के लिए ${\frac {8}{3}}m^{3}$ फ्लॉप्स को जोड़ने पर, कुल सुधार $\approx 9m^{3}$ से $\approx 4m^{3}$ फ्लॉप्स तक होता है।

विभाजन-और-कॉन्कर एल्गोरिदम के व्यावहारिक उपयोग से पता चला है कि अधिकांश यथार्थवादी अभिलक्षणिक मान प्रश्नों में, एल्गोरिदम वास्तव में इससे बेहतर काम करता है। इसका कारण यह है कि प्रायः मैट्रिक्स $Q$ और सदिश $z$ संख्यात्मक रूप से अपर्याप्त होते हैं, जिसका अर्थ है कि उनके पास प्लवी बिंदु परिशुद्धता से छोटे मानों के साथ कई प्रविष्टियाँ हैं, जो संख्यात्मक अपस्फीति की अनुमति देती हैं, अर्थात प्रश्न को अयुग्मित उप-प्रश्नों में तोड़ देती हैं।

भिन्नरूप और कार्यान्वयन

यहां प्रस्तुत एल्गोरिदम सबसे सरल संस्करण है। कई व्यावहारिक कार्यान्वयन में, स्थिरता की गारंटी के लिए अधिक जटिल रैंक-1 सुधारों का उपयोग किया जाता है कुछ भिन्नरूप रैंक-2 सुधारों का भी उपयोग करते हैं।

तर्कसंगत कार्यों के लिए विशेष रूट-खोज तकनीकें उपस्थित हैं जो प्रदर्शन और स्थिरता दोनों की स्थिति में न्यूटन-रेफसन विधि से बेहतर कर सकती हैं। इनका उपयोग विभाजन-और-कॉन्कर एल्गोरिथ्म के पुनरावृत्त भाग को बेहतर बनाने के लिए किया जा सकता है।

विभाजन-और-कॉन्कर एल्गोरिथ्म आसानी से समानांतर है, और एलएपीएसीके (LAPACK) जैसे रैखिक बीजगणित कंप्यूटिंग पैकेज में उच्च गुणवत्ता वाले समानांतर कार्यान्वयन सम्मिलित हैं।

संदर्भ

• Demmel, James W. (1997), Applied Numerical Linear Algebra, Philadelphia, PA: Society for Industrial and Applied Mathematics, ISBN 0-89871-389-7, MR 1463942.
• Cuppen, J.J.M. (1981). "A Divide and Conquer Method for the Symmetric Tridiagonal Eigenproblem". Numerische Mathematik. 36 (2): 177–195. doi:10.1007/BF01396757. S2CID 120504744.