حذف غاوسي

في الجبر الخطي، الحذف الغاوسي (بالإنجليزية: Gaussian elimination)‏ هو خوارزمية مفيدة لحل منظومات من المعادلات الخطية وإيجاد رتبة مصفوفة وحساب معكوس مصفوفة مربعة انعكاسية.^[1]^[2] تم إعطاء هذا الاسم تقديرا للرياضياتي الألماني كارل فريدريك غاوس. يتم تطبيق عمليات الصف الأساسية لتخفيض المصفوفة على صورة مصفوفة مثلثية. يمكن تعميم هذه الخوارزمية باستخدام حذف غاوس جوردان، لتخفيض المصفوفة إلى صورة مصفوفة مثلثية مخفضة ومع ذلك فإن استعمال الحذف الغاوسي بمفرده كاف لأي تطبيق.

[\begin{matrix} 1 & 3 & 1 & 9 \\ 1 & 1 & - 1 & 1 \\ 3 & 11 & 5 & 35 \end{matrix}] \to [\begin{matrix} 1 & 3 & 1 & 9 \\ 0 & - 2 & - 2 & - 8 \\ 0 & 2 & 2 & 8 \end{matrix}] \to [\begin{matrix} 1 & 3 & 1 & 9 \\ 0 & - 2 & - 2 & - 8 \\ 0 & 0 & 0 & 0 \end{matrix}] \to [\begin{matrix} 1 & 0 & - 2 & - 3 \\ 0 & 1 & 1 & 4 \\ 0 & 0 & 0 & 0 \end{matrix}]

مثال

لنفرض أن الغرض هو إيجاد ووصف الحل أو الحلول الممكنة إذا كان أي من نظام المعادلات الخطية التالية:

\begin{array}{r} 2 x + y - z & = 8 & (L_{1}) \\ - 3 x - y + 2 z & = - 11 & (L_{2}) \\ - 2 x + y + 2 z & = - 3 & (L_{3}) \end{array}

تكون الخوارزمية كما يلي: إعزل $x$ عن جميع المعادلات تحت $L_{1}$ , ومن ثم إعزل $y$ عن جميع المعادلات تحت $L_{2}$ . هذا سيجعل النظام على صورة مثلثية. حينئذ، باستعمال التعويض الخلفي، يمكن حل كل واحدة غير معلومة.

في هذا المثال سوف يتم عزل $x$ عن $L_{2}$ بإضافة $\begin{matrix} \end{matrix} L_{1}$ إلى $L_{2}$ , كما يتم عزل $x$ عن $L_{3}$ بإضافة $L_{1}$ إلى $L_{3}$ . بشكل رسمي:

L_{2} + \frac{3}{2} L_{1} \to L_{2}

L_{3} + L_{1} \to L_{3}

والنتيجة تكون:

2 x + y - z = 8

\frac{1}{2} y + \frac{1}{2} z = 1

2 y + z = 5

والآن بعزل $y$ عن $L_{3}$ بإضافة $- 4 L_{2}$ إلى $L_{3}$ :

L_{3} + - 4 L_{2} \to L_{3}

تصبح النتيجة:

2 x + y - z = 8

\frac{1}{2} y + \frac{1}{2} z = 1

- z = 1

هذه النتيجة هي نظام معادلات خطية بالصورة المثلثية، وبالتالي يكون الجزء الأول من الخوارزمية قد اكتمل.

القسم الثاني وهو التعويض الخلفي. يتكون من حل المجاهيل في ترتيب عكسي. وعليه يمكن بسهولة ملاحظة أن

z = - 1 (L_{3})

وعليه, $z$ يمكن تعويضها في $L_{2}$ , والتي يمكن حلها بسهولة لإيجاد

y = 3 (L_{2})

ثانيا, $z$ و $y$ يمكن تعويضها $L_{1}$ , والتي يمكن حلها لإيجاد

x = 2 (L_{1})

وبالتالي تم حل النظام.

تطبيقات

انظر إلى نظام معادلات خطية.

انظر أيضاً

المراجع

^ Fang، Xin Gui؛ Havas، George (1997). "On the worst-case complexity of integer Gaussian elimination" (PDF). Proceedings of the 1997 international symposium on Symbolic and algebraic computation. Kihei, Maui, Hawaii, United States: ACM. ص. 28–31. DOI:10.1145/258726.258740. ISBN:0-89791-875-4. مؤرشف من الأصل (PDF) في 2020-02-23. {{استشهاد بمنشورات مؤتمر}}: الوسيط |عنوان المؤتمر= و|عنوان الكتاب= تكرر أكثر من مرة (مساعدة)
^ Timothy Gowers؛ June Barrow-Green؛ Imre Leader (8 سبتمبر 2008). The Princeton Companion to Mathematics. Princeton University Press. ص. 607. ISBN:978-0-691-11880-2.

[1] Fang، Xin Gui؛ Havas، George (1997). "On the worst-case complexity of integer Gaussian elimination" (PDF). Proceedings of the 1997 international symposium on Symbolic and algebraic computation. Kihei, Maui, Hawaii, United States: ACM. ص. 28–31. DOI:10.1145/258726.258740. ISBN:0-89791-875-4. مؤرشف من الأصل (PDF) في 2020-02-23. {{استشهاد بمنشورات مؤتمر}}: الوسيط |عنوان المؤتمر= و|عنوان الكتاب= تكرر أكثر من مرة (مساعدة)

[2] Timothy Gowers؛ June Barrow-Green؛ Imre Leader (8 سبتمبر 2008). The Princeton Companion to Mathematics. Princeton University Press. ص. 607. ISBN:978-0-691-11880-2.

[1]

[2]