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

संख्यात्मक रैखिक बीजगणित में गाउस-साइडल विधि (Gauss–Seidel method) रैखिक समीकरण निकाय को हल करने की एक पुनरावृत्तिमूलक विधि है। इसे लिबमान विधि (Liebmann method) भी कहते हैं। इसका नाम जर्मनी के गणितज्ञ कार्ल फ्रेडरिक गाउस तथा फिलिप लुडविग फॉन साइडल के नाम पर पड़ा है। यह विधि जकोबी की विधी के जैसी ही है।

यह विधि किसी भी ऐसी मैट्रिक्स के साथ लागू की जा सकती है जिसके विकर्ण के सभी अवयव अशून्य हों। किन्तु अभिसरण केवल तभी सुनिश्चित होगा यदि

• मैट्रिक्स के विकर्ण वाले अवयवों का संख्यात्मक मान अन्य अवयवों की अपेक्षा बड़ा हो,
• सममित आव्यूह (Symmetric matrix) के साथ-साथ धनात्मक निश्‍चित आव्यूह (positive definite matrix) हो। यह विधि गाउस द्वारा अपने एक शिष्य को १८२३ में लिखे एक निजी पत्र में वर्णित की गई थी।^[1]

वर्णन

माना n अज्ञात x चरों से युक्त रैखिक समीकरण निकाय यह है:

${\displaystyle A\mathbf {x} =\mathbf {b} }$.

इसके चरों का मान प्राप्त करने के लिए बारंबार की जाने वाली गणितीय क्रिया यह है:

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

जहाँ मैट्रिक्स A को दो भागों में तोड़ा जाता है-

• (१) निचली त्रिकोणीय मैट्रिक्स ${\displaystyle L_{*}}$, तथा
• (२) पूर्णतः त्रोकोणीय ऊपरी मैट्रिक्स (strictly upper triangular)]] U

${\displaystyle A=L_{*}+U}$.^[2]

इसी बात को विस्तार से नीचे दिया जा रहा है। A, x तथा b को अपने अवयवों के रूप में लिखें तो:

${\displaystyle 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 को निचली त्रिकोणीय मैट्रिक्स तथा पूर्णतः त्रिकोणीय ऊपरी मैट्रिक्स में इस प्रकार तोड़ते हैं:

${\displaystyle A=L_{*}+U\qquad {\text{where}}\qquad L_{*}={\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}},\quad U={\begin{bmatrix}0&a_{12}&\cdots &a_{1n}\\0&0&\cdots &a_{2n}\\\vdots &\vdots &\ddots &\vdots \\0&0&\cdots &0\end{bmatrix}}.}$

इसके बाद दिए हुए रैखिक समीकरणों के निकाय को निम्नलिखित रूप में लिखते हैं:

${\displaystyle L_{*}\mathbf {x} =\mathbf {b} -U\mathbf {x} }$

इसके आधार पर, ${\displaystyle L_{*}}$ के त्रिकोण रूप का लाभ उठाते हुए, x^(k+1) का मान इस प्रकार निकालते हैं:

${\displaystyle x_{i}^{(k+1)}={\frac {1}{a_{ii}}}\left(b_{i}-\sum _{j<i}a_{ij}x_{j}^{(k+1)}-\sum _{j>i}a_{ij}x_{j}^{(k)}\right),\quad i,j=1,2,\ldots ,n.}$^[3]

यही प्रक्रिया बारंबार तब तक करते हैं जब तक x के मानों में नगण्य परिवर्तन हो रहा है। (अर्थात् एक सीमा से कम परिवर्तन हो रहा हो।)

उदाहरण

माना कि k समीकरण दिए हुए हैं तथा x_n इन समीकरणों का वेक्टर है। मानाx₀ इन वेक्टरों का आरम्भिक मान (अनुमान) है। प्रथम समीकरण से, x₁ का मान लिखिए।

${\displaystyle x_{n+1},x_{n+2},\dots ,x_{n}.}$ आगे के समीकरणों को प्राप्त करने के लिए के लिए of x के पुराने मानों को रखकर निकालिए।

इसे समझने के लिए एक उदाहरण लेते हैं।

${\displaystyle {\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}}}$

${\displaystyle x_{1}}$, ${\displaystyle x_{2}}$, ${\displaystyle x_{3}}$ तथा ${\displaystyle x_{4}}$ के लिए हल करने पर हमे यह प्राप्त होता है:

${\displaystyle {\begin{aligned}x_{1}&=x_{2}/10-x_{3}/5+3/5,\\x_{2}&=x_{1}/11+x_{3}/11-3x_{4}/11+25/11,\\x_{3}&=-x_{1}/5+x_{2}/10+x_{4}/10-11/10,\\x_{4}&=-3x_{2}/8+x_{3}/8+15/8.\end{aligned}}}$

माना हम आरम्भ करने के लिए चरों का आरम्भिक अनुमानित मान (0, 0, 0, 0) लेते हैं। इससे हमारा पहला सन्निकट हल (approximate solution) यह मिलता है:

${\displaystyle {\begin{aligned}x_{1}&=3/5=0.6,\\x_{2}&=(3/5)/11+25/11=3/55+25/11=2.3272,\\x_{3}&=-(3/5)/5+(2.3272)/10-11/10=-3/25+0.23272-1.1=-0.9873,\\x_{4}&=-3(2.3272)/8+(-0.9873)/8+15/8=0.8789.\end{aligned}}}$

इससे जो मान मिलते हैं, आगे उनका प्रयोग करते हुए प्रक्रिया को बारबार दोहराते हैं जिससे हमे अधिकाधिक शुद्ध मान प्राप्त होते जाते हैं। जब हमे आवश्यक शुद्धता वाले हल प्राप्त हो जाँय तोब गणना की प्रक्रिया रोक दी जाती है।

चार बार पुनरावृत्ति करने के बाद हमे निम्नलिखित सन्निकट हल प्राप्त होता है:

${\displaystyle x_{1}}$	${\displaystyle x_{2}}$	${\displaystyle x_{3}}$	${\displaystyle x_{4}}$
${\displaystyle 0.6}$	${\displaystyle 2.32727}$	${\displaystyle -0.987273}$	${\displaystyle 0.878864}$
${\displaystyle 1.03018}$	${\displaystyle 2.03694}$	${\displaystyle -1.01446}$	${\displaystyle 0.984341}$
${\displaystyle 1.00659}$	${\displaystyle 2.00356}$	${\displaystyle -1.00253}$	${\displaystyle 0.998351}$
${\displaystyle 1.00086}$	${\displaystyle 2.0003}$	${\displaystyle -1.00031}$	${\displaystyle 0.99985}$

तुलना के लिए, यह जान लीजिए कि समीकरणों के उपरोक्त निकाय का इस ठीकठीक (exact) हल यह है :

(1, 2, −1, 1).

सन्दर्भ

1. Gauss 1903, पृष्ठ 279; direct link Archived 2017-04-21 at the वेबैक मशीन.
2. Golub & Van Loan 1996, पृष्ठ 511.
3. Golub & Van Loan 1996, eqn (10.1.3).