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

संख्यात्मक रैखिक बीजगणित में जैकोबी आइजेनवैल्यू एल्गोरिथ्म वास्तविक संख्या सममित मैट्रिक्स (एक प्रक्रिया जिसे मैट्रिक्स डायगोनलाइज़ेशन के रूप में जाना जाता है) के आइजेनवैल्यू और आइजन्वेक्टर की गणना के लिए पुनरावृत्त विधि है। इसका नाम कार्ल गुस्ताव जैकब जैकोबी के नाम पर रखा गया है जिन्होंने पहली बार सन 1846 में इस पद्धति का प्रस्ताव रखा था। लेकिन सन 1950 के दशक में कंप्यूटर के आगमन के साथ ही इसका व्यापक रूप से उपयोग किया जाने लगा।

विवरण

माना कि $S$ सममित मैट्रिक्स और $G=G(i,j,\theta )$, गिवेंस रोटेशन मैट्रिक्स हो। तब:

$S'=GSG^{\top }\,$

सममित और समान (रैखिक बीजगणित) $S$ है।

अन्य, $S^{\prime }$ प्रविष्टियाँ हैं:

${\begin{aligned}S'_{ii}&=c^{2}\,S_{ii}-2\,sc\,S_{ij}+s^{2}\,S_{jj}\\S'_{jj}&=s^{2}\,S_{ii}+2sc\,S_{ij}+c^{2}\,S_{jj}\\S'_{ij}&=S'_{ji}=(c^{2}-s^{2})\,S_{ij}+sc\,(S_{ii}-S_{jj})\\S'_{ik}&=S'_{ki}=c\,S_{ik}-s\,S_{jk}&k\neq i,j\\S'_{jk}&=S'_{kj}=s\,S_{ik}+c\,S_{jk}&k\neq i,j\\S'_{kl}&=S_{kl}&k,l\neq i,j\end{aligned}}$

जहाँ $s=\sin(\theta )$ और $c=\cos(\theta )$

जब से $G$ का अर्थ ऑर्थोगोनल है, $S$ और $S^{\prime }$ समान फ्रोबेनियस मानदंड $||\cdot ||_{F}$ (सभी घटकों के वर्गों का वर्गमूल योग) है जबकि हम $\theta$ चुन सकते हैं तथा यह इस प्रकार है कि $S_{ij}^{\prime }=0$, इस स्थिति में $S^{\prime }$ विकर्ण पर वर्गों का योग बड़ा है:

$S'_{ij}=\cos(2\theta )S_{ij}+{\tfrac {1}{2}}\sin(2\theta )(S_{ii}-S_{jj})$

इसे 0 के बराबर सेट करें और पुनर्व्यवस्थित करें:

$\tan(2\theta )={\frac {2S_{ij}}{S_{jj}-S_{ii}}}$

यदि $S_{jj}=S_{ii}$

$\theta ={\frac {\pi }{4}}$

इस प्रभाव को अनुकूलित करने के लिए, S_ij सबसे बड़े निरपेक्ष मान वाला ऑफ-विकर्ण तत्व होना चाहिए जिसे पिवोट कहा जाता है।

जैकोबी आइजेनवैल्यू विधि जैकोबी को तब तक बार-बार घुमाती है जब तक कि मैट्रिक्स लगभग विकर्ण न हो जाए। इसके पश्चात विकर्ण में तत्व S के (वास्तविक) स्वदेशी मानों के सन्निकटन हैं।

अभिसरण

यदि $p=S_{kl}$ पिवोट तत्व है तब परिभाषा के अनुसार $1\leq i,j\leq n,i\neq j$ के लिए $|S_{ij}|\leq |p|$ है। माना कि $\Gamma (S)^{2}$ की सभी ऑफ-विकर्ण प्रविष्टियों के वर्गों का योग $S$ निरूपित करें। जब से $S$, $2N:=n(n-1)$ निश्चित है, हमारे पास ऑफ-विकर्ण तत्व $p^{2}\leq \Gamma (S)^{2}\leq 2Np^{2}$ या $2p^{2}\geq \Gamma (S)^{2}/N$ है। अब $\Gamma (S^{J})^{2}=\Gamma (S)^{2}-2p^{2}$। यह संकेत $\Gamma (S^{J})^{2}\leq (1-1/N)\Gamma (S)^{2}$ या $\Gamma (S^{J})\leq (1-1/N)^{1/2}\Gamma (S)$ करता है;

अर्थात् जैकोबी घूर्णन का क्रम एक कारक द्वारा कम से कम रैखिक रूप से $(1-1/N)^{1/2}$ विकर्ण मैट्रिक्स के लिए परिवर्तित होता है।

$N$ की एक संख्या जैकोबी रोटेशन को स्वीप कहा जाता है; माना कि $S^{\sigma }$परिणाम निरूपित करें। पिछला अनुमान उत्पन्न करता है।

$\Gamma (S^{\sigma })\leq \left(1-{\frac {1}{N}}\right)^{N/2}\Gamma (S)$;

अर्थात् स्वीप का क्रम कारक ≈ के साथ कम से कम रैखिक रूप $e^{1/2}$ से परिवर्तित होता है

जबकि अर्नोल्ड शॉनहेज का निम्नलिखित परिणाम स्थानीय रूप से द्विघात अभिसरण उत्पन्न करता है। इस प्रयोजन के लिए मान लीजिए कि S के पास m विशिष्ट आइजेनवैल्यू $\lambda _{1},...,\lambda _{m}$ बहुलता के साथ $\nu _{1},...,\nu _{m}$​​​​हैं और मान लीजिए कि d > 0 दो अलग-अलग आइजेनवैल्यू ​​​​की सबसे छोटी दूरी है। आइए हम कुछ नंबर को प्रयोग करें

$N_{S}:={\frac {n(n-1)}{2}}-\sum _{\mu =1}^{m}{\frac {1}{2}}\nu _{\mu }(\nu _{\mu }-1)\leq N$

जैकोबी शॉनहेज-स्वीप रोटेशन करता है। यदि तब $S^{s}$ परिणाम को दर्शाता है

$\Gamma (S^{s})\leq {\sqrt {{\frac {n}{2}}-1}}\left({\frac {\gamma ^{2}}{d-2\gamma }}\right),\quad \gamma :=\Gamma (S)$ .

इस प्रकार अभिसरण शीघ्र ही द्विघात हो जाता है

$\Gamma (S)<{\frac {d}{2+{\sqrt {{\frac {n}{2}}-1}}}}$

लागत

प्रत्येक जैकोबी घूर्णन O(n) चरणों में किया जा सकता है जब पिवोट तत्व p ज्ञात हो। जबकि p की खोज के लिए सभी N≈1/2 n² ऑफ-विकर्ण तत्व के निरीक्षण की आवश्यकता होती है। यदि हम एक अतिरिक्त सूचकांक सरणी प्रस्तुत करते हैं तो हम इसे O(n) जटिलता तक भी कम कर सकते हैं $m_{1},\,\dots \,,\,m_{n-1}$ उस संपत्ति के साथ $m_{i}$ वर्तमान S की पंक्ति i, (i = 1, ..., n − 1) में सबसे बड़े तत्व का सूचकांक है। इसके पश्चात पिवोट के सूचकांक (k, l) जोड़े में से एक होना चाहिए $(i,m_{i})$. इसके अतिरिक्त सूचकांक सरणी का अद्यतनीकरण O(n) औसत-केस जटिलता में किया जा सकता है: सबसे अद्यतन पंक्तियों k और l में अधिकतम प्रविष्टि O(n) चरणों में पाई जा सकती है। अन्य पंक्तियों में केवल कॉलम k और l में प्रविष्टियाँ परिवर्तित  होता हैं। इन पंक्तियों पर लूपिंग यदि $m_{i}$ न तो k है और न ही l, यह पुराने अधिकतम $m_{i}$ की तुलना करने के लिए पर्याप्त है नई प्रविष्टियों और अद्यतन के लिए $m_{i}$ यदि आवश्यक है। यदि $m_{i}$ k या l के बराबर होना चाहिए और अद्यतन के समय संबंधित प्रविष्टि कम हो गई है एवं अधिकतम पंक्ति i को O(n) जटिलता में स्क्रैच से पाया जाना चाहिए। जबकि ऐसा प्रति रोटेशन औसतन केवल एक बार होगा। इस प्रकार प्रत्येक रोटेशन में O(n) और एक स्वीप O(n)³ होता है) औसत-केस जटिलता जो मैट्रिक्स गुणन के सामान है। इसके अतिरिक्त प्रक्रिया आरम्भ होने से पहले $m_{i}$ आरंभ किया जाना चाहिए, जिसे n^{2 चरणों में किया जा सकता है।}

सामान्य रूप से जैकोबी पद्धति कम संख्या में स्वीप के बाद संख्यात्मक परिशुद्धता के भीतर परिवर्तित हो जाती है। ध्यान दें कि $N_{S}<N$ एकाधिक आइजेनवैल्यू ​​​​पुनरावृत्तियों की संख्या को कम कर देते हैं।

एल्गोरिथम

निम्नलिखित एल्गोरिदम गणित जैसे नोटेशन में जैकोबी पद्धति का विवरण है।

यह वेक्टर e की गणना करता है जिसमें आइजेनवैल्यू ​​​​और मैट्रिक्स E होता है जिसमें संबंधित आइजेनवेक्टर होते हैं; वह $e_{i}$ है, एक आइजेनवैल्यू और स्तंभ है $E_{i}$ के लिए ऑर्थोनॉर्मल आइजेनवेक्टर $e_{i}$, 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. The logical array changed holds the status of each eigenvalue. If the numerical value of $e_{k}$ or $e_{l}$ 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 $e_{1},\,...\,,e_{n}$ 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.

उदाहरण

माना कि

$S={\begin{pmatrix}4&-30&60&-35\\-30&300&-675&420\\60&-675&1620&-1050\\-35&420&-1050&700\end{pmatrix}}$

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

$e_{1}=2585.25381092892231$

$E_{1}={\begin{pmatrix}0.0291933231647860588\\-0.328712055763188997\\0.791411145833126331\\-0.514552749997152907\end{pmatrix}}$

$e_{2}=37.1014913651276582$

$E_{2}={\begin{pmatrix}-0.179186290535454826\\0.741917790628453435\\-0.100228136947192199\\-0.638282528193614892\end{pmatrix}}$

$e_{3}=1.4780548447781369$

$E_{3}={\begin{pmatrix}-0.582075699497237650\\0.370502185067093058\\0.509578634501799626\\0.514048272222164294\end{pmatrix}}$

$e_{4}=0.1666428611718905$

$E_{4}={\begin{pmatrix}0.792608291163763585\\0.451923120901599794\\0.322416398581824992\\0.252161169688241933\end{pmatrix}}$

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

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

एकवचन मान

एक (वर्ग) मैट्रिक्स का एकवचन मान $A$ के (गैर-नकारात्मक) आइजेनवैल्यू ​​​​के वर्गमूल हैं $A^{T}A$. सममित मैट्रिक्स के मामले में $S$ हमारे पास है $S^{T}S=S^{2}$, इसलिए के विलक्षण मूल्य $S$ के आइजेनवैल्यू ​​​​के पूर्ण मूल्य हैं $S$

2-मानदंड और वर्णक्रमीय त्रिज्या

मैट्रिक्स ए का 2-मानदंड यूक्लिडियन वेक्टरनॉर्म पर आधारित मानदंड है; यानी सबसे बड़ा मूल्य $\|Ax\|_{2}$ जब x सभी सदिशों से होकर गुजरता है $\|x\|_{2}=1$. यह का सबसे बड़ा एकल मूल्य है $A$. एक सममित मैट्रिक्स के मामले में यह इसके eigenvectors का सबसे बड़ा निरपेक्ष मान है और इस प्रकार इसके वर्णक्रमीय त्रिज्या के बराबर है।

शर्त संख्या

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

पद

एक मैट्रिक्स $A$ रैंक है $r$ यदि यह है $r$ जो स्तंभ रैखिक रूप से स्वतंत्र होते हैं जबकि शेष स्तंभ इन पर रैखिक रूप से निर्भर होते हैं। समान रूप से, $r$ की सीमा का आयाम है$A$. इसके अतिरिक्त यह शून्येतर एकवचन मानों की संख्या है।

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

छद्म-उलटा

मैट्रिक्स का छद्म व्युत्क्रम $A$ अद्वितीय मैट्रिक्स है $X=A^{+}$ जिसके लिए $AX$ और $XA$ सममित हैं और जिसके लिए $AXA=A,XAX=X$ धारण करता है. यदि $A$ तो इसके पश्चात, यह एकवचन नहीं है $A^{+}=A^{-1}$.

जब प्रक्रिया जैकोबी (एस, ई, ई) कहा जाता है, तो संबंध $S=E^{T}{\mbox{Diag}}(e)E$ वह स्थान रखता है जहां Diag(e) विकर्ण पर वेक्टर e के साथ विकर्ण मैट्रिक्स को दर्शाता है। माना कि $e^{+}$ वेक्टर को निरूपित करें जहां $e_{i}$ द्वारा प्रतिस्थापित किया जाता है $1/e_{i}$ यदि $e_{i}\leq 0$ और 0 से यदि $e_{i}$ (संख्यात्मक रूप से करीब) शून्य है। चूँकि मैट्रिक्स E ऑर्थोगोनल है, इसलिए यह इस प्रकार है कि S का छद्म-व्युत्क्रम दिया गया है $S^{+}=E^{T}{\mbox{Diag}}(e^{+})E$.

न्यूनतम वर्ग समाधान

यदि मैट्रिक्स $A$ पूर्ण रैंक नहीं है, रैखिक प्रणाली का कोई समाधान नहीं हो सकता है $Ax=b$. जबकि कोई इसके लिए वेक्टर x की तलाश कर सकता है $\|Ax-b\|_{2}$ न्यूनतम है. समाधान है $x=A^{+}b$. सममित मैट्रिक्स S के मामले में, पहले की तरह, एक के पास है $x=S^{+}b=E^{T}{\mbox{Diag}}(e^{+})Eb$.

मैट्रिक्स घातांक

से $S=E^{T}{\mbox{Diag}}(e)E$ एक पाता है $\exp S=E^{T}{\mbox{Diag}}(\exp e)E$ जहां ऍक्स्प$e$ वेक्टर कहां है $e_{i}$ द्वारा प्रतिस्थापित किया जाता है $\exp e_{i}$. उसी तरह से, $f(S)$ किसी भी (विश्लेषणात्मक) फ़ंक्शन के लिए स्पष्ट तरीके से गणना की जा सकती है $f$.

रैखिक विभेदक समीकरण

विभेदक समीकरण $x'=Ax,x(0)=a$ समाधान है $x(t)=\exp(tA)$. एक सममित मैट्रिक्स के लिए $S$, यह इस प्रकार है कि $x(t)=E^{T}{\mbox{Diag}}(\exp te)Ea$. यदि $a=\sum _{i=1}^{n}a_{i}E_{i}$ का विस्तार है $a$ के eigenvectors द्वारा $S$, तब $x(t)=\sum _{i=1}^{n}a_{i}\exp(te_{i})E_{i}$.

माना कि $W^{s}$ के eigenvectors द्वारा फैलाया गया सदिश समष्टि हो $S$ जो एक नकारात्मक eigenvalue के अनुरूप है और $W^{u}$ सकारात्मक आइजेनवैल्यू ​​​​के लिए अनुरूप। यदि $a\in W^{s}$ तब ${\mbox{lim}}_{t\rightarrow \infty }x(t)=0$; यानी संतुलन बिंदु 0 आकर्षक है $x(t)$. यदि $a\in W^{u}$ तब ${\mbox{lim}}_{t\rightarrow \infty }x(t)=\infty$; अर्थात् 0 प्रतिकारक है $x(t)$. $W^{s}$ और $W^{u}$ के लिए स्थिर और अस्थिर मैनिफोल्ड कहलाते हैं $S$. यदि $a$ दोनों रूपों में घटक होते हैं, तो एक घटक आकर्षित होता है और एक घटक विकर्षित होता है। इस तरह $x(t)$ दृष्टिकोण $W^{u}$ जैसा $t\to \infty$.

सामान्यीकरण

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

चूँकि वास्तविक मैट्रिक्स के एकवचन मान सममित मैट्रिक्स के आइजेनवैल्यू ​​​​के वर्गमूल होते हैं $S=A^{T}A$ इसका उपयोग इन मानों की गणना के लिए भी किया जा सकता है। इस मामले के लिए, विधि को इस तरह से संशोधित किया गया है कि एस की स्पष्ट रूप से गणना नहीं की जानी चाहिए, जिससे राउंड-ऑफ त्रुटियों का खतरा कम हो जाता है। ध्यान दें कि $JSJ^{T}=JA^{T}AJ^{T}=JA^{T}J^{T}JAJ^{T}=B^{T}B$ साथ $B\,:=JAJ^{T}$ .

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

अग्रिम पठन

• 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 .

बाहरी संबंध

• Matlab implementation of Jacobi algorithm that avoids trigonometric functions
• C++11 implementation