خوارزمية المصفوفة ثلاثية القطر (Tridiagonal Matrix Algorithm)

وصف المصفوفة ثلاثية القطر

المصفوفة ثلاثية القطر هي مصفوفة مربعة تكون فيها جميع العناصر غير الصفرية تقع على القطر الرئيسي أو فوقه أو تحته مباشرة. رياضياً، يمكن تمثيل هذه المصفوفة بالشكل التالي:

حيث:

\(a_i\) هي العناصر الموجودة أسفل القطر الرئيسي.
\(b_i\) هي العناصر الموجودة على القطر الرئيسي.
\(c_i\) هي العناصر الموجودة فوق القطر الرئيسي.
جميع العناصر الأخرى تساوي صفرًا.

تظهر المصفوفات ثلاثية القطر بشكل شائع في حل المعادلات التفاضلية باستخدام طرق الفروق المحدودة (Finite Difference Methods) وفي مسائل الانحناء المكعّب (Cubic Spline Interpolation). طبيعتها المحددة تسمح بتطوير خوارزميات حل فعالة للغاية.

خوارزمية توماس: شرح مفصل

تعتمد خوارزمية توماس على تحليل LU للمصفوفة ثلاثية القطر، حيث يتم تفكيك المصفوفة الأصلية إلى مصفوفتين: مصفوفة مثلثية سفلية (Lower Triangular Matrix) ومصفوفة مثلثية علوية (Upper Triangular Matrix). بعد ذلك، يتم حل نظام المعادلات على مرحلتين: الحل الأمامي (Forward Sweep) والحل الخلفي (Backward Sweep).

الخطوة الأولى: التحليل (Decomposition)

تهدف هذه الخطوة إلى تفكيك المصفوفة ثلاثية القطر \(A\) إلى مصفوفتين \(L\) و \(U\) بحيث \(A = LU\). المصفوفة \(L\) مثلثية سفلية والمصفوفة \(U\) مثلثية علوية.

لنعتبر أن المصفوفة الأصلية \(A\) ممثلة بالعناصر \(a_i\), \(b_i\), \(c_i\) كما ذكرنا سابقًا. المصفوفة \(L\) سيكون لها قطر رئيسي عناصره \(l_i\) وعناصر أسفل القطر الرئيسي قيمتها 1. أما المصفوفة \(U\) سيكون لها قطر رئيسي عناصره \(u_i\) وعناصر فوق القطر الرئيسي قيمتها \(c_i\) (نفس عناصر المصفوفة الأصلية).

يمكن حساب عناصر \(l_i\) و \(u_i\) باستخدام العلاقات التالية:

\(u_1 = b_1\)
\(l_i = a_i / u_{i-1}\) for \(i = 2, 3, …, n\)
\(u_i = b_i – l_i * c_{i-1}\) for \(i = 2, 3, …, n\)

الخطوة الثانية: الحل الأمامي (Forward Sweep)

بعد الحصول على المصفوفتين \(L\) و \(U\)، يمكننا حل النظام \(Ax = d\) عن طريق حل نظامين فرعيين. أولاً، نحل النظام \(Ly = d\) لإيجاد المتجه \(y\). هذا النظام يمكن حله بسهولة باستخدام التعويض الأمامي (Forward Substitution).

لنعتبر أن المتجه \(d\) هو متجه الثوابت في نظام المعادلات الأصلي. يمكن حساب عناصر المتجه \(y\) باستخدام العلاقة التالية:

\(y_1 = d_1\)
\(y_i = d_i – l_i * y_{i-1}\) for \(i = 2, 3, …, n\)

الخطوة الثالثة: الحل الخلفي (Backward Sweep)

بعد إيجاد المتجه \(y\)، نحل النظام \(Ux = y\) لإيجاد المتجه \(x\)، وهو حل نظام المعادلات الأصلي. هذا النظام يمكن حله بسهولة باستخدام التعويض الخلفي (Backward Substitution).

يمكن حساب عناصر المتجه \(x\) باستخدام العلاقة التالية:

\(x_n = y_n / u_n\)
\(x_i = (y_i – c_i * x_{i+1}) / u_i\) for \(i = n-1, n-2, …, 1\)

مثال توضيحي

لنفترض أن لدينا نظام المعادلات التالي:

2x₁ – x₂ = 1
-x₁ + 3x₂ – x₃ = 2
-x₂ + 4x₃ = 3

يمكن تمثيل هذا النظام بالمصفوفة ثلاثية القطر التالية:

A = 2 & -1 & 0 \\ -1 & 3 & -1 \\ 0 & -1 & 4 \end{bmatrix}, d = 1 \\ 2 \\ 3 \end{bmatrix}

باستخدام خوارزمية توماس:

التحليل (Decomposition):

\(u_1 = b_1 = 2\)
\(l_2 = a_2 / u_1 = -1 / 2 = -0.5\)
\(u_2 = b_2 – l_2 * c_1 = 3 – (-0.5) * (-1) = 2.5\)
\(l_3 = a_3 / u_2 = -1 / 2.5 = -0.4\)
\(u_3 = b_3 – l_3 * c_2 = 4 – (-0.4) * (-1) = 3.6\)

الحل الأمامي (Forward Sweep):

\(y_1 = d_1 = 1\)
\(y_2 = d_2 – l_2 * y_1 = 2 – (-0.5) * 1 = 2.5\)
\(y_3 = d_3 – l_3 * y_2 = 3 – (-0.4) * 2.5 = 4\)

الحل الخلفي (Backward Sweep):

\(x_3 = y_3 / u_3 = 4 / 3.6 = 1.111\)
\(x_2 = (y_2 – c_2 * x_3) / u_2 = (2.5 – (-1) * 1.111) / 2.5 = 1.444\)
\(x_1 = (y_1 – c_1 * x_2) / u_1 = (1 – (-1) * 1.444) / 2 = 1.222\)

إذًا، الحل هو \(x = [1.222, 1.444, 1.111]\).

مزايا وعيوب خوارزمية توماس

المزايا:

الكفاءة: تعتبر خوارزمية توماس فعالة للغاية من حيث الحساب، حيث تتطلب عددًا قليلًا من العمليات الحسابية مقارنة بالخوارزميات العامة لحل أنظمة المعادلات الخطية. التعقيد الزمني للخوارزمية هو \(O(n)\)، حيث \(n\) هو حجم المصفوفة.
البساطة: الخوارزمية بسيطة نسبياً في التنفيذ، مما يجعلها سهلة الفهم والاستخدام.
استهلاك منخفض للذاكرة: نظرًا لطبيعة المصفوفة ثلاثية القطر، يمكن تخزين المصفوفة بكفاءة في الذاكرة، مما يقلل من استهلاك الذاكرة.

العيوب:

التقييد بالمصفوفات ثلاثية القطر: الخوارزمية مصممة خصيصًا للمصفوفات ثلاثية القطر ولا يمكن تطبيقها مباشرة على أنواع أخرى من المصفوفات.
الاستقرار العددي: في بعض الحالات، قد تكون الخوارزمية غير مستقرة عدديًا، خاصة إذا كانت هناك عناصر صغيرة جدًا على القطر الرئيسي. يجب اتخاذ احتياطات لضمان الاستقرار العددي، مثل استخدام المحورية الجزئية (Partial Pivoting) إذا لزم الأمر.

تطبيقات خوارزمية توماس

تستخدم خوارزمية توماس على نطاق واسع في العديد من المجالات الهندسية والعلمية، بما في ذلك:

حل المعادلات التفاضلية: تستخدم في طرق الفروق المحدودة لحل المعادلات التفاضلية العادية والجزئية.
الانحناء المكعّب: تستخدم في مسائل الانحناء المكعّب لإيجاد منحنى يمر عبر مجموعة من النقاط.
محاكاة التدفق: تستخدم في محاكاة تدفق السوائل والغازات.
التحليل الهيكلي: تستخدم في تحليل الهياكل لتحديد الإجهادات والانفعالات.
معالجة الإشارات: تستخدم في معالجة الإشارات لتصفية الإشارات وتقليل الضوضاء.

اعتبارات عملية

عند تطبيق خوارزمية توماس، يجب مراعاة بعض الاعتبارات العملية لضمان الحصول على نتائج دقيقة وموثوقة:

التحقق من صحة المدخلات: يجب التأكد من أن المصفوفة هي بالفعل مصفوفة ثلاثية القطر وأن نظام المعادلات قابل للحل.
التعامل مع الأخطاء: يجب تضمين آليات للتعامل مع الأخطاء المحتملة، مثل القسمة على صفر أو عدم الاستقرار العددي.
التحسين: يمكن تحسين أداء الخوارزمية باستخدام تقنيات مثل التوازي (Parallelization) إذا كانت المشكلة كبيرة بما يكفي.

خاتمة

خوارزمية المصفوفة ثلاثية القطر، أو خوارزمية توماس، هي أداة قوية وفعالة لحل أنظمة المعادلات الخطية التي تتضمن مصفوفات ثلاثية القطر. بفضل بساطتها وكفاءتها، تستخدم على نطاق واسع في العديد من التطبيقات الهندسية والعلمية. على الرغم من أن الخوارزمية مصممة خصيصًا لهذا النوع من المصفوفات وقد تتطلب بعض الاحتياطات لضمان الاستقرار العددي، إلا أنها تظل خيارًا ممتازًا لحل هذه الأنظمة بكفاءة.