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

For शून्य स्थान-खोज एल्गोरिदम, see लैंज़ोस एल्गोरिदम को ब्लॉक करें.

For प्रक्षेप विधि, see लैंज़ोस पुनः नमूनाकरण.

For गामा फलन का सन्निकटन, see लैंज़ोस सन्निकटन.

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

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

अपने मूल काम में, इन लेखकों ने यह भी सुझाव दिया कि प्रारंभिक वेक्टर का चयन कैसे करें (अर्थात् प्रारंभिक वेक्टर के प्रत्येक तत्व का चयन करने के लिए यादृच्छिक संख्या जेनरेटर का उपयोग करें) और निर्धारण के लिए अनुभवजन्य रूप से निर्धारित विधि का सुझाव दिया $m$, सदिशों की कम संख्या (अर्थात इसे वांछित सटीक आइजनवैल्यू ​​​​की संख्या का लगभग 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}$ जब आवश्यक है।

आइजन समस्याएं के लिए आवेदन

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

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

सबसे बड़े परिमाण के आइजेनवैल्यू और मैट्रिक्स के संबंधित आइजेनवेक्टर को खोजने की शक्ति विधि $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$ लैंज़ोस एल्गोरिथम विनिर्देश के लिए है।

चरम आइजनवैल्यू ​​​​का एक साथ सन्निकटन

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

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

विशेष रूप से, सबसे बड़ा आइजनवैल्यू $\lambda _{\max }$ का वैश्विक अधिकतम है $r$ और सबसे छोटा आइजनवैल्यू $\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}$ शक्ति विधि की तुलना में धीमी गति से अभिसरण नहीं किया जा सकता है, और दोनों आइजनवैल्यू चरम सीमाओं का अनुमान लगाकर अधिक प्राप्त किया जाएगा। अनुकूलन की उपसमस्या के लिए $r$ कुछ पर ${\mathcal {L}}_{j}$, लम्बवत आधार रखना सुविधाजनक है $\{v_{1},\ldots ,v_{j}\}$ इस वेक्टर स्पेस के लिए. इस प्रकार हम फिर से क्रायलोव उप-स्थानों के अनुक्रम के लिए ऐसे आधार की पुनरावृत्तीय गणना करने की समस्या की ओर अग्रसर हैं।

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

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

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

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

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

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

के लिए सीमा $\theta _{1}$ रेले भागफल के चरम मूल्यों के रूप में आइजनवैल्यू ​​​​की उपरोक्त व्याख्या से आते हैं $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}$ आइजनवेक्टर के रैखिक संयोजन के रूप में, हमें मिलता है

$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}$ लेकिन अन्य सभी आइजनवैल्यू ​​​​पर छोटा होने पर, किसी को त्रुटि पर कड़ी पकड़ मिलेगी $\lambda _{1}-\theta _{1}$.

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

तब सबसे बड़े आइजनवैल्यू का अनुमान है

$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}$ ऑर्थोनॉर्मल आधार का निर्माण करता है, और हल किए गए आइजनवैल्यू/वेक्टर मूल मैट्रिक्स के अच्छे अनुमान हैं। चुकीं, व्यवहार में (चूंकि गणना फ्लोटिंग पॉइंट अंकगणित में की जाती है जहां अशुद्धि अपरिहार्य है), ऑर्थोगोनैलिटी जल्दी से खो जाती है और कुछ मामलों में नया वेक्टर पहले से निर्मित सेट पर रैखिक रूप से निर्भर भी हो सकता है। परिणामस्वरूप, परिणामी त्रिविकर्ण मैट्रिक्स के कुछ आइजनवैल्यू ​​मूल मैट्रिक्स के सन्निकटन नहीं हो सकते हैं। इसलिए, लैंज़ोस एल्गोरिदम बहुत स्थिर नहीं है।

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

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

भिन्नताएँ

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

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

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

Main article: लैंज़ोस एल्गोरिदम को ब्लॉक करें

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

अनुप्रयोग

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

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

कार्यान्वयन

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

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

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

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

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.