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

For the null space-finding algorithm, see block Lanczos algorithm.

For the interpolation method, see Lanczos resampling.

For the approximation of the gamma function, see Lanczos approximation.

लैंज़ोस एल्गोरिदम कॉर्नेलियस लैंज़ोस द्वारा तैयार की गई एक पुनरावृत्तीय विधि है जो खोजने के लिए शक्ति पुनरावृत्ति का एक अनुकूलन है $m$ सबसे उपयोगी (अति उच्चतम/निम्नतम की ओर रुझान) eigenvalues ​​​​और eigenvectors $n\times n$ हर्मिटियन मैट्रिक्स, कहाँ $m$ अक्सर होता है लेकिन जरूरी नहीं कि उससे बहुत छोटा हो $n$. यद्यपि सैद्धांतिक रूप से कम्प्यूटेशनल रूप से कुशल, प्रारंभिक रूप से तैयार की गई विधि अपनी संख्यात्मक स्थिरता के कारण उपयोगी नहीं थी।

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

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

एल्गोरिदम

एक हर्मिटियन मैट्रिक्स इनपुट करें $A$ आकार का $n\times n$, और वैकल्पिक रूप से कई पुनरावृत्तियाँ $m$ (डिफ़ॉल्ट के रूप में, चलो $m=n$).

• कड़ाई से बोलते हुए, एल्गोरिदम को स्पष्ट मैट्रिक्स तक पहुंच की आवश्यकता नहीं है, बल्कि केवल एक फ़ंक्शन की आवश्यकता है $v\mapsto Av$ जो एक मनमाना वेक्टर द्वारा मैट्रिक्स के उत्पाद की गणना करता है। इस फ़ंक्शन को अधिक से अधिक कॉल किया जाता है $m$ बार.

आउटपुट ए $n\times m$ आव्यूह $V$ रूढ़िवादिता कॉलम और एक त्रिविकर्ण मैट्रिक्स वास्तविक सममित मैट्रिक्स के साथ $T=V^{*}AV$ आकार का $m\times m$. अगर $m=n$, तब $V$ एकात्मक मैट्रिक्स है, और $A=VTV^{*}$.

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

1. होने देना $v_{1}\in \mathbb {C} ^{n}$ यूक्लिडियन मानदंड के साथ एक मनमाना वेक्टर बनें $1$.
2. संक्षिप्त प्रारंभिक पुनरावृत्ति चरण:
   1. होने देना $w_{1}'=Av_{1}$.
   2. होने देना $\alpha _{1}=w_{1}'^{*}v_{1}$.
   3. होने देना $w_{1}=w_{1}'-\alpha _{1}v_{1}$.
3. के लिए $j=2,\dots ,m$ करना:
   1. होने देना $\beta _{j}=\|w_{j-1}\|$ (यूक्लिडियन मानदंड भी)।
   2. अगर $\beta _{j}\neq 0$, तो करने दें $v_{j}=w_{j-1}/\beta _{j}$,

      अन्यथा इस रूप में चुनें $v_{j}$ यूक्लिडियन मानदंड के साथ एक मनमाना वेक्टर $1$ यह सभी के लिए ओर्थोगोनल है $v_{1},\dots ,v_{j-1}$.

   3. होने देना $w_{j}'=Av_{j}$.
   4. होने देना $\alpha _{j}=w_{j}'^{*}v_{j}$.
   5. होने देना $w_{j}=w_{j}'-\alpha _{j}v_{j}-\beta _{j}v_{j-1}$.
4. होने देना $V$ कॉलम के साथ मैट्रिक्स बनें $v_{1},\dots ,v_{m}$. होने देना $T={\begin{pmatrix}\alpha _{1}&\beta _{2}&&&&0\\\beta _{2}&\alpha _{2}&\beta _{3}&&&\\&\beta _{3}&\alpha _{3}&\ddots &&\\&&\ddots &\ddots &\beta _{m-1}&\\&&&\beta _{m-1}&\alpha _{m-1}&\beta _{m}\\0&&&&\beta _{m}&\alpha _{m}\\\end{pmatrix}}$.

टिप्पणी $Av_{j}=w_{j}'=\beta _{j+1}v_{j+1}+\alpha _{j}v_{j}+\beta _{j}v_{j-1}$ के लिए $1<j<m$.

पुनरावृत्ति प्रक्रिया को लिखने के सैद्धांतिक रूप से चार तरीके हैं। पेगे और अन्य कार्यों से पता चलता है कि संचालन का उपरोक्त क्रम संख्यात्मक रूप से सबसे स्थिर है। व्यवहार में प्रारंभिक वेक्टर $v_{1}$ प्रक्रिया के एक अन्य तर्क के रूप में लिया जा सकता है $\beta _{j}=0$ और संख्यात्मक अशुद्धि के संकेतकों को अतिरिक्त लूप समाप्ति शर्तों के रूप में शामिल किया जा रहा है।

मैट्रिक्स-वेक्टर गुणन की गणना न करते हुए, प्रत्येक पुनरावृत्ति करता है $O(n)$ अंकगणितीय परिचालन. मैट्रिक्स-वेक्टर गुणन किया जा सकता है $O(dn)$ अंकगणितीय संक्रियाएँ जहाँ $d$ एक पंक्ति में शून्येतर तत्वों की औसत संख्या है। कुल जटिलता इस प्रकार है $O(dmn)$, या $O(dn^{2})$ अगर $m=n$; लैंज़ोस एल्गोरिदम विरल मैट्रिक्स के लिए बहुत तेज़ हो सकता है। संख्यात्मक स्थिरता में सुधार के लिए योजनाओं को आम तौर पर इस उच्च प्रदर्शन के आधार पर आंका जाता है।

वैक्टर $v_{j}$ लैंज़ोस वैक्टर कहलाते हैं। सदिश $w_{j}'$ के बाद उपयोग नहीं किया जाता है $w_{j}$ गणना की जाती है, और वेक्टर $w_{j}$ के बाद उपयोग नहीं किया जाता है $v_{j+1}$ गणना की जाती है. इसलिए कोई भी तीनों के लिए एक ही भंडारण का उपयोग कर सकता है। इसी तरह, यदि केवल त्रिविकर्ण मैट्रिक्स $T$ मांगा जाता है, तो कच्चे पुनरावर्तन की आवश्यकता नहीं होती $v_{j-1}$ गणना करने के बाद $w_{j}$, हालाँकि संख्यात्मक स्थिरता में सुधार के लिए कुछ योजनाओं को बाद में इसकी आवश्यकता होगी। कभी-कभी बाद के लैंज़ोस वैक्टर की पुनर्गणना की जाती है $v_{1}$ जब जरूरत है।

eigenproblem के लिए आवेदन

लैंज़ोस एल्गोरिदम को अक्सर मैट्रिक्स के आइगेनवैल्यू और आइजेनवेक्टर खोजने के संदर्भ में लाया जाता है, लेकिन जबकि एक सामान्य मैट्रिक्स विकर्णीकरण आइजेनवेक्टर और आइगेनवैल्यू को निरीक्षण से स्पष्ट कर देगा, वही लैंज़ोस एल्गोरिदम द्वारा किए गए ट्राइडिएगोनलाइज़ेशन के लिए सच नहीं है; एक भी eigenvalue या eigenvector की गणना करने के लिए गैर-तुच्छ अतिरिक्त चरणों की आवश्यकता होती है। फिर भी, लैंज़ोस एल्गोरिथ्म को लागू करना अक्सर आइगेंडेकंपोजीशन की गणना में एक महत्वपूर्ण कदम है। अगर $\lambda$ का एक प्रतिरूप है $A$, और अगर $Tx=\lambda x$ ($x$ का एक eigenvector है $T$) तब $y=Vx$ का संगत eigenvector है $A$ (तब से $Ay=AVx=VTV^{*}Vx=VTIx=VTx=V(\lambda x)=\lambda Vx=\lambda y$). इस प्रकार लैंज़ोस एल्गोरिथ्म eigendecomposition समस्या को बदल देता है $A$ eigendecomposition समस्या के लिए $T$.

1. त्रिविकर्ण मैट्रिक्स के लिए, कई विशिष्ट एल्गोरिदम मौजूद हैं, जो अक्सर सामान्य-उद्देश्य एल्गोरिदम की तुलना में बेहतर कम्प्यूटेशनल जटिलता के साथ होते हैं। उदाहरण के लिए, यदि $T$ एक $m\times m$ त्रिविकर्ण सममित मैट्रिक्स तब:
   • त्रिविकर्ण मैट्रिक्स#निर्धारक विशेषता बहुपद की गणना करने की अनुमति देता है $O(m^{2})$ संचालन, और एक बिंदु पर इसका मूल्यांकन करना $O(m)$ परिचालन.
   • फूट डालो और जीतो eigenvalue एल्गोरिदम का उपयोग संपूर्ण eigendecomposition की गणना करने के लिए किया जा सकता है $T$ में $O(m^{2})$ परिचालन.
   • फास्ट मल्टीपोल विधि सभी eigenvalues ​​​​की गणना बस में कर सकते हैं $O(m\log m)$ परिचालन.
2. कुछ सामान्य eigendecomposition एल्गोरिदम, विशेष रूप से QR एल्गोरिदम, सामान्य मैट्रिक्स की तुलना में त्रिविकर्ण मैट्रिक्स के लिए तेजी से अभिसरण करने के लिए जाने जाते हैं। त्रिविकर्ण QR की स्पर्शोन्मुख जटिलता है $O(m^{2})$ ठीक वैसे ही जैसे कि फूट डालो और जीतो एल्गोरिथ्म के लिए (हालाँकि स्थिर कारक भिन्न हो सकता है); चूँकि eigenvectors एक साथ हैं $m^{2}$ तत्व, यह स्पर्शोन्मुख रूप से इष्टतम है।
3. यहां तक ​​कि एल्गोरिदम जिनकी अभिसरण दरें एकात्मक परिवर्तनों से अप्रभावित हैं, जैसे कि शक्ति विधि और व्युत्क्रम पुनरावृत्ति, त्रिविकर्ण मैट्रिक्स पर लागू होने से निम्न-स्तरीय प्रदर्शन लाभ का आनंद ले सकते हैं $T$ मूल मैट्रिक्स के बजाय $A$. तब से $T$ अत्यधिक पूर्वानुमानित स्थितियों में सभी गैर-शून्य तत्वों के साथ बहुत विरल है, यह कैश (कंप्यूटिंग) की तुलना में उत्कृष्ट प्रदर्शन के साथ कॉम्पैक्ट स्टोरेज की अनुमति देता है। वैसे ही, $T$ जबकि सभी eigenvectors और eigenvalues ​​​​वास्तविक के साथ एक वास्तविक संख्या मैट्रिक्स है $A$ सामान्य तौर पर इसमें जटिल तत्व और आइजनवेक्टर हो सकते हैं, इसलिए वास्तविक अंकगणित आइजनवेक्टर और आइजनवेक्टर खोजने के लिए पर्याप्त है $T$.
4. अगर $n$ बहुत बड़ा है, फिर घट रहा है $m$ ताकि $T$ प्रबंधनीय आकार का होने पर भी यह अधिक चरम आइजनवैल्यू और आइजेनवेक्टर खोजने की अनुमति देगा $A$; में $m\ll n$ क्षेत्र में, लैंज़ोस एल्गोरिथ्म को हर्मिटियन मैट्रिसेस के लिए एक हानिपूर्ण संपीड़न योजना के रूप में देखा जा सकता है, जो चरम स्वदेशी मूल्यों को संरक्षित करने पर जोर देता है।

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

त्रिविकर्णीकरण का अनुप्रयोग

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

• लैंज़ोस फायदा उठाता है $A$ एक विरल मैट्रिक्स होने के नाते, जबकि हाउसहोल्डर ऐसा नहीं करता है, और विरल मैट्रिक्स #रिड्यूसिंग फिल-इन|फिल-इन उत्पन्न करेगा।
• लैंज़ोस मूल मैट्रिक्स के साथ काम करता है $A$ (और इसे केवल अंतर्निहित रूप से ज्ञात होने में कोई समस्या नहीं है), जबकि कच्चा हाउसहोल्डर गणना के दौरान मैट्रिक्स को संशोधित करना चाहता है (हालांकि इससे बचा जा सकता है)।
• लैंज़ोस एल्गोरिथ्म का प्रत्येक पुनरावृत्ति अंतिम परिवर्तन मैट्रिक्स का एक और कॉलम तैयार करता है $V$, जबकि हाउसहोल्डर का एक पुनरावृत्ति एकात्मक गुणनखंडन में एक और कारक उत्पन्न करता है $Q_{1}Q_{2}\dots Q_{n}$ का $V$. हालाँकि, प्रत्येक कारक एक एकल वेक्टर द्वारा निर्धारित होता है, इसलिए भंडारण आवश्यकताएँ दोनों एल्गोरिदम के लिए समान हैं, और $V=Q_{1}Q_{2}\dots Q_{n}$ में गणना की जा सकती है $O(n^{3})$ समय।
• गृहस्वामी संख्यात्मक रूप से स्थिर है, जबकि कच्चा लैंज़ोस नहीं है।
• लैंज़ोस अत्यधिक समानांतर है, केवल के साथ $O(n)$ सिंक्रोनाइज़ेशन के बिंदु (कंप्यूटर विज्ञान) (की गणना) $\alpha _{j}$ और $\beta _{j}$). गृहस्थ कम समानांतर होता है, जिसका एक क्रम होता है $O(n^{2})$ अदिश मात्राओं की गणना की जाती है जिनमें से प्रत्येक अनुक्रम में पिछली मात्रा पर निर्भर करती है।

एल्गोरिदम की व्युत्पत्ति

तर्क की कई पंक्तियाँ हैं जो लैंज़ोस एल्गोरिदम की ओर ले जाती हैं।

एक अधिक भविष्य शक्ति विधि

Main article: Power iteration

सबसे बड़े परिमाण के आइजेनवैल्यू और मैट्रिक्स के संबंधित आइजेनवेक्टर को खोजने की शक्ति विधि $A$ मोटे तौर पर है

1. एक यादृच्छिक वेक्टर चुनें $u_{1}\neq 0$.
2. के लिए $j\geqslant 1$ (के निर्देश तक $u_{j}$ एकत्रित हो गया है) करें:
   1. होने देना $u_{j+1}'=Au_{j}.$
   2. होने देना $u_{j+1}=u_{j+1}'/\|u_{j+1}'\|.$

• बड़े में $j$ सीमा, $u_{j}$ सबसे बड़े परिमाण के आइगेनवैल्यू के अनुरूप मानक आइजेनवेक्टर के पास पहुंचता है।

इस पद्धति के खिलाफ जो आलोचना की जा सकती है वह यह है कि यह बेकार है: इसमें मैट्रिक्स से जानकारी निकालने में बहुत सारा काम (चरण 2.1 में मैट्रिक्स-वेक्टर उत्पाद) खर्च होता है $A$, लेकिन केवल अंतिम परिणाम पर ही ध्यान देता है; कार्यान्वयन आम तौर पर सभी वैक्टरों के लिए समान चर का उपयोग करते हैं $u_{j}$, प्रत्येक नए पुनरावृत्ति में पिछले वाले के परिणामों को अधिलेखित कर दिया जाता है। इसके बजाय सभी मध्यवर्ती परिणामों को रखना और डेटा को व्यवस्थित करना वांछनीय हो सकता है।

जानकारी का एक टुकड़ा जो तुच्छ रूप से वैक्टर से उपलब्ध है $u_{j}$ क्रायलोव उपस्थानों की एक श्रृंखला है। यह बताने का एक तरीका कि एल्गोरिथम में सेट शामिल किए बिना यह दावा करना है कि यह गणना करता है

उपसमुच्चय $\{v_{j}\}_{j=1}^{m}$ के एक आधार का $\mathbb {C} ^{n}$ ऐसा है कि $Ax\in \operatorname {span} (v_{1},\dotsc ,v_{j+1})$ हरएक के लिए $x\in \operatorname {span} (v_{1},\dotsc ,v_{j})$ और सभी $1\leqslant j<m;$

यह तुच्छ रूप से संतुष्ट है $v_{j}=u_{j}$ जब तक कि $u_{j}$ से रैखिक रूप से स्वतंत्र है $u_{1},\dotsc ,u_{j-1}$ (और यदि ऐसी कोई निर्भरता है तो कोई इसे चुनकर अनुक्रम जारी रख सकता है $v_{j}$ एक मनमाना वेक्टर रैखिक रूप से स्वतंत्र है $u_{1},\dotsc ,u_{j-1}$). एक आधार जिसमें शामिल है $u_{j}$ हालाँकि, वेक्टर के संख्यात्मक रूप से खराब होने की संभावना है, क्योंकि वेक्टर का यह क्रम डिजाइन के अनुसार एक आइजेनवेक्टर में परिवर्तित होने के लिए है। $A$. इससे बचने के लिए, कोई व्यक्ति शक्ति पुनरावृत्ति को ग्राम-श्मिट प्रक्रिया के साथ जोड़ सकता है, इसके बजाय इन क्रायलोव उप-स्थानों का एक ऑर्थोनॉर्मल आधार तैयार कर सकता है।

1. एक यादृच्छिक वेक्टर चुनें $u_{1}$ यूक्लिडियन मानदंड का $1$. होने देना $v_{1}=u_{1}$.
2. के लिए $j=1,\dotsc ,m-1$ करना:
   1. होने देना $u_{j+1}'=Au_{j}$.
   2. सभी के लिए $k=1,\dotsc ,j$ होने देना $g_{k,j}=v_{k}^{*}u_{j+1}'$. (ये के निर्देशांक हैं $Au_{j}=u_{j+1}'$ आधार वैक्टर के संबंध में $v_{1},\dotsc ,v_{j}$.)
   3. होने देना $w_{j+1}=u_{j+1}'-\sum _{k=1}^{j}g_{k,j}v_{k}$. (के घटक को रद्द करें $u_{j+1}'$ यह है $\operatorname {span} (v_{1},\dotsc ,v_{j})$.)
   4. अगर $w_{j+1}\neq 0$ तो करने दें $u_{j+1}=u_{j+1}'/\|u_{j+1}'\|$ और $v_{j+1}=w_{j+1}/\|w_{j+1}\|$,

      अन्यथा इस रूप में चुनें $u_{j+1}=v_{j+1}$ यूक्लिडियन मानदंड का एक मनमाना वेक्टर $1$ यह सभी के लिए ओर्थोगोनल है $v_{1},\dotsc ,v_{j}$.

शक्ति पुनरावृत्ति वैक्टर के बीच संबंध $u_{j}$ और ऑर्थोगोनल वैक्टर $v_{j}$ यह है कि

$Au_{j}=\|u_{j+1}'\|u_{j+1}=u_{j+1}'=w_{j+1}+\sum _{k=1}^{j}g_{k,j}v_{k}=\|w_{j+1}\|v_{j+1}+\sum _{k=1}^{j}g_{k,j}v_{k}$.

यहाँ यह देखा जा सकता है कि वास्तव में हमें इसकी आवश्यकता नहीं है $u_{j}$ इनकी गणना करने के लिए वैक्टर $v_{j}$, क्योंकि $u_{j}-v_{j}\in \operatorname {span} (v_{1},\dotsc ,v_{j-1})$ और इसलिए बीच का अंतर $u_{j+1}'=Au_{j}$ और $w_{j+1}'=Av_{j}$ में है $\operatorname {span} (v_{1},\dotsc ,v_{j})$, जिसे ऑर्थोगोनलाइज़ेशन प्रक्रिया द्वारा रद्द कर दिया गया है। इस प्रकार क्रायलोव उप-स्थानों की श्रृंखला के लिए समान आधार की गणना की जाती है

1. एक यादृच्छिक वेक्टर चुनें $v_{1}$ यूक्लिडियन मानदंड का $1$.
2. के लिए $j=1,\dotsc ,m-1$ करना:
   1. होने देना $w_{j+1}'=Av_{j}$.
   2. सभी के लिए $k=1,\dotsc ,j$ होने देना $h_{k,j}=v_{k}^{*}w_{j+1}'$.
   3. होने देना $w_{j+1}=w_{j+1}'-\sum _{k=1}^{j}h_{k,j}v_{k}$.
   4. होने देना $h_{j+1,j}=\|w_{j+1}\|$.
   5. अगर $h_{j+1,j}\neq 0$ तो करने दें $v_{j+1}=w_{j+1}/h_{j+1,j}$,

      अन्यथा इस रूप में चुनें $v_{j+1}$ यूक्लिडियन मानदंड का एक मनमाना वेक्टर $1$ यह सभी के लिए ओर्थोगोनल है $v_{1},\dotsc ,v_{j}$.

एक प्राथमिकता गुणांक $h_{k,j}$ संतुष्ट करना

$Av_{j}=\sum _{k=1}^{j+1}h_{k,j}v_{k}$ सभी के लिए $j<m$;

मानहानि $h_{j+1,j}=\|w_{j+1}\|$ थोड़ा अजीब लग सकता है, लेकिन सामान्य पैटर्न पर फिट बैठता है $h_{k,j}=v_{k}^{*}w_{j+1}'$ तब से

$v_{j+1}^{*}w_{j+1}'=v_{j+1}^{*}w_{j+1}=\|w_{j+1}\|v_{j+1}^{*}v_{j+1}=\|w_{j+1}\|.$

क्योंकि शक्ति पुनरावृत्ति सदिश $u_{j}$ जो इस पुनरावर्ती संतुष्टि से हटा दिए गए थे $u_{j}\in \operatorname {span} (v_{1},\ldots ,v_{j}),$ सदिश $\{v_{j}\}_{j=1}^{m}$ और गुणांक $h_{k,j}$ से पर्याप्त जानकारी शामिल है $A$ वह सब $u_{1},\ldots ,u_{m}$ गणना की जा सकती है, इसलिए वैक्टर बदलने से कुछ भी नुकसान नहीं हुआ। (वास्तव में, यह पता चला है कि यहां एकत्र किया गया डेटा पावर विधि में समान संख्या में पुनरावृत्तियों से प्राप्त होने वाले सबसे बड़े आइगेनवैल्यू का काफी बेहतर अनुमान देता है, हालांकि इस बिंदु पर यह स्पष्ट नहीं है।)

यह अंतिम प्रक्रिया अर्नोल्डी पुनरावृत्ति है। लैंज़ोस एल्गोरिथ्म तब सरलीकरण के रूप में सामने आता है जो गणना के चरणों को समाप्त करने से प्राप्त होता है जो तब तुच्छ हो जाते हैं $A$ हर्मिटियन है—विशेष रूप से अधिकांश $h_{k,j}$ गुणांक शून्य हो जाते हैं।

प्राथमिक रूप से, यदि $A$ तो हर्मिटियन है

$h_{k,j}=v_{k}^{*}w_{j+1}'=v_{k}^{*}Av_{j}=v_{k}^{*}A^{*}v_{j}=(Av_{k})^{*}v_{j}.$

के लिए $k<j-1$ हम वह जानते हैं $Av_{k}\in \operatorname {span} (v_{1},\ldots ,v_{j-1})$, और तबसे $v_{j}$ निर्माण द्वारा इस उप-स्थान के लिए ऑर्थोगोनल है, यह आंतरिक उत्पाद शून्य होना चाहिए। (यह अनिवार्य रूप से यही कारण है कि ऑर्थोगोनल बहुपदों के अनुक्रमों को हमेशा एक ऑर्थोगोनल बहुपद#पुनरावृत्ति संबंध|तीन-अवधि वाला पुनरावृत्ति संबंध दिया जा सकता है।) $k=j-1$ एक मिलता है

$h_{j-1,j}=(Av_{j-1})^{*}v_{j}={\overline {v_{j}^{*}Av_{j-1}}}={\overline {h_{j,j-1}}}=h_{j,j-1}$ चूँकि वेक्टर का आदर्श होने के कारण उत्तरार्द्ध वास्तविक है। के लिए $k=j$ एक मिलता है

$h_{j,j}=(Av_{j})^{*}v_{j}={\overline {v_{j}^{*}Av_{j}}}={\overline {h_{j,j}}},$

मतलब ये भी असली है.

अधिक संक्षेप में, यदि $V$ स्तंभों वाला मैट्रिक्स है $v_{1},\ldots ,v_{m}$ फिर संख्याएँ $h_{k,j}$ मैट्रिक्स के तत्वों के रूप में पहचाना जा सकता है $H=V^{*}AV$, और $h_{k,j}=0$ के लिए $k>j+1;$ गणित का सवाल $H$ हेसेनबर्ग मैट्रिक्स है. तब से

$H^{*}=\left(V^{*}AV\right)^{*}=V^{*}A^{*}V=V^{*}AV=H$ गणित का सवाल $H$ हर्मिटियन है. इसका अर्थ यह है कि $H$ यह हेसेनबर्ग से भी निचला है, इसलिए यह वास्तव में त्रिविजात्मक होना चाहिए। हर्मिटियन होने के कारण, इसका मुख्य विकर्ण वास्तविक है, और चूंकि इसका पहला उपविकर्ण निर्माण से वास्तविक है, इसलिए इसके पहले सुपरविकर्ण के लिए भी यही सच है। इसलिए, $H$ एक वास्तविक, सममित मैट्रिक्स है - मैट्रिक्स $T$ लैंज़ोस एल्गोरिथम विनिर्देश के।

चरम eigenvalues ​​​​का एक साथ सन्निकटन

हर्मिटियन मैट्रिक्स के आइजेनवेक्टरों को चिह्नित करने का एक तरीका $A$ रेले भागफल के स्थिर बिंदुओं के रूप में है

$r(x)={\frac {x^{*}Ax}{x^{*}x}},\qquad x\in \mathbb {C} ^{n}.$

विशेष रूप से, सबसे बड़ा eigenvalue $\lambda _{\max }$ का वैश्विक अधिकतम है $r$ और सबसे छोटा eigenvalue $\lambda _{\min }$ का वैश्विक न्यूनतम है $r$.

निम्न-आयामी उप-स्थान के भीतर ${\mathcal {L}}$ का $\mathbb {C} ^{n}$ अधिकतम का पता लगाना संभव हो सकता है $x$ और न्यूनतम $y$ का $r$. बढ़ती हुई शृंखला के लिए इसे दोहराते हुए ${\mathcal {L}}_{1}\subset {\mathcal {L}}_{2}\subset \cdots$ वैक्टर के दो अनुक्रम उत्पन्न करता है: $x_{1},x_{2},\ldots$ और $y_{1},y_{2},\dotsc$ ऐसा है कि $x_{j},y_{j}\in {\mathcal {L}}_{j}$ और

${\begin{aligned}r(x_{1})&\leqslant r(x_{2})\leqslant \cdots \leqslant \lambda _{\max }\\r(y_{1})&\geqslant r(y_{2})\geqslant \cdots \geqslant \lambda _{\min }\end{aligned}}$

फिर प्रश्न उठता है कि उप-स्थानों का चयन कैसे किया जाए ताकि ये क्रम इष्टतम दर पर अभिसरित हों।

से $x_{j}$, इष्टतम दिशा जिसमें बड़े मूल्यों की तलाश की जा सके $r$ वह ढाल का है $\nabla r(x_{j})$, और इसी तरह से $y_{j}$ छोटे मूल्यों की तलाश करने के लिए इष्टतम दिशा $r$ वह नकारात्मक प्रवणता का है $-\nabla r(y_{j})$. सामान्य रूप में

$\nabla r(x)={\frac {2}{x^{*}x}}(Ax-r(x)x),$

इसलिए मैट्रिक्स अंकगणित में गणना करने के लिए रुचि की दिशाएं काफी आसान हैं, लेकिन यदि कोई दोनों में सुधार करना चाहता है $x_{j}$ और $y_{j}$ फिर ध्यान में रखने के लिए दो नई दिशाएँ हैं: $Ax_{j}$ और $Ay_{j};$ तब से $x_{j}$ और $y_{j}$ रैखिक रूप से स्वतंत्र वैक्टर हो सकते हैं (वास्तव में, ऑर्थोगोनल के करीब हैं), कोई भी सामान्य रूप से उम्मीद नहीं कर सकता है $Ax_{j}$ और $Ay_{j}$ समानांतर होना. का आयाम बढ़ाना आवश्यक नहीं है ${\mathcal {L}}_{j}$ द्वारा $2$ हर कदम पर अगर $\{{\mathcal {L}}_{j}\}_{j=1}^{m}$ क्रायलोव उप-स्थान के रूप में लिया जाता है, क्योंकि तब $Az\in {\mathcal {L}}_{j+1}$ सभी के लिए $z\in {\mathcal {L}}_{j},$ इस प्रकार विशेष रूप से दोनों के लिए $z=x_{j}$ और $z=y_{j}$.

दूसरे शब्दों में, हम कुछ मनमाने प्रारंभिक वेक्टर से शुरुआत कर सकते हैं $x_{1}=y_{1},$ वेक्टर रिक्त स्थान का निर्माण करें

${\mathcal {L}}_{j}=\operatorname {span} (x_{1},Ax_{1},\ldots ,A^{j-1}x_{1})$

और फिर तलाश करो $x_{j},y_{j}\in {\mathcal {L}}_{j}$ ऐसा है कि

$r(x_{j})=\max _{z\in {\mathcal {L}}_{j}}r(z)\qquad {\text{and}}\qquad r(y_{j})=\min _{z\in {\mathcal {L}}_{j}}r(z).$

के बाद से $j$वें शक्ति विधि पुनरावृत्त $u_{j}$ से संबंधित ${\mathcal {L}}_{j},$ यह इस प्रकार है कि उत्पादन करने के लिए एक पुनरावृत्ति $x_{j}$ और $y_{j}$ शक्ति विधि की तुलना में धीमी गति से अभिसरण नहीं किया जा सकता है, और दोनों eigenvalue चरम सीमाओं का अनुमान लगाकर अधिक हासिल किया जाएगा। अनुकूलन की उपसमस्या के लिए $r$ कुछ पर ${\mathcal {L}}_{j}$, लम्बवत आधार रखना सुविधाजनक है $\{v_{1},\ldots ,v_{j}\}$ इस वेक्टर स्पेस के लिए. इस प्रकार हम फिर से क्रायलोव उप-स्थानों के अनुक्रम के लिए ऐसे आधार की पुनरावृत्तीय गणना करने की समस्या की ओर अग्रसर हैं।

अभिसरण और अन्य गतिशीलता

एल्गोरिथ्म की गतिशीलता का विश्लेषण करते समय, eigenvalues ​​​​और eigenvectors लेना सुविधाजनक होता है $A$ जैसा कि दिया गया है, भले ही वे उपयोगकर्ता को स्पष्ट रूप से ज्ञात न हों। अंकन को ठीक करने के लिए, आइए $\lambda _{1}\geqslant \lambda _{2}\geqslant \dotsb \geqslant \lambda _{n}$ आइगेनवैल्यू बनें (ये सभी जानते हैं कि ये वास्तविक हैं, और इस प्रकार ऑर्डर करना संभव है) और चलो $z_{1},\dotsc ,z_{n}$ eigenvectors का एक ऑर्थोनॉर्मल सेट बनें जैसे कि $Az_{k}=\lambda _{k}z_{k}$ सभी के लिए $k=1,\dotsc ,n$.

प्रारंभिक लैंज़ोस वेक्टर के गुणांकों के लिए एक अंकन तय करना भी सुविधाजनक है $v_{1}$ इस eigenbasis के संबंध में; होने देना $d_{k}=z_{k}^{*}v_{1}$ सभी के लिए $k=1,\dotsc ,n$, ताकि $\textstyle v_{1}=\sum _{k=1}^{n}d_{k}z_{k}$. एक आरंभिक सदिश $v_{1}$ कुछ eigencomponent के ख़त्म होने से संबंधित eigenvalue में अभिसरण में देरी होगी, और भले ही यह त्रुटि सीमा में एक स्थिर कारक के रूप में सामने आता है, कमी अवांछनीय बनी हुई है। लगातार इसकी चपेट में आने से बचने के लिए एक सामान्य तकनीक चुनना है $v_{1}$ पहले माध्य के साथ समान सामान्य वितरण के अनुसार तत्वों को यादृच्छिक रूप से खींचकर $0$ और फिर वेक्टर को मानक पर पुनः स्केल करें $1$. पुनर्स्केलिंग से पहले, यह गुणांक का कारण बनता है $d_{k}$ समान सामान्य वितरण से स्वतंत्र सामान्य रूप से वितरित स्टोकेस्टिक चर भी होना चाहिए (क्योंकि निर्देशांक का परिवर्तन एकात्मक है), और वेक्टर को पुन: स्केल करने के बाद $(d_{1},\dotsc ,d_{n})$ इकाई क्षेत्र पर एक समान वितरण (निरंतर) होगा $\mathbb {C} ^{n}$. इससे उदाहरण के लिए संभावना को सीमित करना संभव हो जाता है $|d_{1}|<\varepsilon$.

तथ्य यह है कि लैंज़ोस एल्गोरिदम समन्वय-अज्ञेयवादी है - ऑपरेशन केवल वैक्टर के आंतरिक उत्पादों को देखते हैं, कभी भी वैक्टर के व्यक्तिगत तत्वों को नहीं देखते हैं - एल्गोरिदम को चलाने के लिए ज्ञात ईजेनस्ट्रक्चर के साथ उदाहरण बनाना आसान बनाता है: बनाना $A$ विकर्ण पर वांछित eigenvalues ​​​​के साथ एक विकर्ण मैट्रिक्स; जब तक आरंभिक वेक्टर $v_{1}$ पर्याप्त गैर-शून्य तत्व हैं, एल्गोरिथ्म एक सामान्य त्रिविकर्ण सममित मैट्रिक्स को आउटपुट करेगा $T$.

कनिएल-पेगे अभिसरण सिद्धांत

बाद $m$ लैंज़ोस एल्गोरिदम के पुनरावृत्ति चरण, $T$ एक $m\times m$ वास्तविक सममित मैट्रिक्स, जो उपरोक्त के समान है $m$ eigenvalues $\theta _{1}\geqslant \theta _{2}\geqslant \dots \geqslant \theta _{m}.$ अभिसरण से मुख्यतः अभिसरण का तात्पर्य है $\theta _{1}$ को $\lambda _{1}$ (और का सममित अभिसरण $\theta _{m}$ को $\lambda _{n}$) जैसा $m$ बढ़ता है, और दूसरा कुछ सीमा का अभिसरण $\theta _{1},\ldots ,\theta _{k}$ के eigenvalues ​​के $T$ उनके समकक्षों के लिए $\lambda _{1},\ldots ,\lambda _{k}$ का $A$. लैंज़ोस एल्गोरिदम के लिए अभिसरण अक्सर पावर पुनरावृत्ति एल्गोरिदम की तुलना में तेज़ परिमाण का आदेश होता है।

के लिए सीमा $\theta _{1}$ रेले भागफल के चरम मूल्यों के रूप में eigenvalues ​​​​की उपरोक्त व्याख्या से आते हैं $r(x)$. तब से $\lambda _{1}$ एक प्राथमिकता अधिकतम है $r$ कुल मिलाकर $\mathbb {C} ^{n},$ जबकि $\theta _{1}$ पर अधिकतम मात्र है $m$-आयामी क्रायलोव उपस्थान, हम तुच्छ रूप से प्राप्त करते हैं $\lambda _{1}\geqslant \theta _{1}$. इसके विपरीत, कोई भी बिंदु $x$ उसमें क्रायलोव उपस्थान निचली सीमा प्रदान करता है $r(x)$ के लिए $\theta _{1}$, इसलिए यदि कोई बिंदु प्रदर्शित किया जा सकता है जिसके लिए $\lambda _{1}-r(x)$ छोटा है तो यह एक टाइट बाउंड प्रदान करता है $\theta _{1}$.

आयाम $m$ क्रायलोव उपस्थान है

$\operatorname {span} \left\{v_{1},Av_{1},A^{2}v_{1},\ldots ,A^{m-1}v_{1}\right\},$ अतः इसके किसी भी तत्व को इस प्रकार व्यक्त किया जा सकता है $p(A)v_{1}$ कुछ बहुपद के लिए $p$ अधिकतम डिग्री का $m-1$; उस बहुपद के गुणांक केवल सदिशों के रैखिक संयोजन के गुणांक हैं $v_{1},Av_{1},A^{2}v_{1},\ldots ,A^{m-1}v_{1}$. हम जो बहुपद चाहते हैं उसके वास्तविक गुणांक होंगे, लेकिन फिलहाल हमें जटिल गुणांकों की भी अनुमति देनी चाहिए, और हम लिखेंगे $p^{*}$ के सभी गुणांकों को सम्मिश्र संयुग्मन द्वारा प्राप्त बहुपद के लिए $p$. क्रायलोव उप-स्थान के इस पैरामीट्रिज़ेशन में, हमारे पास है

$r(p(A)v_{1})={\frac {(p(A)v_{1})^{*}Ap(A)v_{1}}{(p(A)v_{1})^{*}p(A)v_{1}}}={\frac {v_{1}^{*}p(A)^{*}Ap(A)v_{1}}{v_{1}^{*}p(A)^{*}p(A)v_{1}}}={\frac {v_{1}^{*}p^{*}(A^{*})Ap(A)v_{1}}{v_{1}^{*}p^{*}(A^{*})p(A)v_{1}}}={\frac {v_{1}^{*}p^{*}(A)Ap(A)v_{1}}{v_{1}^{*}p^{*}(A)p(A)v_{1}}}$

अब के लिए अभिव्यक्ति का उपयोग करना $v_{1}$ eigenvectors के एक रैखिक संयोजन के रूप में, हमें मिलता है

$Av_{1}=A\sum _{k=1}^{n}d_{k}z_{k}=\sum _{k=1}^{n}d_{k}\lambda _{k}z_{k}$ और अधिक सामान्यतः

$q(A)v_{1}=\sum _{k=1}^{n}d_{k}q(\lambda _{k})z_{k}$ किसी भी बहुपद के लिए $q$.

इस प्रकार

$\lambda _{1}-r(p(A)v_{1})=\lambda _{1}-{\frac {v_{1}^{*}\sum _{k=1}^{n}d_{k}p^{*}(\lambda _{k})\lambda _{k}p(\lambda _{k})z_{k}}{v_{1}^{*}\sum _{k=1}^{n}d_{k}p^{*}(\lambda _{k})p(\lambda _{k})z_{k}}}=\lambda _{1}-{\frac {\sum _{k=1}^{n}|d_{k}|^{2}\lambda _{k}p(\lambda _{k})^{*}p(\lambda _{k})}{\sum _{k=1}^{n}|d_{k}|^{2}p(\lambda _{k})^{*}p(\lambda _{k})}}={\frac {\sum _{k=1}^{n}|d_{k}|^{2}(\lambda _{1}-\lambda _{k})\left|p(\lambda _{k})\right|^{2}}{\sum _{k=1}^{n}|d_{k}|^{2}\left|p(\lambda _{k})\right|^{2}}}.$

यहां अंश और हर के बीच एक महत्वपूर्ण अंतर यह है कि $k=1$ अंश में पद लुप्त हो जाता है, लेकिन हर में नहीं। इस प्रकार यदि कोई चुन सकता है $p$ पर बड़ा होना $\lambda _{1}$ लेकिन अन्य सभी eigenvalues ​​​​पर छोटा होने पर, किसी को त्रुटि पर कड़ी पकड़ मिलेगी $\lambda _{1}-\theta _{1}$.

तब से $A$ की तुलना में कई अधिक स्वदेशी मान हैं $p$ गुणांक है, यह एक लंबा क्रम प्रतीत हो सकता है, लेकिन इसे पूरा करने का एक तरीका चेबीशेव बहुपद का उपयोग करना है। लिखना $c_{k}$ डिग्री के लिए $k$ पहली तरह का चेबीशेव बहुपद (जो संतुष्ट करता है $c_{k}(\cos x)=\cos(kx)$ सभी के लिए $x$), हमारे पास एक बहुपद है जो सीमा में रहता है $[-1,1]$ ज्ञात अंतराल पर $[-1,1]$ लेकिन इसके बाहर तेजी से बढ़ता है। तर्क के कुछ स्केलिंग के साथ, हम इसे छोड़कर सभी eigenvalues ​​​​को मैप कर सकते हैं $\lambda _{1}$ में $[-1,1]$. होने देना

$p(x)=c_{m-1}\left({\frac {2x-\lambda _{2}-\lambda _{n}}{\lambda _{2}-\lambda _{n}}}\right)$ (यदि $\lambda _{2}=\lambda _{1}$, इसके बजाय सबसे बड़े eigenvalue का उपयोग करें जो कि इससे बिल्कुल कम है $\lambda _{1}$), फिर का अधिकतम मान $|p(\lambda _{k})|^{2}$ के लिए $k\geqslant 2$ है $1$ और न्यूनतम मूल्य है $0$, इसलिए

$\lambda _{1}-\theta _{1}\leqslant \lambda _{1}-r(p(A)v_{1})={\frac {\sum _{k=2}^{n}|d_{k}|^{2}(\lambda _{1}-\lambda _{k})|p(\lambda _{k})|^{2}}{\sum _{k=1}^{n}|d_{k}|^{2}|p(\lambda _{k})|^{2}}}\leqslant {\frac {\sum _{k=2}^{n}|d_{k}|^{2}(\lambda _{1}-\lambda _{k})}{|d_{1}|^{2}|p(\lambda _{1})|^{2}}}\leqslant {\frac {(\lambda _{1}-\lambda _{n})\sum _{k=2}^{n}|d_{k}|^{2}}{|p(\lambda _{1})|^{2}|d_{1}|^{2}}}.$

आगे

$p(\lambda _{1})=c_{m-1}\left({\frac {2\lambda _{1}-\lambda _{2}-\lambda _{n}}{\lambda _{2}-\lambda _{n}}}\right)=c_{m-1}\left(2{\frac {\lambda _{1}-\lambda _{2}}{\lambda _{2}-\lambda _{n}}}+1\right);$

मात्रा

$\rho ={\frac {\lambda _{1}-\lambda _{2}}{\lambda _{2}-\lambda _{n}}}$ (यानी, मैट्रिक्स के शेष स्पेक्ट्रम के व्यास के लिए पहले ईजेंगैप का अनुपात) इस प्रकार यहां अभिसरण दर के लिए महत्वपूर्ण महत्व है। लिख भी रहा हूँ

$R=e^{\operatorname {arcosh} (1+2\rho )}=1+2\rho +2{\sqrt {\rho ^{2}+\rho }},$

हम यह निष्कर्ष निकाल सकते हैं

${\begin{aligned}\lambda _{1}-\theta _{1}&\leqslant {\frac {(\lambda _{1}-\lambda _{n})\left(1-|d_{1}|^{2}\right)}{c_{m-1}(2\rho +1)^{2}|d_{1}|^{2}}}\\[6pt]&={\frac {1-|d_{1}|^{2}}{|d_{1}|^{2}}}(\lambda _{1}-\lambda _{n}){\frac {1}{\cosh ^{2}((m-1)\operatorname {arcosh} (1+2\rho ))}}\\[6pt]&={\frac {1-|d_{1}|^{2}}{|d_{1}|^{2}}}(\lambda _{1}-\lambda _{n}){\frac {4}{\left(R^{m-1}+R^{-(m-1)}\right)^{2}}}\\[6pt]&\leqslant 4{\frac {1-|d_{1}|^{2}}{|d_{1}|^{2}}}(\lambda _{1}-\lambda _{n})R^{-2(m-1)}\end{aligned}}$

इस प्रकार अभिसरण दर को मुख्य रूप से नियंत्रित किया जाता है $R$, चूँकि यह सीमा एक कारक द्वारा सिकुड़ती है $R^{-2}$ प्रत्येक अतिरिक्त पुनरावृत्ति के लिए.

तुलना के लिए, कोई इस बात पर विचार कर सकता है कि विद्युत विधि की अभिसरण दर किस प्रकार निर्भर करती है $\rho$, लेकिन चूँकि शक्ति विधि मुख्य रूप से eigenvalues ​​​​के निरपेक्ष मूल्यों के बीच भागफल के प्रति संवेदनशील है, हमें इसकी आवश्यकता है $|\lambda _{n}|\leqslant |\lambda _{2}|$ बीच के ईगेंगैप के लिए $\lambda _{1}$ और $\lambda _{2}$ प्रमुख होना. उस बाधा के तहत, वह मामला जो शक्ति पद्धति को सबसे अधिक पसंद करता है $\lambda _{n}=-\lambda _{2}$, तो उस पर विचार करें। शक्ति विधि में देर से, पुनरावृत्ति वेक्टर:

$u=(1-t^{2})^{1/2}z_{1}+tz_{2}\approx z_{1}+tz_{2},$

जहां प्रत्येक नया पुनरावृत्ति प्रभावी ढंग से गुणा करता है $z_{2}$-आयाम $t$ द्वारा

${\frac {\lambda _{2}}{\lambda _{1}}}={\frac {\lambda _{2}}{\lambda _{2}+(\lambda _{1}-\lambda _{2})}}={\frac {1}{1+{\frac {\lambda _{1}-\lambda _{2}}{\lambda _{2}}}}}={\frac {1}{1+2\rho }}.$

तब सबसे बड़े eigenvalue का अनुमान है

$u^{*}Au=(1-t^{2})\lambda _{1}+t^{2}\lambda _{2},$

इसलिए लैंज़ोस एल्गोरिदम अभिसरण दर के लिए उपरोक्त सीमा की तुलना की जानी चाहिए

$\lambda _{1}-u^{*}Au=(\lambda _{1}-\lambda _{2})t^{2},$

जो एक कारक से सिकुड़ता है $(1+2\rho )^{-2}$ प्रत्येक पुनरावृत्ति के लिए. इस प्रकार यह अंतर बीच में ही सिमट कर रह जाता है $1+2\rho$ और $R=1+2\rho +2{\sqrt {\rho ^{2}+\rho }}$. में $\rho \gg 1$ क्षेत्र, बाद वाला अधिक पसंद है $1+4\rho$, और दोगुने बड़े ईजेंगैप के साथ पावर विधि की तरह प्रदर्शन करता है; एक उल्लेखनीय सुधार. हालाँकि, अधिक चुनौतीपूर्ण मामला यह है $\rho \ll 1,$ जिसमें $R\approx 1+2{\sqrt {\rho }}$ ईजेंगैप पर और भी बड़ा सुधार है; $\rho \gg 1$ वह क्षेत्र है जहां लैंज़ोस एल्गोरिदम अभिसरण-वार पावर विधि पर सबसे छोटा सुधार करता है।

संख्यात्मक स्थिरता

स्थिरता का मतलब है कि यदि छोटी-छोटी संख्यात्मक त्रुटियां पेश की जाती हैं और जमा हो जाती हैं तो एल्गोरिदम कितना प्रभावित होगा (यानी क्या यह मूल परिणाम के करीब अनुमानित परिणाम देगा)। राउंडऑफ़ वाले कंप्यूटर पर एल्गोरिदम को लागू करने की उपयोगिता का आकलन करने के लिए संख्यात्मक स्थिरता केंद्रीय मानदंड है।

लैंज़ोस एल्गोरिदम के लिए, यह साबित किया जा सकता है कि सटीक अंकगणित के साथ, वैक्टर का सेट $v_{1},v_{2},\cdots ,v_{m+1}$ एक ऑर्थोनॉर्मल आधार का निर्माण करता है, और हल किए गए eigenvalues/वेक्टर मूल मैट्रिक्स के अच्छे अनुमान हैं। हालाँकि, व्यवहार में (चूंकि गणना फ्लोटिंग पॉइंट अंकगणित में की जाती है जहां अशुद्धि अपरिहार्य है), ऑर्थोगोनैलिटी जल्दी से खो जाती है और कुछ मामलों में नया वेक्टर पहले से निर्मित सेट पर रैखिक रूप से निर्भर भी हो सकता है। परिणामस्वरूप, परिणामी त्रिविकर्ण मैट्रिक्स के कुछ eigenvalues ​​मूल मैट्रिक्स के सन्निकटन नहीं हो सकते हैं। इसलिए, लैंज़ोस एल्गोरिदम बहुत स्थिर नहीं है।

इस एल्गोरिदम के उपयोगकर्ताओं को उन नकली eigenvalues ​​​​को खोजने और हटाने में सक्षम होना चाहिए। लैंज़ोस एल्गोरिदम का व्यावहारिक कार्यान्वयन इस स्थिरता के मुद्दे से लड़ने के लिए तीन दिशाओं में जाता है:

1. रूढ़िवादिता के नुकसान को रोकें,
2. आधार तैयार होने के बाद रूढ़िवादिता को पुनः प्राप्त करें।
3. अच्छे और नकली सभी स्वदेशी मूल्यों की पहचान हो जाने के बाद, नकली लोगों को हटा दें।

भिन्नताएँ

लैंज़ोस एल्गोरिदम पर भिन्नताएं मौजूद हैं जहां शामिल वेक्टर वेक्टर के बजाय लंबे, संकीर्ण मैट्रिक्स हैं और सामान्यीकरण स्थिरांक छोटे वर्ग मैट्रिक्स हैं। इन्हें ब्लॉक लैंज़ोस एल्गोरिदम कहा जाता है और बड़ी संख्या में रजिस्टरों और लंबी मेमोरी-फ़ेच समय वाले कंप्यूटरों पर यह बहुत तेज़ हो सकता है।

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

एक परिमित क्षेत्र पर शून्यस्थान

Main article: Block Lanczos algorithm

1995 में, पीटर मोंटगोमरी (गणितज्ञ) ने GF(2) पर एक बड़े विरल मैट्रिक्स के कर्नेल (मैट्रिक्स) के तत्वों को खोजने के लिए लैंज़ोस एल्गोरिदम पर आधारित एक एल्गोरिदम प्रकाशित किया; चूँकि परिमित क्षेत्रों में बड़े विरल मैट्रिक्स में रुचि रखने वाले लोगों का समूह और बड़ी स्वदेशी समस्याओं में रुचि रखने वाले लोगों का समूह शायद ही ओवरलैप होता है, इसे अक्सर अनुचित भ्रम पैदा किए बिना ब्लॉक लैंज़ो एल्गोरिदम भी कहा जाता है।

अनुप्रयोग

लैंज़ोस एल्गोरिदम बहुत आकर्षक हैं क्योंकि गुणा $A\,$ एकमात्र बड़े पैमाने का रैखिक ऑपरेशन है। चूंकि भारित-अवधि पाठ पुनर्प्राप्ति इंजन केवल इस ऑपरेशन को कार्यान्वित करते हैं, लैंज़ोस एल्गोरिदम को पाठ दस्तावेज़ों पर कुशलतापूर्वक लागू किया जा सकता है (अव्यक्त अर्थ अनुक्रमणिका देखें)। Eigenvectors बड़े पैमाने पर रैंकिंग विधियों के लिए भी महत्वपूर्ण हैं जैसे कि जॉन क्लेनबर्ग द्वारा विकसित HITS एल्गोरिदम, या Google द्वारा उपयोग किया जाने वाला पृष्ठ रैंक एल्गोरिदम।

लैंज़ोस एल्गोरिदम का उपयोग संघनित पदार्थ भौतिकी में दृढ़ता से सहसंबद्ध सामग्री के हैमिल्टनियन मैट्रिक्स को हल करने की एक विधि के रूप में भी किया जाता है, साथ ही परमाणु भौतिकी में परमाणु शेल मॉडल कोड में भी।

कार्यान्वयन

एनएजी न्यूमेरिकल लाइब्रेरी में कई रूटीन शामिल हैं बड़े पैमाने पर रैखिक प्रणालियों और ईजेनसमस्याओं के समाधान के लिए जो लैंज़ोस एल्गोरिदम का उपयोग करते हैं।

MATLAB और GNU ऑक्टेव ARPACK बिल्ट-इन के साथ आते हैं। संग्रहीत और अंतर्निहित दोनों मैट्रिक्स का विश्लेषण eigs() फ़ंक्शन (Matlab/Octave) के माध्यम से किया जा सकता है।

इसी तरह, Python_(प्रोग्रामिंग_भाषा) में, SciPy पैकेज में scipy.sparse.linalg.eigsh है, जो ARPACK के SSEUPD और DSEUPD फ़ंक्शंस फ़ंक्शंस के लिए एक रैपर भी है जो इम्प्लिसिटली रीस्टार्टेड लैंक्ज़ोस विधि का उपयोग करता है।

लैंज़ोस एल्गोरिथ्म का एक मैटलैब कार्यान्वयन (सटीक मुद्दों पर ध्यान दें) गॉसियन बिलीफ प्रोपेगेशन मैटलैब पैकेज के एक भाग के रूप में उपलब्ध है। ग्राफलैब सहयोगी फ़िल्टरिंग लाइब्रेरी में मल्टीकोर के लिए लैंज़ोस एल्गोरिदम (सी ++ में) के बड़े पैमाने पर समानांतर कार्यान्वयन शामिल है।

PRIMME लाइब्रेरी लैंज़ोस जैसा एल्गोरिदम भी लागू करती है।

अग्रिम पठन

• Golub, Gene H.; Van Loan, Charles F. (1996). "Lanczos Methods". Matrix Computations. Baltimore: Johns Hopkins University Press. pp. 470–507. ISBN 0-8018-5414-8.
• Ng, Andrew Y.; Zheng, Alice X.; Jordan, Michael I. (2001). "Link Analysis, Eigenvectors and Stability" (PDF). IJCAI'01 Proceedings of the 17th International Joint Conference on Artificial Intelligence. 2: 903–910.
• Erik Koch (2019). "Exact Diagonalization and Lanczos Method" (PDF). In E. Pavarini; E. Koch; S. Zhang (eds.). Many-Body Methods for Real Materials. Jülich. ISBN 978-3-95806-400-3.