گاسین اخراج

آزاد دائرۃ المعارف، ویکیپیڈیا سے
:چھلانگ بطرف رہنمائی، تلاش
  • 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]

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

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

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

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

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

  1. اگر قطار سب صفر نہ ہو، تو قطار کا پہلا غیرصفر جُز (بائیں طرف سے) ایک (1) ہو۔ اس 1 کو "اول 1" کہتے ہیں۔
  2. اگر کچھ ایسی قطاریں ہو جو تمام صفر ہوں، تو یہ قطاریں سب سے نیچے ہوں
  3. کسی بھی دو قطاروں (جو غیر صفر ہوں) میں اوپر والی قطار کا "اول 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]

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

نوٹ[ترمیم]

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

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

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

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

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

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

  • مثلاً
E_1 =  \left[ \begin{matrix}
1  &   0   &  0 \\
0  &   3   &  0 \\
0  &   0   &  1
\end{matrix}\right]

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

  • مثلاً
E_2 =  \left[ \begin{matrix}
1  &   0   &  0 \\
0  &   0   &  1 \\
0  &   1   &  0
\end{matrix}\right]

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

  • مثلاً
E_3 =  \left[ \begin{matrix}
1  &   0   &  2 \\
0  &   1   &  0 \\
0  &   0   &  1
\end{matrix}\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 کے الٹ میں بدل دیں گے۔

اور دیکھو[ترمیم]

بیرونی روابط[ترمیم]

E=mc2     اردو ویکیپیڈیا پر ریاضی مساوات کو بائیں سے دائیں LTR پڑھیٔے     ریاضی علامات