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

From Vigyanwiki
Revision as of 13:28, 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. सामान्य, हर्मिटियन और वास्तविक-सममित आव्युह में अनेक उपयोगी गुण होते हैं:

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

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

नियम संख्या

संख्यात्मक गणना की किसी भी समस्या को कुछ इनपुट x के लिए किसी फलन f के मूल्यांकन के रूप में देखा जा सकता है. समस्या की नियम संख्या κ(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. सामान्य आव्युह के लिए, ऑपरेटर मानदंड की गणना करना अधिकांशतः मुश्किल होता है। इस कारण से, स्थिति संख्या का अनुमान लगाने के लिए सामान्यतः अन्य आव्युह मानदंडो का उपयोग किया जाता है।

आइजेनवैल्यू समस्या के लिए, बाउर और फ़ाइक की प्रमेय ने सिद्ध किया कि यदि λ आइगेनवेक्टर आव्युह V के साथ एक विकर्णीय n × n आव्युह A के लिए एक आइगेनवैल्यू है, तो λ की गणना करने में पूर्ण त्रुटि κ(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, A से i-वीं पंक्ति और स्तंभ को हटाकर प्राप्त किया गया आव्युह है |, और मान लीजिए कि λk(Aj) इसका k-वां आइजेनवैल्यू है . तब


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

यह मानते हुए कि व्युत्पन्न पर शून्य नहीं है .

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

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

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

विधि के लिए आवेदन करें निर्माण करना समानता आव्युह के बिना निवेश समानता आव्युह के बिना निवेश वर्णन
हाउसहोल्डर ट्रांसफॉर्मेशन सामान्य हेसेनबर्ग 2n33 + O(n2)[10]: 474  4n33 + O(n2)[10]: 474  प्रत्येक स्तम्भ को उसकी निचली प्रविष्टियों को शून्य करने के लिए एक उप-स्थान के माध्यम से प्रतिबिंबित करें।
गिवेन्स रोटेशन सामान्य हेसेनबर्ग 4n33 + O(n2)[10]: 470  व्यक्तिगत प्रविष्टियों को शून्य करने के लिए समतलीय घुमाव प्रयुक्त करते है तथा घूर्णन का आदेश दिया जाता है जिससे कि इसके पश्चात् में शून्य प्रविष्टियाँ फिर से गैर-शून्य न हो जाएँ।
अर्नोल्डी पुनरावृति सामान्य हेसेनबर्ग क्रायलोव उप-स्थानों पर ग्राम-श्मिट ऑर्थोगोनलाइज़ेशन निष्पादित करें।
लैंज़ोस एल्गोरिथ्म हर्मिटियन त्रिविकर्णीय हर्मिटियन मैट्रिसेस के लिए अर्नोल्डी पुनरावृत्ति, शॉर्टकट के साथ।

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


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

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

विधि प्रयुक्त करें निर्माण करना प्रति कदम निवेश कोन्वेर्गेंस विवरण
लैंज़ोस एल्गोरिदम हर्मिटियन m

लार्जेस्ट/ स्मालेस्ट आइजेनपैयर्स

पॉवर इटेरशन सामान्य आइजेनपैयर सर्वाधिक मान के साथ O(n2) रेखीय आव्युह को एक इच्छा से प्रारंभिक सदिश पर निरंतर प्रयुक्त करता है और पुनर्सामान्यीकृत करता है।
इनवर्स इटेरशन सामान्यl आइजेनपैयर μ के निकटतम मान के साथ रेखीय पॉवर इटेरशन फॉर (AμI)−1
रेलेइ कोटिऐंट इटेरशन हर्मिटियन कोई भी आइजेनपैयर क्यूबिक (A − μiI)−1 के लिए पावर पुनरावृत्ति, जहां प्रत्येक पुनरावृत्ति के लिए μi पिछले पुनरावृत्ति का रेले भागफल है।
पूर्वनिर्धारित इनवर्स इटेरशन[12] or एलओबीपीसीजी एल्गोरिदम धनात्मक-निश्चित वास्तविक सममिति आइजेनपैयर ''μ'' के निकटतम मान के साथ प्रीकंडीशनर का उपयोग करके व्युत्क्रम पुनरावृत्ति ( का लगभग व्युत्क्रम)।
बिसेक्शन विधि वास्तविक सममित त्रिदिकोणीय कोई भी आइजेनवैल्यू रेखीय स्टर्म अनुक्रम द्वारा समर्थित, विशेषता बहुपद की जड़ों को खोजने के लिए द्विभाजन विधि का उपयोग करता है।
लागुएरे इटेरशन वास्तविक सममित त्रिदिकोणीय कोई भी आइजेनवैल्यू क्यूबिक[13] स्टर्म अनुक्रम द्वारा समर्थित, विशेषता बहुपद की जड़ों को खोजने के लिए लैगुएरे की विधि का उपयोग करता है।
क्यूआर एल्गोरिदम हेसेनबर्ग सभी आइजेनवैल्यू O(n2) क्यूबिक कारक A = QR, जहां Q ओर्थोगोनल है और R त्रिकोणीय है, फिर अगला पुनरावृत्ति RQ पर प्रयुक्त होता है।
सभी आइजेनपैयर्स 6n3 + O(n2)
जैकोबी आइजेनवैल्यू एल्गोरिदम वास्तविक सममित सभी आइजेनवैल्यू O(n3) द्विघात सभी ऑफ-विकर्ण प्रविष्टियों को साफ़ करने का प्रयास करने के लिए गिवेंस रोटेशन का उपयोग करता है। यह विफल रहता है, किन्तु विकर्ण को मजबूत करता है।
डिवाइड -एंड-कॉन्कर त्रिदिकोणीय हर्मिटियन सभी आइजेनवैल्यू O(n2) आव्युह को उपमैट्रिस में विभाजित करें जिन्हें विकर्ण किया जाता है और फिर पुनः संयोजित किया जाता है।
सभी आइजेनपैयर्स (43)n3 + O(n2)
होमोटोपी विधि वास्तविक सममित त्रिविकर्ण सभी आइजेनपैयर्स O(n2)[14] एक विकर्ण आइजेनवेल्यू समस्या से एक गणना योग्य समरूप पथ का निर्माण करता है।
फोल्डेड स्पेक्ट्रम विधि वास्तविक सममित आइजेनपैयर μ के निकटतम मान के साथ पूर्वनिर्धारित व्युत्क्रम पुनरावृत्ति (AμI)2 पर लागू होती है
एमआरआरआर एल्गोरिदम[15] वास्तविक सममित त्रिविकर्ण कुछ या सभी आइजेनपैयर्स O(n2) "एकाधिक अपेक्षाकृत मजबूत प्रतिनिधित्व" - स्थानांतरित मैट्रिक्स के एलडीएलटी अपघटन पर उलटा पुनरावृत्ति करता है।


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

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

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

चूंकि त्रिकोणीय आव्युह का निर्धारक इसकी विकर्ण प्रविष्टियों का उत्पाद है, यदि T त्रिकोणीय है, तो . इस प्रकार 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 के स्तंभ स्थान क्रमश +α और α के संगत 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. 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


अग्रिम पठन