Power iteration for matrices with power series entries

तकनीकी सारांश: पावर सीरीज़ प्रविष्टियों वाले मैट्रिसेस के लिए पावर इटरेशन

समस्या विवरण
यह शोध पत्र पावर सीरीज़ प्रविष्टियों वाले मैट्रिसेस, विशेष रूप से लेवी-सेल्वा फील्ड $\mathbb{C}$ और पुइस्यू सीरीज़ फील्ड (Puiseux series field) के लिए आइगेनवैल्यू (eigenvalues) और आइगेनवेक्टर्स (eigenvectors) खोजने की समस्या को संबोधित करता है। जबकि पावर सीरीज़ क्षेत्रों पर बहुपदों के मूल (roots) खोजना बीजगणितीय ज्यामिति और भौतिकी (जैसे हैमिल्टोनियन सिस्टम, इलेक्ट्रिकल नेटवर्क) में एक सुस्थापित समस्या है, इन क्षेत्रों पर मैट्रिक्स आइगेनवैल्यू समस्याओं को हल करने पर सीमित ध्यान दिया गया है। मौजूदा विधियों, जैसे कि विशेषता बहुपद (characteristic polynomial) के मूलों की गणना करना, को गणनात्मक रूप से महंगा बताया गया है। लेखक शास्त्रीय पावर इटरेशन विधि—जो जटिल मैट्रिसेस के लिए एक मानक संख्यात्मक तकनीक है—को इन नॉन-आर्किमिडियन क्षेत्रों (non-Archimedean fields) के अनुकूल बनाने का लक्ष्य रखते हैं, जहाँ मानक अभिसरण (convergence) परिभाषाएँ सीधे लागू नहीं होती हैं।

कार्यप्रणाली और सैद्धांतिक ढांचा
कार्यप्रणाली का मुख्य आधार लेवी-सेल्वा फील्ड ($\mathbb{R}$ और $\mathbb{C}$) के गुण हैं, जो एक नॉन-आर्किमिडियन, कॉची-पूर्ण (Cauchy-complete), रियल-क्लोज्ड (और $\mathbb{C}$ के लिए बीजगणितीय रूप से बंद) क्रमबद्ध क्षेत्र है। लेखक इस संदर्भ में दो प्रकार के अभिसरण के बीच अंतर स्पष्ट करते हैं:

1. सुदृढ़ अभिसरण (Strong Convergence): ऑर्डर टोपोलॉजी के सापेक्ष अभिसरण।
2. दुर्बल अभिसरण (Weak Convergence): सामान्य अर्थ में गुणांकों (coefficients) का अभिसरण, जो पावर सीरीज़ निरूपणों के लिए महत्वपूर्ण है।

लेखक दुर्बल अभिसरण के संबंध में कई सहायक परिणाम स्थापित करते हैं, जिनमें शामिल हैं:

• "नियमित" अनुक्रमों (left-finite support unions वाले अनुक्रमों) के लिए योग और गुणन के तहत दुर्बल अभिसरण की निरंतरता।
• विशिष्ट शर्तों के तहत व्युत्क्रम ($1/a_k \to 1/a$) और वर्ग मूल ($\sqrt{a_k} \to \sqrt{a}$) का दुर्बल अभिसरण (जैसे, $a[0] \neq 0$)।
• सपोर्ट के बाध्यकृत उपसमुच्चयों पर गुणांकों के समान अभिसरण (uniform convergence) पर आधारित दुर्बल अभिसरण का एक मानदंड।

पावर इटरेशन एल्गोरिदम
यह शोध पत्र सिद्ध करता है कि लेवी-सेल्वा फील्ड $\mathbb{C}$ पर विकर्णीय (diagonalizable) मैट्रिसेस के लिए पावर इटरेशन विधि दुर्बल रूप से अभिसरित होती है, यदि निम्नलिखित स्थितियाँ पूरी हों:

1. मैट्रिक्स में अधिकतम {at most} परिमित प्रविष्टियाँ हैं (अर्थात, वैल्यूएशन $\lambda(a_{ij}) \geq 0$)।
2. एक अद्वितीय आइगेनवैल्यू है जिसका "जटिल भाग" (अर्थात, $d^0$ पद का गुणांक, जिसे $\nu[0]$ कहा जाता है) का पूर्ण मान (absolute value) सबसे बड़ा है।
3. प्रारंभिक वेक्टर में डोमिनेंट आइगेनवेक्टर की दिशा में एक गैर-शून्य घटक है।

विशेष रूप से, यदि $\nu_1$ डोमिनेंट आइगेनवैल्यू है ऐसा कि $|\nu_1[0]| > |\nu_2[0]| \geq \dots$, तो सामान्यीकृत वेक्टरों का अनुक्रम $x_k / \|x_k\|$ डोमिनेंट आइगेनवेक्टर की ओर दुर्बल रूप से अभिसरित होता है। इसके अतिरिक्त, रेले कोटिएंट (Rayleigh quotient) $u_k^* A u_k / \|u_k\|^2$ डोमिनेंट आइगेनवैल्यू की ओर दुर्बल रूप से अभिसरित होता है।

उन मैट्रिसेस को संभालने के लिए जो शुरू में "अधिकतम परिमित" शर्त को पूरा नहीं करते हैं या जहाँ डोमिनेंट आइगेनवैल्यू तुरंत स्पष्ट नहीं होता है, लेखक एक स्केलिंग रणनीति प्रस्तावित करते हैं:

• न्यूनतम वैल्यूएशन $q_0$ द्वारा मैट्रिक्स प्रविष्टियों को शिफ्ट करके एक मैट्रिक्स $A' = d^{-q_0}A$ बनाना।
• "जटिल भाग" मैट्रिक्स $\pi(A')$ (0-वें गुणांकों का मैट्रिक्स) का विश्लेषण करना।
• यदि $\pi(A')$ में एक डोमिनेटेड आइगेनवैल्यू है, तो मूल मैट्रिक्स के डोमिनेंट आइगेनवैल्यू और आइगेनवेक्टर को खोजने के लिए स्केल्ड मैट्रिक्स पर पावर इटरेशन लागू किया जा सकता है।

इस दृष्टिकोण को पुइस्यू सीरीज़ फील्ड तक विस्तारित किया गया है, जो लेवी-सेल्वा फील्ड का एक उपक्षेत्र है, जिससे विधि को पुइस्यू सीरीज़ प्रविष्टियों वाले मैट्रिसेस पर लागू करना संभव हो जाता है।

प्रमुख परिणाम

• प्रमेय 5.5: यह स्थापित करता है कि यदि एक विकर्णीय मैट्रिक्स $A$ (संभवतः अनंत रूप से बड़े या छोटे प्रविष्टियों वाला) को इस तरह स्केल किया जा सकता है कि उसका "जटिल भाग" मैट्रिक्स एक स्ट्रिक्टली डोमिनेटेड आइगेनवैल्यू रखता है, तो पावर इटरेशन विधि सफलतापूर्वक सबसे बड़े मोडुलस आइगेनवैल्यू और संगत आइगेनवेक्टर को खोज लेती है।
• उपप्रमेय (Corollary) 5.7: पुष्टि करता है कि विधि पुइस्यू सीरीज़ फील्ड पर विकर्णीय मैट्रिसेस पर लागू होती है, और उसी क्षेत्र के भीतर परिणाम देती है।
• अभिसरण प्रमाण: शोध पत्र अनुक्रमों की नियमितता और लेवी-सेल्वा फील्ड में बीजगणितीय ऑपरेशनों की निरंतरता का उपयोग करते हुए वेक्टर अनुक्रम और रेले कोटिएंट के दुर्बल अभिसरण के लिए कठोर प्रमाण प्रदान करता है।

कार्यान्वयन और प्रयोगात्मक परिणाम
लेखकों ने एल्गोरिदम को पायथन (Python) में लागू किया है। उन्होंने पुइस्यू सीरीज़ फील्ड $\mathbb{R}\{\{t\}\}$ पर एक डिग्री-21 बहुपद के कंपैनियन मैट्रिक्स (companion matrix) पर विधि का परीक्षण किया।

• जटिलता (Complexity): कंपैनियन मैट्रिसेस के लिए, समय जटिलता $O(n d_t \log(d_t))$ अनुमानित है, जहाँ $n$ मैट्रिक्स का आयाम है और $d_t$ वेरिएबल $t$ का अधिकतम डिग्री है। अनिश्चित मैट्रिसेस के लिए, यह $O(n^2 d_t \log(d_t))$ है।
• प्रदर्शन: एक विशिष्ट परीक्षण मामले (डिग्री 21 बहुपद) में, एल्गोरिदम 100 इटरेशन में सबसे बड़े मूल (जिसे $100 + t + \dots$ के रूप में अनुमानित किया गया है) तक अभिसरित हुआ। त्रुटि (error) काफी कम हो गई, जो अधिकांश घटकों के लिए $10^{-12}$ से $10^{-14}$ के परिमाण तक पहुँच गई। 100 इटरेशन के लिए निष्पादन समय एक लेनोवो (Lenovo) p50 पर लगभग 135 सेकंड था।
• अवलोकन: लेखक नोट करते हैं कि एल्गोरिदम के एक संशोधित संस्करण के साथ प्रदर्शन में काफी सुधार किया जा सकता है। वे यह भी उल्लेख करते हैं कि शेष वेक्टर्स को खोजने या सभी वेक्टर्स को एक साथ खोजने के लिए पूरक उपकरणों के रूप में इनवर्स वेक्टर इटरेशन, सबस्पेस इटरेशन और QR एल्गोरिदम को लागू करना संभव है।

महत्व और दावे
शोध पत्र का दावा है कि यह विशेष रूप से पावर सीरीज़ प्रविष्टियों वाले मैट्रिसेस के लिए डिज़ाइन किया गया पहला पावर इटरेशन एल्गोरिदम प्रदान करता है। लेखक तर्क देते हैं कि यह विधि न केवल सैद्धांतिक रूप से दिलचस्प है, बल्कि मल्टीवेरिएट बहुपदों के मूल खोजने के लिए आगे के संख्यात्मक दृष्टिकोण विकसित करने का मार्ग भी खोलती है। वे सुझाव देते हैं कि ये नए दृष्टिकोण उन मौजूदा विधियों की तुलना में बेहतर स्थिरता और दक्षता प्रदान कर सकते हैं जो विशेषता बहुपदों के मूलों की गणना करने पर निर्भर करती हैं। यह कार्य बीजगणितीय ज्यामिति (जहाँ पुइस्यू सीरीज़ आम है) और संख्यात्मक रैखिक बीजगणित (numerical linear algebra) के बीच के अंतर को एक मौलिक पुनरावृत्त विधि (iterative method) को अनुकूलित करके पाटता है।