الرئيسيةعريقبحث

طريقة تكرارية

☰ جدول المحتويات

في الحوسبة العلمية فرعا من الرياضيات وفرعا من علم الحاسوب، الطريقة التكرارية (Iterative method)‏ محاولات متكررة طريقة لحل مشكلة (على سبيل المثال، إيجاد جذور معادلة أو نظام المعادلات) من خلال إيجاد تقريبية المتعاقبة في حل بدءا من التخمين الأولي.[1] هذا النهج هو على النقيض من الأساليب المباشرة، التي تحاول حل المشكلة عن طريق سلسلة من العمليات المحدودة، وفي حالة عدم وجود أخطاء التقريب، وتقديم حل الدقيقة (مثل حل نظام المعادلات الخطية من الفأس = ب من قبل القضاء غاوسي). أساليب تكراري وعادة ما تكون الخيار الوحيد للمعادلات غير الخطية. ومع ذلك، أساليب متكررة وغالبا ما تكون مفيدة حتى للمشاكل خطي يشارك فيها عدد كبير من المتغيرات (في بعض الأحيان من أجل ملايين)، حيث الطرق المباشرة سيكون مكلفا للغاية (والمستحيل في بعض الحالات) حتى مع القدرة الحاسوبية أفضل ما هو متاح.

نقاط ثابتة جذابة

إذا كان يمكن وضع المعادلة في النموذج و(خ) == خ، خ، وإيجاد حل هو نقطة جذب وظيفة ثابتة و، ثم واحدة يمكن ان تبدأ بنقطة x1 في حوض الجذب العاشر واسمحوا، xn + وسوف 1 == و(xn) لن ≥ 1، وتسلسل (ن) xn ≥ 1 تتقارب إلى الحل x. إذا كانت وظيفة وهو مستمر للاختلاف، شرطا كافيا للتقارب هو أن يحدها بدقة دائرة نصف قطرها الطيفية المشتقة من جانب واحد في حي من نقطة ثابتة. إذا كان هذا الشرط يحمل في نقطة ثابتة، ثم حي صغير بما فيه الكفاية (حوض الجذب) يجب أن يكون موجودا.

الأنظمة الخطية

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

الطرق التكرارية المستقرة

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

طرق فضاء جزئي كريلوف

فضاء جزئي كريلوف أساليب العمل من خلال تشكيل أساس متعامد للتسلسل السلطات المتعاقبة مصفوفة مرات المتبقية الأولي (تسلسل كريلوف). وتشكل بعد ذلك تقريبية إلى حل عن طريق التقليل من المشكلة المتبقية على فضاء جزئي. الأسلوب نموذج أولي في هذه الفئة هي طريقة التدرج المتقارن (م). أساليب أخرى هي طريقة عامة الحد الأدنى المتبقي (GMRES) وأسلوب التدرج biconjugate (BiCG).

التقارب

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

التاريخ

من المحتمل أن أول ظهور لطريقة تكرارية من أجل حلحلة نظام خطي يعود إلى رسالة أرسلها غاوس إلى طلابه. واقترح حل نظام 4 * 4 من المعادلات عن طريق حل مرارا المكون الذي كان أكبر المتبقية.

تأسست بقوة نظرية طرق تكرارية ثابتة في العمل مع دايفيد يونغ التي تبدأ في 1950s. كما اخترع طريقة متدرجة صرفي في 1950s، مع التطورات المستقلة التي Lanczos كورنيليوس، Hestenes ماغنوس Stiefel وإدوارد، ولكن من عدم الفهم لطبيعتها وإمكانية تطبيقها في ذلك الوقت. فقط في 1970s كان من الواضح أن الأساليب القائمة conjugacy تعمل بشكل جيد جدا لالمعادلات التفاضلية الجزئية، وخاصة نوع بيضاوي الشكل.

مراجع

  1. Amritkar, Amit; de Sturler, Eric; Świrydowicz, Katarzyna; Tafti, Danesh; Ahuja, Kapil (2015). "Recycling Krylov subspaces for CFD applications and a new hybrid recycling solver". Journal of Computational Physics. 303: 222. doi:10.1016/j.jcp.2015.09.040.

وصلات خارجية

نماذج لحلول لنظم الخطي يوسف سعد : طرق المتكررة لأنظمة متناثر الخطي، 1st طبعة، 1996 PWS

مقالات ذات صلة

موسوعات ذات صلة :