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

From Vigyanwiki
Revision as of 09:54, 29 July 2023 by alpha>Shikhav

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

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

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

जहाँ 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)n v = 0 λ के साथ जुड़े सभी सामान्यीकृत आइजेनवेक्टर v के लिए समान्तर लिया जा सकता है |

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

जहाँ det निर्धारक फलन है, तथा λi A के सभी विशिष्ट आइजेनवैल्यू ​​हैं और यह αi संगत बीजगणितीय बहुलता हैं। फलन pA(z) A का अभिलक्षणिक बहुपद है. इसलिए बीजगणितीय बहुलता अभिलाक्षणिक बहुपद की बहुपद मूल के गुणों के रूप में आइगेनवैल्यू की बहुलता है। चूँकि कोई भी आइजेनवेक्टर सामान्यीकृत आइजेनवेक्टर भी है, तब ज्यामितीय बहुलता बीजगणितीय बहुलता से कम या उसके समान्तर है। बीजगणितीय बहुलताओं का योग n होता है, जो कि विशेषता बहुपद की डिग्री है। समीकरण pA(z) = 0 को अभिलक्षणिक समीकरण कहा जाता है, क्योंकि इसकी मूल बिल्कुल A कि आइजेनवैल्यू ​​​​हैं. केली-हैमिल्टन प्रमेय के द्वारा, A स्वयं उसी समीकरण का पालन करता है: जिसमे परिणामस्वरूप pA(A) = 0. आव्युह के कॉलम या तो 0 होना चाहिए या आइजेनवैल्यू λj का सामान्यीकृत आइजेनवेक्टर होना चाहिए , चूंकि वह नष्ट कर दिए जाते है . वास्तव में, स्तंभ स्थान λj का सामान्यीकृत ईजेनस्पेस है .

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

  • यदि vi और vj का आइजेनवैल्यू समान है, तो i और j के बीच प्रत्येक k के लिए vk में ऐसा ही समान होता है, और
  • यदि vi साधारण आइजनवेक्टर नहीं है, और यदि λi इसका आइजेनवैल्यू है तो फिर (AλiI)vi = vi−1 (विशेष रूप से, v1 साधारण आइजेनवेक्टर होना चाहिए)।

यदि इन आधार सदिशों को आव्युह V = [v1 v2vn] के कॉलम सदिश के रूप में रखा जाता है, तब V का उपयोग A को उसके जॉर्डन सामान्य रूप में परिवर्तित करने के लिए किया जा सकता है :

जहां λi आइजेनवैल्यू ​​हैं, βi = 1 यदि (Aλi+1)vi+1 = vi और βi = 0 अन्यथा।

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

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

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

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

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

नियम संख्या

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

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

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

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

एल्गोरिदम

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

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

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

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

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

सामान्य आव्युह के यूनिट ईजेनवेक्टर घटकों के मानदंड के लिए सूत्र रॉबर्ट थॉम्पसन द्वारा 1966 में खोजा गया था और कई अन्य लोगों द्वारा स्वतंत्र रूप से फिर से खोजा गया था। [5][6][7][8][9] यदि A आइजेनवैल्यू ​​​​के साथ सामान्य आव्युह λi(A) और संबंधित इकाई आइजेनवेक्टर viजिसकी घटक प्रविष्टियाँ हैं vi,j, होने देना Aj हो को हटाकर प्राप्त आव्युह i-वीं पंक्ति और स्तंभ से A, और जाने λk(Aj) यह हो k-वां आइजेनवैल्यू . तब

यदि के अभिलाक्षणिक बहुपद हैं और , सूत्र को इस प्रकार पुनः लिखा जा सकता है
व्युत्पन्न मानते हुए पर शून्य नहीं है .

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

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

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

Method Applies to Produces Cost without similarity matrix Cost with similarity matrix Description
Householder transformations General Hessenberg 2n33 + O(n2)[10]: 474  4n33 + O(n2)[10]: 474  Reflect each column through a subspace to zero out its lower entries.
Givens rotations General Hessenberg 4n33 + O(n2)[10]: 470  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)) में संख्यात्मक रूप से गणना की जा सकती है। [11]


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

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

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[12] 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[13] 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 (43)n3 + O(n2)
Homotopy method real symmetric tridiagonal all eigenpairs O(n2)[14] 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[15] real symmetric tridiagonal some or all eigenpairs O(n2) "Multiple relatively robust representations" – performs inverse iteration on a LDLT decomposition of the shifted matrix.


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

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

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

चूंकि त्रिकोणीय आव्युह का निर्धारक इसकी विकर्ण प्रविष्टियों का उत्पाद है, यदि टी त्रिकोणीय है, तो . इस प्रकार T के आइजेनवैल्यू ​​इसकी विकर्ण प्रविष्टियाँ हैं।

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

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

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

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

संतुष्ट करना

और

के स्तंभ स्थान P+ और P के ईजेनस्पेस s हैं A तदनुसार +α और α, क्रमश।

2×2 आव्यूह

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

2×2 आव्युह के लिए

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

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

परिभाषित दो आइजेनवैल्यू ​​​​के बीच की दूरी होने के लिए, इसकी गणना करना सीधा है

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

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

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

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

और आइजेनवैल्यू ​​​​3 और -2 हैं। अब,

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

3×3 आव्यूह

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

इस समीकरण को क्यूबिक समीकरण#कार्डानो की विधि या क्यूबिक समीकरण#लैग्रेंज की विधि का उपयोग करके हल किया जा सकता है, लेकिन एफ़िन परिवर्तन A अभिव्यक्ति को काफी सरल बना देगा, और सीधे घन समीकरण#त्रिकोणमितीय और अतिशयोक्तिपूर्ण समाधान की ओर ले जाएगा। यदि A = pB + qI, तब A और B समान आइजेनवेक्टर हैं, और β का प्रतिमान है B यदि और केवल यदि α = + q का प्रतिमान है A. दे और , देता है

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

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

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

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

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

आइजेनवैल्यू ​​​​1 (बहुलता 2 का) और -1 के साथ। गणना,

और

इस प्रकार (−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 आव्युह सामान्य है, तो क्रॉस-प्रोडक्ट का उपयोग ईजेनवेक्टर खोजने के लिए किया जा सकता है। यदि का प्रतिरूप है , फिर का शून्य स्थान इसके स्तंभ स्थान पर लंबवत है। के दो स्वतंत्र स्तंभों का क्रॉस उत्पाद शून्य स्थान में होगा. यानी यह आइजेनवेक्टर से जुड़ा होगा . चूँकि इस स्तिथियों में स्तंभ स्थान द्वि-आयामी है, इसलिए ईजेनस्पेस आयामी होना चाहिए, इसलिए कोई भी अन्य आइजेनवेक्टर इसके समानांतर होगा।

यदि इसमें दो स्वतंत्र कॉलम नहीं हैं लेकिन ऐसा नहीं है 0, क्रॉस-प्रोडक्ट का अभी भी उपयोग किया जा सकता है। इस स्तिथियों में गुणन 2 का आइजेनवैल्यू है, इसलिए स्तंभ स्थान पर लंबवत कोई भी सदिश आइजेनवेक्टर होगा। कल्पना करना का गैर-शून्य स्तंभ है . मनमाना सदिश चुनें के समानांतर नहीं . तब और के लंबवत होगा और इस प्रकार के आइजेनसदिश होंगे .

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

यह भी देखें

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

टिप्पणियाँ

  1. This ordering of the inner product (with the conjugate-linear position on the left), is preferred by physicists. Algebraists often place the conjugate-linear position on the right: wv = v* w.


संदर्भ

  1. Axler, Sheldon (1995), "Down with Determinants!" (PDF), American Mathematical Monthly, 102 (2): 139–154, doi:10.2307/2975348, JSTOR 2975348, archived from the original (PDF) on 2012-09-13, retrieved 2012-07-31
  2. F. L. Bauer; C. T. Fike (1960), "Norms and exclusion theorems", Numer. Math., 2: 137–141, doi:10.1007/bf01386217, S2CID 121278235
  3. S.C. Eisenstat; I.C.F. Ipsen (1998), "Relative Perturbation Results for Eigenvalues and Eigenvectors of Diagonalisable Matrices", BIT, 38 (3): 502–9, doi:10.1007/bf02510256, S2CID 119886389
  4. J. Dongarra and F. Sullivan (2000). "सदी के शीर्ष दस एल्गोरिदम". Computing in Science and Engineering. 2: 22-23.
  5. Thompson, R. C. (June 1966). "सामान्य और हर्मिटियन मैट्रिक्स के प्रमुख उपमैट्रिसेस". Illinois Journal of Mathematics. 10 (2): 296–308. doi:10.1215/ijm/1256055111.
  6. Peter Nylen; Tin-Yau Tam; Frank Uhlig (1993). "सामान्य, हर्मिटियन और सममित मैट्रिक्स के प्रमुख उपमैट्रिसेस के आइगेनवैल्यू पर". Linear and Multilinear Algebra. 36 (1): 69–78. doi:10.1080/03081089308818276.
  7. N. Bebiano, S. Furtado, J. da Providência (2011). "जे-सामान्य मैट्रिक्स के प्रमुख उपमैट्रिसेस के आइगेनवैल्यू पर". Linear Algebra and Its Applications. 435 (12): 3101–3114. doi:10.1016/j.laa.2011.05.033.{{cite journal}}: CS1 maint: uses authors parameter (link)
  8. Forrester PJ, Zhang J (2021). "कॉरैंक-1 प्रक्षेपण और यादृच्छिक हॉर्न समस्या". Tunisian Journal of Mathematics. 3: 55–73. arXiv:1905.05314. doi:10.2140/tunis.2021.3.55. S2CID 153312446.
  9. Denton PB, Parke SJ, Tao T, Zhang X (2021). "Eigenvectors from eigenvalues: A survey of a basic identity in linear algebra". Bulletin of the American Mathematical Society. 59: 1. arXiv:1908.03795. doi:10.1090/bull/1722. S2CID 213918682.
  10. 10.0 10.1 10.2 Press, William H.; Teukolsky, Saul A.; Vetterling, William T.; Flannery, Brian P. (1992). Numerical Recipes in C (2nd ed.). Cambridge University Press. ISBN 978-0-521-43108-8.
  11. Coakley, Ed S. (May 2013), "A fast divide-and-conquer algorithm for computing the spectra of real symmetric tridiagonal matrices.", Applied and Computational Harmonic Analysis, 34 (3): 379–414, doi:10.1016/j.acha.2012.06.003
  12. Neymeyr, K. (2006), "A geometric theory for preconditioned inverse iteration IV: On the fastest convergence cases.", Linear Algebra Appl., 415 (1): 114–139, doi:10.1016/j.laa.2005.06.022
  13. Li, T. Y.; Zeng, Zhonggang (1992), "Laguerre's Iteration In Solving The Symmetric Tridiagonal Eigenproblem - Revisited", SIAM Journal on Scientific Computing
  14. Chu, Moody T. (1988), "A Note on the Homotopy Method for Linear Algebraic Eigenvalue Problems", Linear Algebra Appl., 105: 225–236, doi:10.1016/0024-3795(88)90015-8
  15. Dhillon, Inderjit S.; Parlett, Beresford N.; Vömel, Christof (2006), "The Design and Implementation of the MRRR Algorithm" (PDF), ACM Transactions on Mathematical Software, 32 (4): 533–560, doi:10.1145/1186785.1186788, S2CID 2410736
  16. Smith, Oliver K. (April 1961), "Eigenvalues of a symmetric 3 × 3 matrix.", Communications of the ACM, 4 (4): 168, doi:10.1145/355578.366316, S2CID 37815415


अग्रिम पठन