जैकोबी आइजेनवैल्यू एल्गोरिथम: Difference between revisions

From Vigyanwiki
(Created page with "संख्यात्मक रैखिक बीजगणित में, जैकोबी eigenvalue एल्गोरिथ्म एक वास्त...")
 
No edit summary
 
(10 intermediate revisions by 3 users not shown)
Line 1: Line 1:
[[संख्यात्मक रैखिक बीजगणित]] में, जैकोबी [[eigenvalue]] एल्गोरिथ्म एक [[वास्तविक संख्या]] [[सममित मैट्रिक्स]] (एक प्रक्रिया जिसे मैट्रिक्स डायगोनलाइज़ेशन#डायगोनलाइज़ेशन के रूप में जाना जाता है) के आइगेनवैल्यू और [[आइजन्वेक्टर]] की गणना के लिए एक पुनरावृत्त विधि है। इसका नाम [[कार्ल गुस्ताव जैकब जैकोबी]] के नाम पर रखा गया है, जिन्होंने पहली बार 1846 में इस पद्धति का प्रस्ताव रखा था।<ref>{{cite journal
[[संख्यात्मक रैखिक बीजगणित]] में जैकोबी [[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</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</math> सममित और [[समान (रैखिक बीजगणित)]] है।


आगे, <math>S^\prime</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>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>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>  S_{jj} = S_{ii} </math>
:<math> \theta = \frac{\pi} {4}  </math>
:<math> \theta = \frac{\pi} {4}  </math>
इस प्रभाव को अनुकूलित करने के लिए, एस<sub>''ij''</sub> सबसे बड़े निरपेक्ष मान वाला [[ऑफ-विकर्ण तत्व]] होना चाहिए, जिसे धुरी कहा जाता है।
इस प्रभाव को अनुकूलित करने के क्रम में 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> p = S_{kl} </math> पिवोट तत्व है तब परिभाषा के अनुसार  <math> 1 \le i, j \le n, i \ne j</math> के लिए <math> |S_{ij} | \le |p| </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>  (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> .
अर्थात् स्वीप का क्रम कारक ≈<math>  e ^{1 / 2}</math> के साथ कम से कम रैखिक रूप से परिवर्तित होता है


हालाँकि अर्नोल्ड शॉनहेज|शॉनहेज का निम्नलिखित परिणाम<ref>{{cite journal
जबकि अर्नोल्ड शॉनहेज का निम्नलिखित परिणाम<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 विशिष्ट eigenvalues ​​​​हैं <math>  \lambda_1, ... , \lambda_m </math> बहुलता के साथ  <math>  \nu_1, ... , \nu_m </math> और मान लीजिए कि d > 0 दो अलग-अलग eigenvalues ​​​​की सबसे छोटी दूरी है। आइए हम कुछ नंबर पर कॉल करें
}}</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> 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 ज्ञात हो। हालाँकि p की खोज के लिए सभी N≈ के निरीक्षण की आवश्यकता होती है{{sfrac|1|2}} एन<sup>2</sup>ऑफ-विकर्ण तत्व। यदि हम एक अतिरिक्त सूचकांक सरणी पेश करते हैं तो हम इसे O(n) जटिलता तक भी कम कर सकते हैं <math> m_1, \, \dots \, , \, m_{n - 1} </math> उस संपत्ति के साथ <math> m_i </math> वर्तमान एस की पंक्ति 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 कदम.
प्रत्येक जैकोबी घूर्णन 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 चरणों में किया जा सकता है।


आमतौर पर जैकोबी पद्धति कम संख्या में स्वीप के बाद संख्यात्मक परिशुद्धता के भीतर परिवर्तित हो जाती है। ध्यान दें कि एकाधिक eigenvalues ​​​​पुनरावृत्तियों की संख्या को कम कर देते हैं <math>N_S < N</math>.
सामान्य रूप से जैकोबी पद्धति कम संख्या में स्वीप के बाद संख्यात्मक परिशुद्धता के भीतर परिवर्तित हो जाती है। ध्यान दें कि <math>N_S < N</math> एकाधिक आइजेनवैल्यू ​​​​पुनरावृत्तियों की संख्या को कम कर देते हैं।


== एल्गोरिथम ==
== एल्गोरिथम ==


निम्नलिखित एल्गोरिदम गणित जैसे नोटेशन में जैकोबी पद्धति का विवरण है।
निम्नलिखित एल्गोरिदम गणित जैसे नोटेशन में जैकोबी पद्धति का विवरण है।
यह एक वेक्टर e की गणना करता है जिसमें eigenvalues ​​​​और एक मैट्रिक्स E होता है जिसमें संबंधित eigenvectors होते हैं; वह है, <math> e_i </math> एक eigenvalue और स्तंभ है <math> E_i </math> के लिए एक ऑर्थोनॉर्मल आइजेनवेक्टर <math> e_i </math>, मैं = 1, ..., एन।


  'प्रक्रिया' जैकोबी(एस ∈ 'आर'<sup>n×n</sup>; 'बाहर' ∈ 'आर'<sup>n</sup>; 'बाहर' ई ∈ 'आर'<sup>n×n</sup>)
यह वेक्टर e की गणना करता है जिसमें आइजेनवैल्यू ​​​​और मैट्रिक्स E होता है जिसमें संबंधित आइजेनवेक्टर होते हैं; वह है, <math> e_i </math> आइजेनवैल्यू है और स्तंभ <math> E_i </math> के लिए ऑर्थोनॉर्मल आइजेनवेक्टर <math> e_i </math>, I = 1, ..., n है।
   'वर'
 
     मैं, के, एल, एम, अवस्था ∈ 'एन'
  '''procedure''' jacobi(S ∈ '''R'''<sup>n×n</sup>; '''out''' e ∈ '''R'''<sup>n</sup>; out E ∈ '''R'''<sup>n×n</sup>)
     एस, सी, टी, पी, वाई, डी, आर ∈ 'आर'
   '''var'''
     इंडस्ट्रीज़ ∈ 'एन'<sup>n</sup>
     i, k, l, m, state ∈ '''N'''
     परिवर्तित ∈ 'एल'<sup>n</sup>
     s, c, t, p, y, d, r ∈ '''R'''
     ind ∈ '''N'''<sup>n</sup>
     changed ∈ '''L'''<sup>n</sup>
   
   
   'फ़ंक्शन' मैक्सिंड(k ∈ 'N') ∈ 'N' ! पंक्ति k में सबसे बड़े ऑफ-विकर्ण तत्व का सूचकांक
   '''function''' maxind(k ∈ '''N''') ∈ '''N'''! index of largest off-diagonal element in row k
     एम := के+1
     m:= k+1
     'के लिए' i := k+2 'to' n 'do'
     '''for''' i:= k+2 '''to''' n '''do'''
       'अगर' │S<sub>''ki''</sub>│ > │S<sub>''km''</sub>│ फिर ''एम'' := ''आई'' एंडिफ
       if │S<sub>ki</sub>│ > │S<sub>km</sub>│ '''then''' m:= i '''endif'''
     अंत के लिए
     '''endfor'''
     वापसी ''एम''
     '''return''' m
   एंडफंक
   '''endfunc'''
 
   प्रक्रिया अद्यतन(''k'' N; ''t'' R) ! ''अद्यतन ई<sub>k</sub> और इसकी स्थिति
   '''procedure''' update(k ∈ '''N'''; t ∈ '''R''')! update e<sub>k</sub> and its status
     := <sub>''k''</sub>; यह है<sub>''k''</sub> := y+t
     y:= e<sub>k</sub>; e<sub>k</sub>:= y+t
     'अगर' बदल गया<sub>''k''</sub> और (y=e<sub>''k''</sub>) फिर ''बदल गया''<sub>''k''</sub> := असत्य; राज्य := राज्य−1
     '''if''' changedk and (y=e<sub>k</sub>) '''then''' changedk:= false; state:= state−1
     'एल्सिफ़' (नहीं बदला गया<sub>''k''</sub>) और (y≠e<sub>''k''</sub>) फिर ''बदल गया''<sub>''k''</sub> := सत्य; राज्य := राज्य+1
     '''elsif''' (not changedk) and (y≠e<sub>k</sub>) '''then''' changedk:= true; state:= state+1
     'अगर अंत'
     '''endif'''
   'एंडप्रोक'
   '''endproc'''  
 
   'प्रक्रिया' घुमाएँ(k,l,i,j ∈ 'N') ! S का घूर्णन करें<sub>ij</sub>, एस<sub>kl</sub>┌ <sub>  </sub>┐    ┌    ┐┌ <sub>  </sub>┐
   '''procedure''' rotate(k,l,i,j ∈ '''N''')! perform rotation of S<sub>ij</sub>, S<sub>kl</sub>
     │S<sub>''kl''</sub>│    │c  −s││S<sub>''kl''</sub>│
     │S<sub>''kl''</sub>│    │c  −s││S<sub>''kl''</sub>│
     │ <sub>  </sub>│ := │    ││ <sub>  </sub>│
     │ <sub>  </sub>│ := │    ││ <sub>  </sub>│
     │S<sub>''ij''</sub>│    │s  c││S<sub>''ij''</sub>│
     │S<sub>''ij''</sub>│    │s  c││S<sub>''ij''</sub>│
     └ <sub>  </sub>┘    └    ┘└ <sub>  </sub>┘
     └ <sub>  </sub>┘    └    ┘└ <sub>  </sub>┘
   एंडप्रोक
   '''endproc'''
   
   
  ! ''init e, E, और arrays ind, परिवर्तित'
 
   ''ई'' := ''मैं''; ''स्थिति'' := ''एन''
! init e, E, and arrays ind, changed
  ''k'' के लिए := 1 से ''n'' तक ''ind'' करें<sub>''k''</sub> := मैक्सिंड(के); <sub>''k''</sub> := एस<sub>''kk''</sub>; बदला हुआ<sub>''k''</sub> :=सच्चा अंत
   E:= I; state:= n
   जबकि ''state''≠0 करो ! ''अगला रोटेशन''
  '''for''' k:= 1 '''to''' n '''do''' ind<sub>k</sub>:= maxind(k); e<sub>k</sub>:= S<sub>kk</sub>; changedk:= true '''endfor'''
    ''एम'' := 1 ! ''धुरी पी का सूचकांक (के,एल) ढूंढें''
   '''while''' state≠0 '''do'''! next rotation
    ''k'' के लिए := 2 से ''n''−1 करें
    m:= 1! find index (k,l) of pivot p
      अगर │''एस''<sub>''k''&nbsp;''ind''<sub>''k''</sub></sub>│ > │S<sub>''m''&nbsp;''ind''<sub>''m''</sub></sub>│ फिर ''m'' := ''k'' एंडिफ़
    '''for''' k:= 2 '''to''' n−1 '''do'''
    अंत के लिए
      '''if''' │S<sub>k</sub> ind<sub>k</sub>│ > │S<sub>m</sub> indm│ '''then''' m:= k '''endif'''
     ''k'' := ''m''; ''एल'' := ''इंड''<sub>''m''</sub>; पी := एस<sub>''kl''</sub>
     '''endfor'''
! सी = कॉस φ, एस = पाप φ की गणना करें
    k:= m; l:= ind<sub>m</sub>; p:= S<sub>kl</sub>
     और := (ई<sub>''l''</sub>−और<sub>''k''</sub>)/2; d := │y│+√(p<sup>2</sup>+y<sup>2</sup>)
! calculate c = cos φ, s = sin φ
     आर := √(पी<sup>2</sup>+डी<sup>2</sup>); सी := डी/आर; एस := पी/आर; टी := पी<sup>2</sup>/d
     y:= (el−ek)/2; d:= │y│+√(p2+y2)
     'यदि' y<0 'तब' s := −s; t := −t 'endif'
     r:= √(p<sup>2</sup>+d<sup>2</sup>); c:= d/r; s:= p/r; t:= p<sup>2</sup>/d
    एस<sub>''kl''</sub> := 0.0; अद्यतन(k,−t); अद्यतन(एल,टी)
     '''if''' y<0 '''then''' s:= −s; t:= −t '''endif'''
    ! पंक्तियों और स्तंभों को k और l घुमाएँ
    Skl:= 0.0; update(k,−t); update(l,t)
     'के लिए' i := 1 'से' k−1 'do' घुमाएँ(i,k,i,l) 'endfor'
    ! rotate rows and columns k and l
     'के लिए' i := k+1 'से' l−1 'do' घुमाएँ(k,i,i,l) 'endfor'
     '''for''' i:= 1 '''to''' k−1 '''do''' rotate(i,k,i,l) '''endfor'''
     'के लिए' i := l+1 'to' n 'do' रोटेट(k,i,l,i) 'endfor'
     '''for''' i:= k+1 '''to''' l−1 '''do''' rotate(k,i,i,l) '''endfor'''
    ! eigenvectors घुमाएँ
     '''for''' i:= l+1 '''to''' n '''do''' rotate(k,i,l,i) '''endfor'''
     'के लिए' मैं := 1 'से' और 'करें'
   
! rotate eigenvectors
     '''for''' i:= 1 '''to''' n '''do'''
       ┌ <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 137: Line 137:
       │E<sub>''il''</sub>│    │s  c││E<sub>''il''</sub>│
       │E<sub>''il''</sub>│    │s  c││E<sub>''il''</sub>│
       └ <sub>  </sub>┘    └    ┘└ <sub>  </sub>┘
       └ <sub>  </sub>┘    └    ┘└ <sub>  </sub>┘
     अंत के लिए
     '''endfor'''
     ! '' सभी संभावित रूप से परिवर्तित इंडस्ट्रीज़ को अपडेट करें<sub>i</sub>'for' i := 1 'to' n 'do' ind<sub>''i''</sub> := मैक्सइंड(i) 'एंडफॉर'
    ! update all potentially changed indi
   'कुंडली'
     '''for''' i:= 1 '''to''' n '''do''' indi:= maxind(i) '''endfor'''
  'एंडप्रोक'
   '''loop'''
  '''endproc'''


=== टिप्पणियाँ ===
=== टिप्पणियाँ ===


1. The logical array ''changed'' holds the status of each eigenvalue. If the numerical value of <math> e_k </math> or <math> e_l </math>  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 <math> e_1,\, ...\, , e_n </math> 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.
1. तार्किक सरणी प्रत्येक परिवर्तित आइजेनवैल्यू की स्थिति बनाये रखती है। यदि पुनरावृत्ति के समय <math> e_k </math> या <math> e_l </math>  का संख्यात्मक मान परिवर्तित होता है तो परिवर्तित का संबंधित घटक ''true'' पर सेट होता है अन्यथा ''false'' पर। पूर्णांक स्थिति परिवर्तित घटकों की संख्या की गणना करती है जिनका मान ''true'' है। अवस्था = 0 होने पर पुनरावृत्ति रुक जाती है। इसका अर्थ यह है कि किसी भी सन्निकटन <math> e_1,\, ...\, , e_n </math> ने हाल ही में अपना मूल्य परिवर्तित नहीं किया है और इस प्रकार यह बहुत संभावना नहीं है कि यदि पुनरावृत्ति जारी रहती है तो ऐसा होगा। यहां यह माना जाता है कि फ़्लोटिंग पॉइंट ऑपरेशंस को उच्चतम रूप से निकटतम फ़्लोटिंग पॉइंट नंबर तक पूर्णांकित किया जाता है।


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
2. मैट्रिक्स ''S'' का ऊपरी त्रिकोण समाप्त हो गया है जबकि निचला त्रिकोण और विकर्ण अपरिवर्तित हैं। इस प्रकार यदि आवश्यक हो तो ''S'' को पुनर्स्थापित करना संभव है,


  '''for''' ''k'' := 1 '''to''' ''n''−1 '''do''' ! ''restore matrix S''
  '''for''' ''k'':= 1 '''to''' ''n''−1 '''do'''! ''restore matrix S''
     '''for''' ''l'' := ''k''+1 '''to''' ''n'' '''do'''
     '''for''' ''l'':= ''k''+1 '''to''' ''n'' '''do'''
         ''S''<sub>''kl''</sub> := ''S''<sub>''lk''</sub>
         ''S''<sub>''kl''</sub>:= ''S''<sub>''lk''</sub>
     '''endfor'''
     '''endfor'''
  '''endfor'''
  '''endfor'''


3. The eigenvalues are not necessarily in descending order. This can be achieved by a simple sorting algorithm.
3. आइजेनवैल्यू आवश्यक रूप से अवरोही क्रम में नहीं हैं। इसे सरल श्रेणीबद्ध एल्गोरिदम द्वारा प्राप्त किया जा सकता है।


  '''for''' ''k'' := 1 '''to''' ''n''−1 '''do'''
  '''for''' ''k'':= 1 '''to''' ''n''−1 '''do'''
     ''m'' := ''k''
     ''m'':= ''k''
     '''for''' ''l'' := ''k''+1 '''to''' ''n'' '''do'''
     '''for''' ''l'':= ''k''+1 '''to''' ''n'' '''do'''
         '''if''' ''e''<sub>''l''</sub> > ''e''<sub>''m''</sub> '''then'''
         '''if''' ''e''<sub>''l''</sub> > ''e''<sub>''m''</sub> '''then'''
             ''m'' := ''l''
             ''m'':= ''l''
         '''endif'''
         '''endif'''
     '''endfor'''
     '''endfor'''
Line 169: Line 170:
  '''endfor'''
  '''endfor'''


4. The algorithm is written using matrix notation (1 based arrays instead of 0 based).
4. एल्गोरिथ्म मैट्रिक्स नोटेशन (0 आधारित के स्थान पर 1 आधारित सरणियाँ) का उपयोग करके लिखा गया है।
 
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 eigenvalues will change.  Hence, in real implementations, extra logic must be added to account for this case.


5. एल्गोरिदम लागू करते समय मैट्रिक्स नोटेशन का उपयोग करके निर्दिष्ट भाग को एक साथ निष्पादित किया जाना चाहिए।


6. यह कार्यान्वयन उस स्थिति का सही प्रकार से वर्णन नहीं करता है जिसमें एक आयाम स्वतंत्र उप-स्थान है। उदाहरण के लिए यदि विकर्ण मैट्रिक्स दिया गया है तो उपरोक्त कार्यान्वयन कभी भी समाप्त नहीं होगा क्योंकि आइजेनवैल्यू में से कोई भी परिवर्तित नहीं होगा। इसलिए वास्तविक कार्यान्वयन में इस स्थिति को ध्यान में रखते हुए अतिरिक्त तर्क जोड़ा जाना चाहिए।
=== उदाहरण ===
=== उदाहरण ===


होने देना
माना कि
  <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 पुनरावृत्तियों) के बाद निम्नलिखित eigenvalues ​​​​और eigenvectors का उत्पादन करता है:
इसके पश्चात जैकोबी 3 स्वीप (19 पुनरावृत्तियों) के पश्चात निम्नलिखित आइजेनवैल्यू ​​​​और आइजेनवेक्टर का उत्पादन करता है:


<math>
<math>
Line 219: Line 218:
== वास्तविक सममित आव्यूहों के लिए अनुप्रयोग ==
== वास्तविक सममित आव्यूहों के लिए अनुप्रयोग ==


जब एक सममित मैट्रिक्स के eigenvalues ​​​​(और eigenvectors) ज्ञात होते हैं, तो निम्नलिखित
जब सममित मैट्रिक्स के आइजेनवैल्यू ​​​​(और आइजेनवेक्टर) ज्ञात होते हैं तो निम्नलिखित मूल्यों की गणना सरलता से की जाती है।
मूल्यों की गणना आसानी से की जाती है।


;एकवचन मान
;एकवचन मान
:एक (वर्ग) मैट्रिक्स का एकवचन मान <math>A</math> के (गैर-नकारात्मक) eigenvalues ​​​​के वर्गमूल हैं <math> A^T A </math>. सममित मैट्रिक्स के मामले में <math>S</math> हमारे पास है <math> S^T S = S^2 </math>, इसलिए के विलक्षण मूल्य <math>S</math> के eigenvalues ​​​​के पूर्ण मूल्य हैं <math>S</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 का सबसे बड़ा निरपेक्ष मान है और इस प्रकार इसके वर्णक्रमीय त्रिज्या के बराबर है।
:मैट्रिक्स A का 2-मानदंड यूक्लिडियन वेक्टरनॉर्म पर आधारित मानदंड है; अर्थात सबसे बड़ा मूल्य <math> \| A x\|_2 </math> जब x सभी सदिशों <math> \|x\|_2 = 1 </math> से होकर गुजरता है। यह <math>A</math> का सबसे बड़ा एकल मूल्य है। सममित मैट्रिक्स की स्थिति में यह इसके आइजेनवेक्टर का सबसे बड़ा निरपेक्ष मान है और इस प्रकार यह इसके वर्णक्रमीय त्रिज्या के बराबर है।


;शर्त संख्या
;स्थिति संख्या
:एक गैर-एकवचन मैट्रिक्स की स्थिति संख्या <math>A</math> परिभाषित किया जाता है  <math> \mbox{cond} (A) = \| A \|_2 \| A^{-1}\|_2 </math>. एक सममित मैट्रिक्स के मामले में यह सबसे बड़े और सबसे छोटे eigenvalue के भागफल का निरपेक्ष मान है। बड़ी स्थिति संख्याओं वाले मैट्रिक्स संख्यात्मक रूप से अस्थिर परिणाम पैदा कर सकते हैं: छोटी गड़बड़ी के परिणामस्वरूप बड़ी त्रुटियां हो सकती हैं। [[हिल्बर्ट मैट्रिक्स]] सबसे प्रसिद्ध खराब स्थिति वाले मैट्रिक्स हैं। उदाहरण के लिए, चौथे क्रम के हिल्बर्ट मैट्रिक्स की स्थिति 15514 है, जबकि क्रम 8 के लिए यह 2.7 × 10 है<sup>8</sup>.
:व्युत्क्रमणीय मैट्रिक्स <math>A</math> की स्थिति संख्या को <math> \mbox{cond} (A) = \| A \|_2 \| A^{-1}\|_2 </math> के रूप में परिभाषित किया जाता है। सममित मैट्रिक्स की स्थिति में यह सबसे बड़े और सबसे छोटे आइजेनवैल्यू के भागफल का निरपेक्ष मान है। बड़ी स्थिति संख्याओं वाले मैट्रिक्स संख्यात्मक रूप से अस्थिर परिणाम उत्पन्न कर सकते हैं: छोटी गड़बड़ी के परिणामस्वरूप बड़ी त्रुटियां हो सकती हैं। [[हिल्बर्ट मैट्रिक्स]] सबसे प्रसिद्ध खराब स्थिति वाले मैट्रिक्स हैं। उदाहरण के लिए चौथे क्रम के हिल्बर्ट मैट्रिक्स की स्थिति 15514 है जबकि क्रम 8 के लिए यह 2.7 × 10<sup>8</sup> है।


;पद
;रैंक
:एक मैट्रिक्स <math>A</math> रैंक है <math>r</math> अगर यह है <math>r</math> जो स्तंभ रैखिक रूप से स्वतंत्र होते हैं जबकि शेष स्तंभ इन पर रैखिक रूप से निर्भर होते हैं। समान रूप से, <math>r</math> की सीमा का आयाम है<math>A</math>. इसके अलावा यह शून्येतर एकवचन मानों की संख्या है।
:मैट्रिक्स <math>A</math> की रैंक <math>r</math> है यदि  <math>r</math> स्तंभ जो रैखिक रूप से स्वतंत्र होते हैं, जबकि शेष स्तंभ इन पर रैखिक रूप से निर्भर होते हैं। समान रूप से <math>r</math> की सीमा का आयाम <math>A</math> है। इसके अतिरिक्त यह शून्येतर एकवचन मानों की संख्या है।
:एक सममित मैट्रिक्स के मामले में r गैर-शून्य eigenvalues ​​​​की संख्या है। दुर्भाग्य से पूर्णांकन त्रुटियों के कारण शून्य eigenvalues ​​​​का संख्यात्मक सन्निकटन शून्य नहीं हो सकता है (यह भी हो सकता है कि एक संख्यात्मक सन्निकटन शून्य हो जबकि वास्तविक मान शून्य न हो)। इस प्रकार कोई केवल यह निर्णय लेकर संख्यात्मक रैंक की गणना कर सकता है कि कौन सा स्वदेशी मान शून्य के काफी करीब है।
:सममित मैट्रिक्स की स्थिति में r गैर-शून्य आइजेनवैल्यू ​​​​की संख्या है। दुर्भाग्य से पूर्णांकन त्रुटियों के कारण शून्य आइजेनवैल्यू ​​​​का संख्यात्मक सन्निकटन शून्य नहीं हो सकता है (यह भी हो सकता है कि संख्यात्मक सन्निकटन शून्य हो जबकि वास्तविक मान शून्य न हो)। इस प्रकार कोई केवल यह निर्णय लेकर संख्यात्मक रैंक की गणना कर सकता है कि कौन सा आइजेनवैल्यू शून्य के सबसे निकट है।


;छद्म-उलटा
;छद्म-व्युत्क्रम
:मैट्रिक्स का छद्म व्युत्क्रम <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>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> 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>.
:जब प्रक्रिया जैकोबी (S, 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>. हालाँकि कोई इसके लिए वेक्टर x की तलाश कर सकता है  <math> \| Ax - b \|_2 </math> न्यूनतम है. समाधान है <math> x = A^+ b </math>. सममित मैट्रिक्स S के मामले में, पहले की तरह, एक के पास है <math> x = S^+ b = E^T \mbox{Diag} (e^+) E 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>.


;मैट्रिक्स घातांक
;मैट्रिक्स घातांक
:से <math> S = E^T \mbox{Diag} (e) E </math> एक पाता है <math> \exp S = E^T \mbox{Diag} (\exp e) E </math> जहां ऍक्स्प<math>e</math> वेक्टर कहां है <math> e_i </math> द्वारा प्रतिस्थापित किया जाता है <math> \exp e_i </math>. उसी तरह से, <math>f(S)</math> किसी भी (विश्लेषणात्मक) फ़ंक्शन के लिए स्पष्ट तरीके से गणना की जा सकती है <math>f</math>.
:<math> S = E^T \mbox{Diag} (e) E </math> से एक <math> \exp S = E^T \mbox{Diag} (\exp e) E </math> पाता है जहां exp <math>e</math> वेक्टर जहां <math> e_i </math> है, <math> \exp e_i </math> द्वारा प्रतिस्थापित किया जाता है। उसी प्रकार से <math>f(S)</math> किसी भी (विश्लेषणात्मक) फ़ंक्शन <math>f</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>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> के आइजेनवेक्टर द्वारा <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> सकारात्मक eigenvalues ​​​​के लिए अनुरूप। अगर <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>.
:माना कि <math> W^s </math> के आइजेनवेक्टर <math>S</math> द्वारा फैलाया गया सदिश समष्टि हो जो नकारात्मक आइजेनवैल्यू <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 250:
जैकोबी विधि को जटिल हर्मिटियन मैट्रिक्स, सामान्य गैर-सममित वास्तविक और जटिल मैट्रिक्स के साथ-साथ ब्लॉक मैट्रिक्स के लिए जैकोबी विधि में सामान्यीकृत किया गया है।
जैकोबी विधि को जटिल हर्मिटियन मैट्रिक्स, सामान्य गैर-सममित वास्तविक और जटिल मैट्रिक्स के साथ-साथ ब्लॉक मैट्रिक्स के लिए जैकोबी विधि में सामान्यीकृत किया गया है।


चूँकि वास्तविक मैट्रिक्स के एकवचन मान सममित मैट्रिक्स के eigenvalues ​​​​के वर्गमूल होते हैं <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> .
चूँकि वास्तविक मैट्रिक्स के एकवचन मान सममित मैट्रिक्स <math> S = A^T A</math> के आइजेनवैल्यू ​​​​के वर्गमूल होते हैं इसका उपयोग इन मानों की गणना के लिए भी किया जा सकता है। इस स्थिति के लिए विधि को इस प्रकार से संशोधित किया गया है कि S की स्पष्ट रूप से गणना नहीं की जानी चाहिए जिससे राउंड-ऑफ त्रुटियों का संकट कम हो जाता है। ध्यान दें कि <math> B \, := J A J^T </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>,


जैकोबी पद्धति भी समानता के लिए उपयुक्त है।
जैकोबी पद्धति भी समानता के लिए उपयुक्त है।
Line 311: Line 309:


{{Numerical linear algebra}}
{{Numerical linear algebra}}
[[Category: संख्यात्मक रैखिक बीजगणित]] [[Category: स्यूडोकोड उदाहरण सहित लेख]]


[[Category: Machine Translated Page]]
[[Category:CS1 maint]]
[[Category:Collapse templates]]
[[Category:Created On 24/07/2023]]
[[Category:Created On 24/07/2023]]
[[Category:Machine Translated Page]]
[[Category:Navigational boxes| ]]
[[Category:Navigational boxes without horizontal lists]]
[[Category:Pages with script errors]]
[[Category:Sidebars with styles needing conversion]]
[[Category:Template documentation pages|Documentation/doc]]
[[Category:Templates Vigyan Ready]]
[[Category:Templates generating microformats]]
[[Category:Templates that are not mobile friendly]]
[[Category:Templates using TemplateData]]
[[Category:Wikipedia metatemplates]]
[[Category:संख्यात्मक रैखिक बीजगणित]]
[[Category:स्यूडोकोड उदाहरण सहित लेख]]

Latest revision as of 14:30, 11 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 है।

procedure jacobi(S ∈ Rn×n; out e ∈ Rn; out E ∈ Rn×n)
  var
    i, k, l, m, state ∈ N
    s, c, t, p, y, d, r ∈ R
    ind ∈ Nn
    changed ∈ Ln

  function maxind(k ∈ N) ∈ N! index of largest off-diagonal element in row k
    m:= k+1
    for i:= k+2 to n do
      if │Ski│ > │Skmthen m:= i endif
    endfor
    return m
  endfunc
  procedure update(k ∈ N; t ∈ R)! update ek and its status
    y:= ek; ek:= y+t
    if changedk and (y=ek) then changedk:= false; state:= state−1
    elsif (not changedk) and (y≠ek) then changedk:= true; state:= state+1
    endif
  endproc 
  procedure rotate(k,l,i,j ∈ N)! perform rotation of Sij, Skl
    │Skl│    │c  −s││Skl│
    │   │ := │     ││   │
    │Sij│    │s   c││Sij│
    └   ┘    └     ┘└   endproc

 
! init e, E, and arrays ind, changed
  E:= I; state:= n
  for k:= 1 to n do indk:= maxind(k); ek:= Skk; changedk:= true endfor
  while state≠0 do! next rotation
    m:= 1! find index (k,l) of pivot p
    for k:= 2 to n−1 do
      if │Sk indk│ > │Sm indm│ then m:= k endif
    endfor
    k:= m; l:= indm; p:= Skl

! calculate c = cos φ, s = sin φ

    y:= (el−ek)/2; d:= │y│+√(p2+y2)
    r:= √(p2+d2); c:= d/r; s:= p/r; t:= p2/d
    if y<0 then s:= −s; t:= −t endif
    Skl:= 0.0; update(k,−t); update(l,t)
   ! rotate rows and columns k and l
    for i:= 1 to k−1 do rotate(i,k,i,l) endfor
    for i:= k+1 to l−1 do rotate(k,i,i,l) endfor
    for i:= l+1 to n do rotate(k,i,l,i) endfor
   
! rotate eigenvectors
    for i:= 1 to n do  ┐    ┌     ┐┌   ┐
      │Eik│    │c  −s││Eik│
      │   │ := │     ││   │
      │Eil│    │s   c││Eil│
      └   ┘    └     ┘└   endfor
   ! update all potentially changed indi
    for i:= 1 to n do indi:= maxind(i) endfor
  loop
endproc

टिप्पणियाँ

1. तार्किक सरणी प्रत्येक परिवर्तित आइजेनवैल्यू की स्थिति बनाये रखती है। यदि पुनरावृत्ति के समय या का संख्यात्मक मान परिवर्तित होता है तो परिवर्तित का संबंधित घटक true पर सेट होता है अन्यथा false पर। पूर्णांक स्थिति परिवर्तित घटकों की संख्या की गणना करती है जिनका मान true है। अवस्था = 0 होने पर पुनरावृत्ति रुक जाती है। इसका अर्थ यह है कि किसी भी सन्निकटन ने हाल ही में अपना मूल्य परिवर्तित नहीं किया है और इस प्रकार यह बहुत संभावना नहीं है कि यदि पुनरावृत्ति जारी रहती है तो ऐसा होगा। यहां यह माना जाता है कि फ़्लोटिंग पॉइंट ऑपरेशंस को उच्चतम रूप से निकटतम फ़्लोटिंग पॉइंट नंबर तक पूर्णांकित किया जाता है।

2. मैट्रिक्स S का ऊपरी त्रिकोण समाप्त हो गया है जबकि निचला त्रिकोण और विकर्ण अपरिवर्तित हैं। इस प्रकार यदि आवश्यक हो तो S को पुनर्स्थापित करना संभव है,

for k:= 1 to n−1 do! restore matrix S
    for l:= k+1 to n do
        Skl:= Slk
    endfor
endfor

3. आइजेनवैल्यू आवश्यक रूप से अवरोही क्रम में नहीं हैं। इसे सरल श्रेणीबद्ध एल्गोरिदम द्वारा प्राप्त किया जा सकता है।

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 km then
        swap em,ek
        swap Em,Ek
    endif
endfor

4. एल्गोरिथ्म मैट्रिक्स नोटेशन (0 आधारित के स्थान पर 1 आधारित सरणियाँ) का उपयोग करके लिखा गया है।

5. एल्गोरिदम लागू करते समय मैट्रिक्स नोटेशन का उपयोग करके निर्दिष्ट भाग को एक साथ निष्पादित किया जाना चाहिए।

6. यह कार्यान्वयन उस स्थिति का सही प्रकार से वर्णन नहीं करता है जिसमें एक आयाम स्वतंत्र उप-स्थान है। उदाहरण के लिए यदि विकर्ण मैट्रिक्स दिया गया है तो उपरोक्त कार्यान्वयन कभी भी समाप्त नहीं होगा क्योंकि आइजेनवैल्यू में से कोई भी परिवर्तित नहीं होगा। इसलिए वास्तविक कार्यान्वयन में इस स्थिति को ध्यान में रखते हुए अतिरिक्त तर्क जोड़ा जाना चाहिए।

उदाहरण

माना कि


इसके पश्चात जैकोबी 3 स्वीप (19 पुनरावृत्तियों) के पश्चात निम्नलिखित आइजेनवैल्यू ​​​​और आइजेनवेक्टर का उत्पादन करता है:


वास्तविक सममित आव्यूहों के लिए अनुप्रयोग

जब सममित मैट्रिक्स के आइजेनवैल्यू ​​​​(और आइजेनवेक्टर) ज्ञात होते हैं तो निम्नलिखित मूल्यों की गणना सरलता से की जाती है।

एकवचन मान
(वर्ग) मैट्रिक्स का एकवचन मान के (गैर-नकारात्मक) आइजेनवैल्यू ​​​​ के वर्गमूल हैं। सममित मैट्रिक्स की स्थिति में हमारे पास है। इसलिए के विलक्षण मूल्य के आइजेनवैल्यू ​​​​ के पूर्ण मूल्य हैं।
2-मानदंड और वर्णक्रमीय त्रिज्या
मैट्रिक्स A का 2-मानदंड यूक्लिडियन वेक्टरनॉर्म पर आधारित मानदंड है; अर्थात सबसे बड़ा मूल्य जब x सभी सदिशों से होकर गुजरता है। यह का सबसे बड़ा एकल मूल्य है। सममित मैट्रिक्स की स्थिति में यह इसके आइजेनवेक्टर का सबसे बड़ा निरपेक्ष मान है और इस प्रकार यह इसके वर्णक्रमीय त्रिज्या के बराबर है।
स्थिति संख्या
व्युत्क्रमणीय मैट्रिक्स की स्थिति संख्या को के रूप में परिभाषित किया जाता है। सममित मैट्रिक्स की स्थिति में यह सबसे बड़े और सबसे छोटे आइजेनवैल्यू के भागफल का निरपेक्ष मान है। बड़ी स्थिति संख्याओं वाले मैट्रिक्स संख्यात्मक रूप से अस्थिर परिणाम उत्पन्न कर सकते हैं: छोटी गड़बड़ी के परिणामस्वरूप बड़ी त्रुटियां हो सकती हैं। हिल्बर्ट मैट्रिक्स सबसे प्रसिद्ध खराब स्थिति वाले मैट्रिक्स हैं। उदाहरण के लिए चौथे क्रम के हिल्बर्ट मैट्रिक्स की स्थिति 15514 है जबकि क्रम 8 के लिए यह 2.7 × 108 है।
रैंक
मैट्रिक्स की रैंक है यदि स्तंभ जो रैखिक रूप से स्वतंत्र होते हैं, जबकि शेष स्तंभ इन पर रैखिक रूप से निर्भर होते हैं। समान रूप से की सीमा का आयाम है। इसके अतिरिक्त यह शून्येतर एकवचन मानों की संख्या है।
सममित मैट्रिक्स की स्थिति में r गैर-शून्य आइजेनवैल्यू ​​​​की संख्या है। दुर्भाग्य से पूर्णांकन त्रुटियों के कारण शून्य आइजेनवैल्यू ​​​​का संख्यात्मक सन्निकटन शून्य नहीं हो सकता है (यह भी हो सकता है कि संख्यात्मक सन्निकटन शून्य हो जबकि वास्तविक मान शून्य न हो)। इस प्रकार कोई केवल यह निर्णय लेकर संख्यात्मक रैंक की गणना कर सकता है कि कौन सा आइजेनवैल्यू शून्य के सबसे निकट है।
छद्म-व्युत्क्रम
मैट्रिक्स का छद्म व्युत्क्रम अद्वितीय मैट्रिक्स है जिसके लिए और सममित हैं और जिसके लिए धारण करता है। यदि एकवचन नहीं है तो इसके पश्चात, यह
जब प्रक्रिया जैकोबी (S, e, E) कहा जाता है, तो संबंध वह स्थान रखता है जहां Diag(e) विकर्ण पर वेक्टर e के साथ विकर्ण मैट्रिक्स को दर्शाता है। माना कि वेक्टर को निरूपित करें जहां द्वारा प्रतिस्थापित किया जाता है यदि और 0 से यदि (संख्यात्मक रूप से करीब) शून्य है। चूँकि मैट्रिक्स E ऑर्थोगोनल है इसलिए यह इस प्रकार है कि S का छद्म-व्युत्क्रम दिया गया है,
न्यूनतम वर्ग समाधान
यदि मैट्रिक्स पूर्ण रैंक नहीं है तब रैखिक प्रणाली का कोई समाधान नहीं हो सकता है जबकि कोई इसके लिए वेक्टर x की खोज कर सकता है न्यूनतम है। समाधान है। सममित मैट्रिक्स S की स्थिति में, पूर्व रूप से पास है .
मैट्रिक्स घातांक
से एक पाता है जहां exp वेक्टर जहां है, द्वारा प्रतिस्थापित किया जाता है। उसी प्रकार से किसी भी (विश्लेषणात्मक) फ़ंक्शन के लिए स्पष्ट रूप से से गणना की जा सकती है।
रैखिक विभेदक समीकरण
विभेदक समीकरण का समाधान है। सममित मैट्रिक्स के लिए यह इस प्रकार है कि . यदि का विस्तार है के आइजेनवेक्टर द्वारा , तब .
माना कि के आइजेनवेक्टर द्वारा फैलाया गया सदिश समष्टि हो जो नकारात्मक आइजेनवैल्यू के अनुरूप है और सकारात्मक आइजेनवैल्यू ​​​​के लिए अनुरूप है। यदि तब ; अर्थात संतुलन बिंदु 0 का आकर्षण है। यदि तब ; अर्थात् 0 प्रतिकारक है एवं . और , के लिए स्थिर और अस्थिर मैनिफोल्ड कहलाते हैं। यदि दोनों रूपों में घटक होते हैं तो एक घटक आकर्षित होता है और एक घटक विकर्षित होता है। इस प्रकार , के निकट है, जैसे .

सामान्यीकरण

जैकोबी विधि को जटिल हर्मिटियन मैट्रिक्स, सामान्य गैर-सममित वास्तविक और जटिल मैट्रिक्स के साथ-साथ ब्लॉक मैट्रिक्स के लिए जैकोबी विधि में सामान्यीकृत किया गया है।

चूँकि वास्तविक मैट्रिक्स के एकवचन मान सममित मैट्रिक्स के आइजेनवैल्यू ​​​​के वर्गमूल होते हैं इसका उपयोग इन मानों की गणना के लिए भी किया जा सकता है। इस स्थिति के लिए विधि को इस प्रकार से संशोधित किया गया है कि S की स्पष्ट रूप से गणना नहीं की जानी चाहिए जिससे राउंड-ऑफ त्रुटियों का संकट कम हो जाता है। ध्यान दें कि के साथ ,

जैकोबी पद्धति भी समानता के लिए उपयुक्त है।

संदर्भ

  1. 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)
  2. 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.
  3. 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)


अग्रिम पठन



बाहरी संबंध