گاسین اخراج

* Gaussian elimination

**گاسین اخراج** یکلخت لکیری مساوات کا نظام کا حل نکالنے کا ایک تیز طریقہ ہے جو اکثر شمارندہ کے الخوارزمیہ میں استعمال کیا جاتا ہے۔

*n* متغیر \ x_{k} میں *m* یکلخت لکیری مساوات کا نظام، جہاں \ a_{k,j} اور \ b_{k} دائم ہیں:

\begin{matrix}
a_{1,1} x_1 + a_{1,2} x_2 + \cdots + a_{1,n} x_n = b_1 \\
a_{2,1} x_1 + a_{2,2} x_2 + \cdots + a_{2,n} x_n = b_2 \\
\vdots \\
a_{m,1} x_1 + a_{m,2} x_2 + \cdots + a_{m,n} x_n = b_m 
\end{matrix}


کو بطور افزائشی میٹرکس یوں لکھا جاتا ہے
\left[
\begin{matrix}
a_{1,1} & a_{1,2} & \cdots & a_{1,n} & b_1 \\
a_{2,1} & a_{2,2} & \cdots & a_{2,n} & b_2 \\
\vdots & \vdots & & \vdots & \vdots \\
a_{m,1} & a_{m,2} & \cdots & a_{m,n} & b_m 
\end{matrix}\right]


جو عمل کرنے سے مساوات کے نظام کے حل پر کوئی فرق نہیں پڑتا، ان کو افزائشی میٹرکس کے حوالے سے یوں بولا جا سکتا ہے:
# ایک قطار کو کسی دائم عدد سے ضرب دے دو
# دو قطاروں کا باہمی تبادلہ کر دو
# ایک قطار کو کسی دائم عدد سے ضرب دینے کے بعد جو حاصل ضرب قطار ملے، اسے کسی دوسری قطار میں جمع کر دو

ان عملیات کو *ابتدائی قطار عملیات* کہا جاتا ہے۔ 
* elementary row operations = ابتدائی قطار عملیات

گاسین اخراج کے طریقہ میں مساوات کے حل کی طرف جانے کے لیے افزائشی میٹرکس کو ابتدائی قطار عملیات کے ذریعہ ترتیبہ ہیئت میں لے جاتے ہیں۔
تعریف: اگر میٹرکس میں مندرجہ ذیل خصوصیات ہوں، تو میٹرکس کو *ترتیبہ ہیئت* کہتے ہیں:
# اگر قطار سب صفر نہ ہو، تو قطار کا پہلا غیر صفر جُز (بائیں طرف سے ) ایک (1) ہو۔ اس 1 کو "اول 1" کہتے ہیں۔
# اگر کچھ ایسی قطاریں ہو جو تمام صفر ہوں، تو یہ قطاریں سب سے نیچے ہوں
# کسی بھی دو قطاروں (جو غیر صفر ہوں) میں اوپر والی قطار کا "اول 1" نیچے والی قطار کے "اول "1 کے بائیں طرف ہونا چاہیے۔
* row echelon form=ترتیبہ ہیئت
* leading=اول
مثال کے طور پر میٹرکس
\left[
\begin{matrix}
1 & 2 & 7 & -3 \\
0 & 1 & -4 & 13 \\
0 & 0 & 1 & 11 
\end{matrix}\right]

ترتیبہ ہیئت میں ہے۔
جب میٹرکس اس ہیئت میں آ جائے تو نظام کا حل آسانی سے "الٹا تبادلہ" کے ذریعہ نکالا جا سکتا ہے۔
* back substitution=الٹا تبادلہ
اب ہم ایک مثال کے ذریعہ اوپر والے عملیات استعمال کرتے ہوئے لکیری مساوات کا نظام حل کرنے کا گاسین اخراج کا کا طریقہ سمجھاتے ہیں:

### مثال
* تیں متغیر میں تین لکیری مساوات کے نظام

\begin{matrix}
2 x_1 + 3 x_2 - x_3 = 4 \\
3 x_1 - 2 x_2 + 4 x_3 = -1 \\
-5 x_1 - 4 x_2 + 8 x_3 = -3 
\end{matrix}

کو افزائشی میٹرکس کے بطور لکھو
\left[
\begin{matrix}
2 & 3 & -1 & 4 \\
3 & -2 & 4 & -1 \\
-5 & -4 & 8 & -3 
\end{matrix}\right]

* اوپر کی میٹرکس میں پہلے ستون (بائیں طرف سے ) میں مطلق قیمت میں سب سے بڑا عنصر -5 ہے۔ اس لیے ہم تیسری قطار کو سب سے اوپر لے آتے ہیں۔ یعنی پہلی اور تیسری قطار کا تبادلہ۔
\left[
\begin{matrix}
-5 & -4 & 8 & -3 \\
2 & 3 & -1 & 4 \\
3 & -2 & 4 & -1 
\end{matrix}\right]

* اوپر کی میٹرکس کی پہلی قطار کو -1/5 سے ضرب دو (تو افزائشی میٹرکس یوں ہو جائے گی)
\left[
\begin{matrix}
1 & 4/5 & -8/5 & 3/5 \\
3 & -2 & 4 & -1 \\
2 & 3 & -1 & 4 
\end{matrix}\right]

* اوپر کی میٹرکس کی پہلی قطار کو -3 سے ضرب دے کر جو حاصل ضرب آئے اسے دوسری قطار میں جمع کر دو
\left[
\begin{matrix}
1 & 4/5 & -8/5 & 3/5 \\
0 & -22/5 & 44/5 & -14/5 \\
2 & 3 & -1 & 4 
\end{matrix}\right]

* اوپر کی میٹرکس کی پہلی قطار کو 2 سے ضرب دے کر جو حاصل ضرب آئے اسے تیسری قطار میں جمع کر دو
\left[
\begin{matrix}
1 & 4/5 & -8/5 & 3/5 \\
0 & -22/5 & 44/5 & -14/5 \\
0 & 7/5 & 11/5 & 14/5 
\end{matrix}\right]

* اب اوپر کی میٹرکس میں پہلی قطار کو بھول جاؤ اور اس سے نیچے کی قطاروں کو دیکھو۔ دوسرے ستون میں مطلق قیمت میں سب سے بڑی رقم (-22/5) سب سے اوپر ہے اس لیے ہمیں قطار تبادلہ کرنے کی ضرورت نہیں۔ اوپر کی میٹرکس کی دوسری قطار کو -5/22 سے ضرب دو
\left[
\begin{matrix}
1 & 4/5 & -8/5 & 3/5 \\
0 & 1 & -2 & 7/11 \\
0 & 7/5 & 11/5 & 14/5 
\end{matrix}\right]

* اوپر کی میٹرکس کی دوسری قطار کو -7/5 سے ضرب دے کر جو حاصل ضرب آئے اسے تیسیر قطار میں جمع کر دو
\left[
\begin{matrix}
1 & 4/5 & -8/5 & 3/5 \\
0 & 1 & -2 & 7/11 \\
0 & 0 & 5 & 21/11 
\end{matrix}\right]

* اوپر کی میٹرکس کی تیسری قطار کو 1/5 سے ضرب دو
\left[
\begin{matrix}
1 & 4/5 & -8/5 & 3/5 \\
0 & 1 & -2 & 7/11 \\
0 & 0 & 1 & 21/55 
\end{matrix}\right]

اب یہ میٹرکس ترتیبہ ہیئت میں آ گئی ہے۔ اس میٹرکس کا نظام یوں لکھا جا سکتا ہے:

\begin{matrix}
x_1 &+ (4/5) x_2 &- (8/5) x_3 &= 3/5 \\
& x_2 & -2 x_3 &= 7/11 \\
& & x_3 &= 21/55 
\end{matrix}

* دیکھو کہ آخری مساوات سے ہمیں x_3 کی قیمت معلوم ہو چکی ہے:
:x_3 = \frac{21}{55} 
اب یہ قیمت ہم دوسری مساوات میں ڈال کر x_2 کی قیمت حاصل کر لیتے ہیں:
:x_2 = 2 x_3 + \frac{7}{11} = 2 \times \frac{21}{55}
+ \frac{7}{11} = \frac{77}{55}

اب x_3 اور x_2 کی قیمتیں پہلی مساوات میں ڈال کر x_1 کی قیمت یوں معلوم ہوتی ہے:
:x_1 = -\frac{4}{5} x_2 + \frac{8}{5} x_3 + \frac{3}{5}
= \frac{4}{5} \times \frac{77}{55} + \frac{8}{5} \times \frac{21}{55} + \frac{3}{5}
=\frac{1}{11}

تو پورے لکیری مساوات نظام کا حل یوں ہوا
:(x_1, x_2, x_3) = 
\left(\frac{1}{11}, \frac{77}{55}, \frac{21}{55}\right)

## مٰیٹرکس کا اُلٹ نکالنا
گاسین اخراج جیسے طریقے سے ایک میٹرکس کا اُلٹ نکالا جا سکتا ہے۔ اس کے لیے n \times n میٹرکس *A* کو تطابق قالب I_n کے ساتھ افزائش کر کے لکھتے ہیں [A|I_n]
پھر اس افزائش میٹرکس پر یکے بعد دیگرے بنیادی قطار عمل اس طرح کرتے ہیں کہ اس کا روپ [I_n|B] جائے۔ اب مٰیٹرکس *A* اور *B* ایک دوسرے کا الٹ ہوں گے۔
یعنی 
:B=A^{-1}
یہ طریقہ ہم ایک مثال کے ذریعہ سمجھاتے ہیں:

### مثال
میٹرکس
:\left[ \begin{matrix}
2 & 3 & -1 \\
3 & -2 & 4 \\
5 & 4 & -8
\end{matrix}\right]

کو مقلوب کرنا مقصود ہے۔
* اس کی شناخت میٹرکس سے افزائش کرتے ہوئے:
:\left[ \begin{matrix}
2 & 3 & -1 & | & 1 & 0 & 0\\
3 & -2 & 4 & | & 0 & 1 & 0\\
5 & 4 & -8 & | & 0 & 0 & 1
\end{matrix}\right]

* اوپر کی میٹرکس میں پہلی قطار کو 1/2 سے ضرب دے کر
:\left[ \begin{matrix}
1 & 3/2 & -1/2 & | & 1/2 & 0 & 0\\
3 & -2 & 4 & | & 0 & 1 & 0\\
5 & 4 & -8 & | & 0 & 0 & 1
\end{matrix}\right]

* اوپر کی میٹرکس میں پہلی قطار کو -3 سے ضرب دے کر جو حاصل ضرب آئے، اسے دوسری قطار میں جمع کر دو
:\left[ \begin{matrix}
1 & 3/2 & -1/2 & | & 1/2 & 0 & 0\\
0 & -13/2 & 11/2 & | & -3/2 & 1 & 0\\
5 & 4 & -8 & | & 0 & 0 & 1
\end{matrix}\right]

* اوپر کی میٹرکس میں پہلی قطار کو -5 سے ضرب دے کر جو حاصل ضرب آئے، اسے تیسری قطار میں جمع کر دو
:\left[ \begin{matrix}
1 & 3/2 & -1/2 & | & 1/2 & 0 & 0\\
0 & -13/2 & 11/2 & | & -3/2 & 1 & 0\\
0 & -7/2 & -11/2 & | & -5/2 & 0 & 1
\end{matrix}\right]

* اوپر کی میٹرکس میں دوسری قطار کو -2/13 سے ضرب دو
:\left[ \begin{matrix}
1 & 3/2 & -1/2 & | & 1/2 & 0 & 0\\
0 & 1 & -11/13 & | & 3/13 & -2/13 & 0\\
0 & -7/2 & -11/2 & | & -5/2 & 0 & 1
\end{matrix}\right]

* اوپر کی میٹرکس میں دوسری قطار کو 7/2 سے ضرب دے کر جو حاصل ضرب آئے، اسے تیسری قطار میں جمع کر دو
:\left[ \begin{matrix}
1 & 3/2 & -1/2 & | & 1/2 & 0 & 0\\
0 & 1 & -11/13 & | & 3/13 & -2/13 & 0\\
0 & 0 & -110/13 & | & -22/13 & -7/13 & 1
\end{matrix}\right]

* اوپر کی میٹرکس میں تیسری قطار کو -13/110 سے ضرب دو
:\left[ \begin{matrix}
1 & 3/2 & -1/2 & | & 1/2 & 0 & 0\\
0 & 1 & -11/13 & | & 3/13 & -2/13 & 0\\
0 & 0 & 1 & | & 1/5 & 7/110 & -13/110
\end{matrix}\right]

* اوپر کی میٹرکس میں تیسری قطار کو 11/13 سے ضرب دے کر جو حاصل ضرب آئے، اسے دوسری قطار میں جمع کر دو
:\left[ \begin{matrix}
1 & 3/2 & -1/2 & | & 1/2 & 0 & 0\\
0 & 1 & 0 & | & 2/5 & -1/10 & -1/10\\
0 & 0 & 1 & | & 1/5 & 7/110 & -13/110
\end{matrix}\right]

* اوپر کی میٹرکس میں تیسری قطار کو 1/2 سے ضرب دے کر جو حاصل ضرب آئے، اسے پہلی قطار میں جمع کر دو
:\left[ \begin{matrix}
1 & 3/2 & 0 & | & 3/5 & 7/220 & -13/220\\
0 & 1 & 0 & | & 2/5 & -1/10 & -1/10\\
0 & 0 & 1 & | & 1/5 & 7/110 & -13/110
\end{matrix}\right]

* اوپر کی میٹرکس میں دوسری قطار کو -3/2 سے ضرب دے کر جو حاصل ضرب آئے، اسے پہلی قطار میں جمع کر دو
:\left[ \begin{matrix}
1 & 0 & 0 & | & 0 & 2/11 & 1/11\\
0 & 1 & 0 & | & 2/5 & -1/10 & -1/10\\
0 & 0 & 1 & | & 1/5 & 7/110 & -13/110
\end{matrix}\right]

* اب ہمارے پاس بائیں طرف شناخت میٹرکس آ گئی ہے۔ اس لیے دائیں جانب میٹرکس
:\left[ \begin{matrix}
0 & 2/11 & 1/11\\
2/5 & -1/10 & -1/10\\
1/5 & 7/110 & -13/110
\end{matrix}\right]

اصل میٹرکس کا الٹ ہے۔

### نوٹ
اگر کسی مرحلہ پر تمام صفر قطار مل جائے تو اس سے یہ نتیجہ نکلتا ہے کہ میٹرکس مقلوب نہیں (یعنی الٹ ممکن نہیں)۔

### ابتدائی میٹرکسیں
اوپر ہم نے بنیادی قطار عملیات بیان کیے، جو کی یہ ہیں:
# ایک قطار کو کسی دائم عدد سے ضرب دے دو
# دو قطاروں کا باہمی تبادلہ کر دو
# ایک قطار کو کسی دائم عدد سے ضرب دینے کے بعد جو حاصل ضرب قطار ملے، اسے کسی دوسری قطار میں جمع کر دو

تعریف: ابتدائی میٹرکس:
ایسی میٹرکس جو شناخت میٹرکس پر کوئی بھی ابتدائی قطار عمل سے حاصل ہو کو *ابتدائی میٹرکس* کہتے ہیں۔

ابتدائی میٹرکس کی خوبی یہ ہے کہ اس سے کسی میٹرکس *A" کو ضرب دینے سے میٹرکس *A* پر ابتدائی قطار عمل ہو جاتا ہے۔
* مثلاً
:<math>E_1 = \left[ \begin{matrix}
1 & 0 & 0 \\
0 & 3 & 0 \\
0 & 0 & 1
\end{matrix}\right]
</math>
ابتدائی میٹرکس سے ضرب دینے سے کسی بھی <math> 3 \times m </math> میٹرکس کی دوسری قطار 3 سے ضرب کھا جاتی ہے۔
* مثلاً
:<math>E_2 = \left[ \begin{matrix}
1 & 0 & 0 \\
0 & 0 & 1 \\
0 & 1 & 0
\end{matrix}\right]
</math>
ابتدائی میٹرکس سے ضرب دینے سے کسی بھی <math> 3 \times m </math> میٹرکس کی دوسری اور تیسری قطاروں کا باہمی تبادلہ ہو جاتا ہے۔
* مثلاً
:<math>E_3 = \left[ \begin{matrix}
1 & 0 & 2 \\
0 & 1 & 0 \\
0 & 0 & 1
\end{matrix}\right]
</math>
ابتدائی میٹرکس سے ضرب دینے سے کسی بھی <math> 3 \times m </math> میٹرکس کی پہلی قطار میں تیسری قطار کا 2 سے حاصل ضرب جمع ہو جاتا ہے۔
* ابتدائی میٹرکس =Elementary matrix

ابتدائی میٹرکس ہمیشہ [[مقلوب میٹرکس]] ہوتی ہے۔

=== میٹرکس الٹ طریقہ کی وجہ ===
اوپر ہم نے میٹرکس الٹ نکالنے کا طریقہ بنیادی قطار عملیات کے ذریعہ نکالنے کا طریقہ بیان کیا جس میں <math>n \times n</math> میٹرکس *A* کا الٹ نکالنے کے لیے افزائش میٹرکس <math>\ [A|I_n]</math> پر بنیادی قطار عملیات کیے جاتے ہیں حتی کہ افزائش میٹرکس کا روپ <math>\ [I_n|B]</math> ہو جائے۔ یعنی افزائش میٹرکس کا *A* والا حصہ شناخت میٹرکس میں تبدیل ہو جائے۔ اس طریقہ کو ابتدائی میٹرکس کی مدد سے یوں سمجھا جا سکتا ہے۔ فرض کرو کہ میٹرکس پر بنیاد قطار عمل ان *K* ابتدائی میٹرکس (میٹرکسوں) سے ضرب کے برابر ہیں:
:<math>\ I_n = E_K E_{K-1} \cdots E_1 A</math>
تو میٹرکس الجبرا کی رو سے 
:<math>\ A^{-1} = E_K E_{K-1} \cdots E_1 I_n </math>
یعنی وہی عمل شناخت میٹرکس کو *A'' کے الٹ میں بدل دیں گے۔

## مزید دیکھیے
* یکلخت لکیری مساوات کا نظام
* مقلوب میٹرکس
* سائیلیب help slash

## بیرونی روابط
* سائیلیب سبق

زمرہ:خطی الجبرا
زمرہ:ویکی ڈیٹا سے مطابقت رکھنے والی مختصر تفصیل