आइजेनवैल्यू एल्गोरिदम

संख्यात्मक विश्लेषण में, सबसे महत्वपूर्ण समस्याओं में से एक मैट्रिक्स (गणित) के eigenvalues ​​​​को खोजने के लिए कुशल और संख्यात्मक स्थिरता कलन विधि डिजाइन करना है। ये eigenvalue एल्गोरिदम eigenvectors भी ढूंढ सकते हैं।

आइजेनवैल्यू और आइजेनवेक्टर

Main articles: Eigenvalues and eigenvectors and Generalized eigenvector

एक दिया गया n × n वर्ग आव्यूह#वर्ग आव्यूह A वास्तविक संख्या या सम्मिश्र संख्या संख्याओं का, एक eigenvalue λ और इससे संबंधित सामान्यीकृत आइजेनवेक्टर vरिश्ते का पालन करने वाला जोड़ा है

$\left(A-\lambda I\right)^{k}{\mathbf {v} }=0,$

कहाँ v एक अशून्य है n × 1 कॉलम वेक्टर, I है n × n शिनाख्त सांचा, k एक धनात्मक पूर्णांक है, और दोनों λ और v को तब भी जटिल रहने की अनुमति है A यह सचमुच का है। कब k = 1, वेक्टर को केवल एक आइजन्वेक्टर कहा जाता है, और जोड़ी को एक आइजेनपेयर कहा जाता है। इस मामले में, Av = λv. कोई भी eigenvalue λ का Aसाधारण है इससे जुड़े eigenvectors, यदि के लिए k ऐसा सबसे छोटा पूर्णांक है (A − λI)^k v = 0 एक सामान्यीकृत eigenvector के लिए v, तब (A − λI)^k−1 v एक साधारण eigenvector है. मूल्य k को हमेशा से कम या बराबर के रूप में लिया जा सकता है n. विशेष रूप से, (A − λI)ⁿ v = 0 सभी सामान्यीकृत eigenvectors के लिए v के साथ जुड़े λ.

प्रत्येक eigenvalue के लिए λ का A, कर्नेल (मैट्रिक्स) ker(A − λI) से जुड़े सभी eigenvectors शामिल हैं λ (0 के साथ), का eigenspace कहा जाता है λ, जबकि सदिश समष्टि ker((A − λI)ⁿ) में सभी सामान्यीकृत ईजेनवेक्टर शामिल हैं, और इसे सामान्यीकृत ईजेनस्पेस कहा जाता है। की ज्यामितीय बहुलता λ इसके eigenspace का आयाम है। की बीजगणितीय बहुलता λ इसके सामान्यीकृत eigenspace का आयाम है। बाद वाली शब्दावली समीकरण द्वारा उचित है

$p_{A}\left(z\right)=\det \left(zI-A\right)=\prod _{i=1}^{k}(z-\lambda _{i})^{\alpha _{i}},$

कहाँ det निर्धारक फलन है, λ_i के सभी विशिष्ट eigenvalues ​​हैं A और यह α_i संगत बीजगणितीय बहुलताएँ हैं। कार्यक्रम p_A(z) का अभिलक्षणिक बहुपद है A. तो बीजगणितीय बहुलता विशेषता बहुपद की बहुपद जड़ों के गुणों के रूप में आइगेनवैल्यू की बहुलता है। चूँकि कोई भी eigenvector भी एक सामान्यीकृत eigenvector है, ज्यामितीय बहुलता बीजगणितीय बहुलता से कम या उसके बराबर है। बीजगणितीय बहुलताओं का योग है n, विशेषता बहुपद की डिग्री। समीकरण p_A(z) = 0 को अभिलक्षणिक समीकरण कहा जाता है, क्योंकि इसकी जड़ें बिल्कुल eigenvalues ​​​​हैं A. केली-हैमिल्टन प्रमेय द्वारा, A स्वयं उसी समीकरण का पालन करता है: p_A(A) = 0. परिणामस्वरूप, मैट्रिक्स के कॉलम ${\textstyle \prod _{i\neq j}(A-\lambda _{i}I)^{\alpha _{i}}}$ या तो 0 होना चाहिए या eigenvalue का सामान्यीकृत eigenvectors होना चाहिए λ_j, चूंकि वे नष्ट हो गए हैं $(A-\lambda _{j}I)^{\alpha _{j}}$. वास्तव में, स्तंभ स्थान सामान्यीकृत eigenspace है λ_j.

विशिष्ट eigenvalues ​​​​के सामान्यीकृत eigenvectors का कोई भी संग्रह रैखिक रूप से स्वतंत्र है, इसलिए सभी के लिए एक आधार Cⁿ को सामान्यीकृत eigenvectors से मिलकर चुना जा सकता है। अधिक विशेष रूप से, यह आधार {v_i}ⁿ
_i=1 को चुना और व्यवस्थित किया जा सकता है ताकि

• अगर v_i और v_j का eigenvalue समान है, तो ऐसा ही होता है v_k प्रत्येक के लिए k बीच में i और j, और
• अगर v_i एक साधारण आइजनवेक्टर नहीं है, और यदि λ_i तो फिर इसका स्वदेशी मान है (A − λ_iI)v_i = v_i−1 (विशेष रूप से, v₁ एक साधारण eigenvector होना चाहिए)।

यदि इन आधार वैक्टरों को मैट्रिक्स के कॉलम वैक्टर के रूप में रखा जाता है V = [v₁ v₂ ⋯ v_n], तब V का उपयोग परिवर्तित करने के लिए किया जा सकता है A अपने जॉर्डन सामान्य रूप में:

$V^{-1}AV={\begin{bmatrix}\lambda _{1}&\beta _{1}&0&\ldots &0\\0&\lambda _{2}&\beta _{2}&\ldots &0\\0&0&\lambda _{3}&\ldots &0\\\vdots &\vdots &\vdots &\ddots &\vdots \\0&0&0&\ldots &\lambda _{n}\end{bmatrix}},$

जहां λ_i eigenvalues ​​हैं, β_i = 1 अगर (A − λ_i+1)v_i+1 = v_i और β_i = 0 अन्यथा।

अधिक सामान्यतः, यदि W कोई उलटा मैट्रिक्स है, और λ का एक प्रतिमान है A सामान्यीकृत आइजेनवेक्टर के साथ v, तब (W⁻¹AW − λI)^k W^−kv = 0. इस प्रकार λ का एक प्रतिमान है W⁻¹AW सामान्यीकृत आइजेनवेक्टर के साथ W^−kv. अर्थात्, समान आव्यूहों के eigenvalues ​​​​समान होते हैं।

सामान्य, हर्मिटियन, और वास्तविक-सममित मैट्रिक्स

Main articles: Adjoint matrix, Normal matrix, and Hermitian matrix

संयुग्म स्थानांतरण M^* एक जटिल मैट्रिक्स का M के संयुग्म का स्थानान्तरण है M: M ^* = M ^T. एक वर्ग मैट्रिक्स A को सामान्य मैट्रिक्स कहा जाता है यदि यह अपने सहायक के साथ आवागमन करता है: A^*A = AA^*. इसे हर्मिटियन मैट्रिक्स कहा जाता है यदि यह इसके सहायक के बराबर है: A^* = A. सभी हर्मिटियन मैट्रिस सामान्य हैं। अगर A में केवल वास्तविक तत्व हैं, तो जोड़ केवल स्थानान्तरण है, और A हर्मिटियन है यदि और केवल यदि यह सममित मैट्रिक्स है। जब कॉलम वैक्टर पर लागू किया जाता है, तो विहित आंतरिक उत्पाद को परिभाषित करने के लिए एडजॉइंट का उपयोग किया जा सकता है Cⁿ: w ⋅ v = w^* v. सामान्य, हर्मिटियन और वास्तविक-सममित मैट्रिक्स में कई उपयोगी गुण होते हैं:

• सामान्य मैट्रिक्स का प्रत्येक सामान्यीकृत आइजनवेक्टर एक साधारण आइजेनवेक्टर होता है।
• कोई भी सामान्य मैट्रिक्स विकर्ण मैट्रिक्स के समान होता है, क्योंकि इसका जॉर्डन सामान्य रूप विकर्ण होता है।
• एक सामान्य मैट्रिक्स के अलग-अलग आइगेनवैल्यू के आइजेनवेक्टर ऑर्थोगोनल होते हैं।
• सामान्य मैट्रिक्स का शून्य स्थान और छवि (या स्तंभ स्थान) एक दूसरे के लिए ओर्थोगोनल हैं।
• किसी भी सामान्य मैट्रिक्स के लिए A, Cⁿ का एक ऑर्थोनॉर्मल आधार है जिसमें eigenvectors शामिल हैं A. eigenvectors का संगत मैट्रिक्स एकात्मक मैट्रिक्स है।
• चूंकि हर्मिटियन मैट्रिक्स के आइगेनवैल्यू वास्तविक हैं (λ − λ)v = (A^* − A)v = (A − A)v = 0 एक गैर-शून्य ईजेनवेक्टर के लिए v.
• अगर A वास्तविक है, इसके लिए एक लंबात्मक आधार है Rⁿ के eigenvectors से मिलकर A अगर और केवल अगर A सममित है.

एक वास्तविक या जटिल मैट्रिक्स के लिए हर्मिटियन हुए बिना सभी वास्तविक स्वदेशी मान होना संभव है। उदाहरण के लिए, एक वास्तविक त्रिकोणीय मैट्रिक्स के विकर्ण के साथ इसके स्वदेशी मान होते हैं, लेकिन सामान्य तौर पर यह सममित नहीं होता है।

शर्त संख्या

संख्यात्मक गणना की किसी भी समस्या को किसी फ़ंक्शन के मूल्यांकन के रूप में देखा जा सकता है f कुछ इनपुट के लिए x. शर्त संख्या κ(f, x) समस्या फ़ंक्शन के आउटपुट में सापेक्ष त्रुटि और इनपुट में सापेक्ष त्रुटि का अनुपात है, और फ़ंक्शन और इनपुट दोनों के साथ भिन्न होता है। शर्त संख्या बताती है कि गणना के दौरान त्रुटि कैसे बढ़ती है। इसका बेस-10 लघुगणक बताता है कि परिणाम में इनपुट में मौजूद सटीकता के कितने कम अंक मौजूद हैं। शर्त संख्या सर्वोत्तम स्थिति है. यह समस्या में अंतर्निहित अस्थिरता को दर्शाता है, भले ही इसे कैसे भी हल किया जाए। संयोग को छोड़कर, कोई भी एल्गोरिदम कभी भी स्थिति संख्या द्वारा इंगित से अधिक सटीक परिणाम नहीं दे सकता है। हालाँकि, खराब तरीके से डिज़ाइन किया गया एल्गोरिदम काफी खराब परिणाम दे सकता है। उदाहरण के लिए, जैसा कि नीचे बताया गया है, सामान्य आव्यूहों के लिए स्वदेशी मान खोजने की समस्या हमेशा अच्छी तरह से तैयार की जाती है। हालाँकि, एक बहुपद की जड़ों को खोजने की समस्या विल्किंसन बहुपद हो सकती है|बहुत ख़राब स्थिति में। इस प्रकार eigenvalue एल्गोरिदम जो विशेषता बहुपद की जड़ों को ढूंढकर काम करते हैं, समस्या न होने पर भी खराब स्थिति में हो सकते हैं।

रैखिक समीकरण को हल करने की समस्या के लिए Av = b कहाँ A उलटा है, शर्त संख्या#मैट्रिसेस κ(A⁻¹, b) द्वारा दिया गया है ||A||_op||A⁻¹||_op, कहाँ || ||_op संचालिका मानदंड सामान्य मानदंड (गणित)#यूक्लिडियन मानदंड के अधीनस्थ है Cⁿ. चूँकि यह संख्या स्वतंत्र है b और के लिए भी वैसा ही है A और A⁻¹, इसे आमतौर पर केवल कंडीशन नंबर कहा जाता है κ(A) मैट्रिक्स का A. यह मान κ(A) सबसे बड़े eigenvalue के अनुपात का निरपेक्ष मान भी है A अपने सबसे छोटे से. अगर A तो एकात्मक मैट्रिक्स है ||A||_op = ||A⁻¹||_op = 1, इसलिए κ(A) = 1. सामान्य मैट्रिक्स के लिए, ऑपरेटर मानदंड की गणना करना अक्सर मुश्किल होता है। इस कारण से, स्थिति संख्या का अनुमान लगाने के लिए आमतौर पर अन्य मैट्रिक्स मानदंडों का उपयोग किया जाता है।

आइजेनवैल्यू समस्या के लिए, बाउर-फ़ाइक प्रमेय कि यदि λ एक विकर्णीय मैट्रिक्स के लिए एक eigenvalue है n × n आव्यूह A eigenvector मैट्रिक्स के साथ V, तो गणना में पूर्ण त्रुटि λ के उत्पाद से घिरा है κ(V) और पूर्ण त्रुटि A. बाउर-फ़ाइक प्रमेय#उपप्रमेय, खोजने के लिए शर्त संख्या λ है κ(λ, A) = κ(V) = ||V ||_op ||V ⁻¹||_op. अगर A तो सामान्य है V एकात्मक है, और κ(λ, A) = 1. इस प्रकार सभी सामान्य मैट्रिक्स के लिए eigenvalue समस्या अच्छी तरह से वातानुकूलित है।

एक सामान्य मैट्रिक्स के आइजनस्पेस को खोजने की समस्या के लिए शर्त संख्या A एक eigenvalue के अनुरूप λ को बीच की न्यूनतम दूरी के व्युत्क्रमानुपाती दिखाया गया है λ और अन्य विशिष्ट eigenvalues A. विशेष रूप से, सामान्य मैट्रिक्स के लिए आइजेनस्पेस समस्या पृथक आइजेनवैल्यू के लिए अच्छी तरह से अनुकूलित है। जब eigenvalues ​​​​अलग-थलग नहीं होते हैं, तो सबसे अच्छी उम्मीद की जा सकती है कि आस-पास के eigenvalues ​​​​के सभी eigenvectors की अवधि की पहचान की जाए।

एल्गोरिदम

आइजनवैल्यू की गणना के लिए सबसे विश्वसनीय और सबसे व्यापक रूप से इस्तेमाल किया जाने वाला एल्गोरिदम जॉन जी.एफ. फ्रांसिस का क्यूआर एल्गोरिदम है, जिसे 20वीं सदी के शीर्ष दस एल्गोरिदम में से एक माना जाता है। कोई भी राक्षसी बहुपद उसके साथी मैट्रिक्स का विशिष्ट बहुपद होता है। इसलिए, eigenvalues ​​​​खोजने के लिए एक सामान्य एल्गोरिदम का उपयोग बहुपदों की जड़ों को खोजने के लिए भी किया जा सकता है। एबेल-रफिनी प्रमेय से पता चलता है कि 4 से अधिक आयामों के लिए ऐसा कोई भी एल्गोरिदम या तो अनंत होना चाहिए, या प्राथमिक अंकगणितीय संचालन और आंशिक शक्तियों की तुलना में अधिक जटिलता के कार्यों को शामिल करना चाहिए। इस कारण से एल्गोरिदम जो चरणों की एक सीमित संख्या में eigenvalues ​​​​की सटीक गणना करते हैं, केवल कुछ विशेष वर्गों के मैट्रिक्स के लिए मौजूद हैं। सामान्य मैट्रिक्स के लिए, एल्गोरिदम पुनरावृत्तीय विधि है, जो प्रत्येक पुनरावृत्ति के साथ बेहतर अनुमानित समाधान उत्पन्न करती है।

कुछ एल्गोरिदम प्रत्येक eigenvalue का उत्पादन करेंगे, अन्य कुछ या केवल एक का उत्पादन करेंगे। हालाँकि, बाद वाले एल्गोरिदम का उपयोग भी सभी eigenvalues ​​​​को खोजने के लिए किया जा सकता है। एक बार एक eigenvalue λ एक मैट्रिक्स का A की पहचान कर ली गई है, इसका उपयोग या तो अगली बार एल्गोरिदम को एक अलग समाधान की ओर निर्देशित करने के लिए किया जा सकता है, या उस समस्या को कम करने के लिए किया जा सकता है जो अब नहीं है λ समाधान के रूप में.

पुनर्निर्देशन आमतौर पर शिफ्टिंग: रिप्लेसिंग द्वारा पूरा किया जाता है A साथ A − μI कुछ स्थिरांक के लिए μ. के लिए eigenvalue पाया गया A − μI होना आवश्यक है μ के लिए एक eigenvalue प्राप्त करने के लिए वापस जोड़ा गया A. उदाहरण के लिए, शक्ति पुनरावृत्ति के लिए, μ = λ. पावर पुनरावृत्ति पूर्ण मूल्य में सबसे बड़ा eigenvalue पाता है, तब भी जब λ केवल एक अनुमानित eigenvalue है, शक्ति पुनरावृत्ति इसे दूसरी बार खोजने की संभावना नहीं है। इसके विपरीत, व्युत्क्रम पुनरावृत्ति आधारित विधियाँ सबसे कम eigenvalue पाती हैं μ से काफी दूर चुना गया है λ और उम्मीद है कि यह किसी अन्य eigenvalue के करीब होगा।

कमी को प्रतिबंधित करके पूरा किया जा सकता है A मैट्रिक्स के कॉलम स्थान पर A − λI, कौन A अपने पास ले जाता है। तब से A - λI एकवचन है, स्तंभ स्थान कम आयाम का है। फिर eigenvalue एल्गोरिदम को प्रतिबंधित मैट्रिक्स पर लागू किया जा सकता है। इस प्रक्रिया को तब तक दोहराया जा सकता है जब तक कि सभी eigenvalues ​​नहीं मिल जाते।

यदि एक eigenvalue एल्गोरिदम eigenvectors का उत्पादन नहीं करता है, तो एक आम अभ्यास एक व्युत्क्रम पुनरावृत्ति आधारित एल्गोरिदम का उपयोग करना है μ eigenvalue के निकट सन्निकटन पर सेट करें। यह शीघ्रता से निकटतम eigenvalue के eigenvector में परिवर्तित हो जाएगा μ. छोटे मैट्रिक्स के लिए, एक विकल्प यह है कि उत्पाद के कॉलम स्थान को देखा जाए A − λ'I अन्य प्रत्येक eigenvalues ​​के लिए λ'.

सामान्य मैट्रिक्स के यूनिट ईजेनवेक्टर घटकों के मानदंड के लिए एक सूत्र रॉबर्ट थॉम्पसन द्वारा 1966 में खोजा गया था और कई अन्य लोगों द्वारा स्वतंत्र रूप से फिर से खोजा गया था। अगर A एक ${\textstyle n\times n}$ eigenvalues ​​​​के साथ सामान्य मैट्रिक्स λ_i(A) और संबंधित इकाई eigenvectors v_iजिसकी घटक प्रविष्टियाँ हैं v_i,j, होने देना A_j हो ${\textstyle n-1\times n-1}$ को हटाकर प्राप्त मैट्रिक्स i-वीं पंक्ति और स्तंभ से A, और जाने λ_k(A_j) यह हो k-वां eigenvalue. तब

$$|v_{i,j}|^{2}\prod _{k=1,k\neq i}^{n}(\lambda _{i}(A)-\lambda _{k}(A))=\prod _{k=1}^{n-1}(\lambda _{i}(A)-\lambda _{k}(A_{j}))$$

अगर $p,p_{j}$ के अभिलाक्षणिक बहुपद हैं $A$ और $A_{j}$, सूत्र को इस प्रकार पुनः लिखा जा सकता है

$$|v_{i,j}|^{2}={\frac {p_{j}(\lambda _{i}(A))}{p'(\lambda _{i}(A))}}$$

व्युत्पन्न मानते हुए $p'$ पर शून्य नहीं है $\lambda _{i}(A)$.

हेसेनबर्ग और त्रिविकर्ण आव्यूह

Main article: Hessenberg matrix

चूँकि एक त्रिकोणीय मैट्रिक्स के eigenvalues ​​​​इसके विकर्ण तत्व हैं, सामान्य मैट्रिक्स के लिए eigenvalues ​​​​को संरक्षित करते हुए मैट्रिक्स को त्रिकोणीय रूप में परिवर्तित करने के लिए गाऊसी उन्मूलन जैसी कोई सीमित विधि नहीं है। लेकिन त्रिकोणीय के करीब कुछ पहुंचना संभव है. हेसेनबर्ग मैट्रिक्स एक वर्ग मैट्रिक्स है जिसके लिए उपविकर्ण के नीचे की सभी प्रविष्टियाँ शून्य हैं। निचला हेसेनबर्ग मैट्रिक्स वह है जिसके लिए अतिविकर्ण के ऊपर की सभी प्रविष्टियाँ शून्य हैं। वे मैट्रिक्स जो हेसेनबर्ग के ऊपरी और निचले दोनों हैं, त्रिदिकोणीय मैट्रिक्स हैं। हेसेनबर्ग और त्रिदिकोणीय मैट्रिक्स कई आइगेनवैल्यू एल्गोरिदम के लिए शुरुआती बिंदु हैं क्योंकि शून्य प्रविष्टियां समस्या की जटिलता को कम करती हैं। एक सामान्य मैट्रिक्स को समान eigenvalues ​​​​के साथ हेसेनबर्ग मैट्रिक्स में परिवर्तित करने के लिए आमतौर पर कई तरीकों का उपयोग किया जाता है। यदि मूल मैट्रिक्स सममित या हर्मिटियन था, तो परिणामी मैट्रिक्स त्रिविकर्ण होगा।

जब केवल eigenvalues ​​​​की आवश्यकता होती है, तो समानता मैट्रिक्स की गणना करने की कोई आवश्यकता नहीं होती है, क्योंकि रूपांतरित मैट्रिक्स में समान eigenvalues ​​​​होते हैं। यदि eigenvectors की भी आवश्यकता है, तो हेसेनबर्ग मैट्रिक्स के eigenvectors को मूल मैट्रिक्स के eigenvectors में बदलने के लिए समानता मैट्रिक्स की आवश्यकता हो सकती है।

Method	Applies to	Produces	Cost without similarity matrix	Cost with similarity matrix	Description
Householder transformations	General	Hessenberg	2n3⁄3 + O(n2)	4n3⁄3 + O(n2)	Reflect each column through a subspace to zero out its lower entries.
Givens rotations	General	Hessenberg	4n3⁄3 + O(n2)		Apply planar rotations to zero out individual entries. Rotations are ordered so that later ones do not cause zero entries to become non-zero again.
Arnoldi iteration	General	Hessenberg			Perform Gram–Schmidt orthogonalization on Krylov subspaces.
Lanczos algorithm	Hermitian	Tridiagonal			Arnoldi iteration for Hermitian matrices, with shortcuts.

सममित त्रिदिकोणीय eigenvalue समस्याओं के लिए सभी eigenvalues ​​​​(eigenvectors के बिना) को विशेषता बहुपद पर द्विभाजन का उपयोग करके समय O(n log(n)) में संख्यात्मक रूप से गणना की जा सकती है।

पुनरावृत्तीय एल्गोरिदम

पुनरावृत्त एल्गोरिदम आइगेनवैल्यू समस्या को ऐसे अनुक्रमों का निर्माण करके हल करते हैं जो आइगेनवैल्यू में परिवर्तित होते हैं। कुछ एल्गोरिदम वैक्टर के अनुक्रम भी उत्पन्न करते हैं जो आइजेनवेक्टर में परिवर्तित होते हैं। आमतौर पर, आइगेनवैल्यू अनुक्रमों को समान मैट्रिक्स के अनुक्रम के रूप में व्यक्त किया जाता है जो त्रिकोणीय या विकर्ण रूप में परिवर्तित हो जाते हैं, जिससे आइजेनवैल्यू को आसानी से पढ़ा जा सकता है। आइजेनवेक्टर अनुक्रमों को संगत समानता मैट्रिक्स के रूप में व्यक्त किया जाता है।

Method	Applies to	Produces	Cost per step	Convergence	Description
Lanczos algorithm	Hermitian	m largest/smallest eigenpairs
Power iteration	general	eigenpair with largest value	O(n2)	linear	Repeatedly applies the matrix to an arbitrary starting vector and renormalizes.
Inverse iteration	general	eigenpair with value closest to μ		linear	Power iteration for (A − μI)−1
Rayleigh quotient iteration	Hermitian	any eigenpair		cubic	Power iteration for (A − μiI)−1, where μi for each iteration is the Rayleigh quotient of the previous iteration.
Preconditioned inverse iteration or LOBPCG algorithm	positive-definite real symmetric	eigenpair with value closest to μ			Inverse iteration using a preconditioner (an approximate inverse to A).
Bisection method	real symmetric tridiagonal	any eigenvalue		linear	Uses the bisection method to find roots of the characteristic polynomial, supported by the Sturm sequence.
Laguerre iteration	real symmetric tridiagonal	any eigenvalue		cubic	Uses Laguerre's method to find roots of the characteristic polynomial, supported by the Sturm sequence.
QR algorithm	Hessenberg	all eigenvalues	O(n2)	cubic	Factors A = QR, where Q is orthogonal and R is triangular, then applies the next iteration to RQ.
		all eigenpairs	6n3 + O(n2)
Jacobi eigenvalue algorithm	real symmetric	all eigenvalues	O(n3)	quadratic	Uses Givens rotations to attempt clearing all off-diagonal entries. This fails, but strengthens the diagonal.
Divide-and-conquer	Hermitian tridiagonal	all eigenvalues	O(n2)		Divides the matrix into submatrices that are diagonalized then recombined.
		all eigenpairs	(4⁄3)n3 + O(n2)
Homotopy method	real symmetric tridiagonal	all eigenpairs	O(n2)		Constructs a computable homotopy path from a diagonal eigenvalue problem.
Folded spectrum method	real symmetric	eigenpair with value closest to μ			Preconditioned inverse iteration applied to (A − μI)2
MRRR algorithm	real symmetric tridiagonal	some or all eigenpairs	O(n2)		"Multiple relatively robust representations" – performs inverse iteration on a LDLT decomposition of the shifted matrix.

प्रत्यक्ष गणना

हालाँकि सामान्य आव्यूहों के लिए सीधे eigenvalues ​​​​की गणना करने के लिए कोई सरल एल्गोरिदम नहीं है, मैट्रिक्स के कई विशेष वर्ग हैं जहां eigenvalues ​​​​की सीधे गणना की जा सकती है। इसमे शामिल है:

त्रिकोणीय आव्यूह

चूंकि त्रिकोणीय मैट्रिक्स का निर्धारक इसकी विकर्ण प्रविष्टियों का उत्पाद है, यदि टी त्रिकोणीय है, तो ${\textstyle \det(\lambda I-T)=\prod _{i}(\lambda -T_{ii})}$. इस प्रकार T के eigenvalues ​​इसकी विकर्ण प्रविष्टियाँ हैं।

गुणनखंडीय बहुपद समीकरण

अगर p कोई बहुपद है और p(A) = 0, फिर के eigenvalues A भी उसी समीकरण को संतुष्ट करते हैं। अगर p एक ज्ञात गुणनखंडन होता है, फिर के eigenvalues A इसकी जड़ों के बीच स्थित है।

उदाहरण के लिए, एक प्रक्षेपण (रैखिक बीजगणित) एक वर्ग मैट्रिक्स है P संतुष्टि देने वाला P² = P. संगत अदिश बहुपद समीकरण की जड़ें, λ² = λ, 0 और 1 हैं। इस प्रकार किसी भी प्रक्षेपण के eigenvalues ​​​​के लिए 0 और 1 हैं। एक eigenvalue के रूप में 0 की बहुलता कर्नेल (रैखिक बीजगणित) # मैट्रिक्स गुणन के रूप में प्रतिनिधित्व है P, जबकि 1 की बहुलता की रैंक है P.

एक अन्य उदाहरण एक मैट्रिक्स है A जो संतुष्ट करता है A² = α²I कुछ अदिश राशि के लिए α. eigenvalues ​​​​होना चाहिए ±α. प्रक्षेपण संचालक

$P_{+}={\frac {1}{2}}\left(I+{\frac {A}{\alpha }}\right)$

$P_{-}={\frac {1}{2}}\left(I-{\frac {A}{\alpha }}\right)$

संतुष्ट करना

$AP_{+}=\alpha P_{+}\quad AP_{-}=-\alpha P_{-}$

और

$P_{+}P_{+}=P_{+}\quad P_{-}P_{-}=P_{-}\quad P_{+}P_{-}=P_{-}P_{+}=0.$

के स्तंभ स्थान P₊ और P₋ के eigenspaces हैं A तदनुसार +α और −α, क्रमश।

2×2 आव्यूह

आयाम 2 से 4 के लिए, रेडिकल से जुड़े सूत्र मौजूद हैं जिनका उपयोग आइगेनवैल्यू खोजने के लिए किया जा सकता है। जबकि 2×2 और 3×3 मैट्रिक्स के लिए एक सामान्य अभ्यास, 4×4 मैट्रिक्स के लिए क्वार्टिक फ़ंक्शन#फेरारी के समाधान की बढ़ती जटिलता इस दृष्टिकोण को कम आकर्षक बनाती है।

2×2 मैट्रिक्स के लिए

$A={\begin{bmatrix}a&b\\c&d\end{bmatrix}},$

अभिलाक्षणिक बहुपद है

$\det {\begin{bmatrix}\lambda -a&-b\\-c&\lambda -d\end{bmatrix}}=\lambda ^{2}\,-\,\left(a+d\right)\lambda \,+\,\left(ad-bc\right)=\lambda ^{2}\,-\,\lambda \,{\rm {tr}}(A)\,+\,\det(A).$

इस प्रकार द्विघात सूत्र का उपयोग करके eigenvalues ​​​​पाया जा सकता है:

$\lambda ={\frac {{\rm {tr}}(A)\pm {\sqrt {{\rm {tr}}^{2}(A)-4\det(A)}}}{2}}.$

परिभाषित ${\textstyle {\rm {gap}}\left(A\right)={\sqrt {{\rm {tr}}^{2}(A)-4\det(A)}}}$ दो eigenvalues ​​​​के बीच की दूरी होने के लिए, इसकी गणना करना सीधा है

${\frac {\partial \lambda }{\partial a}}={\frac {1}{2}}\left(1\pm {\frac {a-d}{{\rm {gap}}(A)}}\right),\qquad {\frac {\partial \lambda }{\partial b}}={\frac {\pm c}{{\rm {gap}}(A)}}$

के लिए समान सूत्रों के साथ c और d. इससे यह पता चलता है कि यदि आइगेनवैल्यू को अलग कर दिया जाए तो गणना अच्छी तरह से अनुकूल है।

केली-हैमिल्टन प्रमेय का उपयोग करके आइजेनवेक्टर पाया जा सकता है। अगर λ₁, λ₂ तो फिर आइगेनवैल्यू हैं (A − λ₁I)(A − λ₂I) = (A − λ₂I)(A − λ₁I) = 0, तो के कॉलम (A − λ₂I) द्वारा नष्ट कर दिया जाता है (A − λ₁I) और इसके विपरीत। यह मानते हुए कि कोई भी मैट्रिक्स शून्य नहीं है, प्रत्येक के कॉलम में अन्य eigenvalue के लिए eigenvectors शामिल होने चाहिए। (यदि कोई भी मैट्रिक्स शून्य है, तो A पहचान का गुणज है और कोई भी गैर-शून्य वेक्टर एक आइजेनवेक्टर है।)

उदाहरण के लिए, मान लीजिए

$A={\begin{bmatrix}4&3\\-2&-3\end{bmatrix}},$

तब tr(A) = 4 − 3 = 1 और det(A) = 4(−3) − 3(−2) = −6, तो विशेषता समीकरण है

$0=\lambda ^{2}-\lambda -6=(\lambda -3)(\lambda +2),$

और eigenvalues ​​​​3 और -2 हैं। अब,

$A-3I={\begin{bmatrix}1&3\\-2&-6\end{bmatrix}},\qquad A+2I={\begin{bmatrix}6&3\\-2&-1\end{bmatrix}}.$

दोनों मैट्रिक्स में, कॉलम एक-दूसरे के गुणज होते हैं, इसलिए किसी भी कॉलम का उपयोग किया जा सकता है। इस प्रकार, (1, −2) को eigenvalue -2 से जुड़े एक eigenvector के रूप में लिया जा सकता है, और (3, −1) एक आइजनवेक्टर के रूप में जो आइगेनवैल्यू 3 से जुड़ा है, जैसा कि उन्हें गुणा करके सत्यापित किया जा सकता है A.

3×3 आव्यूह

सममित 3×3 मैट्रिक्स का अभिलक्षणिक समीकरण A है:

$\det \left(\alpha I-A\right)=\alpha ^{3}-\alpha ^{2}{\rm {tr}}(A)-\alpha {\frac {1}{2}}\left({\rm {tr}}(A^{2})-{\rm {tr}}^{2}(A)\right)-\det(A)=0.$

इस समीकरण को क्यूबिक समीकरण#कार्डानो की विधि या क्यूबिक समीकरण#लैग्रेंज की विधि का उपयोग करके हल किया जा सकता है, लेकिन एक एफ़िन परिवर्तन A अभिव्यक्ति को काफी सरल बना देगा, और सीधे एक घन समीकरण#त्रिकोणमितीय और अतिशयोक्तिपूर्ण समाधान की ओर ले जाएगा। अगर A = pB + qI, तब A और B समान eigenvectors हैं, और β का एक प्रतिमान है B अगर और केवल अगर α = pβ + q का एक प्रतिमान है A. दे ${\textstyle q={\rm {tr}}(A)/3}$ और ${\textstyle p=\left({\rm {tr}}\left((A-qI)^{2}\right)/6\right)^{1/2}}$, देता है

$\det \left(\beta I-B\right)=\beta ^{3}-3\beta -\det(B)=0.$

प्रतिस्थापन β = 2cos θ और पहचान का उपयोग करके कुछ सरलीकरण cos 3θ = 4cos³ θ − 3cos θ समीकरण को कम कर देता है cos 3θ = det(B) / 2. इस प्रकार

$\beta =2{\cos }\left({\frac {1}{3}}{\arccos }\left(\det(B)/2\right)+{\frac {2k\pi }{3}}\right),\quad k=0,1,2.$

अगर det(B) जटिल है या निरपेक्ष मान में 2 से अधिक है, आर्ककोसाइन को सभी तीन मानों के लिए एक ही शाखा के साथ लिया जाना चाहिए k. कब ये बात नहीं उठती A वास्तविक और सममित है, जिसके परिणामस्वरूप एक सरल एल्गोरिदम बनता है:

% Given a real symmetric 3x3 matrix A, compute the eigenvalues
% Note that acos and cos operate on angles in radians

p1 = A(1,2)^2 + A(1,3)^2 + A(2,3)^2
if (p1 == 0) 
   % A is diagonal.
   eig1 = A(1,1)
   eig2 = A(2,2)
   eig3 = A(3,3)
else
   q = trace(A)/3               % trace(A) is the sum of all diagonal values
   p2 = (A(1,1) - q)^2 + (A(2,2) - q)^2 + (A(3,3) - q)^2 + 2 * p1
   p = sqrt(p2 / 6)
   B = (1 / p) * (A - q * I)    % I is the identity matrix
   r = det(B) / 2

   % In exact arithmetic for a symmetric matrix  -1 <= r <= 1
   % but computation error can leave it slightly outside this range.
   if (r <= -1) 
      phi = pi / 3
   elseif (r >= 1)
      phi = 0
   else
      phi = acos(r) / 3
   end

   % the eigenvalues satisfy eig3 <= eig2 <= eig1
   eig1 = q + 2 * p * cos(phi)
   eig3 = q + 2 * p * cos(phi + (2*pi/3))
   eig2 = 3 * q - eig1 - eig3     % since trace(A) = eig1 + eig2 + eig3
end

एक बार फिर, के eigenvectors A केली-हैमिल्टन प्रमेय का सहारा लेकर प्राप्त किया जा सकता है। अगर α₁, α₂, α₃ के विशिष्ट eigenvalues ​​​​हैं A, तब (A − α₁I)(A − α₂I)(A − α₃I) = 0. इस प्रकार इनमें से किन्हीं दो आव्यूहों के गुणनफल के कॉलम में तीसरे eigenvalue के लिए एक eigenvector होगा। हालांकि, यदि α₃ = α₁, तब (A − α₁I)²(A − α₂I) = 0 और (A − α₂I)(A − α₁I)² = 0. इस प्रकार का सामान्यीकृत eigenspace α₁ के कॉलम द्वारा फैलाया गया है A − α₂I जबकि साधारण आइगेनस्पेस को स्तंभों द्वारा फैलाया जाता है (A − α₁I)(A − α₂I). का साधारण eigenspace α₂ के कॉलम द्वारा फैलाया गया है (A − α₁I)².

उदाहरण के लिए, चलो

$A={\begin{bmatrix}3&2&6\\2&2&5\\-2&-1&-4\end{bmatrix}}.$

विशेषता समीकरण है

$0=\lambda ^{3}-\lambda ^{2}-\lambda +1=(\lambda -1)^{2}(\lambda +1),$

eigenvalues ​​​​1 (बहुलता 2 का) और -1 के साथ। गणना,

$A-I={\begin{bmatrix}2&2&6\\2&1&5\\-2&-1&-5\end{bmatrix}},\qquad A+I={\begin{bmatrix}4&2&6\\2&3&5\\-2&-1&-3\end{bmatrix}}$

और

$(A-I)^{2}={\begin{bmatrix}-4&0&-8\\-4&0&-8\\4&0&8\end{bmatrix}},\qquad (A-I)(A+I)={\begin{bmatrix}0&4&4\\0&2&2\\0&-2&-2\end{bmatrix}}$

इस प्रकार (−4, −4, 4) −1 के लिए एक eigenvector है, और (4, 2, −2) 1 के लिए एक eigenvector है। (2, 3, −1) और (6, 5, −3) दोनों 1 से जुड़े सामान्यीकृत आइजनवेक्टर हैं, जिनमें से किसी एक को इसके साथ जोड़ा जा सकता है (−4, −4, 4) और (4, 2, −2) के सामान्यीकृत eigenvectors का आधार बनाने के लिए A. एक बार मिल जाने के बाद, जरूरत पड़ने पर आइजनवेक्टर को सामान्य किया जा सकता है।

सामान्य 3×3 मैट्रिक्स के आइजनवेक्टर

यदि एक 3×3 मैट्रिक्स $A$ सामान्य है, तो क्रॉस-प्रोडक्ट का उपयोग ईजेनवेक्टर खोजने के लिए किया जा सकता है। अगर $\lambda$ का एक प्रतिरूप है $A$, फिर का शून्य स्थान $A-\lambda I$ इसके स्तंभ स्थान पर लंबवत है। के दो स्वतंत्र स्तंभों का क्रॉस उत्पाद $A-\lambda I$ शून्य स्थान में होगा. यानी यह एक आइजेनवेक्टर से जुड़ा होगा $\lambda$. चूँकि इस मामले में स्तंभ स्थान द्वि-आयामी है, इसलिए eigenspace एक आयामी होना चाहिए, इसलिए कोई भी अन्य eigenvector इसके समानांतर होगा।

अगर $A-\lambda I$ इसमें दो स्वतंत्र कॉलम नहीं हैं लेकिन ऐसा नहीं है 0, क्रॉस-प्रोडक्ट का अभी भी उपयोग किया जा सकता है। इस मामले में $\lambda$ गुणन 2 का एक eigenvalue है, इसलिए स्तंभ स्थान पर लंबवत कोई भी वेक्टर एक eigenvector होगा। कल्पना करना $\mathbf {v}$ का एक गैर-शून्य स्तंभ है $A-\lambda I$. एक मनमाना वेक्टर चुनें $\mathbf {u}$ के समानांतर नहीं $\mathbf {v}$. तब $\mathbf {v} \times \mathbf {u}$ और $(\mathbf {v} \times \mathbf {u} )\times \mathbf {v}$ के लंबवत होगा $\mathbf {v}$ और इस प्रकार के eigenvectors होंगे $\lambda$.

यह कब काम नहीं करता $A$ सामान्य नहीं है, क्योंकि ऐसे मैट्रिक्स के लिए शून्य स्थान और स्तंभ स्थान को लंबवत होने की आवश्यकता नहीं है।

यह भी देखें

• संख्यात्मक विश्लेषण विषयों की सूची#आइजेनवैल्यू एल्गोरिदम

अग्रिम पठन

• Bojanczyk, Adam W.; Adam Lutoborski (Jan 1991). "Computation of the Euler angles of a symmetric 3X3 matrix". SIAM Journal on Matrix Analysis and Applications. 12 (1): 41–48. doi:10.1137/0612005.