जैकोबी आइजेनवैल्यू एल्गोरिथम: Difference between revisions
No edit summary |
No edit summary |
||
Line 88: | Line 88: | ||
changed ∈ '''L'''<sup>n</sup> | changed ∈ '''L'''<sup>n</sup> | ||
'''function''' maxind(k ∈ '''N''') ∈ '''N''' ! index of largest off-diagonal element in row k | '''function''' maxind(k ∈ '''N''') ∈ '''N'''! index of largest off-diagonal element in row k | ||
m := k+1 | m:= k+1 | ||
'''for''' i := k+2 '''to''' n '''do''' | '''for''' i:= k+2 '''to''' n '''do''' | ||
if │S<sub>ki</sub>│ > │S<sub>km</sub>│ '''then''' m := i '''endif''' | if │S<sub>ki</sub>│ > │S<sub>km</sub>│ '''then''' m:= i '''endif''' | ||
'''endfor''' | '''endfor''' | ||
'''return''' m | '''return''' m | ||
Line 97: | Line 97: | ||
'''procedure''' update(k ∈ '''N'''; t ∈ '''R''') ! update e<sub>k</sub> and its status | '''procedure''' update(k ∈ '''N'''; t ∈ '''R''')! update e<sub>k</sub> and its status | ||
y := e<sub>k</sub>; e<sub>k</sub> := y+t | y:= e<sub>k</sub>; e<sub>k</sub>:= y+t | ||
'''if''' changedk and (y=e<sub>k</sub>) '''then''' changedk := false; state := state−1 | '''if''' changedk and (y=e<sub>k</sub>) '''then''' changedk:= false; state:= state−1 | ||
'''elsif''' (not changedk) and (y≠e<sub>k</sub>) '''then''' changedk := true; state := state+1 | '''elsif''' (not changedk) and (y≠e<sub>k</sub>) '''then''' changedk:= true; state:= state+1 | ||
'''endif''' | '''endif''' | ||
'''endproc''' | '''endproc''' | ||
'''procedure''' rotate(k,l,i,j ∈ '''N''') ! perform rotation of S<sub>ij</sub>, S<sub>kl</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>│ | ||
Line 114: | Line 114: | ||
! init e, E, and arrays ind, changed | ! init e, E, and arrays ind, changed | ||
E := I; state := n | E:= I; state:= n | ||
'''for''' k := 1 '''to''' n '''do''' ind<sub>k</sub> := maxind(k); e<sub>k</sub> := S<sub>kk</sub>; changedk := true '''endfor''' | '''for''' k:= 1 '''to''' n '''do''' ind<sub>k</sub>:= maxind(k); e<sub>k</sub>:= S<sub>kk</sub>; changedk:= true '''endfor''' | ||
'''while''' state≠0 '''do''' ! next rotation | '''while''' state≠0 '''do'''! next rotation | ||
m := 1 ! find index (k,l) of pivot p | m:= 1! find index (k,l) of pivot p | ||
'''for''' k := 2 '''to''' n−1 '''do''' | '''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''' | '''if''' │S<sub>k</sub> ind<sub>k</sub>│ > │S<sub>m</sub> indm│ '''then''' m:= k '''endif''' | ||
'''endfor''' | '''endfor''' | ||
k := m; l := ind<sub>m</sub>; p := S<sub>kl</sub> | k:= m; l:= ind<sub>m</sub>; p:= S<sub>kl</sub> | ||
! calculate c = cos φ, s = sin φ | ! calculate c = cos φ, s = sin φ | ||
y := (el−ek)/2; d := │y│+√(p2+y2) | y:= (el−ek)/2; d:= │y│+√(p2+y2) | ||
r := √(p<sup>2</sup>+d<sup>2</sup>); c := d/r; s := p/r; t := p<sup>2</sup>/d | r:= √(p<sup>2</sup>+d<sup>2</sup>); c:= d/r; s:= p/r; t:= p<sup>2</sup>/d | ||
'''if''' y<0 '''then''' s := −s; t := −t '''endif''' | '''if''' y<0 '''then''' s:= −s; t:= −t '''endif''' | ||
Skl := 0.0; update(k,−t); update(l,t) | 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:= 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:= 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''' | '''for''' i:= l+1 '''to''' n '''do''' rotate(k,i,l,i) '''endfor''' | ||
! rotate eigenvectors | ! rotate eigenvectors | ||
'''for''' i := 1 '''to''' n '''do''' | '''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 140: | Line 140: | ||
└ <sub> </sub>┘ └ ┘└ <sub> </sub>┘ | └ <sub> </sub>┘ └ ┘└ <sub> </sub>┘ | ||
'''endfor''' | '''endfor''' | ||
! update all potentially changed indi | |||
'''for''' i := 1 '''to''' n '''do''' indi := maxind(i) '''endfor''' | '''for''' i:= 1 '''to''' n '''do''' indi:= maxind(i) '''endfor''' | ||
'''loop''' | '''loop''' | ||
'''endproc''' | '''endproc''' | ||
Line 147: | Line 147: | ||
=== टिप्पणियाँ === | === टिप्पणियाँ === | ||
1. | 1. परिवर्तित तार्किक सरणी प्रत्येक आइजेनवैल्यू की स्थिति रखती है। यदि पुनरावृत्ति के दौरान <math> e_k </math> or <math> e_l </math> का संख्यात्मक मान बदलता है, तो परिवर्तित का संबंधित घटक ''true'' पर सेट होता है अन्यथा ''false'' पर। पूर्णांक स्थिति परिवर्तित घटकों की संख्या की गणना करती है जिनका मान ''true'' है। जैसे ही अवस्था = 0 होने पर पुनरावृत्ति रुक जाती है। इसका मतलब यह है कि किसी भी सन्निकटन <math> e_1,\, ...\, , e_n </math> ने हाल ही में अपना मूल्य नहीं बदला है और इस प्रकार यह बहुत संभावना नहीं है कि यदि पुनरावृत्ति जारी रहती है तो ऐसा होगा। यहां यह माना जाता है कि फ़्लोटिंग पॉइंट ऑपरेशंस को इष्टतम रूप से निकटतम फ़्लोटिंग पॉइंट नंबर तक पूर्णांकित किया जाता है। | ||
2. | 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. | 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 172: | Line 172: | ||
'''endfor''' | '''endfor''' | ||
4. | 4. एल्गोरिथ्म मैट्रिक्स नोटेशन (0 आधारित के बजाय 1 आधारित सरणियाँ) का उपयोग करके लिखा गया है। | ||
5. | 5. एल्गोरिदम लागू करते समय, मैट्रिक्स नोटेशन का उपयोग करके निर्दिष्ट भाग को एक साथ निष्पादित किया जाना चाहिए। | ||
6. | 6. यह कार्यान्वयन उस मामले का सही ढंग से वर्णन नहीं करता है जिसमें एक आयाम एक स्वतंत्र उप-स्थान है। उदाहरण के लिए, यदि एक विकर्ण मैट्रिक्स दिया गया है, तो उपरोक्त कार्यान्वयन कभी भी समाप्त नहीं होगा, क्योंकि आइजेनवैल्यू में से कोई भी नहीं बदलेगा। इसलिए, वास्तविक कार्यान्वयन में, इस मामले को ध्यान में रखते हुए अतिरिक्त तर्क जोड़ा जाना चाहिए। | ||
Line 185: | Line 185: | ||
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 पुनरावृत्तियों) के बाद निम्नलिखित आइजेनवैल्यू और | इसके पश्चात जैकोबी 3 स्वीप (19 पुनरावृत्तियों) के बाद निम्नलिखित आइजेनवैल्यू और आइजेनवेक्टर का उत्पादन करता है: | ||
<math> | <math> |
Revision as of 22:24, 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।
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│ > │Skm│ then 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. परिवर्तित तार्किक सरणी प्रत्येक आइजेनवैल्यू की स्थिति रखती है। यदि पुनरावृत्ति के दौरान or का संख्यात्मक मान बदलता है, तो परिवर्तित का संबंधित घटक 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 k ≠ m then swap em,ek swap Em,Ek endif endfor
4. एल्गोरिथ्म मैट्रिक्स नोटेशन (0 आधारित के बजाय 1 आधारित सरणियाँ) का उपयोग करके लिखा गया है।
5. एल्गोरिदम लागू करते समय, मैट्रिक्स नोटेशन का उपयोग करके निर्दिष्ट भाग को एक साथ निष्पादित किया जाना चाहिए।
6. यह कार्यान्वयन उस मामले का सही ढंग से वर्णन नहीं करता है जिसमें एक आयाम एक स्वतंत्र उप-स्थान है। उदाहरण के लिए, यदि एक विकर्ण मैट्रिक्स दिया गया है, तो उपरोक्त कार्यान्वयन कभी भी समाप्त नहीं होगा, क्योंकि आइजेनवैल्यू में से कोई भी नहीं बदलेगा। इसलिए, वास्तविक कार्यान्वयन में, इस मामले को ध्यान में रखते हुए अतिरिक्त तर्क जोड़ा जाना चाहिए।
उदाहरण
माना कि
इसके पश्चात जैकोबी 3 स्वीप (19 पुनरावृत्तियों) के बाद निम्नलिखित आइजेनवैल्यू और आइजेनवेक्टर का उत्पादन करता है:
वास्तविक सममित आव्यूहों के लिए अनुप्रयोग
जब एक सममित मैट्रिक्स के आइजेनवैल्यू (और 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 .