लैंज़ोस एल्गोरिथ्म

लैंक्ज़ोस एल्गोरिथ्म एक पुनरावृत्तीय विधि है जिसे कॉर्नेलियस लैंक्ज़ोस द्वारा विकसित किया गया था, जो एक n×n हर्मिटीयन मैट्रिक्स के m "सबसे उपयोगी" (अत्यधिक उच्चतम या निम्नतम की ओर प्रवृत्त) eigenvalues और eigenvectors खोजने के लिए पावर विधियों को अनुकूलित करती है, जहाँ m अक्सर n से काफी छोटा होता है, हालाँकि आवश्यक नहीं। हालाँकि सैद्धांतिक रूप से कम्प्यूटेशनल रूप से कुशल, प्रारंभिक रूप में यह विधि अपनी संख्यात्मक अस्थिरता के कारण उपयोगी नहीं थी। 1970 में, ओजाल्वो और न्यूमैन ने दिखाया कि विधि को संख्यात्मक रूप से स्थिर कैसे बनाया जाए और इसे गतिशील भार के अधीन बहुत बड़ी इंजीनियरिंग संरचनाओं के समाधान पर लागू किया। यह लैंक्ज़ोस वैक्टर को शुद्ध करने की एक विधि का उपयोग करके प्राप्त किया गया था (अर्थात प्रत्येक नए उत्पन्न वेक्टर को पहले उत्पन्न सभी वैक्टरों के साथ बार-बार पुनःऑर्थोगोनलाइज़ करके) किसी भी सटीकता की डिग्री तक, जिसे निष्पादित न करने पर, वैक्टरों की एक श्रृंखला उत्पन्न होती थी जो सबसे कम प्राकृतिक आवृत्तियों से जुड़े वैक्टरों द्वारा अत्यधिक दूषित होती थी।

अपने मूल कार्य में, इन लेखकों ने यह भी सुझाव दिया कि प्रारंभिक वेक्टर कैसे चुनें (अर्थात प्रारंभिक वेक्टर के प्रत्येक तत्व को चुनने के लिए एक यादृच्छिक-संख्या जनरेटर का उपयोग करें) और m, कम किए गए वैक्टरों की संख्या निर्धारित करने के लिए एक अनुभवजन्य रूप से निर्धारित विधि सुझाई (अर्थात इसे लगभग 1.5 गुना वांछित सटीक eigenvalues की संख्या के रूप में चुना जाना चाहिए)। उनके कार्य के तुरंत बाद पेज का कार्य आया, जिन्होंने एक त्रुटि विश्लेषण भी प्रदान किया। 1988 में, ओजाल्वो ने इस एल्गोरिथ्म का एक अधिक विस्तृत इतिहास और एक कुशल eigenvalue त्रुटि परीक्षण प्रस्तुत किया।

एल्गोरिथ्म अवलोकन

आकार n×n का एक हर्मिटीयन मैट्रिक्स A इनपुट करें, और वैकल्पिक रूप से पुनरावृत्तियों की संख्या m (डिफ़ॉल्ट रूप से, m=n लें)। कड़ाई से कहें तो, एल्गोरिथ्म को स्पष्ट मैट्रिक्स तक पहुंच की आवश्यकता नहीं है, बल्कि केवल एक फ़ंक्शन v↦Av की आवश्यकता है जो मैट्रिक्स के गुणनफल को एक मनमाना वेक्टर द्वारा गणना करता है। इस फ़ंक्शन को अधिकतम m बार कॉल किया जाता है। आउटपुट एक n×m मैट्रिक्स V है जिसमें ऑर्थोनॉर्मल कॉलम और एक त्रिविकर्णीय वास्तविक सममित मैट्रिक्स T=VAV आकार m×m का है। यदि m=n, तो V एकात्मक है, और A=VTV। लैंक्ज़ोस पुनरावृत्ति संख्यात्मक अस्थिरता के लिए प्रवण है; जब गैर-सटीक अंकगणित में निष्पादित किया जाता है, तो परिणामों की वैधता सुनिश्चित करने के लिए अतिरिक्त उपाय (जैसा कि बाद के अनुभागों में उल्लिखित है) किए जाने चाहिए।

एल्गोरिथ्म ऑर्थोनॉर्मल वैक्टरों v1, v2, ..., vm का एक अनुक्रम उत्पन्न करके आगे बढ़ता है जो क्रायलोव उपसमष्टि के लिए एक आधार बनाते हैं। मानक 1 के एक मनमाना वेक्टर v1 से शुरू करते हुए, प्रत्येक चरण मैट्रिक्स A को लागू करके, पिछले वेक्टर के विरुद्ध ऑर्थोगोनलाइज़ करके, और सामान्यीकरण करके एक नया वेक्टर गणना करता है। गुणांक αj और βj त्रिविकर्णीय मैट्रिक्स T के विकर्ण और ऑफ-विकर्ण प्रविष्टियाँ बनाते हैं, जिनके eigenvalues A के eigenvalues का अनुमान लगाते हैं।

संख्यात्मक स्थिरता और पुनःऑर्थोगोनलाइज़ेशन

मूल लैंक्ज़ोस एल्गोरिथ्म फ्लोटिंग-पॉइंट राउंडऑफ के कारण ऑर्थोगोनैलिटी के नुकसान से पीड़ित था, जिससे नकली eigenvalues और गलत eigenvectors उत्पन्न होते थे। 1970 में ओजाल्वो और न्यूमैन द्वारा स्थिरीकरण ने पूर्ण पुनःऑर्थोगोनलाइज़ेशन पेश किया: प्रत्येक नए उत्पन्न वेक्टर को पहले उत्पन्न सभी वैक्टरों के विरुद्ध ऑर्थोगोनलाइज़ किया जाता है। यह लैंक्ज़ोस वैक्टरों को शुद्ध करता है और संख्यात्मक स्थिरता बहाल करता है, हालाँकि बढ़ी हुई कम्प्यूटेशनल लागत की कीमत पर। 1970 के दशक की शुरुआत में पेज का त्रुटि विश्लेषण राउंडऑफ के प्रभावों पर सैद्धांतिक सीमाएँ प्रदान करता है और पुनःऑर्थोगोनलाइज़ेशन दृष्टिकोण को उचित ठहराता है।

मशीन लर्निंग में अनुप्रयोग

मशीन लर्निंग में, लैंक्ज़ोस एल्गोरिथ्म का उपयोग बड़े पैमाने पर eigenvalue समस्याओं के लिए किया जाता है, जैसे PCA में सहप्रसरण मैट्रिक्स के शीर्ष eigenvalues की गणना करना या वर्णक्रमीय क्लस्टरिंग। यह डीप लर्निंग में तंत्रिका नेटवर्क के हेसियन स्पेक्ट्रम का अनुमान लगाने के लिए भी नियोजित है, जो अनुकूलन और सामान्यीकरण विश्लेषण में सहायता करता है। एल्गोरिथ्म की केवल मैट्रिक्स-वेक्टर गुणनफल के साथ काम करने की क्षमता इसे बड़े भाषा मॉडल और जनरेटिव AI प्रणालियों में उत्पन्न होने वाले बहुत बड़े मैट्रिक्स के लिए उपयुक्त बनाती है, जहाँ स्पष्ट मैट्रिक्स भंडारण असंभव है।

संबंधित विधियाँ और विस्तार

लैंक्ज़ोस एल्गोरिथ्म रैखिक प्रणालियों को हल करने के लिए संयुग्म ग्रेडिएंट विधि से निकटता से संबंधित है, क्योंकि दोनों क्रायलोव उपसमष्टि बनाते हैं। यह गैर-हर्मिटीयन मैट्रिक्स के लिए अर्नोल्डी पुनरावृत्ति से भी जुड़ता है। ब्लॉक लैंक्ज़ोस एल्गोरिथ्म जैसे वेरिएंट कई प्रारंभिक वैक्टरों को संभालते हैं, और अंतर्निहित रूप से पुनःप्रारंभित लैंक्ज़ोस विधि (ARPACK में उपयोग की जाने वाली) अभिसरण और मेमोरी उपयोग में सुधार करती है। ये विस्तार LAPACK और SciPy जैसी संख्यात्मक लाइब्रेरीज़ में लागू किए गए हैं, जिससे एल्गोरिथ्म वैज्ञानिक कंप्यूटिंग में एक मानक उपकरण बन गया है।

ऐतिहासिक प्रभाव और आधुनिक उपयोग

अपने स्थिरीकरण के बाद से, लैंक्ज़ोस एल्गोरिथ्म संरचनात्मक इंजीनियरिंग, क्वांटम रसायन विज्ञान और सिग्नल प्रोसेसिंग पर लागू किया गया है। कृत्रिम बुद्धिमत्ता के संदर्भ में, यह डेटा विश्लेषण और मॉडल संपीड़न में उपयोग की जाने वाली कई वर्णक्रमीय विधियों को रेखांकित करता है। एल्गोरिथ्म की दक्षता और मजबूती ने इसे संख्यात्मक रैखिक बीजगणित का एक आधारशिला बना दिया है, जिसमें आधुनिक हार्डवेयर जैसे GPU और विशेष AI त्वरक के लिए इसकी स्थिरता और समानांतरीकरण में सुधार पर चल रहे शोध हैं।

यह भी देखें

• पावर पुनरावृत्ति
• eigenvalue अपघटन
• क्रायलोव उपसमष्टि
• संयुग्म ग्रेडिएंट