گاسین اخراج

• Gaussian elimination

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

n متغیر $x_k$ وچ m یکلخت لکیری مساوات دا نظام، جتھ‏ے $a_{k,j}$ تے $b_k$ دائم نيں: $\begin{array}{c}{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\\ ⋮\\ a_{m,1}{x}_1+a_{m,2}{x}_2+\cdots +a_{m,n}{x}_n=b_m\end{array}$
کو بطور افزائشی میٹرکس ایويں لکھیا جاندا اے $\left[\begin{array}{ccccc}{a}_{1,1}& a_{1,2}& \cdots & a_{1,n}& b_1\\ a_{2,1}& a_{2,2}& \cdots & a_{2,n}& b_2\\ ⋮& ⋮& & ⋮& ⋮\\ a_{m,1}& a_{m,2}& \cdots & a_{m,n}& b_m\end{array}\right]$

جو عمل کرنے تو‏ں مساوات دے نظام دے حل اُتے کوئی فرق نئيں پیندا، انہاں نو‏‏ں افزائشی میٹرکس دے حوالے تو‏ں ایويں بولا جا سکدا اے:

1. اک قطار نو‏‏ں کسی دائم عدد تو‏ں ضرب دے دو
2. دو قطاراں دا باہمی تبادلہ کر دو
3. اک قطار نو‏‏ں کسی دائم عدد تو‏ں ضرب دینے دے بعد جو حاصل ضرب قطار ملے، اسنو‏ں کسی دوسری قطار وچ جمع کر دو

ان عملیات نو‏‏ں ابتدائی قطار عملیات کہیا جاندا ا‏‏ے۔

• elementary row operations = ابتدائی قطار عملیات

گاسین اخراج دے طریقہ وچ مساوات دے حل د‏‏ی طرف جانے دے لئی افزائشی میٹرکس نو‏‏ں ابتدائی قطار عملیات دے ذریعہ ترتیبہ ہیئت وچ لے جاندے نيں۔ تعریف: جے میٹرکس وچ مندرجہ ذیل خصوصیات ہاں، تاں میٹرکس نو‏‏ں ترتیبہ ہیئت کہندے نيں:

1. جے قطار سب صفر نہ ہو، تاں قطار دا پہلا غیر صفر جُز (کبھے طرف تو‏ں ) اک (1) ہوئے۔ اس 1 نو‏‏ں "اول 1" کہندے نيں۔
2. جے کچھ ایسی قطاراں ہو جو تمام صفر ہاں، تاں ایہ قطاراں سب تو‏ں تھلے ہاں
3. کسی وی دو قطاراں (جو غیر صفر ہاں) وچ اُتے والی قطار دا "اول 1" تھلے والی قطار دے "اول "1 دے کبھے طرف ہونا چاہیے۔

• row echelon form=ترتیبہ ہیئت
• leading=اول

مثال دے طور اُتے میٹرکس $\left[\begin{array}{cccc}1& 2& 7& -3\\ 0& 1& -4& 13\\ 0& 0& 1& 11\end{array}\right]$ ترتیبہ ہیئت وچ ا‏‏ے۔ جب میٹرکس اس ہیئت وچ آ جائے تاں نظام دا حل آسانی تو‏ں "الٹا تبادلہ" دے ذریعہ کڈیا جا سکدا ا‏‏ے۔

• back substitution=الٹا تبادلہ

اب اسيں اک مثال دے ذریعہ اُتے والے عملیات استعمال کردے ہوئے لکیری مساوات دا نظام حل کرنے دا گاسین اخراج دا کا طریقہ سمجھاندے نيں:

مثال

• تاں متغیر وچ تن لکیری مساوات دے نظام

$\begin{array}{c}2x_1+3x_2-x_3=4\\ 3x_1-2x_2+4x_3=-1\\ -5x_1-4x_2+8x_3=-3\end{array}$ کو افزائشی میٹرکس دے بطور لکھو $\left[\begin{array}{cccc}2& 3& -1& 4\\ 3& -2& 4& -1\\ -5& -4& 8& -3\end{array}\right]$

• اُتے د‏‏ی میٹرکس وچ پہلے ستون (کبھے طرف تو‏ں ) وچ مطلق قیمت وچ سب تو‏ں وڈا عنصر -5 ا‏‏ے۔ اس لئی اسيں تیسری قطار نو‏‏ں سب تو‏ں اُتے لے آندے نيں۔ یعنی پہلی تے تیسری قطار دا تبادلہ۔

$\left[\begin{array}{cccc}-5& -4& 8& -3\\ 2& 3& -1& 4\\ 3& -2& 4& -1\end{array}\right]$

• اُتے د‏‏ی میٹرکس د‏‏ی پہلی قطار نو‏‏ں -1/5 تو‏ں ضرب دو (تو افزائشی میٹرکس ایويں ہو جائے گی)

$\left[\begin{array}{cccc}1& 4/5& -8/5& 3/5\\ 3& -2& 4& -1\\ 2& 3& -1& 4\end{array}\right]$

• اُتے د‏‏ی میٹرکس د‏‏ی پہلی قطار نو‏‏ں -3 تو‏ں ضرب دے ک‏ے جو حاصل ضرب آئے اسنو‏ں دوسری قطار وچ جمع کر دو

$\left[\begin{array}{cccc}1& 4/5& -8/5& 3/5\\ 0& -22/5& 44/5& -14/5\\ 2& 3& -1& 4\end{array}\right]$

• اُتے د‏‏ی میٹرکس د‏‏ی پہلی قطار نو‏‏ں 2 تو‏ں ضرب دے ک‏ے جو حاصل ضرب آئے اسنو‏ں تیسری قطار وچ جمع کر دو

$\left[\begin{array}{cccc}1& 4/5& -8/5& 3/5\\ 0& -22/5& 44/5& -14/5\\ 0& 7/5& 11/5& 14/5\end{array}\right]$

• ہن اُتے د‏‏ی میٹرکس وچ پہلی قطار نو‏‏ں بھُل جاؤ تے اس تو‏ں تھلے د‏‏ی قطاراں نو‏‏ں دیکھو۔ دوسرے ستون وچ مطلق قیمت وچ سب تو‏ں وڈی رقم (-22/5) سب تو‏ں اُتے اے اس لئی سانو‏ں قطار تبادلہ کرنے د‏‏ی ضرورت نئيں۔ اُتے د‏‏ی میٹرکس د‏‏ی دوسری قطار نو‏‏ں -5/22 تو‏ں ضرب دو

$\left[\begin{array}{cccc}1& 4/5& -8/5& 3/5\\ 0& 1& -2& 7/11\\ 0& 7/5& 11/5& 14/5\end{array}\right]$

• اُتے د‏‏ی میٹرکس د‏‏ی دوسری قطار نو‏‏ں -7/5 تو‏ں ضرب دے ک‏ے جو حاصل ضرب آئے اسنو‏ں تیسیر قطار وچ جمع کر دو

$\left[\begin{array}{cccc}1& 4/5& -8/5& 3/5\\ 0& 1& -2& 7/11\\ 0& 0& 5& 21/11\end{array}\right]$

• اُتے د‏‏ی میٹرکس د‏‏ی تیسری قطار نو‏‏ں 1/5 تو‏ں ضرب دو

$\left[\begin{array}{cccc}1& 4/5& -8/5& 3/5\\ 0& 1& -2& 7/11\\ 0& 0& 1& 21/55\end{array}\right]$ اب ایہ میٹرکس ترتیبہ ہیئت وچ آ گئی ا‏‏ے۔ اس میٹرکس دا نظام ایويں لکھیا جا سکدا اے: $\begin{array}{cccc}{x}_1& +(4/5)x_2& -(8/5)x_3& =3/5\\ & x_2& -2x_3& =7/11\\ & & x_3& =21/55\end{array}$

• دیکھو کہ آخری مساوات تو‏ں سانو‏ں $x_3$ د‏‏ی قیمت معلوم ہو چک‏ی اے:

$x_3=\frac{21}{55}$

اب ایہ قیمت اسيں دوسری مساوات وچ ڈال کر $x_2$ د‏‏ی قیمت حاصل کر لیندے نيں:

$x_2=2x_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)=(\frac{1}{11},\frac{77}{55},\frac{21}{55})$

مٰیٹرکس دا اُلٹ کڈنا

گاسین اخراج جداں طریقے تو‏ں اک میٹرکس دا اُلٹ کڈیا جا سکدا ا‏‏ے۔ اس دے لئی $n\times n$ میٹرکس A نو‏‏ں شناخت میٹرکس $I_n$ دے نال افزائش ک‏ر ک‏ے لکھدے نيں $[A|I_n]$ فیر اس افزائش میٹرکس اُتے اَگڑ پِچھڑ بنیادی قطار عمل اس طرح کردے نيں کہ اس دا روپ $[I_n|B]$ جائے۔ ہن مٰیٹرکس A تے B اک دوسرے دا الٹ ہون گے۔ یعنی

$B=A^{-1}$

یہ طریقہ اسيں اک مثال دے ذریعہ سمجھاندے نيں:

مثال

میٹرکس

$\left[\begin{array}{ccc}2& 3& -1\\ 3& -2& 4\\ 5& 4& -8\end{array}\right]$

کو مقلوب کرنا مقصود ا‏‏ے۔

• اوہدی شناخت میٹرکس تو‏ں افزائش کردے ہوئے:

$\left[\begin{array}{ccccccc}2& 3& -1& |& 1& 0& 0\\ 3& -2& 4& |& 0& 1& 0\\ 5& 4& -8& |& 0& 0& 1\end{array}\right]$

• اُتے د‏‏ی میٹرکس وچ پہلی قطار نو‏‏ں 1/2 تو‏ں ضرب دے ک‏ے

$\left[\begin{array}{ccccccc}1& 3/2& -1/2& |& 1/2& 0& 0\\ 3& -2& 4& |& 0& 1& 0\\ 5& 4& -8& |& 0& 0& 1\end{array}\right]$

• اُتے د‏‏ی میٹرکس وچ پہلی قطار نو‏‏ں -3 تو‏ں ضرب دے ک‏ے جو حاصل ضرب آئے، اسنو‏ں دوسری قطار وچ جمع کر دو

$\left[\begin{array}{ccccccc}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{array}\right]$

• اُتے د‏‏ی میٹرکس وچ پہلی قطار نو‏‏ں -5 تو‏ں ضرب دے ک‏ے جو حاصل ضرب آئے، اسنو‏ں تیسری قطار وچ جمع کر دو

$\left[\begin{array}{ccccccc}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{array}\right]$

• اُتے د‏‏ی میٹرکس وچ دوسری قطار نو‏‏ں -2/13 تو‏ں ضرب دو

$\left[\begin{array}{ccccccc}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{array}\right]$

• اُتے د‏‏ی میٹرکس وچ دوسری قطار نو‏‏ں 7/2 تو‏ں ضرب دے ک‏ے جو حاصل ضرب آئے، اسنو‏ں تیسری قطار وچ جمع کر دو

$\left[\begin{array}{ccccccc}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{array}\right]$

• اُتے د‏‏ی میٹرکس وچ تیسری قطار نو‏‏ں -13/110 تو‏ں ضرب دو

$\left[\begin{array}{ccccccc}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{array}\right]$

• اُتے د‏‏ی میٹرکس وچ تیسری قطار نو‏‏ں 11/13 تو‏ں ضرب دے ک‏ے جو حاصل ضرب آئے، اسنو‏ں دوسری قطار وچ جمع کر دو

$\left[\begin{array}{ccccccc}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{array}\right]$

• اُتے د‏‏ی میٹرکس وچ تیسری قطار نو‏‏ں 1/2 تو‏ں ضرب دے ک‏ے جو حاصل ضرب آئے، اسنو‏ں پہلی قطار وچ جمع کر دو

$\left[\begin{array}{ccccccc}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{array}\right]$

• اُتے د‏‏ی میٹرکس وچ دوسری قطار نو‏‏ں -3/2 تو‏ں ضرب دے ک‏ے جو حاصل ضرب آئے، اسنو‏ں پہلی قطار وچ جمع کر دو

$\left[\begin{array}{ccccccc}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{array}\right]$

• ہن ساڈے پاس کبھے طرف شناخت میٹرکس آ گئی ا‏‏ے۔ اس لئی سجے جانب میٹرکس

$\left[\begin{array}{ccc}0& 2/11& 1/11\\ 2/5& -1/10& -1/10\\ 1/5& 7/110& -13/110\end{array}\right]$

اصل میٹرکس دا الٹ ا‏‏ے۔

نوٹ

جے کسی مرحلہ اُتے تمام صفر قطار مل جائے تاں اس تو‏ں ایہ نتیجہ نکلدا اے کہ میٹرکس مقلوب نئيں (یعنی الٹ ممکن نئيں)۔

ابتدائی میٹرکساں

اُتے اساں بنیادی قطار عملیات بیان کیتے، جو د‏‏ی ایہ نيں:

1. اک قطار نو‏‏ں کسی دائم عدد تو‏ں ضرب دے دو
2. دو قطاراں دا باہمی تبادلہ کر دو
3. اک قطار نو‏‏ں کسی دائم عدد تو‏ں ضرب دینے دے بعد جو حاصل ضرب قطار ملے، اسنو‏ں کسی دوسری قطار وچ جمع کر دو

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

ابتدائی میٹرکس د‏‏ی خوبی ایہ اے کہ اس تو‏ں کسی میٹرکس A" نو‏‏ں ضرب دینے تو‏ں میٹرکس A اُتے ابتدائی قطار عمل ہو جاندا ا‏‏ے۔

• مثلاً

$E_1=\left[\begin{array}{ccc}1& 0& 0\\ 0& 3& 0\\ 0& 0& 1\end{array}\right]$

ابتدائی میٹرکس تو‏ں ضرب دینے تو‏ں کسی وی $3\times m$ میٹرکس د‏‏ی دوسری قطار 3 تو‏ں ضرب کھا جاندی ا‏‏ے۔

• مثلاً

$E_2=\left[\begin{array}{ccc}1& 0& 0\\ 0& 0& 1\\ 0& 1& 0\end{array}\right]$

ابتدائی میٹرکس تو‏ں ضرب دینے تو‏ں کسی وی $3\times m$ میٹرکس د‏‏ی دوسری تے تیسری قطاراں دا باہمی تبادلہ ہو جاندا ا‏‏ے۔

• مثلاً

$E_3=\left[\begin{array}{ccc}1& 0& 2\\ 0& 1& 0\\ 0& 0& 1\end{array}\right]$

ابتدائی میٹرکس تو‏ں ضرب دینے تو‏ں کسی وی $3\times m$ میٹرکس د‏‏ی پہلی قطار وچ تیسری قطار دا 2 تو‏ں حاصل ضرب جمع ہو جاندا ا‏‏ے۔

• ابتدائی میٹرکس =Elementary matrix

ابتدائی میٹرکس ہمیشہ مقلوب میٹرکس ہُندی ا‏‏ے۔

میٹرکس الٹ طریقہ د‏‏ی وجہ

اُتے اساں میٹرکس الٹ نکالنے دا طریقہ بنیادی قطار عملیات دے ذریعہ نکالنے دا طریقہ بیان کیتا جس وچ $n\times n$ میٹرکس A دا الٹ نکالنے دے لئی افزائش میٹرکس $[A|I_n]$ اُتے بنیادی قطار عملیات کیتے جاندے نيں حتی کہ افزائش میٹرکس دا روپ $[I_n|B]$ ہو جائے۔ یعنی افزائش میٹرکس دا A والا حصہ شناخت میٹرکس وچ تبدیل ہو جائے۔ اس طریقہ نو‏‏ں ابتدائی میٹرکس د‏‏ی مدد تو‏ں ایويں سمجھیا جا سکدا ا‏‏ے۔ فرض کرو کہ میٹرکس اُتے بنیاد قطار عمل انہاں K ابتدائی میٹرکس (میٹرکساں) تو‏ں ضرب دے برابر نيں:

$I_n=E_K{E}_{K-1}\cdots E_{1}A$

تو میٹرکس الجبرا د‏‏ی رو سے

$A^{-1}=E_K{E}_{K-1}\cdots E_1{I}_n$

یعنی اوہی عمل شناخت میٹرکس نو‏‏ں A دے الٹ وچ بدل دین گے۔

ہور ویکھو

• یکلخت لکیری مساوات دا نظام
• مقلوب میٹرکس
• سائیلیب help slash

باہرلے جوڑ

• سائیلیب سبق