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

From Vigyanwiki
Revision as of 14:30, 11 August 2023 by Manidh (talk | contribs)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

संख्यात्मक रैखिक बीजगणित में जैकोबी आइजेनवैल्यू एल्गोरिथ्म वास्तविक संख्या सममित मैट्रिक्स (प्रक्रिया जिसे मैट्रिक्स डायगोनलाइज़ेशन के रूप में जाना जाता है) के आइजेनवैल्यू और आइजन्वेक्टर की गणना हेतु पुनरावृत्त विधि है। इसका नाम कार्ल गुस्ताव जैकब जैकोबी के नाम पर रखा गया है जिन्होंने पहली बार सन 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)


अग्रिम पठन



बाहरी संबंध