خوارزمية جديدة تعتمد على الطرق المباشرة لحل الأنظمة الخطية المتناثرة

العناوين الأخرى

A new algorithm based on direct methods for soving sparse linear systems

مقدم أطروحة جامعية

الداود، عصام فالح سعيد

مشرف أطروحة جامعية

الطويق، محمد حسن

أعضاء اللجنة

العلاونة، أحمد
البصول، عدنان أحمد
الطعاني، علي

الجامعة

جامعة آل البيت

الكلية

كلية العلوم

القسم الأكاديمي

قسم الرياضيات

دولة الجامعة

الأردن

الدرجة العلمية

ماجستير

تاريخ الدرجة العلمية

1998

الملخص العربي

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

و من المفيد في حل الأنظمة الخطية المتناثرة إعادة ترتيب الصفوف و الأعمدة للتقليل من التعبئة و ذلك للأسباب التالية : 1.

التقليل من السعة التخزينية اللازمة لحل النظام 2.

تحقيق دقة أفضل، و ذلك لارتباط عدد عناصر المصفوفة A بالخطأ الناتج عن تحليلها. 3.

التقليل من الزمن اللازم لحل النظام بسبب انخفاض عدد العمليات الحسابية و العناوين غير المباشرة عندما تقل العناصر المتولدة في النظام المتناثر. و قد ظهر العديد من البرمجيات تعتمد على الطرق المباشرة مثل : MA 28 SPARSPAK, Y12Mحيث بينا الإيجابيات و ال سلبيات لكل منها، و المخططات و التقنيات المتبعة. و نقدم في هذا البحث خوارزمية جديدة تمتاز بما يلي : 1.

الفعالية في حل الأنظمة الخطية المتناثرة بشكل عام. 2.

التقليل من عمليات البحث عن العنصر المطلوب. 3.

تسريع التقارب في خطوات التحسين المتكرر في الأنظمة بطيئة التقارب. 4.

استخدام تبديل الصفوف و الأعمدة و ثابت الإسقاط معا للتقليل من التعبئة أثناء تحليل المصفوفة إلى LU. 5.

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

تعديل مخطط القوائم المترابطة لتخزين الأنظمة الخطية المتناثرة : حيث بينا أنه باستخدام المخطط المعدل يمكن الاستغناء عن عملية البحث عن العصر السابق في صف و عمود العصر الجديد، كما أن عمليات تبديل الصفوف و الأعمدة تتم بسهولة و سرعة. 2.

إتباع خطوات جديدة في تحليل المصفوفة إلى LU بحيث تتناسب مع مخطط التخزين : نلاحظ أن اتباع الطريقة المعتادة في التحليل تجعل تكلفة التحليل عالية جدا من الناحية الزمنية مما يجعل هذا المخطط غير مجدي، و على سبيل المثال في الخطوة k من تحليل المصفوفة الكثيفة إلى LU نحتاج بالمعدل للبحث عن عنصر واحد إلى (n + 1) / 2 عملية اختبار، و لتشكيل العمود k من المصفوفة السفلى نحتاج إلى (k – 1) (n-k) (n + 1) عملية اختبار.

و لكن من الممكن تحقيق الحد الأدنى من عمليات البحث لتشكيل العمود k من المصفوفة السفلى و ذلك بعد تعديل خطوات تحليل المصفوفة، و قد بينا تجريبيا أنه باستخدام المخطط المعدل نحتاج إلى ثلث الزمن اللازم لحل النظام باستخدام المخطط السابق. 3.

إعادة تريب الصفوف و الأعمدة : و ذلك بتحسين استراتيجيه أقل صف في أقل عمود باستخدام عتبة الارتكاز، حيث بينا أنه باستخدام ثابت الاستقرار u يقلل من التعبئة في كل خطوة من تحليل المصفوفة و يعطي نتائج باستقرار مقبول مما يجعل عملية تحسين النتائج تتم بسرعة أكبر . 4.

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

التخصصات الرئيسية

الرياضيات

الموضوعات

• بحوث العمليات
• البرمجة الخطية
• الرياضيات
• التحليل العددي
• الجبر
• المصفوفات
• برمجيات الحاسوب
• البرمجة الديناميكية

عدد الصفحات

52

قائمة المحتويات

• APA
• MLA
• AMA

لغة النص

العربية

نوع البيانات

رسائل جامعية

رقم السجل

BIM-310119