गाउस विलोपन
रैखिक बीजगणित में गाउस की विलोपन विधि रैखिक समीकरणों के निकाय को हल करने की एक विधि है जिसके अन्तर्गत क्रम से कुछ संक्रियाएँ करने पर अन्ततः एक को छोड़कर बाकी सभी चर विलुप्त हो जाते हैं।
रैखिक समीकरणों के निकाय को हल करने के अलावा गाउस की विलोपन विधि का उपयोग किसी मैट्रिक्स की रैंक प्राप्त करने के लिए, किसी मैट्रिक्स के डिटरमिनैण्ट का मान निकालने के लिए, तथा किसी वर्ग मैट्रिक्स का व्युत्क्रम (इन्वर्स) निकालने के लिए किया जाता है। इस विधि का नाम जर्मनी के गणितज्ञ कार्ल फ्रेडरिक गाउस के नाम पर पड़ा है, यद्यपि यह विधि उनसे पहले भी ज्ञात थी।
गाउस की विलोपन विधि को सम्बन्धित समीकरणों की मैट्रिक्स पर क्रम से की जाने वाली संक्रियाओं के रूप में समझा जा सकता है। अर्थात् समीकरणों को उनके चरों सहित लेकर चलने की आवश्यकता नहीं रहती बल्कि चरों को छोड़ने के बाद जो मैट्रिक्स बचती है, उसी पर सारी संक्रियाएँ एक क्रम से करनी होती हैं। इस विलोपन विधि में केवल पंक्तियों की सरल संक्रियाएँ की जाती हैं ताकि मूल मैट्रिक्स ऐसी मैट्रिक्स में परिवर्तित हो जाय जिसके बाएँ निचले कोने के अधिक से अधिक अवयव शून्य हों। इसके लिए तीन प्रकार की पंक्ति-संक्रियाएँ की जातीं हैं-
- (१) दो पंक्तियों को आपस में बदलना
- (२) किसी पंक्ति को किसी अशून्य संख्या से गुणा करना
- (३) किसी पंक्ति में किसी अशून्य संख्या से गुणा करके दूसरी पंक्ति में जोड़ना
इन तीन संक्रियाओं को समुचित ढंग से करने पर किसी भी मैट्रिक्स को ऊपरी त्रिकोणीय मैट्रिक्स में बदला जा सकता है जो वास्तव में 'पंक्ति-सोपानक स्वरूप' (row echelon form) में होगी। उदाहरण के लिए निम्नलिखित पंक्ति-संक्रियाएँ करते हुए तीसरी और चौथी मैट्रिक्स पंक्ति-सोपानक के रूप में आ गईं हैं तथा अन्तिम मैट्रिक्स अनन्य लघूकृत पंक्ति-सोपानक स्वरूप (unique reduced row echelon form) में है।
- <math>\left[\begin{array}{rrr|r}
1 & 3 & 1 & 9 \\ 1 & 1 & -1 & 1 \\ 3 & 11 & 5 & 35 \end{array}\right]\to \left[\begin{array}{rrr|r} 1 & 3 & 1 & 9 \\ 0 & -2 & -2 & -8 \\ 0 & 2 & 2 & 8 \end{array}\right]\to \left[\begin{array}{rrr|r} 1 & 3 & 1 & 9 \\ 0 & -2 & -2 & -8 \\ 0 & 0 & 0 & 0 \end{array}\right]\to \left[\begin{array}{rrr|r} 1 & 0 & -2 & -3 \\ 0 & 1 & 1 & 4 \\ 0 & 0 & 0 & 0 \end{array}\right] </math>
पंक्ति-संक्रियाएँ करके किसी मैट्रिक्स को लघूकृत पंक्ति-सोपानक रूप में लाने की प्रक्रिया को कभी-कभी गाउस-जॉर्डन विलोपन (Gauss–Jordan elimination) कहते हैं। कुछ लेखक मैट्रिक्स को ऊपरी तिकोनी मैट्रिक्स (अल्घुकृत) में बदलने तक की प्रक्रिया को 'गाउस विलोपन' कहते हैं। जब रैखिक समीकरणों के निकाय का हल निकालना होता है तब कभी-कभी मैट्रिक्स के पूर्णतः लघूकृत होने के पहले ही पंक्ति-संक्रियाओं को रोक देना अधिक सुविधाजनक होता है।
उदाहरण
उदाहरण (१)
माना कि निम्नलिखित समीकरणों के निकाय का हल निकालना है।
- <math>\begin{alignat}{7}
2x &&\; + \;&& y &&\; - \;&& z &&\; = \;&& 8 & \qquad (L_1) \\ -3x &&\; - \;&& y &&\; + \;&& 2z &&\; = \;&& -11 & \qquad (L_2) \\ -2x &&\; + \;&& y &&\; +\;&& 2z &&\; = \;&& -3 & \qquad (L_3) \end{alignat}</math>
नीचे की सारणी में सारी प्रक्रिया दिखाई गई है जिसमें तीन चीजें दिखाई गईं हैं:
- (१) पंक्ति-संक्रिया (एँ)
- (२) क्रमशः परिवर्तित होती मैट्रिक्स
- (३) क्रमशः परिवर्तित होते हुए समीकरण
ध्यान रखें कि प्रायः पूरे समीकरणों को बदलते हुए नहीं दिखाया जाता है बल्कि केवल संवर्धित आव्यूह (augmented matrix) और उसके परिवर्तित रूपों को ही लेकर चलते हैं। कम्प्यूटर के लिए भी यही सुविधाजनक है।
| समीकरणों का निकाय | पंक्ति संक्रियाएँ | संवर्धित मैट्रिक्स |
|---|---|---|
| <math>\begin{alignat}{7}
2x &&\; + \;&& y &&\; - \;&& z &&\; = \;&& 8 & \\ -3x &&\; - \;&& y &&\; + \;&& 2z &&\; = \;&& -11 & \\ -2x &&\; + \;&& y &&\; +\;&& 2z &&\; = \;&& -3 & \end{alignat}</math> || || <math> \left[ \begin{array}{ccc|c} 2 & 1 & -1 & 8 \\ -3 & -1 & 2 & -11 \\ -2 & 1 & 2 & -3 \end{array} \right] </math> | ||
| <math>\begin{alignat}{7}
2x &&\; + && y &&\; - &&\; z &&\; = \;&& 8 & \\
&& && \frac{1}{2}y &&\; + &&\; \frac{1}{2}z &&\; = \;&& 1 & \\
&& && 2y &&\; + &&\; z &&\; = \;&& 5 &
\end{alignat}</math> || <math>L_2 + \frac{3}{2}L_1 \rightarrow L_2</math> | ||
| <math>\begin{alignat}{7}
2x &&\; + && y \;&& - &&\; z \;&& = \;&& 8 & \\ && && \frac{1}{2}y \;&& + &&\; \frac{1}{2}z \;&& = \;&& 1 & \\ && && && &&\; -z \;&&\; = \;&& 1 & \end{alignat}</math> || <math>L_3 + -4L_2 \rightarrow L_3</math> || <math>\left[ \begin{array}{ccc|c} 2 & 1 & -1 & 8 \\ 0 & 1/2 & 1/2 & 1 \\ 0 & 0 & -1 & 1 \end{array} \right] </math> | ||
| मैट्रिक्स अब सोपान (सीढ़ी /echelon) रूप में है जिसे 'तिकोना रूप' भी कहते हैं। | ||
| <math>\begin{alignat}{7}
2x &&\; + && y \;&& &&\; \;&& = \;&& 7 & \\
&& && \frac{1}{2}y \;&& &&\; \;&& = \;&& 3/2 & \\
&& && && &&\; -z \;&&\; = \;&& 1 &
\end{alignat}</math> || <math>L_2+\frac{1}{2}L_3 \rightarrow L_2</math> | ||
| <math>\begin{alignat}{7}
2x &&\; + && y \;&& &&\; \;&& = \;&& 7 & \\
&& && y \;&& &&\; \;&& = \;&& 3 & \\
&& && && &&\; z \;&&\; = \;&& -1 &
\end{alignat}</math> || <math>2L_2 \rightarrow L_2</math> | ||
| <math>\begin{alignat}{7}
x &&\; && \;&& &&\; \;&& = \;&& 2 & \\
&& && y \;&& &&\; \;&& = \;&& 3 & \\
&& && && &&\; z \;&&\; = \;&& -1 &
\end{alignat}</math> || <math>L_1 - L_2 \rightarrow L_1</math> |
जैसे ही तीसरी पंक्ति से y विलुप्त हो जाता है, समीकरणों का निकाय तिकोने रूप में बदल जाता है। इस कलनविधि का पहला भाग यहीं समाप्त हुआ। गणना की दृष्टि से चरों का मान उल्टे क्रम में निकालें तो काम जल्दी हो जाता है। इसे पश्च-प्रतिस्थापन (back-substitution) कहते हैं। हल निम्नलिखित है:
- साँचा:nowrap, साँचा:nowrap, तथा साँचा:nowrap.
अर्थात् दिए गए समीकरणों के निकाय का अनन्य (यूनिक) हल है।
मैट्रिक्स के पंक्ति-सोपानक रूप में आने के बाद ही न रूककर मैट्रिक्स के लघूकृत पंक्ति-सोपानक रूप में बदलने तक प्रक्रिया को जारी रखा जा सकता है। (सारणी में यही किया गया है)। शुरू से लेकर यहाँ तक की प्रक्रिया को कभी-कभी गाउस-जॉर्डन विलोपन (Gauss-Jordan elimination) कहा जाता है।
उदाहरण (२)
निम्नलिखित समीकरणों को हल करना है:
<math> \left\{\begin{array}{*{7}{c}} x &-& y &+& 2z &=& 5 \\ 3x &+& 2y &+&z &=& 10 \\ 2x &-& 3y &-& 2z &=& -10 \\ \end{array}\right. </math>
गाउस-विलोपन विधि का पहला चरण है मैट्रिक्स को लिखना। पिवोट (pivot) 1 है।
<math> \left(\begin{array}{ccc|c} (1) & -1 & 2 & 5 \\ 3 & 2 & 1 & 10 \\ 2 & -3 & -2 & -10 \end{array}\right) </math>
पहली पंक्ति में -3 से गुणा करके दूसरी में जोड़ने से शून्य मिलता है। इसी तरह पहली पंक्ति में - से गुणा करके तीसरी पंक्ति में जोड़ने से शून्य मिलता है। नया धुरी (pivot) 5 है:
<math> \left(\begin{array}{ccc|c} 1 & -1 & 2 & 5 \\ 0 & (5) & -5 & -5 \\ 0 & -1 & -6 & -20 \end{array}\right) </math>
दूसरी पंक्ति में 1/5 से गुणा करने पर:
<math> \left(\begin{array}{ccc|c} 1 & -1 & 2 & 5 \\ 0 & (1) & -1 & -1 \\ 0 & -1 & -6 & -20 \end{array}\right) </math>
अब दूसरी पंक्ति को प्रथम पंक्ति तथा तृतीय पंक्ति में जोड़ते हैं। नयी धुरी -7 है:
<math> \left(\begin{array}{ccc|c} 1 & 0 & 1 & 4 \\ 0 & 1 & -1 & -1 \\ 0 & 0 & (-7) & -21 \end{array}\right) </math>
तीसरी पंक्ति को -7 से भाग देने पर:
<math> \left(\begin{array}{ccc|c} 1 & 0 & 1 & 4 \\ 0 & 1 & -1 & -1 \\ 0 & 0 & (1) & 3 \end{array}\right) </math>
तीसरी पंक्ति को पहली पंक्ति से घटाने पर तथा तीसरी पंक्ति को दूसरी पंक्ति में जोड़ने पर जो मैट्रिक्स प्राप्त होती है उसमें उर्ध्व रेखा के बाएँ तरफ विकर्ण पर 1 हैं।
<math> \left(\begin{array}{ccc|c} 1 & 0 & 0 & 1 \\ 0 & 1 & 0 & 2 \\ 0 & 0 & 1 & 3 \end{array}\right) </math>
समीकरण का हल निकल चुका है, जो यह है:
<math> \left\{\begin{array} {ccc} x &=& 1 \\ y &=& 2 \\ z &=& 3 \\ \end{array}\right. </math>
इन्हें भी देखें
- गाउस-साइडल विधि (रैखिक समीकरणों को हल करने की एक पुनरावृत्तिमूलक विधि)