التحسين التكراري

التحسين التكراري هو أسلوب تكراري اقترحه جيمس إتش. ويلكنسون لتحسين دقة الحلول العددية لأنظمة المعادلات الخطية . ^{[ 1 ] [ 2 ]}

عند حل نظام خطي${\displaystyle A\mathbf {x} =\mathbf {b} \,,}$بسبب التراكم المضاعف لأخطاء التقريب ، فإن الحل المحسوب${\displaystyle {\hat {\mathbf {x} }}}$قد ينحرف أحيانًا عن الحل الدقيق${\displaystyle \mathbf {x} _{\star }\,.}$بدءاً من${\displaystyle \mathbf {x} _{1}={\hat {\mathbf {x} }}\,,}$تحسب عملية التحسين التكراري سلسلة${\displaystyle \{\mathbf {x} _{1},\,\mathbf {x} _{2},\,\mathbf {x} _{3},\dots \}}$والتي تتقارب إلى${\displaystyle \mathbf {x} _{\star }\,,}$عند استيفاء افتراضات معينة.

ل${\displaystyle m=1,2,3,\dots \,,}$تتكون الدورة رقم m من عملية التحسين التكراري من ثلاث خطوات:

يكمن السبب الرئيسي لخوارزمية التحسين في أنه على الرغم من أن حل c _m في الخطوة  (ii) قد يعاني بالفعل من أخطاء مماثلة لتلك التي يعاني منها الحل الأول،${\displaystyle {\hat {\mathbf {x} }}}$بالمقارنة، فإن حساب الباقي rm في الخطوة (i) دقيقٌ عدديًا تقريبًا: قد لا تعرف الإجابة الصحيحة تمامًا، لكنك تعرف بدقة مدى بُعد الحل الذي بين يديك عن النتيجة الصحيحة ( _b ) . إذا كان الباقي صغيرًا بمعنى ما، فلا بد أن يكون التصحيح صغيرًا أيضًا، ويجب على الأقل أن يُقرّب التقدير الحالي للإجابة، xm _، من الإجابة المطلوبة. ${\displaystyle \mathbf {x} _{\star }\,.}$

ستتوقف التكرارات من تلقاء نفسها عندما يكون الباقي r _m يساوي صفرًا، أو قريبًا بما يكفي من الصفر بحيث يكون التصحيح المقابل c _m صغيرًا جدًا بحيث لا يغير الحل x _m الذي أنتجه؛ بدلاً من ذلك، تتوقف الخوارزمية عندما يكون r _m صغيرًا جدًا بحيث لا يقنع عالم الجبر الخطي الذي يراقب التقدم بأنه من المجدي الاستمرار في أي تحسينات أخرى.

لاحظ أن معادلة المصفوفة التي تم حلها في الخطوة (ii) تستخدم نفس المصفوفة${\displaystyle A}$لكل تكرار. إذا تم حل معادلة المصفوفة باستخدام طريقة مباشرة، مثل تحليل تشوليسكي أو تحليل LU ، فإن عملية التحليل المكلفة حسابيًا لـ${\displaystyle A}$يتم ذلك مرة واحدة، ثم يُعاد استخدامه في عملية التعويض الأمامي والخلفي غير المكلفة نسبيًا لحل المعادلة c _m في كل تكرار. ^{[ 2 ]}

كقاعدة عامة، ينتج عن التحسين التكراري لحذف غاوس حلاً صحيحاً بدقة العمل إذا تم استخدام ضعف دقة العمل في حساب r ، على سبيل المثال باستخدام دقة الفاصلة العائمة الرباعية أو المزدوجة الموسعة IEEE 754 ، وإذا لم تكن A سيئة التكييف للغاية (ويتم تحديد التكرار ومعدل التقارب بواسطة رقم حالة A ). ^{[ 3 ]}

بصورة أكثر رسمية، بافتراض  إمكانية حل كل خطوة (ii) بدقة معقولة، أي من الناحية الرياضية، لكل m ، لدينا $${\displaystyle A\left(I+F_{m}\right)\mathbf {c} _{m}=\mathbf {r} _{m}}$$

حيث ‖F _m ‖ _∞ < 1 ، فإن الخطأ النسبي في التكرار m من عملية التحسين التكراري يحقق الشرط التالي: $${\displaystyle {\frac {\lVert \mathbf {x} _{m}-\mathbf {x} _{\star }\rVert _{\infty }}{\lVert \mathbf {x} _{\star }\rVert _{\infty }}}\leq {\bigl (}\sigma \,\kappa (A)\,\varepsilon _ {1}{\bigr )}^{m}+\mu _{1}\,\varepsilon _{1}+n\,\kappa (A)\,\mu _{2}\,\varepsilon _{2}}$$

أين

• ‖ · ‖ _∞ يرمز إلى المعيار اللانهائي للمتجه،
• κ (A)هورقمالحالة اللانهائي لـA،
• n هو رتبة A ،
• يمثل ε ₁ و ε _{2 عمليات} تقريب الوحدة لعمليات حسابية ذات فاصلة عائمة ،
• σ و μ ₁ و μ ₂ هي ثوابت تعتمد على A و ε ₁ و ε ₂

إذا كانت A "ليست سيئة التكييف للغاية"، وهو ما يعني في هذا السياق

وهذا يعني أن μ ₁ و μ ₂ من رتبة الواحد.

يهدف التمييز بين ε1 _و ε2 إلى _{السماح بتقييم} rm بدقة مختلطة ، حيث تُحسب _{النتائج} الوسيطة بتقريب الوحدة ε2 قبل تقريب النتيجة النهائية (أو اقتطاعها) بتقريب الوحدة ε1 . ويُفترض _أن جميع العمليات الحسابية الأخرى تُجرى بتقريب الوحدة _{ε1 .}