خوارزمية حل جملة معادلات خطية (عدد المعادلات يساوي عدد المجاهيل) باستخدام طريقة الحذف لغوص:
لنفرض أنه لدينا جملة المعادلات التالية:
ونريد إيجاد قيم المجاهيل x1 و x2 و x3
سنسمي المصفوفة التالية مصفوفة الأمثال:
وسنسمي المصفوفة التالية مصفوفة الأمثال الموسعة:
يوجد عدة طرق لحل جملة المعادلات هذه أو أي جملة معادلات خطية من الدرجة n، منها:
- إيجاد مقلوب مصفوفة الأمثال وضربه بشعاع الطرف الثاني، وقد استخدمتها في ملف الإكسل المشار إليه أعلاه.
- طريقة غوص
وهي موضوع البحث
- طريقة غوص جوردان
- طريقة كولسكي
- طريقة غوص سايدل العددية
- طرق أخرى...
سنعتبر أثناء دراستنا أن جملة المعادلات الأصلية
لها حل وحيد، ولكن أثناء عملية التحليل سنختبر إن كانت مصفوفة الأمثال
نظامية أو شاذة، فإن كانت نظامية فعندها يوجد حل وحيد للجملة سنقوم بإيجاده، وإلا سنخرج من البرنامج مع رسالة خطأ تفيد أنه لا يوجد حل وحيد للجملة.
ملاحظة: نقول أن مصفوفة الأمثال شاذة إذا كان معينها (محددها) يساوي الصفر.
وقبل البدء سأذكّر بالتحويلات الأولية التي يمكننا تطبيقها على جملة المعادلات بحيث نحصل على جملة معادلات مكافئة، أي لها نفس الحل، وهذه التحويلات هي:
1- تبديل معادلتين: وهذا واضح أنه لا يغير الحل
2- ضرب طرفي معادلة بعدد لا يساوي الصفر: إذا كان لدينا طرفان متساويان فإنه بضرب كل طرف بنفس العدد سنحصل أيضاً على طرفين متساويين.
3- إضافة معادلة مضروبة بعدد إلى معادلة ثانية: أيضاً إذا كان لدينا طرفان متساويان وأضفنا إلى كل طرف عدداً ما نحصل على طرفين متساويين.
مبدأ طريقة التحويلات لغوص:
إن مبدأ الطريقة هو تحويل جملة المعادلات السابقة إلى جملة معادلات مكافئة بالشكل التالي:
أي تحويل جملة المعادلات إلى شكل مثلثي يسهل معه حساب قيم المتحولات.
ففي جملة المعادلات المكافئة، من المعادلة الثالثة نحصل على x3 بسهولة، ونعوضها في المعادلة الثانية لنحصل على x2 ونعوض القيمتين في المعادلة الأولى لنحصل على x1.
إجراء التحويلات:
إذا قسمنا المعادلة الأولى من جملة المعادلات الأولى على a11 (بفرض a11 لا يساوي الصفر) وضربناها ب a21 ثم طرحناها من المعادلة الثانية (أي طبقنا التحويل الثالث على المعادلة الثانية)، ونفس الشيء فعلناه مع المعادلة الثالثة أي قسمنا الأولى على a11 وضربناها ب a31 ثم طرحناها من الثالثة فإننا نحصل على جملة المعادلات المكافئة التالية:
إن الرقم بين قوسين فوق الحد يدل على رقم عملية التحويل.
أي أننا بهذه العملية اختصرنا الحد الأول من المعادلتين الثانية والثالثة، وسنسمي الحد a11 محور المعادلة رقم 1.
ويمكننا ترجمة ذلك بشكل رمزي كما يلي:
ولكن ماذا لو كان a11=0؟
نقوم عندها بتبديل المعادلة الأولى مع أي من المعادلات التي تليها بحيث يكون الحد ai1 لا يساوي الصفر حيث i هو رقم السطر.
فإن لم نجد، وكانت كلها تساوي الصفر؟
عندها نحكم أن مصفوفة الأمثال شاذة وليس لجملة المعادلات حل وحيد، والسبب أن إحدى المعادلات (أو أكثر) مرتبطة خطياً بمعادلات أخرى.
نعود إلى جملة المعادلات الأخيرة وسنحاول حذف (a32(1 الجديد من المعادلة الثالثة.
نكرر العملية بأن ننسى المعادلة الأولى وتصبح لدينا المعادلتين الثانية والثالثة بمجهولين، أي أننا نقسم المعادلة الثانية (الجديدة) على محورها وهو (a22(1 ونضربها ب (a32(1 ونجمعها إلى الثالثة فنحصل على جملة المعادلات المكافئة التالية:
ونترجم ذلك بشكل رمزي كما يلي:
وهكذا حذفنا الحد الثاني أيضاً من المعادلة الثالثة.
الآن يمكننا حساب المجاهيل بسهولة كما يلي:
أي بشكل رمزي:
تعميم الحالة على n معادلة:
إن عمليات التحويل تصبح بالشكل:
أي أنه لدينا ثلاث حلقات متداخلة:
1- الحلقة الأولى هي حلقة k وتبدأ من 1 وحتى n-1 وفيها نختار المحور akk
2- الحلقة الثانية وهي ضمن الأولى وهي حلقة i وتبدأ من السطر الذي يلي سطر المحور k، أي تبدأ من k+1 وتنتهي في السطر n، وهي تمثل السطر الذي سنقوم بعملية التحويل له.
3- الحلقة الثالثة وهي ضمن الثانية وهي حلقة j وتبدأ من رقم العمود الذي يلي رقم عمود المحور وهو k، أي تبدأ من k+1 وتنتهي في آخر عمود وهو n+1، على اعتبار أن كل العناصر في السطر i قبل العمود k+1 تساوي الصفر.
ملاحظة: فرضنا أن akk لا تساوي الصفر، فإن كانت كذلك نقوم بتبديل السطر k بسطر آخر يليه بحيث يكون akk الجديد لا يساوي الصفر، فإن لم يوجد قلنا أن جملة المعادلات لا تملك حلاً وحيداً، كما وضحنا ذلك سابقاً.
ملاحظة2: سيتم توضيح هذه الحلقات في البرنامج لاحقاً.
أما تفسير علاقة حساب aij فهي:
إن قيمة aij الجديدة تساوي قيمتها القديمة التي حصلنا عليها من الحساب السابق مطروحاً منها (قيمة a في نفس عمودها في سطر العنصر المحور مضروبة في قيمة a في نفس سطرها في عمود العنصر المحور ومقسومة على العنصر المحور) أي كما في الشكل:
أما حساب x في الحالة العامة فهو بالشكل:
وهنا لدينا حلقتان متداخلتان:
1- الأولى هي حلقة i وتبدأ من n وتنتهي ب 1، وهي تدل على رقم المجهول المراد حساب قيمته.
2- حلقة ضمنها وهي حلقة j وهي تستخدم للجمع، وتبدأ من i+1 وتنتهي ب n
أرجو أن يكون الشرح واضحاً، وسيتوضح أكثر إن شاء الله عند حل مثال، وأكثر عند ترجمة الخوارزمية إلى برنامج حاسوبي إن شاء الله.