जैकोबी विधि

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 के दो वैक्टर हैं।

एल्गोरिथम

Input: initial guess x(0) to the solution, (diagonal dominant) matrix A, right-hand side vector b, convergence criterion
Output: solution when convergence is reached
Comments: pseudocode based on the element-based formula above

k = 0
while convergence not reached do
    for i := 1 step until n do
        σ = 0
        for j := 1 step until n do
            if j ≠ i then
                σ = σ + aij xj(k)
            end
        end
        xi(k+1) = (bi − σ) / aii
    end
    increment k
end

अभिसरण

मानक अभिसरण स्थिति (किसी पुनरावृत्त विधि के लिए) तब होती है जब पुनरावृत्ति मैट्रिक्स का वर्णक्रमीय त्रिज्या 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).

पायथन उदाहरण

import numpy as np

ITERATION_LIMIT = 1000

initialize the matrix

A = np.array([[10., -1., 2., 0.],

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

initialize the RHS vector

b = np.array([6., 25., -11., 15.])

prints the system

print("System:") for i in range(A.shape[0]):

   row = [f"{A[i, j]}*x{j + 1}" for j in range(A.shape[1])]
   print(f'{" + ".join(row)} = {b[i]}')

print() x = np.zeros_like(b) for it_count in range(ITERATION_LIMIT):

   if it_count != 0:
       print(f"Iteration {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]
       if x_new[i] == x_new[i-1]:
         break
   if np.allclose(x, x_new, atol=1e-10, rtol=0.):
       break
   x = x_new

print("Solution: ") print(x) error = np.dot(A, x) - b print("Error:") print(error)

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

भारित जैकोबी पुनरावृत्ति एक पैरामीटर का उपयोग करता है $\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