گاسین اخراج

* 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

## باہرلے جوڑ
* سائیلیب سبق

گٹھ:لکیری الجبرا
گٹھ:ریاضی