मान लीजिये n रैखिक समीकरण की एक वर्ग प्रणाली हो, जहां:
जब और ज्ञात हैं, और अज्ञात है, हम अनुमान लगाने के लिए गाउस-साइडल विधि का उपयोग कर सकते हैं। सदिश के लिए हमारे प्रारंभिक अनुमान (प्रायः के लिए ) को दर्शाता है। हम के रूप में k-वाँ सन्निकटन या पुनरावर्तन निरूपित करते हैं, और का अगला (या k+1) पुनरावर्तन है।
आव्यूह-आधारित सूत्र
समाधान पुनरावर्ती रूप से प्राप्त किया जाता है
जहां आव्यूह एक त्रिकोणीय आव्यूह घटक में विघटित हो जाता है, और एक अनुशासनपूर्वक त्रिकोणीय आव्यूह घटक इस प्रकार है कि । [4] अधिक विशेष रूप से, में और का अपघटन निम्न द्वारा दिया गया है:
आव्यूह-आधारित सूत्र क्यों काम करता है
रैखिक समीकरणों की प्रणाली को इस प्रकार फिर से लिखा जा सकता है:
दाहिनी ओर के लिए पिछले मान का उपयोग करके, गाउस-साइडल विधि के लिए अब इस अभिव्यक्ति के बाईं ओर को हल करती है। विश्लेषणात्मक रूप से, इसे इस प्रकार लिखा जा सकता है:
तत्व-आधारित सूत्र
हालाँकि, त्रिकोणीय रूप का लाभ उठाकर , के तत्व प्रत्येक पंक्ति के लिए प्रगल्भ प्रतिस्थापन का उपयोग करके क्रमिक रूप से गणना की जा सकती है: [5]
ध्यान दें कि सूत्र प्रति पुनरावर्तन दो योगों का उपयोग करता है जिन्हें एक योग के रूप में व्यक्त किया जा सकता है, जो कि सबसे हाल ही में गणना की गई पुनरावर्तन का उपयोग करता है। प्रक्रिया सामान्यतः तब तक जारी रखी जाती है जब तक कि पुनरावर्तन द्वारा किए गए परिवर्तन कुछ सहनशीलता से कम न हों, जैसे कि पर्याप्त रूप से छोटा अवशिष्ट (संख्यात्मक विश्लेषण)।
चर्चा
गाउस-साइडल विधि का तत्व-वार सूत्र जैकोबी विधि के समान है।
की गणना के तत्वों का उपयोग करती है। जिसकी गणना पहले ही की जा चुकी है, और केवल के तत्व जिनकी गणना (k+1)-वें पुनरावर्तन में नहीं की गई है। इसका अर्थ यह है कि, जैकोबी पद्धति के विपरीत, केवल एक संग्रहण सदिश की आवश्यकता होती है क्योंकि तत्वों की गणना करते समय उन्हें उपरिलेखन किया जा सकता है, जो बहुत बड़ी समस्याओं के लिए लाभकारी हो सकता है।
हालाँकि, जैकोबी विधि के विपरीत, प्रत्येक तत्व की गणना सामान्यतः समानांतर कलन विधि में लागू करना बहुत कठिन होता है, क्योंकि उनमें समानांतर कलन विधि का बहुत लंबा विश्लेषण हो सकता है, और इस प्रकार विरल आव्यूह के लिए सबसे अधिक संभव है। इसके अतिरिक्त, प्रत्येक पुनरावर्तन के मान मूल समीकरणों के क्रम पर निर्भर होते हैं।
A अनुशासनपूर्वक से या अपरिवर्तनीय रूप से विकर्ण रूप से प्रभावशाली आव्यूह है। [7]
गाउस-साइडल विधि कभी-कभी इन स्तिथियों के संतुष्ट न होने पर भी अभिसरण करती है।
गोलूब और वैन लोन एक कलन विधि के लिए एक प्रमेय देते हैं जो को दो भागों में विभाजित करता है। मान लीजिये निरर्थक है। मान लीजिये की वर्णक्रमीय त्रिज्या है। फिर पुनरावर्तन द्वारा परिभाषित में किसी भी आरंभिक सदिश के लिए अभिसरित होता है अगर निरर्थक है और है। [8]
कलन विधि
चूँकि इस कलन विधि में तत्वों की गणना करते समय उन्हें उपरिलेखन किया जा सकता है, केवल एक संग्रह सदिश की आवश्यकता होती है, और सदिश अनुक्रमणीकरण को छोड़ दिया जाता है। कलन विधि इस प्रकार है:
algorithm Gauss–Seidel method isinputs:A, boutput:φ
Choose an initial guess φ to the solution
repeat until convergence
forifrom 1 untilndoσ ← 0
forjfrom 1 untilndoifj ≠ ithenσ ← σ + aijφjend ifend (j-loop)
φi ← (bi − σ) / aiiend (i-loop)
check if convergence is reached
end (repeat)
उदाहरण
आव्यूह संस्करण के लिए एक उदाहरण
एक रैखिक प्रणाली के रूप में दिखाया गया निम्न द्वारा दिया गया है:
हम समीकरण का उपयोग करना चाहते हैं
प्रपत्र में
जहाँ:
हमें को निचले त्रिकोणीय घटक और यथार्थ ऊपरी त्रिकोणीय घटक के योग में विघटित करना होगा: :
का उलटा निम्न है:
अब हम पा सकते हैं:
अब हमारे पास और है और हम उनका उपयोग पुनरावर्ती रूप से सदिश प्राप्त करने के लिए कर सकते हैं।
सबसे पहले हमें चुनना होगा : हम केवल अनुमान लगा सकते हैं. अनुमान जितना बेहतर होगा, कलन विधि उतनी ही तीव्रता से काम करेगी।
हम एक प्रारंभिक बिंदु चुनते हैं:
फिर हम गणना कर सकते हैं:
जैसा कि अपेक्षित था, कलन विधि सटीक समाधान में परिवर्तित होता है:
वास्तव में, आव्यूह A अनुशासनपूर्वक से विकर्ण रूप से प्रभावशाली है (लेकिन सकारात्मक निश्चित नहीं)।
आव्यूह संस्करण के लिए एक और उदाहरण
एक अन्य रैखिक प्रणाली के रूप में दिखाया गया निम्न रूप में दिया गया है:
हम समीकरण का उपयोग करना चाहते हैं
प्रपत्र में
जहाँ:
हमें को निचले त्रिकोणीय घटक और यथार्थ ऊपरी त्रिकोणीय घटक के योग में विघटित करना होगा:
का उलटा निम्न है:
अब हम पा सकते हैं:
अब हमारे पास और है और हम उनका उपयोग पुनरावर्ती रूप से सदिश प्राप्त करने के लिए कर सकते हैं।
सबसे पहले हमें चुनना होगा : हम केवल अनुमान लगा सकते हैं। अनुमान जितना बेहतर होगा, कलन विधि उतनी ही तीव्रता से निष्पादित होगी।
हम कल्पना करते हैं:
फिर हम गणना कर सकते हैं:
यदि हम अभिसरण के लिए परीक्षण करते हैं तो हम पाएंगे कि कलन विधि अलग हो जाती है। वास्तव में, आव्यूह A न तो विकर्ण रूप से प्रभावशाली है और न ही सकारात्मक निश्चित है।
फिर, सटीक समाधान के लिए अभिसरण
इसकी प्रत्याभुति नहीं है और, इस स्तिथि में, घटित नहीं होगा।
समीकरण संस्करण के लिए एक उदाहरण
मान लीजिए k समीकरण दिया गया है जहां xn इन समीकरणों के सदिश और प्रारंभिक बिंदु x0 हैं।
पहले समीकरण से x1 के लिए के पदों में हल करें। अगले समीकरण के लिए xs के पिछले मानों को प्रतिस्थापित करें।
इसे स्पष्ट करने के लिए एक उदाहरण पर विचार करें।
और को हल करने पर निम्न प्राप्त होता है::
मान लीजिए हम (0, 0, 0, 0) प्रारंभिक सन्निकटन के रूप में चुनते हैं, फिर पहला सन्निकटन समाधान दिया जाता है
प्राप्त अनुमानों का उपयोग करते हुए, वांछित सटीकता तक पहुंचने तक पुनरावर्तन प्रक्रिया दोहराई जाती है। चार पुनरावृत्तियों के बाद अनुमानित समाधान निम्नलिखित हैं।
0.6
2.32727
−0.987273
0.878864
1.03018
2.03694
−1.01446
0.984341
1.00659
2.00356
−1.00253
0.998351
1.00086
2.0003
−1.00031
0.99985
प्रणाली का सटीक समाधान (1, 2, −1, 1) है।
पायथन और नम्पि का उपयोग करने वाला एक उदाहरण
निम्नलिखित संख्यात्मक प्रक्रिया केवल समाधान सदिश उत्पन्न करने के लिए पुनरावृत्त होती है।
importnumpyasnpITERATION_LIMIT=1000# initialize the matrixA=np.array([[10.0,-1.0,2.0,0.0],[-1.0,11.0,-1.0,3.0],[2.0,-1.0,10.0,-1.0],[0.0,3.0,-1.0,8.0],])# initialize the RHS vectorb=np.array([6.0,25.0,-11.0,15.0])print("System of equations:")foriinrange(A.shape[0]):row=[f"{A[i,j]:3g}*x{j+1}"forjinrange(A.shape[1])]print("[{0}] = [{1:3g}]".format(" + ".join(row),b[i]))x=np.zeros_like(b,np.float_)forit_countinrange(1,ITERATION_LIMIT):x_new=np.zeros_like(x,dtype=np.float_)print(f"Iteration {it_count}: {x}")foriinrange(A.shape[0]):s1=np.dot(A[i,:i],x_new[:i])s2=np.dot(A[i,i+1:],x[i+1:])x_new[i]=(b[i]-s1-s2)/A[i,i]ifnp.allclose(x,x_new,rtol=1e-8):breakx=x_newprint(f"Solution: {x}")error=np.dot(A,x)-bprint(f"Error: {error}")
↑Bagnara, Roberto (March 1995). "जैकोबी और गॉस-सीडेल विधियों के अभिसरण के लिए एक एकीकृत प्रमाण". SIAM Review. 37 (1): 93–97. doi:10.1137/1037008. JSTOR2132758.