जैकोबी विधि: Difference between revisions
From Vigyanwiki
No edit summary |
No edit summary |
||
| (8 intermediate revisions by 4 users not shown) | |||
| Line 1: | Line 1: | ||
{{Short description|Iterative method used to solve a linear system of equations}} | {{Short description|Iterative method used to solve a linear system of equations}}[[संख्यात्मक रैखिक बीजगणित]] में '''जैकोबी विधि''' रैखिक समीकरणों के विकर्ण प्रभावी प्रणाली के समाधान को निर्धारण करने के लिए एक पुनरावृत्ति एल्गोरिथ्म है, जो प्रत्येक विकर्ण अवयव के लिए हल किया जाता है, और अनुमानित मान को रखा जाता है। यह प्रक्रिया तब तक दोहराई जाती है जब तक कि यह अभिसरित न हो जाए। यह एल्गोरिथम आव्यूह विकर्णन के जैकोबी परिवर्तन बिधि का एक स्ट्रिप्ड-डाउन संस्करण है। इस विधि का नाम [[कार्ल गुस्ताव जैकब जैकोबी]] के नाम पर रखा गया है। | ||
[[संख्यात्मक रैखिक बीजगणित]] में जैकोबी | |||
== विवरण == | == विवरण == | ||
चलो <math>A\mathbf x = \mathbf b</math> n रैखिक समीकरणों की एक वर्ग प्रणाली हो, जहाँ:<math display="block">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}.</math> | चलो <math>A\mathbf x = \mathbf b</math>, n रैखिक समीकरणों की एक वर्ग प्रणाली हो, जहाँ:<math display="block">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}.</math> | ||
जब <math>A</math> और <math>\mathbf b</math> ज्ञात हैं, और <math>\mathbf x</math> अज्ञात है, हम अनुमानित <math>\mathbf x</math> के लिए जैकोबी विधि का उपयोग कर सकते हैं। सदिश <math>\mathbf x^{(0)}</math> के लिए हमारे प्रारंभिक अनुमान | जब <math>A</math> और <math>\mathbf b</math> ज्ञात हैं, और <math>\mathbf x</math> अज्ञात है, हम अनुमानित <math>\mathbf x</math> के लिए जैकोबी विधि का उपयोग कर सकते हैं। सदिश <math>\mathbf x^{(0)}</math> के लिए हमारे प्रारंभिक अनुमान <math>\mathbf x</math> को दर्शाता है (प्रायः <math>\mathbf x^{(0)}_i=0</math> के लिए <math>i=1,2,...,n</math>) के रूप में निरूपित करते हैं <math>\mathbf{x}^{(k)}</math>को <math>\mathbf{x}</math> के k-वें सन्निकटन या पुनरावृत्ति के रूप में निरुपित करते है, और <math>\mathbf{x}^{(k+1)}</math> का अगला पुनरावृत्ति ( k+1) है . | ||
=== मैट्रिक्स आधारित सूत्र === | === मैट्रिक्स आधारित सूत्र === | ||
तब A को एक | तब A को एक विकर्ण घटक D, एक निचला त्रिकोणीय भाग L और एक ऊपरी त्रिकोणीय भाग U में विघटित किया जा सकता है:<math display="block">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}. </math>इसके बाद समाधान को पुनरावृत्त रूप से प्राप्त किया जाता है | ||
:<math> \mathbf{x}^{(k+1)} = D^{-1} (\mathbf{b} - (L+U) \mathbf{x}^{(k)}). </math> | :<math> \mathbf{x}^{(k+1)} = D^{-1} (\mathbf{b} - (L+U) \mathbf{x}^{(k)}). </math> | ||
| Line 16: | Line 13: | ||
=== तत्व-आधारित सूत्र === | === तत्व-आधारित सूत्र === | ||
प्रत्येक पंक्ति के लिए तत्व-आधारित सूत्र <math>i</math> इस प्रकार है:<math display="block"> x^{(k+1)}_i = \frac{1}{a_{ii}} \left(b_i -\sum_{j\ne i}a_{ij}x^{(k)}_j\right),\quad i=1,2,\ldots,n. </math> | प्रत्येक पंक्ति के लिए तत्व-आधारित सूत्र <math>i</math> इस प्रकार है:<math display="block"> x^{(k+1)}_i = \frac{1}{a_{ii}} \left(b_i -\sum_{j\ne i}a_{ij}x^{(k)}_j\right),\quad i=1,2,\ldots,n. </math><math>x_i^{(k+1)}</math> की गणना के लिए स्वयं को छोड़कर <math>\mathbf{x}^{(k)}</math>में प्रत्येक अवयव की आवश्यकता होती है। गॉस-सीडेल विधि के विपरीत, हम <math>x_i^{(k)}</math> को <math>x_i^{(k+1)}</math> के साथ अधिलेखित नहीं कर सकते क्योंकि शेष गणना के लिए उस मान की आवश्यकता होगी। भंडारण की न्यूनतम मात्रा आकार n के दो वैक्टर हैं। | ||
== एल्गोरिथम == | == एल्गोरिथम == | ||
| Line 38: | Line 35: | ||
== अभिसरण == | == अभिसरण == | ||
मानक अभिसरण स्थिति (किसी पुनरावृत्त विधि के लिए) तब होती है जब पुनरावृत्ति | मानक अभिसरण स्थिति (किसी पुनरावृत्त विधि के लिए) तब होती है जब पुनरावृत्ति आव्यूह का [[वर्णक्रमीय त्रिज्या]] 1 से कम होता है: | ||
:<math>\rho(D^{-1}(L+U)) < 1. </math> | :<math>\rho(D^{-1}(L+U)) < 1. </math> | ||
अभिसरण की विधि के लिए एक पर्याप्त (लेकिन आवश्यक नहीं) शर्त यह है कि मैट्रिक्स | अभिसरण की विधि के लिए एक पर्याप्त (लेकिन आवश्यक नहीं) शर्त यह है कि मैट्रिक्स A अलघुकरणीय रूप से विकर्ण प्रमुख है। यथार्थ पंक्ति विकर्ण प्रमुख का अर्थ है कि प्रत्येक पंक्ति के लिए विकर्ण पद का निरपेक्ष मान अन्य पदों के निरपेक्ष मानों के योग से अधिक हो : | ||
:<math>\left | a_{ii} \right | > \sum_{j \ne i} {\left | a_{ij} \right |}. </math> | :<math>\left | a_{ii} \right | > \sum_{j \ne i} {\left | a_{ij} \right |}. </math> | ||
जैकोबी पद्धति कभी-कभी अभिसरण करती है, भले ही ये शर्तें संतुष्ट न हों। | जैकोबी पद्धति कभी-कभी अभिसरण करती है, भले ही ये शर्तें संतुष्ट न हों। | ||
ध्यान दें कि जैकोबी विधि प्रत्येक सममित [[सकारात्मक-निश्चित मैट्रिक्स]] के लिए अभिसरण नहीं करती है। उदाहरण के लिए, | ध्यान दें कि जैकोबी विधि प्रत्येक सममित [[सकारात्मक-निश्चित मैट्रिक्स|सकारात्मक-निश्चित आव्यूह]] के लिए अभिसरण नहीं करती है। उदाहरण के लिए, | ||
<math display="block"> | <math display="block"> | ||
A = | A = | ||
| Line 69: | Line 66: | ||
=== उदाहरण 1 === | === उदाहरण 1 === | ||
एक रैखिक प्रणाली <math>Ax=b</math> प्रारंभिक अनुमान के साथ <math>x^{(0)}</math> द्वारा दिया गया है | |||
:<math> A= | :<math> A= | ||
| Line 86: | Line 83: | ||
1 \\ | 1 \\ | ||
\end{bmatrix} .</math> | \end{bmatrix} .</math> | ||
हम समीकरण | <math>x</math> का अनुमान लगाने के लिए हम ऊपर वर्णित समीकरण <math> x^{(k+1)}=D^{-1}(b - (L+U)x^{(k)})</math> का उपयोग करते हैं | सबसे पहले हम हम ज्ञात मानों से <math>T=-D^{-1}(L+U)</math>और <math>C = D^{-1}b</math> समीकरण को अधिक सुविधाजनक रूप में फिर से समीकरण को <math>D^{-1}(b - (L+U)x^{(k)}) = Tx^{(k)} + C</math> लिखते हैं | | ||
<math display=block> D^{-1}= | <math display=block> D^{-1}= | ||
\begin{bmatrix} | \begin{bmatrix} | ||
| Line 163: | Line 160: | ||
1.143 \\ | 1.143 \\ | ||
\end{bmatrix} .</math> | \end{bmatrix} .</math> | ||
अगला पुनरावृत्ति | अगला पुनरावृत्ति निम्न है | ||
<math display=block> x^{(2)}= | <math display=block> x^{(2)}= | ||
\begin{bmatrix} | \begin{bmatrix} | ||
| Line 218: | Line 215: | ||
\end{align} | \end{align} | ||
</math> | </math> | ||
प्राप्त सन्निकटनों का उपयोग करते हुए, पुनरावृत्त प्रक्रिया को तब तक दोहराया जाता है जब तक कि वांछित सटीकता प्राप्त नहीं हो जाती। निम्नलिखित पाँच पुनरावृत्तियों के बाद अनुमानित | प्राप्त सन्निकटनों का उपयोग करते हुए, पुनरावृत्त प्रक्रिया को तब तक दोहराया जाता है जब तक कि वांछित सटीकता प्राप्त नहीं हो जाती। निम्नलिखित पाँच पुनरावृत्तियों के बाद अनुमानित हल हैं। | ||
{| class="wikitable" border="1" | {| class="wikitable" border="1" | ||
| Line 252: | Line 249: | ||
| 1.02135 | | 1.02135 | ||
|} | |} | ||
व्यवस्था का सटीक | व्यवस्था का सटीक हल {{math|(1, 2, −1, 1)}} है | | ||
=== पायथन | === पायथन उदहारण === | ||
<blockquote> | <blockquote> | ||
#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) | |||
</blockquote> | </blockquote> | ||
==भारित जैकोबी विधि== | |||
भारित जैकोबी पुनरावृत्ति, पुनरावृत्ति की गणना करने के लिए एक पैरामीटर <math>\omega</math> का उपयोग करता है | |||
भारित जैकोबी पुनरावृत्ति एक पैरामीटर | |||
:<math> \mathbf{x}^{(k+1)} = \omega D^{-1} (\mathbf{b} - (L+U) \mathbf{x}^{(k)}) + \left(1-\omega\right)\mathbf{x}^{(k)}</math> | :<math> \mathbf{x}^{(k+1)} = \omega D^{-1} (\mathbf{b} - (L+U) \mathbf{x}^{(k)}) + \left(1-\omega\right)\mathbf{x}^{(k)}</math> | ||
<math>\omega = 2/3</math> के साथ अत्यधिक उपयोग होने के कारण <ref>{{cite book|last=Saad|first=Yousef|author-link=Yousef Saad|title=विरल रेखीय प्रणालियों के लिए पुनरावर्ती तरीके|edition=2nd|year=2003|publisher=[[Society for Industrial and Applied Mathematics|SIAM]]|isbn=0898715342|page=[https://archive.org/details/iterativemethods0000saad/page/414 414]|url=https://archive.org/details/iterativemethods0000saad/page/414}}</ref> संबंध <math> L + U = A - D </math> से इसे <math> \mathbf{x}^{(k+1)} = \omega D^{-1} \mathbf{b} + \left( I - \omega D^{-1} A \right) \mathbf{x}^{(k)} </math> के रूप में भी व्यक्त किया जा सकता है। | |||
संबंध | :. | ||
=== सममित सकारात्मक निश्चित मामले में अभिसरण === | ===सममित सकारात्मक निश्चित मामले में अभिसरण=== | ||
मामले में कि सिस्टम मैट्रिक्स <math> A </math> सममित सकारात्मक-निश्चित | इस मामले में कि सिस्टम [[सकारात्मक-निश्चित मैट्रिक्स|आव्यूह]] <math> A </math> सममित सकारात्मक-निश्चित प्रकार का है, कोई अभिसरण दिखा सकता है। | ||
माना <math> C=C_\omega = I-\omega D^{-1}A </math> पुनरावृति मैट्रिक्स हो और फिर <math> | |||
फिर | |||
\rho(C_\omega) < 1 | \rho(C_\omega) < 1 | ||
\quad \Longleftrightarrow \quad | \quad \Longleftrightarrow \quad | ||
0 < \omega < \frac{2}{\lambda_\text{max} (D^{-1}A)} \,, | 0 < \omega < \frac{2}{\lambda_\text{max} (D^{-1}A)} \,, | ||
</math> | </math> के लिए अभिसरण की गारंटी दी जाती है, जहां <math> \lambda_\text{max} </math>अधिकतम एगेनवैल्यू है| | ||
<math> \omega = \omega_\text{opt} </math> के अनुसार किसी विशेष विकल्प के लिए वर्णक्रमीय त्रिज्या को कम किया जा सकता है | | |||
<math display="block"> | <math display="block"> | ||
\min_\omega \rho (C_\omega) = \rho (C_{\omega_\text{opt}}) = 1-\frac{2}{\kappa(D^{-1}A)+1} | \min_\omega \rho (C_\omega) = \rho (C_{\omega_\text{opt}}) = 1-\frac{2}{\kappa(D^{-1}A)+1} | ||
| Line 323: | Line 313: | ||
\omega_\text{opt} := \frac{2}{\lambda_\text{min}(D^{-1}A)+\lambda_\text{max}(D^{-1}A)} \,, | \omega_\text{opt} := \frac{2}{\lambda_\text{min}(D^{-1}A)+\lambda_\text{max}(D^{-1}A)} \,, | ||
</math> | </math> | ||
जंहा एक <math> \kappa </math> स्थिति संख्या [[सकारात्मक-निश्चित मैट्रिक्स|आव्यूह]] है। | |||
== यह भी देखें == | ==यह भी देखें== | ||
* गॉस-सीडेल विधि | * गॉस-सीडेल विधि | ||
* लगातार अति-विश्राम | *लगातार अति-विश्राम | ||
* इटरेटिव मेथड # लीनियर सिस्टम | इटरेटिव मेथड § लीनियर सिस्टम | *इटरेटिव मेथड # लीनियर सिस्टम | इटरेटिव मेथड § लीनियर सिस्टम | ||
*विश्वास प्रचार#गाऊसी विश्वास प्रसार .28GaBP.29 | *विश्वास प्रचार#गाऊसी विश्वास प्रसार .28GaBP.29 | ||
* [[मैट्रिक्स विभाजन]] | *[[मैट्रिक्स विभाजन]] | ||
== संदर्भ == | ==संदर्भ== | ||
{{Reflist}} | {{Reflist}} | ||
| Line 339: | Line 329: | ||
==बाहरी संबंध== | ==बाहरी संबंध== | ||
* {{CFDWiki|name=Jacobi_method}} | * {{CFDWiki|name=Jacobi_method}} | ||
* {{MathWorld|urlname=JacobiMethod|title=Jacobi method|author=Black, Noel|author2=Moore, Shirley|author3= Weisstein, Eric W.|name-list-style=amp}} | *{{MathWorld|urlname=JacobiMethod|title=Jacobi method|author=Black, Noel|author2=Moore, Shirley|author3= Weisstein, Eric W.|name-list-style=amp}} | ||
* [http://www.math-linux.com/spip.php?article49 Jacobi Method from www.math-linux.com] | *[http://www.math-linux.com/spip.php?article49 Jacobi Method from www.math-linux.com] | ||
{{Numerical linear algebra}} | {{Numerical linear algebra}} | ||
{{Authority control}} | {{Authority control}} | ||
[[Category: | [[Category:Collapse templates]] | ||
[[Category:Created On 23/05/2023]] | [[Category:Created On 23/05/2023]] | ||
[[Category:Lua-based templates]] | |||
[[Category:Machine Translated Page]] | |||
[[Category:Navigational boxes| ]] | |||
[[Category:Navigational boxes without horizontal lists]] | |||
[[Category:Pages with script errors]] | |||
[[Category:Sidebars with styles needing conversion]] | |||
[[Category:Template documentation pages|Documentation/doc]] | |||
[[Category:Templates Vigyan Ready]] | |||
[[Category:Templates generating microformats]] | |||
[[Category:Templates that add a tracking category]] | |||
[[Category:Templates that are not mobile friendly]] | |||
[[Category:Templates that generate short descriptions]] | |||
[[Category:Templates using TemplateData]] | |||
[[Category:Wikipedia articles licensed under the GNU Free Document License]] | |||
[[Category:Wikipedia metatemplates]] | |||
[[Category:आराम (पुनरावृत्ति के तरीके)]] | |||
[[Category:लेख उदाहरण के साथ पायथन (प्रोग्रामिंग भाषा) कोड]] | |||
[[Category:संख्यात्मक रैखिक बीजगणित]] | |||
[[Category:स्यूडोकोड के उदाहरण वाले लेख]] | |||
Latest revision as of 08:50, 13 June 2023
संख्यात्मक रैखिक बीजगणित में जैकोबी विधि रैखिक समीकरणों के विकर्ण प्रभावी प्रणाली के समाधान को निर्धारण करने के लिए एक पुनरावृत्ति एल्गोरिथ्म है, जो प्रत्येक विकर्ण अवयव के लिए हल किया जाता है, और अनुमानित मान को रखा जाता है। यह प्रक्रिया तब तक दोहराई जाती है जब तक कि यह अभिसरित न हो जाए। यह एल्गोरिथम आव्यूह विकर्णन के जैकोबी परिवर्तन बिधि का एक स्ट्रिप्ड-डाउन संस्करण है। इस विधि का नाम कार्ल गुस्ताव जैकब जैकोबी के नाम पर रखा गया है।
विवरण
चलो , n रैखिक समीकरणों की एक वर्ग प्रणाली हो, जहाँ: