جبر خطي رياضيات طرق عددية معادلات تفاضلية

الاسترخاء المتتالي المفرط (Successive Over-Relaxation (SOR))

- SOR, استرخاء, جاوس-سيدل, حل المعادلات, معامل الاسترخاء

مقدمة

في مجال الجبر الخطي العددي، تُعتبر طريقة الاسترخاء المتتالي المفرط (SOR) تعديلًا لطريقة جاوس-سيدل لحل أنظمة المعادلات الخطية. تُستخدم هذه الطريقة على نطاق واسع في حل المعادلات التفاضلية الجزئية الناتجة عن نماذج رياضية للعديد من الظواهر الفيزيائية والهندسية. تهدف SOR إلى تسريع تقارب الحلول من خلال إدخال معامل استرخاء، مما يسمح بالتحكم في حجم التحديثات التي يتم إجراؤها على قيم المتغيرات في كل تكرار.

الأساس النظري لطريقة SOR

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

Ax = b

حيث A هي مصفوفة المعاملات، x هو متجه المتغيرات المجهولة، و b هو متجه الثوابت. يمكننا تقسيم المصفوفة A إلى ثلاثة أجزاء:

A = D – L – U

حيث D هي مصفوفة قطرية تحتوي على عناصر القطر الرئيسي للمصفوفة A، و L هي مصفوفة مثلثية سفلية تحتوي على العناصر الموجودة أسفل القطر الرئيسي، و U هي مصفوفة مثلثية علوية تحتوي على العناصر الموجودة فوق القطر الرئيسي.

باستخدام هذا التقسيم، يمكننا إعادة كتابة نظام المعادلات كالتالي:

(D – L – U)x = b

ثم، نعيد ترتيب المعادلة للحصول على صيغة تكرارية:

Dx = (L + U)x + b

x = D-1(L + U)x + D-1b

في طريقة جاوس-سيدل، يتم استخدام القيم المحدثة للمتغيرات فور توفرها في كل تكرار. أما في طريقة SOR، يتم إدخال معامل الاسترخاء ω (أوميغا) لتعديل التحديث كالتالي:

x(k+1) = (1 – ω)x(k) + ω(D-1(L + U)x(k) + D-1b)

حيث x(k) هو متجه المتغيرات في التكرار k، و x(k+1) هو متجه المتغيرات في التكرار التالي k+1.

يمكن تبسيط هذه المعادلة إلى:

x(k+1) = (D – ωL)-1[(1 – ω)D + ωU]x(k) + ω(D – ωL)-1b

معامل الاسترخاء (ω)

يُعتبر معامل الاسترخاء ω هو المفتاح لأداء طريقة SOR. قيمته تؤثر بشكل كبير على سرعة التقارب. بشكل عام:

  • إذا كان ω = 1، فإن طريقة SOR تصبح مماثلة لطريقة جاوس-سيدل.
  • إذا كان ω < 1، فإن الطريقة تُعرف باسم “الاسترخاء السفلي” (Under-relaxation). يمكن أن يكون هذا مفيدًا عندما تتباعد طريقة جاوس-سيدل، حيث يساعد على تهدئة التذبذبات وتقريب الحل.
  • إذا كان ω > 1، فإن الطريقة تُعرف باسم “الاسترخاء المفرط” (Over-relaxation). يهدف هذا إلى تسريع التقارب، ولكن يجب اختيار قيمة ω بعناية لتجنب التباعد.

إيجاد القيمة المثالية لـ ω ليس بالأمر السهل ويعتمد على خصائص المصفوفة A. توجد بعض الطرق التحليلية لتقدير هذه القيمة، خاصة في حالات خاصة مثل مصفوفات بوزيتيف ديفينيت (Positive definite) و مصفوفات ذات خصائص معينة. غالبًا ما يتم استخدام التجربة والخطأ لتحديد قيمة مناسبة لـ ω.

خوارزمية SOR

لتوضيح كيفية تطبيق طريقة SOR، يمكن تلخيص الخوارزمية في الخطوات التالية:

  1. الإعداد:
    • حدد مصفوفة المعاملات A ومتجه الثوابت b.
    • حدد قيمة معامل الاسترخاء ω.
    • حدد معيار التقارب ε (إبسلون) (مثل الفرق بين التكرارات المتتالية).
    • حدد الحد الأقصى لعدد التكرارات N.
    • اختر قيمة أولية للمتجه x(0).
  2. التكرار:

    لكل تكرار k = 0, 1, 2, … حتى يتم استيفاء معيار التقارب أو الوصول إلى الحد الأقصى لعدد التكرارات:

    • لكل عنصر i في المتجه x:

      احسب القيمة المحدثة xi(k+1) باستخدام المعادلة:

      xi(k+1) = (1 – ω)xi(k) + ω(bi – Σj<i aijxj(k+1) – Σj>i aijxj(k)) / aii

    • تحقق من معيار التقارب. إذا كان ||x(k+1) – x(k)|| < ε، فتوقف.
    • إذا تم الوصول إلى الحد الأقصى لعدد التكرارات N، فتوقف وأبلغ عن عدم التقارب.
  3. النتيجة:

    إذا تقاربت الخوارزمية، فإن x(k+1) هو الحل التقريبي للنظام Ax = b.

مزايا وعيوب طريقة SOR

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

المزايا:

  • سرعة التقارب: يمكن أن تكون طريقة SOR أسرع بكثير من طريقة جاوس-سيدل، خاصة عند اختيار قيمة مناسبة لمعامل الاسترخاء ω.
  • بساطة التنفيذ: الخوارزمية بسيطة نسبيًا وسهلة التنفيذ في معظم لغات البرمجة.
  • توفير الذاكرة: لا تتطلب طريقة SOR تخزين مصفوفات كبيرة إضافية، مما يجعلها مناسبة للمشاكل الكبيرة.

العيوب:

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

تطبيقات طريقة SOR

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

  • حل المعادلات التفاضلية الجزئية: تُستخدم طريقة SOR لحل المعادلات التفاضلية الجزئية التي تصف الظواهر الفيزيائية مثل انتقال الحرارة، وتدفق السوائل، والانتشار.
  • التحليل الهيكلي: تُستخدم في تحليل الإجهادات والتشوهات في الهياكل الهندسية.
  • معالجة الصور: تُستخدم في بعض خوارزميات معالجة الصور، مثل إزالة الضوضاء وتحسين الحدة.
  • النمذجة المالية: تُستخدم في حل بعض النماذج المالية المعقدة.

مثال توضيحي

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

4x1 – x2 = 1

-x1 + 4x2 – x3 = 6

-x2 + 4x3 = 5

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

A = [[4, -1, 0], [-1, 4, -1], [0, -1, 4]]

x = [x1, x2, x3]

b = [1, 6, 5]

باستخدام طريقة SOR مع ω = 1.25 وقيمة أولية x(0) = [0, 0, 0] ومعيار تقارب ε = 0.001، يمكننا الحصول على الحل التقريبي بعد عدة تكرارات. (هذا المثال يتطلب إجراء العمليات الحسابية يدويًا أو باستخدام برنامج لحل المعادلات).

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

عند تطبيق طريقة SOR، يجب مراعاة بعض الاعتبارات العملية لتحسين الأداء وضمان التقارب:

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

خاتمة

تُعد طريقة الاسترخاء المتتالي المفرط (SOR) أداة قوية لحل أنظمة المعادلات الخطية، خاصة تلك الناتجة عن المعادلات التفاضلية الجزئية. من خلال إدخال معامل الاسترخاء، يمكن تسريع التقارب مقارنة بطريقة جاوس-سيدل. ومع ذلك، يتطلب تطبيق SOR بعناية اختيار قيمة مناسبة لمعامل الاسترخاء ومراعاة بعض الاعتبارات العملية لضمان الأداء الأمثل والتقارب الموثوق.

المراجع

مقالات مرتبطة