الخوارزمية الأساسية
الحذف الغاوسي هو الإجراء المنهجي لحل الأنظمة الخطية. بدءًا من المصفوفة المعززة [A|b]، يُطبّق سلسلة من عمليات الصفوف البسيطة لتحويل المصفوفة إلى صورة مثلثية علوية — تُسمى الصورة الدرجية للصفوف — يمكن من خلالها استعادة الحل بالتعويض العكسي. نسخة موسّعة من الخوارزمية تستمر أكثر لتُنتج الصورة الدرجية المختزلة، حيث يمكن قراءة الحل مباشرةً دون أي تعويض.
الخوارزمية ليست مجرد تقنية يدوية، بل هي أساس كل مكتبات الجبر الخطي العددي تقريبًا — من عامل الشرطة المائلة في MATLAB إلى دالة linalg.solve في NumPy. فهمها يمنحك بصيرة حول سبب تصرّف المُحلّلات العددية كما تتصرف، وما الذي قد يسوء حين تكون المصفوفة قريبة من الشذوذ.
عمليات الصفوف الأولية
الفكرة الجوهرية وراء الحذف الغاوسي هي أن بعض العمليات على صفوف المصفوفة المعززة لا تُغيّر مجموعة حلولها. هذه هي عمليات الصفوف الأولية الثلاث:
المصفوفة المعززة كنقطة انطلاق
قبل البدء في الحذف، اكتب النظام على صورة مصفوفته المعززة [A|b]. الشريط العمودي يفصل مصفوفة المعاملات A على اليسار عن متجه الطرف الأيمن b على اليمين. كل عملية صفوف تُطبَّق على [A|b] تُحوّل كلا النصفين في آنٍ واحد، محافظةً على التكافؤ بين المصفوفة ونظام المعادلات الأصلي.
كتابة المعادلات بالكامل — مع رموز x₁، x₂، x₃ — أمر مُضنٍ وعُرضة للأخطاء. المصفوفة المعززة تُجرّد أسماء المتغيرات وتكشف الأرقام المهمة فقط. تصبح عمليات الصفوف خطوات آلية نظيفة بدلًا من معالجات جبرية، وهذا بالضبط سبب استخدام الحواسيب لهذا التمثيل.
الصورة الدرجية للصفوف
هدف مرحلة الحذف الأمامي هو الوصول إلى الصورة الدرجية للصفوف (REF). تكون المصفوفة في الصورة الدرجية إذا استوفت ثلاثة شروط:
- جميع الصفوف الصفرية (إن وُجدت) تكون في الأسفل.
- أول عنصر غير صفري في كل صف غير صفري — يُسمى العنصر الرائد أو عنصر المحور — يقع بدقة إلى يمين عنصر المحور في الصف الذي فوقه.
- جميع العناصر تحت عنصر المحور في العمود نفسه تساوي صفرًا.
يُنشئ هذا نمطًا درجيًا ينزل من أعلى اليسار إلى أسفل اليمين. مواضع عناصر المحور تُسمى مواضع المحاور، والأعمدة التي تحتويها تُسمى أعمدة المحاور. الأعمدة التي لا تحتوي محاور تقابل المتغيرات الحرة — المجاهيل التي يمكن أن تأخذ أي قيمة حين يكون للنظام حلول لا نهائية.
الصورة الدرجية المختزلة
الصورة الدرجية كافية للتعويض العكسي، لكن استمرار عملية الحذف — الآن صعودًا لإصفار العناصر فوق كل محور، وتحجيم كل محور ليصبح 1 — يُنتج الصورة الدرجية المختزلة (RREF). تستلزم الصورة الدرجية المختزلة شرطين إضافيين فوق الصورة الدرجية:
- كل عنصر محور يساوي 1 بالضبط (يتحقق بتحجيم صف المحور).
- كل عنصر فوق محور يساوي صفرًا أيضًا (يتحقق بإضافة مضاعفات صفوف المحاور إلى الصفوف التي فوقها).
في الصورة الدرجية المختزلة، يمكن قراءة الحل مباشرةً: كل متغير محوري مُعبَّر عنه فقط بدلالة المتغيرات الحرة (إن وُجدت)، دون الحاجة إلى تعويض. بالنسبة لنظام له حل وحيد، تكون الصورة الدرجية المختزلة للمصفوفة المعززة على الشكل [I|x*]، حيث I هي مصفوفة الوحدة وx* هو متجه الحل.
التعويض العكسي
إذا توقفت عند الصورة الدرجية بدلًا من الاستمرار إلى الصورة الدرجية المختزلة، تُستعاد قيم المجاهيل عبر التعويض العكسي. الإجراء بسيط: الصف غير الصفري الأخير في الصورة الدرجية يُعطي قيمة آخر متغير محوري مباشرةً. عوّض بهذه القيمة في المعادلة قبل الأخيرة للحصول على المتغير المحوري التالي. استمر صعودًا حتى تتحدد جميع المجاهيل.
لنظام 3×3 في الصورة الدرجية بمحاور a وd وf، الخطوات هي:
- اقرأ x₃ من الصف الأخير: fx₃ = r₃، إذن x₃ = r₃/f.
- عوّض بـ x₃ في الصف الثاني للحصول على x₂.
- عوّض بـ x₂ وx₃ في الصف الأول للحصول على x₁.
التعويض العكسي يكلّف O(n²) لنظام n×n — أرخص من مرحلة الحذف الأمامي التي تكلف O(n³) — مما يجعل التكلفة الإجمالية لحل Ax = b يهيمن عليها خطوة الحذف.
مثال عملي محلول
لنحل النظام الذي تظهر صورته الدرجية والصورة الدرجية المختزلة في كتل المعادلات أعلاه:
- 2x₁ + x₂ − x₃ = 8
- −3x₁ − x₂ + 2x₃ = −11
- −2x₁ + x₂ + 2x₃ = −3
الخطوة 1 — كتابة المصفوفة المعززة
رتّب المعاملات والأطراف اليمنى في [A|b]:
[ 2، 1، −1 | 8 ] / [ −3، −1، 2 | −11 ] / [ −2، 1، 2 | −3 ]
الخطوة 2 — الحذف تحت أول محور (المحور = 2، العمود 1)
استخدم R₁ لإصفار العناصر تحته في العمود 1. طبّق R₂ ← R₂ + (3/2)R₁ وR₃ ← R₃ + R₁. بعد هذه العمليات يصبح العمود الأول أصفارًا تحت المحور وتبدأ المصفوفة بأخذ شكلها المثلثي العلوي.
الخطوة 3 — الحذف تحت المحور الثاني (العمود 2)
المحور الثاني هو العنصر الجالس الآن في الصف 2، العمود 2. استخدمه لإصفار العنصر في الصف 3، العمود 2 عبر R₃ ← R₃ − (مضاعف مناسب)·R₂. بعد هذه الخطوة تكون المصفوفة في الصورة الدرجية، مطابقةً للشكل المثلثي العلوي الظاهر في كتلة المعادلة أعلاه.
الخطوة 4 — التعويض العكسي
من الصف الأخير: 5x₃ = −5، إذن x₃ = −1. بالتعويض في الصف الثاني: 3x₂ + 2(−1) = 11، فنحصل على x₂ = 3. بالتعويض في الصف الأول: 2x₁ + 3 − (−1) = 8، فنحصل على x₁ = 2. هذا يتطابق مع حل الصورة الدرجية المختزلة [2، 3، −1]ᵀ.
تحقّق دائمًا بتعويض x = [2، 3، −1]ᵀ في المعادلات الأصلية: 2(2) + 3 − (−1) = 8 ✓، −3(2) − 3 + 2(−1) = −11 ✓، −2(2) + 3 + 2(−1) = −3 ✓.
الإزاحة الجزئية للاستقرار العددي
في الحساب الدقيق، الحذف الغاوسي يعمل دائمًا (طالما النظام له حل). في الحساب العائم بالنقطة، تنشأ مشكلات حين يكون المحور صفرًا أو صغيرًا جدًا: القسمة على عدد صغير جدًا تُضخّم أخطاء التقريب، مما يُسبّب تشوّهًا كبيرًا في الحل المحسوب حتى دون ارتكاب أي خطأ في الحساب الدقيق.
الإزاحة الجزئية تعالج هذا باختيار العنصر الأكبر قيمةً مطلقةً في العمود الحالي دائمًا محورًا، وإجراء تبديل الصفوف اللازم قبل الحذف. هذا يجعل جميع المضاعفات (c = عنصر/محور) محدودةً بقيمة مطلقة لا تتجاوز 1، مما يمنع تضخيم الأخطاء خلال مرحلة الحذف.
عمليًا، كل المُحلّلات العددية تستخدم الإزاحة الجزئية افتراضيًا. المقايضة هي تكلفة إدارية طفيفة (تتبّع تبديلات الصفوف عبر متجه التباديل)، لكن الربح في الاستقرار لا غنى عنه للحساب الموثوق.
يستخدم الحذف الغاوسي ثلاث عمليات صفوف أولية — التبديل والقياس وإضافة المضاعفات — لتحويل المصفوفة المعززة [A|b] دون تغيير مجموعة حلولها. مرحلة الحذف الأمامي تُنتج الصورة الدرجية للصفوف، وهي نمط درجي بأصفار تحت كل محور. الاستمرار صعودًا يُنتج الصورة الدرجية المختزلة، حيث يُقرأ الحل مباشرةً. التعويض العكسي على الصورة الدرجية يكافئ حسابيًا. الإزاحة الجزئية — اختيار أكبر محور متاح — ضرورية للاستقرار العددي في الحساب العائم بالنقطة. التالي: ماذا يكشف شكل الصورة الدرجية المختزلة عن أنواع حلول النظام.