गाउस-साइडल विधि

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

विवरण

होने देना ${\textstyle 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)}$ के रूप में k-वाँ सन्निकटन या पुनरावृत्ति $\mathbf {x}$, और $\mathbf {x} ^{(k+1)}$ का अगला (या k+1) पुनरावृत्ति है $\mathbf {x}$.

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

समाधान पुनरावर्ती रूप से प्राप्त किया जाता है

$$L_{*}\mathbf {x} ^{(k+1)}=\mathbf {b} -U\mathbf {x} ^{(k)},$$

जहां मैट्रिक्स $A$ एक त्रिकोणीय मैट्रिक्स घटक में विघटित हो जाता है $L_{*}$, और एक त्रिकोणीय मैट्रिक्स # कड़ाई से त्रिकोणीय मैट्रिक्स घटक $U$ ऐसा है कि $A=L_{*}+U$. अधिक विशेष रूप से, का अपघटन $A$ में $L_{*}$ और $U$ द्वारा दिया गया है:

$$A=\underbrace {\begin{bmatrix}a_{11}&0&\cdots &0\\a_{21}&a_{22}&\cdots &0\\\vdots &\vdots &\ddots &\vdots \\a_{n1}&a_{n2}&\cdots &a_{nn}\end{bmatrix}} _{\textstyle L_{*}}+\underbrace {\begin{bmatrix}0&a_{12}&\cdots &a_{1n}\\0&0&\cdots &a_{2n}\\\vdots &\vdots &\ddots &\vdots \\0&0&\cdots &0\end{bmatrix}} _{\textstyle U}.$$

मैट्रिक्स-आधारित सूत्र क्यों काम करता है

रैखिक समीकरणों की प्रणाली को इस प्रकार फिर से लिखा जा सकता है:

${\begin{alignedat}{1}A\mathbf {x} &=\mathbf {b} \\(L_{*}+U)\mathbf {x} &=\mathbf {b} \\L_{*}\mathbf {x} +U\mathbf {x} &=\mathbf {b} \\L_{*}\mathbf {x} &=\mathbf {b} -U\mathbf {x} \end{alignedat}}$

गॉस-सीडेल विधि अब इस अभिव्यक्ति के बाईं ओर को हल करती है$\mathbf {x}$, के लिए पिछले मान का उपयोग करना$\mathbf {x}$दाहिने हाथ की ओर। विश्लेषणात्मक रूप से, इसे इस प्रकार लिखा जा सकता है:

$$\mathbf {x} ^{(k+1)}=L_{*}^{-1}\left(\mathbf {b} -U\mathbf {x} ^{(k)}\right).$$

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

हालाँकि, त्रिकोणीय रूप का लाभ उठाकर $L_{*}$, के तत्व $\mathbf {x} ^{(k+1)}$ प्रत्येक पंक्ति के लिए क्रमिक रूप से गणना की जा सकती है $i$ आगे प्रतिस्थापन का उपयोग करना:

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

ध्यान दें कि सूत्र प्रति पुनरावृत्ति दो योगों का उपयोग करता है जिन्हें एक योग के रूप में व्यक्त किया जा सकता है $\sum _{j\neq i}a_{ij}x_{j}$ जो कि सबसे हाल ही में गणना की गई पुनरावृत्ति का उपयोग करता है $x_{j}$. प्रक्रिया आम तौर पर तब तक जारी रखी जाती है जब तक कि पुनरावृत्ति द्वारा किए गए परिवर्तन कुछ सहनशीलता से कम न हों, जैसे कि पर्याप्त रूप से छोटा अवशिष्ट (संख्यात्मक विश्लेषण)।

चर्चा

गॉस-सीडेल विधि का तत्व-वार सूत्र जैकोबी विधि के समान है।

की गणना $\mathbf {x} ^{(k+1)}$ के तत्वों का उपयोग करता है $\mathbf {x} ^{(k+1)}$ जिसकी गणना पहले ही की जा चुकी है, और केवल इसके तत्व $\mathbf {x} ^{(k)}$ जिसकी गणना नहीं की गई है (k+1)-वाँ पुनरावृत्ति. इसका मतलब यह है कि, जैकोबी पद्धति के विपरीत, केवल एक स्टोरेज वेक्टर की आवश्यकता होती है क्योंकि तत्वों की गणना करते समय उन्हें ओवरराइट किया जा सकता है, जो बहुत बड़ी समस्याओं के लिए फायदेमंद हो सकता है।

हालाँकि, जैकोबी विधि के विपरीत, प्रत्येक तत्व की गणना आमतौर पर समानांतर एल्गोरिथ्म में लागू करना बहुत कठिन होता है, क्योंकि उनमें समानांतर एल्गोरिदम का बहुत लंबा विश्लेषण हो सकता है, और इस प्रकार विरल मैट्रिक्स के लिए सबसे अधिक संभव है। इसके अलावा, प्रत्येक पुनरावृत्ति के मान मूल समीकरणों के क्रम पर निर्भर होते हैं।

गॉस-सीडेल क्रमिक अति-विश्राम के समान है $\omega =1$.

अभिसरण

गॉस-सीडेल विधि के अभिसरण गुण मैट्रिक्स ए पर निर्भर हैं। अर्थात्, प्रक्रिया को अभिसरण के लिए जाना जाता है यदि या तो:

• A सममित सकारात्मक-निश्चित मैट्रिक्स है|सकारात्मक-निश्चित, या
• A सख्ती से या अपरिवर्तनीय रूप से विकर्ण रूप से प्रभावशाली मैट्रिक्स है।

गॉस-सीडेल विधि कभी-कभी इन शर्तों के संतुष्ट न होने पर भी अभिसरण करती है।

गोलूब और वैन लोन एक एल्गोरिथ्म के लिए एक प्रमेय देते हैं जो विभाजित होता है $A$ दो भागों में. कल्पना करना $A=M-N$ निरर्थक है. होने देना $r=\rho (M^{-1}N)$ की वर्णक्रमीय त्रिज्या हो $M^{-1}N$. फिर पुनरावृत्त होता है $x^{(k)}$ द्वारा परिभाषित $Mx^{(k+1)}=Nx^{(k)}+b$ में जुटना $x=A^{-1}b$ किसी भी आरंभिक वेक्टर के लिए $x^{(0)}$ अगर $M$ निरर्थक है और $r<1$.

एल्गोरिथम

चूँकि इस एल्गोरिथ्म में तत्वों की गणना करते समय उन्हें ओवरराइट किया जा सकता है, केवल एक स्टोरेज वेक्टर की आवश्यकता होती है, और वेक्टर इंडेक्सिंग को छोड़ दिया जाता है। एल्गोरिथ्म इस प्रकार है:

एल्गोरिथम गॉस-सीडेल विधि है
    इनपुट: A, b     

output: φ

Choose an initial guess φ to the solution

    अभिसरण तक दोहराएँ
        के लिए i 1 से तक n करना             

σ ← 0

            के लिए j 1 से तक n करना
                अगर j ≠ i तब                     

σ ← σ + a_ijφ_j

                अगर अंत
            अंत (j-कुंडली)             

φ_i ← (b_i − σ) / a_ii

        अंत (i-कुंडली)
        जाँच करें कि क्या अभिसरण पहुँच गया है
    अंत (दोहराएँ)

उदाहरण

मैट्रिक्स संस्करण के लिए एक उदाहरण

एक रैखिक प्रणाली के रूप में दिखाया गया है $A\mathbf {x} =\mathbf {b}$ द्वारा दिया गया है:

$$A={\begin{bmatrix}16&3\\7&-11\\\end{bmatrix}}\quad {\text{and}}\quad b={\begin{bmatrix}11\\13\end{bmatrix}}.$$

हम समीकरण का उपयोग करना चाहते हैं

$$\mathbf {x} ^{(k+1)}=L_{*}^{-1}(\mathbf {b} -U\mathbf {x} ^{(k)})$$

प्रपत्र में

$$\mathbf {x} ^{(k+1)}=T\mathbf {x} ^{(k)}+C$$

कहाँ:

$T=-L_{*}^{-1}U\quad {\text{and}}\quad C=L_{*}^{-1}\mathbf {b} .$

हमें विघटित होना चाहिए $A$ निचले त्रिकोणीय घटक के योग में $L_{*}$ और एक सख्त ऊपरी त्रिकोणीय घटक $U$:

$$L_{*}={\begin{bmatrix}16&0\\7&-11\\\end{bmatrix}}\quad {\text{and}}\quad U={\begin{bmatrix}0&3\\0&0\end{bmatrix}}.$$

का उलटा $L_{*}$ है:

$$L_{*}^{-1}={\begin{bmatrix}16&0\\7&-11\end{bmatrix}}^{-1}={\begin{bmatrix}0.0625&0.0000\\0.0398&-0.0909\\\end{bmatrix}}.$$

अब हम पा सकते हैं:

$${\begin{aligned}T&=-{\begin{bmatrix}0.0625&0.0000\\0.0398&-0.0909\end{bmatrix}}{\begin{bmatrix}0&3\\0&0\end{bmatrix}}={\begin{bmatrix}0.000&-0.1875\\0.000&-0.1194\end{bmatrix}},\\[1ex]C&={\begin{bmatrix}0.0625&0.0000\\0.0398&-0.0909\end{bmatrix}}{\begin{bmatrix}11\\13\end{bmatrix}}={\begin{bmatrix}0.6875\\-0.7439\end{bmatrix}}.\end{aligned}}$$

अब हमारे पास है $T$ और $C$ और हम उनका उपयोग सदिश प्राप्त करने के लिए कर सकते हैं $\mathbf {x}$ पुनरावर्ती रूप से।

सबसे पहले हमें चुनना होगा $\mathbf {x} ^{(0)}$: हम केवल अनुमान लगा सकते हैं. अनुमान जितना बेहतर होगा, एल्गोरिदम उतनी ही तेजी से काम करेगा।

हम एक प्रारंभिक बिंदु चुनते हैं:

$$x^{(0)}={\begin{bmatrix}1.0\\1.0\end{bmatrix}}.$$

फिर हम गणना कर सकते हैं:

$$\mathbf {x} =A^{-1}\mathbf {b} \approx {\begin{bmatrix}0.8122\\-0.6650\end{bmatrix}}.$$