जैकोबी विधि

Not to be confused with Jacobi eigenvalue algorithm.

संख्यात्मक रैखिक बीजगणित में, जैकोबी विधि (उर्फ जैकोबी पुनरावृति विधि) रैखिक समीकरणों के विकर्ण रूप से प्रभावी मैट्रिक्स प्रणाली के समाधान का निर्धारण करने के लिए एक पुनरावृत्त एल्गोरिथम है। प्रत्येक विकर्ण तत्व के लिए हल किया जाता है, और एक अनुमानित मान प्लग इन किया जाता है। प्रक्रिया तब तक दोहराई जाती है जब तक कि यह अभिसरण न हो जाए। यह एल्गोरिथम जैकोबी ईजेनवेल्यू एल्गोरिथम का एक स्ट्रिप्ड-डाउन संस्करण है। विधि का नाम कार्ल गुस्ताव जैकब जैकोबी के नाम पर रखा गया है।

विवरण

होने देना $A\mathbf {x} =\mathbf {b}$ n रैखिक समीकरणों की एक वर्ग प्रणाली हो, जहाँ:

$$A={\begin{bmatrix}a_{11}&a_{12}&\cdots &a_{1n}\\a_{21}&a_{22}&\cdots &a_{2n}\\\vdots &\vdots &\ddots &\vdots \\a_{n1}&a_{n2}&\cdots &a_{nn}\end{bmatrix}},\qquad \mathbf {x} ={\begin{bmatrix}x_{1}\\x_{2}\\\vdots \\x_{n}\end{bmatrix}},\qquad \mathbf {b} ={\begin{bmatrix}b_{1}\\b_{2}\\\vdots \\b_{n}\end{bmatrix}}.$$

कब $A$ और $\mathbf {b}$ जाने जाते हैं, और $\mathbf {x}$ अज्ञात है, हम अनुमान लगाने के लिए जैकोबी पद्धति का उपयोग कर सकते हैं $\mathbf {x}$. सदिश $\mathbf {x} ^{(0)}$ के लिए हमारे प्रारंभिक अनुमान को दर्शाता है $\mathbf {x}$ (अक्सर $\mathbf {x} _{i}^{(0)}=0$ के लिए $i=1,2,...,n$). हम निरूपित करते हैं $\mathbf {x} ^{(k)}$ के-वें सन्निकटन या पुनरावृत्ति के रूप में $\mathbf {x}$, और $\mathbf {x} ^{(k+1)}$ का अगला (या k+1) पुनरावृत्ति है $\mathbf {x}$.

मैट्रिक्स आधारित सूत्र

तब A को एक विकर्ण मैट्रिक्स घटक D, एक निचला त्रिकोणीय भाग L और एक ऊपरी त्रिकोणीय भाग U में विघटित किया जा सकता है:

$$A=D+L+U\qquad {\text{where}}\qquad D={\begin{bmatrix}a_{11}&0&\cdots &0\\0&a_{22}&\cdots &0\\\vdots &\vdots &\ddots &\vdots \\0&0&\cdots &a_{nn}\end{bmatrix}}{\text{ and }}L+U={\begin{bmatrix}0&a_{12}&\cdots &a_{1n}\\a_{21}&0&\cdots &a_{2n}\\\vdots &\vdots &\ddots &\vdots \\a_{n1}&a_{n2}&\cdots &0\end{bmatrix}}.$$

इसके बाद समाधान को पुनरावृत्त रूप से प्राप्त किया जाता है

$\mathbf {x} ^{(k+1)}=D^{-1}(\mathbf {b} -(L+U)\mathbf {x} ^{(k)}).$

तत्व-आधारित सूत्र

प्रत्येक पंक्ति के लिए तत्व-आधारित सूत्र $i$ इस प्रकार है:

$$x_{i}^{(k+1)}={\frac {1}{a_{ii}}}\left(b_{i}-\sum _{j\neq i}a_{ij}x_{j}^{(k)}\right),\quad i=1,2,\ldots ,n.$$

की गणना $x_{i}^{(k+1)}$ में प्रत्येक तत्व की आवश्यकता है $\mathbf {x} ^{(k)}$ खुद को छोड़कर। गॉस-सीडेल पद्धति के विपरीत, हम अधिलेखित नहीं कर सकते $x_{i}^{(k)}$ साथ $x_{i}^{(k+1)}$, क्योंकि शेष गणना के लिए उस मान की आवश्यकता होगी। भंडारण की न्यूनतम मात्रा आकार n के दो वैक्टर हैं।

एल्गोरिथम

इनपुट: initial guess x(0) to the solution, (विकर्ण प्रभावी) मैट्रिक्स A, दाएँ हाथ की ओर सदिश b, अभिसरण मानदंड
'आउटपुट:' solution when convergence is reached
टिप्पणियाँ: उपरोक्त तत्व-आधारित सूत्र के आधार पर स्यूडोकोड 

k = 0

जबकि अभिसरण नहीं हुआ है
    i के लिए := 1 चरण तक n करें         

σ = 0

        for j := 1 कदम तक n करते हैं
            अगर जे ≠ मैं तो                 

σ = σ + a_ij x_j^(k)

            अंत
        अंत         

x_i^(k+1) = (b_i − σ) / a_ii

    अंत
    वेतन वृद्धि के
अंत

अभिसरण

मानक अभिसरण स्थिति (किसी पुनरावृत्त विधि के लिए) तब होती है जब पुनरावृत्ति मैट्रिक्स का वर्णक्रमीय त्रिज्या 1 से कम होता है:

$\rho (D^{-1}(L+U))<1.$

अभिसरण की विधि के लिए एक पर्याप्त (लेकिन आवश्यक नहीं) शर्त यह है कि मैट्रिक्स ए सख्ती से या अनियमित रूप से तिरछे प्रभावशाली मैट्रिक्स है। सख्त पंक्ति विकर्ण प्रभुत्व का अर्थ है कि प्रत्येक पंक्ति के लिए, विकर्ण पद का निरपेक्ष मान अन्य पदों के निरपेक्ष मानों के योग से अधिक है:

$\left|a_{ii}\right|>\sum _{j\neq i}{\left|a_{ij}\right|}.$

जैकोबी पद्धति कभी-कभी अभिसरण करती है, भले ही ये शर्तें संतुष्ट न हों।

ध्यान दें कि जैकोबी विधि प्रत्येक सममित सकारात्मक-निश्चित मैट्रिक्स के लिए अभिसरण नहीं करती है। उदाहरण के लिए,

$$A={\begin{pmatrix}29&2&1\\2&6&1\\1&1&{\frac {1}{5}}\end{pmatrix}}\quad \Rightarrow \quad D^{-1}(L+U)={\begin{pmatrix}0&{\frac {2}{29}}&{\frac {1}{29}}\\{\frac {1}{3}}&0&{\frac {1}{6}}\\5&5&0\end{pmatrix}}\quad \Rightarrow \quad \rho (D^{-1}(L+U))\approx 1.0661\,.$$

उदाहरण

उदाहरण 1

फॉर्म की एक रैखिक प्रणाली $Ax=b$ प्रारंभिक अनुमान के साथ $x^{(0)}$ द्वारा दिया गया है

$A={\begin{bmatrix}2&1\\5&7\\\end{bmatrix}},\ b={\begin{bmatrix}11\\13\\\end{bmatrix}}\quad {\text{and}}\quad x^{(0)}={\begin{bmatrix}1\\1\\\end{bmatrix}}.$

हम समीकरण का उपयोग करते हैं $x^{(k+1)}=D^{-1}(b-(L+U)x^{(k)})$, ऊपर वर्णित, अनुमान लगाने के लिए $x$. सबसे पहले, हम समीकरण को अधिक सुविधाजनक रूप में फिर से लिखते हैं $D^{-1}(b-(L+U)x^{(k)})=Tx^{(k)}+C$, कहाँ $T=-D^{-1}(L+U)$ और $C=D^{-1}b$. ज्ञात मूल्यों से

$$D^{-1}={\begin{bmatrix}1/2&0\\0&1/7\\\end{bmatrix}},\ L={\begin{bmatrix}0&0\\5&0\\\end{bmatrix}}\quad {\text{and}}\quad U={\begin{bmatrix}0&1\\0&0\\\end{bmatrix}}.$$

हम निर्धारित करते हैं $T=-D^{-1}(L+U)$ जैसा

$$T={\begin{bmatrix}1/2&0\\0&1/7\\\end{bmatrix}}\left\{{\begin{bmatrix}0&0\\-5&0\\\end{bmatrix}}+{\begin{bmatrix}0&-1\\0&0\\\end{bmatrix}}\right\}={\begin{bmatrix}0&-1/2\\-5/7&0\\\end{bmatrix}}.$$

आगे, $C$ रूप में पाया जाता है

$$C={\begin{bmatrix}1/2&0\\0&1/7\\\end{bmatrix}}{\begin{bmatrix}11\\13\\\end{bmatrix}}={\begin{bmatrix}11/2\\13/7\\\end{bmatrix}}.$$

साथ $T$ और $C$ गणना, हम अनुमान लगाते हैं $x$ जैसा $x^{(1)}=Tx^{(0)}+C$:

$$x^{(1)}={\begin{bmatrix}0&-1/2\\-5/7&0\\\end{bmatrix}}{\begin{bmatrix}1\\1\\\end{bmatrix}}+{\begin{bmatrix}11/2\\13/7\\\end{bmatrix}}={\begin{bmatrix}5.0\\8/7\\\end{bmatrix}}\approx {\begin{bmatrix}5\\1.143\\\end{bmatrix}}.$$

अगला पुनरावृत्ति उपज देता है

$$x^{(2)}={\begin{bmatrix}0&-1/2\\-5/7&0\\\end{bmatrix}}{\begin{bmatrix}5.0\\8/7\\\end{bmatrix}}+{\begin{bmatrix}11/2\\13/7\\\end{bmatrix}}={\begin{bmatrix}69/14\\-12/7\\\end{bmatrix}}\approx {\begin{bmatrix}4.929\\-1.714\\\end{bmatrix}}.$$

यह प्रक्रिया अभिसरण तक दोहराई जाती है (यानी, जब तक $\|Ax^{(n)}-b\|$ छोटा है)। 25 पुनरावृत्तियों के बाद समाधान है

$x={\begin{bmatrix}7.111\\-3.222\end{bmatrix}}.$

उदाहरण 2

मान लीजिए कि हमें निम्नलिखित रैखिक प्रणाली दी गई है:

${\begin{aligned}10x_{1}-x_{2}+2x_{3}&=6,\\-x_{1}+11x_{2}-x_{3}+3x_{4}&=25,\\2x_{1}-x_{2}+10x_{3}-x_{4}&=-11,\\3x_{2}-x_{3}+8x_{4}&=15.\end{aligned}}$

अगर हम चुनते हैं (0, 0, 0, 0) को प्रारंभिक सन्निकटन के रूप में, तो प्रथम सन्निकट हल द्वारा दिया जाता है

$${\begin{aligned}x_{1}&=(6+0-(2*0))/10=0.6,\\x_{2}&=(25+0+0-(3*0))/11=25/11=2.2727,\\x_{3}&=(-11-(2*0)+0+0)/10=-1.1,\\x_{4}&=(15-(3*0)+0)/8=1.875.\end{aligned}}$$

प्राप्त सन्निकटनों का उपयोग करते हुए, पुनरावृत्त प्रक्रिया को तब तक दोहराया जाता है जब तक कि वांछित सटीकता प्राप्त नहीं हो जाती। निम्नलिखित पाँच पुनरावृत्तियों के बाद अनुमानित समाधान हैं।

$x_{1}$	$x_{2}$	$x_{3}$	$x_{4}$
0.6	2.27272	-1.1	1.875
1.04727	1.7159	-0.80522	0.88522
0.93263	2.05330	-1.0493	1.13088
1.01519	1.95369	-0.9681	0.97384
0.98899	2.0114	-1.0102	1.02135

व्यवस्था का सटीक समाधान है (1, 2, −1, 1).

पायथन उदाहरण

<वाक्यविन्यास प्रकाश लैंग = संख्यात्मक रेखा = 1> Numpy को np के रूप में आयात करें

ITERATION_LIMIT = 1000

1. मैट्रिक्स को इनिशियलाइज़ करें

ए = एनपी। सरणी (10।, -1।, 2।, 0।],

             [-1., 11., -1., 3.],
             [2., -1., 10., -1.],
             [0.0, 3., -1., 8.)

1. आरएचएस वेक्टर को इनिशियलाइज़ करें

बी = एनपी। सरणी ([6।, 25।, -11।, 15।])

1. सिस्टम प्रिंट करता है

प्रिंट (सिस्टम:) for i in range(A.shape[0]):

   पंक्ति = [एफ {ए [आई, जे]} * एक्स {जे + 1} फॉर जे इन रेंज (ए आकार [1])]
   प्रिंट (एफ '{ + .जॉइन (पंक्ति)} = {बी [i]}')

प्रिंट ()

x = np.zeros_like (ख) इसके लिए_गिनती श्रेणी में (ITERATION_LIMIT):

   अगर it_count! = 0:
       प्रिंट (एफ पुनरावृत्ति {it_count}: {x})
   x_new = np.zeros_like(x)

   for i in range(A.shape[0]):
       s1 = np.dot(A[i, :i], x[:i])
       s2 = np.dot(A[i, i + 1:], x[i + 1:])
       x_new[i] = (b[i] - s1 - s2) / A[i, i]
       अगर x_new[i] == x_new[i-1]:
         तोड़ना

   अगर np.allclose(x, x_new, atol=1e-10, rtol=0.):
       तोड़ना

   एक्स = x_new

प्रिंट (समाधान:) प्रिंट (एक्स) त्रुटि = एनपी डॉट (ए, एक्स) - बी प्रिंट (त्रुटि:) प्रिंट (त्रुटि) </वाक्यविन्यास हाइलाइट>

भारित जैकोबी विधि

भारित जैकोबी पुनरावृत्ति एक पैरामीटर का उपयोग करता है $\omega$ पुनरावृत्ति की गणना करने के लिए

$\mathbf {x} ^{(k+1)}=\omega D^{-1}(\mathbf {b} -(L+U)\mathbf {x} ^{(k)})+\left(1-\omega \right)\mathbf {x} ^{(k)}$

साथ $\omega =2/3$ सामान्य पसंद होने के नाते। संबंध से $L+U=A-D$, इसे इस रूप में भी व्यक्त किया जा सकता है

$\mathbf {x} ^{(k+1)}=\omega D^{-1}\mathbf {b} +\left(I-\omega D^{-1}A\right)\mathbf {x} ^{(k)}$.

सममित सकारात्मक निश्चित मामले में अभिसरण

मामले में कि सिस्टम मैट्रिक्स $A$ सममित सकारात्मक-निश्चित मैट्रिक्स का है | सकारात्मक-निश्चित प्रकार कोई अभिसरण दिखा सकता है।

होने देना $C=C_{\omega }=I-\omega D^{-1}A$ पुनरावृत्ति मैट्रिक्स हो। फिर, अभिसरण की गारंटी है

$\rho (C_{\omega })<1\quad \Longleftrightarrow \quad 0<\omega <{\frac {2}{\lambda _{\text{max}}(D^{-1}A)}}\,,$ कहाँ $\lambda _{\text{max}}$ अधिकतम eigenvalue है।

किसी विशेष विकल्प के लिए वर्णक्रमीय त्रिज्या को कम किया जा सकता है $\omega =\omega _{\text{opt}}$ निम्नलिखित नुसार

$$\min _{\omega }\rho (C_{\omega })=\rho (C_{\omega _{\text{opt}}})=1-{\frac {2}{\kappa (D^{-1}A)+1}}\quad {\text{for}}\quad \omega _{\text{opt}}:={\frac {2}{\lambda _{\text{min}}(D^{-1}A)+\lambda _{\text{max}}(D^{-1}A)}}\,,$$

कहाँ $\kappa$ स्थिति संख्या#मैट्रिसेस है।

यह भी देखें

• गॉस-सीडेल विधि
• लगातार अति-विश्राम
• इटरेटिव मेथड # लीनियर सिस्टम | इटरेटिव मेथड § लीनियर सिस्टम
• विश्वास प्रचार#गाऊसी विश्वास प्रसार .28GaBP.29
• मैट्रिक्स विभाजन

बाहरी संबंध

• This article incorporates text from the article Jacobi_method on CFD-Wiki that is under the GFDL license.

• Black, Noel; Moore, Shirley & Weisstein, Eric W. "Jacobi method". MathWorld.
• Jacobi Method from www.math-linux.com