जैकोबी आइजेनवैल्यू एल्गोरिथम: Difference between revisions
(Created page with "संख्यात्मक रैखिक बीजगणित में, जैकोबी eigenvalue एल्गोरिथ्म एक वास्त...") |
No edit summary |
||
Line 1: | Line 1: | ||
[[संख्यात्मक रैखिक बीजगणित]] में | [[संख्यात्मक रैखिक बीजगणित]] में जैकोबी [[eigenvalue|आइजेनवैल्यू]] एल्गोरिथ्म [[वास्तविक संख्या]] [[सममित मैट्रिक्स]] (एक प्रक्रिया जिसे मैट्रिक्स डायगोनलाइज़ेशन के रूप में जाना जाता है) के आइजेनवैल्यू और [[आइजन्वेक्टर]] की गणना के लिए पुनरावृत्त विधि है। इसका नाम [[कार्ल गुस्ताव जैकब जैकोबी]] के नाम पर रखा गया है जिन्होंने पहली बार सन 1846 में इस पद्धति का प्रस्ताव रखा था।<ref>{{cite journal | ||
|last=Jacobi |first=C.G.J. |authorlink=Carl Gustav Jacob Jacobi | |last=Jacobi |first=C.G.J. |authorlink=Carl Gustav Jacob Jacobi | ||
|url=http://gdz.sub.uni-goettingen.de/dms/load/img/?PID=GDZPPN002144522 | |url=http://gdz.sub.uni-goettingen.de/dms/load/img/?PID=GDZPPN002144522 | ||
Line 6: | Line 6: | ||
|volume=1846 |issue=30 |year=1846 |pages=51–94 | |volume=1846 |issue=30 |year=1846 |pages=51–94 | ||
|language=German | |language=German | ||
|doi=10.1515/crll.1846.30.51 }}</ref> लेकिन 1950 के दशक में कंप्यूटर के आगमन के साथ ही इसका व्यापक रूप से उपयोग किया जाने लगा।<ref>{{cite journal | |doi=10.1515/crll.1846.30.51 }}</ref> लेकिन सन 1950 के दशक में कंप्यूटर के आगमन के साथ ही इसका व्यापक रूप से उपयोग किया जाने लगा।<ref>{{cite journal | ||
|first=G.H. |last=Golub | |first=G.H. |last=Golub | ||
|first2=H.A. |last2=van der Vorst | |first2=H.A. |last2=van der Vorst | ||
Line 14: | Line 14: | ||
|doi=10.1016/S0377-0427(00)00413-1 | |doi=10.1016/S0377-0427(00)00413-1 | ||
|doi-access=free}}</ref> | |doi-access=free}}</ref> | ||
== विवरण == | == विवरण == | ||
माना कि <math>S</math> सममित मैट्रिक्स और <math>G=G(i,j,\theta)</math>, [[गिवेंस रोटेशन|गिवेंस रोटेशन मैट्रिक्स]] हो। तब: | |||
:<math>S'=G S G^\top \, </math> | :<math>S'=G S G^\top \, </math> | ||
सममित और [[समान (रैखिक बीजगणित)]] | सममित और [[समान (रैखिक बीजगणित)]] <math>S</math> है। | ||
अन्य, <math>S^\prime</math> प्रविष्टियाँ हैं: | |||
:<math>\begin{align} | :<math>\begin{align} | ||
Line 32: | Line 30: | ||
S'_{kl} &= S_{kl} &k,l \ne i,j | S'_{kl} &= S_{kl} &k,l \ne i,j | ||
\end{align}</math> | \end{align}</math> | ||
जहाँ <math>s=\sin(\theta)</math> और <math>c=\cos(\theta)</math> | |||
जब से <math>G</math> का अर्थ ऑर्थोगोनल है, <math>S</math> और <math>S^\prime</math> समान [[फ्रोबेनियस मानदंड]] <math>||\cdot||_F</math> (सभी घटकों के वर्गों का वर्गमूल योग) है जबकि हम <math>\theta</math> चुन सकते हैं तथा यह इस प्रकार है कि <math>S^\prime_{ij}=0</math>, इस स्थिति में <math>S^\prime</math> विकर्ण पर वर्गों का योग बड़ा है: | |||
:<math> S'_{ij} = \cos(2\theta) S_{ij} + \tfrac{1}{2} \sin(2\theta) (S_{ii} - S_{jj}) </math> | :<math> S'_{ij} = \cos(2\theta) S_{ij} + \tfrac{1}{2} \sin(2\theta) (S_{ii} - S_{jj}) </math> | ||
Line 40: | Line 38: | ||
:<math> \tan(2\theta) = \frac{2 S_{ij}}{S_{jj} - S_{ii}} </math> | :<math> \tan(2\theta) = \frac{2 S_{ij}}{S_{jj} - S_{ii}} </math> | ||
यदि <math> S_{jj} = S_{ii} </math> | |||
:<math> \theta = \frac{\pi} {4} </math> | :<math> \theta = \frac{\pi} {4} </math> | ||
इस प्रभाव को अनुकूलित करने के लिए, | इस प्रभाव को अनुकूलित करने के लिए, S<sub>''ij''</sub> सबसे बड़े निरपेक्ष मान वाला [[ऑफ-विकर्ण तत्व]] होना चाहिए जिसे धुरी कहा जाता है। | ||
जैकोबी | जैकोबी आइजेनवैल्यू विधि जैकोबी को तब तक बार-बार घुमाती है जब तक कि मैट्रिक्स लगभग विकर्ण न हो जाए। इसके पश्चात विकर्ण में तत्व S के (वास्तविक) स्वदेशी मानों के सन्निकटन हैं। | ||
== अभिसरण == | == अभिसरण == | ||
यदि <math> p = S_{kl} </math> परिभाषा के अनुसार धुरी तत्व <math> |S_{ij} | \le |p| </math> के लिए <math> 1 \le i, j \le n, i \ne j</math> है। माना कि <math>\Gamma(S)^2</math> की सभी ऑफ-विकर्ण प्रविष्टियों के वर्गों का योग <math>S</math> निरूपित करें। जब से <math>S</math>, <math> 2N := n(n-1) </math> निश्चित है, हमारे पास ऑफ-विकर्ण तत्व <math> p^2 \le \Gamma(S )^2 \le 2 N p^2 </math> या <math> 2 p^2 \ge \Gamma(S )^2 / N </math> है। अब <math>\Gamma(S^J)^2=\Gamma(S)^2-2p^2</math>। यह संकेत <math> \Gamma(S^J )^2 \le (1 - 1 / N ) \Gamma (S )^2 </math> या <math> \Gamma (S^ J ) \le (1 - 1 / N )^{1 / 2} \Gamma(S ) </math> करता है; | |||
अर्थात् | |||
अर्थात् जैकोबी घूर्णन का क्रम एक कारक द्वारा कम से कम रैखिक रूप से <math> (1 - 1 / N )^{1 / 2} </math> विकर्ण मैट्रिक्स के लिए परिवर्तित होता है। | |||
<math> N </math> की एक संख्या जैकोबी रोटेशन को स्वीप कहा जाता है; माना कि <math> S^{\sigma} </math>परिणाम निरूपित करें। पिछला अनुमान उत्पन्न करता है। | |||
: <math> \Gamma(S^{\sigma} ) \le \left(1 - \frac{1}{N} \right)^{N / 2} \Gamma(S ) </math>; | : <math> \Gamma(S^{\sigma} ) \le \left(1 - \frac{1}{N} \right)^{N / 2} \Gamma(S ) </math>; | ||
अर्थात् | अर्थात् स्वीप का क्रम कारक ≈ के साथ कम से कम रैखिक रूप <math> e ^{1 / 2}</math> से परिवर्तित होता है | ||
जबकि अर्नोल्ड शॉनहेज का निम्नलिखित परिणाम<ref>{{cite journal | |||
|last=Schönhage |first=A. | |last=Schönhage |first=A. | ||
|title=Zur quadratischen Konvergenz des Jacobi-Verfahrens | |title=Zur quadratischen Konvergenz des Jacobi-Verfahrens | ||
Line 62: | Line 61: | ||
|language=German | |language=German | ||
|doi=10.1007/BF01386091 |mr=174171 | |doi=10.1007/BF01386091 |mr=174171 | ||
}}</ref> स्थानीय रूप से द्विघात अभिसरण उत्पन्न करता है। इस प्रयोजन के लिए मान लीजिए कि S के पास m विशिष्ट | }}</ref> स्थानीय रूप से द्विघात अभिसरण उत्पन्न करता है। इस प्रयोजन के लिए मान लीजिए कि S के पास m विशिष्ट आइजेनवैल्यू <math> \lambda_1, ... , \lambda_m </math> बहुलता के साथ <math> \nu_1, ... , \nu_m </math>हैं और मान लीजिए कि d > 0 दो अलग-अलग आइजेनवैल्यू की सबसे छोटी दूरी है। आइए हम कुछ नंबर को प्रयोग करें | ||
: <math> N_S := \frac{n (n - 1)}{2} - \sum_{\mu = 1}^{m} \frac{1}{2} \nu_{\mu} (\nu_{\mu} - 1) \le N </math> | : <math> N_S := \frac{n (n - 1)}{2} - \sum_{\mu = 1}^{m} \frac{1}{2} \nu_{\mu} (\nu_{\mu} - 1) \le N </math> | ||
जैकोबी शॉनहेज-स्वीप | जैकोबी शॉनहेज-स्वीप रोटेशन करता है। यदि तब <math> S^ s </math> परिणाम को दर्शाता है | ||
: <math> \Gamma(S^ s ) \le\sqrt{\frac{n}{2} - 1} \left(\frac{\gamma^2}{d - 2\gamma}\right), \quad \gamma := \Gamma(S ) </math> . | : <math> \Gamma(S^ s ) \le\sqrt{\frac{n}{2} - 1} \left(\frac{\gamma^2}{d - 2\gamma}\right), \quad \gamma := \Gamma(S ) </math> . | ||
इस प्रकार अभिसरण | इस प्रकार अभिसरण शीघ्र ही द्विघात हो जाता है | ||
<math> \Gamma(S ) < \frac{d}{2 + \sqrt{\frac{n}{2} - 1}} </math> | <math> \Gamma(S ) < \frac{d}{2 + \sqrt{\frac{n}{2} - 1}} </math> | ||
== लागत == | == लागत == | ||
प्रत्येक जैकोबी घूर्णन O(n) चरणों में किया जा सकता है जब धुरी तत्व p ज्ञात हो। | प्रत्येक जैकोबी घूर्णन O(n) चरणों में किया जा सकता है जब धुरी तत्व p ज्ञात हो। जबकि p की खोज के लिए सभी N≈{{sfrac|1|2}} n<sup>2</sup> ऑफ-विकर्ण तत्व के निरीक्षण की आवश्यकता होती है। यदि हम एक अतिरिक्त सूचकांक सरणी प्रस्तुत करते हैं तो हम इसे O(n) जटिलता तक भी कम कर सकते हैं <math> m_1, \, \dots \, , \, m_{n - 1} </math> उस संपत्ति के साथ <math> m_i </math> वर्तमान S की पंक्ति i, (i = 1, ..., n − 1) में सबसे बड़े तत्व का सूचकांक है। इसके पश्चात धुरी के सूचकांक (k, l) जोड़े में से एक होना चाहिए <math> (i, m_i) </math>. इसके अतिरिक्त सूचकांक सरणी का अद्यतनीकरण O(n) औसत-केस जटिलता में किया जा सकता है: सबसे अद्यतन पंक्तियों k और l में अधिकतम प्रविष्टि O(n) चरणों में पाई जा सकती है। अन्य पंक्तियों में केवल कॉलम k और l में प्रविष्टियाँ परिवर्तित होता हैं। इन पंक्तियों पर लूपिंग यदि <math> m_i </math> न तो k है और न ही l, यह पुराने अधिकतम <math> m_i </math> की तुलना करने के लिए पर्याप्त है नई प्रविष्टियों और अद्यतन के लिए <math> m_i </math> यदि आवश्यक है। यदि <math> m_i </math> k या l के बराबर होना चाहिए और अद्यतन के समय संबंधित प्रविष्टि कम हो गई है एवं अधिकतम पंक्ति i को O(n) जटिलता में स्क्रैच से पाया जाना चाहिए। जबकि ऐसा प्रति रोटेशन औसतन केवल एक बार होगा। इस प्रकार प्रत्येक रोटेशन में O(n) और एक स्वीप O(n)<sup>3</sup> होता है) औसत-केस जटिलता जो मैट्रिक्स गुणन के सामान है। इसके अतिरिक्त प्रक्रिया आरम्भ होने से पहले <math> m_i </math> आरंभ किया जाना चाहिए, जिसे n<sup>2 चरणों में किया जा सकता है। | ||
सामान्य रूप से जैकोबी पद्धति कम संख्या में स्वीप के बाद संख्यात्मक परिशुद्धता के भीतर परिवर्तित हो जाती है। ध्यान दें कि <math>N_S < N</math> एकाधिक आइजेनवैल्यू पुनरावृत्तियों की संख्या को कम कर देते हैं। | |||
== एल्गोरिथम == | == एल्गोरिथम == | ||
निम्नलिखित एल्गोरिदम गणित जैसे नोटेशन में जैकोबी पद्धति का विवरण है। | निम्नलिखित एल्गोरिदम गणित जैसे नोटेशन में जैकोबी पद्धति का विवरण है। | ||
यह | |||
यह वेक्टर e की गणना करता है जिसमें आइजेनवैल्यू और मैट्रिक्स E होता है जिसमें संबंधित आइजेनवेक्टर होते हैं; वह <math> e_i </math> है, एक आइजेनवैल्यू और स्तंभ है <math> E_i </math> के लिए ऑर्थोनॉर्मल आइजेनवेक्टर <math> e_i </math>, I = 1, ..., n। | |||
'प्रक्रिया' जैकोबी(एस ∈ 'आर'<sup>n×n</sup>; 'बाहर' ई ∈ 'आर'<sup>n</sup>; 'बाहर' ई ∈ 'आर'<sup>n×n</sup>) | 'प्रक्रिया' जैकोबी(एस ∈ 'आर'<sup>n×n</sup>; 'बाहर' ई ∈ 'आर'<sup>n</sup>; 'बाहर' ई ∈ 'आर'<sup>n×n</sup>) | ||
Line 93: | Line 91: | ||
एम := के+1 | एम := के+1 | ||
'के लिए' i := k+2 'to' n 'do' | 'के लिए' i := k+2 'to' n 'do' | ||
' | 'यदि' │S<sub>''ki''</sub>│ > │S<sub>''km''</sub>│ फिर ''एम'' := ''आई'' एंडिफ | ||
अंत के लिए | अंत के लिए | ||
वापसी ''एम'' | वापसी ''एम'' | ||
एंडफंक | एंडफंक | ||
प्रक्रिया अद्यतन(''k'' ∈ N; ''t'' ∈ R) ! ''अद्यतन ई<sub>k</sub> और इसकी स्थिति | प्रक्रिया अद्यतन(''k'' ∈ N; ''t'' ∈ R) ! ''अद्यतन ई<sub>k</sub> और इसकी स्थिति'' | ||
य := ई<sub>''k''</sub>; यह है<sub>''k''</sub> := y+t | य := ई<sub>''k''</sub>; यह है<sub>''k''</sub> := y+t | ||
' | 'यदि' बदल गया<sub>''k''</sub> और (y=e<sub>''k''</sub>) फिर ''बदल गया''<sub>''k''</sub> := असत्य; राज्य := राज्य−1 | ||
'एल्सिफ़' (नहीं बदला गया<sub>''k''</sub>) और (y≠e<sub>''k''</sub>) फिर ''बदल गया''<sub>''k''</sub> := सत्य; राज्य := राज्य+1 | 'एल्सिफ़' (नहीं बदला गया<sub>''k''</sub>) और (y≠e<sub>''k''</sub>) फिर ''बदल गया''<sub>''k''</sub> := सत्य; राज्य := राज्य+1 | ||
' | 'यदि अंत' | ||
'एंडप्रोक' | 'एंडप्रोक' | ||
Line 112: | Line 110: | ||
एंडप्रोक | एंडप्रोक | ||
! ''init e, E, और arrays ind, परिवर्तित' | ! ''init e, E, और arrays ind, परिवर्तित''' | ||
''ई'' := ''मैं''; ''स्थिति'' := ''एन'' | ''ई'' := ''मैं''; ''स्थिति'' := ''एन'' | ||
''k'' के लिए := 1 से ''n'' तक ''ind'' करें<sub>''k''</sub> := मैक्सिंड(के); इ<sub>''k''</sub> := एस<sub>''kk''</sub>; बदला हुआ<sub>''k''</sub> :=सच्चा अंत | ''k'' के लिए := 1 से ''n'' तक ''ind'' करें<sub>''k''</sub> := मैक्सिंड(के); इ<sub>''k''</sub> := एस<sub>''kk''</sub>; बदला हुआ<sub>''k''</sub> :=सच्चा अंत | ||
Line 118: | Line 116: | ||
''एम'' := 1 ! ''धुरी पी का सूचकांक (के,एल) ढूंढें'' | ''एम'' := 1 ! ''धुरी पी का सूचकांक (के,एल) ढूंढें'' | ||
''k'' के लिए := 2 से ''n''−1 करें | ''k'' के लिए := 2 से ''n''−1 करें | ||
यदि │''एस''<sub>''k'' ''ind''<sub>''k''</sub></sub>│ > │S<sub>''m'' ''ind''<sub>''m''</sub></sub>│ फिर ''m'' := ''k'' एंडिफ़ | |||
अंत के लिए | अंत के लिए | ||
''k'' := ''m''; ''एल'' := ''इंड''<sub>''m''</sub>; पी := एस<sub>''kl''</sub> | ''k'' := ''m''; ''एल'' := ''इंड''<sub>''m''</sub>; पी := एस<sub>''kl''</sub> | ||
! सी = कॉस φ, एस = पाप φ की गणना करें | ! सी = कॉस φ, एस = पाप φ की गणना करें | ||
और := (ई<sub>''l''</sub>−और<sub>''k''</sub>)/2; d := │y│+√(p<sup>2</sup>+y<sup>2</sup>) | और := (ई<sub>''l''</sub>−और<sub>''k''</sub>)/2; d := │y│+√(p<sup>2</sup>+y<sup>2</sup>) | ||
आर�:= √(पी<sup>2</sup>+डी<sup>2</sup>); सी := डी/आर; एस := पी/आर; टी := पी<sup>2</sup>/d | |||
'यदि' y<0 'तब' | 'यदि' y<0 'तब' ss:= −s; tt:= −t 'endif' | ||
एस<sub>''kl''</sub> := 0.0; अद्यतन(k,−t); अद्यतन(एल,टी) | एस<sub>''kl''</sub> := 0.0; अद्यतन(k,−t); अद्यतन(एल,टी) | ||
! पंक्तियों और स्तंभों को k और l घुमाएँ | ! पंक्तियों और स्तंभों को k और l घुमाएँ | ||
'के लिए' i := 1 'से' k−1 'do' घुमाएँ(i,k,i,l) 'endfor' | 'के लिए' i := 1 'से' k−1 'do' घुमाएँ(i,k,i,l) 'endfor' | ||
'के लिए' i := k+1 'से' l−1 'do' घुमाएँ(k,i,i,l) 'endfor' | 'के लिए' i':= k+1 'से' l−1 'do' घुमाएँ(k,i,i,l) 'endfor' | ||
'के लिए' | 'के लिए' i�:= l+1 'to' n 'do' रोटेट(k,i,l,i) 'endfor' | ||
'के लिए' | ! eigenvectors घुमाएँ | ||
'के लिए' मैं�:= 1 'से' और 'करें' | |||
┌ <sub> </sub>┐ ┌ ┐┌ <sub> </sub>┐ | ┌ <sub> </sub>┐ ┌ ┐┌ <sub> </sub>┐ | ||
│E<sub>''ik''</sub>│ │c −s││E<sub>''ik''</sub>│ | │E<sub>''ik''</sub>│ │c −s││E<sub>''ik''</sub>│ | ||
Line 138: | Line 137: | ||
└ <sub> </sub>┘ └ ┘└ <sub> </sub>┘ | └ <sub> </sub>┘ └ ┘└ <sub> </sub>┘ | ||
अंत के लिए | अंत के लिए | ||
! '' सभी संभावित रूप से परिवर्तित इंडस्ट्रीज़ को अपडेट करें<sub>i</sub>'for' i := 1 'to' n 'do' ind<sub>''i''< | ! '' सभी संभावित रूप से परिवर्तित इंडस्ट्रीज़ को अपडेट करें<sub>i</sub>'for' i := 1 'to' n 'do' ind<sub>''i''<:= मैक्सइंड(i) 'एंडफॉर''' | ||
'कुंडली' | 'कुंडली' | ||
'एंडप्रोक' | 'एंडप्रोक' | ||
Line 154: | Line 153: | ||
'''endfor''' | '''endfor''' | ||
3. The | 3. The आइजेनवैल्यू are not necessarily in descending order. This can be achieved by a simple sorting algorithm. | ||
'''for''' ''k'' := 1 '''to''' ''n''−1 '''do''' | '''for''' ''k'' := 1 '''to''' ''n''−1 '''do''' | ||
Line 173: | Line 172: | ||
5. When implementing the algorithm, the part specified using matrix notation must be performed simultaneously. | 5. When implementing the algorithm, the part specified using matrix notation must be performed simultaneously. | ||
6. This implementation does not correctly account for the case in which one dimension is an independent subspace. For example, if given a diagonal matrix, the above implementation will never terminate, as none of the | 6. This implementation does not correctly account for the case in which one dimension is an independent subspace. For example, if given a diagonal matrix, the above implementation will never terminate, as none of the आइजेनवैल्यू will change. Hence, in real implementations, extra logic must be added to account for this case. | ||
=== उदाहरण === | === उदाहरण === | ||
माना कि | |||
<math> | <math> | ||
S = \begin{pmatrix} 4 & -30 & 60 & -35 \\ -30 & 300 & -675 & 420 \\ 60 & -675 & 1620 & -1050 \\ -35 & 420 & -1050 & 700 \end{pmatrix} | S = \begin{pmatrix} 4 & -30 & 60 & -35 \\ -30 & 300 & -675 & 420 \\ 60 & -675 & 1620 & -1050 \\ -35 & 420 & -1050 & 700 \end{pmatrix} | ||
</math> | </math> | ||
इसके पश्चात जैकोबी 3 स्वीप (19 पुनरावृत्तियों) के बाद निम्नलिखित आइजेनवैल्यू और eigenvectors का उत्पादन करता है: | |||
<math> | <math> | ||
Line 219: | Line 218: | ||
== वास्तविक सममित आव्यूहों के लिए अनुप्रयोग == | == वास्तविक सममित आव्यूहों के लिए अनुप्रयोग == | ||
जब एक सममित मैट्रिक्स के | जब एक सममित मैट्रिक्स के आइजेनवैल्यू (और eigenvectors) ज्ञात होते हैं, तो निम्नलिखित | ||
मूल्यों की गणना आसानी से की जाती है। | मूल्यों की गणना आसानी से की जाती है। | ||
;एकवचन मान | ;एकवचन मान | ||
:एक (वर्ग) मैट्रिक्स का एकवचन मान <math>A</math> के (गैर-नकारात्मक) | :एक (वर्ग) मैट्रिक्स का एकवचन मान <math>A</math> के (गैर-नकारात्मक) आइजेनवैल्यू के वर्गमूल हैं <math> A^T A </math>. सममित मैट्रिक्स के मामले में <math>S</math> हमारे पास है <math> S^T S = S^2 </math>, इसलिए के विलक्षण मूल्य <math>S</math> के आइजेनवैल्यू के पूर्ण मूल्य हैं <math>S</math> | ||
;2-मानदंड और वर्णक्रमीय त्रिज्या | ;2-मानदंड और वर्णक्रमीय त्रिज्या | ||
:मैट्रिक्स ए का 2-मानदंड यूक्लिडियन वेक्टरनॉर्म पर आधारित मानदंड है; यानी सबसे बड़ा मूल्य <math> \| A x\|_2 </math> जब x सभी सदिशों से होकर गुजरता है <math> \|x\|_2 = 1 </math>. यह का सबसे बड़ा एकल मूल्य है <math>A</math>. एक सममित मैट्रिक्स के मामले में यह इसके eigenvectors का सबसे बड़ा निरपेक्ष मान है और इस प्रकार इसके वर्णक्रमीय त्रिज्या के बराबर है। | :मैट्रिक्स ए का 2-मानदंड यूक्लिडियन वेक्टरनॉर्म पर आधारित मानदंड है; यानी सबसे बड़ा मूल्य <math> \| A x\|_2 </math> जब x सभी सदिशों से होकर गुजरता है <math> \|x\|_2 = 1 </math>. यह का सबसे बड़ा एकल मूल्य है <math>A</math>. एक सममित मैट्रिक्स के मामले में यह इसके eigenvectors का सबसे बड़ा निरपेक्ष मान है और इस प्रकार इसके वर्णक्रमीय त्रिज्या के बराबर है। | ||
Line 231: | Line 230: | ||
;पद | ;पद | ||
:एक मैट्रिक्स <math>A</math> रैंक है <math>r</math> | :एक मैट्रिक्स <math>A</math> रैंक है <math>r</math> यदि यह है <math>r</math> जो स्तंभ रैखिक रूप से स्वतंत्र होते हैं जबकि शेष स्तंभ इन पर रैखिक रूप से निर्भर होते हैं। समान रूप से, <math>r</math> की सीमा का आयाम है<math>A</math>. इसके अतिरिक्त यह शून्येतर एकवचन मानों की संख्या है। | ||
:एक सममित मैट्रिक्स के मामले में r गैर-शून्य | :एक सममित मैट्रिक्स के मामले में r गैर-शून्य आइजेनवैल्यू की संख्या है। दुर्भाग्य से पूर्णांकन त्रुटियों के कारण शून्य आइजेनवैल्यू का संख्यात्मक सन्निकटन शून्य नहीं हो सकता है (यह भी हो सकता है कि एक संख्यात्मक सन्निकटन शून्य हो जबकि वास्तविक मान शून्य न हो)। इस प्रकार कोई केवल यह निर्णय लेकर संख्यात्मक रैंक की गणना कर सकता है कि कौन सा स्वदेशी मान शून्य के काफी करीब है। | ||
;छद्म-उलटा | ;छद्म-उलटा | ||
:मैट्रिक्स का छद्म व्युत्क्रम <math>A</math> अद्वितीय मैट्रिक्स है <math> X = A^+ </math> जिसके लिए <math>AX</math> और <math>XA</math> सममित हैं और जिसके लिए <math>AXA = A, XAX = X</math> धारण करता है. | :मैट्रिक्स का छद्म व्युत्क्रम <math>A</math> अद्वितीय मैट्रिक्स है <math> X = A^+ </math> जिसके लिए <math>AX</math> और <math>XA</math> सममित हैं और जिसके लिए <math>AXA = A, XAX = X</math> धारण करता है. यदि <math>A</math> तो इसके पश्चात, यह एकवचन नहीं है <math> A^+ = A^{-1} </math>. | ||
:जब प्रक्रिया जैकोबी (एस, ई, ई) कहा जाता है, तो संबंध <math> S = E^T \mbox{Diag} (e) E </math> वह स्थान रखता है जहां Diag(e) विकर्ण पर वेक्टर e के साथ विकर्ण मैट्रिक्स को दर्शाता है। | :जब प्रक्रिया जैकोबी (एस, ई, ई) कहा जाता है, तो संबंध <math> S = E^T \mbox{Diag} (e) E </math> वह स्थान रखता है जहां Diag(e) विकर्ण पर वेक्टर e के साथ विकर्ण मैट्रिक्स को दर्शाता है। माना कि <math> e^+ </math> वेक्टर को निरूपित करें जहां <math> e_i </math> द्वारा प्रतिस्थापित किया जाता है <math> 1/e_i </math> यदि <math> e_i \le 0 </math> और 0 से यदि <math> e_i </math> (संख्यात्मक रूप से करीब) शून्य है। चूँकि मैट्रिक्स E ऑर्थोगोनल है, इसलिए यह इस प्रकार है कि S का छद्म-व्युत्क्रम दिया गया है <math> S^+ = E^T \mbox{Diag} (e^+) E </math>. | ||
;न्यूनतम वर्ग समाधान | ;न्यूनतम वर्ग समाधान | ||
:यदि मैट्रिक्स <math>A</math> पूर्ण रैंक नहीं है, रैखिक प्रणाली का कोई समाधान नहीं हो सकता है <math>Ax=b</math>. | :यदि मैट्रिक्स <math>A</math> पूर्ण रैंक नहीं है, रैखिक प्रणाली का कोई समाधान नहीं हो सकता है <math>Ax=b</math>. जबकि कोई इसके लिए वेक्टर x की तलाश कर सकता है <math> \| Ax - b \|_2 </math> न्यूनतम है. समाधान है <math> x = A^+ b </math>. सममित मैट्रिक्स S के मामले में, पहले की तरह, एक के पास है <math> x = S^+ b = E^T \mbox{Diag} (e^+) E b </math>. | ||
;मैट्रिक्स घातांक | ;मैट्रिक्स घातांक | ||
Line 245: | Line 244: | ||
;रैखिक विभेदक समीकरण | ;रैखिक विभेदक समीकरण | ||
:विभेदक समीकरण <math>x'=Ax, x(0) =a</math> समाधान है <math>x(t)=\exp(tA)</math>. एक सममित मैट्रिक्स के लिए <math>S</math>, यह इस प्रकार है कि <math> x(t) = E^T \mbox{Diag} (\exp t e) E a </math>. | :विभेदक समीकरण <math>x'=Ax, x(0) =a</math> समाधान है <math>x(t)=\exp(tA)</math>. एक सममित मैट्रिक्स के लिए <math>S</math>, यह इस प्रकार है कि <math> x(t) = E^T \mbox{Diag} (\exp t e) E a </math>. यदि <math> a = \sum_{i = 1}^n a_i E_i </math> का विस्तार है <math>a</math> के eigenvectors द्वारा <math>S</math>, तब <math> x(t) = \sum_{i = 1}^n a_i \exp(t e_i) E_i </math>. | ||
: | :माना कि <math> W^s </math> के eigenvectors द्वारा फैलाया गया सदिश समष्टि हो <math>S</math> जो एक नकारात्मक eigenvalue के अनुरूप है और <math> W^u </math> सकारात्मक आइजेनवैल्यू के लिए अनुरूप। यदि <math> a \in W^s </math> तब <math> \mbox{lim}_{t \rightarrow \infty} x(t) = 0 </math>; यानी संतुलन बिंदु 0 आकर्षक है <math>x(t)</math>. यदि <math> a \in W^u </math> तब <math> \mbox{lim}_{t \rightarrow \infty} x(t) = \infty </math>; अर्थात् 0 प्रतिकारक है <math>x(t)</math>. <math> W^s </math> और <math> W^u </math> के लिए स्थिर और अस्थिर मैनिफोल्ड कहलाते हैं <math>S</math>. यदि <math>a</math> दोनों रूपों में घटक होते हैं, तो एक घटक आकर्षित होता है और एक घटक विकर्षित होता है। इस तरह <math>x(t)</math> दृष्टिकोण <math> W^u </math> जैसा <math> t \to \infty </math>. | ||
== सामान्यीकरण == | == सामान्यीकरण == | ||
Line 252: | Line 251: | ||
जैकोबी विधि को जटिल हर्मिटियन मैट्रिक्स, सामान्य गैर-सममित वास्तविक और जटिल मैट्रिक्स के साथ-साथ ब्लॉक मैट्रिक्स के लिए जैकोबी विधि में सामान्यीकृत किया गया है। | जैकोबी विधि को जटिल हर्मिटियन मैट्रिक्स, सामान्य गैर-सममित वास्तविक और जटिल मैट्रिक्स के साथ-साथ ब्लॉक मैट्रिक्स के लिए जैकोबी विधि में सामान्यीकृत किया गया है। | ||
चूँकि वास्तविक मैट्रिक्स के एकवचन मान सममित मैट्रिक्स के | चूँकि वास्तविक मैट्रिक्स के एकवचन मान सममित मैट्रिक्स के आइजेनवैल्यू के वर्गमूल होते हैं <math> S = A^T A</math> इसका उपयोग इन मानों की गणना के लिए भी किया जा सकता है। इस मामले के लिए, विधि को इस तरह से संशोधित किया गया है कि एस की स्पष्ट रूप से गणना नहीं की जानी चाहिए, जिससे राउंड-ऑफ त्रुटियों का खतरा कम हो जाता है। ध्यान दें कि <math> J S J^T = J A^T A J^T = J A^T J^T J A J^T = B^T B </math> साथ <math> B \, := J A J^T </math> . | ||
जैकोबी पद्धति भी समानता के लिए उपयुक्त है। | जैकोबी पद्धति भी समानता के लिए उपयुक्त है। |
Revision as of 21:11, 5 August 2023
संख्यात्मक रैखिक बीजगणित में जैकोबी आइजेनवैल्यू एल्गोरिथ्म वास्तविक संख्या सममित मैट्रिक्स (एक प्रक्रिया जिसे मैट्रिक्स डायगोनलाइज़ेशन के रूप में जाना जाता है) के आइजेनवैल्यू और आइजन्वेक्टर की गणना के लिए पुनरावृत्त विधि है। इसका नाम कार्ल गुस्ताव जैकब जैकोबी के नाम पर रखा गया है जिन्होंने पहली बार सन 1846 में इस पद्धति का प्रस्ताव रखा था।[1] लेकिन सन 1950 के दशक में कंप्यूटर के आगमन के साथ ही इसका व्यापक रूप से उपयोग किया जाने लगा।[2]
विवरण
माना कि सममित मैट्रिक्स और , गिवेंस रोटेशन मैट्रिक्स हो। तब:
सममित और समान (रैखिक बीजगणित) है।
अन्य, प्रविष्टियाँ हैं:
जहाँ और
जब से का अर्थ ऑर्थोगोनल है, और समान फ्रोबेनियस मानदंड (सभी घटकों के वर्गों का वर्गमूल योग) है जबकि हम चुन सकते हैं तथा यह इस प्रकार है कि , इस स्थिति में विकर्ण पर वर्गों का योग बड़ा है:
इसे 0 के बराबर सेट करें और पुनर्व्यवस्थित करें:
यदि
इस प्रभाव को अनुकूलित करने के लिए, Sij सबसे बड़े निरपेक्ष मान वाला ऑफ-विकर्ण तत्व होना चाहिए जिसे धुरी कहा जाता है।
जैकोबी आइजेनवैल्यू विधि जैकोबी को तब तक बार-बार घुमाती है जब तक कि मैट्रिक्स लगभग विकर्ण न हो जाए। इसके पश्चात विकर्ण में तत्व S के (वास्तविक) स्वदेशी मानों के सन्निकटन हैं।
अभिसरण
यदि परिभाषा के अनुसार धुरी तत्व के लिए है। माना कि की सभी ऑफ-विकर्ण प्रविष्टियों के वर्गों का योग निरूपित करें। जब से , निश्चित है, हमारे पास ऑफ-विकर्ण तत्व या है। अब । यह संकेत या करता है;
अर्थात् जैकोबी घूर्णन का क्रम एक कारक द्वारा कम से कम रैखिक रूप से विकर्ण मैट्रिक्स के लिए परिवर्तित होता है।
की एक संख्या जैकोबी रोटेशन को स्वीप कहा जाता है; माना कि परिणाम निरूपित करें। पिछला अनुमान उत्पन्न करता है।
- ;
अर्थात् स्वीप का क्रम कारक ≈ के साथ कम से कम रैखिक रूप से परिवर्तित होता है
जबकि अर्नोल्ड शॉनहेज का निम्नलिखित परिणाम[3] स्थानीय रूप से द्विघात अभिसरण उत्पन्न करता है। इस प्रयोजन के लिए मान लीजिए कि S के पास m विशिष्ट आइजेनवैल्यू बहुलता के साथ हैं और मान लीजिए कि d > 0 दो अलग-अलग आइजेनवैल्यू की सबसे छोटी दूरी है। आइए हम कुछ नंबर को प्रयोग करें
जैकोबी शॉनहेज-स्वीप रोटेशन करता है। यदि तब परिणाम को दर्शाता है
- .
इस प्रकार अभिसरण शीघ्र ही द्विघात हो जाता है
लागत
प्रत्येक जैकोबी घूर्णन O(n) चरणों में किया जा सकता है जब धुरी तत्व p ज्ञात हो। जबकि p की खोज के लिए सभी N≈1/2 n2 ऑफ-विकर्ण तत्व के निरीक्षण की आवश्यकता होती है। यदि हम एक अतिरिक्त सूचकांक सरणी प्रस्तुत करते हैं तो हम इसे O(n) जटिलता तक भी कम कर सकते हैं उस संपत्ति के साथ वर्तमान S की पंक्ति i, (i = 1, ..., n − 1) में सबसे बड़े तत्व का सूचकांक है। इसके पश्चात धुरी के सूचकांक (k, l) जोड़े में से एक होना चाहिए . इसके अतिरिक्त सूचकांक सरणी का अद्यतनीकरण O(n) औसत-केस जटिलता में किया जा सकता है: सबसे अद्यतन पंक्तियों k और l में अधिकतम प्रविष्टि O(n) चरणों में पाई जा सकती है। अन्य पंक्तियों में केवल कॉलम k और l में प्रविष्टियाँ परिवर्तित होता हैं। इन पंक्तियों पर लूपिंग यदि न तो k है और न ही l, यह पुराने अधिकतम की तुलना करने के लिए पर्याप्त है नई प्रविष्टियों और अद्यतन के लिए यदि आवश्यक है। यदि k या l के बराबर होना चाहिए और अद्यतन के समय संबंधित प्रविष्टि कम हो गई है एवं अधिकतम पंक्ति i को O(n) जटिलता में स्क्रैच से पाया जाना चाहिए। जबकि ऐसा प्रति रोटेशन औसतन केवल एक बार होगा। इस प्रकार प्रत्येक रोटेशन में O(n) और एक स्वीप O(n)3 होता है) औसत-केस जटिलता जो मैट्रिक्स गुणन के सामान है। इसके अतिरिक्त प्रक्रिया आरम्भ होने से पहले आरंभ किया जाना चाहिए, जिसे n2 चरणों में किया जा सकता है।
सामान्य रूप से जैकोबी पद्धति कम संख्या में स्वीप के बाद संख्यात्मक परिशुद्धता के भीतर परिवर्तित हो जाती है। ध्यान दें कि एकाधिक आइजेनवैल्यू पुनरावृत्तियों की संख्या को कम कर देते हैं।
एल्गोरिथम
निम्नलिखित एल्गोरिदम गणित जैसे नोटेशन में जैकोबी पद्धति का विवरण है।
यह वेक्टर e की गणना करता है जिसमें आइजेनवैल्यू और मैट्रिक्स E होता है जिसमें संबंधित आइजेनवेक्टर होते हैं; वह है, एक आइजेनवैल्यू और स्तंभ है के लिए ऑर्थोनॉर्मल आइजेनवेक्टर , I = 1, ..., n।
'प्रक्रिया' जैकोबी(एस ∈ 'आर'n×n; 'बाहर' ई ∈ 'आर'n; 'बाहर' ई ∈ 'आर'n×n) 'वर' मैं, के, एल, एम, अवस्था ∈ 'एन' एस, सी, टी, पी, वाई, डी, आर ∈ 'आर' इंडस्ट्रीज़ ∈ 'एन'n परिवर्तित ∈ 'एल'n 'फ़ंक्शन' मैक्सिंड(k ∈ 'N') ∈ 'N' ! पंक्ति k में सबसे बड़े ऑफ-विकर्ण तत्व का सूचकांक एम := के+1 'के लिए' i := k+2 'to' n 'do' 'यदि' │Ski│ > │Skm│ फिर एम := आई एंडिफ अंत के लिए वापसी एम एंडफंक प्रक्रिया अद्यतन(k ∈ N; t ∈ R) ! अद्यतन ईk और इसकी स्थिति य := ईk; यह हैk := y+t 'यदि' बदल गयाk और (y=ek) फिर बदल गयाk := असत्य; राज्य := राज्य−1 'एल्सिफ़' (नहीं बदला गयाk) और (y≠ek) फिर बदल गयाk := सत्य; राज्य := राज्य+1 'यदि अंत' 'एंडप्रोक' 'प्रक्रिया' घुमाएँ(k,l,i,j ∈ 'N') ! S का घूर्णन करेंij, एसkl┌ ┐ ┌ ┐┌ ┐ │Skl│ │c −s││Skl│ │ │ := │ ││ │ │Sij│ │s c││Sij│ └ ┘ └ ┘└ ┘ एंडप्रोक ! init e, E, और arrays ind, परिवर्तित' ई := मैं; स्थिति := एन k के लिए := 1 से n तक ind करेंk := मैक्सिंड(के); इk := एसkk; बदला हुआk :=सच्चा अंत जबकि state≠0 करो ! अगला रोटेशन एम := 1 ! धुरी पी का सूचकांक (के,एल) ढूंढें k के लिए := 2 से n−1 करें यदि │एसk indk│ > │Sm indm│ फिर m := k एंडिफ़ अंत के लिए k := m; एल := इंडm; पी := एसkl
! सी = कॉस φ, एस = पाप φ की गणना करें
और := (ईl−औरk)/2; d := │y│+√(p2+y2) आर�:= √(पी2+डी2); सी := डी/आर; एस := पी/आर; टी := पी2/d 'यदि' y<0 'तब' ss:= −s; tt:= −t 'endif' एसkl := 0.0; अद्यतन(k,−t); अद्यतन(एल,टी) ! पंक्तियों और स्तंभों को k और l घुमाएँ 'के लिए' i := 1 'से' k−1 'do' घुमाएँ(i,k,i,l) 'endfor' 'के लिए' i':= k+1 'से' l−1 'do' घुमाएँ(k,i,i,l) 'endfor' 'के लिए' i�:= l+1 'to' n 'do' रोटेट(k,i,l,i) 'endfor' ! eigenvectors घुमाएँ 'के लिए' मैं�:= 1 'से' और 'करें' ┌ ┐ ┌ ┐┌ ┐ │Eik│ │c −s││Eik│ │ │ := │ ││ │ │Eil│ │s c││Eil│ └ ┘ └ ┘└ ┘ अंत के लिए ! सभी संभावित रूप से परिवर्तित इंडस्ट्रीज़ को अपडेट करेंi'for' i := 1 'to' n 'do' indi<:= मैक्सइंड(i) 'एंडफॉर' 'कुंडली' 'एंडप्रोक'
टिप्पणियाँ
1. The logical array changed holds the status of each eigenvalue. If the numerical value of or changes during an iteration, the corresponding component of changed is set to true, otherwise to false. The integer state counts the number of components of changed which have the value true. Iteration stops as soon as state = 0. This means that none of the approximations has recently changed its value and thus it is not very likely that this will happen if iteration continues. Here it is assumed that floating point operations are optimally rounded to the nearest floating point number.
2. The upper triangle of the matrix S is destroyed while the lower triangle and the diagonal are unchanged. Thus it is possible to restore S if necessary according to
for k := 1 to n−1 do ! restore matrix S for l := k+1 to n do Skl := Slk endfor endfor
3. The आइजेनवैल्यू are not necessarily in descending order. This can be achieved by a simple sorting algorithm.
for k := 1 to n−1 do m := k for l := k+1 to n do if el > em then m := l endif endfor if k ≠ m then swap em,ek swap Em,Ek endif endfor
4. The algorithm is written using matrix notation (1 based arrays instead of 0 based).
5. When implementing the algorithm, the part specified using matrix notation must be performed simultaneously.
6. This implementation does not correctly account for the case in which one dimension is an independent subspace. For example, if given a diagonal matrix, the above implementation will never terminate, as none of the आइजेनवैल्यू will change. Hence, in real implementations, extra logic must be added to account for this case.
उदाहरण
माना कि
इसके पश्चात जैकोबी 3 स्वीप (19 पुनरावृत्तियों) के बाद निम्नलिखित आइजेनवैल्यू और eigenvectors का उत्पादन करता है:
वास्तविक सममित आव्यूहों के लिए अनुप्रयोग
जब एक सममित मैट्रिक्स के आइजेनवैल्यू (और eigenvectors) ज्ञात होते हैं, तो निम्नलिखित मूल्यों की गणना आसानी से की जाती है।
- एकवचन मान
- एक (वर्ग) मैट्रिक्स का एकवचन मान के (गैर-नकारात्मक) आइजेनवैल्यू के वर्गमूल हैं . सममित मैट्रिक्स के मामले में हमारे पास है , इसलिए के विलक्षण मूल्य के आइजेनवैल्यू के पूर्ण मूल्य हैं
- 2-मानदंड और वर्णक्रमीय त्रिज्या
- मैट्रिक्स ए का 2-मानदंड यूक्लिडियन वेक्टरनॉर्म पर आधारित मानदंड है; यानी सबसे बड़ा मूल्य जब x सभी सदिशों से होकर गुजरता है . यह का सबसे बड़ा एकल मूल्य है . एक सममित मैट्रिक्स के मामले में यह इसके eigenvectors का सबसे बड़ा निरपेक्ष मान है और इस प्रकार इसके वर्णक्रमीय त्रिज्या के बराबर है।
- शर्त संख्या
- एक गैर-एकवचन मैट्रिक्स की स्थिति संख्या परिभाषित किया जाता है . एक सममित मैट्रिक्स के मामले में यह सबसे बड़े और सबसे छोटे eigenvalue के भागफल का निरपेक्ष मान है। बड़ी स्थिति संख्याओं वाले मैट्रिक्स संख्यात्मक रूप से अस्थिर परिणाम पैदा कर सकते हैं: छोटी गड़बड़ी के परिणामस्वरूप बड़ी त्रुटियां हो सकती हैं। हिल्बर्ट मैट्रिक्स सबसे प्रसिद्ध खराब स्थिति वाले मैट्रिक्स हैं। उदाहरण के लिए, चौथे क्रम के हिल्बर्ट मैट्रिक्स की स्थिति 15514 है, जबकि क्रम 8 के लिए यह 2.7 × 10 है8.
- पद
- एक मैट्रिक्स रैंक है यदि यह है जो स्तंभ रैखिक रूप से स्वतंत्र होते हैं जबकि शेष स्तंभ इन पर रैखिक रूप से निर्भर होते हैं। समान रूप से, की सीमा का आयाम है. इसके अतिरिक्त यह शून्येतर एकवचन मानों की संख्या है।
- एक सममित मैट्रिक्स के मामले में r गैर-शून्य आइजेनवैल्यू की संख्या है। दुर्भाग्य से पूर्णांकन त्रुटियों के कारण शून्य आइजेनवैल्यू का संख्यात्मक सन्निकटन शून्य नहीं हो सकता है (यह भी हो सकता है कि एक संख्यात्मक सन्निकटन शून्य हो जबकि वास्तविक मान शून्य न हो)। इस प्रकार कोई केवल यह निर्णय लेकर संख्यात्मक रैंक की गणना कर सकता है कि कौन सा स्वदेशी मान शून्य के काफी करीब है।
- छद्म-उलटा
- मैट्रिक्स का छद्म व्युत्क्रम अद्वितीय मैट्रिक्स है जिसके लिए और सममित हैं और जिसके लिए धारण करता है. यदि तो इसके पश्चात, यह एकवचन नहीं है .
- जब प्रक्रिया जैकोबी (एस, ई, ई) कहा जाता है, तो संबंध वह स्थान रखता है जहां Diag(e) विकर्ण पर वेक्टर e के साथ विकर्ण मैट्रिक्स को दर्शाता है। माना कि वेक्टर को निरूपित करें जहां द्वारा प्रतिस्थापित किया जाता है यदि और 0 से यदि (संख्यात्मक रूप से करीब) शून्य है। चूँकि मैट्रिक्स E ऑर्थोगोनल है, इसलिए यह इस प्रकार है कि S का छद्म-व्युत्क्रम दिया गया है .
- न्यूनतम वर्ग समाधान
- यदि मैट्रिक्स पूर्ण रैंक नहीं है, रैखिक प्रणाली का कोई समाधान नहीं हो सकता है . जबकि कोई इसके लिए वेक्टर x की तलाश कर सकता है न्यूनतम है. समाधान है . सममित मैट्रिक्स S के मामले में, पहले की तरह, एक के पास है .
- मैट्रिक्स घातांक
- से एक पाता है जहां ऍक्स्प वेक्टर कहां है द्वारा प्रतिस्थापित किया जाता है . उसी तरह से, किसी भी (विश्लेषणात्मक) फ़ंक्शन के लिए स्पष्ट तरीके से गणना की जा सकती है .
- रैखिक विभेदक समीकरण
- विभेदक समीकरण समाधान है . एक सममित मैट्रिक्स के लिए , यह इस प्रकार है कि . यदि का विस्तार है के eigenvectors द्वारा , तब .
- माना कि के eigenvectors द्वारा फैलाया गया सदिश समष्टि हो जो एक नकारात्मक eigenvalue के अनुरूप है और सकारात्मक आइजेनवैल्यू के लिए अनुरूप। यदि तब ; यानी संतुलन बिंदु 0 आकर्षक है . यदि तब ; अर्थात् 0 प्रतिकारक है . और के लिए स्थिर और अस्थिर मैनिफोल्ड कहलाते हैं . यदि दोनों रूपों में घटक होते हैं, तो एक घटक आकर्षित होता है और एक घटक विकर्षित होता है। इस तरह दृष्टिकोण जैसा .
सामान्यीकरण
जैकोबी विधि को जटिल हर्मिटियन मैट्रिक्स, सामान्य गैर-सममित वास्तविक और जटिल मैट्रिक्स के साथ-साथ ब्लॉक मैट्रिक्स के लिए जैकोबी विधि में सामान्यीकृत किया गया है।
चूँकि वास्तविक मैट्रिक्स के एकवचन मान सममित मैट्रिक्स के आइजेनवैल्यू के वर्गमूल होते हैं इसका उपयोग इन मानों की गणना के लिए भी किया जा सकता है। इस मामले के लिए, विधि को इस तरह से संशोधित किया गया है कि एस की स्पष्ट रूप से गणना नहीं की जानी चाहिए, जिससे राउंड-ऑफ त्रुटियों का खतरा कम हो जाता है। ध्यान दें कि साथ .
जैकोबी पद्धति भी समानता के लिए उपयुक्त है।
संदर्भ
- ↑ Jacobi, C.G.J. (1846). "Über ein leichtes Verfahren, die in der Theorie der Säkularstörungen vorkommenden Gleichungen numerisch aufzulösen". Crelle's Journal (in German). 1846 (30): 51–94. doi:10.1515/crll.1846.30.51.
{{cite journal}}
: CS1 maint: unrecognized language (link) - ↑ Golub, G.H.; van der Vorst, H.A. (2000). "Eigenvalue computation in the 20th century". Journal of Computational and Applied Mathematics. 123 (1–2): 35–65. doi:10.1016/S0377-0427(00)00413-1.
- ↑ Schönhage, A. (1964). "Zur quadratischen Konvergenz des Jacobi-Verfahrens". Numerische Mathematik (in German). 6 (1): 410–412. doi:10.1007/BF01386091. MR 0174171.
{{cite journal}}
: CS1 maint: unrecognized language (link)
अग्रिम पठन
- Press, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007), "Section 11.1. Jacobi Transformations of a Symmetric Matrix", Numerical Recipes: The Art of Scientific Computing (3rd ed.), New York: Cambridge University Press, ISBN 978-0-521-88068-8
- Rutishauser, H. (1966). "Handbook Series Linear Algebra: The Jacobi method for real symmetric matrices". Numerische Mathematik. 9 (1): 1–10. doi:10.1007/BF02165223. MR 1553948.
- Sameh, A.H. (1971). "On Jacobi and Jacobi-like algorithms for a parallel computer". Mathematics of Computation. 25 (115): 579–590. doi:10.1090/s0025-5718-1971-0297131-6. JSTOR 2005221. MR 0297131.
- Shroff, Gautam M. (1991). "A parallel algorithm for the eigenvalues and eigenvectors of a general complex matrix". Numerische Mathematik. 58 (1): 779–805. CiteSeerX 10.1.1.134.3566. doi:10.1007/BF01385654. MR 1098865.
- Veselić, K. (1979). "On a class of Jacobi-like procedures for diagonalising arbitrary real matrices". Numerische Mathematik. 33 (2): 157–172. doi:10.1007/BF01399551. MR 0549446.
- Veselić, K.; Wenzel, H. J. (1979). "A quadratically convergent Jacobi-like method for real matrices with complex eigenvalues". Numerische Mathematik. 33 (4): 425–435. doi:10.1007/BF01399324. MR 0553351.
- Yousef Saad: "Revisiting the (block) Jacobi subspace rotation method for the symmetric eigenvalue problem", Numerical Algorithms, vol.92 (2023), pp.917-944. https://doi.org/10.1007/s11075-022-01377-w .