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

संख्यात्मक रैखिक बीजगणित में, गाउस-साइडल विधि, जिसे लिबमैन विधि या क्रमिक विस्थापन की विधि के रूप में भी जाना जाता है, एक पुनरावृत्त विधि है जिसका उपयोग रैखिक समीकरणों की प्रणाली को हल करने के लिए किया जाता है। इसका नाम जर्मनी के गणितज्ञ कार्ल फ्रेडरिक गॉस और फिलिप लुडविग वॉन सीडेल के नाम पर रखा गया है, और यह जैकोबी पद्धति के समान है। यद्यपि इसे विकर्णों पर गैर-शून्य तत्वों वाले किसी भी आव्यूह पर लागू किया जा सकता है, अभिसरण की प्रत्याभुति केवल तभी दी जाती है जब आव्यूह या तो विकर्ण रूप से प्रमुख आव्यूह हो या सममित आव्यूह और सकारात्मक-निश्चित आव्यूह हो। इसका उल्लेख केवल 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)}$ $\mathbf {x}$ का अगला (या k+1) पुनरावर्तन है।

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

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

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

कलन विधि

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

algorithm Gauss–Seidel method is
    inputs: A, b
    output: φ

    Choose an initial guess φ to the solution
    repeat until convergence
        for i from 1 until n do
            σ ← 0
            for j from 1 until n do
                if j ≠ i then
                    σ ← σ + aijφj
                end if
            end (j-loop)
            φi ← (bi − σ) / aii
        end (i-loop)
        check if convergence is reached
    end (repeat)             

उदाहरण

आव्यूह संस्करण के लिए एक उदाहरण

एक रैखिक प्रणाली के रूप में दिखाया गया $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}}.$$