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

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

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

Main articles: आइजेनवैल्यू और आइजेनवेक्टर and सामान्यीकृत ईजेनवेक्टर

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

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

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

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

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

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

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

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

यदि इन आधार सदिशों को आव्युह के कॉलम सदिश के रूप में रखा जाता है 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 आइजेनवैल्यू ​​हैं, β_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. अर्थात्, समान आव्यूहों के आइजेनवैल्यू ​​​​समान होते हैं।

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

Main articles: संलग्न आव्युह, साधारण आव्युह, and हर्मिटियन आव्युह

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

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

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

नियम संख्या

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

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

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

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

एल्गोरिदम

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

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

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

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

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

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

$$|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: हेस्सेनबर्ग आव्युह

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

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

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.

सममित त्रिदिकोणीय आइजेनवैल्यू समस्याओं के लिए सभी आइजेनवैल्यू ​​​​(आइजेनवेक्टर के बिना) को विशेषता बहुपद पर द्विभाजन का उपयोग करके समय 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 आइजेनवैल्यू		linear	Uses the bisection method to find roots of the characteristic polynomial, supported by the Sturm sequence.
Laguerre iteration	real symmetric tridiagonal	any आइजेनवैल्यू		cubic	Uses Laguerre's method to find roots of the characteristic polynomial, supported by the Sturm sequence.
QR algorithm	Hessenberg	all आइजेनवैल्यू	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 आइजेनवैल्यू algorithm	real symmetric	all आइजेनवैल्यू	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 आइजेनवैल्यू	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 आइजेनवैल्यू 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.

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

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

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

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

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

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

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

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

$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₋ के ईजेनस्पेस s हैं 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).$

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

$\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)}}}$ दो आइजेनवैल्यू ​​​​के बीच की दूरी होने के लिए, इसकी गणना करना सीधा है

${\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) और इसके विपरीत। यह मानते हुए कि कोई भी आव्युह शून्य नहीं है, प्रत्येक के कॉलम में अन्य आइजेनवैल्यू के लिए आइजेनवेक्टर सम्मिलित होने चाहिए। (यदि कोई भी आव्युह शून्य है, तो 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),$

और आइजेनवैल्यू ​​​​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) को आइजेनवैल्यू -2 से जुड़े आइजेनवेक्टर के रूप में लिया जा सकता है, और (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 समान आइजेनवेक्टर हैं, और β का प्रतिमान है 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

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

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

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

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

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