گاسین اخراج

وکیپیڈیا سے

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 پر ابتدائی قطار عمل ہو جاتا ہے۔

مثلاً

$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 کے الٹ میں بدل دیں گے۔

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

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

سائیلیب سبق

        اردو ویکیپیڈیا پر ریاضی مساوات کو بائیں سے دائیں (LTR) پڑھیۓ        ریاضی علامات

Retrieved from "http://ur.wikipedia.org../../../%DA%AF/%D8%A7/%D8%B3/%DA%AF%D8%A7%D8%B3%DB%8C%D9%86_%D8%A7%D8%AE%D8%B1%D8%A7%D8%AC.html"

زمرہ جات: لکیری الجبرا | ریاضیات

گاسین اخراج

وکیپیڈیا سے

فہرست

[ترمیم] مثال

[ترمیم] مٰیٹرکس کا اُلٹ نکالنا

[ترمیم] مثال

[ترمیم] نوٹ

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

[ترمیم] میٹرکس الٹ طریقہ کی وجہ

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

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

Views

رہنمائی

ساتھی منصوبے

تلاش

دیگر زبانیں